多媒体搜索引擎课件.ppt

1、查询结果处理多媒体搜索引擎2022年8月2日Multimedia Search Engine2查询结果处理查询的特征短英语：平均2.5词，80%02022年8月2日Multimedia Search Engine10查询结果处理结果排序2.tf-idf用idf为权重的加权词频和qttdtidftfdqs,文档中一个词的重要性nnttttttidftfidftfidftf,.,2211文档矢量文档矢量2022年8月2日Multimedia Search Engine11查询结果处理结果排序2.tf-矢量空间模型矢量空间模型(vector space model)查询查询?2022年8月2日Mul

2、timedia Search Engine12查询结果处理结果排序2.tf-idf文档矢量不一定是归一化的docdoc X 2doc X 3dqdqdqVVVVdqsim,cos,归一化因子归一化因子2022年8月2日Multimedia Search Engine13查询结果处理结果排序2.tf-idf长文档的问题：如果把文档切割成几部分l单一主题l词频比例相对固定l词条相对固定l多主题l词频比例变化较大l词条变化大2022年8月2日Multimedia Search Engine14查询结果处理结果排序2.tf-idf长文档的问题d1d2d1+d2文档集与集中单个文档的相似度如何衡量？FA

3、Q文档及其查询2022年8月2日Multimedia Search Engine15查询结果处理结果排序2.tf-idfSEO SPAM(Search Engine Optimization SPAM)l出现在搜索引擎上对网站的访问量影响巨大l希望自己的网站总是出现在搜索结果的最前面lSEO:Search Engine Optimizationl根据索引算法优化页面设计tf-idf相关性计算准则下如何优化？华师大 华师大 华师大华师大 华师大 华师大华师大 华师大 华师大华师大 华师大 华师大这个页面没人看？2022年8月2日Multimedia Search Engine16查询结果处理结果

4、排序2.tf-idfSEO SPAMl隐藏文字lMeta Tag：lImage Tag:lHTML注释l超长标题l同色文字：文字与背景色相同l自动跳转页l包含大量关键字的页面自动跳转到真实页面2022年8月2日Multimedia Search Engine17查询结果处理结果排序2.tf-idf“王婆卖瓜自卖自夸”l文档的优劣程度不可能通过文档本身来评价l通过文档本身的内容对文档排序的方法不可靠l谁可以评价文档的优劣？l用户评价l同行评议2022年8月2日Multimedia Search Engine18查询结果处理结果排序用户评价根据用户在查询结果中的点击来度量网站与关键字的相关性l需要

5、巨量的用户记录l跟踪较困难同行评议根据同行对文档质量的评价来度量网站与关键字的相关性l谁是同行？lInternet2022年8月2日Multimedia Search Engine19查询结果处理结果排序同行评议网页有很多链接Page AhyperlinkPage BAnchorJournal of the ACM.2022年8月2日Multimedia Search Engine20查询结果处理结果排序3.用链接文字索引网页Armonk,NY-based computergiant IBM announced todayJoes computer hardware linksCompaqHP

6、IBMBig Blue today announcedrecord profits for the quarter2022年8月2日Multimedia Search Engine21查询结果处理结果排序3.用链接文字索引网页http:/citeseer.ist.psu.edu/101589.htmllUsing Common Hypertext Links to Identify the Best Phrasal Description of Target Web Documents优点：可能比网页文字更准确l“旁观者清”缺点：仍然易于作弊l在自己的网站内建立大量的页面，所有页面中建立大量的

7、链接指向主页l引用分析2022年8月2日Multimedia Search Engine22查询结果处理结果排序引用分析最简单的实现：用链接数计算重要性l方法1：计算出度和入度l方法2：只计算入度l作弊还是很容易2022年8月2日Multimedia Search Engine23查询结果处理结果排序4.PageRank(Google)随机选择一个起始页面随机跳转到页面中的一个链接长时间迭代后，每个页面的被访问概率趋于稳定2022年8月2日Multimedia Search Engine24查询结果处理结果排序4.PageRank“死端点”？(dead-end)l没有链接的页面?2022年8月

8、2日Multimedia Search Engine25查询结果处理结果排序4.PageRank修正的策略l碰到死端点：随机跳转到任意页面l在非死端点：以10%概率随机跳转到任意页面，以90%概率随机跳转到某一个链接l为什么？l局部陷阱如何计算(每个页面的)这个概率？这个概率真的能够稳定吗？2022年8月2日Multimedia Search Engine26查询结果处理结果排序4.PageRank马尔科夫链(Markov chains)lN个状态lN*N个状态转换概率ikmnPikPimPin1,01NjijijPPP：N*N状态转换矩阵2022年8月2日Multimedia Search

9、Engine27查询结果处理结果排序4.PageRank各态历经(Ergodic)马尔科夫链l任意两个态之间都是连通的l从任何初始态开始，经过有限时间T0以后，在TT0时处于任何某一个态的概率大于0l所有态存在稳定的长期访问概率l该概率与起始态无关l如何计算？2022年8月2日Multimedia Search Engine28查询结果处理结果排序4.PageRank各态历经(Ergodic)马尔科夫链x=(x1,xi,xN)处于状态1的概率处于状态i的概率处于状态N的概率.11niix下一步：xP2022年8月2日Multimedia Search Engine29查询结果处理结果排序4.P

10、ageRank各态历经(Ergodic)马尔科夫链l如果我们在稳定态a=(a1,ai,aN)下一步：aP=aa是P的最大特征值对应的特征矢量对各态历经的状态转换矩阵，该特征值总是存在的2022年8月2日Multimedia Search Engine30查询结果处理结果排序4.PageRank算法1：求P的特征值和特征矢量l不现实：超高维数算法2：la=x*P*Pl可以任意取合理的x：与起始状态无关l还是比较慢思考题：如何快速计算PageRank?l针对超大规模网页链接2022年8月2日Multimedia Search Engine31查询结果处理结果排序5.HITS(Hypertext-I

11、nduced Topic Search)针对某个主题，有两类非常重要的网站l目录(hub)：本主题相关网站的列表l权威(Authority)：与本主题内容密切相关的网站l如果查询的是较宽泛的主题，则以上两类网站更能满足用户需求2022年8月2日Multimedia Search Engine32查询结果处理结果排序5.HITS通信公司张三李四中国移动中国联通中国电信2022年8月2日Multimedia Search Engine33查询结果处理结果排序5.HITS提取算法l第一步：针对某个主题，获取一个可能包含好的hub和authority的基本网页集合l用主题词作为关键字查询200-500

12、个根网页集l增加根网页集指向的网页和指向根网页集中网页的网页根网页集基本网页集2022年8月2日Multimedia Search Engine34查询结果处理结果排序5.HITS提取算法l第二步：在这个集合中找到好的hub和authorityl迭代执行下面的计算l值无限增大？l用比例因子归一化l绝对大小无意义，只需排序结果h(x)1a(x)1yxyaxh)()(xyyhxa)()(xx2022年8月2日Multimedia Search Engine35查询结果处理结果排序5.HITS迭代收敛吗？l收敛：可证明见课本迭代多少次？l5次左右即可l因为只需要排序结果2022年8月2日Multimedia Search Engine36查询结果处理结果排序现实系统中使用的方法把各种排序因子按一定权重融合lPageRankltf-idflhub-authorityl