论文部分内容阅读
[摘 要]HITS算法是基于链接分析的一种权威资源提取算法。相对于其他Web结构挖掘算法来说，HITS算法优势非常明显。针对HITS算法的缺陷，可以使用基本集缩减法对HITS算法进行改进。
[关键词]Web结构挖掘；HITS算法；数据挖掘
[中图分类号] G633.67 [文献标识码] A [文章编号] 1674-6058（2018）15-0036-02
Web拥有海量的信息，为人们提供丰富多样的信息服务。随着信息技术的发展和Web信息量的指数级增长，快速准确地从Web网络中获取信息变得愈发重要。因此，如何从Web网络中寻找信息，提取出有价值的内容，已成为当前Web结构挖掘的重要研究课题。用户不但需要获取Web页面，还希望查找的页面质量高，即为权威页面。HITS算法是基于链接分析的一种权威资源提取算法。而作为Web数据挖掘的重要内容，Web结构挖掘的关键在于信息检索。在Web结构挖掘领域中，链接分析的作用非常重要，主要用于分析超链接以确定权威信息源。本文研究HITS算法，分析了传统HITS算法存在的问题，并在此基础上运用基本集缩减法优化HITS算法，从而实现更有效率的权威网页检索。
一、HITS算法基本原理
作为数据提取的典型算法之一，HITS算法的应用和需要检索的主题有直接关系。HITS算法的基本思想是先提取出Web链接结构中用户需要检索的相关页面，组成Web链接结构子图，再运用HITS算法分析计算这个链接结构子图。而Web链接主要有以下几点特征：（1）有些链接的作用是广告或导航，只有具有注释性的链接才能用于判断权威性。（2）由于商业竞争，指向Web网页竞争领域的权威网页的情况很少。（3）一般来说，权威网页都缺少明显的描述，如百度搜索主页不会给出明确的有关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算法优化方法——基本集缩减法。所谓基本集缩减法，是指通过考虑指向或来自根集中网页的链接数目缩减基本集，再从中提取适当的Web Communities。基本集缩减法的优化对象是传统HITS算法的第二个步骤：通过向S中加入被S引用的网页和引用S的网页，将S扩展成一个更大的集合T。改进的HITS算法第二步骤是：首先加入所有的根集网页指向的网页以及最多d个指向根集R中网页的Web网页，将根集R的规模扩展至n，构建基本集S，再筛选已建立的基本集S，只选择指向至少k个根集网页以及被至少k个根集网页所链向的网页，从而实现基本集的缩减。由此，可以总结出运用基本集缩减算法提取Authoritiy网页的基本步骤：（1）在搜索引擎中输入特定关键词，检索到的r个等级的结果网页构成根集Rσ。（2）扩展根集R的规模至n，构建基本集Sσ，加入所有的根集网页指向的网页以及最多d个指向根集R中网页的Web网页，将根集R的规模扩展至n，构建基本集S，再筛选已建立的基本集S，只选择指向至少k个根集网页以及被至少k个根集网页所链向的网页，从而实现基本集的缩减。（3）用G（Sσ）表示根据基本集Sσ中的网页链接关系推导而来的结构子图，则G（Sσ）中包含内链、外链两种链接。所谓外链，是指域名不同的Web网页之间的链接，内链是指域名相同的网页之间的链接，在实际情况下，只考虑外链，而忽略基本集Sσ中的所有内链。（4）结合基本集Sσ构造邻接矩阵矩阵A和转置矩阵AT，计算其每个特征值及所对应的特征向量，并归一化。（5）归一化后的特征向量中将绝对值较大的元素作为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算法的计算效率和精确度。
[ 参 考 文 献 ]
[1] 刘军.基于Web结构挖掘的HITS算法研究[D].长沙：中南大学， 2008.
[2] 卢虹宇.Web结构挖掘中HITS算法的研究[D].成都：西南交通大学， 2008.
[3] 范聪贤，徐汀荣，范强贤.Web结构挖掘中HITS算法改进的研究[J]. 微计算机信息， 2010（3）.
（责任编辑 周侯辰）
[关键词]Web结构挖掘；HITS算法；数据挖掘
[中图分类号] G633.67 [文献标识码] A [文章编号] 1674-6058（2018）15-0036-02
Web拥有海量的信息，为人们提供丰富多样的信息服务。随着信息技术的发展和Web信息量的指数级增长，快速准确地从Web网络中获取信息变得愈发重要。因此，如何从Web网络中寻找信息，提取出有价值的内容，已成为当前Web结构挖掘的重要研究课题。用户不但需要获取Web页面，还希望查找的页面质量高，即为权威页面。HITS算法是基于链接分析的一种权威资源提取算法。而作为Web数据挖掘的重要内容，Web结构挖掘的关键在于信息检索。在Web结构挖掘领域中，链接分析的作用非常重要，主要用于分析超链接以确定权威信息源。本文研究HITS算法，分析了传统HITS算法存在的问题，并在此基础上运用基本集缩减法优化HITS算法，从而实现更有效率的权威网页检索。
一、HITS算法基本原理
作为数据提取的典型算法之一，HITS算法的应用和需要检索的主题有直接关系。HITS算法的基本思想是先提取出Web链接结构中用户需要检索的相关页面，组成Web链接结构子图，再运用HITS算法分析计算这个链接结构子图。而Web链接主要有以下几点特征：（1）有些链接的作用是广告或导航，只有具有注释性的链接才能用于判断权威性。（2）由于商业竞争，指向Web网页竞争领域的权威网页的情况很少。（3）一般来说，权威网页都缺少明显的描述，如百度搜索主页不会给出明确的有关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算法优化方法——基本集缩减法。所谓基本集缩减法，是指通过考虑指向或来自根集中网页的链接数目缩减基本集，再从中提取适当的Web Communities。基本集缩减法的优化对象是传统HITS算法的第二个步骤：通过向S中加入被S引用的网页和引用S的网页，将S扩展成一个更大的集合T。改进的HITS算法第二步骤是：首先加入所有的根集网页指向的网页以及最多d个指向根集R中网页的Web网页，将根集R的规模扩展至n，构建基本集S，再筛选已建立的基本集S，只选择指向至少k个根集网页以及被至少k个根集网页所链向的网页，从而实现基本集的缩减。由此，可以总结出运用基本集缩减算法提取Authoritiy网页的基本步骤：（1）在搜索引擎中输入特定关键词，检索到的r个等级的结果网页构成根集Rσ。（2）扩展根集R的规模至n，构建基本集Sσ，加入所有的根集网页指向的网页以及最多d个指向根集R中网页的Web网页，将根集R的规模扩展至n，构建基本集S，再筛选已建立的基本集S，只选择指向至少k个根集网页以及被至少k个根集网页所链向的网页，从而实现基本集的缩减。（3）用G（Sσ）表示根据基本集Sσ中的网页链接关系推导而来的结构子图，则G（Sσ）中包含内链、外链两种链接。所谓外链，是指域名不同的Web网页之间的链接，内链是指域名相同的网页之间的链接，在实际情况下，只考虑外链，而忽略基本集Sσ中的所有内链。（4）结合基本集Sσ构造邻接矩阵矩阵A和转置矩阵AT，计算其每个特征值及所对应的特征向量，并归一化。（5）归一化后的特征向量中将绝对值较大的元素作为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算法的计算效率和精确度。
[ 参 考 文 献 ]
[1] 刘军.基于Web结构挖掘的HITS算法研究[D].长沙：中南大学， 2008.
[2] 卢虹宇.Web结构挖掘中HITS算法的研究[D].成都：西南交通大学， 2008.
[3] 范聪贤，徐汀荣，范强贤.Web结构挖掘中HITS算法改进的研究[J]. 微计算机信息， 2010（3）.
（责任编辑 周侯辰）