基于KNN的2015NIPS论文集文档相似度分析

尧涛

摘 要：以2015年NIPS会议（世界上顶级的机器学习会议之一）上收录的论文集为研究对象，通过一系列的相关数据处理方法将其整理成实验数据（提供下载），基于Abstract和Fulltext模型下建立TF-IDF矩阵，通过KNN算法来计算和对比二者的文档相似度。实验结果发现，Abstract模型下建立TF-IDF矩阵的时间要远优于Fulltext模型；二者模型下的共同相似文档个数随着K nearest neighborhood（KNN）算法K的增大而增大。与以往单方面在Fulltext模型下进行文档相似度计算而言，Abstract模型在为我们进一步研究文档相似度提供了更好的依据。

关键词：相似论文 Abstract Fulltext TF-IDF KNN

中图分类号：TP311 文献标识码：A 文章编号：1672-3791（2017）03（a）-0217-03

现如今随着越来越多的学术会议的召开，学术成果数量的日益增长，如何快速查找相关论文变得非常重要。对于一篇给定的论文来查找当前论文集的其他相似论文，文档相似度的有效计算是进行信息处理[1]的关键。文档相似度[2]是表示两个或者多个文档直接匹配程度的一个度量参数，相似度越大说明两者文档相似程度高，反之则文档相似程度低。大多数情况下研究者对TF-IDF建立文档矩阵只会考虑Fulltext，而忽略Abstract。基于这一点，本文通过尝试性的实验研究來对论文相似度进行比较分析。主要是以2015年NIPS（Neural Information Processing Systems）收录的论文为研究对象，基于Abstract和Fulltext的模型下先建立TF-IDF矩阵，再利用KNN[3]算法进行相似度的分析，这为进一步研究文档相似度提供新方法。

1 相关知识

1.1 自定义文档分块

文档分块[4]是通过识别文档的组织结构，并根据结构将文档划分为多个块。比如一般的论文，被划分为标题（Title）、摘要（Abstract）、正文（body）、参考文献（References）等部分，从而构建出一个文档块向量空间模型[5]，并根据各文档块的文本内容建立与之对应的特征项向量。下面给出文档块定义。

定义1：文档块，指文档经过分块处理后得到的第j个具有特殊作用的文档部分，记作。正如前面提到的标题、摘要、正文、参考文献等文档部分都可以作为文档块，从而可以将文档di 用公式表示：

（1）

式中 n表示文档di 经过划分后得到的文档块数量。

在文档块向量空间模型中，一个文本被分割为无数个文本块，每个文本块代表该文本中一个独特的部分，可能只包含一个句子（如标题），可能包含一个自然段的文本（如摘要），也可能是很多个自然段的组合（如正文）。

1.2 KNN：k-最近邻

KNN是一种分类方法，又叫k近邻算法。其主要思想：给定一个训练集D和一个测试对象z，该测试对象是一个由属性值和一个未知的类别标签组成的向量，该算法需要计算z和每个训练对象之间的距离（或相似度），这样就可以确定最近邻的列表。然后，将最近中实例数量占优的类别赋给z，当然也不是只能采取这一种策略，例如，甚至可以从训练集中随机选择一个类或选择最大类。

基本的KNN算法如下：

（1）Input： D，是训练集；z，测试对象，它是属性值构成的向量；L，对象的类别标签集合。

（2）Output：cz属于L，即z的类别。

（3）foreach y属于D do。

（4）计算d（y，z），即y和z的距离；或者sim（y，z），即y和z的相似度。

（5）end。

（6）从数据集D中选出子集N，N包含k个距z最近的训练对象。

（7）。

（8）I（.）是一个指标函数，当其值为true时返回值为1，否则返回0。

2 实验开展

2.1 实验数据

该文整理了2015年在NIPS会议上收录的403篇论文，将其构造成2015-nips-data.zip供研究者下载（下载地址：https：//github.com/Yiutto/2015-nips-data.zip/）。2015-nips-data.zip主要包括Papers.csv、Author.csv、PaperAuthors.csv。

（1）Papers.csv：该文件包含2015年共收录得403篇NIPS papers，包括以下字段：

* Id-论文的唯一标识符

* Title-论文的标题

* EventType-是否为poster、oral、或者spotlight presentation

* PdfName-pdf文档的名

* Abstract-论文的摘要

* Fulltext-pdf格式文档转换为text文档

（2）Authors.csv：该文件包含这一年在NIPS会议上的作者标识符和作者名（2015年共有1078个唯一作者）。

* Id-作者的唯一标识符

* Name-作者名

（3）PaperAuthors.csv：该文件链接的是作者对应自己的论文。

* Id-索引号

* PaperId-论文的唯一标识符

* AuthorId-作者的唯一标识

2.2 实验准备工作

实验环境在Python2.7，Linux环境下进行的，实验数据是上文中的2015-nips-data.zip（Papers.csv、Author.csv、PaperAuthors.csv）。

（1）数据的导入：可以通过Python包pandas中的read_csv函数。

（2）数据的清洗：一般说来，pdf文档转换为文本文档中可以含有一些特殊字符，如“＼n”、“＼x”等等，为了方便数据处理，必须将这些字符替换为空白字符，使所有字母统一为小写字母，在这里还将用到正则表达式[6] “[^a-zA-Z]+”来将非英文单词替换为空。

（3）提取词干：可以利用Python包NLTK中的SnowballStemmer，通过正则表达式“[a-zA-Z]”来获取英文单词。

（4）建立TF-IDF矩阵：通过Python包sklearn.feature_extraction.text中的TfidfVectorize来建立基于Abstract和Fulltext的 TF-IDF矩阵。

（5）KNN算法实现：可以利用Python包sklearn.neighbors的NearestNeighbors里实现了无监督的最近邻学习，它为三种不同的学习算法（Ball-Tree，KD-Tree，还有基于sklearn.metrics.pairwise规则的brute-force）提供了统一的接口。如果需要使用哪种算法只需要设置参数时指定关键字‘algorithm為[‘auto，‘ball_tree，‘kd_tree，‘brute] 其中的一种就好，默认值是auto。在auto下，将会从你给定的测试数据当中选择最终性能最好的哪一个算法。

2.3 实验结果及分析

2.3.1 基于Abstract&Fulltext模型下建立TF-IDF的时间对比

如表1，结合实验数据通过对两种模型下建立TF-IDF的真实时间（Wall time）对比可以发现，基于Fulltext模型下建立TF-IDF_MATRIX所花费的时间是基于Abstract模型下的29.33倍。

2.3.2 基于Abstract&Fulltext实验结果下文档相似度的对比

下面以Paper_Index=1的论文为例，分别找出该论文在Abstract和Fulltext下的相似文档，以便对比二者下文档相似度，得出的实验结果将添加至表2，此时KNN算法中的k=4。

结合表2可发现：（1）基于Abstract和Fulltext下，二者共同的相似论文只有一篇Paper_Index=112；（2）Paper_Index=1与Paper_Index =112在基于Abstract模型下的文档相似度（这里用的是欧几里得距离）为1.12697021，而在基于Fulltext模型下为1.12549633，两者相差0.001左右。其他Paper_Index下的对比相差0.1～0.2左右。

2.3.3 不同K值下KNN对Abstract&Fulltext的影响

图1是笔者基于KNN取不同k值（k=3，4，5，6），针对所有2015年NIPS papers（共计403篇）来分别计算出Abstract和Fulltext模型下的相似论文，统计出共同的相似论文篇数。横坐标Paper_Idx表示论文的索引号，纵坐标CommonSimilarPaper_Nums表示Abstract和Fulltext模型下共同的相似论文篇数。从图1可见，k越大，索引号为Paper_Idx的论文在Abstract和Fulltext模型下共同的相似论文篇数也逐渐增大。

3 结语

该文整理了2015年NIPS所收录的论文作为实验数据并提供下载，在此数据上，研究者可用于分析2015年NIPS的研究趋势、作者附属机构、合作者等。如若有需要，研究者也可以根据附在网站的相应代码自行整理近几年NIPS的论文集。针对上述实验结果分析，在时间上Abstract模型优于Fulltext模型；在某种程度上二者模型下的共同相似文档个数随着KNN算法k的增大而增大。

参考文献

[1] 黄昌宁.中文信息处理中的分词问题[J].语言文字应用， 1997 （1）： 74-80.

[2] 郭庆琳，李艳梅，唐琦.基于 VSM 的文本相似度计算的研究[J].计算机应用研究，2008，25（11）：3256-3258.

[3] 乔鸿欣.基于MapReduce的KNN分类算法的研究与实现[D].北京交通大学，2012.

[4] CHEN Z P，LIN Y P，TONG T S.AN INFORMATION-RETRIEVAL METHOD BASED ON N-LEVEL VECTOR MODEL[J].Journal of Computer Research and Development，2002（10）：10.

[5] Salton G，Wong A， Yang C S. A vector space model for automatic indexing[J].Communications of the ACM，1975， 18（11）：613-620.

[6] Friedl J E F，余晟.精通正则表达式[M].电子工业出版社， 2007.