（计算机应用技术专业论文）互联网络信息挖掘算法的研究.pdf

浙江工业大学学位论文原创性声明 7 4 9 6 8 本人郑重声明：所提交的学位论文是本人在导师的指导下，独立进行研究工 作所取得的研究成果。除文中已经加以标注引用的内容外，本论文不包含其他个 人或集体已经发表或撰写过的研究成果，也不含为获得浙江工业大学或其它教育 机构的学位证书而使用过的材料。对本文的研究作出重要贡献的个人和集体，均 已在文中以明确方式标明。本人承担本声明的法律责任。 作者签名 蔽昭 日期口以年( 月i6 日 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，同意学校保 留并向国家有关部门或机构送交论文的复印件和电子版，允许论文被查阅和借 阅。本人授权浙江工业大学可以将本学位论文的全部或部分内容编入有关数据库 进行检索，可以采用影印、缩印或扫描等复制手段保存和汇编本学位论文。 本学位论文属于 1 、保密口，在年解密后适用本授权书。 2 、不保密囤。 ( 请在以上相应方框内打“”) 日期：瓣r 月偌日 日期：加孵罗月7 日 镳断 戚爱 孙缸签签者师怍导 互联弼络信息挖掘算法研究 互联网络信息挖掘算法的研究 摘要 随着社会进步和互联网络的快速发展，i n t e r n e t 已经达到大约有 8 0 亿个网页和5 6 0 亿个超链接的规模，并且随着时间推移，其网页 的数量和超链接的规模将来会变得更加庞大。如何让这个庞大的互联 网络更好地为人类服务，己成为世界关注的热点问题。一方面是人们 希望能快速、准确而全面获取信息，另一方面却是互联网络上信息的 纷繁芜杂，难于取舍。从早期的国内外对互联网络的使用情况来看， 大多数仍停留于很初级的互联网络信息搜集的层次上，需要耗费大量 的人力，手工进行网页分类，采用机械的关键词匹配等方法，缺乏知 识处理能力和理解能力，缺少对网络信息的挖掘和利用，智能化程度 很低。因此，为了提高巨联网络的利用程度，对互联网络信息进行挖 掘无疑成为当前的一个研究热点。 本文首先介绍了在互联网络信息挖掘研究领域的3 大研究方向： 互联网络结构挖掘、互联网络日志挖掘、互联网络内容挖掘，并选择 本文研究的重点是互联网络结构挖掘。然后，着重回顾了互联网络结 构挖掘领域的当前发展现状，详细阐述了该领域中最著名的两种挖掘 算法：p a g e r a n k 算法和h i t s 算法。并在此基础上，针对p a g e r a n k 算法的一些不足，提出相应的改进算法： ( 1 ) 针对p a g e r a n k 算法偏重旧网页，本文将网页的发布日期引 互联网络信息挖掘算法研究 入算法，提出“具有时间反馈的p a g e r a n k - t i m e s 算法”。该算法主要 针对网页内容的重要性与网页发布时间紧密相关的网页( 比如新闻网 页) ，而对其他的网页就不是很有效了，这也是这个算法的不足之处。 详见本文的第四章。 ( 2 ) 针对p a g e r a n k 算法容易出现“主题漂移”现象，将网页间 的相似度计算引入算法，并对不同的相似度模型进行比较，提出“基 于相似度分析的t - p a g e r a n k 算法”。该算法根据链接到的网页的主题 相关性的高低来传递p a g e r a n k 值，使较多的、令用户满意的、有效 的网页集中在整个排序结果集的靠前位置，这样就容易被用户查询 到，从而改善互联网络的p a g e r a n k 值的分布情况，提高查询质量。 实验证明，本文提出的改进算法是有效的。详见本文的第五章。 接着，将介绍本文的实验系统模拟的互联网络搜索引擎， 该系统实现互联网络爬行、网页分析、排序算法实现、搜索查询等功 能。 最后，总结全文，展望互联网络信息挖掘领域的未来发展方向 及未来要做的工作。 关键词：互联网络挖掘，p a g e r a n k ，时间反馈，数据挖掘，相似度 互联网络信息挖掘算法研究 1 1 背景 1 1 1 问题的提出 第一章绪论 互联网络就像是由成千上万个相互连接、交织在一起的细胞组织起来的一个 极其复杂的结构体。它是巨型的世界性产物，不断地迅速发展壮大，不断地包含 全世界不管是个人的、组织的还是国家的知识。今天，它的规模已经发展到包含 大约8 0 亿张网页和5 6 0 亿个超链接。虽然互联网络的发展已经超出了一般人的 想象，几乎包容了整个人类历史所积累的全部知识，但是，它现在还在以每天超 过1 0 0 万张网页的速度增长。 一方面，互联网络上的知识越积越多；一方面，人们在互联网络上找到自己 想要的信息却变得越来越困难，甚至渐渐变成一种灾难。互联网络上有人们需要 的知识，但更多的是人们不需要的知识。对一个互联网络使用者来说，他仅仅用 到了这个互联网络1 的信息量，但却要在这9 9 的无效信息中苦苦搜寻j 无疑 是大海捞针、苦不堪言。同时，由于在传统的电子商务活动中，许多企业、商家 已经积累了大量诸如客户信息、交易记录、访问记录等数据，也没有被充分地加 以利用，无法提升企业的核心竞争力。为了能在残酷的商场上立于不败之地，越 来越多的企业、商家想要将这些数据转换成为有用的信息和知识，为他们的电子 商务决策提供有力支持，以期占领商业竞争的制高点。 于是，互联网络信息挖掘就在这样的环境下应运而生，并迅速成为互联网络 信息检索和信息服务领域的热点。对网络信息挖掘的含义有两种比较典型的看 法： 1 ) 互联网络信息挖掘就是利用数据挖掘技术，自动地从互联网络的文档以及 服务中发现和抽取信息的过程。它涉及到多个研究领域，除了密切相关的机器学 习和自然语言处理领域以外，还有数据库、信息检索、人工智能等研究领域 2 1 。 互联唰络信息挖掘算法研究 2 ) 互联f 回络信息挖掘就是互联网络的数据挖掘，即利用数据挖掘技术从互联 网络的网站上收集的数据中发现潜在的模式和关联。互联网络信息挖掘技术能够 将互联网络上的数据转换成为有用的洞察力和智能，从而描述互联网络上的站点 和访问站点的人，加强站点的导航功能、客户交互的个性化以及保证站点的可靠 性【3 1 。 怠而言之，互联网络信息挖掘就是指在大量样本的基础上，得到数据对象间 的内在特征，并以此为依据进行有目的信息提取过程。例如，当互联网络信息挖 掘系统发现“信息源”，它就会自动过滤掉与“信息源”无关的数据，这样可以 大大减少用户的检索时间和成本。互联网络信息挖掘系统除了处理传统数据库中 的数值型结构化数据外，处理更多的是文本、图像、互联网络信息资源等半结构、 无结构的数据。 从19 9 9 年开始，针对互联网络信息挖掘研究的w e b k d d ( w e bk n o w l e d g e d i s c o v e r y ) 专题讨论会开始与每年的k d d ( k n o w l e d g ed i s c o v e r yi nd a t a b a s e ) 际 研讨会联合举办，其讨论主题也从互联网络信息挖掘一般方法的探讨，深入到面 向电子商务的应用，进而探讨先进的互联网络的用法和用户跟踪技术等。 1 1 2 相关概念的辨析 互联网络信息挖掘和数据挖掘的区别 数据挖掘( d a t am i n i n g ) 又称数据库中的知识发现k d d 是指从大型数据库或 数据仓库中提取隐含的、未知的、非平凡的及有潜在应用价值的信息或模式，它 是数据库研究中的一个很有应用价值的新领域，融合了数据库、人工智能机器 学习、统计学等多个领域的理论和技术。由以上的论述可见，互联网络信息挖掘 不同于传统的数据挖掘。数据挖掘针对的是大型数据库中的数据，而互联网络信 息挖掘则针对的是互联网络中的数据。同时，互联网络信息挖掘面对的海量信息 也不全是简单的结构化数据，而常常为半结构化的数据，如文本、图像数据，甚 至是异构型数据；发现知识的方法可以是数学的、非数学的：可以是演绎的、归 纳的。 互联网络信息挖掘与互联网络信息检索的区别 互联网络信息挖掘与互联网络信息检索所采用的技术有很多相似之处，但两 互联删络信息挖掘算法研究 者也有本质的区别。从使用的技术上讲，互联网络信息挖掘沿用了r o b o t 、全文 检索等互联网络信息检索技术中的优秀成果，同时也综合运用人工智能、模式识 别、神经网络等领域的各种新技术；并且，从最终目的上讲，互联网络信息挖掘 系统能够获取用户个性化的信息需求，根据目标特征信息在互联网络上或者信息 库中进行有目的的信息搜寻。 1 2 本文的安排 本文的第二章概述了目前有关互联网络信息挖掘领域的相关内容，指出本文 的研究重点是互联网络信息挖掘领域中的互联网络超链接拓扑结构挖掘。第三章 讨论了互联网络超链接拓扑结构挖掘领域内的主要研究现状及最新研究成果，并 详细介绍了该领域内的两种最主要的算法：p a g e r a n k 算法和h i t s 算法，及相应 的改进算法。第四章和第五章主要介绍本文对p a g e r a n k 算法的若干改进。其中， 第四章针对p a g e r a n k 算法偏重旧网页的缺憾，提出“具有时间反馈的p a g e r a n k 算法”：第五章针对p a g e r a n k 算法容易出现“主题漂移”现象，提出“基于相似 度分析的p a g e r a n k 算法”。并对这两种改进算法进行实验，实验结果证明本文的 改进是有效的。第六章介绍了本文的实验系统一模拟的网络搜索b l 擎，主要出网 络蜘蛛、信息服务器、网页分析器、信息查询器等组成。该系统通过对互联网络 的爬行为本文的算法提供计算数据，并在实验系统上实现相应的p a g e r a n k 算法 和本文的改进算法。在本文的第七章，总结全文的研究工作，展望互联网络超链 接拓扑结构挖掘的发展方向及未来要做的工作。 互联斟络信息挖掘算法研究 第二章互联网络信息挖掘概述 互联网络信息挖掘的三种类型：互联网络内容挖掘和互联网络e t 志挖掘、互 联网络超链接拓扑结构挖掘。 1 ) 互联网络内容挖掘：是从互联网络的文本、图像和组成网页的其它内容中提 取有用信息的过程。 2 ) 互联网络日志挖掘：是根据互联网络的网站用户如何使用该网站的内容来提 取有用信息的过程。 3 ) 互联网络超链接拓扑结构挖掘：是从互联网络的超链接拓扑结构中提取有用 信息的过程。 三种互联网络信息挖掘类型之间的关系，见表2 1 挖掘类型数据来源数据形式数据对象l | 殳集 【互联网络内容挖掘网页内容文本索引网页集 l 互联网络日志挖掘访问形式点击流用户行为日志数据库 l 互联网络超链接拓扑结构挖掘拓扑结构超链接有向图超链接集 表2 。1 三种互联网络信息挖掘类型之间的关系表 2 1 互联网络内容挖掘 互联网络内容挖掘即从互联网络的文本、图像和组成网页的其它内容中发现 有用信息的过程。互联网络的信息资源类型众多：从互联网络信息源的角度来看， 大量的互联网络信息资源可以直接从互联网络上抓取、建立索引、实现检索服务， 但是还有一些互联网络信息是“隐藏”的，如由用户的提问而动态生成的提问结 果，或是存在数据库中的数据，或是那些私人数据，它们都是无法被索引，从而 无法对它们进行有效的检索服务；从资源形式上来看，互联网络信息内容是由文 本、图像、音频、视频、元数据等形式的数据组成的，因此互联网络内容挖掘可 以认为是一种多媒体数据的挖掘形式。 互联网络内容挖掘实际上有二个方面：互联网络网页内容挖掘和互联网络信 互联网络信息挖掘算法研究 息检索。 2 ；1 1 互联网络网页内容挖掘 互联网络网页内容挖掘也称互联网络信息提取( w e bi n f o r m a t i o ne x t r a c t i o n ) ， 是从各仓互联网络网页中提取出有用信息的过程，即常规意义上的数据挖掘技术 在互联网络上地应用。 由于每一个互联网络的网站都是一个复杂的、具有自己组织特点的数据源， 从而整个互联网络可以看成是一个庞大的、异构的分布式数据库。但是，传统的 数据库数据都是以结构化的形式存储，有统一的格式，便于查询和访问，也便于 数据库挖掘技术地应用；而互联网络的数据则往往以非结构化的形式出现，具有 动态、不完全、混沌的特点和巨大、分层、多维的形式，显然传统的数据库管理 系统是难以实现对其操纵和管理，因此针对传统数据库的数据挖掘技术也就不能 直接用到互联网络的数据挖掘上来。所以，为了能把传统的数据库挖掘技术应用 到互联网络的信息挖掘上来，就需要解决以下两个问题：如何完成分布式数据挖 掘的问题；如何解决非结构、半结构化数据挖掘的问题。 分布式数据挖掘 所谓分布式数据挖掘就是使用分布式计算，从分布式数据库中发现知识的过 程。典型的挖掘算法分2 个步骤： ( 1 ) 局部数据分析，生成局部数据模型； ( 2 ) 组合不同数据站点上的局部数据模型，得到全局数据模型。 非结构、半结构化数据挖掘 目前各互联网络的站点主要是以h t m l 、x m l 等文本格式存放半结构化数 据的。另外，随着互联网络的快速发展，诸如p p t 、w o r d 、p d f 、e m a i l 等 文件、音频、视频等多媒体信息以及e r p 、c r m 等应用软件数据库信息也大量 地出现。因此，互联网络网页内容挖掘也主要归结为互联网络文本内容的挖掘。 互联网络文本内容挖掘是基于文本信息的知识发现。它利用智能算法( 如神经网 络) ，基于案例的推理、可能性推理等，并结合文字处理技术，分析大量的非结 构化文本源( 如文档、电子表格、网页等) ，抽取或标记关键字概念、文字间的 关系，按照内容对文档进行分类，以获取有用的知识和信息。 互联网络信息挖掘算法研究 目前，互联网络文本内容挖掘除了用于进行文本分类外，主要用于自动生成 网页文本的摘要。互联网络的文本摘要通常应用在互联网络信息检索中，目前多 采用基于统计的自动生成方式，其基本思想就是把文中与主题思想密切相关的句 子( 这样的句子往往位于文中的特殊位置，比如结论性的句子、标题、子标题以 及段落的开头、结尾等) 挑选出来，判断该句子与文中主题的相关程度，并赋予 不同的权重，然后根据相应的权值评价函数把符合要求的句子组合在、一起，形成 该网页文本的摘要。 最常用的互联网络文本内容挖掘方法是基于文档特征向量空问模型( c v s m ： c h a r a c t e r i s t i c v e c t o rs p a c e m o d e l ) 的，主要的步骤有： ( 1 ) 向量表示。从互联网络的文本中提取反映该文本内容的有效特征项，一 般可以选择字、词或词组作为文本的特征项。根据实验结果显示，普遍认为选取 词作为特征项要优于字和词组。对于汉语文本，就首先要将文本分词，形成特征 向量的维数，并将这些词在文中的出现次数( 即词频) 作为该特征向量相应维上 的值。词频分为绝对词频和相对词频：绝对词频即是词在文本中出现的频率；相 对词频为归一化的词频，其计算方法主要运用t f i d f 公式。 f 2 1 特征提取。用上述方法( 1 ) 表示出来的向量空间的维数相当大，可以达 到几万维，而且不同的词对要进行的互联网络文本内容挖掘的贡献也是不同的， 需要赋予其不同的权值，因此要进行向量空间的降维和权值的调整处理。这个过 程主要是通过对训练数据集上的统计来计算每一维的某种特征值，根据指标值的 高低决定是否保留相应的字或词，或者对相应维的权值进行调整，从而实现特征 项的选择和提取。目前存在多种筛选特征项的算法，如根据词和类别的互信息量 判断、根据词熵判断、根据k l 距离判断等。通常，用以上方法得到的特征项集 还可能数目巨大，有时还要进行缩减。其算法一般是构造一个评价函数，对每个 特征向量进行评估，然后根据评估值的大小选取一定数量或超过阀值的特征向量 子集。评估函数有多种，如信息增益、期望交叉熵、文本证据权、几率比及词频 等。最后将结果将存入文档矢量库，形成结构化的文档特征数据集。 2 1 2 互联网络信息检索 互联网络信息检索( w e bi n f o r m a t i o nr e 扛i e v a l ) 也称互联网络信息发现或查 互联嘲络信息挖掘算法研究 询，是根据用户的查询要求找出有关互联网络文档的位置，并自动生成索引。它 的一般过程是：用户向互联网络信息检索系统提出查询条件，由系统调用搜索引 擎开始工作，然后把搜索结果提交给用户。互联网络信息检索的关键在于自动生 成互联网络文档的索引。 2 2 互联网络日志挖掘 互联网络日志挖掘是根据互联网络的网站用户如何使用网站内容来提取有 用信息的过程。在互联网络的服务器上囤积了大量的用户访问记录，这些记录都 符合通用日志格式( c o m m o nl o gf o r m a t ，c l f ) ，包含了基本的客户访问信息( 客 户端i p 、客户端机器名、访问时间、访问资源的u r l 和用户的浏览器版本等) 。 互联网络日志挖掘的主要目的是通过日志挖掘的方法获得用户在互联网络上的 测览模式，了解用户在互联网络上的行为，以便为站点管理者提供改进意见，增 加个性化服务，或者在电子商务中发现潜在的客户群等。尽管互联网络日志挖掘 类似于传统的数据挖掘，但主要处理的是半结构或无结构的数据，所以在算法的 设计时还要涉及许多数据预处理工作，相对复杂点。 互联网络目志挖掘过程一般分为4 个阶段，即预处理阶段、事务识别阶段、 挖掘算法实施阶段和模式分析阶段，图2 1 是互联网络日志挖掘的过程图 图2 1 互联网络日志挖掘的过程图 互联网络信息挖掘算法研究 2 2 1 数据预处理阶段 该阶段的主要任务是从原始的日志文件中选取出可供用户浏览模式发现算 法使用的规范化数据，其结果将直接影响到算法产生结果的准确度与可信度，主 要包括数据净化、用户识别、会话识别和路径补充等过程。 ( 1 ) 数据净化过程 该过程就是删除用户浏览模式发现算法不需要的数据，通常有下面几种情 况： 一般情况下用户不会显式请求站点中的图形文件和网页样式文件，这些 文件通常是站点根据请求网页的链接自动下载的，所以需要将请求项中 以j p g 、d p e g 、g i f 等结尾的记录都删除。 用户请求访问失败的数据记录。 用户请求方法中不是g e t 的数据记录。 ( ”用户识i l 过程 该过程是把用户和请求的网页相关联的过程，其中主要处理多个用户通过代 理服务器或防火墙访问互鞋网络站点的情况。在用户识别的过程中，不仅需要服 务器几志文件，还需要知道该站点的拓扑结构。 ( 3 ) 会话识别过程 该过程是将一个用，h 在段时间内所有的请求网页进行分解以得到用户会 话。 ( 4 ) 路径补充过程 该过程就是将请求的网页因为本地或代理服务器缓存所造成的路径遗漏请 求页补充完整。 执行上面的四步操作后，就得到了事务识别阶段所需的输入信息一用户会话 文件，该文件中包含访问互联网络站点的用户、用户请求的网页、请求发生的顺 序、每一页的浏览时间等信息。 互呋剐络信息挖掘算法研究 2 2 2 事务识别阶段 该阶段是对用户会话进行语义分组，产生用户事务。例如在市场分析中，事 务的含义是用户一次结帐时购买的所有物品。在互联网络日志挖掘领域中，惟一 具备自然事务特征的对象就是用户会话，但是这个用户会话对于关联规则挖掘任 务来说显然是粒度太粗了，所以需要特定的算法将它分割为更小的事务。分割后 事务的具体意义是：用户为获得一项有意义的信息所点击的网页序列，包就是用 户会话中的每一次前进浏览的第一页到回退的前一页组成的路径。例如一个用户 会话中请求的网页顺序是a b a c d c ( 用大写字母标记网页) ，则对应 的事务为a b 和a c - d 。这种方法的基本模型是事务中的最后一页是内容页 ( 也叫做最大向前引用页) ，在此之前的网页都是辅助页。这种事务也叫最大向 前引用路径( 简称m f p ) 。 2 2 3 挖掘算法实施阶段 该阶段是对事务识别阶段的结果施用挖掘算法产生关联规则和模式的过程。 在这一阶段的结果中既包括一般的统计，如每个网页的访问数、最频繁访问的网 页、每个网页的平均浏览时间等，也包括其他的一些挖掘结果，如序列模式、关 联规则、聚类等。 2 2 4 模式分析阶段 该阶段通过分析挖掘算法计算得到的关联规则和模式，提取有意义的、感兴 趣的关联规则与模式作为挖掘结果。 以上就是互联网络日志挖掘的全过程。互联网络目志挖掘也可以结合其他数 据库( 如客户数据库、电子商务数据库、银行数据库等) 一起进行挖掘，以获得 更详细的信息( 如用户的性格与他在互联网络上进行浏览的行为有什么联系? 哪 一个广告条带来的收益最高? 等) 。 因此，从上面的论述可以看出，通过挖掘互联网络的网站曰志可以发现非常 有价值的潜在信息。 互联列络信息挖掘算法研究 2 3 互联网络超链接拓扑结构挖掘 随着互联网络的不断发展，人们越来越多地在互联网络上发布和获取信息。 互联网络已经成为信息制造、发布、加工和处理的主要平台。传统的互联网络信 息挖掘技术大多是基于互联网络文档内容的，与经典的信息检索技术和数据库技 术有着密切的联系。但是，互联网络中存在的许多特有问题，诸如非结构化文档、 良莠不齐的阏页质量、包含在文档中的大量多媒体信息、甚至相当含糊或不规范 帘鼯户奄铺表示等，都使得经典的信息检索技术和数据库技术在互联网络中很难 有效地应用。 另一方面，互联网络又包含了在传统数据环境所没有的另一种特征信息，即 互联网络的超链接拓扑结构。互联网络的超链接既是引导用户进行网页浏览，又 反映了网页创建者的一种判断，有理由认为：如果网页a 存在一条超链接指向 网页b ，那么网页a 的作者是认为网页b 包含了对网页a 有价值的信息。 闻此，充分利用互联网络的超链接拓扑结构进行互联网络信息挖掘迅速成为 当前的一个研究热点。目前，对该领域的研究主要集中在p a g e r a n k 算法和h i t s 算法这两种影响相当广泛的超链接分析算法上，其中又以p a g e r a n k 算法更为著 名，它是搜索引擎g o o g l e 的核心算法。在本文的下一章将重点介绍这两个算法 及其最新研究成果。 ：! = i = 联网络信息挖掘算法研究 第三章网络结构挖掘现状研究 目前，由于互联网络的快速发展，它已经是一个名副其实的超级数据中，t b 了。 人们对能有效快捷地在互联网络上发现、获取自己想要的信息的要求越来越迫 切，关于这方面的研究也越来越多的受到人们的重视。其中一个比较有效的方法 就是通过对互联网络超链接拓扑结构的挖掘，获取互联网络中的权威网页，在用 户查询时将相关领域内的权威网页作为查询结果推荐给用户，提高用户查询的质 量。这就是所渭的互联网络超链接拓扑结构挖掘，其中涉及到的算法主要有 p a g e r a n k 算法和h i t s 算法。下文将主要介绍有关这两种算法的当前研究状态。 3 1p a g e r a n k 算法研究现状 3 1 1p a g e r a n k 算法介绍 p a g e r a n k 算法 3 1 是最早并且成功地将超链接分析技术应用到商业搜索引擎 叶l 的算法。它应用传统情报检索理论中的引文分析思想，试图为搜索引擎所涵盖 的每个网页赋严一个量化的重要性度量值，作为最后网页输出排序时的参考。 基本原理 传统情报检索理论中确定学术文献权威性的重要方法之一就是引文分析方 法，它根据引文的数量来确定文献的权威性。p a g e r a n k 算法的发明者p a g e 对互 联网络超链接拓扑结孝句和文献引文分析机制的相似性进行了研究，把引文分析思 想借鉴到互联网络网页重要性的计算中来，利用互联网络自身的超链接拓扑结构 给所有的网页确定一个重要性的等级数。当从网页a 链接到网页丑时，就认为 “网页a 投了网页b 一票”，增加了网夏b 的重要性。最后根据网页的得票数评 定其重要性，以此来帮助实璐排序算法的优化，而这个重要性的量化指标就是 p a g e r a n k 值。 但是互联网络上的网页和学术论文的差别很大。首先学术论文的出版发表是 非常严格的，而网页的发布非常自由、成本很低并缺乏控制，用一个简单的程序 互联剐络信息挖掘算法研究 就可以产生大量的网页和超链接。另外学术论文的引文一般和该文的领域有关 系，而网页的超链接范围却可以很广。 可见简单的超链接数量计算并不能客观真实地反映互联网络中网页的重要 性，所以p a g e r a n k 算法除了考虑网页得票数( 即超链接) 的纯数量之外，还要分 析为其投票的网页的重要性，因为网页的重要性决定着同时也依赖于其他网页的 重要性，重要的网页所投的票有助于增强其他网页的“重要性”。简单地说 p a g e r a n k 算法就是要从互联网络的超链接结构中计算出网页的重要性。 算法描述 p a g e r a n k 算法采用的数学模型是随机网上冲 ) 良( s u r f e r ) 模型。具体来说，如果 假设冲浪者跟随超链接进行了若干步的浏览后转向一个随机的刚页，冲浪者又重 新跟随超链接浏览，那么这个网页的价值程度就由该网页被随机冲浪者访问到的 频率所决定。故，可以把整个互联网络看做是一个巨大的有向图结构，每个网页 是这个有向图中的一个结点，网页问超链接关系是有向图的边。所以，这个有向 图g 可以这样定义：对于每个网页构成有向图g 的一个结点；当且仅当网页“ 中包含指向网页v 的超链接时，存在着从“到v 的有向边( “，v ) 。有向图g ，如 图3 - 1 有向图g 对于结点v 来说，结点b ，c ，“对于v 的权值大小都有贡献，因为这3 个结 点都存在到v 的有向边。根据上文所述，可以知道指向某一结点的有向边越多， 该结点( 网页) 的质量越高。 1 9 9 8 年，斯坦福大学的p a g e 和b r i n 提出了p a g e r a n k 算法：某一+ 互联网络 互瞒网络信息挖掘算法研究 上的网页( 文档) 的p a g e r a n k 值等于所有包含指向该网页( 文档) 的源网页( 文档) 的 p a g e r a n k 值与该网页内超链接总数之比的总和，该算法的原文表达如下 定义1 1 1 1 l e tub eaw e bp a g e t h e nl e tf ub et h es e to f p a g e s 比p o i n t st oa n d b ub et h es e to fp a g e st h a tp o i n tt o 1 e tn u = l f u ib et h en u m b e r o ff i n k sf r o m “ a n deb eaf a c t o ru s e df o rn o r m a l i z a t i o n r ( 科) = c 。r ( v ) ， ( 3 1 ) 其中r ) 为网页“的p a g e r a n k 值。 图3 - 2 是文献 1 】中的一个简单p a g e r a n k 值计算图示意图 图3 - 2 一个简单p a g e r a n k 值计算图示意图 如果用矩阵的观点来考察定义1 的话，假设a 为网页“的邻接矩阵，当有边 从“指向v 时， 4 。= 厩，否则一。= 0a 所以公式( 3 1 ) 可表述为 r = c a r( 3 2 ) 可见，r 即是a 关于特征值c 的特征向量。而事实上，我们需要的也正是这 巨联网络信息挖掘算法研究 个特征向量。 但是，这里还有个小问题。考虑如果存在这么一类网页，该类网页中不包含 任何指向其他外部网页的超链接，但包含从外部网页指向该类网页的超链接，使 得互联网络的p a g e r a n k 值只能从外部网页传到该类网页中，而不能传出去。于 是，该类网页就成为沉积( s i n k ) 页，使得互联网络中的p a g e r a n k 值传递过程在 这类沉积网页上永远终止，见图3 - 3 。 图3 - 3 沉淀网页实例 解决这个问题的方法很简单，假如一个随机冲浪者遇到了这种沉积网页，那 么他可以随机地挑选另一个网页并继续他的浏览。为了对那些不是沉积的网页也 一视同仁，这种类型的随机迁跃应该能以相同的概率在任何一个网页上发生。 修改的定义1 定义1 1 1 4 i l e te ( u ) b es o l ：l i ev e c t o ro v e rt h ew e bp a g e st h a tc o r r e s p o n d st oa s o u r c eo fr a n k r ( “) = c 峨“，+ 扭0 ) ( 3 - 3 ) 其矩阵形式为 r = c ( a + e 1 ) r ( 3 4 ) 由矩阵知识可以知道，式( 3 1 ) 、( 3 2 ) 、( 3 3 ) 和式( 3 4 ) 都是收敛的。在 实际计算中，迭代方程组的解在1 5 次迭代之后趋于稳定，在大规模的互联网络 计算中，收敛过程也可以在不超过1 0 0 次的递归内完成。 实例介绍 图3 4 是用于实例计算的有向图g 。 互联网络信息挖掘算洼研究 图3 4 用于实例计算的有向图g 根据公式( 3 1 ) 计算，图o 中各节点的p a g e r a n k 值分布见表3 - 2 名次p a g e r a n k 值文件d 发出链接i d 被链接i d 1o 3 0 41 2 , 3 ，4 ，5 ，72 , 3 ，5 ，6 20 1 7 95 - 1 , 3 ，4 ，61 , 4 ，6 ，7 30 1 6 621 1 ，3 , 4 4 0 1 4 1 3 1 , 21 ，4 , 5 50 1 0 54 2 , 3 ，51 ，5 6o 0 6 l751 70 0 4 56 1 ，5 5 表3 - 2 图g 中各节点的p a g e r a n k 值分布 令r ( i ) 为l d = i 节点的p a g e r a n k 值，则i d = i 节点的p a g e r a n k 值为 i v l ) = r ( 2 ) + r ( 3 ) 2 + r ( 4 ) 4 + r i ：5 ) 2 = 0 1 6 6 + 0 1 4 1 2 + 0 1 7 9 4 ；+ 0 0 4 5 2 盘联网络信息挖掘算法研究 0 3 0 3 7 5 以上就是著名的超链接分析算法予a g e r a n k 算法，虽然该算法已经获得了 巨大的成功，但它还是有许多不足之处。为此，很多专家也都提出了新的以 p a g e r a n k 算法为蓝本的改进算法。 3 1 2p a g e r a n k 算法的改进 上海交通大学的张岭博士对p a g e r a n k 算法的改进 上海交通大学的张岭博士 6 】认为p a g e r a n k 算法递归地计算每个网页的被链 接数目和链接到其他网页的超链接数目( 即有向图g 中各个节点的入度和出度) ， 然后给每个网页计算出一个p a g e r a n k 值，该值代表了一个网页的重要性程度。 虽然这种方法一方面提高了搜索引擎的检索质量；一方面却也导致了检索的两极 分化现象，妨碍新加入到互联网络上高质量网页内容的传播。因为新网页刚被发 布到互联网络上，还没有被其他网页所链接，那么按照公式( 3 1 ) 计算获得的 p a g e r a n k 值就很低，也就很难出现在搜索结果的前面，从而很难被检索用户发 现。为此，张博士提出了一个加速评估算法，它能有效地解决以p a g e r m a k 算法 为代表的超链接分析算法的不足，使得互联网络上有价值的内容可以更快地传 播；同时，一些已陈旧的网页将加速下滑。这种算法保证了互联网络信息检索中 的优胜劣汰，确保向用户提供高质量的查询结果集。 加速评估算法的核心思想是通过分析一组基于时间序列的网页的p a g e r a n k 值的变化情况，预测各个网页在未来一段时期内的期望值，并把它作为搜索引擎 提供给检索服务的有效参数。用户检索时，搜索引擎将按照预测的p a g e r a n k 值 的高低决定一个网页超链接在检索结果中出现的位置。 加速评估算法具体做法是对这组基于时间序列的网页的p a g e r a n k 值进行线 性拟合，拟合出的直线的斜率( 即所谓的加速因子) 代表了该网页的未来发展趋 势：斜率为正，表示该网页重要性在增加；斜率为负，则相反。斜率的绝对值越 大表明该网页的重要性变化越剧烈。加速评估算法计算出每个网页所对应的线性 拟合的直线斜率，并用下一个统计点的p a g e r a n k 值作为当前有效的评估值。加 速评估算法的实质是给予加速因子呈上升态势的网页以额外的奖励；对加速因子 呈下降趋势的网页以额外的惩罚。这样就可以促进并加速互联网络上优质内容的 互联网络信息挖掘算法研究 传播和网页内容的优胜劣汰，克服p a g e r a n k 算法对新内容的迟钝性，提高搜索 引擎信息检索的质量。 但一个网页的加速因子也仅仅反映了该网页的基于时间序列的一个发展趋 势，而整个互联网络是时刻在变动的、是动态的、是混沌的，时间不是互联网络 变化的惟一决定因素。比如，某个突发事件或某个社会热点会一下子传遍互联网 络，但加速评估算法却很难对此有所反映。所以，该算法仅能在一定程度上改善 用户的查询效果，还不能精确描述整个互联网络的特性，提高用户的查询质量。 上海交通大学的宋聚平博士对p a g e r a n k 算法的改进 上海交通大学的宋聚平博士 8 】也提出了自己不同的观点： ( 1 ) p a g e r a n k 算法偏重旧网页。由公式( 3 1 ) 可以看出，决定一个网页 p a g e r a n k 值的主要因素是指向该网页的超链接个数。如果一个网页被放到互联 网络上不久，时间短暂，许多其他网页还没有指向它的超链接，通过公式( 31 ) 计算得出的网页的p a g e r a n k 值也就很低，在搜索引擎返回的结果中往往就会把 它排在较后的位置。这样，返回结果中新的网页反而被放在后面，正好与用户的 需求相反。因为很多情况下，用户想首先看到最新的网页，比如最新的新闻、资 讯。冈此，宋博士认为在通过指向某个网页的超链接来计算该网页的p a g e r a n k 值时，应该考虑到该网页的发布日期。为此，他提出一个网页的日期权重概念， 即 ( 3 5 ) 其中：彤为网页t 的日期权重；c 为搜索引擎对其库存网页列表索取一遍所需 要的时间，即一个访问周期；t 为一个网页被网络蜘蛛( 网络蜘蛛是一个自动搜 索互联网络并下载指定文件的软件) 访问时的日期与该网页的最近更新日期相距 的天数；d 为常数，它的取值受到公式( 3 ：1 ) 0 0 的阻尼因子c 的影响，且也和网络 蜘蛛的访问周期相关。 事实上一旦网页被放到互联网络上以后，很少会对其进行修改，即使修改了， 也不会陔网页的主题进行大的调整，所以，网页的更新很难被认为是因为网页的 主题变化而引起网页更新。同时，采用公式( 3 5 ) 来描述网页的权重也容易引 起网页作者为了提高网页的p a g e r a n k 值而采取作弊手段，频繁更新自己的网页， 导致对网页p a g e r a n k 值的描述出现偏差。 互联网络信息挖掘算法研究 因此，宋博士提出的网页的日期权重所的计算方法是不太切合实际的，本 文的下一章里，将采用宋博士的“在计算网页的p a g e r a n k 值时要考虑到该网页 的发布时间”这一思想，采用新的网页日期权重度量方法，提出具有时间反馈的 p a g e r a n k 算法，详见第四章。 ( 2 ) p a g e r a n k 算法忽视专业站点。由于以c o r n 结尾的站点往往是一些综 合性站点，规模很大，因此，该类站点内的某些网页( 比如网站的首页) 在 p a g e r a n k 算法下往往能取得较高的p a g e r a n k 值。这样，隐含的意思就是以c 0 1 t i 结尾的网站比其他的网站重要。但这个判断依据实际上并不恰当。因为许多 以c o r n 结尾的网站虽然是规模大、领域广的综合性站点，但正是因为其规模大、 领域广，所以很难对一些专业内容做比较的深刻论述，在特定领域内，它与其他 专业站点相比，前者网页的权威性远不如后者。因此，宋博士认为在考虑站点的 权威性要从该站点中所有网页的p a g e r a n k 值来评判，即在搜索引擎的网页列表 库中，如果来自于同一个站点的网页都具有较高的p a g e r a n k 值，刁可以认为该 站点具有较大的权威性。 ( 3 ) 网页中的超链接对网页p a g e r a n k 值的影响。公式( 3 1 ) 中计算网页的 p a g e r a n k 值时，对于同一个网页中指出的超链接的处理并不恰当。如图3 - 5 ，| j ：) 9 页中的超链接对网页p a g e r a n k 值的影响示图 日d 图3 - 5 网页中的超链接对网页p a g e r a n k 值的影响示图 互联捌络信息挖掘算法研究 图3 - 5 中，节点a 、b 、c 、d 、e 表示5 个任意的不同网页，箭头表示网页 间的超链接关系，图3 5 中的( b ) 表示在( a ) 的基础上，网页爿又添加了两个 指向权威网页d 和e 的超链接。从客观上来分析，既然网页a 增加了两个指向 重要网页的超链接，那它本身的p a g e r a n k 值也应该有所增加，但根据公式( 3 1 ) 推导的结果却是：网页a 的p a g e r a n k 值没有变化( 因为指向么的所有网页都没 有发生任何变化) ，相反网页b 的p a g e r a n k 值却减少了许多( 因为网页a 的指 出超链接数目增加了) ，这显然不符合常理的。产生这种情况的主要原因是公式 ( 3 ，1 ) 过于简单地判定一个网页的指出链接对该网页的影响都是负面的。其实 网页所包含的指出超链对于该网页p a g e r a n k 值的影响应该区别对待：如果网页 a 中的一个超链接所指向的网页占在内容上与网页4 的内容相关，则该超链接将 增加网页a 的p a g e r a n k 值；否则，该超链接将减少网页a 的p a g e r a n k 值。因 此，宋博士以厂( ) 表示网页z ，的所有m 个超链接中的第k 个超链接对该网页 的影响剧子，当l 中的第k 个超链接所指向的劂页与t 在内容上相关时，则 。厂a o 为正；当与瓦在内容上无关时，则，( k ) 为负。故，对p a g e r a n k 值的计 算公式( 3 1 ) 修正为 r ( u ) = ( 1 - c ) + c ( r ( 1 ) 一，( ) ) ( 3 6 ) f = ik = l 在该算法的关键就是如何界定两个网页在内容上的相关性，遗憾的是在宋博 士的论文中并没有提到相关的具体算法。受此启发，本文也对网页间的相关性进 行了研究，并提出基于相似度分析的p a g e r a n k 算法，详见第五章。 吉林大学的李凯对p a g e r a n k 算法的改进 吉林大学的李凯 9 1 将用户的选择( 即用户对网页超链接的每一次点击就是对 相应网页的一次选择) 作为影响网页重要性的一个因素。在用户使用搜索引擎时， 每次点击网页超链接的动作( 即用户的口地址与相应的网页编号的关联) 都被 搜索引擎的服务器记录下来。这样，在下次计算网页的p a g e r a n k 值时，就得到 一个新的向量，记为b ，称为全局个性化向量( 其每个分量对应网页的点击次数 与所有网页的点击次数总和之比) ，代表了所有用户对网页选择的合力。则，公 式f 31 ) 修正为 互联瑚络信息挖掘算法研究 r ( “) = c “+ c e ( ) + 6 ( 3 7 ) 但由于用户在察看搜索引擎提供的推荐查询结果时，对网页的每一次点击并 不代表用户对该网页的肯定，因为用户只有浏览了网页才能做出判断。所以，该 算法对那些查询返回错误的查询主题，其结果就是越查越糟糕了。 斯坦福大学的t a h e rh a v e l i w a l a 对p a g e r a n k 算法的改进 美国斯坦福大学的t a h e rh a v e l i w a l at t 0 3 认为由p a g e 提出的p a g e r a n k 算法没 有考虑到用户的查询主题，所以，一些p a g e r a n k 值很高但却与用户查询主题无 关的网页也会出现在最后的推荐结果里，导致查询主题的漂移。为此，他提出一 种主题敏感( t o p i c s e n s i t i v e ) 的p a g e r a n k 算法。算法先根据o p e nd i r e c t e r y 1 列出的1 6 个基本主题向量，为每个网页离线计算出对这些基本主题向量的 p a g e r a n k 值。在用户查询时，算法可以根据用户的输入或查询的上下文，在基 本主题中选择一个最接近的主题代替用户的查询主题。算法的形式化表示为 r ( u ) = m 。x r ( u ) = c m x r ( u ) + ( 1 一c ) s u ( 3 8 ) 其中s 。是网页“的主题敏感向量a 该算法可以有效地避免一些明显的主题漂移现象，比如在查询关键字为“美 洲虎”时，有上下文的指引，算法能明确的区分用户查询的是( 1 ) 美洲虎汽车： ( 2 ) 美洲虎橄榄球队；( 3 ) 美洲虎产品；还是( 4 ) 哺乳动物美洲虎。但是，一 旦失去了上下文的指引，该算法的改进效果就消失了，因为无法有效的对查询主 题进行归类。嗣时，一般的互联网络用户也很难会对自己的查询主题有精确的描 述，这也导致该算法无法在现实中广泛应用。 华盛顿大学的m a t t h e wr i c h a r d s o n 对p a g e r a n k 算法的改进 华盛顿大学的m a t t h e wr i c h a r d s o n 和p e d r od o m i n g g o s 1 2 l 提出了一个结合超 链接和网页内容信息的p a g e r a n k 算法。 该算法的计算形式为 0 ( - ，) = ( 1 - c ) 巧( ，) + c p q ( i ) p q ( i 寸- ，) ( 3 9 ) j 5 8 - 这里乞( f 专，) 指用户在查询主题q 下从网页i 跳转到_ ，的可能性。 ( _ ，) 表示用 户在网页中没有链出超链接时，跳转到- ，的可能性。而j p o ( j