多媒体搜索引擎DriveHQppt课件.ppt

查询结果处理 多媒体搜索引擎 28 03 2020 MultimediaSearchEngine 2 查询结果处理 查询的特征短英语 平均2 5词 80 3词不精确 华师大 你想要什么 只使用简单语法有几个用户懂布尔代数 大多数查询将返回大量的结果 华师大 174万 28 03 2020 MultimediaSearchEngine 3 查询结果处理 查询的特征缺乏耐心85 的用户只看第一页结果78 的查询不会被用户改进 要把用户需要的结果放在第一页 结果排序 28 03 2020 MultimediaSearchEngine 4 查询结果处理 结果排序理想情况 把结果按与用户的需求相关的程度排序用户需要什么 把结果按与查询相关的程度排序如何度量文档和查询的相关度 华师大 28 03 2020 MultimediaSearchEngine 5 查询结果处理 结果排序1 按词频查询关键字在文档中出现的次数越多则越相关查询关键字有多个 相应词频相加 tf termfrequency 词频 重要性与词频一定是线性关系 28 03 2020 MultimediaSearchEngine 6 查询结果处理 结果排序1 按词频非线性词频对数词频归一化词频 28 03 2020 MultimediaSearchEngine 7 查询结果处理 结果排序1 按词频非线性词频布尔词频对数平均词频 28 03 2020 MultimediaSearchEngine 8 查询结果处理 结果排序1 按词频每个词重要性一样 北朝鲜的核试验 北朝鲜 的 核试验 689万网页 125万网页 词的重要性是不同的 28 03 2020 MultimediaSearchEngine 9 查询结果处理 结果排序2 tf idfidf inversedocumentfrequency逆文档频率 所有文档都出现的词 如 的 D Dt idft log 1 0在1 文档中出现的词 D Dt 100 idft log 100 0 28 03 2020 MultimediaSearchEngine 10 查询结果处理 结果排序2 tf idf用idf为权重的加权词频和 28 03 2020 MultimediaSearchEngine 11 查询结果处理 结果排序2 tf idf 矢量空间模型 vectorspacemodel 28 03 2020 MultimediaSearchEngine 12 查询结果处理 结果排序2 tf idf文档矢量不一定是归一化的 28 03 2020 MultimediaSearchEngine 13 查询结果处理 结果排序2 tf idf长文档的问题 如果把文档切割成几部分单一主题词频比例相对固定词条相对固定多主题词频比例变化较大词条变化大 28 03 2020 MultimediaSearchEngine 14 查询结果处理 结果排序2 tf idf长文档的问题 文档集与集中单个文档的相似度如何衡量 28 03 2020 MultimediaSearchEngine 15 查询结果处理 结果排序2 tf idfSEOSPAM SearchEngineOptimizationSPAM 出现在搜索引擎上对网站的访问量影响巨大 希望自己的网站总是出现在搜索结果的最前面 SEO SearchEngineOptimization根据索引算法优化页面设计 tf idf相关性计算准则下如何优化 华师大华师大华师大华师大华师大华师大华师大华师大华师大华师大华师大华师大 这个页面没人看 28 03 2020 MultimediaSearchEngine 16 查询结果处理 结果排序2 tf idfSEOSPAM隐藏文字MetaTag ImageTag HTML注释超长标题同色文字 文字与背景色相同自动跳转页包含大量关键字的页面自动跳转到真实页面 28 03 2020 MultimediaSearchEngine 17 查询结果处理 结果排序2 tf idf 王婆卖瓜自卖自夸 文档的优劣程度不可能通过文档本身来评价 通过文档本身的内容对文档排序的方法不可靠 谁可以评价文档的优劣 用户评价同行评议 28 03 2020 MultimediaSearchEngine 18 查询结果处理 结果排序用户评价根据用户在查询结果中的点击来度量网站与关键字的相关性需要巨量的用户记录跟踪较困难同行评议根据同行对文档质量的评价来度量网站与关键字的相关性谁是同行 Internet 28 03 2020 MultimediaSearchEngine 19 查询结果处理 结果排序同行评议网页有很多链接 JournaloftheACM 28 03 2020 MultimediaSearchEngine 20 查询结果处理 结果排序3 用链接文字索引网页 Armonk NY basedcomputergiantIBMannouncedtoday Joe scomputerhardwarelinksCompaqHPIBM BigBluetodayannouncedrecordprofitsforthequarter 28 03 2020 MultimediaSearchEngine 21 查询结果处理 结果排序3 用链接文字索引网页UsingCommonHypertextLinkstoIdentifytheBestPhrasalDescriptionofTargetWebDocuments优点 可能比网页文字更准确 旁观者清 缺点 仍然易于作弊在自己的网站内建立大量的页面 所有页面中建立大量的链接指向主页 引用分析 28 03 2020 MultimediaSearchEngine 22 查询结果处理 结果排序引用分析最简单的实现 用链接数计算重要性方法1 计算出度和入度方法2 只计算入度 作弊还是很容易 28 03 2020 MultimediaSearchEngine 23 查询结果处理 结果排序4 PageRank Google 随机选择一个起始页面随机跳转到页面中的一个链接 长时间迭代后 每个页面的被访问概率趋于稳定 28 03 2020 MultimediaSearchEngine 24 查询结果处理 结果排序4 PageRank 死端点 dead end 没有链接的页面 28 03 2020 MultimediaSearchEngine 25 查询结果处理 结果排序4 PageRank修正的策略碰到死端点 随机跳转到任意页面在非死端点 以10 概率随机跳转到任意页面 以90 概率随机跳转到某一个链接 为什么 局部陷阱 如何计算 每个页面的 这个概率 这个概率真的能够稳定吗 28 03 2020 MultimediaSearchEngine 26 查询结果处理 结果排序4 PageRank马尔科夫链 Markovchains N个状态N N个状态转换概率 i k m n Pik Pim Pin P N N状态转换矩阵 28 03 2020 MultimediaSearchEngine 27 查询结果处理 结果排序4 PageRank各态历经 Ergodic 马尔科夫链任意两个态之间都是连通的从任何初始态开始 经过有限时间T0以后 在T T0时处于任何某一个态的概率大于0 所有态存在稳定的长期访问概率 该概率与起始态无关 如何计算 28 03 2020 MultimediaSearchEngine 28 查询结果处理 结果排序4 PageRank各态历经 Ergodic 马尔科夫链 x x1 xi xN 处于状态1的概率 处于状态i的概率 处于状态N的概率 28 03 2020 MultimediaSearchEngine 29 查询结果处理 结果排序4 PageRank各态历经 Ergodic 马尔科夫链如果我们在稳定态 a a1 ai aN 下一步 aP a a是P的最大特征值对应的特征矢量 对各态历经的状态转换矩阵 该特征值总是存在的 28 03 2020 MultimediaSearchEngine 30 查询结果处理 结果排序4 PageRank算法1 求P的特征值和特征矢量不现实 超高维数算法2 a x P P 可以任意取合理的x 与起始状态无关还是比较慢 思考题 如何快速计算PageRank 针对超大规模网页链接 28 03 2020 MultimediaSearchEngine 31 查询结果处理 结果排序5 HITS Hypertext InducedTopicSearch 针对某个主题 有两类非常重要的网站目录 hub 本主题相关网站的列表权威 Authority 与本主题内容密切相关的网站 如果查询的是较宽泛的主题 则以上两类网站更能满足用户需求 28 03 2020 MultimediaSearchEngine 32 查询结果处理 结果排序5 HITS 通信公司 张三 李四 中国移动 中国联通 中国电信 28 03 2020 MultimediaSearchEngine 33 查询结果处理 结果排序5 HITS提取算法第一步 针对某个主题 获取一个可能包含好的hub和authority的基本网页集合用主题词作为关键字查询 200 500个根网页集增加根网页集指向的网页和指向根网页集中网页的网页 基本网页集 28 03 2020 MultimediaSearchEngine 34 查询结果处理 结果排序5 HITS提取算法第二步 在这个集合中找到好的hub和authority迭代执行下面的计算值无限增大 用比例因子归一化 绝对大小无意义 只需排序结果 h x 1a x 1 x 28 03 2020