HITS算法在Web挖掘中的应用与改进

软件导刊

２００８年２月ＳｏｆｔｗａｒｅＧｕｉｄｅ

Ｖｏｌ．７Ｎｏ．２Ｆｅｂ．２００８

ＨＩＴＳ算法在Ｗｅｂ挖掘中的应用与改进

蔡

琼，罗雪松

（武汉工程大学计算机科学与工程学院，湖北武汉４３００７３）

摘

要：重点研究了ＨＩＴＳ算法，并且在原有算法的基础上对其进行了改进。对搜索出的信息利用改进的ＨＩＴＳ算法确

定了权威Ｗｅｂ页面，有效地去除了无效网页。关键词：数据的预处理；ＨＩＴＳ算法；权威Ｗｅｂ页面中图分类号：ＴＰ３１２

文献标识码：Ａ

文章编号：１６７２－７８００（２００８）０２－０１５０－０２

际使用过程中，所有Ｓσ中的内部链接都将被忽略，而仅仅只考

１Ｗｅｂ数据挖掘过程中的数据预处理

数据的预处理是对Ｗｅｂ上的数据检索后进行的数据预处

虑外部链接；

（４）将根集Ｓσ构造为ｎ×ｎ的邻接矩阵Ａ及其转置矩阵ＡＴ，计算ＡＴＡ的最大特征值λ１，并将λ１所对应最大特征值的主特征向量ｅ１进行归一化；

（５）将经过归一化后的特征向量ｅ１中具有较大绝对值的元素作为ａｕｔｈｏｒｉｔｉｅｓ返回；

＇＇

（６）计算ＡＡＴ的最大特征值λ１，并将λ１所对应最大特征值的

理，为数据挖掘模块提供挖掘所需要的数据。确定挖掘主题后，可使用Ｇｏｏｇｌｅ的ＷｅｂＡＰＩ，利用ＪＢｕｉｌｄｅｒ实现对Ｇｏｏｇｌｅ的巨大

Ｗｅｂ索引的搜索。但是，用户的一个查询请求往往会检索出庞

大的结果集，而用户所需要的只是其中很小一部分，面对如此多的结果，用户仍然不知所措。所以必须用ＨＩＴＳ算法来确定权威Ｗｅｂ页面，这样就可以有效地去除无效网页。

主特征向量ｅ１＇进行归一化；

（７）将经过归一化后的特征向量ｅ１＇中具有较大绝对值的元素作为ｈｕｂｓ返回［３］。

２ＨＩＴＳ算法

ＨＩＴＳ（ｈｙｐｅｒｔｅｘｔｉｎｄｕｃｅｄｔｏｐｉｃｓｅａｒｃｈ）［１］算法是一种有效的

３ＨＩＴＳ算法中存在的问题

ＨＩＴＳ算法虽然在某些查询主题下能够较为准确地提取出

权威网页，但仍存在在一些场合中会使得算法发生严重的“主题漂移”的现象［４］（ａｕｔｈｏｒｉｔｉｅｓ集中到一些链接稠密的非相关网页的现象被称为“主题漂移”问题）。该现象的出现说明在传统

基于链接分析的主题提取方法，它所依赖的是对超链接环境下链接结构的分析。ＨＩＴＳ算法为每个页面引入两个权值：ａｕｔｈｏｒｉｔｙ权值和ｈｕｂ权值。最后分别输出一组具有最大ａｕｔｈｏｒｉｔｙ权值的页面和一组具有最大ｈｕｂ权值的页面。ａｕｔｈｏｒｉｔｉｅｓ是那些与给定查询主题的上下文最为相关并具有权威性的网页；而ｈｕｂｓ则是那些本身的内容虽然未必具有权威性，但却包含了多个指向ａｕ－

ＨＩＴＳ算法中仍存在一些缺点，这就要求对传统ＨＩＴＳ算法进行

改进，以使其具有更为广泛的适用性，提高权威页面搜索的效率［６］。

ｔｈｏｒｉｔｉｅｓ的超链接的网页。整个ＨＩＴＳ算法可以归纳为以下几个

步骤：

（１）在搜索引擎上输入给定的关键词，以此搜索到的最前面的ｒ个等级最高的查询结果网页作为根集Ｒσ；

（２）将根集的规模扩展至ｎ，形成基本集Ｓσ。扩展规则为，将根集中的全部网页加入进来，并加入最多ｄ个链接到根集Ｒσ中的Ｗｅｂ网页；

（３）用Ｇ（Ｓσ）来表示从基本集Ｓσ中网页的链接关系所推导出的子图，则Ｇ（Ｓσ）中包含两种类型的链接———外部链接和内部链接。外部链接是在两个有着不同域名的网页之间的链接，而内部链接则是在两个有着相同域名的网页之间的链接。在实

［２］

４ＨＩＴＳ算法的改进

４．１

迭代过程中尽量向根集投影

仔细观察ＨＩＴＳ算法的第（４）步和第（５）步，便会发现传统的主题漂移”现象，就是因为它从主特ＨＩＴＳ算法之所以会出现“

征向量中所提取的权威网页组，虽然其内部链接关系最为稠密，但是该组网页与根集的关系却最小，即和原查询主题的关联程度非常小。也就是说传统的ＨＩＴＳ算法是基于权威值迭代的算法，如果根集中存在着与主题不相关的一组稠密网页相连

作者简介：蔡琼（１９６１－），女，湖北武汉人，硕士，武汉工程大学计算机学院副教授，研究方向为数据库、数据挖掘；罗雪松（１９８２－），男，湖北武汉人，

武汉工程大学计算机学院硕士研究生，研究方向为数据挖掘。第２期蔡琼，罗雪松：ＨＩＴＳ算法在Ｗｅｂ挖掘中的应用与改进・１５１・

接的网页，那么，那组内部链接稠密的网页就会使得该组网页的权值在ＨＩＴＳ算法的运行过程中不公平地迅速增加，使得结果不可避免地向该组网页集中。为了避免这种情形的发生，就应该考虑从其它非主特征向量中提取不同的、虽然内部链接并不是最为稠密、但与根集关系却更为密切的权威网页组。

所以要对原来ＨＩＴＳ算法的第（４）、（５）步进行如下改动，以使其具有更为广泛的适用性，增强权威页面搜索的效果。

对于第（４）步的改进为：①根据Ｓσ构造ｎ×ｎ的矩阵Ａ及其转置矩阵ＡＴ，计算其每个特征值λ１，λ２，…，λｎ所对应的特征向量

程度上抑止“主题漂移”现象的产生。

５ＨＩＴＳ算法实验结果及其分析

选择了“这一查询主题进行了实验，ＡｒｔｉｆｉｃｉａｌＩｎｔｅｌｌｉｇｅｎｃｅ”

“主题下的基本集包含１２０６个网页。用未ＡｒｔｉｆｉｃｉａｌＩｎｔｅｌｌｉｇｅｎｃｅ”

主题漂移”。用改改进的ＨＩＴＳ算法得到的结果产生了严重的“

进的ＨＩＴＳ算法，其中ａｕｔｈｏｒｉｔｉｅｓ中前几项的结果包括Ａｍｅｒｉｃａｎ

ＡｓｓｏｃｉａｔｉｏｎｆｏｒＡｒｔｉｆｉｃｉａｌＩｎｔｅｌｌｉｇｅｎｃｅ的主页，这是美国一个非营

，这利性科学团体；《ＪｏｕｒｎａｌｏｆＡｒｔｉｆｉｃｉａｌＩｎｔｅｌｌｉｇｅｎｃｅＲｅｓｅａｒｃｈ》是人工智能方面的国际期刊网页；还有介绍人工智能方面科学的网页和全面介绍人工智能学科的综合网站等。显然，它们都符合权威网页的要求。在ｈｕｂｓ中，包含了大量指向人工智能学科领域中团体、文献、成果等各方面的有用链接，也完全符合

ｅ１，ｅ２，…，ｅｎ，并将它们归一化；②将每一特征向量的各项元素均

取其绝对值，然后在根集子空间Ｗ上进行投影Ｐ，再进行比

＊较，从中找到使｜Ｐλｉｅｉ｜的值达到最大的特征向量ｅ。

对于第５步的改进为：将归一化后的特征向量ｅ＊中具有较大绝对值的元素作为ａｕｔｈｏｒｉｔｉｅｓ返回。

（５）步，可以有效地抑止与查通过修改原来算法的第（４）、

询主题无关的内部链接稠密网页组的提取，使提取结果更为向根集靠近，从而避免了“主题漂移”现象的产生。

ｈｕｂｓ包含丰富的有价值链接的要求。

从实验结果来看，应该说改进的ＨＩＴＳ算法较为地完成了提取ａｕｔｈｏｒｉｔｉｅｓ和ｈｕｂｓ的任务，算法是可行的。

参考文献：［１］［２］［３］［４］［５］［６］

聂培尧．基于ＸＭＬ的半结构数据管理及数据集成问题研究［Ｄ］．西安：西北工业大学，２００２．

吴共庆，陈恩红．一种基于ＸＭＬ的半结构化数据存储方法研究［Ｊ］．计算机工程，２００４（４）．

王宁，徐宏炳，王能斌．基于带根连通有向图的对象集成模型及代数［Ｊ］．软件学报，１９９８（５）．

韩江洪，郑淑丽，魏振春等．面向ＸＭＬ的Ｗｅｂ数据模型研究［Ｊ］．小型微型计算机系统，２００５．

刘洋．基于Ｗｅｂ的内容挖掘技术研究［Ｄ］．哈尔滨：哈尔滨工业大学，２００３．

蒲秋菊．基于ＸＭＬ的Ｗｅｂ数据挖掘技术的研究［Ｄ］．武汉：武汉大学，２００４．

（责任编辑：赵

峰）

４．２基本集收缩

通过前面的分析，“主题漂移”的产生是由于基本集中包含

了大量互不相关的网页。因此对基本集还可以进一步精简：一方面，剔除掉与根集关系不大的网页可以对“主题漂移”问题加以控制；另一方面，还可以大大减少运算量。所以可以对传统

ＨＩＴＳ算法的第（２）步进行如下改进：

的规模扩展至ｎ，形成基本集Ｓσ。扩展规则（１）将根集Ｒσ

为：将根集中网页所链接的全部网页加入进来，并加入最多ｄ个中的Ｗｅｂ网页；链接到根集Ｒσ

（２）设定一个参数ｋ，对已经获取的基本集进行进一步筛选。即只选取那些链向多于ｋ个根集网页的网页，以及被多于ｋ个根集网页所链向的网页，得到缩减后的基本集。

随着基本集规模的缩减，邻接矩阵的阶数也大大减小，因此该改进不但可以有效地降低特征值的计算开销，也可以很大

ＡｐｐｌｉｃａｔｉｏｎａｎｄＩｍｐｒｏｖｅｍｅｎｔｏｆＨＩＴＳｉｎＷｅｂＭｉｎｉｎｇ

ＣＡＩＱｉｏｎｇ，ＬＵＯＸｕｅ－Ｓｏｎｇ

（ＩｎｓｔｉｔｕｔｅｏｆＣｏｍｐｕｔｅｒＳｃｉｅｎｃｅａｎｄＴｅｃｈｎｏｌｏｇｙ，ＷｕｈａｎＩｎｓｔｉｔｕｔｅｏｆＴｅｃｈｎｏｌｏｇｙ，Ｗｕｈａｎ４３００７３，Ｃｈｉｎａ）

Ａｂｓｔｒａｃｔ：ＴｈｅｐａｐｅｒｍａｉｎｌｙｒｅｓｅａｒｃｈｅｓｔｈｅａｌｇｏｒｉｔｈｍＨＩＴＳａｎｄｉｍｐｒｏｖｅｉｔｂａｓｅｄｏｎｔｈｅｏｒｉｇｉｏｎａｌｇｏｒｉｔｈｍ．Ａｎｄｏｎｔｈｅｂａｓｅｏｆｐｒｅｔｒｅａｔ－ｍｅｎｔ，ｕｓｉｎｇｉｍｐｒｏｖｅｄＨＩＴＳａｌｇｏｒｉｔｈｍｃａｎｃｏｎｆｉｒｍｔｈｅａｕｔｈｏｒｉｔｙｏｆＷｅｂｐａｇｅ．ＫｅｙＷｏｒｄｓ：ｐｒｅｔｒｅａｔｍｅｎｔ；ＨＩＴＳ；ａｕｔｈｏｒｉｔａｔｉｖｅＷｅｂｐａｇｅ

!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!勘

程师，研究方向为单片机控制和应用。误

本刊２００８年１月刊《作者李元斌简介为：李元斌（１９６２－），男，湖北天门人，华中科技大学工ＤＳ１８Ｂ２０数字传感器温度检测显示系统》