多媒体搜索引擎DriveHQ课件

1、多媒体搜索引擎DriveHQ,查询结果处理,多媒体搜索引擎,2020/11/12,多媒体搜索引擎DriveHQ,2,查询结果处理,查询的特征 短 英语：平均2.5词，80% 3词 不精确 “华师大” 你想要什么？ 只使用简单语法 有几个用户懂布尔代数？ 大多数查询将返回大量的结果 “华师大”：174万,2020/11/12,多媒体搜索引擎DriveHQ,3,查询结果处理,查询的特征 缺乏耐心 85%的用户只看第一页结果 78%的查询不会被用户改进 要把用户需要的结果放在第一页 结果排序,2020/11/12,多媒体搜索引擎DriveHQ,4,查询结果处理,结果排序 理想情况：把结果按与用户的需

2、求相关的程度排序 用户需要什么？ 把结果按与查询相关的程度排序 如何度量文档和查询的相关度？,“华师大”,2020/11/12,多媒体搜索引擎DriveHQ,5,查询结果处理,结果排序 1.按词频 查询关键字在文档中出现的次数越多则越相关 查询关键字有多个？ 相应词频相加,tf: term frequency (词频),重要性与词频一定是线性关系？,2020/11/12,多媒体搜索引擎DriveHQ,6,查询结果处理,结果排序 1.按词频 非线性词频 对数词频 归一化词频,2020/11/12,多媒体搜索引擎DriveHQ,7,查询结果处理,结果排序 1.按词频 非线性词频 布尔词频 对数平均

3、词频,2020/11/12,多媒体搜索引擎DriveHQ,8,查询结果处理,结果排序 1.按词频 每个词重要性一样？ “北朝鲜的核试验” 北朝鲜 / 的 / 核试验,689万网页,125万网页,?,词的重要性是不同的！,2020/11/12,多媒体搜索引擎DriveHQ,9,查询结果处理,结果排序 2.tf-idf idf: inverse document frequency 逆文档频率？,所有文档都出现的词(如“的”)：D=Dt idft = log(1) = 0 在1%文档中出现的词：D/Dt = 100 idft = log(100) 0,2020/11/12,多媒体搜索引擎Drive

4、HQ,10,查询结果处理,结果排序 2.tf-idf 用idf为权重的加权词频和,2020/11/12,多媒体搜索引擎DriveHQ,11,查询结果处理,结果排序 2.tf-idf,矢量空间模型(vector space model),?,2020/11/12,多媒体搜索引擎DriveHQ,12,查询结果处理,结果排序 2.tf-idf 文档矢量不一定是归一化的,2020/11/12,多媒体搜索引擎DriveHQ,13,查询结果处理,结果排序 2.tf-idf 长文档的问题：如果把文档切割成几部分 单一主题 词频比例相对固定 词条相对固定 多主题 词频比例变化较大 词条变化大,2020/11/

5、12,多媒体搜索引擎DriveHQ,14,查询结果处理,结果排序 2.tf-idf 长文档的问题,文档集与集中单个文档的相似度如何衡量？,2020/11/12,多媒体搜索引擎DriveHQ,15,查询结果处理,结果排序 2.tf-idf SEO SPAM (Search Engine Optimization SPAM) 出现在搜索引擎上对网站的访问量影响巨大 希望自己的网站总是出现在搜索结果的最前面 SEO: Search Engine Optimization 根据索引算法优化页面设计,tf-idf相关性计算准则下如何优化？,华师大 华师大 华师大 华师大 华师大 华师大 华师大 华师大

6、华师大 华师大 华师大 华师大,这个页面没人看？,2020/11/12,多媒体搜索引擎DriveHQ,16,查询结果处理,结果排序 2.tf-idf SEO SPAM 隐藏文字 Meta Tag： Image Tag: HTML注释 超长标题 同色文字：文字与背景色相同 自动跳转页 包含大量关键字的页面自动跳转到真实页面,2020/11/12,多媒体搜索引擎DriveHQ,17,查询结果处理,结果排序 2.tf-idf “王婆卖瓜自卖自夸” 文档的优劣程度不可能通过文档本身来评价 通过文档本身的内容对文档排序的方法不可靠 谁可以评价文档的优劣？ 用户评价 同行评议,2020/11/12,多媒体

7、搜索引擎DriveHQ,18,查询结果处理,结果排序 用户评价 根据用户在查询结果中的点击来度量网站与关键字的相关性 需要巨量的用户记录 跟踪较困难 同行评议 根据同行对文档质量的评价来度量网站与关键字的相关性 谁是同行？ Internet,2020/11/12,多媒体搜索引擎DriveHQ,19,查询结果处理,结果排序 同行评议 网页有很多链接,Journal of the ACM.,2020/11/12,多媒体搜索引擎DriveHQ,20,查询结果处理,结果排序 3. 用链接文字索引网页,Armonk, NY-based computer giant IBM announced today

8、,Joes computer hardware links Compaq HP IBM,Big Blue today announced record profits for the quarter,2020/11/12,多媒体搜索引擎DriveHQ,21,查询结果处理,结果排序 3. 用链接文字索引网页 Using Common Hypertext Links to Identify the Best Phrasal Description of Target Web Documents 优点：可能比网页文字更准确 “旁观者清” 缺点：仍然易于作弊 在自己的网站内建立大量的页面，所有页面中建

9、立大量的链接指向主页 引用分析,2020/11/12,多媒体搜索引擎DriveHQ,22,查询结果处理,结果排序 引用分析 最简单的实现：用链接数计算重要性 方法1：计算出度和入度 方法2：只计算入度 作弊还是很容易,2020/11/12,多媒体搜索引擎DriveHQ,23,查询结果处理,结果排序 4. PageRank (Google) 随机选择一个起始页面 随机跳转到页面中的一个链接 长时间迭代后，每个页面的被访问概率趋于稳定,2020/11/12,多媒体搜索引擎DriveHQ,24,查询结果处理,结果排序 4. PageRank “死端点”？(dead-end) 没有链接的页面,?,20

10、20/11/12,多媒体搜索引擎DriveHQ,25,查询结果处理,结果排序 4. PageRank 修正的策略 碰到死端点：随机跳转到任意页面 在非死端点：以10%概率随机跳转到任意页面，以90%概率随机跳转到某一个链接 为什么？ 局部陷阱,如何计算(每个页面的)这个概率？ 这个概率真的能够稳定吗？,2020/11/12,多媒体搜索引擎DriveHQ,26,查询结果处理,结果排序 4. PageRank 马尔科夫链(Markov chains) N个状态 N*N个状态转换概率,i,k,m,n,Pik,Pim,Pin,P：N*N状态转换矩阵,2020/11/12,多媒体搜索引擎DriveHQ,

11、27,查询结果处理,结果排序 4. PageRank 各态历经(Ergodic)马尔科夫链 任意两个态之间都是连通的 从任何初始态开始，经过有限时间T0以后，在TT0时处于任何某一个态的概率大于0 所有态存在稳定的长期访问概率 该概率与起始态无关 如何计算？,2020/11/12,多媒体搜索引擎DriveHQ,28,查询结果处理,结果排序 4. PageRank 各态历经(Ergodic)马尔科夫链,x = (x1, , xi, , xN),处于状态1的概率,处于状态i的概率,处于状态N的概率,2020/11/12,多媒体搜索引擎DriveHQ,29,查询结果处理,结果排序 4. PageRa

12、nk 各态历经(Ergodic)马尔科夫链 如果我们在稳定态,a = (a1, , ai, , aN),下一步：aP,= a,a是P的最大特征值对应的特征矢量,对各态历经的状态转换矩阵，该特征值总是存在的,2020/11/12,多媒体搜索引擎DriveHQ,30,查询结果处理,结果排序 4. PageRank 算法1：求P的特征值和特征矢量 不现实：超高维数 算法2： a = x*P*P 可以任意取合理的x：与起始状态无关 还是比较慢 思考题：如何快速计算PageRank? 针对超大规模网页链接,2020/11/12,多媒体搜索引擎DriveHQ,31,查询结果处理,结果排序 5. HITS

13、(Hypertext-Induced Topic Search) 针对某个主题，有两类非常重要的网站 目录(hub)：本主题相关网站的列表 权威(Authority)：与本主题内容密切相关的网站 如果查询的是较宽泛的主题，则以上两类网站更能满足用户需求,2020/11/12,多媒体搜索引擎DriveHQ,32,查询结果处理,结果排序 5. HITS,通信公司,张三,李四,中国移动,中国联通,中国电信,2020/11/12,多媒体搜索引擎DriveHQ,33,查询结果处理,结果排序 5. HITS 提取算法 第一步：针对某个主题，获取一个可能包含好的hub和authority的基本网页集合 用主题词作为关键字查询200-500个根网页集 增加根网页集指向的网页和指向根网页集中网页的网页,基本网页集,2020/11/12,多媒体搜索引擎DriveHQ,34,查询结果处理,结果排序 5. HITS 提取算法 第二步：在这个集合中找到好的hub和authority 迭代执行下面的计算 值无限增大？ 用比例因子归一化 绝对大小无意义，只需排序结果,h(x)1 a(x)1,x,2020/11/12,多媒体搜索引擎Driv