08006基于网页排序pagerank改进算法

1摘要本文就网页排序规则设计的问题，根据题目中的条件和要求，在合理的假设下，建立了两个模型。模型一采用PageRank算法建立了网页等级排序模型；模型二对模型一中存在的不足进行了改进建立了基于主题的网页等级排序模型，通过求解这两个模型，很好的解决了问题。在问题一中，我们将网页间的链接关系抽象为有向图，构造出了网页间的链接关系矩阵，即邻接矩阵A=(aij)，然后我们将邻接矩阵转化为转移概率矩阵记为M=(mij)，给出了网页顺时等级方程：Rt+1(i)=mi1Rt(1)+⋯⋯+mikRt(k)+⋯⋯minRt(n)我们以特征向量R的值(PageRank值)作为每个网页的权重，其值越大则该网页为用户感兴趣网页的概率越大。根据pagerank值的大小为排序规则建立了网页等级模型。在问题二中，考虑到人为统计网页的链入链出量不易实现，于是我们用模拟网页链接图代替真正的网页链接图，如图一。通过幂法中的迭代关系式MR=ℷR求解网页顺时等级方程，我们求解得到特征向量R，然后根据特征向量的权重对网页排序，得到排序结果为：A6,A8,A9,A4,A5,A3,A2,A1,A7,A10，排序越靠前的网页与主题相关度越大，最后我们对网页排序规则的合理性进行了说明。考虑到通过PageRank算法建立的网页等级模型会出现主题漂移现象，于是我们对该模型进行了改进。我们通过对网络系统中的主题分类，然后根据分类的结果分别对每一个主题进行页面等级计算，得到主题页面等级的计算公式：TPR(P)=(1-12)+1(KA[1,i])TPR(1)/C(1)+⋯+KA[1,i]TPR(n)/C(n)+2KA[p,i]，这样每一个页面对不同的主题将呈现出不同的页面等级得分，能更加准确地反映出页面的重要性。运用改进的模型我们重新求解了第二问，我们以体育为主题将网络系统中的网页分为13个类别，然后假定主题相似度矩阵CO[i,j]如表三，结合网页间的链接关系矩阵A=(aij)，通过文本分类算法求得各网页与叶子主题的相关度矩阵为KT[p,i]如表四，最后由主题页面等级计算公式得到各了网页对相应主题的权值(TPR值)并对改进的规则进行了合理性分析。关键词：PageRank算法网页等级排序模型基于主题网页排序模型2一、问题重述当我们利用搜索引擎，如Google、百度等按关键字搜索时，往往希望我们感兴趣的网页靠前排序。实际中你可能也注意到所搜索到的结果是进行了排序的。现在请你们建立数学模型解决下面的问题：1、试设计一种你们认为合理的排序规则，使搜索到的网页结果排序满足要求；2、选取若干个网页为例，试用你们的规则进行一次排序，并说明规则的合理性。二、问题假设1、网页之间的链入链出量能反映实际情况；2、网页主题的分类按照ODP分类法分类；3、关键词的选取符合人们的习惯；4、网页靠前排序的规则基于用户的感兴趣程度；5、假设主题传递的权重因子为k(0k1)。三、符号说明N，|N|网页页面数,训练文本的总数ni1A...A...A网页A=(aij)页面间的链接关系CO[i,j]，主题相似度矩阵KT[p,i]各页面与叶子主题的相关度矩阵KA[p,i]每一个页面与所有主题的相关度iW选取词特征项d)W(t，词t在文本d中的权重d训练文本数)(dttf，词t在文本d中的词频tn训练文本集中出现t的文本数）jC/P(WW在Cj中出现的比重3N(W,i)W在i中的词频|V|总词数id新文本的特征向量jd第j类的中心向量M转移概率矩阵kW向量的第K维四、问题分析4.1.1基于网页排序规则合理性分析由于科技飞速发展，计算机在我国的普及率相当高，面对互联网上包含的信息越来越丰富，我们如何快速地搜索到自己感兴趣的主题呢？因此我们需要设计一种合理的网页排序规则，使人们通过关键字搜索快速的查找到与主题相关的内容。当我们利用搜索引擎，如Google、百度等按关键字搜索时，我们注意到所搜索到的结果是进行了排序的。通过查找的资料以及实际情况，我们定义网页排序的合理规则是输入关键字时我们感兴趣的网页会靠前排序。4.1.2基于网页靠前排序分析对于网页排序，我们引入pagerank算法，其原理是通过网页被链接的数量和质量来确定搜索结果的排序权重，在关键词文本匹配的基础上，利用Web超链结构，对一个网页与其它网页的链接关系进行分析，即检验一个网页被其他网页链接的次数，指向它的网页越多并且质量越高，说明该网页越重要，进而pagerank值越大，从而确定该网页在检索结果中的排列顺序。4.2.1网页排序实例分析第二问要求我们根据第一问设计的规则，选取若干个网页进行排序，使我们感兴趣的网页能靠前排列。根据pagerank算法，我们需要统计出所选取的网页的链入链出量，计算出每个网页的pagerank值，以此为基准进行排序。然而作为非网站人员的我们统计这些数据是不易实现的，因此我们想到用模拟网页链接图代替真正的网页链接图，即人为设定网页间的链入链出量，再进行相关性计算，虽然这样有一定的实际偏差，但我们仍可以得到比较理想的结果。4.2.2模型改进分析4PageRank算法主要根据网页上的外部链接站点的数量和质量及链接页面等级决定PR值的大小，由PR值来决定该网页在搜索引擎中的排名。却忽略了链接页面对查询条件的主题相关性。如果该页面只是在内容中出现了关键词，可主题内容与该关键词相差很大，也会因其存在的页面PR值大而获得一个比较高的排名，这对用户来说是没有意义的。所以，决定网页排名不但需要考虑网页的页面等级，更要考虑该网页的页面主题内容与查询主题的相关性是否相称。为了改善这种情况，我们应对每一个页面进行基于主题的分类，然后针对每一个主题分别计算出对应主题的主体性页面等级得分，这样当我们进行搜索时就可以根据用户的检索条件来对主题相关的页面进行排序输出。五、模型建立与求解5.1.1PageRank算法在PageRank算法中，基本原理是“从许多优质的网页链接过来的网页，必定还是优质网页”。对网页的等级评价不是简单在仅仅用链接它的其它网页的数量来评定，还依赖于链接到它的网页本身的质量等级。以网页为结点，网页间的链接用有向边表示，形成一个有向图。网页结点上的数字标记表示网页当前的“等级量”，正向链接到其它结点规定为是均匀分布。PageRank技术中，对网页的量的确定基于如下原则：(1)反向链接数只作为受欢迎度指标之一。被许多页面链接的网页，其等级会提高。(2)受到优质网页访问网页，同样是优质网页，而且访问的概率越高，对其“等级”的贡献就越大，被许多“重要”的页面链接会使得推荐快速上升。(3)完全没有关联性的网页的链接会被认为“几乎没有什么价值”而被轻视。(4)网页等级是动态的，与时间有关系。5.1.2网页等级模型建立设网页页面数为N，用A1，⋯An表示N个页面，则NN的方阵A=(aij)表示页面间的链接关系:aij={1Ai→Aj0否则其中，Ai→Aj表示页面Ai链接到页面Aj以V={A1⋯⋯An}为结点集，链接关系Ai→Aj引入有向边，则对应的有向图记为G=（V,E）。5由于PageRank算法不是重视“链接到其它网页”，而是重视“被其它网页链接”，因此将邻接矩阵A=(aij)求转置得矩阵B，即B=AT。B的第i行表示页面Pi的反向链接。将B=(B1，⋯⋯，Bn)按列单位化，使各列向量的总和变成1(全概率)，以形成一个概率转移矩阵M=(mij)，其中mij=aij/∑akjnk=1，mij可以理解为Pi链接到Pj的概率。M称为转移概率矩阵，它有N个随机变量，第j列对应一个随机变量Xj的分布概律。引入Rt(i)n1，Rt+1(i)n1两个列向量，其中的各元素分别表示t时刻和t+1时刻各网页的瞬时等级值。在t时刻，第k个网页将自身的等级量Rt(k)以比例mik转移给第i个网页，或者以概率mik访问第i个网页，用mikRt(k)表示，则所有网页在t时刻向第i个网页等级量的转移累计为Rt+1(i)，其计算公式为：Rt+1(i)=mi1Rt(1)+⋯⋯+mikRt(k)+⋯⋯minRt(n)于是建立动态方程：MRt(i)=Rt+1(i)。如果存在常数ℷ，当t→+∞时，迭代方程MRt(i)=ℷRt+1(i)就会有不动点R,即MR=ℷR。ℷ为转移概率矩阵的特征值，R为转移概率矩阵的特征向量。在迭代方程MRt(i)=ℷRt+1(i)中，设有初始PageRank向量R0(i)，MRt(i)=ℷRt+1(i)理解为：从t时刻的PageRank特征向量Rt(i)转移到t+1时刻的PageRank特征向量Rt+1(i)，其中ℷ为放大系数。这就是下一步中要选择最大特征根的理由来求解转移概率矩阵绝对值最大的特征根λmax和对应的特征向量R0(i)，将R单位化成为一个PageRank概率向量。用向量R中PageRank值的大小量化网页的等级，则较大值对应较高等级。5.2.1网页等级模型求解通过上面的分析，我们知道要搜索出各个网页的链入链出量是不易实现的，并且各个网页间应是有关联性的，关联性越强就越具有代表性，如果大多数网页不相关联则就没有意义，因此我们选定10个网页A1,A2⋯A10,设定其链接关系如下图：6图一网页链接图将上图中的各网页间的链接关系表示为如下排列式，即根据各个链接源文件列举链接目标文件，如下表：表一网页链接表反向链接源iA节点iA正向链接目标iA4A、5A1A2A、4A1A、4A2A5A4A、5A、7A、10A3A9A1A、6A4A1A、2A、3A、5A2A、4A5A1A、3A、6A、7A、8A5A、8A6A4A、9A5A7A3A、8A、10A1A2A9A10A8A7A6A3A5A4A7根据上表将网页间的链接关系用邻接矩阵A=(aij)表示，在A中，若第i行元素值为1，则表示文件i正向链接文件j，否则其值为0；若第j列元素值为1则表示文件j反向链接文件i，或者为指向文件j反向链接的文件源，否则其值为0，其邻接矩阵如下：A=0010000100001000000000001000001010000100010000100000111001010000010111010000000000000100000000001010将临接矩阵A转置，并将转置后的矩阵按列单位化，得到转移概率矩阵M=(mij)，mij=aij/∑akjnk=1，转移概率矩阵如下：M=00031000000000021001002110310510000000005100000010051000000000041010000021000021210031051410000000004100210000051410005A、7A、9A、10A8A6A3A、6A9A8A7A10A3A、8A8设转移概率矩阵M的特征根为ℷ，其特征向量为R,由pagerank算法我们知道他们满足关系MR=ℷR，采用幂法进行MATLAB编程算出转移概率矩阵M共有10个特征根(含复数根)，取其中绝对值最大的特征根ℷmax=1和与之对应的特征向量：W=(0.1340,0.1531,0.1579,0.3446,0.2393,0.5551,0.0479,0.5073,0.4355,0.0160)T将特征向量单位化得：W=(0.0517,0.0591,0.0610,0.1330,0.0924,0.2143,0.0185,0.1958,0.1681,0.0062)T对单位化后的特征向量W=(wij)按照权值(PageRank值)大小排序，则对应网页的排序为：A6,A8,A9,A4,A5,A3,A2,A1,A7,A10，其中网页A6的pagerank值最大，这表明当用户搜索关键词时，网页A6为用户最感兴趣的网页，其他网页依次递减。5.2.2网页等级排序模型的合理性为了验证网页等级量化方法的科学性，我们对以上10个网页排序结果进行分析评价。将10个网页的链接关系和排名关系制作为表格，如表二：表二