基于PageRank值的文本相似度改进模型.docx

          基于PageRank值的文本相似度改进模型                    熊才权田浩湖北工业大学计算机学院湖北430068摘要：相似度计算的质量对于搜索引擎的速度和准确率有着很大的影响本文提出了基于PageRank值的文本相似度改进模型(BPVSM)，以PageRank值对文本分类，在计算文本相似度时考虑不同类别的信息差异对1370条信息进行检索，用改进后的模型对检索结果进行重排序实验表明，改进后的模型可以提高检索的准确率关键词：搜索引擎；PageRank；向量空间模型l TF/IDF0 引言在Google模式中，PageRank值的计算和向量空间模型的计算是相互独立的，在向量空间模型的计算中也没有考虑到PageRank值本身所包含的信息含义本文在计算文本相似度时结合PageRank值所包含的信息提出在计算文本相似度时先以PageRank值的大小作为特征选择的条件，然后在VSM模型中考虑类别信息以提高检索的质量1 基于PageRank值的VSM改进模型对文本进行分类是一个比较复杂的问题，文本自动分类是信息检索与数据挖掘领域的研究热点与核心技术，而基于机器学习的文本分类技术的相关研究已经取得较大进展。

本文首先简单的把具有相同PageRank值的网页归为同一类，然后在计算相似度的过程中考虑这种分类的影响，并区分不同类别间的信息差异，最终得到更为有效的检索结果如果把具有相同PageRank值的网页归为同一类，就可以把所有网页文本根据其重要性简单划分为Il种类别在下载系统中对网络爬虫添加部分代码使其根据PageRank值的大小对网页分类存储可以简单实现这种初步的分类1.1 词频的统计方法在文本分类中词频一般是基于自然语言的，经过文本分类后得到的词条可以认为是计算机可识别的机器语言，在真实生活中使用频率高的词条可能在机器语言中使用率并不高在考虑文本分类的同时为了保证相似度计算的一致性，可以对机器语言的文本频率进行统计以在文本相似度计算中使用 词条频率的统计过程如下：(1)对所有分类后的页面提取特征词；(2)统计各个类别Ci的文本总数Mi和包含词条t的文档数mi;(3)计算词条t在各个类别的各个文本中的词频，公式如下：在词条频率的统计过程中首先需要提取特征词，特征词的提取与用户可能的检索词是相关的例如“搜索引擎”、“天安门”等都可能是用户潜在的检索词，所以必须做为特征词进行统计本文提供了包含1370个检索内容的检索库，所有检索库中的词都作为特征词进行统计。

然而，在搜索引擎中进行的每一次检索都对词条进行一次频率统计是不现实的，即使根据本文所提供的检索库所得到的最终统计结果也是不全面的但是，由PageRank算法可知，网页的连接是基于词条的，所以词条频率的变化与PageRan[来自www.Lw5U.com]k值的传递具有一致性，在PageRank值更新的时期内，基于网络的词条频率可认为保持不变可以在计算PageRank值的同时进行词条频率的统计计算，也可以改进PageRank算法，利用PageRank算法计算出词条频率1.2 改进的IDF方法一个词条如果在一个类别的文档中频率较高，则说明该词条能够很好的代表这个类别的文本特征，这样的词条应该给它们赋予较高的权重，并选来作为该类文本的特征词以区别其它类文档例如，计算机类的文本中“CPU”会出现在许多文档中，“CPU”应该选来作为计算机类文本的特征词以区别其它类文档根据上述原理提出改进的IDF方法如下：设总的文档数为N，包含词条t的文档数为n，其中某一类Ci中包含词条t的文档数为mi，除Ci类外，包含词条t的文档数为k，则t在Ci类中的IDFi值为：1.3 改进的VSM模型综上所述，在对搜索引擎中文本相似度计算的方法和过程进行改进后提出“基于PageRank值的VSM改进模型”，其文本相似度的计算过程如下：(1)对所有下载的页面根据PageRank值的大小进行分类，并统计特征词条在各个类别中的词频TFi；(2)由改进的IDF方法计算词条在各个类别中的IDFi;(3)计算该特征项t在文本d中的重要程度Wtd;(4)计算文本d和查询式q的相似度sim(q，d)；其公式如下：(5)根据相似度的大小生成相似度排序列表。

其中，具有相同相似度的页面PageRank值大的排在前面为了验证改进后的效果，需对原模型和改进后的模型所生成的结果进行比较假设：由原模型(VSM)得到的排序为：{Ai，A2，……，An)；由改进后的模型(BPVSM)得到的排序为：{Bi，B2，……，Bn）定义1：相关：若检索结果页面Ai或Bi中包含检索信息则Ai或Bi相关，否则Ai或Bi不相关定义2：异点：在两次排序中若Al≠Bi则Ai和Bi为异点定义3：优异点：在两次排序中∑ Ai≠Bi，若Ai相关而Bi不相关则Ai为优异点，若Bi相关而Ai不相关则Bi为优异点，在两次排序中∑Ai=Bj，若i>j则Ai为优异点，若i

其次，根据改进后的模型对检索结果进行再排序由于在搜索引擎中一个页面显示10个结果，而用户一般难以容忍翻看到1 0以后的结果，所以尽量避免对后面的结果页面进行分析计算在实验中，只对结果页面的前1/3进行了分析计算（检索结果少于300则全部进行分析计算），最终只显示前10个页面的排序最后，分别统计两次排序前十个页中所包含的相关页面的数目，比较两次排序的相关性；分别统计两次排序的优异点，比较两次排序的优异性；并用MATLAB对统计结果进行模拟得到仿真图在实验中，检索内容库主要分为复杂检索和简单检索，复杂检索为可以确定具体结果的检索，例如检索内容为“毛泽东开国典礼语录”为复杂检索，而“毛泽东语录”为简单检索同时考虑到部分新词如“绿领”并未被词典收录，检索内容库具有37条包含新词的检索如“绿领含义”检索内容库概要见表l经过对实验数据统计分析发现改进后的模型在提高检索的准确率上比原模型更加有效，在对包含新词的检索中贡献更加明显最终统计结果见表2对1370次排序的相关性进行模拟，发现两条相关[来自wwW.lw5U.coM]性曲线相互交织在一起，其中BPVSM的大部分略高于VSM;见图1（纵坐标表示相关页面的数目，横坐标表示按照相关页面的数目的大小排列的1370次统计）。

对相关数(其范围为0-100)进行逆向统计的模拟，发现两条曲线在11%和20%左右有较大的起伏；BPVSM在11%和20%有两次波峰，而VSM仅在20%有一次波峰见图2（横坐标为页面相关数，纵坐标表示具有某个相关数的统计次数）对1370次排序的优异点统计进行模拟，发现VSM曲线有少量的奇异点落在BPVSM曲线的上方，忽略少量的奇异点后可认为BPVSM曲线在VSM曲线的上方见图3（纵坐标表示优异点数目，横坐标为按照优异点数目排序的1370次统计）综上所述，实验结果表明：(l)两种模型检索结果的查准率比较接近，但改进后的模型查准率更高；(2)两次排序的查准率在7%-35%之间，在11%和20%左右达到最大概率；(3)改进后的模型可以明显提高对新词的查准率；(4)改进后的模型对前100个网页的可信度提高了约1.45174倍3 结束语相似度的计算与排序是搜索引擎的一个重要部分，提高相似度的计算与排序的效率和质量对提高整个搜索引擎的质量具有重大的意义本文基于搜索引擎的文本检索部分提出了基于PageRank值的文本相似度改进模型，通过模拟实验表明改进后的模型可以提高检索的准确率，在对新词的检索中更加明显。

基于PageRank值统计词频，词频的统计必须保持与PageRank值的更新同步，这必然会增加整个搜索引擎的工作量；其次，改进后的模型依然存在奇异点（即完全不相关的页面却获得了很高的相似度），若在改进后的模型中考虑消去产生奇异点的原因可以提高模型的稳定性参考文献[l]PAGE.L,BRIN.S.The anatomy of a large scalehyper textualWeb search engine [J].Computer Networks and ISDN Systems.1998．[2]PAGE.L,BRIN.S,MOTWAN.R.WINOGRAD.T. The PageRankcitation Ranking:Bringing Order to the Web[J].Stanford DigitalLibrary Technologies Project.1998.[3]MATTEW.R,PEDRO.D.The intelligent surfer: Probabilisticcombination of link and content information.n PageRank[J].Neural Information Processing Systems.2002.[4]SALTON qWONG A,YANG C.A Vector SpaceModel forAutomatic Indexing[J]. Comm-unications ofACM.1975.[5]YANG Y.An evaluation of Statistical Approaches to TextCategorization[J].lnformation Retrieval.1 999.[6]梁斌，走进搜索引擎[M].北京：电子工业出版社.2007.[7]苏金树，张博锋，徐昕．基于机器学习的文本分类技术研究进展软件学报[J].2006．  -全文完-。