跳到主要内容

既然来了就选服务吧

我们承诺所有的项目完好充分地被执行,以满足高要求客户的需求。

携手米国生活,创造美好生活!

SEO关键词密度 网页排名算法

SEO关键词密度 网页排名算法

从简单入难的介绍几个算法:

关键词密度

=关键词出现次数x关键词字数/文章总字数(不含标题)x100%

PageRank算法-网页排名

什么是pagerank

PageRank的Page可是认为是网页,表示网页排名,

PageRank,即网页排名,又称网页级别Google左侧排名佩奇排名(也可以认为是Larry Page(google 产品经理),因为他是这个算法的发明者之一,也是google CEO)

是Google创始人拉里·佩奇和谢尔盖·布林于1997年构建早期的搜索系统原型时提出的链接分析算法,自从Google在商业上获得空前的成功后,该算法也成为其他搜索引擎和学术界十分关注的计算模型。目前很多重要的链接分析算法都是在PageRank算法基础上衍生出来的。PageRank是Google用于用来标识网页的等级/重要性的一种方法,是Google用来衡量一个网站的好坏的唯一标准。在揉合了诸如Title标识和Keywords标识等所有其它因素之后,Google通过PageRank来调整结果,使那些更具“等级/重要性”的网页在搜索结果中另网站排名获得提升,从而提高搜索结果的相关性和质量。其级别从0到10级,10级为满分。PR值越高说明该网页越受欢迎(越重要)。例如:一个PR值为1的网站表明这个网站不太具有流行度,而PR值为7到10则表明这个网站非常受欢迎(或者说极其重要)。一般PR值达到4,就算是一个不错的网站了。Google把自己的网站的PR值定到10,这说明Google这个网站是非常受欢迎的,也可以说这个网站非常重要。

互联网中的网页可以看出是一个有向图,其中网页是结点,如果网页A有链接到网页B,则存在一条有向边A->B,下面是一个简单的示例:

SEO-pagerank

 

从入链数量到 PageRank

在PageRank提出之前,已经有研究者提出利用网页的入链数量来进行链接分析计算,这种入链方法假设一个网页的入链越多,则该网页越重要。早期的很多搜索引擎也采纳了入链数量作为链接分析方法,对于搜索引擎效果提升也有较明显的效果。 PageRank除了考虑到入链数量的影响,还参考了网页质量因素,两者相结合获得了更好的网页重要性评价标准。
对于某个互联网网页A来说,该网页PageRank的计算基于以下两个基本假设:
     数量假设:在Web图模型中,如果一个页面节点接收到的其他网页指向的入链数量越多,那么这个页面越重要。
     质量假设:指向页面A的入链质量不同,质量高的页面会通过链接向其他页面传递更多的权重。所以越是质量高的页面指向页面A,则页面A越重要。
利用以上两个假设,PageRank算法刚开始赋予每个网页相同的重要性得分,通过迭代递归计算来更新每个页面节点的PageRank得分,直到得分稳定为止。 PageRank计算得出的结果是网页的重要性评价,这和用户输入的查询是没有任何关系的,即算法是主题无关的。假设有一个搜索引擎,其相似度计算函数不考虑内容相似因素,完全采用PageRank来进行排序,那么这个搜索引擎的表现是什么样子的呢?这个搜索引擎对于任意不同的查询请求,返回的结果都是相同的,即返回PageRank值最高的页面。

PageRank算法原理

PageRank的计算充分利用了两个假设:数量假设和质量假设。步骤如下:
1)在初始阶段:网页通过链接关系构建起Web图,每个页面设置相同的PageRank值,通过若干轮的计算,会得到每个页面所获得的最终PageRank值。随着每一轮的计算进行,网页当前的PageRank值会不断得到更新。

2)在一轮中更新页面PageRank得分的计算方法:在一轮更新页面PageRank得分的计算中,每个页面将其当前的PageRank值平均分配到本页面包含的出链上,这样每个链接即获得了相应的权值。而每个页面将所有指向本页面的入链所传入的权值求和,即可得到新的PageRank得分。当每个页面都获得了更新后的PageRank值,就完成了一轮PageRank计算。

 

基本思想:

如果网页T存在一个指向网页A的连接,则表明T的所有者认为A比较重要,从而把T的一部分重要性得分赋予A。这个重要性得分值为:PR(T)/L(T)

其中PR(T)为T的PageRank值,L(T)为T的出链数

则A的PageRank值为一系列类似于T的页面重要性得分值的累加。

即一个页面的得票数由所有链向它的页面的重要性来决定,到一个页面的超链接相当于对该页投一票。一个页面的PageRank是由所有链向它的页面(链入页面)的重要性经过递归算法得到的。一个有较多链入的页面会有较高的等级,相反如果一个页面没有任何链入页面,那么它没有等级。

PageRank简单计算:

假设一个由只有4个页面组成的集合:A,B,C和D。如果所有页面都链向A,那么A的PR(PageRank)值将是B,C及D的和。

继续假设B也有链接到C,并且D也有链接到包括A的3个页面。一个页面不能投票2次。所以B给每个页面半票。以同样的逻辑,D投出的票只有三分之一算到了A的PageRank上。

换句话说,根据链出总数平分一个页面的PR值。

例子:

图1 所示的例子来说明PageRank的具体计算过程。

修正PageRank计算公式

         由于存在一些出链为0,也就是那些不链接任何其他网页的网, 也称为孤立网页,使得很多网页能被访问到。因此需要对 PageRank公式进行修正,即在简单公式的基础上增加了阻尼系数(damping factor)q, q一般取值q=0.85。

其意义是,在任意时刻,用户到达某页面后并继续向后浏览的概率。 1- q= 0.15就是用户停止点击,随机跳到新URL的概率)的算法被用到了所有页面上,估算页面可能被上网者放入书签的概率。

最后,即所有这些被换算为一个百分比再乘上一个系数q。由于下面的算法,没有页面的PageRank会是0。所以,Google通过数学系统给了每个页面一个最小值。

这个公式就是.S Brin 和 L. Page 在《The Anatomy of a Large- scale Hypertextual Web Search Engine Computer Networks and ISDN Systems 》定义的公式。

所以一个页面的PageRank是由其他页面的PageRank计算得到。Google不断的重复计算每个页面的PageRank。如果给每个页面一个随机PageRank值(非0),那么经过不断的重复计算,这些页面的PR值会趋向于正常和稳定。这就是搜索引擎使用它的原因。

4. PageRank幂法计算(线性代数应用)

 完整公式:

关于这节内容,可以查阅:谷歌背后的数学

首先求完整的公式:

Arvind Arasu 在《Junghoo Cho Hector Garcia - Molina, Andreas Paepcke, Sriram Raghavan. Searching the Web》 更加准确的表达为:

PageRank值是一个特殊矩阵中的特征向量。这个特征向量为:

R是如下等式的一个解:

如果网页i有指向网页j的一个链接,则

使用幂法求PageRank

幂法计算过程如下:
X  设任意一个初始向量, 即设置初始每个网页的 PageRank值均。一般为1.

R = AX;

while  (1 )(
if ( l X - R I  <  ) { //如果最后两次的结果近似或者相同,返回R
return R;
}    else   {
X =R;
R = AX;
}

}

求解步骤:

 P概率转移矩阵的计算过程:

先建立一个网页间的链接关系的模型,即我们需要合适的数据结构表示页面间的连接关系。

      1) 首先我们使用图的形式来表述网页之间关系:

现在假设只有四张网页集合:A、B、C,其抽象结构如下图1:

 图1 网页间的链接关系

显然这个图是强连通的(从任一节点出发都可以到达另外任何一个节点)。

2)我们用矩阵表示连通图:

用邻接矩阵 P表示这个图中顶点关系 ,如果顶(页面)i向顶点(页面)j有链接情况 ,则pij   =   1 ,否则pij   =   0 。如图2所示。如果网页文件总数为N , 那么这个网页链接矩阵就是一个N x N  的矩 阵 。

3)网页链接概率矩阵

然后将每一行除以该行非零数字之和,即(每行非0数之和就是链接网个数)则得到新矩阵P’,如图3所示。 这个矩阵记录了 每个网页跳转到其他网页的概率,即其中i行j列的值表示用户从页面i 转到页面j的概率。图1 中A页面链向B、C,所以一个用户从A跳转到B、C的概率各为1/2。

4)概率转移矩阵P

采用P’ 的转置矩 阵进行计算, 也就是上面提到的概率转移矩阵P 。  如图4所示:

 

         图2  网页链接矩阵:                                      图3  网页链接概率矩阵:  

                         图4  P’ 的转置矩 阵

 

A矩阵计算过程

1)P概率转移矩阵  :

初始每个网页的 PageRank值均为1 , 即X~t = ( 1 , 1 , 1 ) 。

循环迭代计算PageRank的过程

 第一步:

因为X 与R的差别较大。 继续迭代。

第二步:

继续迭代这个过程...

直到最后两次的结果近似或者相同,即R最终收敛,R 约等于X,此时计算停止。最终的R 就是各个页面的 PageRank 值。

用幂法计算PageRank 值总是收敛的,即计算的次数是有限的。

 

Larry Page和Sergey Brin 两人从理论上证明了不论初始值如何选取,这种算法都保证了网页排名的估计值能收敛到他们的真实值。

由于互联网上网页的数量是巨大的,上面提到的二维矩阵从理论上讲有网页数目平方之多个元素。如果我们假定有十亿个网页,那么这个矩阵 就有一百亿亿个元素。这样大的矩阵相乘,计算量是非常大的。Larry Page和Sergey Brin两人利用稀疏矩阵计算的技巧,大大的简化了计算量。

PageRank算法优缺点

优点:

是一个与查询无关的静态算法,所有网页的PageRank值通过离线计算获得;有效减少在线查询时的计算量,极大降低了查询响应时间。

缺点:

1)人们的查询具有主题特征,PageRank忽略了主题相关性,导致结果的相关性和主题性降低

2)旧的页面等级会比新页面高。因为即使是非常好的新页面也不会有很多上游链接,除非它是某个站点的子站点。

 

TF-IDF算法计算公式及含义

tf-idf算法计算公式

什么是TF-IDF

TF-IDF(Term Frequency-Inverse Document Frequency, 词频-逆文件频率).

是一种用于资讯检索与资讯探勘的常用加权技术。TF-IDF是一种统计方法,用以评估一字词对于一个文件集或一个语料库中的其中一份文件的重要程度。字词的重要性随着它在文件中出现的次数成正比增加,但同时会随着它在语料库中出现的频率成反比下降。

上述引用总结就是, 一个词语在一篇文章中出现次数越多, 同时在所有文档中出现次数越少, 越能够代表该文章.

这也就是TF-IDF的含义.

词频 (term frequency, TF) 指的是某一个给定的词语在该文件中出现的次数。这个数字通常会被归一化(一般是词频除以文章总词数), 以防止它偏向长的文件。(同一个词语在长文件里可能会比短文件有更高的词频,而不管该词语重要与否。)

但是, 需要注意, 一些通用的词语对于主题并没有太大的作用, 反倒是一些出现频率较少的词才能够表达文章的主题, 所以单纯使用是TF不合适的。权重的设计必须满足:一个词预测主题的能力越强,权重越大,反之,权重越小。所有统计的文章中,一些词只是在其中很少几篇文章中出现,那么这样的词对文章的主题的作用很大,这些词的权重应该设计的较大。IDF就是在完成这样的工作.

TF-IDF算法计算公式

TF计算公式

TFw=在某一类中词条w出现的次数/该类中所有的词条数目

逆向文件频率 (inverse document frequency, IDF) IDF的主要思想是:如果包含词条t的文档越少, IDF越大,则说明词条具有很好的类别区分能力。某一特定词语的IDF,可以由总文件数目除以包含该词语之文件的数目,再将得到的商取对数得到。

 

IDF计算公式

IDF=log(语料库的文档总数/包含词条w的文档数+1),分母之所以要加1,是为了避免分母为0

 

某一特定文件内的高词语频率,以及该词语在整个文件集合中的低文件频率,可以产生出高权重的TF-IDF。因此,TF-IDF倾向于过滤掉常见的词语,保留重要的词语。

 

TF-IDF算法计算公式

TF−IDF=TF∗IDF

TF-IDF值越大,则这个词成为一个关键词的概率就越大。

TF-IDF算法实例

以《亚洲的网络技术》为例,假定该文长度为1000个词,"亚洲"、"网络"、"技术"各出现20次,则这三个词的"词频"(TF)都为0.02。 然后,搜索Google发现,包含"的"字的网页共有250亿张(假定这就是中文网页总数),包含"亚洲"的网页共有62.3亿张,包含"网络"的网页为0.484亿张,包含"技术"的网页为0.973亿张。则它们的逆文档频率(IDF)和TF-IDF的计算结果如下:

tf-idf实例:什么叫TF-IDF TF-IDF算法和公式的解读

从上表可见,"网络"的TF-IDF值最高,"技术"其次,"亚洲"最低。(如果还计算"的"字的TF-IDF,那将是一个极其接近0的值。)所以,如果只选择一个词,"网络"就是这篇文章的关键词。 除了自动提取关键词,TF-IDF算法还可以用于许多别的地方。比如,信息检索时,对于每个文档,都可以分别计算一组搜索词("亚洲"、"网络"、"技术")的TF-IDF,将它们相加,就可以得到整个文档的TF-IDF。这个值最高的文档就是与搜索词最相关的文档。 TF-IDF算法的优点是简单快速,结果比较符合实际情况。缺点是,单纯以"词频"衡量一个词的重要性,不够全面,有时重要的词可能出现次数并不多。而且,这种算法无法体现词的位置信息,出现位置靠前的词与出现位置靠后的词,都被视为重要性相同,这是不正确的。(一种解决方法是,对全文的第一段和每一段的第一句话,给予较大的权重。)

TF-IDF算法不足

TF-IDF 算法会倾向于选出某一特定文档内的高频词语,同时该词语在整个文档集合中分布是比较集中的。因此,TF-IDF算法倾向于过滤掉常见的词语,保留“独有”词语。但是这也造成了TF-IDF算法的缺陷。 因为IDF的主要思想是:如果包含词条t的文档越少,也就是n越小,idf越大,则说明词条t 具有很好的类别区分能力。如果某一文档C中包含词条t的文档数为m, 而其他类包含t的文档总数为k,显然所有包含t的文档数n = m + k, 当m大的时候,n也大,按照IDF公式得到的IDF的值会小,就说明该词条t 类别区分能力不强。但实际上,如果一个词条在一个类的文档中频繁出现,则说明该词条能够很好地代表这个类的文本特征,这样的词条应该给它们赋予较高的权重,并选来作为该类文本的特征词,以区别于其他类的文档。

比如对于如下几个短文本:
1、鲜花多少钱?
2、白百合多少钱?
3、月季多少钱?
4、香蕉多少钱?

如果按照TF-IDF算法,鲜花、香蕉这些主体词会成为关键词,但是从这些语句的总体来看,他们又都属于询问价格的类型,所以“多少钱”应该成为关键词。这就是IDF的不足之处。
改进的方法可以通过改变文档结构,比如将上述短文本归并为一个文档,这样就可以在增加TF值的同时,也增加IDF值。但是这样就会增加模型的计算成本,需要大量的人为经验加入其中。

本文内容来源:http://www.360baidu.cn/seo/tf-idf.html 和https://blog.csdn.net/hguisu/article/details/7996185

算法记录源于:百度百科和维基百科

返回顶部