[搜索引擎技术普及 - 3] 搜索引擎系统的网络链接结构分析技术（中）

sowang

内容出自：搜狗实验室


这次介绍一下搜索引擎中链接分析的HITS算法

HITS算法是由Kleinberg在90年代末提出的一种链接分析算法，与随后我们将介绍的PageRank等实用性算法不同，HITS算法更大程度上是一种实验性质的尝试。它必须在网络信息检索系统进行面向内容的检索操作之后，基于内容检索的结果页面及其直接相连的页面之间的链接关系进行计算。这使得在实际应用环境中使用HITS算法变得十分困难，尽管有人尝试通过算法改进和专门设立链接结构计算服务器（Connectivity Server）等操作，可以实现一定程度的在线实时计算，但这对于每天要处理超过几十亿次用户需求的商用搜索引擎而言，这样的计算代价仍然是不可接受的。


尽管如此，但HITS算法仍在学术界和产业界都获得了非常多的关注，IBM公司甚至基于改进后的HITS算法开发了专门的检索应用系统Clever系统（尽管此系统并没有投入真实的网络信息检索服务）。这是与HITS算法设计本身所具有的高度的数学严谨性相关的，但更重要的，是因为HITS算法的设计符合网络用户评价网络资源质量的普遍标准，因此能够为用户更好的利用网络信息检索工具访问互联网资源带来便利。


HITS算法对网页进行质量评估的结果反映在它对每个网页给出的两个评价数值——内容权威度（Authority）和链接权威度（Hub）上。


内容权威度与网页自身直接提供内容信息的质量相关，被越多网页所引用的网页，其内容权威度越高；与之相对应的，链接权威度与网页提供的超链接的质量相关，引用越多内容质量高网页的网页，其链接权威度越高。如果我们把一个内容权威度高的网页比作一个味道不错的饭馆的话，那么链接权威度高的网页就是旅游杂志中美食家撰写的一篇推荐饮食地点的文章。


由于网络信息检索所面临的数据对象即万维网数据具有极为繁杂的数据规模，因此，用户所涉及到的绝大多数查询主题都会返回数量繁多的相关查询结果。面对数目动辄上千上万的相关结果集合，绝大多数用户会倾向于查找出结果集合中对自己获取信息最有价值的那一部分网页。HITS算法所解决的正是这一问题：它所施行的数据集合，就是网络信息检索工具返回的与查询主题相关的结果集合，而其输出的结果，就是对此结果集合中网页的内容权威度和链接权威度的评价。HITS算法因而被认为能够极大地改善用户的检索体验，也得到了众多研究人员的关注。


从具体施行步骤而言，HITS算法的施行是一个“迭代—收敛”的过程，由于具体的算法流程比较复杂，我们不准备详细描述其运行过程，只是说明：网页A链接权威度的数值是通过其链向的网页的内容权威度决定的，而网页A的内容权威度的数值则是由链向其的网页的链接权威度所决定的。是不是有点像鸡生蛋与蛋生鸡的关系呢？


HITS算法在特定的应用环境中取得了一定的成功，如在Chakrabarti等基于HITS算法的小规模试验尝试中，研究者获得了超过Yahoo!和AltaVista手工分类结果的检索性能，但其实验数据的规模较小，实验结果测试集合的标注也缺乏足够的客观性。


HITS算法的施行对象及其迭代算法的本质决定了其不可能在网络信息检索系统中取得大规模的应用。而更多的基于实际网络数据的实验结果证明，这个算法本身在挑选内容或链接质量较高的页面时也并非格外有效，究其原因而言，大致包括以下几点：


A. 站点内部网页在权威度数值上的的相互加强；
B. 网页辅助制作工具自动生成的链接条目的干扰；
C. 与主题无关的网页或者主题漂移。


针对上述缺点， Bharat等人对HITS算法进行了相关的修改，具体内容包括忽略站点内部的链接、或者利用网页的内容相似度对Hub/Authority值进行初始化等。这些改进获得了有限的成功，但从算法的核心思想而言与HITS并没有实质的改变，因此在此不再赘述。