hits算法python实现,hits算法提出哪两种关键的概念

　　hits(Hyperlink-Induced Topic Search)算法由康奈尔大学的乔恩克莱因伯格博士于1997年首次提出，它是IBM Almaden研究中心名为“CLEVER”的研究项目的一部分。

　　HITS算法是链接分析中非常基础和重要的算法，已经被Teoma搜索引擎(www.teoma.com)在实践中使用。

　　1.中心页面和权威页面Hub页面（枢纽页面）和Authority页面（权威页面）是HITS算法最基本的两个定义。

　　所谓“权威”页面，是指与某个领域或话题相关的优质网页，如搜索引擎领域，谷歌、百度的首页，即该领域的优质网页，如视频领域，优酷、土豆的首页，即该领域的优质网页。

　　所谓“枢纽”页面是指包含许多高质量“权威”页面链接的网页。比如hao123的首页，可以算是典型的高质量“枢纽”网页。

　　图1显示了一个“Hub”页面的例子，它由斯坦福大学的计算语言学研究组维护。该页面收集了与统计自然语言处理相关的优质资源，包括一些著名的开源软件包和语料库，并通过链接指向这些资源页面。这个页面可以认为是“自然语言处理”领域的“枢纽”页面。相应的，这个页面所指向的资源页面，大部分都是高质量的“权威”页面。

　　图1自然语言处理领域的Hub页面

　　HITS算法的目的是通过一定的技术手段在海量网页中找到与用户查询主题相关的高质量“权威”页面和“枢纽”页面，尤其是“权威”页面，因为这些页面代表了能够满足用户查询的高质量内容，搜索引擎将其作为搜索结果返回给用户。

　　2.算法的基本思想：相互增强。

　　假设1:一个好的“权威”页面会被很多好的“枢纽”页面指向；

　　假设2:一个好的“枢纽”页会指向很多好的“权威”页；

　　3.HITS算法具体算法：可以利用上述两个基本假设，以及相互增强的原理等。进行多轮迭代计算，每轮迭代计算更新每页的两个权重，直到权重稳定，没有明显变化。

　　步骤：

　　3.1 根集合

　　1)向基于关键词查询的检索系统提交查询Q，从返回的结果页面集合中取前N个网页(如n=200)为根集合(root set)，记为root，则root满足：

　　1).根目录下的网页比较少。

　　2).root中的网页是与查询q相关的网页。

　　3).根中的网页包含更多权威网页。

　　这个集合是一个有向图结构：

　　3.2 扩展集合base

　　在根集root的基础上，HITS算法扩展了网页集(参考图2)。扩展原理是：将所有直接链接到根集合中网页的网页扩展到集合库，无论是有根集合中网页的链接，还是根集合中网页有链接，都扩展到扩展后的网页集合base。HITS算法在这个扩展的网页集中寻找一个好的“中心”页面和一个好的“权威”页面。

　　2图根集和可拓集

　　base

　　3.3 计算扩展集base中所有页面的Hub值（枢纽度）和Authority值（权威度），分别表示网页节点I的权威值(权威度)和中心值(中心度)

　　2)对于“扩展集1)”，我们不知道哪些页面是好的“枢纽”或“权威”页面，每个页面都有潜在的可能性，所以为每个页面设置两个权重，分别记录这个页面是好的枢纽或权威页面的可能性。在初始情况下，在没有更多可用信息之前，每个页面的两个权重是相同的，它们都可以设置为1，即：

　　扩展集base

　　在该迭代中，网页a (i)的权威权重是指向网页a (i)的所有中枢权重的总和：

　　a(I)=h(I)；

　　网页的中心分数(I)是所指向页面的权威权重的总和：

　　h(I)=a(I).

　　标准化a (i)和h (i):

　　将所有网页的中心性除以最高中心性，以标准化它们：

　　a(I)=a(I)/ a(I)；

　　按最高权限划分所有网页的权限，使其标准化：

　　h (i)=h (i)/h(i):

　　3）每次迭代计算Hub权值和Authority权值：上一次迭代计算的权重与当前迭代后的权重之差。如果发现权值总体上没有明显变化，说明系统已经进入稳定状态，可以结束计算，即a (u)，h(v)收敛。

　　算法描述：

　　如图3所示，给出了迭代计算过程中一个页面的Hub权重和Authority权重的更新方法。假设A(i)代表网页I的权威权重，H(i)代表网页I的Hub权重，在图6-14的例子中，“扩展网页集合”中有三个页面的链接指向页面1，而页面1有三个链接指向其他页面。那么，网页1在本次迭代中的权威权重就是指向网页1的所有Hub权重之和；类似地，网页1的中心分数是所指向的页面的权威权重的总和。

　　图3中心和权威权重计算

　　5）如此不断的重复第4）：

　　根据权威权重从高到低对页面进行排序，并且具有最高权重的页面作为响应于用户查询的搜索结果被输出。

　　4.HITS算法的问题4。HITS算法总体上是一种有效的算法。目前不仅用于搜索引擎领域，还被“自然语言处理”、“社会分析”等许多其他计算机领域借鉴，取得了良好的应用效果。然而，HITS算法的原始版本仍然存在一些问题，许多基于HITS算法的后续链接分析方法被提出来改进这些问题。

　　综上所述，HITS算法在以下几个方面存在不足：

　　1.计算效率低。

　　HITS算法与查询相关，所以必须在收到用户查询后实时计算。HITS算法本身需要多轮迭代计算才能得到最终结果，导致其计算效率较低，在实际应用中必须慎重考虑。

　　2.话题漂移。

　　如果扩展网页集包含一些与查询主题无关的页面，并且这些页面之间有很多链接，那么HITS算法可能会给这些无关的网页一个很高的排名，导致搜索结果的主题漂移。这种现象被称为“紧密联系的群体效应”。

　　3.容易被骗子操纵。

　　HITS在机制上很容易被作弊者操纵。例如，骗子可以建立一个网页，其中有许多指向高质量网页或著名网站的URL。这是一个很好的Hub页面，然后作弊者可以把这个网页链接指向作弊网页，这样可以提高作弊网页的权威评分。

　　4.不稳定结构

　　所谓结构不稳定，是指在原有的“扩展网页集合”中，如果增加或删除个别网页或改变少数链接，HITS算法的排名结果会发生较大变化。

　　5.HITS算法和PageRank算法的比较3.4 输出排序结果HITS算法和PageRank算法可以说是搜索引擎链接分析最基本也是最重要的两个算法。从以上对两种算法的介绍可以看出，两种算法在基本的概念模型、计算思路和技术实现细节上都存在很大的差异。在这里，两种算法的区别逐一说明。

　　1.HITS算法与用户输入的查询请求密切相关，而PageRank与查询请求无关。因此，HITS算法可以单独作为相似度计算的评价标准，而PageRank必须与内容相似度计算相结合，才能用于评价网页的相关性。

　　2.HITS算法与用户查询密切相关，在接收到用户查询后必须实时计算，计算效率低；而PageRank可以在爬虫爬行后离线计算，计算结果可以直接在线使用，所以计算效率高。

　　3.HITS算法计算对象数量少，只需要计算扩展集中网页之间的链接关系；PageRank是一种全局算法，它处理所有的互联网页面节点。

　　4.比较计算效率和对象集大小，PageRank更适合部署在服务器端，HITS算法更适合部署在客户端；

　　5.HITS算法存在主题泛化的问题，因此更适合处理特定的用户查询；PageRank在处理广泛的用户查询方面更有优势；

　　6.HITS算法需要为每个页面计算两个分值，而PageRank只需要计算一个分值；在搜索引擎领域，更多关注的是HITS算法计算的权威权重，但在其他很多应用HITS算法的领域，Hub评分也起着重要的作用；

　　7.从链接反作弊的角度来看，PageRank在机制上优于HITS算法，而HITS算法更容易受到链接作弊的影响。

　　8.八号。HITS算法结构不稳定。当“扩展网页集合”中的链接稍有变动，最终排名会受到很大影响；相比于HITS，PageRank是稳定的，根本原因在于PageRank计算中的“远程跳转”。

　　更多数据挖掘算法：【十八大】(https://github.com/linyiqun/datamining算法)3359github.com/linyiqun/datamining算法

郑重声明：本文由网友发布，不代表盛行IT的观点，版权归原作者所有，仅为传播更多信息之目的，如有侵权请联系，我们将第一时间修改或删除，多谢。