算法搜索引擎教程

1主讲:于俊清http://media.
hust.
edu.
cn搜索引擎技术基础1内容提要搜索引擎的前世今生商用搜索引擎结构与组成搜索引擎质量评估搜索引擎排序策略分布式搜索引擎http://media.
hust.
edu.
cn2搜索引擎的排序策略用户的浏览行为F现象排序策略将用户最想要的网页放在前面有哪些因素可以影响网页的排序http://media.
hust.
edu.
cn3搜索引擎的排序算法文本信息检索模型布尔模型向量空间模型概率模型语言模型http://media.
hust.
edu.
cn4搜索引擎的排序算法链接分析排序HITS算法PageRank算法Hilltop算法其他提升网页排序的方法http://media.
hust.
edu.
cn5文本信息检索模型文档和查询词差异在于如何定义和计算文档与检索词之间的关系http://media.
hust.
edu.
cn62布尔模型布尔模型基于集合论和布尔代数早期搜索引擎使用的检索模型三个主要逻辑运算符http://media.
hust.
edu.
cnABABBA逻辑与逻辑或逻辑非逻辑与、逻辑或、逻辑非示意图7布尔模型http://media.
hust.
edu.
cngoogle搜索引擎提供的布尔模型搜索8布尔模型布尔模型示例查询词Q=(K1ANDK2)OR(K3NOTK4)检索步骤首先,分别检索含有关键词K1、K2、K3和K4的文档集合,记为C1、C2、C3、C4http://media.
hust.
edu.
cnK1nDocsK2nDocsK3nDocsK4nDocsDoc1Doc2Doc3Doc4Doc1Doc2Doc1Doc2Doc3Doc19布尔模型检索步骤(续)然后通过集合的布尔运算C=(C1ANDC2)OR(C3NOTC4)最终得到该检索词的返回文档集合C,运算过程如下最终返回文档集合{Doc1,Doc2,Doc3}http://media.
hust.
edu.
cn布尔表达式页面C1ANDC2{Doc1,Doc2}C3NOTC4{Doc2,Doc3}(C1ANDC2)OR(C3NOTC4){Doc1,Doc2,Doc3}10布尔模型特点是一种精确匹配的检索模型返回只有两种状态,难以排序用户使用门槛高http://media.
hust.
edu.
cn11向量空间模型提出SaltonCommunicationsoftheACM,1975基本思想事物由原子性基本单元构成词项作为原子单元http://media.
hust.
edu.
cnɑABCDocQuery向量空间模型示例123向量空间模型网页文本表示为如下n维向量:表示该文档在第j个词项上的权重包含d个页面的集合可以表示为一个矩阵:http://media.
hust.
edu.
cnTerm1Term2TermnDoc1Doc2Docd13向量空间模型利用空间向量模型度量两个文本之间的相似度两个文档分别表示为内积相似度可表示为问题:内积相似度度量更偏向于较长的文档——改进比内积相似度更有效的相似度度量——余弦相似度http://media.
hust.
edu.
cn14向量空间模型余弦相似度与内积相似度的不同:它对内积相似度进行了归一化通过归一化避免文档长度对相似度度量的影响对于文档D和查询词Q,其余弦相似度为:http://media.
hust.
edu.
cn15向量空间模型关键词与文档之间的相关度用关键词出现的次数(频率)度量——TF(TermFrequence)频率越高越重要某个词项k在文档中的TF值即该词项出现次数除以该文档的长度(所有词的个数):表示词项k在中的出现次数http://media.
hust.
edu.
cn16向量空间模型大量文档中,关键词出现的次数越少,其重要性越高,权值越大IDF(Inversedocumentfrequence)对于词项k中的IDF值计算如下:出现词项k的文档数N:集合中的文档数http://media.
hust.
edu.
cn17向量空间模型TF、IDF计算实例对于如下4个文档:http://media.
hust.
edu.
cnd1清华大学是中国著名高等学府d2清华大学的前身是清华学堂d3清华大学面临前所未有的历史机遇d4清华大学跻身世界一流大学行列184向量空间模型TF、IDF计算实例(续)http://media.
hust.
edu.
cn假设某个词项在文档中的权重是它出现的次数,则得如图矩阵:Termd1d2d3d4清华1211大学1112中国1000著名1000高等1000学府1000前身0100学堂0100面临0010前所未有0010历史0010机遇0010跻身0001世界0001一流0001行列000119向量空间模型TF、IDF计算实例(续)http://media.
hust.
edu.
cn词项"清华"在文档d2中的TF、IDF值:TF2,清华=2/(2+1+1+1)=0.
4IDF清华=log(4/4)词项"面临"在文档d3中的TF、IDF值为:TF3,面临=1/6IDF面临=log(4/1)20向量空间模型TF、IDF应用如输入搜索词"一流大学",搜索范围为上述四个文档d1、d2、d3、d4将此项分解为"一流"、"大学"词项"一流"在四个文档中的TF值:TF1,一流=0/6=0TF2,一流=0/4=0TF3,一流=0/6=0TF4,一流=1/7=0.
143http://media.
hust.
edu.
cn21向量空间模型TF、IDF应用(续)词项"大学"在四个文档中的TF值TF1,大学=1/6=0.
167TF2,大学=1/4=0.
25TF3,大学=1/6=0.
167TF4,大学=2/7=0.
286"一流"、"大学"在四个文档中的IDF值IDF一流=log(4/0),IDF大学=log(4/4)=0http://media.
hust.
edu.
cn22向量空间模型TF、IDF分析TF值表示某词项在某一文档中的重要程度,即TF值越大说明该词项越重要IDF值表示某词项在集合文档中的重要程度,一个词项出现的文档数越多,说明该词项的区分度越差,其在文档集合中的重要性就越低http://media.
hust.
edu.
cn23向量空间模型特点简单,易于实现对网页质量要求较高空间映射问题词项不匹配——解决方案http://media.
hust.
edu.
cn245向量空间模型向量空间模型问题解决充分利用锚文本(anchortext)信息提高网页向量表示的精确性根据语义对查询词进行扩展用户先验行为信息积累对用户整体搜索偏好和热点分析,提高检索实时性对用户个体检索偏好分析,提高信息检索个性http://media.
hust.
edu.
cn25万维网链接结构图Graph节点A-H:网页有向边:网页之间的连接关系链接结构分析http://media.
hust.
edu.
cnHBAFEDCG26万维网链接结构关系用邻接矩阵M表示,其中某个元素的取值满足:注:n为链接结构图Graph的节点规模,则邻接矩阵M为的矩阵链接结构分析http://media.
hust.
edu.
cn27链接结构图Graph的邻接矩阵表示:链接结构分析http://media.
hust.
edu.
cn28链接结构分析万维网的规模很难给出准确的统计结果网页存在形式复杂——静态页面、动态页面(服务器端自动生成的超链接等)通过实验性万维网语料库相关数据估算AltaVista:2.
03亿网页,14.
66亿链接ClueWeb09:10.
41亿节点,79.
44亿链接SogouT:1.
39亿网页,33.
4亿链接节点集合规模在万亿以上边集合规模约为节点集合规模的几到几十倍http://media.
hust.
edu.
cn29链接结构分析万维网链接图连通情况基本概念强连通子图(StronglyConnectedComponent,SCC)弱连通子图(WeaklyConnectedComponent,WCC)强、弱连通子图规模分布规律基本相同设连通子图的规模为Size,而具有规模Size的连通子图数目Number近似满足http://media.
hust.
edu.
cn306链接结构分析万维网链接图连通情况指数形式表示语料库中词项出现频率与按频率排名的规律——幂律分布幂律分布广泛存在于自然科学与社会科学研究中地震规模大小的分布、月球表面月坑直径的分布战争规模的分布、大多数国家姓氏的分布http://media.
hust.
edu.
cn31链接结构分析万维网链接结构图的面貌"领结"形式的结构(bow-tiestructure)Core:规模最大的强连通子图SCChttp://media.
hust.
edu.
cnCore27.
7%IN21.
2%OUT21.
2%Others29.
9%32链接结构分析万维网链接图入度和出度反映某节点(网页)被其他节点(网页)链接以及链接到其他节点(网页)的情况入度为Indegree的网页数目N(Indegree)出度为Outdegree的网页数目N(Outdegree)ɑ、均为大于零的参数,C与C'为常数http://media.
hust.
edu.
cn33链接结构分析万维网链接图入度和出度分布情况(a)入度(b)出度http://media.
hust.
edu.
cn34链接结构分析万维网链接图入度和出度分布情况(续)由上图实验数据得:入度与出度分别服从指数为ɑ=2.
09与=2.
72的幂律分布大部分网页入度出度值低,即高质量网页数目少出度值小于10的网页数目分布未严格遵循幂律,因网页中均有难以删除的"刚性"超链接http://media.
hust.
edu.
cn35链接结构分析超链接结构分析基础——超链接的两个特性特性1:内容推荐特性链接文本检索算法,提高网络信息检索质量如HITS算法和PageRank算法特性2:主题相关特性重复/冗余网页判定算法如扩散(SpreadingActivity,SA)算法http://media.
hust.
edu.
cn367链接结构分析超链接的两个特性(续)万维网节点间的超链接关系远比上述特性1、2描述的情况复杂的多,如:导航栏链接:方便并协助用户访问广告等商业内容传播链接版权信息、注册信息超链接http://media.
hust.
edu.
cn37HITS算法HITSHITS:Hyperlink-InducedTopicSearch,针对特定主题文档进行链接分析计算JonKleinberg(CornellUniversity)核心思想:页面质量从如下两方面进行评价内容权威度(AuthorityValue)链接权威度(HubValue)举例--什么是一篇"好"论文--哪个城市"重要"http://media.
hust.
edu.
cn38HITS算法实施方式首先,文本搜索过程选取网络信息检索结果集合R,将R,R所指向以及指向R的网页构成的链接结构图称为G对G中每一个节点n,设定器内容权威度A(0)(n)和链接权威度H(0)(n)初始值均为1迭代计算,Fork=1,2,3,…,N,对G中每一个节点n--I操作--O操作http://media.
hust.
edu.
cn39HITS算法迭代过程迭代结束判断结果向量和收敛,或达到迭代次数上限N——结果向量一定收敛吗http://media.
hust.
edu.
cnHb1HbkAf1AfmApHpPageP…Sum…Sum40HITS算法收敛性说明设G对应的邻接矩阵为M,则有:http://media.
hust.
edu.
cn41HITS算法收敛性说明(续)若代入初始条件,假设,则由此知HITS算法的收敛性,和分别收敛到对应矩阵的主特征向量算法收敛速度与矩阵各个特征值之间的大小关系相关http://media.
hust.
edu.
cn428HITS算法HITS算法的缺陷内容检索算法并非总是格外有效噪音影响:与主题不相关文档主题偏移:与主题部分相关文档运行效率运算量比PageRank小准确性高于PageRank算法但需实时进行Connectivityserver可实现一定程度的在线实时计算,但计算代价过高,难应用于大规模的网页数据集http://media.
hust.
edu.
cn43PageRank算法SergeyBrin、LarryPage(Google)搜索引擎排序算法算法描述把超链接关系作为一个"投票"动作获得较多投票的网页质量较高入链接个数:直接统计票数,各票等权重PageRank:质量较高的网页投票权重较高"不公平"的"民主决策"过程http://media.
hust.
edu.
cn44PageRank算法PageRank算法运行定义"网页质量"HITS:链接权威度与内容权威度PageRank:用户随机浏览互联网时访问到某个页面的概率大小估计用户访问某网页的概率建立用户浏览模型——"随机游走"(randomwalk)模型随机:浏览起始点及页内超链接选择的随机性http://media.
hust.
edu.
cn45PageRank算法随机浏览模型网民小刚使用浏览器的收藏夹提供的"随便逛逛"功能进行万维网冲浪(注:该浏览器未设置"地址栏"及"后退"按钮)小刚使用"随便逛逛"功能挑选一随机起点进行访问,浏览该页面后他可能点击页面上某链接继续访问他感兴趣的内容,也可能使用"随便逛逛"功能跳转到另一网页浏览浏览中某网页被访问的概率称为该页面的PageRankhttp://media.
hust.
edu.
cn46PageRank算法网页A的PageRank估算小刚使用"随便逛逛"跳转到页面A,则A被访问概率--N为互联网上的网页总数浏览中通过其他网页超链接访问到A,则通过Pi页面访问到A的概率为:注:P1,…,Pk为链接到A的所有网页--访问Pi的概率--访问Pi时点击页面A超链接的概率通过Pi访问到A的概率为:http://media.
hust.
edu.
cn47PageRank算法网页A的PageRank估算(续)通过P1,…,Pk这k个页面访问到A的概率综上:设小刚主动使用"随便逛逛"功能的概率为ɑ,则页面A被访问的概率为http://media.
hust.
edu.
cn489PageRank算法网页A的PR值计算实例如blog.
sina.
com.
cn/seo的PR=4,blog.
sina.
com.
cn/seo只有1个链接,并且链接到A,则如blog.
sina.
com.
cn/seo有2个链接,并且链接到A,则如果10个PR=0的网站链接到A,则http://media.
hust.
edu.
cn49PageRank算法PageRank简化算法取万维网链接结构图G,G的规模为N,即G中包含N个节点对G中每个节点n,设其初始PageRank值为Fork=1,2,…,TN,对G中每个节点n当结果向量未收敛时,返回上一步继续循环;收敛时算法结束,输出G中各节点的PageRank数值PR(n)http://media.
hust.
edu.
cn50PageRank算法PageRank简化算法示例如右图示链接结构图初值:第一次迭代:http://media.
hust.
edu.
cnACDB51PageRank算法PageRank简化算法示例(续)第二次迭代:http://media.
hust.
edu.
cn52PageRank算法详细迭代结果如下http://media.
hust.
edu.
cnPR(A)PR(B)PR(C)PR(D)第1次迭代0.
25000.
25000.
25000.
25001.
0000第2次迭代0.
25000.
15000.
15000.
45001.
0000第3次迭代0.
41000.
15000.
15000.
29001.
0000第4次迭代0.
28200.
21400.
21400.
29001.
0000第5次迭代0.
28200.
16280.
16280.
39241.
0000…第10次迭代0.
30680.
18610.
18610.
32101.
0000…第20次迭代0.
31440.
17580.
17580.
33411.
0000…第30次迭代0.
31580.
17620.
17620.
33191.
0000…第100次迭代0.
31560.
17620.
17620.
33201.
000053PageRank算法PageRank简化算法的问题有些页面没有超链接txt,doc,jpg,…随机浏览进入死胡同简化算法无法保证迭代过程中的PageRank值之和为1,算法失效对简化算法进行改进http://media.
hust.
edu.
cn5410PageRank算法PageRank标准算法取万维网链接结构图G,G的规模为N,即G中包含N个节点对G中每个节点n,设其初始PageRank值为,同时设定临时变量Fork=1,2,…,M,对G中每个节点n若Outdegree(n)>0,则有若Outdegree(n)=0,则有http://media.
hust.
edu.
cn55PageRank算法PageRank标准算法(续)当结果向量未收敛时,返回上一步继续循环;收敛时算法结束,输出G中各节点的PageRank数值PR(n)算法效率低每次遍历节点n时,若n的出度为0,需对每一个链接图内的节点进行操作相当于为"死胡同"网页和G中所有网页之间添加了一条虚拟的出链接改进邻接矩阵http://media.
hust.
edu.
cn56PageRank算法改进邻接矩阵原始邻接矩阵M改进邻接矩阵Ahttp://media.
hust.
edu.
cn57PageRank算法基于改进邻接矩阵的算法描述依照上述改进邻接矩阵的定义,则标准PageRank算法的迭代过程可表示为(其中):存在问题A为稀疏矩阵,传统矩阵运算空间消耗巨大用稀疏矩阵加速算法来改善运算http://media.
hust.
edu.
cn58PageRank算法PageRank加速算法输入:万维网链接结构图G(节点规模为N)的链接关系特征文件D,参数ɑ,迭代次数MD:只记录改进邻接矩阵中的非零元素输出:G对应的各节点的PageRank数值PR临时变量:I(每个节点的PageRank值)S(无出链接节点的PageRank值之和)http://media.
hust.
edu.
cn59PageRank算法PageRank加速算法(续1)1.
遍历文件D,对于D记录的每条链接关系E(i,j):2.
Forn=1,2,…,N,若Outdegree(n)=0,则http://media.
hust.
edu.
cn6011PageRank算法PageRank加速算法(续2)3.
Fork=1,2,…,M遍历文件D,对于D中每一条链接关系E(i,j):Forn=1,2,…,N若Outdegree(i)=0,则有http://media.
hust.
edu.
cn61PageRank算法PageRank加速算法(续)需要进行的遍历次数M:迭代次数;N:节点规模;L:链接规模需存储的内容与N规模相关的PR临时变量Ihttp://media.
hust.
edu.
cn62PageRank算法PageRank局限性在真实应用环境中未获巨大成功Upstill:在链接分析方法使用较多的主页查找任务中,PageRank算法及其变形只比纯内容检索略好Amento:小规模数据中PageRank/HITS均无法有效提高纯文本检索的效果实验研究:PageRank在TREC大规模检索数据时失效原因网络数据的繁杂导致的数据规模、数据质量问题http://media.
hust.
edu.
cn63PageRank算法PageRank困境http://media.
hust.
edu.
cn网站域名PageRank得分排名Alexa.
com给出的流量排名www.
adobe.
com1139www.
hd315.
gov.
com21655www.
qq.
com32labs.
adobe.
com4139www.
tencent.
com51062www.
baidu.
com61www.
miibeian.
com7179blog.
sohu.
com88www.
sina.
com.
cn93www.
xinhuanet.
com104264PageRank算法PageRank困境(续1)根据SougoT语料库中PageRank得分最高的10个站点及其对应的Alexa流量排名情况,PageRank得分与受用户欢迎程度(以访问量衡量)的一致性比较:部分网站用户访问量排名与其PageRank得分不符部分网站在万维网链接结构中为了符合相关法律法规的要求或者为了网页读者浏览的便利而被推荐处于重要位置,却不为用户所关注,如网站:www.
hd315.
gov.
cn、www.
adobe.
com、labs.
adobe.
com等http://media.
hust.
edu.
cn65PageRank算法PageRank困境(续2)大量无意义、低质量乃至垃圾链接严重影响其页面质量评估的效果使链接结构分析算法同样适合于真实万维网环境使用用户浏览信息对万维网链接结构信息进行过滤和清理,使之真正反映用户的互联网访问情况http://media.
hust.
edu.
cn6612其他提升网页排序的方法锚文本(AnchorText)即链接文本可作为其所在页面内容的评估精确描述其所指向页面的内容收集一些搜索引擎不能索引的文件网页中合适的锚文本会增加所在网页和所指向网页的重要程度http://media.
hust.
edu.
cn67其他提升网页排序的方法页面版式包括标题、文字、标签等搜索引擎利用这些版式来识别搜索词与页面内容的相关程度合理利用网页的页面版式,可提升网页在搜索结果页的排序位置http://media.
hust.
edu.
cn68其他提升网页排序的方法收费排名不属于排序技术搜索引擎的盈利模式——直接影响搜索引擎的排序给企业带来访问量——对于企业来说,是提升网站在搜索引擎中排名的最直接和最简单的办法对访问者有一定好处,但更多的是不真实排序失去公正性,甚至带来大量垃圾http://media.
hust.
edu.
cn69搜索引擎存在的问题没有真正解决相关性问题没有出现查询词的网页就不是用户需要的网页搜索结果的单一化检索结果的排序应该更加个性化:根据用户的不同产生不同的排序结果http://media.
hust.
edu.
cn70课后作业问题1:按照搜索引擎的排序策略,如何生成垃圾网页以提高排序时pr值问题2:搜索引擎如何处理垃圾网页http://media.
hust.
edu.
cn71http://media.
hust.
edu.
cn