无链接文档排序算法研究
2016-01-22蒋招龙赵泽茂
蒋招龙，赵泽茂
(1.杭州电子科技大学通信工程学院，浙江 杭州 310018；
2.丽水学院工程与设计学院，浙江 丽水 32300)
摘要：大数据时代的到来，数据格式呈现多样化，对Web数据的处理不仅仅局限在网页链接上，还需要处理无链接结构的文档。如何从海量的文档中获取所需的信息是搜索引擎亟待解决的问题，目前传统的根据索引分析并不能满足这一需求。为了从数百万个结果中选取价值最高的文档子集，提出了新的DocumentRank算法，通过构建衡量文档重要性矩阵来计算查询相关度得分对文档进行排序。最后通过对互联网文档数据集搜索的实验说明，DocumentRank算法相比Lucene索引技术提高了文档检索的精确度和综合相关度。
关键词：信息检索；PageRank算法；DocumentRank算法；链接结构 在实验中，本文输入相应的来搜索相关的文档，相应的阙值ε值设置为0.000 000 1并且衰减因子为设置为0.9。在测试实验中，本文关注的是相关度得分排名前5的文档。基于Lucene索引技术和本文算法的实验结果如表2所示。
互联网信息具有分散、无序、海量等特点，如何从浩瀚的信息资源中快速、有效、准确地找到所需信息是一个具有挑战性的研究课题[1]。因此，学术界和工业界对信息检索掀起了新的研究高潮[2-3]，相继形成了诸多排序算法模型。文献[4]提出了基于链接分析的PageRank排序算法，文献[5]提出了基于查询需求的查询聚类模型对文档进行排序。文献[6]对用户相关反馈排序算法进行了研究。在文献[7-8]中，对获取相关网页文档方法进行了研究。这些算法更多地考虑网页文档的排序，但是很多时候我们需要获取非网页的文档。在实际的应用中，倘若要想在数百万乃至上亿个Word文档中进行搜索，传统的根据索引分析并不能满足这一需求。针对这一问题，受PageRank算法思想的启发，本文提出了新的DocumentRank算法。实验的结果表明，相比Lucene索引技术，本文算法在文档检索的精确度和综合相关度上均有所提高。
PageRank属于静态的网页评级算法，网页之间的超链接被视为网页重要性的一个衡量指标。在互联网中，PageRank主要是通过构建Web链接结构来得到各个网页的重要性。因此，可以通过构造Web有向图来表示网页之间的链接关系，如图1所示。
为了确保在计算PageRank值的过程收敛需要满足两个条件：1)有向图是强连通的；2)有向图中不包含没有外链的循环子图。
PageRank算法是基于随机浏览模型，对于条件1可以由网络结构保证，条件2可以引入衰减因子来解决。为了将图1公式化，文献[9]中将整个Web看成是一个有向图G=(V，E)，其中，V代表所有网页节点的集合，而E是所有有向边的集合。N表示整个有向图中节点数量。则网页i的PR值定义如下：
(1)
式中，d表示衰减因子，d∈[0，1]，通常设置为0.85，Nj表示网页j的出度(即由节点j指向的节点数量)。通常采用幂迭代方法来计算PR值，迭代过程重复进行，直到两次计算所得到的PR值之间的差别小于预定的阙值为止，即所需的排序结果。
在信息检索领域，文档传统上通常表述为向量空间模型。在向量空间模型下，将文档看成是一个K维向量，K值的大小表示文档中索引项(term)的个数。这里的索引项通常指的是文档中的一个单词。对于向量中的每个索引项都有对应的权重(weight)。因此，文档di表示为：
di=(w1，i，w2，i，…，wk，i)
(2)
式中，wk，i表示第k个索引项在文档i中所占的权重。文档是由词组成的，如果将一个词解析成特定空间的词向量[10]，式(2)的向量形式可表示为：
TFIDF(tj，di)Tj
(3)
式中，TFIDF是表示一种权值法，Tj为词tj的词向量。词向量是一组由项-频率对组成的集合。因此，可以通过词向量得到索引项的频率。
在文档向量空间模型中，通过搜索词向量可以得到索引项在文档中的次数，这对衡量文档的重要性来说非常关键。对于文档A，根据PageRank链接分析技术的思想，如何来计算文档B的重要性。本文引入用来衡量文档重要性的矩阵M，对于矩阵M中各个元素的取值需要满足两个条件：1)矩阵中各个元素的取值都是正数；2)各行元素的总和相加等于1。
在求矩阵M的过程中，如图2所示。根据搜索词向量找到文档A和B中频繁出现索引项的交集；对于交集中的每个索引项，计算该索引项在两个文档中出现次数的比值。为了满足矩阵中两个要求，利用双曲正切函数，对该比值取双曲正切后再四舍五入，最后求出所有这些比值的总和，即矩阵M中第i行第j列的元素。
算法的伪代码如下：
BEGIN:
Map
Map
Set
for(String word: sharedWords){
//对于交集中的每个词，计算该词在两个文档中比值，取双曲正切值求出所有比值的总和，即为矩阵M中相应的元素
}
END
为了验证算法的有效性，实验在64位Windows 7操作系统的PC上完成，在MyEclipse集成开发环境下用Java语言实现了一个Web数据搜索工具。工具使用开源的TextMining库解析Word文档。
实验数据集来源于上百篇关于2014年度新闻的Word文档。另外在实验测试中，加入若干篇以spam为前缀的垃圾文档。这些文档经过整理，用爬虫技术抓取的Word文档，相当于一个简化版的互联网。在实验测试数据时需要预定设置一些阙值和参数，阙值和参数如表1所示。
表1中，衰减因子d的不同会导致迭代次数的不同，对于少量文档，这个区别不是很明显，但是如果是上亿个文档，d的选择就会变得非常重要。通常d的值设置为0.85，在0.70.9之间一般也能兼顾应用的效果。
在获取搜索信息时，最常用的量化搜索质量的标准是精确度和查全率，如图3所示。
相关文档和获取文档之间的交集表示搜索的精确度和查全率。对于精确度，用户往往更关心排名靠前的文档。因此可以取检索结果的前5个文档，若假设其中与查询内容相关的文档数目为dr。则每次查询的检索精度R可以表示为：
(4)
通过多次查询求平均值，即可得到该方法的检索精度。
DOI: 10.13954/j.cnki.hdu.2015.01.017
无链接文档排序算法研究
蒋招龙1，赵泽茂2
(1.杭州电子科技大学通信工程学院，浙江 杭州 310018；
2.丽水学院工程与设计学院，浙江 丽水 32300)
摘要：大数据时代的到来，数据格式呈现多样化，对Web数据的处理不仅仅局限在网页链接上，还需要处理无链接结构的文档。如何从海量的文档中获取所需的信息是搜索引擎亟待解决的问题，目前传统的根据索引分析并不能满足这一需求。为了从数百万个结果中选取价值最高的文档子集，提出了新的DocumentRank算法，通过构建衡量文档重要性矩阵来计算查询相关度得分对文档进行排序。最后通过对互联网文档数据集搜索的实验说明，DocumentRank算法相比Lucene索引技术提高了文档检索的精确度和综合相关度。
关键词：信息检索；PageRank算法；DocumentRank算法；链接结构 在实验中，本文输入相应的来搜索相关的文档，相应的阙值ε值设置为0.000 000 1并且衰减因子为设置为0.9。在测试实验中，本文关注的是相关度得分排名前5的文档。基于Lucene索引技术和本文算法的实验结果如表2所示。
0引言
互联网信息具有分散、无序、海量等特点，如何从浩瀚的信息资源中快速、有效、准确地找到所需信息是一个具有挑战性的研究课题[1]。因此，学术界和工业界对信息检索掀起了新的研究高潮[2-3]，相继形成了诸多排序算法模型。文献[4]提出了基于链接分析的PageRank排序算法，文献[5]提出了基于查询需求的查询聚类模型对文档进行排序。文献[6]对用户相关反馈排序算法进行了研究。在文献[7-8]中，对获取相关网页文档方法进行了研究。这些算法更多地考虑网页文档的排序，但是很多时候我们需要获取非网页的文档。在实际的应用中，倘若要想在数百万乃至上亿个Word文档中进行搜索，传统的根据索引分析并不能满足这一需求。针对这一问题，受PageRank算法思想的启发，本文提出了新的DocumentRank算法。实验的结果表明，相比Lucene索引技术，本文算法在文档检索的精确度和综合相关度上均有所提高。
1PageRank算法
PageRank属于静态的网页评级算法，网页之间的超链接被视为网页重要性的一个衡量指标。在互联网中，PageRank主要是通过构建Web链接结构来得到各个网页的重要性。因此，可以通过构造Web有向图来表示网页之间的链接关系，如图1所示。
为了确保在计算PageRank值的过程收敛需要满足两个条件：1)有向图是强连通的；2)有向图中不包含没有外链的循环子图。
PageRank算法是基于随机浏览模型，对于条件1可以由网络结构保证，条件2可以引入衰减因子来解决。为了将图1公式化，文献[9]中将整个Web看成是一个有向图G=(V，E)，其中，V代表所有网页节点的集合，而E是所有有向边的集合。N表示整个有向图中节点数量。则网页i的PR值定义如下：
(1)
式中，d表示衰减因子，d∈[0，1]，通常设置为0.85，Nj表示网页j的出度(即由节点j指向的节点数量)。通常采用幂迭代方法来计算PR值，迭代过程重复进行，直到两次计算所得到的PR值之间的差别小于预定的阙值为止，即所需的排序结果。
2DocumentRank算法
2.1 文档向量空间模型
在信息检索领域，文档传统上通常表述为向量空间模型。在向量空间模型下，将文档看成是一个K维向量，K值的大小表示文档中索引项(term)的个数。这里的索引项通常指的是文档中的一个单词。对于向量中的每个索引项都有对应的权重(weight)。因此，文档di表示为：
di=(w1，i，w2，i，…，wk，i)
(2)
式中，wk，i表示第k个索引项在文档i中所占的权重。文档是由词组成的，如果将一个词解析成特定空间的词向量[10]，式(2)的向量形式可表示为：
(3)
式中，TFIDF是表示一种权值法，Tj为词tj的词向量。词向量是一组由项-频率对组成的集合。因此，可以通过词向量得到索引项的频率。
2.2 DocumentRank原理
在文档向量空间模型中，通过搜索词向量可以得到索引项在文档中的次数，这对衡量文档的重要性来说非常关键。对于文档A，根据PageRank链接分析技术的思想，如何来计算文档B的重要性。本文引入用来衡量文档重要性的矩阵M，对于矩阵M中各个元素的取值需要满足两个条件：1)矩阵中各个元素的取值都是正数；2)各行元素的总和相加等于1。
在求矩阵M的过程中，如图2所示。根据搜索词向量找到文档A和B中频繁出现索引项的交集；对于交集中的每个索引项，计算该索引项在两个文档中出现次数的比值。为了满足矩阵中两个要求，利用双曲正切函数，对该比值取双曲正切后再四舍五入，最后求出所有这些比值的总和，即矩阵M中第i行第j列的元素。
算法的伪代码如下：
BEGIN:
Map
Map
Set
for(String word: sharedWords){
//对于交集中的每个词，计算该词在两个文档中比值，取双曲正切值求出所有比值的总和，即为矩阵M中相应的元素
}
END
3实验结果与分析
3.1 实验环境和数据来源
为了验证算法的有效性，实验在64位Windows 7操作系统的PC上完成，在MyEclipse集成开发环境下用Java语言实现了一个Web数据搜索工具。工具使用开源的TextMining库解析Word文档。
表1 阙值参数符号表
实验数据集来源于上百篇关于2014年度新闻的Word文档。另外在实验测试中，加入若干篇以spam为前缀的垃圾文档。这些文档经过整理，用爬虫技术抓取的Word文档，相当于一个简化版的互联网。在实验测试数据时需要预定设置一些阙值和参数，阙值和参数如表1所示。
3.2 结果分析
在获取搜索信息时，最常用的量化搜索质量的标准是精确度和查全率，如图3所示。
相关文档和获取文档之间的交集表示搜索的精确度和查全率。对于精确度，用户往往更关心排名靠前的文档。因此可以取检索结果的前5个文档，若假设其中与查询内容相关的文档数目为dr。则每次查询的检索精度R可以表示为：
(4)
通过多次查询求平均值，即可得到该方法的检索精度。
DOI:10.13954/j.cnki.hdu.2015.01.017
收稿日期：2014-05-08
通信作者：
作者简介：蒋招龙(1988-)，男，浙江台州人，在读研究生，数据安全.赵泽茂教授，E-mail: zhaozemao@163.com.
中图分类号：TP391.3
文献标识码：：A
文章编号：：1001-9146(2015)01-0084-04
Abstract:The arrival of the era of big data， data formats diversified， data processing is not limited with Web page link， and sometimes need to deal with non-link structure of the document， such as Word documents， PDF documents etc. How to obtain the required information from the mass of documents is a problem that search engine need to solve， but the traditional analysis based on an index can not meet this demand. In order to select a subset of the most valuable documents from millions of results， proposes a new DocumentRank algorithm， by constructing a matrix to calculate the document importance scores for relevant documents to be sorted. Finally， the experiments on the search of the internet document data sets show that， compared to the Lucene indexing technology， DocumentRank algorithm improve the accuracy of document retrieval and integration-related degrees.
表2 搜索排序精确度结果对比
从表2的检索精度对比结果中可以得出，相比Lucene方法的检索精度(0.65)，DocmentRank算法的检索精度(0.9)有比较大的提升。基于Lucene索引技术所得到的排序结果中，相关度得分排名靠前的并不是本文所需要的文档，其中包含一些垃圾文档。在DocmentRank算法中，相关度得分靠前的是我们所需要的文档，也的确是与搜索词相关的。这表明本文算法在一定程度上提高了文档检索的精确度和综合相关度。
4结束语
本文提出了一种新的用于搜索非网页的文档的DocumentRank算法，利用搜索词向量得到文档中的词汇以及它们在文档中出现的次数来构建文档之间的重要性矩阵，根据矩阵计算相关度得分对文档进行排序。通过实验证明，相比Lucene索引技术本文的DocumentRank算法提高了文档检索的精确度和综合相关度。
参考文献
[1]陈浩.Web搜索的用户兴趣与智能优化研究[D].长沙：中南大学，2012.
[2]Lv Y H，Zhai C X，Chert W. A boosting approach to improving pseudo-relevance feedback[C]//Research and development in Information Retrieval，ACM，2011:165-174.
[3]Wang L， Lin J， Metzler D. A cascade ranking model for efficient ranked retrieval//Research and development in Information Retrieval，ACM，2011:105-114.
[4]Page L， Brin S， Motwani R， et al.The PageRank citation ranking: Bringing order to the web[J].1998.
[5]花贵春，张敏，刘奕群，等.面向排序的基于查询需求的查询聚类模型[J].计算机研究与发展，2012，49(11)：2 407-2 413.
[6]蔡飞，陈洪辉，舒振.基于用户相关反馈的排序学习算法研究[J].国防科技大学学报，2013，35(2)：132-136.
[7]Bhardwaj A， Mangat V. A Novel Approach for Content Extraction from Web Pages[C]//Engineering and Computational Sciences(RAECS)，2014:1-4.
[8]Sarnovsky M， Vronc M. Distributed boosting algorithm for classification of text documents[C]//Applied Machine Intelligence and Informatics(SAMI)，2014:217-220.
[9]Bing Liu.俞勇等译.Web数据挖掘[M].北京：清华大学出版社，2009:98-102.
[10]马应龙，李鹏鹏，张敬旭.一种基于多分类语义分析和个性化的语义检索方法[J].东南大学学报(自然科学版)，2014，44(2)：262-265.
None-link Document Sorting Algorithm Research
Jiang Zhaolong1， Zhao Zemao2
(1.SchoolofCommunicationEngineering，HangzhouDianziUniversity，HangzhouZhejiang310018，China；
2.DepartmentofIndustrialandDesign,LishuiUniversity,LishuiZhejiang32300,China)
Key words: information retrieval; PageRank algorithm; DocumentRank algorithm; link structure
