搜索引擎技术基础.

TLSPR算法孟德鑫2015.04.28目录•PageRank算法简介•余弦相似度算法•网页链接向量•TLSPR算法详解•总结PageRank算法简介数量假设:一个好的网页必然会吸引大量的链接,即一个网页的入链度越大,这个网页就越重要。质量假设：越是重要的网页通过出向链接向其他网页传递的权重越是大，即被重要的网页所引用的网页也更为重要。初始条件：每一个网页都有一个初始的PageRank值，初始值一般为1/N，（N是网络中的的网页数量）。理论基础：优质网页指向网页必是优质网页。模型基础：随机游走模型。PageRank算法简介PageRank算法简介公式：N:网络中网页数量，P：代表指向网页W的网页:任意浏览访问W的概率α：一般取0.85PageRank算法简介迭代过程：PageRank算法简介PageRank算法简介缺点：1.主题漂移现象；2.平分网页权值；3.偏重旧网页；4.忽视用户浏览兴趣等。余弦相似度算法向量空间模型是一个用来表示文本文档(通常也包含一些对象)的特征向量的数学模型，例如索引词项。它被广泛应用于信息过滤，信息检索，索引和相关度计算。定义一个文档可以表示成一个向量。一个维度相当于一个词项(term)。如果一个词项出现在一篇文档中，它在向量中的值是非零的。有几种不同的计算这些被看作(词项)权重的向量值的方法被逐渐提出来.其中一种最著名的方法是TF-IDF加权。词项的定义是依赖于应用的。一般而言,词项就是单字(单词)，关键字，或者长短语。如果词(word)被选作词项(term)，向量的维度就等于词汇表中的词数(出现在文档全集中所有不同的词的数量)。余弦相似度算法应用基于关键字检索的文档相关度计算,可以用文档相似度理论的假设来实现，就是比较每个文档向量和原始查询向量的夹角，其中查询是表示为与文档一样的向量。(注:其实就是两个文档向量之间比较)在实践中,计算两个向量夹角的余弦值(cosine)会比直接计算角度更简单:余弦值为0时表示查询向量和文档向量之间呈直角，也就是查询和文档完全不相似(也就是查询的词项在被查询的文档中不存在)。网页链接向量网页的入链代表了其它网页对其的一种认可，因此，很多网页向量模型均以一个N维的网页入链情况向量表示网页的主题特征，由于这些方面未考虑到网页的出链情况，因此，考虑也不全面，必然存在着偏差。一个优质的枢纽页往往指向大量优质的权威页，那么一个优质的权威页往往存在大量优质的枢纽页入链。网页中的出链实质上是网页作者在对网页主题的理解上，指出的网页必然与自己的网页存在某一主题的相关性。因此,将网页的出链情况也加入了向量中,向量维度增至2N。这样,网页的主题链接向量即包含了他人对该网页的认同,又包含了该网页作者对主题相关网页的认同。网页链接向量定义1：假定网络中搜索范围内的网页数量共有N个,对其依次从1始编号。对于任意网页W，在其对应2N主题链接向量的前n维中，当网页i存在指向网页W的链接时，第i个向量分量等于1，反之等于0;在向量的后N维中，当网页W存在指向网页i的链接时，第N+i个分量等于1，反之等于0。特别定义，指向网页W本身链接所对应的向量分量等于0。网页链接向量定义2：由于网页的入链和出链所关联到的网页中占搜索涵盖网页的很小一部分，因此，在生成向量时，采用如下表达方式：令Vw=[i1,i2,..,ik,o1,o2,…,om]其中i1,i2,..,ik代表网页W入链网页的序号；o1,o2,…,om代表网页W出链网页的序号，如此就能够以较少的计算代价换取大量地算法的空间复杂度。TLSPR算法又称基于主题链接相似度的PageRank算法主题漂移现象：把当前网页的权威值平均传递给它的全部链接，但是互联网中的网页存在着差别，对于主题无关的网页就应该减少传递给它的权值，从而提高主题相关网页的排序效果。原理：以当前网页和入链网页的主题链接相关性的大小传递权值，取代PageRank算法中平均传递权值的策略，TLSPR算法引入了网页之间的链接向量，用來表示一个网页，并通过这种链接关系表示的向量的余弦相似度描述网页之间的主题相关性，避免了其它改进算法额外文本信息的负担。TLSPR算法启发：向量代表多维空间中有方向的线段，如果两个向量的方向一致，即夹角越接近于0，两个向量就越相近。而确定两个向量方向一致性的方法，就可以用余弦定理来计算两个向量的夹角。余弦相似度就是通过测量两个向量内积空间的夹角的余弦值来度量它们之间的相似度。注：余弦相似度可以用于任何维度的向量比较中,在高维正空间中它的使用尤为频繁。TLSPR算法余弦相似度一直以来都是传统文件分类中被用来度量文件之间距离的一种基本方法,本文也利用其这一特征,来计算两个网页的主题相关性。假定网页X、Y，主题链接向量分别是Vx，Vy，那么,它们的主题链接相似度计算公式如下:显然结果在0和1之间，数字越大主题就越正相似。TLSPR算法改进PageRank算法的公式为:其中,TLSPR(w)代表网页w的PageRank值；Ti(i=1,2,3,…,k)代表网页w的全部入链网页；j=1,2,3,…,m代表网页Ti的出链网页。原式：TLSPR算法特殊情况下,如果，代表网页Ti与其全部出链网页不存在任何相关性，为了公式的正常运算以及算法的正常运行，特别定义此时的其中，N代表搜索范围内的网页数量。TLSPR算法令：则矩阵S=[sij]，这时，只需知道搜索引擎所涵盖网页的初始向量TLSPR0，公式就可以变为:TLSPR算法因为||Sll1=1，所以,公式整个迭代计算过程必然收敛。通过TLSPR算法可以使网页的PageRank值在相似主题的网页上进行不均等传播，从而有效地减少主题无关网页对PageRank值的扩散。总结1.PageRank2.向量空间模型3.结合应用