信息检索之HITS算法

-一、实验目的理解搜索引擎的链接结构子系统的基本功能；了解万维网链接的结构图及特性；理解HITS算法的基本思想和原理。二、实验原理及基本技术路线图（方框原理图）万维网的链接结构通常使用有向图的方式来描述，在万维网链接结构图中，网页是图的节点；而超链接则是链接节点的有向边（从源网页指向目的网页）。每一条从源网页指向目的网页的超链接，既称为源网页的“出链接”，又称为目的网页的“入链接”。用图表示万维网链接结构，如下图：HHBAFDECG关于万维网结构图的规模很难给出一个准确的统计结果，这是因为：图中的节点存在形式纷繁复杂，即使不考虑网页的可访问性问题（部分网页会对用户访问加以限制，如采取登录策略等），只考虑能够被自由访问的网页，这些网页中既有以传统形式存在的静态页面，又有随用户查询要求在服务器端实时生成的动态页面，甚至还有用AJAX技术生成的URL相同但页面内容千差万别的页面。而超链接的界定在当前的网络环境下也存在诸多困难。2008年7月，谷歌在其官方博客上声称其索引量达到1万亿网页，这一估计一定程序上反映了图的节点集合规模。链接结构信息是网络信息环境与传统信息媒介的最大区别之一。对于搜索引擎而言，与用户查询需求乃至页面内容均相对独立的超链接结构是用以评价万维网数据质量的重要依据。在2001年SIGIR会议上，Craswell等人对链接结构分析算法的应用方式进行了分析，提出万维网超链接应具有的两个特性：如果存在超链接L从页面Psource指向页面Pdestiny，则Psource与Pdestiny满足：特性1：（内容推荐特性）页面Psource的作者推荐页面Pdestiny的内容，且利用L的链接文本内容对Pdestiny进行描述。特性2：（主题相关特性）被超链接连接的两个页面Psource与Pdestiny的页面内容涉及类似的主题。然而这两个特性对于万维网数据爆炸性增长的背景下被认为过于理想主义。万维网节点之间的超链接关系远比特性1和特性2描述的情况要复杂的多。但是，一方面，经过改进的链接分析算法还是可以为页面质量评估提供参考；另一方面，在经过数据清理之后的近似理想的网络环境中，它们还是可以发挥其挑选高质量网页的作用，因此链接分析算法仍旧是当前研究的热点之一。HITS算法是由JonKleinberg在20世纪90年代提出的一种链接分析算法。HITS算法是Hyperlink-InducedTopicSearch（基于超链接推演的主题搜索算法）的简称，它的核心思想是对网页如下两个方面的权威程度进行评价。首先，内容权威度（AuthorityValue），即网页本身内容的受欢迎程序；其次，链接权威度（HubValue），即网页链接到其他受欢迎资源的程度。HITS算法的实施包括两个阶段，对用户输入的查询主题而言，首先是通过文本搜索过程获取与此查询主题内容相关的网页集合，并适当扩充该网页集合，以包括尽可能多的结果候选网页，同时使用结果集合网页间的链接结构关系更加完整；随后则是通过一个“迭代—收敛”的过程计算网页集合中每个页面对应的链接权威度和内容权威度数值。算法最后输出的是分别按照链接权威度与内容权威度排序的结果列表，用户可以根据需求不同，选择其中的结果页面进行浏览。HITS（Hyperlink-InducedTopicSearch）算法HITS（Hyperlink-InducedTopicSearch）算法（1）选取网络信息检索系统的结果集合R将R，R所指向的网页和指向R的网页构成的链接结构图称为G。对于G中每一个节点n，设H(n)和A(n)分别是其链接权威度和内容权威度，向量和分别为G的链接权威度和内容权威度结果向量。（2）设定==(1,1,…,1)，即：对G中每一个节点n，设定其初始值H(0)(n)和A(0)(n)均为1.（3）Fork=1,2,3,…,N①对G中每一个节点n，（称为I操作）②对G中每一个节点n，（称为O操作）③将H(0)(n)和A(0)(n)(n∈G)作规范化处理，使，。（4）当结果向量和未收敛时，返回（3）；当和收敛时，输出算法所计算出的G中每一个节点n的H(0)(n)和A(0)(n)的结果。三、所用仪器、材料（设备名称、型号、规格等）硬件：PC机一台操作系统：Windows7编程语言：JavaIDE：eclipse3.5.2四、实验方法、步骤实现HITS算法的主要功能模块，并可对测试数据计算所需要内容权威度和链接权威度的值。要求能够输出每次迭代过程的详细信息。五、实验过程原始记录(数据、图表、计算等)本次实验中没有实现HITS算法中要求的Web图的扩展功能，而是将图的结点和边的信息存储在文件中，由程序读入并计算各自内容权威度和链接权威度，并能够指定最大迭代次数和输出迭代过程的详细信息。Web图的构造过程的主要代码： /** *Web图类的构造方法 *参数文件中每一行存储一条边的信息,格式如下:url1->url2 *该方法将扫描文件中的每一行,将所有的边及结点信息读入并构造整个图 *注:程序设计思想参考/ * *@paramfile存储了图中边及结点信息的文件 *@throwsIOException */ publicWebGraph(Filefile)throwsIOException{ this();//初始化相关变量 BufferedReaderreader=newBufferedReader(newFileReader(file)); Stringline; inturlIndex=0; //读入文件,解析并存储结点及边的信息 while((line=reader.readLine())!=null){ intindex=line.indexOf("->"); if(index>0){ StringurlFrom=line.substring(0,index).trim(); StringurlTo=line.substring(index+2).trim(); inturlIndexFrom=-1; inturlIndexTo=-1; //存储URL到ID的映射 if(urlToId.containsKey(urlFrom)){ urlIndexFrom=urlToId.get(urlFrom); }else{ idToURL.put(urlIndex,urlFrom.trim()); urlToId.put(urlFrom.trim(),urlIndex); urlIndex++; urlIndexFrom=urlToId.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<Integer,Integer>tedge=newHashMap<Integer,Integer>(); tedge.put(urlIndexFrom,urlIndexTo); edge.add(tedge.entrySet().iterator().next()); } } this.nodeCount=idToURL.size();//结点数量 //填充边到对应的邻接矩阵 this.matrix=newint[nodeCount][nodeCount]; for(inti=0;i<edge.size();i++){ Entry<Integer,Integer>entry=edge.get(i); intfrom=entry.getKey(); intto=entry.getValue(); matrix[from][to]=1; } }HITS算法内容权威度和链接权威度的计算： /** *HITS类构造方法 *@paramwebGraphweb图 */ publicHITS(WebGraphwebGraph){ this.webGraph=webGraph; this.authorityScores=newHashMap<Integer,Double>(); this.hubScores=newHashMap<Integer,Double>(); this.nodeCount=webGraph.getNodeCount(); //初始的内容权威度和链接权威度均设为1 for(inti=0;i<webGraph.getNodeCount();i++){ this.authorityScores.put(i,1.0); this.hubScores.put(i,1.0); } //计算结点的内容权威度和链接权威度,指定最大迭代次数为25 computeHITS(25); } /** *计算结点的内容权威度和链接权威度 *@paramnumIterations最大迭代次数 */ privatevoidcomputeHITS(intnumIterations){ //迭代次数 intiterNum=numIterations; //上一次迭代的内容权威度和链接权威度,初始值均设为0 Map<Integer,Double>preAuthorityScore=newHashMap<Integer,Double>(); Map<Integer,Double>preHubScore=newHashMap<Integer,Double>(); for(inti=0;i<nodeCount;i++){ preAuthorityScore.put(i,0.0); preHubScore.put(i,0.0); } System.out.println("第0次迭代:"); printAuthorAndHub(); //如果未达到最大迭代次数或未收敛,则继续迭代 while((numIterations--)>0 &&!isConvergence(preAuthorityScore,authorityScores, preHubScore,hubScores)){ //存储计算所得的内容权威度和链接权威度值,用于下次迭代之前的收敛判断 copyAtoB(authorityScores,preAuthorityScore); copyAtoB(hubScores,preHubScore); System.out.println("第"+(iterNum-numIterations)+"次迭代:"); for(inti=0;i<nodeCount;i++){ List<Integer>inLinks=webGraph.getInLinks(i);//入链接集 doubleauthorityScore=0;//内容权威度 for(Integerin:inLinks){ //内容权威度等于所有入链接的链接权威度之和 authorityScore+=hubScores.get(in).doubleValue(); } authorityScores.put(i,authorityScore); } for(inti=0;i<nodeCount;i++){ List<Integer>outLinks=webGraph.getOutLinks(i);//出链接集 doublehubScore=0;//链接权威度 for(Integerout:outLinks){ //链接权威度等于所有出链接的内容权威度之和 hubScore+=authorityScores.get(out).doubleValue(); } hubScores.put(i,hubScore); } //归一化(使用最大值) doubleaMax=getMaxValue(authorityScores); doublehMax=getMaxValue(hubScores); for(inti=0;i<nodeCount;i++){ doubleaScore=authorityScores.get(i); doublehScore=hubScores.get(i); authorityScores.put(i,aScore/aMax); hubScores.put(i,hScore/hMax); } //输出每次迭代所得的值 printAuthorAndHub(); } }测试程序代码： publicstaticvoidmain(String[]args)throwsIOException{ //HITS算法测试 FilefileHITS=newFile("hits.txt"); WebGraphwebGraphHITS=newWeb