【毕业学位论文】（Word原稿）结合语义相似度的链接分析-计算机网络技术

1 北京大学硕士研究生学位论文 题目： 结合语义相似度的链接分析 姓 名：朱家稷 学 号： 10308194 院 系：信息科学技术学院 专 业：计算机软件与理论 研究方向：计算机网络与分布式系统 导 师：李晓明 教授 2006 年 5 月 2 版权声明 任何收存和保管本论文各种版本的单位和个人，未经本论文作者同意，不得将本论文转借他人，亦不得随意复制、抄录、拍照或以任何方式传播。否则，引起有碍作者著作权之问题，将可能承担法律责任。 3 摘要 链接分析技术 作为文本分析和日志挖掘 技术 的有效补充， 被广泛应用在主题提取、网页分类、资源发现等诸多 息处理任务和服务中。 由于 巨大 、动态变化 和复杂 ， 给链接分析技术带来了很大的挑战。 链接表达了网页 间复杂而隐蔽的关系 。 为了更有效的进行链接分析， 需要 细致的考察并 区分 对待不同的 链接 关系 （后面如何体现？） 。 在本文中 我们 研究 了 链接网页间多种属性，包括 网页的入度、出度分布， 内容相似度 和 链接相似度 等 ， 并且引入了语义相似度 的概念 。 语义相似度 描述了 网页 表达的 潜在主题间的相似程度。 它与内容相似度和链接相似度相关却 又有很大差别 。它更 精 确 的 刻画 了链接网页 间 语义上的关联程度 。 我们用 语义相似度作为区 分 链接 权重的 标准，并将它应用在 改进中。 在 基本框架下，我们提出了如下假设：浏览者在选择链接浏览下一网页时，他以更大的概率选择与当前网页主题相似的 网页链接；并且网页 间 的语义相似度恰好 刻画了网页间主题间的这种 相似程度。 直接计算网页间的语义相似度是 困难的。为此我们计算了链接网页间的内容相似度和链接相似度，并结合当前的研究 成果 探索了 三者间的联系。 我们 发现 接网页间的内容相似度和链接相似度 的 并 且在 实验 中使 用不同的函数来模拟语义相似度和内容相似度之间的关系。 实验证明，改进后的 序在主题提取任务中优于改进前的序 。 关键词： 万维网 ， 搜索引擎， 链接分析，语义相似度， to eb to ebs its a to It if we to In we of we of of in is to We as of it to a a he is of he is is is We of we we of to of in 5 第 1 章 引言 . 7 究背景 . 7 文研究内容 . 8 1 3 本文贡献 . 8 文组织 . 9 第 2 章 相关研究 . 10 掘 . 10 接分析 . 11 型 . 11 量和算法 . 15 接分析的应用 . 19 索引擎 . 20 索引擎发展历史 . 21 索引擎分类 . 22 于 搜索引擎基本原理 . 25 义相似度 . 26 第 3 章 链接结构的特征 . 28 页的链接特征 . 28 接的 性 . 28 页的链入链出分布 . 29 页间的内容相似度 . 29 页的链接相似度 . 30 页的语义相似度 . 31 容相似度、链接相似度和语义相似度之间的联系 . 31 6 页的链接特征 . 32 接网页的 征 . 33 接网页的入度出度分布 . 36 接网页间的 内容相似度 . 36 接网页间的链接相似度 . 38 接网页间内容相似度和链接相似度的关系 . 39 第 4 章 结合语义相似度的链接分析 . 42 缺陷 . 43 合语义相似度的 . 45 式 . 46 合语义相似度的 验 . 49 验数据集和测试集 . 49 验步骤和设置 . 51 验结果 . 52 法总结和启示 . 58 结 . 60 望 . 60 参考资料 . 62 作者就读期间参加的科研项目和发表的论文 . 67 致谢 . 68 7 第 1 章 引言 研究背景 万维网（ 记为 因特网上最成功的应用 。 随着信息的飞速增长，针对 信息检索已成为一个最具挑战的工作。 在对 网页进行分析处理的过程中，传统信息检索领域的技术自然的会被引用进来。但 网页与传统的文档相比 ，人们发现 的网页有一个极大的相异点 链接 。如果我们将每个网页认为是一个节点，每一条 链接 认为是一条有向边，那么整个 构成了一个庞大的有向图。 链接结构对网页分析处理提供了更多的信息和手段。 链接分析技术已应用于多种目的： 衡量特定主题的网页质量。目前的搜索引擎几乎都使用了链接分析技术对返回结果网页进行排序，最重要的有 法。 描述 构特征。比如网页的入度和出度分布， 径， 区等。 网页分类。结合链接信息和内容信息的网页分类的效果高于只基于内容信息分类算法，甚至只依据链接信息的分类效果与内容分类效果相当。（适当的引文 be 网页搜集 。 依据链接信息，可以针对某个主题或特定目的，对 行高效的网页搜集。 个性化。链接分析和用户的 为日志结合，可以更好预测用户意图，以提供更好的用户体验。 8 但同时我们也应该看到目前链接分析的一些局限和缺点： 正由于链接分析技术的成功，使得很多网站为了提高自身的声望，使用了各种 术使原有的链接分析算法产生误差 。 (算法 缺点： 抵抗 性能差？ ) 链接有多种目的和类型，而传统的链接分析算法没有区别对待不同类型的链接，这使得链接分析的结果 与人们的期望之间产生差别。 链接分析技术没有和其 它网页分析技术很好的结合。 (s 本文相信，如果能够改进上述的缺点和局限，链接分析的效果 将会更加明显。本文 的研究工作也是基于这个目标展开的。 文研究内容 本文的研究围绕以下几个方面进行： 分析 接 网页间 的特征 ， 主要包括 链接 网页的内容相似度、链接相似度和语义相似度 。 给出它们的定义和计算公式，并描述三者间的区别和联系。 对 顺沿链接的跳转策略 进行改进：选择链接的 网页跳转 概率不是 均等 的，而是 与 链接网页间的语义相似度 相关 的。 通过 网页间的内容相似度来模拟 语义相似 度， 重新 评估链接权重 和跳转概率， 改进 法。 1 3 本文贡献 本文 在链接分析中 引入 了 链接网页间的语义相似度来 作为链接权重的评判标准，区别对待链接来 提高链接分析的效率。 本文认为网页链接与论文引用的很大区别是链接的 目的和种类更加复杂 。 而通过语义相似度作为链接可信度的参考，在链接分析中，区分对待不同的链接，会提高链接分析的效率。 9 分析 链接 网页间 的 内容相似度、链接相似度和语义相似度 ，考查三者间的区别和联系， 尝试了用 几种函数 来模拟 内容相似度 和 语义相似度 之间的关系，并比较 了 它们的效果 。 利用 语义相似度 改 进 法。 在 随机游走模型中，浏览者沿着链接跳向下一个网页的概率是相同的 。而我们认为，浏览者跳向链接的概率取决 当前网页 与链接网页 间 的语义相似度：浏览者以更大的概率跳向 相似 主题网页的链接（即网页间语义相似度较高的链接）。通过 内容相似度来模拟语义相似度，并重新 评估网页间跳转的概率 来计算 实验证明， 改进后的 于主题提取任务的精度 比原先提高了 5以上。 文组织 本文后面是这样组织的，第 2 章是相关领域的研究；第 3 章讨论网页链接的特征 ，给出 了链接 网 页间各种相似度的定义和计算公式，并用 为 实验 数据 计算和分析 这些相似度 ；第 4 章给出 结合 网页 语义相似度的 进算法和 实验 结果；第 5 章是对本文的总结和对未来工作的展望。 10 第 2章 相关研究 掘 链接分析本身属于一个更大的研究领域的一部分 掘。 掘是应用数据挖掘技术来从 据中抽取有用信息。用于 掘分析的数据种类包括内容数据、结构数据和用 法 数据 3。 因此 掘可以根据要挖掘的数据种类划分为三类 3, 4： 1 容挖掘： 容挖 掘是从 档的内容中抽取有用信息。内容数据是网页要传达给用户的事实集合。它可以包括文字、图片、音频、视频、或者结构记录比如列表或表格等。这个领域的研究经常包括其它学科的技术，比如信息检索（ 自然语言处理（ 2 构挖掘： 典型的 结构是以网页为节点，以连接两个相关网页的链接为边的图。 此外，网页内部也可以根据自身的 签组织为一个树形结构。因此， 构挖掘是从 发现结构信息的过程。这种挖掘既可 在网页的层面上（ 也可以是在链接的层面上（ 3 法挖掘： 法挖掘是应用数据挖掘技术从 据中发现有趣的使用模式，以用来理解和更好的服务于基于 应用需求 3。用法数据跟踪 户在访问 点时的浏览行为，典型的记录包括 户的 所 访问 的 页面和访问时间。 图 1 展示了 掘领域研究的一个 层 次 分类。对于 构挖掘，我们可以把这个领域再划分两个类别，即文档结构分析（比如 链接分析（连接多个文档的链接结构）。如图所示，链接分析主要专 11 注于文档间的链接结构所提取出的信息。但是，链接分析可以与文档结构分析，容挖掘或 法挖掘结合使用。 比如，链接提供的结构信息和 容结合，可以更好的挖掘 用信息和衡量信息质量。 图 1. 掘分类及链接分析在 构挖掘中的 位置 (摘自 2) 接分析 根据 2的总结， 链接分析的研究 包括模型、度量标准及算法，以及应用等。以下给出这些研究的描述。 型 大多数链接分析的 研究都会有一个基本的 构的表示模型，各种度量和算法都基于这个模型衍生而来。 不同类型的模型包括图结构模型，统计模型，网络流模型等。 12 1. 图结构模型 在这一节，我们讨论各种 掘中表示某种概念和信息单元的图结构。图结构包括单节点结构，多节点结构和图中所有节点的结构。 单节点结构 单节点结构模型包括一个单独的节点（网页），以及链向它或从它链出的链接。 个 页是指被大量其它网页链向的网页。 个 页是指链向大量其它网页的网页。 一个好的 页会链向很多 好的 页；而好的 页会被很多好的 页所链向。 概念首先在 30中被引出。单节点模型通常用来决定网页的质量 11, 12, 13。 多节点结构 多节点结构包括多个节点以及它们之间的链接。一些结构和模式已经在 14中讨论。我们下面将描述这些模型和概念： 共同 链入 （ 如果节点 A 同时链向节点 B 和 C，那 么 节点 B 和C 被 A 共同 链入 。在 ，共同 链入 直观上表明网页 B 和 C 间的某种 相 似。 共同 链出（ 如果节点 B 和 C 同时链向节点 A，那么节点 共同链出 A。和共同链入一样，共同链出也表明 网页 B 和 C 间的某种相似。 有向二分图 (如果图 G 可以划分为两个节点集合 ，每条有向边都从 F 中的某个节点 u 链向 C 中某个节点 v，那么图 G 为有向二分图。 13 完全二分图（ 如果二分图 G 包含所有的从 F 链向 C 的边，那么 G 为完全二分图。 二分核（ 核 (i, j)是一个完全有向二分子图，并且 F 中至少包含 i 个节 点，而 C 中至少包含 j 个节点。 在 中，这包含链接的 i 个网页被称为“ 而被链向的 j 个网页被称为“ 从概念角度来说，二分核的“ “ 本就是 页和 页。 对某个主题的网页集合来说，可以寻找二分核来发现该主题的 页核 页。 页和 页表示了这个主题的良好的信息来源。 社区（ 社区是 被 页共同链向的 页 的核心 15。它还被定义被一组网页集合，使得集合 中网页在社区内的链接度（任意方向）大于社区外的链接度 16。 整体图结构 领结模型（ 7, 17提出了 的领结模型，详细描述了的各种属性、度量和方法。领结结构包含一个强连通部分（ 一个链向 部分（ 一个被 向的部分（ 还有一些不相连的部分。 2. 马尔可夫模型（ n 阶马尔可夫链表示系统的下一状态只由当前状态和前 状态决定。 1阶马尔可夫模型通常用来模拟用户的浏览行为。 1和随机 8就使用了基于马尔可夫模型的随机游走过程：用户随机选择跳向某个新网页或跟随链接到某个网页（在 是正向链接，而在随机 根据不同的时间步，选择正向链接或反向链接）。 其它的方法，比如 2也引入了 14 马尔可夫随机游走过程。 19中使用马尔可夫链为自适应网站预测链接。 走模型， 即基于马尔可夫模型的链接跳动，被链接分析 大量 使用 。 3. 最大流模型（ 大流问题可以表述如下：图 G=(V, E)，每条边被赋予为正数的传输能力， s 和 t 是 G 的两个不同节点，问题是要找到从 s 到 t 的最大流能力。 20提出最大流问题等价于“ 题，即从图 G 去掉最小数量的边，使得 s和 t 分割。 已有一些算法被提出来解决这个问题 21, 22。 17, 23中应用这些算法来识别“ 区”，其被定义为“社区内部链接度大于社区外部链接度的网页集合”。 4. 概率关系模型（ 概率关系模型是关系模型和贝叶斯置信网络的结合。 类内部属性的关系合类间属性的关系可以 通过赋予不同的概率分布来建模。 24将网页和链接作为实体，并赋予它们间以关系。一个网页实体的属性包括： ；而链接实体包含属性 示网页实体间的关系。通过预先给出的网页实体 性 的概率分布，可以利用贝叶斯和置信传播方法来进行文档分类。 5. 其它模型 25提出“ 识别 页。 26中定义页为被多个网页链向的网页，且根据 它们的社区中排名靠前；其目的在于识别刚浮现出的社区 。 还有其它一些对 改进 18, 12, 27, 28 , 29在这里不在讨论。 15 量 和算法 链接可以用来作为单个网页、一组网页或整个 构属性的度量标准。例如，链接分析已被用来作为衡量主题网页的权威性、网页知名度和网页间距离的有效工具。已有多种方法利用链接分析来衡量网页质量。一些标准基于 一些基于 构的完全二分图和二分核，还有的基于概率和随机方法。这些度量标准还有一个区别是它 们是否与查询相关。在本节，将给出利用链接信 息的一些的常用 的度量 和算法 。 链接在衡量单个网页、一组网页和整个 的属性上非常有用。平均点击度（ 利用链接结构衡量网页间距离的一种方法。 可以根据度量的元素是单个网页、多个网页和整个 这些度量标准进行分类。 1、 0、 2和网页知名度（ 13用来衡量单个网页的质量。 对网页质量进行 排名 的一个标准。 11使用这个度量 应用于索引擎。其 主要思想是如果 一个网页的所有链入网页的排名总和很高，那么这个网页的排名也会很高。因此一个网页的排名取决于链向它的网页的排名。排名是一个迭代的过程，直到所有网页的排名稳定。 排名的公式如下： 直观上看， 在 上的随机游走的分析方法。表示一个随机冲浪的用户直接跳转的概率，比如通过键入 书签中或特定主页中访问某个网页。 n 表示总网页数。 /n 即表示随机直接跳转到网页 概率 。对所 16 有链向 网页 从 着链接跳转到 概率是 链接出度的倒数，即假设跳向任意链接的概率是相同的。其右面的项则表示 通过链接跳转到网页概率。 而整个 即表示用户停留在网页 概率。 与查询无关的全局值。 33给出计算 高效方法。其它排名标准的稳定性在 18, 27, 34中讨论。根据 18, 34，只要高的网页的链接结构没有改变，那么修改链接结构对排名的影响不大。其中的一个主要原因在于随机直接跳转的存在。 文提到的 可以通过 法来计算。其主要过程是，首先通过查询得到一组相关的网页集合（ 加入 链入链出网页得到扩展的 构造 网页 的 和 可以通过如下公式迭代计算： 法对主题查询的应用是成功的。但有时候会出现“主题漂移”的现象，即一个细节查询的结果可能是其概括问题的结果，或者相反。其原因是 中链接密集处的主题结果。 28, 29中对 的邻接矩阵进行了改进。 1使用了基于 算法来进行 集、网页分类和识别 区。 12提出。它结 17 合了随机游走模型以及 的 样， 是与查询相关的。其主要思想是，在由查询词构成的 图上随机游走，游走者会以较大的概率访问 高质量信息的网页，即 较高的网页；同样，游走者会以较大的概率访问链向较高的 页的网页，即 较高的网页。 它的查询词网页集合的构造与 同，然后以此集合得到一个无向的二分图 G。两种游走方式来计算网页的 。一种是游走于 G 的图部分而生成 ，另一种游走于 G 的 图而生成 执行游走过程时，游走者从二分图的一个部分开始，每步跳跃两条边 第一条边将他带到图 G 的另一部分，而第二条边将他带回原来的部分。利用马尔可夫模型帮助即可估算出游走者访问 图或 图中某个节点的概率。 其游走过程的概率矩阵 H 和 A 表示如下： 通过计算 H 和 A 的主特征向量，即可得到网页的 和 。由于引入了随机游走， 会 出现 “主题漂移”问题。 13中，作者提出了网页在不同主题下“声望”的概念。与 似，它也是执行两阶段随机游走过程，并计算针对某个主题的网页的 望和 望。其每步游走的原理是： 以概率 d0，游走者随机直接跳向某个网页 ； 以概率 1走者从所在网页沿着正向链接或反向链接跳向另一个网页。 18 其 望和 望的定义分别是： 对某个主题，游走者正向游走访问网页 p 的概 率。 对某个主题，游走者反向游走访问网页 p 的概率。 其计算公式在这里就不在列出。 平均点击度（ 在 34中提出用点击度（ of 衡量网页间的距离不能与人们的直觉相符。因为用户以较大的概率沿着链接数较少的网页跳转，而以较小的概率沿着链接数较多的网页跳转。因此，他们提出平均点击度，它基于随机游走中点击某个链接的概率。根据这个模型，定义网页 p 中链接的长度为 。因此网页 p 与 q 间的距离为 p 到 q 的最短路径上的链接长度之和。 平 均点击度可以用来过滤网站以识别一定距离内的 区，也可以用来衡量用户在网站内访问到需要信息的代价，以改善网站的友好性 和可用性 。 信息 气味 （ 信息线索的概念是指利用网页链接周围的信息片断作为“ 气味 ”来评估它链向的网页质量和访问该网页的代价 41。 其基本思想是用户在某个网页搜寻信息时，会跟踪“气味”最浓的链接。“气味”的计算方法是比较用户信息需求与链接信息片断的相似度。 其它 其它一些重要的概念包括网页的共同入度和共同出度。 网页 p 和 q 的共同入度表示同时链向 p 和 q 的网页数 ，共同出度表示 p 和 q 同时链向的网页数。 1 19 中讨论了这些概念。 的属性包括 径，连 通 性、入度和出度分布等。 6, 7, 17给出了 径的讨论，并指出 页的入度和出度分布遵从“ 布。在整个 构研究中，发现 区是一个热点。其主要方法是最大流方法17, 23。 接分析的应用 链接分析技术被广泛应用，包括判断主题网页的质量，网页分类，网页搜集，社区发现，网站 优化，个性化和网页推荐等。本节将介绍一些应用。 主题提取（ 主题提取是从网页集合中识别与主题最相关的网页。在 50中它被定义为“寻找指定主题的密切联系的 页和 页”。 法 30本身就是一种典型的主题提取算法。基于文档对象模型（ 更精细的链接分析算法在 50, 51中讨论。 52改进 出主题相关的法。 网页分类 网页分类是将网页划分到指定的类别中。 53给出了 8 种网页类别和 7 种描述网页特性的属性。 54给出一种基于链接和上下文的自 动网页分类方法，其主要思想是 如果一个网页被其它网页链向，其链接上下文会给予一定的权重，因为它表示某些人通过链接信息而阅读了该网页。 24将网页和链接看作实体关系模型中的实体，并用概率关系模型来进行网页分类。 55给出了利用主题类别和自动分类器来估计整个 的主题分布。 区识别 20 整个互联网存在着成千上万的社区。这些社区有的已经以非常清晰的形式表现出来 (例如，门户网站中的层次目录式结构 )。但是，在极度分散和无序的互联网环境中。有理由认为必然还存在更多潜在的未被发现和定义的互联网社区从互联网中 系统地抽取这些社区至少有以下 3 方面的意义： 这些社区为了解互联网用户的兴趣提供了有价值的，甚至是最及时、最可靠的信息。 这些社区展现了互联网社会学 (of 研究和发现这些社区可以深入了解互联网的进化过程。 门户网站通过识别和区分这些社区，可以更有效地组织它们的目录层次(因为很多潜在的社区以很快的速度在增长，而很多已经清晰出现的社区又在逐渐消失 )。这同时意味着互联网的自动分类成为可能。 主要的社区发现技术有最大流算法 17, 23的和基于 二分有向图 算法 55。 集 “主题搜集”是一种针对特定主题的高效网页搜集方法 50。 在搜集中，需要识别主题中好的 页和 页，还要决定是否跟踪某个链接进行搜集 50。 索引擎 人们带来了巨大的方便，使人们可以跨越时间和空间的界限共享大量的信息。但是，面对如此大量的信息，人们同时也开始感到无所适从。太多的信息使他们很难迅速定位到真正需要的信息，而跟随超链 接 在 漫游则会浪费大量的时间，而且很可能徒劳无功。因此，人们迫切需要有效的信息发 21 现工具来为他们在 进行导航。这种需求导致 了搜索引擎的问世。搜索引擎迅速成为人们网上搜索的有效工具。 索引擎发展历史 如何在 包含海量信息 的互联网上获得有价值的信息 一直是 户 关注的焦点 问题。搜索技术的出现为 用户 快速 定位 所需信息带来了福音。 1993 年，出现了最早的 览器 年 出了 览器的发展促使 到迅速推广，同时也推动着搜索引擎的发展。 1994 年春天 出现了最早的真正意义上的搜索引擎 当时 序接入到其索引程序中 ，实现网页的自动发现和索引。随后 , 相继出现。这些搜索引擎主