基于Web结构挖掘的HITS算法分析及改进

第３８卷第１期・学术　Ｖ０Ｉ．３８　Ｎｏ．１　湖南ｇ－ｑ机　２０１　１年１月　ＨＵＮＡＮ　ＡＧＲＩＣＵＬＴＵＲＡＬ　ＭＡＣＨＩＮＥＲＹ　Ｊａｎ．２Ｏ１　１　基于Ｗｅｂ结构挖掘的　ＨＩＴＳ算法分析及改进　邓超，何月顺　（东华理工大学信息工程学院，江西抚州　３４４０００）　摘要：随着网络和数据挖掘技术的发展，Ｗｅｂ数据挖掘得到了较多的研究。文章从Ｗ。ｂ结构挖掘的角度　出发，在分析传统的ＨＩＴＳ（Ｈｙｐｅｒｌｉｎｋ—Ｉｎｄｕｃｅｄ　Ｔｏｐｉｃ　ｓｅａｒｃ１１）算法的基础上，针对Ｈｕｂ页面的多主题性、无关页面　和无关链接等对ＨＩＴＳ算法的影响，提出了ＨＩＴＳ算法的改进算法。　关键词：Ｗｅｂ结构挖掘：ＨＩＴＳ；Ｈｕｂ　中图分类号：ＴＰ３９３　文献标￣ｔｌｑ－：Ａ　文章编号：１００７—８３２０（２０１　１）Ｏｌ一００８０—０２　Ａｎａｌｙｓｉｓ　ａｎｄ　Ｉｍｐｒｏｖｅｍｅｎｔ　ｏｆ　ＨＩＴＳ　Ａｌｇｏｒｉｔｈｍ　Ｂａｓｅｄ　ｏｎ　Ｗｅｂ　Ｓｔｒｕｃｔｕｒｅ　Ｍｉｎｉｎｇ　ＤＥＮＧ　Ｃｈａｏ，ＨＥ　Ｙｕｅ—ｓｈｕｎ　（Ｃｏｌｌｅｇｅ　ｏｆ　Ｉｎｆｏｒｍａｔｉｏｎ　Ｅｎｇｉｎｅｅｒｉｎｇ，Ｅａｓｔ　Ｃｈｉｎａ　Ｕｎｉｖｅｒｓｉｔｙ　ｏｆ　Ｔｅｃｈｎｏｌｏｇｙ；Ｆｕｚｈｏｕ，Ｊｉａｎｇｘｉ　３４４０００，Ｃｈｉｎａ）　Ａｂｓｔｒａｃｔ：Ｗｉｔｈ　ｔｈｅ　ｄｅｖｅｌｏｐｍｅｎｔ　ｏｆ　ｔｈｅ　ｌｎｔｅｒｎｅｔ　ａｎｄ　ｔｈｅ　ｄａｔａ　ｍｉｎｉｎｇ，／／ｌｏｒｅ　ａｎｄ　ｍｏｒｅ　ｒｅｓｅａｒｃｈ　ｗｏｒｋ　ａｒｅ　ｃｏｍｅ　ｏｕｔ　ｗｉｔｈ　ｔｈｅ　Ｗｅｂ　ｄａｔａ　ｍｉｎｉｎｇ．Ｆｒｏｍ　ｔｈｅ　ｄｉｒｅｃｔｉｏｎ　ｏｆ　Ｗｅｂ　ｓｔｒｕｃｔｕｒｅ　ｍｉｎｉｎｇ　ａｎｄ　ｆｏｃｕｓｅｄ　ｏｎ　ＨＩＴＳ　（Ｈｙｐｅｄｉｎｋ—Ｉｎｄｕｃｅｄ　Ｔｏｐｉｃ　Ｓｅａｒｃｈ）ａｌｇｏｒｉｔｈｍｓ　ａｎａｌｙｚｉｎｇ　ａｆｔｅｒ　ａｎａｌｙｚｉｎｇ　ｏｆ　ｔｈｅ　ｔｗｏ　ｍａｉｎ　ａｌｇｏｒｉｔｈｍｓ（ＰａｇｅＲａｎｋ　ａｎｄ　ＨＩＳＴ）．Ｍｕｃｈ　ｆａｃｔｏｒｓ　ｉｎｃｌｕｄｉｎｇ　ｍｕｌｔｉ—ｓｕｂｊｅｃｔｓ　ｏｆ　Ｈｕｂ　ｐａｇｅｓ、ｉｒｒｅｌｅｖａｎｔ　ｐａｇｅｓ　ａｎｄ　ｉｒｒｅｌｅｖａｎｔ　ｌｉｎｋｓ　ｈａｖｅ　ｅｆｆｅｃｔｓ　ｏｎ　ＨＩＴＳ　ｐｅｒｆｏｒｍａｎｃｅ．Ｔｏ　ｒｅｓｏｌｖｅ　ｔｈｏｓｅ　ｐｒｏｂｌｅｍｓ，ｗｅ　ｐｒｏｐｏｓｅ　ａｎ　ｉｍｐｒｏｖｅｄ　ａｌｇｏｒｉｔｈｍ　ｏｎ　ＨＩＳＴ．　Ｋｅｙ　ｗｏｒｄｓ：Ｗｅｂ　ｓｔｕｒｃｔｕｒｅ　ｍｉｎｉｎｇ；ＨＩＴＳ；Ｈｕｂ　随着Ｉｎｔｅｍｅｔ的快速发展。Ｗｅｂ正在成为一种新的数据　源，其中汇集了大量信息。但是Ｗｅｂ具有无结构、动态、组织　复杂的特点，给用户搜索数据造成了很大困难。为了从大量半　０操作：ｈ。＝ｑ满足∑ａ　ｑ　（２）　ｑ＜Ｐ　结构化数据中发现可用的模式，Ｗｅｂ挖掘技术应运而生，Ｗｅｂ　规范化ａｐ，ｈ　挖掘分为Ｗｅｂ内容挖掘、Ｗｅｂ使用挖掘和Ｗｅｂ结构挖掘。本　ａ　文主要介绍当前Ｗｅｂ结构挖掘的一个主流算法（ＨＩＴＳ算法），　（３）　并分析传统ＨＩＴＳ算法存在的一些缺陷，针对这些缺陷提出了　改进的ＨＩＳＴ算法。　、Ｔ／∑【　ｑ　Ｅ　Ｔ　ａ　】　１　Ｗｅｂ结构挖掘的主流ＨＩＴＳ算法　ｈ　：．．　（４）　１．１算法原理　通过挖掘Ｗｅｂ链接结构，分析Ｗｅｂ间的链接关系，找出　、／ｑ∑［ｈｑ　Ｗｅｂ集合中的ａｕｔｈｏｒｉｔｉｅｓ和ｈｕｂｓ。　其中，Ｐ的权威值等于所有指向Ｐ的超链接网页中心值　其中Ｐａｇｅ小圆代表网页，里面的红色椭同代表根基Ｓ；外　之和；Ｐ的中心值等于Ｐ所链向的所有网页的权威值之和。　面的黑色椭圆代表根基Ｔ。　１．３　ＨＩＴＳ算法的缺陷　１．２计算Ａｕｔｈｏｒｉｔｙ值和ｈｕｂ值　（１）Ｈｕｂ页面的多主题性。如果一个Ｈｕｂ页面包含有多个　主题，就会有许多链接是指向不相关页面的，这些不相关页面　、．１　Ｉ操作：ａ。＝ｑ满足　ｈ　ｑ　（１）　的Ａｕｔｈ０ｒｉｔｖ权重虽然较低，但是ＨＩＴＳ算法将它们的Ａｕｔｈｏｒｉｔｙ　权重之和作为该Ｈｕｂ页面的Ｈｕｂ权重，于是该Ｈｕｂ页面就会　有一个非常大的Ｈｕｂ权重。而实际上，该Ｈｕｂ页面只有很少甚　收稿日期：２０１１－１２—２４　至没有链接指向好的Ａｕｔｈｏｉｒｔｙ页面。　作者简介：，Ｆ超（１９８５一），男，江西吉安人，硕士研究生，研究方　向：分布式数据库与数据挖掘。　（２）两台主机之间的互相强化关系。比如，一台主机上的　第３８卷第１期　邓　超，等：基于Ｗｅｂ结构挖掘的ＨＩＴＳ算法分析及改　的ｋ分之一。很显然，式（７）已经包括式（６）。　２．３通过对链接上下文的分析来处理无关链接的影响　！　许多页面链接到另一台主机上的同一个页面Ｐ１，这就会大大　增加Ｐ１的Ａｕｔｈｏｆｉｙ权重。反过来，ｔ如果一台主机上的同一个　页面Ｐ２链接到另外一台主机的许多页面上，这又会大大增加　Ｐ２的Ｈｕｂ权重。　对链接上下文的分析主要集中在链接地址和链接描述　上。通过对联接地址的分析，很容易去除站点内的导航链接，可　以给每一链接一个链接权重Ｌｗ，对于站内导航链接可忽略不　计，链接权重Ｌｗ＝０。对联接描述的分析主要是对ＨＴＭＬ标记　（３）无关链接的影响。通常情况下，一个页面上的链接并　不都与主题有关，它包括站点内的导航链接，广告链接，系统自　动生成的一些链接等等。这些链接会极大地影响ＨＩＴＳ算法的　（ａ＞ＬＤ＜／ａ＞之间的文本ＬＤ进行分析。文本ＬＤ通常是该链接　效果　２　ＨＩＴＳ算法的改进　以上列出的影响ＨＩＴＳ算法效果的几个因素并不是相互　独立的，它们彼此间有内在的联系。例如解决了无关页面的影　响，则无关链接的影响也可能随之解决。因为，即使无关链接将　一些无关页面扩展进了基本集，但在处理无关页面的时候，可　以同时将其带来的副作用消除或减弱。本文提出了一些改进　算法消除或减弱以上不利因素。当然，这些算法不可能完全消　除上述不利因素及其他潜在因素的影响，但是在我们的实验　结果中，这些算法确实能得出满意的结果。　２．１　Ｈｕｂ权重算法的改进　当一个Ｈｕｂ页面链接到许多无关页面时，它的Ｈｕｂ权重　将异常升高，导致输出的Ｈｕｂ页面偏离主题。这主要是由于　ＨＩＴＳ算法计算Ｈｕｂ权重时，采用Ｈｕｂ所指向的所有Ａｕｔｈｏｒｉｔｙ　权重之和所致。现在将计算公式改为：　ｈｐ　（ｑ满足　ａｑ）／ｎ　（５）　ｑ＜一Ｐ　ｎ表示指向网页Ｐ的网页ｑ的总数，即该Ｈｕｂ指向的页面　数。将Ｈｕｂ权重的计算由它所指向的Ａｕｔｈｏｒｉｔｙ权重之和改为　Ａｕｔｈｏｒｉｔｙ权重的平均值。这样，即使该Ｈｕｂ指向再多的无关页　面，它的Ｈｕｂ权重也不会异常升高，反而会下降，因为无关页面　的Ａｕｔｈｏｒｉｔｙ权重很低。　２．２改进算法解决两台主机之间的互相强化关系　采用以下算法可以消除两台主机之间的互相强化关系：　ａ　＝　满足∑ｈ　／ｋ．　（６）　ｑ＞一Ｐ　ｈｐ＝（　满足ａｎ／ｍ）／ｎ　（７）　ｑ＜一ｐ　ｋ表示与ｑ同主机并指向Ｐ的页面数，ｉｎ表示与ｑ同主机　并被Ｐ所指向的页面数，ｎ表示ｑ的总数。式（６）表示，若主机１　有ｋ个页面指向主机２的同一页面ｐ，则该ｋ个页面各自对ｐ　的Ａｕｔｈｏｒｉｔｙ权重的贡献为其Ｈｕｂ权重的ｋ分之一。式（７）表示，　若主机１的同一页面ｐ同时指向主机２的ｋ个页面，则该ｋ　个页面各自对页面Ｐ的Ｈｕｂ权重的贡献为其Ａｕｔｈ０ｒｉｔｖ权重　所指向页面的主题的概括，对ＬＤ的分析比分析它所指向的整　个页面容易得多，甚至精确得多。根据搜索主题ｑ和链接文本　ＬＤ的匹配程度ＭＤ可以确定链接权重Ｌｗ，匹配程度的计算　可以用到很复杂的技术包括语义分析，文本挖掘技术等等。本　文采用比较简单的方法，ＭＤ为ｑ中的单词在ＬＤ中出现的次　数，这样，ＬＷ可由下式得出：　ＬＷ＝Ｉ＋ＭＤ　（８）　于是，式（６）、式（７）变为：　ｌ　Ｉｈｐ　（ｑ满足　ｑｑ。Ｌｗ／ｍ）／ｎ　（１０）　ｑ＜一ｐ　猎　足　通过对联接地址和链接描述的分析，确定出链接权重ＬＷ　作为计算Ｈｕｂ和Ａｕｔｈｏｒｉｙｔ权重的系数可以有效解决无效链　接的影响。式（９）、式（１Ｏ）已经包括式（６）、式（７）的改进结果。　３　结论　基于ＨＩＴＳ算法原理的搜索引擎不是预先计算页面的权　威权重和Ｈｕｂ权重，而是在用户提交搜索主体后再对普通搜　索引擎的结果进行处理，这就带来一个响应速度慢的问题。而　Ｇｏｏｇｌｅ搜索引擎虽然可以预先计算页面的等级值，但是却不能　将搜索主题的相关性计入等级值中去，因而也存在一些问题。　本文在深入研究了以上两种系统后提出了一个改进后的原型　系统，使搜索结果的质量有了显著提高，但是如何将这两种　Ｗｅｂ结构挖掘系统的特点结合起来，在保证搜索结果质量的　基础上进一步提高响应速度是我们以后重要解决的问题。　参　考　文　献　【１］Ｈａｎ　Ｊｉａｗｅｉ，Ｋａｍｂｅｒ　Ｍ．数据挖掘一概念与技术【Ｍ】．北京：高等教育出　版社．２００７．　【２］杨炳儒，李岩，陈新中，等．Ｗｅｂ结构挖掘［Ｄ］．北京科技大学计算　机科学系，２００３．　［３］Ｓｏｕｍｅｎ　Ｃｈａｋｒａｂａｒｔｉ．Ｗｅｂ数据挖掘：超文本数据的知识发现［Ｍ］．北　京：人民邮政出版社．２００９．　［４］Ｃａｒｏｌ　Ｌｅａ　Ｃｌａｒｋ．Ａｒｔ：ＨＩＴＳ　ｏｎ　ｔｈｅ　ｗｅｂ［Ｊ］．Ｈａｒｃｏｕｒｔ　Ｃｏｌｌｅｇｅ　Ｐｕｂｌｉｓｈｅｒｓ，２００１．　［５］胡可云，田凤占，黄厚宽．数据挖掘理论与应用【Ｍ】．北京：清华大学出　版社．２００８．　∑　ｈ　Ｌ　／ｗ　Ｋ