基于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.