基于KNN的2015NIPS論文集文檔相似度分析

堯濤

摘 要：以2015年NIPS會(huì)議（世界上頂級(jí)的機(jī)器學(xué)習(xí)會(huì)議之一）上收錄的論文集為研究對(duì)象，通過一系列的相關(guān)數(shù)據(jù)處理方法將其整理成實(shí)驗(yàn)數(shù)據(jù)（提供下載），基于Abstract和Fulltext模型下建立TF-IDF矩陣，通過KNN算法來計(jì)算和對(duì)比二者的文檔相似度。實(shí)驗(yàn)結(jié)果發(fā)現(xiàn)，Abstract模型下建立TF-IDF矩陣的時(shí)間要遠(yuǎn)優(yōu)于Fulltext模型；二者模型下的共同相似文檔個(gè)數(shù)隨著K nearest neighborhood（KNN）算法K的增大而增大。與以往單方面在Fulltext模型下進(jìn)行文檔相似度計(jì)算而言，Abstract模型在為我們進(jìn)一步研究文檔相似度提供了更好的依據(jù)。

關(guān)鍵詞：相似論文 Abstract Fulltext TF-IDF KNN

中圖分類號(hào)：TP311 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1672-3791（2017）03（a）-0217-03

現(xiàn)如今隨著越來越多的學(xué)術(shù)會(huì)議的召開，學(xué)術(shù)成果數(shù)量的日益增長(zhǎng)，如何快速查找相關(guān)論文變得非常重要。對(duì)于一篇給定的論文來查找當(dāng)前論文集的其他相似論文，文檔相似度的有效計(jì)算是進(jìn)行信息處理[1]的關(guān)鍵。文檔相似度[2]是表示兩個(gè)或者多個(gè)文檔直接匹配程度的一個(gè)度量參數(shù)，相似度越大說明兩者文檔相似程度高，反之則文檔相似程度低。大多數(shù)情況下研究者對(duì)TF-IDF建立文檔矩陣只會(huì)考慮Fulltext，而忽略Abstract?；谶@一點(diǎn)，本文通過嘗試性的實(shí)驗(yàn)研究來對(duì)論文相似度進(jìn)行比較分析。主要是以2015年NIPS（Neural Information Processing Systems）收錄的論文為研究對(duì)象，基于Abstract和Fulltext的模型下先建立TF-IDF矩陣，再利用KNN[3]算法進(jìn)行相似度的分析，這為進(jìn)一步研究文檔相似度提供新方法。

1 相關(guān)知識(shí)

1.1 自定義文檔分塊

文檔分塊[4]是通過識(shí)別文檔的組織結(jié)構(gòu)，并根據(jù)結(jié)構(gòu)將文檔劃分為多個(gè)塊。比如一般的論文，被劃分為標(biāo)題（Title）、摘要（Abstract）、正文（body）、參考文獻(xiàn)（References）等部分，從而構(gòu)建出一個(gè)文檔塊向量空間模型[5]，并根據(jù)各文檔塊的文本內(nèi)容建立與之對(duì)應(yīng)的特征項(xiàng)向量。下面給出文檔塊定義。

定義1：文檔塊，指文檔經(jīng)過分塊處理后得到的第j個(gè)具有特殊作用的文檔部分，記作。正如前面提到的標(biāo)題、摘要、正文、參考文獻(xiàn)等文檔部分都可以作為文檔塊，從而可以將文檔di 用公式表示：

（1）

式中 n表示文檔di 經(jīng)過劃分后得到的文檔塊數(shù)量。

在文檔塊向量空間模型中，一個(gè)文本被分割為無數(shù)個(gè)文本塊，每個(gè)文本塊代表該文本中一個(gè)獨(dú)特的部分，可能只包含一個(gè)句子（如標(biāo)題），可能包含一個(gè)自然段的文本（如摘要），也可能是很多個(gè)自然段的組合（如正文）。

1.2 KNN：k-最近鄰

KNN是一種分類方法，又叫k近鄰算法。其主要思想：給定一個(gè)訓(xùn)練集D和一個(gè)測(cè)試對(duì)象z，該測(cè)試對(duì)象是一個(gè)由屬性值和一個(gè)未知的類別標(biāo)簽組成的向量，該算法需要計(jì)算z和每個(gè)訓(xùn)練對(duì)象之間的距離（或相似度），這樣就可以確定最近鄰的列表。然后，將最近中實(shí)例數(shù)量占優(yōu)的類別賦給z，當(dāng)然也不是只能采取這一種策略，例如，甚至可以從訓(xùn)練集中隨機(jī)選擇一個(gè)類或選擇最大類。

基本的KNN算法如下：

（1）Input： D，是訓(xùn)練集；z，測(cè)試對(duì)象，它是屬性值構(gòu)成的向量；L，對(duì)象的類別標(biāo)簽集合。

（2）Output：cz屬于L，即z的類別。

（3）foreach y屬于D do。

（4）計(jì)算d（y，z），即y和z的距離；或者sim（y，z），即y和z的相似度。

（5）end。

（6）從數(shù)據(jù)集D中選出子集N，N包含k個(gè)距z最近的訓(xùn)練對(duì)象。

（7）。

（8）I（.）是一個(gè)指標(biāo)函數(shù)，當(dāng)其值為true時(shí)返回值為1，否則返回0。

2 實(shí)驗(yàn)開展

2.1 實(shí)驗(yàn)數(shù)據(jù)

該文整理了2015年在NIPS會(huì)議上收錄的403篇論文，將其構(gòu)造成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-論文的唯一標(biāo)識(shí)符

* Title-論文的標(biāo)題

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

* PdfName-pdf文檔的名

* Abstract-論文的摘要

* Fulltext-pdf格式文檔轉(zhuǎn)換為text文檔

（2）Authors.csv：該文件包含這一年在NIPS會(huì)議上的作者標(biāo)識(shí)符和作者名（2015年共有1078個(gè)唯一作者）。

* Id-作者的唯一標(biāo)識(shí)符

* Name-作者名

（3）PaperAuthors.csv：該文件鏈接的是作者對(duì)應(yīng)自己的論文。

* Id-索引號(hào)

* PaperId-論文的唯一標(biāo)識(shí)符

* AuthorId-作者的唯一標(biāo)識(shí)

2.2 實(shí)驗(yàn)準(zhǔn)備工作

實(shí)驗(yàn)環(huán)境在Python2.7，Linux環(huán)境下進(jìn)行的，實(shí)驗(yàn)數(shù)據(jù)是上文中的2015-nips-data.zip（Papers.csv、Author.csv、PaperAuthors.csv）。

（1）數(shù)據(jù)的導(dǎo)入：可以通過Python包pandas中的read_csv函數(shù)。

（2）數(shù)據(jù)的清洗：一般說來，pdf文檔轉(zhuǎn)換為文本文檔中可以含有一些特殊字符，如“＼n”、“＼x”等等，為了方便數(shù)據(jù)處理，必須將這些字符替換為空白字符，使所有字母統(tǒng)一為小寫字母，在這里還將用到正則表達(dá)式[6] “[^a-zA-Z]+”來將非英文單詞替換為空。

（3）提取詞干：可以利用Python包NLTK中的SnowballStemmer，通過正則表達(dá)式“[a-zA-Z]”來獲取英文單詞。

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

（5）KNN算法實(shí)現(xiàn)：可以利用Python包sklearn.neighbors的NearestNeighbors里實(shí)現(xiàn)了無監(jiān)督的最近鄰學(xué)習(xí)，它為三種不同的學(xué)習(xí)算法（Ball-Tree，KD-Tree，還有基于sklearn.metrics.pairwise規(guī)則的brute-force）提供了統(tǒng)一的接口。如果需要使用哪種算法只需要設(shè)置參數(shù)時(shí)指定關(guān)鍵字‘a(chǎn)lgorithm為[‘a(chǎn)uto，‘ball_tree，‘kd_tree，‘brute] 其中的一種就好，默認(rèn)值是auto。在auto下，將會(huì)從你給定的測(cè)試數(shù)據(jù)當(dāng)中選擇最終性能最好的哪一個(gè)算法。

2.3 實(shí)驗(yàn)結(jié)果及分析

2.3.1 基于Abstract&Fulltext模型下建立TF-IDF的時(shí)間對(duì)比

如表1，結(jié)合實(shí)驗(yàn)數(shù)據(jù)通過對(duì)兩種模型下建立TF-IDF的真實(shí)時(shí)間（Wall time）對(duì)比可以發(fā)現(xiàn)，基于Fulltext模型下建立TF-IDF_MATRIX所花費(fèi)的時(shí)間是基于Abstract模型下的29.33倍。

2.3.2 基于Abstract&Fulltext實(shí)驗(yàn)結(jié)果下文檔相似度的對(duì)比

下面以Paper_Index=1的論文為例，分別找出該論文在Abstract和Fulltext下的相似文檔，以便對(duì)比二者下文檔相似度，得出的實(shí)驗(yàn)結(jié)果將添加至表2，此時(shí)KNN算法中的k=4。

結(jié)合表2可發(fā)現(xiàn)：（1）基于Abstract和Fulltext下，二者共同的相似論文只有一篇Paper_Index=112；（2）Paper_Index=1與Paper_Index =112在基于Abstract模型下的文檔相似度（這里用的是歐幾里得距離）為1.12697021，而在基于Fulltext模型下為1.12549633，兩者相差0.001左右。其他Paper_Index下的對(duì)比相差0.1～0.2左右。

2.3.3 不同K值下KNN對(duì)Abstract&Fulltext的影響

圖1是筆者基于KNN取不同k值（k=3，4，5，6），針對(duì)所有2015年NIPS papers（共計(jì)403篇）來分別計(jì)算出Abstract和Fulltext模型下的相似論文，統(tǒng)計(jì)出共同的相似論文篇數(shù)。橫坐標(biāo)Paper_Idx表示論文的索引號(hào)，縱坐標(biāo)CommonSimilarPaper_Nums表示Abstract和Fulltext模型下共同的相似論文篇數(shù)。從圖1可見，k越大，索引號(hào)為Paper_Idx的論文在Abstract和Fulltext模型下共同的相似論文篇數(shù)也逐漸增大。

3 結(jié)語

該文整理了2015年NIPS所收錄的論文作為實(shí)驗(yàn)數(shù)據(jù)并提供下載，在此數(shù)據(jù)上，研究者可用于分析2015年NIPS的研究趨勢(shì)、作者附屬機(jī)構(gòu)、合作者等。如若有需要，研究者也可以根據(jù)附在網(wǎng)站的相應(yīng)代碼自行整理近幾年NIPS的論文集。針對(duì)上述實(shí)驗(yàn)結(jié)果分析，在時(shí)間上Abstract模型優(yōu)于Fulltext模型；在某種程度上二者模型下的共同相似文檔個(gè)數(shù)隨著KNN算法k的增大而增大。

參考文獻(xiàn)

[1] 黃昌寧.中文信息處理中的分詞問題[J].語言文字應(yīng)用， 1997 （1）： 74-80.

[2] 郭慶琳，李艷梅，唐琦.基于 VSM 的文本相似度計(jì)算的研究[J].計(jì)算機(jī)應(yīng)用研究，2008，25（11）：3256-3258.

[3] 喬鴻欣.基于MapReduce的KNN分類算法的研究與實(shí)現(xiàn)[D].北京交通大學(xué)，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，余晟.精通正則表達(dá)式[M].電子工業(yè)出版社， 2007.