Web结构的数据挖掘HITS算法论文.docx

Web结构的数据挖掘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中网页的We