信息检索之HITS算法

《信息检索之HITS算法》由会员分享，可在线阅读，更多相关《信息检索之HITS算法（10页珍藏版）》请在装配图网上搜索。

1、一、实验目的理解搜索引擎的链接结构子系统的基本功能；了解万维网链接的结构图及特性；理解HITS算法的基本思想和原理。二、实验原理及基本技术路线图（方框原理图）万维网的链接结构通常使用有向图的方式来描述， 在万维网链接结构图中，网页是图的节点; 而超链接则是链接节点的有向边（从源网页指向目的网页） 。每一条从源网页指向目的网页的超 链接，既称为源网页的“出链接”，又称为目的网页的“入链接”。用图表示万维网链接结构，如 下图：关于万维网结构图的规模很难给出一个准确的统计结果， 这是因为：图中的节点存在形式纷 繁复杂，即使不考虑网页的可访问性问题（部分网页会对用户访问加以限制，如采取登录策略等），

2、只考虑能够被自由访问的网页，这些网页中既有以传统形式存在的静态页面， 又有随用户查询要 求在服务器端实时生成的动态页面，甚至还有用 AJAX技术生成的URL相同但页面内容千差万 别的页面。而超链接的界定在当前的网络环境下也存在诸多困难。2008年7月，谷歌在其官方博客上声称其索引量达到1万亿网页，这一估计一定程序上反映了图的节点集合规模。链接结构信息是网络信息环境与传统信息媒介的最大区别之一。对于搜索引擎而言，与用户查询需求乃至页面内容均相对独立的超链接结构是用以评价万维网数据质量的重要依据。在2001年SIGIR会议上，Craswell等人对链接结构分析算法的应用方式进行了分析，提出万维网超

3、链接应具有的两个特性:如果存在超链接L从页面Psource指向页面Pdestiny,则Psource与 Pdestiny满足：特性1：（内容推荐特性）页面Psource的作者推荐页面Pdestiny的内容，且利用L的链接文本内 容对Pdestiny进行描述。特性2：（主题相关特性）被超链接连接的两个页面Psource与P destiny的页面内容涉及类似的主 题。然而这两个特性对于万维网数据爆炸性增长的背景下被认为过于理想主义。万维网节点之间的超链接关系远比特性1和特性2描述的情况要复杂的多。但是，一方面，经过改进的链接分析 算法还是可以为页面质量评估提供参考；另一方面，在经过数据清理之后的近

4、似理想的网络环境中,它们还是可以发挥其挑选高质量网页的作用，因此链接分析算法仍旧是当前研究的热点之一。HITS算法是由Jon Kleinberg在20世纪90年代提出的一种链接分析算法。HITS算法是Hyperlink-Induced Topic Search （基于超链接推演的主题搜索算法）的简称，它的核心思想是对 网页如下两个方面的权威程度进行评价。首先，内容权威度（Authority Value），即网页本身内容的受欢迎程序；其次，链接权威度（Hub Value），即网页链接到其他受欢迎资源的程度。HITS算法的实施包括两个阶段，对用户输入的查询主题而言，首先是通过文本搜索过程获 取与此

5、查询主题内容相关的网页集合，并适当扩充该网页集合，以包括尽可能多的结果候选网页， 同时使用结果集合网页间的链接结构关系更加完整；随后则是通过一个“迭代一收敛”的过程计算网页集合中每个页面对应的链接权威度和内容权威度数值。算法最后输出的是分别按照链接权威度与内容权威度排序的结果列表，用户可以根据需求不同，选择其中的结果页面进行浏览。-2-3-HITS ( Hyperlink-Induced T opic Search)算法(1) 选取网络信息检索系统的结果集合R将R, R所指向的网页和指向R的网页构成的链接结构图称为G。对于G中每一个节点n,设H(n)和A(n)分别是其链接权威度和内容权威度，向

6、量H和A分别为G的链接权威度和内容权威度结果向量。(2) 设定h=A=(1, 1,1)，即：对G中每一个节点n,设定其初始值 H(0)( n)和A(0)( n)均为1.(3) For k=1,2, 3,，N 对G中每一个节点n,A(k)(n)=匕 H (k J) (mi )(称为 I 操作)mixn 对G中每一个节点n,H (k)( n)A(k)(mi)(称为 0 操作) 将 H( n)和 A(0)( n)(n G)作规范化处理，使 Z (A(k) n )2 =1 , Z (H (k) n)2 =1。nGn 0(4) 当结果向量h和A未收敛时，返回(3);当H和A收敛时，输出算法所计算出的G中

7、每一个节点n的H(n)和A(0)(n)的结果。三、所用仪器、材料(设备名称、型号、规格等)硬件：PC机一台操作系统：Windows 7编程语言：JavaIDE: eclipse 3.5.2四、实验方法、步骤实现HITS算法的主要功能模块，并可对测试数据计算所需要内容权威度和链接权威度的 值。要求能够输出每次迭代过程的详细信息。五、实验过程原始记录(数据、图表、计算等)本次实验中没有实现HITS算法中要求的Web图的扩展功能，而是将图的结点和边的信息存 储在文件中，由程序读入并计算各自内容权威度和链接权威度， 并能够指定最大迭代次数和输出 迭代过程的详细信息。Web图的构造过程的主要代码：/*格

8、式如下：url1 - url2* Web图类的构造方法*参数文件中每一行存储一条边的信息*该方法将扫描文件中的每一行，将所有的边及结点信息读入并构造整个图* 注：程序设计思想参考 http:/webla.sourceforge. net/* param file存储了图中边及结点信息的文件* throws lOExcepti on*/public WebGraph(File file)throws IOException this ();/初始化相关变量BufferedReader reader =new BufferedReader(new FileReader(file);Stri ng

9、line;int urlI ndex = 0;/读入文件，解析并存储结点及边的信息while (li ne = reader.readL in e() !=n ull ) int in dex = lin e.i ndexOf(-);if (in dex 0) String urlFrom = lin e.substri ng(0, in dex).trim();String urlTo = lin e.substri ng(i ndex + 2).trim();inturlI ndexFrom = -1;inturlI ndexTo = -1;/ 存储URL到ID的映射if ( urlToI

10、d .containsKey(urlFrom) urlI ndexFrom =urlToId .get(urlFrom); else idToURL .put(urlIndex, urlFrom.trim();urlToId .put(urlFrom.trim(), urlI ndex);urlI ndex+;urlI ndexFrom =urlToId .get(urlFrom);/ 存储ID到URL的映射if ( urlToId.containsKey(urlTo) urlI ndexTo =urlToId .get(urlTo); else idToURL .put(urlIndex,

11、urlTo.trim();urlToId .put(urlTo.trim(), url In dex);urlI ndex+;urlI ndexTo =urlToId .get(urlTo);/ 存储边Map tedge =new HashMapv In teger, I nteger();tedge.put(urlI ndexFrom, urlI ndexTo);edge .add(tedge.entrySet().iterator().next();this . nodeCount= idToURL .size(); / 结点数量/填充边到对应的邻接矩阵this . matrix = ne

12、w int nodeCount nodeCount ;for (int i = 0; i entry =edge .get(i);int from = en try.getKey(); int to = en try.getValue(); matrix fromto = 1;HITS算法内容权威度和链接权威度的计算:* HITS 类构造方法* param webGraph web 图*/public HITS(WebGraph webGraph) this . webGraph = webGraph;this . authorityscores= new HashMapvInteger, D

13、ouble();this . hubScores = new HashMapvInteger, Double();this .no deCou nt= webGraph.getNodeCou nt();/初始的内容权威度和链接权威度均设为1for (int i = 0; i webGraph.getNodeCou nt(); i+) this . authorityScores .put(i, 1.0);this . hubScores .put(i, 1.0);/计算结点的内容权威度和链接权威度,指定最大迭代次数为 25 computeHITS(25);/*计算结点的内容权威度和链接权威度p

14、aram numIterations最大迭代次数*/private void computeHITS( int n umIterati ons) /迭代次数int iterNum = n umIterati ons;/上一次迭代的内容权威度和链接权威度,初始值均设为0Map preAuthorityScore =new HashMapv In teger, Double();Map preHubScore =new HashMapv In teger, Double();for (int i = 0; i 0& !isC on verge nce(preAuthorityScore,autho

15、rityScorespreHubScore, hubScores ) /存储计算所得的内容权威度和链接权威度值，用于下次迭代之前的收敛判断copyAtoB( authorityScores , preAuthorityScore);-6-copyAtoB( hubScores , preHubScore);System. out .println(第+ (iterNum - numIterations) +次迭代：“);for(int i = 0; i List inLinks = double authorityScore = 0;for (In teger in : inLin ks) /

16、内容权威度等于所有入链接的链接权威度之和authorityScore +=hubScores .get(i n).doubleValue(); authorityScoresno deCou nt ; i+) webGraph .getInLinks(i);/内容权威度.put(i, authorityScore);/入链接集 for(int i = 0; i List outL inks =double hubScore = 0;no deCou nt ; i+) webGraph .getOutL in ks(i);/ 链接权威度/岀链接集for (In teger out : outL

17、in ks) /链接权威度等于所有岀链接的内容权威度之和hubScore += authorityScores .get(out).doubleValue();hubScores .put(i, hubScore);/ double double for归一化(使用最大值)aMax = getMaxValue(hMax = getMaxValue(int i = 0; i B3A f C- ASB C6C - Bhits.txt，如上图（右），将输入设为测试数据以上图（左）为例，将结点和边信息存入文件文件hits.txt，然后运行以上测试程序，得运行结果如下：HITSW法示例：吋小團所对应的邻

18、接矩阵:ABCA 1 1 1B 1 0 1C 0 1 0吕算法的执行过程:第0次迭代:-9-A(A三丄AB：=1.0AC=1.0 第1次迭代：AA=1.0AB=1.0AC-1.0 第2次迭代：AA=1.0AC =1.0第却欠迭代：AA=1.0AB-0.7SAC=1.0第电次迭代：AA=1.0AE=0.73S iC-1.0 第引欠迭代：A(A=1.0AB=OAC=1.GHB=1.0H(C=1.0HA)=l,0HB0.666HC-0.3333HA=1.0|H(B-0.7142HC=0.2857HAJ-1.0H(B=0.7272HC-0.2727H(A=】OHB-0,7307HC-042S92H(A

19、=1.0HB=07317H(C=0.2582第E次迭代:AA=1.0A B =0*7323AC=1.0第7次迭代：AA1.0AB-0 .7321ACJ=l*0第住次迭代：A(A-1.0AB=0.732A(C=1.0 第9次迭代；AA=1.0ABJ-0.732AC-l,0第10；欠迭代：AA=1.0AB=0*732AC=1.0HA-1.0HB=0.7319 HCJ=0.26EHA=1.0HB=0,732HCH0.279H(A-1.0HBJ=0.732HC=0.279HA-1.0HB-0.732HC-0279HA-10HB=a.732HCJ=02679-#-#-在本实验程序中，默认最大迭代次数为2

20、5次，连接两次计算所得值之差小于0.00001认为结果收敛。由上述运行过程可以看出，测试数据在第10次迭代时已收敛，所得结果为:-#-#-aA = 1.0 aB = 0.732 ac = 1.0hA = 1.0 hB = 0.732 hc = 0.2679六、实验结果分析、经验总结或结论（例如对实验获取数据的误差分析、数据处理、成果 等。其中，绘制曲线图时必须用标准计算纸，不得随意用普通白纸绘画）HITS通过本次实验我们理解了 HITS算法的基本思想和方法，并编程实现了一个简单的 算法的程序，对链接结构分析子系统的作用和功能有了一个较为直观的认识。另外，这里 所得的链接结构分析结果，可以为搜索结果排序提供依据，但一定是根据多个因素综合得 出排序结果而不是仅凭一个因素，因为每个算法均有其不足之处，需要相互平衡各个算法 的优缺点，这样得到的排序效果才会比较好。-10-