《信息检索之HITS算法》由会员分享，可在线阅读，更多相关《信息检索之HITS算法（8页珍藏版）》请在金锄头文库上搜索。
1、-1-一、实验目的一、实验目的 理解搜索引擎的链接结构子系统的基本功能； 了解万维网链接的结构图及特性； 理解 HITS 算法的基本思想和原理。二、实验原理及基本技术路线图（方框原理图）二、实验原理及基本技术路线图（方框原理图）万维网的链接结构通常使用有向图的方式来描述，在万维网链接结构图中，网页是图的节点；而超链接则是链接节点的有向边（从源网页指向目的网页） 。每一条从源网页指向目的网页的超链接，既称为源网页的“出链接” ，又称为目的网页的“入链接” 。用图表示万维网链接结构，如下图：HBAFDECG关于万维网结构图的规模很难给出一个准确的统计结果，这是因为：图中的节点存在形式纷繁复杂，即使
2、不考虑网页的可访问性问题（部分网页会对用户访问加以限制，如采取登录策略等） ，只考虑能够被自由访问的网页，这些网页中既有以传统形式存在的静态页面，又有随用户查询要求在服务器端实时生成的动态页面，甚至还有用 AJAX 技术生成的 URL 相同但页面内容千差万别的页面。而超链接的界定在当前的网络环境下也存在诸多困难。2008 年 7 月，谷歌在其官方博客上声称其索引量达到 1 万亿网页，这一估计一定程序上反映了图的节点集合规模。链接结构信息是网络信息环境与传统信息媒介的最大区别之一。对于搜索引擎而言，与用户查询需求乃至页面内容均相对独立的超链接结构是用以评价万维网数据质量的重要依据。-2-在 20
3、01 年 SIGIR 会议上，Craswell 等人对链接结构分析算法的应用方式进行了分析，提出万维网超链接应具有的两个特性：如果存在超链接 L 从页面 Psource指向页面 Pdestiny，则 Psource与 Pdestiny满足：特性 1：（内容推荐特性）页面 Psource的作者推荐页面 Pdestiny的内容，且利用 L 的链接文本内容对 Pdestiny进行描述。特性 2：（主题相关特性）被超链接连接的两个页面 Psource与 P destiny的页面内容涉及类似的主题。然而这两个特性对于万维网数据爆炸性增长的背景下被认为过于理想主义。万维网节点之间的超链接关系远比特性 1
4、和特性 2 描述的情况要复杂的多。但是，一方面，经过改进的链接分析算法还是可以为页面质量评估提供参考；另一方面，在经过数据清理之后的近似理想的网络环境中，它们还是可以发挥其挑选高质量网页的作用，因此链接分析算法仍旧是当前研究的热点之一。HITS 算法是由 Jon Kleinberg 在 20 世纪 90 年代提出的一种链接分析算法。HITS 算法是Hyperlink-Induced Topic Search（基于超链接推演的主题搜索算法）的简称，它的核心思想是对网页如下两个方面的权威程度进行评价。首先，内容权威度（Authority Value） ，即网页本身内容的受欢迎程序；其次，链接权威度
5、（Hub Value） ，即网页链接到其他受欢迎资源的程度。HITS 算法的实施包括两个阶段，对用户输入的查询主题而言，首先是通过文本搜索过程获取与此查询主题内容相关的网页集合，并适当扩充该网页集合，以包括尽可能多的结果候选网页，同时使用结果集合网页间的链接结构关系更加完整；随后则是通过一个“迭代收敛”的过程计算网页集合中每个页面对应的链接权威度和内容权威度数值。算法最后输出的是分别按照链接权威度与内容权威度排序的结果列表，用户可以根据需求不同，选择其中的结果页面进行浏览。-3-HITS（Hyperlink-Induced Topic Search）算法）算法 （1）选取网络信息检索系统的结果
6、集合 R 将 R，R 所指向的网页和指向 R 的网页构成的链接结构图称为 G。对于 G 中每一个节点 n，设 H(n)和 A(n)分别是其链接权威度和内容权威度，向量和分别为 G 的链 H A接权威度和内容权威度结果向量。（2）设定=(1, 1, , 1)，即：对 G 中每一个节点 n，设定其初始值 H(0)(n)和 A(0)(n)均为 1. H A（3）For k=1, 2, 3, , N 对 G 中每一个节点 n，（称为 I 操作）)()()1()( iknmkmHnAi对 G 中每一个节点 n，（称为 O 操作）)()()()( ikmnkmAnHi将 H(0)(n)和 A(0)(n)(
7、nG)作规范化处理，使，。1)(2)( nAkGn1)(2)( nHkGn（4）当结果向量和未收敛时，返回（3） ；当和收敛时，输出算法所计算出的 G 中每一个节点 H A H An 的 H(0)(n)和 A(0)(n)的结果。三、所用仪器、材料（设备名称、型号、规格等）三、所用仪器、材料（设备名称、型号、规格等）硬件：PC 机一台操作系统：Windows 7编程语言：JavaIDE：eclipse 3.5.2四、实验方法、步骤四、实验方法、步骤实现 HITS 算法的主要功能模块，并可对测试数据计算所需要内容权威度和链接权威度的值。要求能够输出每次迭代过程的详细信息。五、实验过程原始记录五、实
8、验过程原始记录(数据、图表、计算等数据、图表、计算等)本次实验中没有实现 HITS 算法中要求的 Web 图的扩展功能，而是将图的结点和边的信息存储在文件中，由程序读入并计算各自内容权威度和链接权威度，并能够指定最大迭代次数和输出迭代过程的详细信息。 Web 图的构造过程的主要代码：/* Web图类的构造方法* 参数文件中每一行存储一条边的信息, 格式如下: url1 - url2-4-* 该方法将扫描文件中的每一行,将所有的边及结点信息读入并构造整个图* 注: 程序设计思想参考http:/ * param file 存储了图中边及结点信息的文件* throws IOException*/ p
9、ublic WebGraph(File file) throws IOException this(); / 初始化相关变量 BufferedReader reader = new BufferedReader(new FileReader(file); String line; int urlIndex = 0;/ 读入文件, 解析并存储结点及边的信息 while (line = reader.readLine() != null) int index = line.indexOf(“-“); if (index 0) String urlFrom = line.substring(0, i
10、ndex).trim(); String urlTo = line.substring(index + 2).trim(); int urlIndexFrom = -1; int urlIndexTo = -1;/ 存储URL到ID的映射 if (urlToId.containsKey(urlFrom) urlIndexFrom = urlToId.get(urlFrom); else idToURL.put(urlIndex, urlFrom.trim(); urlToId.put(urlFrom.trim(), urlIndex); urlIndex+; urlIndexFrom = ur
11、lToId.get(urlFrom); / 存储ID到URL的映射 if (urlToId.containsKey(urlTo) urlIndexTo = urlToId.get(urlTo); else idToURL.put(urlIndex, urlTo.trim(); urlToId.put(urlTo.trim(), urlIndex); urlIndex+; urlIndexTo = urlToId.get(urlTo); / 存储边 Map tedge = new HashMap(); tedge.put(urlIndexFrom, urlIndexTo); edge.add(t
12、edge.entrySet().iterator().next(); this.nodeCount = idToURL.size();/ 结点数量 / 填充边到对应的邻接矩阵 this.matrix = new intnodeCountnodeCount; for (int i = 0; i entry = edge.get(i);-5-int from = entry.getKey(); int to = entry.getValue(); matrixfromto = 1; HITS 算法内容权威度和链接权威度的计算：/* HITS类构造方法* param webGraph web图*/
13、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 preAuthorityScore = new HashMap(); Map preHubScore = new HashMap(); for (int i = 0; i 0-6-cop
14、yAtoB(hubScores, preHubScore);System.out.println(“第“ + (iterNum - numIterations) + “次迭代:“);for (int i = 0; i inLinks = webGraph.getInLinks(i); / 入链接集 double authorityScore = 0; / 内容权威度 for (Integer in : inLinks) / 内容权威度等于所有入链接的链接权威度之和 authorityScore += hubScores.get(in).doubleValue(); authorityScore
15、s.put(i, authorityScore); for (int i = 0; i outLinks = webGraph.getOutLinks(i); / 出链接集 double hubScore = 0; / 链接权威度 for (Integer out : outLinks) / 链接权威度等于所有出链接的内容权威度之和 hubScore += authorityScores.get(out).doubleValue(); hubScores.put(i, hubScore); / 归一化(使用最大值) double aMax = getMaxValue(authorityScor
16、es); double hMax = getMaxValue(hubScores); for (int i = 0; i nodeCount; i+) double aScore = authorityScores.get(i); double hScore = hubScores.get(i); authorityScores.put(i, aScore / aMax); hubScores.put(i, hScore / hMax); / 输出每次迭代所得的值 printAuthorAndHub(); 测试程序代码：public static void main(String args) throws IOException / HITS算法测试 File
