AI 技术内参
洪亮劼
Etsy 数据科学主管,前雅虎研究院资深科学家
33455 人已学习
新⼈⾸单¥98
登录后,你可以任选6讲全文学习
课程目录
已完结/共 166 讲
开篇词 (1讲)
人工智能国际顶级会议 (31讲)
搜索核心技术 (28讲)
推荐系统核心技术 (22讲)
数据科学家与数据科学团队养成 (25讲)
AI 技术内参
15
15
1.0x
00:00/00:00
登录|注册

050 | 经典图算法之HITS

计算权威值和枢纽值
构建相邻图
用矩阵表达
求解X和Y
页面的权威值和枢纽值
循环定义
输出链接和输入链接
特点
原始定义和算法
简明历史
依赖于查询关键字
计算量大
查询关键字相关
收敛性
迭代计算
应用于搜索
数学表述
权威和枢纽结点
网页的网络结构
与PageRank算法同时期发表
由乔·克莱恩堡于1998年发明
小结
弱点
特点
基本原理
简要历史
HITS算法

该思维导图由 AI 生成,仅供参考

这周我们分享的内容是如何理解网页和网页之间的关系。周一我们介绍了用图(Graph)来表达网页与网页之间的关系并计算网页的重要性,就是经典算法 PageRank。今天我来介绍一下 PageRank 的姊妹算法:HITS 算法

HITS 的简要历史

HITS 是 Hypertext-Induced Topic Search 算法的简称。这个算法是由康奈尔大学计算机科学教授乔·克莱恩堡(Jon Kleinberg)于 1998 年发明的,正好和我们周一讲的布林和佩奇发表 PageRank 算法是同一年。
这里有必要简单介绍一下乔这个人。乔于 1971 年出生在马萨诸塞州波士顿。1993 年他毕业于康奈尔大学获得计算机科学学士学位,并于 1996 年从麻省理工大学获得计算机博士学位。1998 的时候,乔正在位于美国西海岸硅谷地区的 IBM 阿尔玛登(Almaden)研究院做博士后研究。HITS 的工作最早发表于 1998 年在旧金山举办的第九届 ACM-SIAM 离散算法年会上(详细论述可参阅参考文献)。
乔目前是美国国家工程院(National Academy of Engineering)和美国自然与人文科学院(American Academy of Arts and Sciences)院士。顺便提一下,乔的弟弟罗伯特·克莱恩堡也在康奈尔大学计算机系任教职。

HITS 的基本原理

在介绍 HITS 算法的基本原理之前,我们首先来复习一下网页的网络结构。每一个网页都有一个“输出链接”(Outlink)的集合。输出链接指的是从当前网页出发所指向的其他页面,比如从页面 A 有一个链接到页面 B,那么 B 就是 A 的输出链接。根据这个定义,我们来看“输入链接”(Inlink),指的就是指向当前页面的其他页面,比如页面 C 指向页面 A,那么 C 就是 A 的输入链接。
要理解 HITS 算法,我们还需要引入一组概念:“权威”(Authority)结点“枢纽”(Hub)结点。这两类结点到底是什么意思呢?
确认放弃笔记?
放弃后所记笔记将不保留。
新功能上线,你的历史笔记已初始化为私密笔记,是否一键批量公开?
批量公开的笔记不会为你同步至部落
公开
同步至部落
取消
完成
0/2000
荧光笔
直线
曲线
笔记
复制
AI
  • 深入了解
  • 翻译
    • 英语
    • 中文简体
    • 中文繁体
    • 法语
    • 德语
    • 日语
    • 韩语
    • 俄语
    • 西班牙语
    • 阿拉伯语
  • 解释
  • 总结

HITS算法是一种用于计算网页重要性的算法,它包括权威值和枢纽值两个概念。权威值表示页面被其他枢纽页面链接的程度,而枢纽值表示页面链接到其他权威页面的程度。这种循环定义需要为每个页面准备两个值,即权威值和枢纽值。通过矩阵运算和特征向量求解,HITS算法可以计算出每个页面的权威值和枢纽值。与PageRank算法不同,HITS是查询关键字相关的算法,可以为用户提供不同的网页排序结果。然而,HITS算法在原始情况下可能不收敛到唯一解,需要进行类似于PageRank的处理。虽然HITS算法提供了新的视角,但其依赖于查询关键字可能导致计算量巨大。文章还提出了一个思考题,即是否可以将权威值和枢纽值对应的两个排序合并成一个排序。 HITS算法的核心思想是通过权威值和枢纽值来衡量网页的重要性,为用户提供不同的排序视角。

仅可试看部分内容,如需阅读全部内容,请付费购买文章所属专栏
《AI 技术内参》
新⼈⾸单¥98
立即购买
登录 后留言

全部留言(3)

  • 最新
  • 精选
  • xxw
    感觉可以适量列些公式。用文字表达公司有点闷逼
    2018-05-21
    4
  • 黄德平
    理一下思路,L表示连接矩阵,Lij是矩阵i行j列的元素,这个值取1当且仅当节点有链接指向节点j,否则为0。L的转置用M表示,根据权威值X和枢纽值Y的定义,我们可以得到 X=MY Y=LX 进一步可以得到 X=MLX Y=LMY LM和ML分别是两个矩阵的乘积,X和Y 可以迭代求解了。 真是费劲。。。 极客时间的回复是否可以支持latex公式渲染,或者图片
    2018-12-16
    3
  • 白杨
    某种意义上,可以把权威理解为精度,枢纽理解为广度,然后用F值的思想去合并
    2018-05-16
    1
收起评论
显示
设置
留言
3
收藏
沉浸
阅读
分享
手机端
快捷键
回顶部