Web结构的数据挖掘HITS算法

摘要：信息技术的发展催生了更多更先进的数据挖掘技术，其中基于Web结构的数据挖掘技术获得业界普遍关注。文章从Web结构挖掘深入研究运用Hyperlink-InducedTopicSearch（HITS）算法挖掘web数据，从而准确判断web链接页面的重要性，分析了HITS算法的基本思想和存在的问题，并提出了HITS算法的改进方案。

关键词：Web结构挖掘；HITS算法；数据挖掘

Web拥有海量的信息，为人们提供丰富多样的信息服务。随着信息技术的发展和Web信息量的指数级增长，快速准确地从Web网络中获取信息变得愈发重要。因此，如何从海量的Web网络中寻找有价值的数据信息已然是现阶段Web结构挖掘的一个非常重要的研究课题。在实际应用场景中，用户往往需要在获得Web页面的基础上快速找到高质量的所谓权威页面。在Web结构挖掘中链接分析的作用非常重要，而以链接分析为基础建立的HITS算法能够高效地筛选出Web页面中的权威资源。常常用于分析超链接以确定权威信息源。本文研究HITS算法，分析了传统HITS算法存在的问题，并在此基础上运用基本集缩减法优化HITS算法，从而实现更有效率的权威网页检索，提高提高算法的效率和灵活性。

一、HITS算法基本原理

作为数据提起算法的典型算法之一，HITS算法的应用和需要检索的主题有直接关系。HITS算法的基本思想是先提取出Web链接结构中用户需要检索的相关页面，组成Web链接结构子图，再运用HITS算法分析计算这个连接结构子图。而Web链接主要有以下几点特征。其一，有些链接的作用是广告或导航，只有具有注释性的链接才能用于权威性的评判。其二，商业竞争因素的影响下，权威网页链接至Web网页竞争领域的情况很少。其三，一般来说，权威网页都缺少明显的描述，如百度搜索主页并不会将与Web信息检索引擎有关的具体描述信息呈现给用户。可见，Web链接的实际情况与平均分配权值不相符。因此，在HITS算法中新增了一种新的网页类型，也就是Hub网页。Hub网页集中了链接至权威网页的链接。实际上，很少有网页指向Hub网页，但是Hub网页中集中了链接至权威网页的链接。如，排列在课本主页上的一列参考文献。在常规情况下，高质量的Hub网页指向了大量的权威网页，而一个高质量的权威网页拥有许多指向它的Hub网页，但是一个页面的authority等于链接至这个页面的全部hub的和；一个页面的hub等于它指向的页面的全部authority的和。而Hub和Authority网页之间的关系是自动查询权威网页和Web结构和资源的重要工具。这就是HITS算法的基本原理。

二、传统HITS算法存在的问题

传统的HITS算法主要存在以下几个问题。第一，下载、分析网页包含的链接，并且排除重复的链接需要耗费大量的时间，计算量比PageRank算法大。第二，某些情况下，大量主机A上的网页会指向另一台主机B上的某一个特定网页，从而使主机A上的网页Hub值和主机B上网页的Authority增加，反之也一样。HITS算法假设决定某一个网页权威值的组织和个人不同，上述情况对主机A和B上网页的Hub和Authority的值有所影响。第三，网页中的一些无关链接指向的网页中包含的无关链接对Hub和Authority值的计算造成影响。网页在制作的过程中往往会被加入一些无关链接，如广告、友情链接都对HITS算法的精确度有影响。第四，主题漂移是HITS算法存在的最大问题。Web链接结构的自组织性，使WWW中主题一样或相关的页面通过超链接形成一个个紧密链接区域。当用户查询范围较宽的定义主题或者多个主题时，链接结构子图会因为多个子主题对应多个信息形成多个相对紧密链接区域。而HITS算法属于迭代算法，因此，紧密链接区域的页面权值必然会增大，从而干扰检索的精确度，使用户获得的结果发生漂移，这种现象叫做主题漂移。第五，在查询主题时采用HITS算法时有一定的几率出现主题泛化的现象，也就是说结果中出现了新的与查询无关的主题。

三、利用基本集缩减法优化

HITS算法在HITS算法的基本集中含有很多互相之间毫无关联的网页，因此，需要对基本集进行精简。可以通过剔除与根集没什么关系的网页，从而有效抑制主题偏移问题，同时大大降低运算量。为了实现这个目的，可以对HITS算法进行优化，以优化获取基本集的方式，产生新的HITS算法改进方案———基本集缩减法。所谓基本集缩减法，是指通过考虑指向或来自根集中网页的链接数目缩减基本集，再从提取适当的WebCommunities。基本集缩减法向S中加入被S引用的网页和引用S的网页将S扩展成一个更大的集合T。HITS算法改进：首先加入所有的根集网页指向的网页以及最多d个指向根集R中网页的Web网页，将根集R的规模扩展至n，构建基本集S，再筛选已建立的基本集S，只选择指向至少k个根集网页以及被至少k个根集网页链向的网页，从而实现基本集的缩减。由此，可以总结出采用基本集缩减算法提取authorities网页的步骤。第一步，输入特定的关键词，检索到的r个等级的结果网页构成根集Rσ。第二步，扩展根集R的规模至n，构建基本集Sσ，加入所有的根集网页指向的网页以及最多d个指向根集R中网页的Web网页，将根集R的规模扩展至n，构建基本集S，再筛选已建立的基本集S，只选择指向至少k个根集网页以及被至少k个根集网页链向的网页，从而实现基本集的缩减。第三步，用G(Sσ)表示根据基本集Sσ中的网页链接关系推导而来的结构子图，则G(Sσ)中包含内链、外链两种链接。所谓外链是指域名不同的Web网页之间的链接，内链是指相同域名的网页之间的链接，在实际情况下，只考虑了外链，而忽略基本集Sσ中的所有内链。第四步，结合基本集Sσ构造邻接矩阵矩阵A和转置矩阵AT，计算其每个特征值及所对应的特征向量。第五步，特征向量归一化后会以authorities值返回具有较大绝对值的元素。缩减基本集可以减少邻接矩阵阶数，降低特征值的计算量。缩减基本集方法中的计算量的预估方法如下：从与基本集S对应的一个n*n邻接矩阵中选取出链接至根集R中元素的多个网页，从邻接矩阵中从第n-r行中选择前r个元素之和≥2的行，可预估其计算量为r(n—r)。与之类似，选取多个根集网页链接的网页所需计算量一样。运用该方法可以将基本集缩减为原先的一半，考虑到计算与Web数据挖掘中HITS算法有关的特征向量的计算量为n3，计算是加上2r(n—r)的额外计算量，运用基本集缩减法还可以有效减少计算量，同时基本集缩减法能够有效抑制主题偏移问题。四、结语综上所述，HITS算法虽然存在一些问题，但是相对于其他Web结构挖掘算法来说，优势非常明显。HITS算法的基本思想以页面之间的链接关系为基础。从Web结构挖掘的本质入手，分析了HITS算法的基本思想，探讨了HITS算法的基本原理。但是由于篇幅限制无法进一步深入研究其算法，通过分析HITS算法的缺陷，找到相应的改进方案，进而提高HITS算法的使用效果，促进其在信息检索领域的运用。在研究改进HITS算法的过程中，应该先深入研究传统的HITS算法中存在的不足，针对主题偏移现象和减少基本集邻接矩阵特征值和特征向量的计算量，提出使用基本集缩减法对HITS算法进行改进，根据网页与根集元素之间的链接数量进一步提取基本集，使基本集规模进一步缩减，从而使搜索结果更加集中于根集，有效降低计算开销，从而有效提升HITS算法的计算效率和精确度。

参考文献:

[1]刘军.基于Web结构挖掘的HITS算法研究[D].中南大学,2008.

[2]卢虹宇.Web结构挖掘中HITS算法的研究[D].西南交通大学,2008.

[3]范聪贤,徐汀荣,范强贤.Web结构挖掘中HITS算法改进的研究[J].微计算机信息,2010,26(3):160-162.

[4]马洁.web结构挖掘中HITS算法的研究[J].软件:电子版,2013(5).

作者:赵炎 单位:宿迁经贸高等职业技术学校