信息检索之HITS算法

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

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

3、应用方式进行了分析，提出 万维网超链接应具有的两个特性： -2- 如果存在超链接L从页面Psource指向页面Pdestiny,则Psource与Pdestiny W足： 特性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、个阶段，对用户输入的查询主题而言，首先是通过文本搜索过程获 取与此查询主题内容相关的网页集合，并适当扩充该网页集合，以包括尽可能多的结果候选网页， 同时使用结果集合网页问的链接结构关系更加完整； 随后则是通过一个“迭代一收敛”的过程计 算网页集合中每个页面对应的链接权威度和内容权威度数值。 算法最后输出的是分别按照链接权 威度与内容权威度排序的结果列表，用户可以根据需求不同，选择其中的结果页面进行浏览。-3- HITS ( HyperlinkHITS ( Hyperlink- -Induced T opic Search)Induced T opic Search)算法 (1) 选取网络信息检

6、索系统的结果集合 R 将R, R所指向的网页和指向 R的网页构成的链接结构图称为 G。 对于G中每一个节点n,设H(n)和A(n)分别是其链接权威度和内容权威度，向量 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)m )(称为 I 操作) 对G中每一个节点n, H (n)A(k)(mi)(称为 O 操作) 将 H(0)(n)和 A(0)(n)(n G)作规范化处理，使A(

7、k) n) 2冒 1 , W ( H (k) n)2 且1。 n 二G n G (4)当结果向量H和A未收敛时，返回(3)；当H和A收敛时，输出算法所计算出的 G中每一个节点 n 的 H(0)(n)和 A(0)(n)的结果。 三、所用仪器、材料(设备名称、型号、规格等) 硬件：PC机一台 操作系统：Windows 7 编程语言：Java IDE: eclipse 3.5.2 四、 实验方法、步骤 实现HITS算法的主要功能模块，并可对测试数据计算所需要内容权威度和链接权威度的 值。要求能够输出每次迭代过程的详细信息。 五、 实验过程原始记录(数据、图表、计算等) 本次实验中没有实现HITS算法

8、中要求的Web图的扩展功能，而是将图的结点和边的信息存 储在文件中，由程序读入并计算各自内容权威度和链接权威度， 并能够指定最大迭代次数和输出 迭代过程的详细信息。 Web图的构造过程的主要代码: /* * Web图类的构造方法 -4- *参数文件中每一行存储一条边的信息 *该方法将扫描文件中的每一行，将所有的边及结点信息读入并构造整个图 * 注：程序设计思想参考 http:/ * * param file 存储了图中边及结点信息的文件 * throws lOException */ public WebGraph(File file) throws lOException ( this ()

9、; / 初始化相关变量 BufferedReader reader = new BufferedReader( new FileReader(file); String line; int urllndex = 0; /读入文件，解析并存储结点及边的信息 while (line = reader.readLine() != null ) ( int index = line.indexOf( -); if (index 0) ( String urlFrom = line.substring(0, index).trim(); String urlTo = line.substring(ind

10、ex + 2).trim(); int urllndexFrom = -1; int urllndexTo = -1; / 存储URL到lD的映射 if ( urlTold .containsKey(urlFrom) ( urllndexFrom = urlTold .get(urlFrom); ) else ( idToURL .put(urllndex, urlFrom.trim(); urlTold .put(urlFrom.trim(), urllndex); urllndex+; urllndexFrom = urlTold .get(urlFrom); ) / 存储lD到URL的映

11、射 if ( urlTold .containsKey(urlTo) ( urllndexTo = urlTold .get(urlTo); ) else ( idToURL .put(urllndex, urlTo.trim(); urlTold .put(urlTo.trim(), urllndex); urllndex+; urllndexTo = urlTold .get(urlTo); ) / 存储边 Map tedge = new HashMap(); tedge.put(urllndexFrom, urllndexTo); edge .add(tedge.entrySet().i

12、terator().next(); ) ) this . nodeCount = idToURL .size(); / 结点数量 / 填充边到对应的邻接矩阵 this . matrix = new int nodeCount nodeCount ; for ( int i = 0; i edge .size(); i+) ( Entry entry = edge .get(i); ,格式如下：url1 - url2 -5- int from = entry.getKey(); int to = entry.getValue(); matrix fromto = 1; ) ) HITS算法内容权

13、威度和链接权威度的计算: /* * HITS 类构造方法 * param webGraph web 图 */ public HITS(WebGraph webGraph) ( this . webGraph = webGraph; this . authorityScores = new HashMap(); this . hubScores = new HashMap(); this . nodeCount = webGraph.getNodeCount(); /初始的内容权威度和链接权威度均设为 1 for ( int i = 0; i webGraph.getNodeCount(); i

14、+) ( this . authorityScores .put(i, 1.0); this . hubScores .put(i, 1.0); ) /计算结点的内容权威度和链接权威度 ，指定最大迭代次数为 25 computeHITS(25); ) *计算结点的内容权威度和链接权威度 * param numIterations 最大迭代次数 */ private void computeHITS( int numIterations) ( / 迭代次数 int iterNum = numIterations; / 上一次迭代的内容权威度和链接权威度 ,初始值均设为0 Map preAutho

15、rityScore = new HashMap(); Map preHubScore = new HashMap(); for ( int i = 0; i 0 & !isConvergence(preAuthorityScore, authorityScores preHubScore, hubScores ) ( /存储计算所得的内容权威度和链接权威度值 ，用于下次迭代之前的收敛判断 copyAtoB( authorityScores , preAuthorityScore);-6- WebGraph webGraphHITS = new WebGraph(fileHITS); S

16、ystem. out .println( HITS 算法示例：); System. out .println( nweb 图所对应的矩阵:); webGraphHITS.printMatrix(); System. out .println( nHITS 算法的执行过程:); hits = new HITS(webGraphHITS); copyAtoB( hubScores ,preHubScore); System. out .println( 第+ (iterNum - numIterations) + for ( int i = 0; i nodeCount ; i+) List in

17、Links = webGraph .getInLinks(i); / 入链接集 double authorityScore = 0; / 内容权威度 for (Integer in : inLinks) /内容权威度等于所有入链接的链接权威度之和 authorityScore += hubScores .get(in).doubleValue(); authorityScores .put(i, authorityScore); for ( int i = 0; i nodeCount ; i+) List outLinks = webGraph .getOutLinks(i); / 出链接集

18、 double hubScore = 0; / 链接权威度 for (Integer out : outLinks) /链接权威度等于所有出链接的内容权威度之和 hubScore += authorityScores .get(out).doubleValue(); hubScores .put(i, hubScore); /归一化(使用最大值) double aMax = getMaxValue( authorityScores ); double hMax = getMaxValue( hubScores ); for ( int i = 0; i 2A - 戏 5B 6C 测试数据以上图

19、（左）为例，将结点和边信息存入文件 hits.txt，如上图（右），将输入设为 文件hits.txt,然后运行以上测试程序，得运行结果如下: HITSW法示例：法示例： s*s*图图所对应所对应的邻接拒阵的邻接拒阵: : ABC A 1 1 1 B 1 0 1 C 0 1 0 HITSM法的执行过程法的执行过程: : 第。次迭代第。次迭代： aA = 1.0 aB = 0.732 ac = 1.0 hA = 1.0 hB = 0.732 hc = 0.2679 六、实验结果分析、经验总结或结论（例如对实验获取数据的误差分析、数据处理、成果 等。其中，绘制曲线图时必须用标准计算纸，不得随意用普通白纸绘画） 通过本次实验我们理解了 HIT S算法的基本思想和方法，并编程实现了一个简单的HITS 算法的程序，对链接结构分析子系统的作用和功能有了一个较为直观的认识。另外，这里 所得的链接结构分析结果，可A(A =1.0 AB：=1.0 AC=1.0 第第1次次迭代：迭代： AA=1.0 AC-1.0 第第2次次迭代：迭代： AA=1.0 AC =1.0 第第3次次迭代：迭代： AA=1.0 AB-0.7S AC=1.0 第第9次次迭代：迭代： AA=i.a AE=0.73S 第第5次