自然鄰在文本分類中的應用

朱慶生，張浪，張程

（重慶大學計算機學院，重慶 400044）

自然鄰在文本分類中的應用

朱慶生，張浪，張程

（重慶大學計算機學院，重慶 400044）

在文本分類中，傳統的KNN算法面臨K值不確定，數據集分布不平衡等缺點的影響?；诖颂岢鲎匀秽彽乃枷耄⑵鋺玫轿谋痉诸愔校芎玫乜朔﨣NN文本分類的缺點。首先，自然鄰算法能夠根據數據集自動獲取文本向量的自然鄰居，不需要人為干預，解決K值不確定問題。其次，對于不同的數據點其鄰居數可能不一樣，它會根據數據集的分布自動獲取其對應的自然鄰居，很好地克服數據集分布不平衡問題。并且，根據訓練集的自然鄰居設計一種權重分配算法，使得好鄰居的權值較大，壞鄰居的權值較小，進一步提高分類算法的精確度。

文本分類；自然鄰居；KNN；權重分配

0 引言

近年來，隨著互聯網的飛快發展，網絡信息量呈爆炸性的增長，增長速度比人類歷史任何時期都要快的多，以互聯網為載體的海量數據蘊含著大量的信息價值，因此有效地發現分析挖掘這些信息中的價值是很有必要的，可以給我們帶來更大的生產力，給我們的生活帶來更多的便利。傳統的信息處理方法已經不能完全勝任各式各樣的任務需要，一種新的數據處理方法應運而生，數據挖掘技術[1]彌補了傳統數據處理方法的不足，能夠發現海量數據背后蘊藏的有效信息，并且對于復雜的數據結構，對于那些傳統數據處理方法很難下手的數據類型擁有更強的靈活性。更為重要的是在處理的方法上，不再拘泥于傳統數據的增刪改查，或是數據倉庫的處理，其方法的廣泛性和靈活性非傳統方法所能比擬。

自動文本分類[2]屬于數據挖掘技術中一個重要領域，在互聯網出現之前，人們已經對文本分類進行了一定的研究工作，這些研究往往針對特定的領域，然而，隨著互聯網興起，隨著對大量不同類型的文本進行分類的需求，傳統的分類方法不再適用。我們需要更加自動化的分類方法，文檔自動分類技術的研究勢在必行。國外對文本自動分類的研究最早可追溯到上世紀50年代末，由H.P.LUhn提出的一種基于詞頻統計的文本分類思想開創了文本自動分類的新天地。1960年，Maron發表了第一篇關于文本自動分類算法的論文，之后K.Spark、G.Salton等學者相繼提出了很多關于文本自動分類的實用方法。由于對文本自動分類的研究較早，且技術相對比較成熟，所以在文本自動分類的實際應用上，國外也開始的比較早，而且應用廣泛。其中郵件分類、電子會議取得了廣泛的應用。知名度比較高的有麻省理工學院為白宮開發的郵件分類系統，卡內基集團為路透社開發的Construe系統[4]。

國內文本自動分類的起步較晚，1981年，候漢清教授對計算機在文本自動分類中的應用作了探討和論述[6]。在分類算法的研究方面，中科院計算所的李曉黎、史忠植等人將概念推理網應用到文本分類中[5]，使得準確率和召回率得到比較明顯的提高。中國科技大學的范焱等人提出了一種超文本協調分類器[3]，它適當考慮了HTML文本中的結構化信息，并將其和KNN、貝葉斯、和文檔相似性研究結合起來，使得正確率接近80%。復旦大學和富士通研究中心的黃萱箐、吳力德對獨立語種的文本分類進行了研究[8]，用詞匯和類別的互信息量為評價函數，使得召回率達到88.87%。上海交通大學的刁倩、王永成等人考慮了詞的權重和信息[11]，使得分類算法的準確率到達97%。

對于文本分類，相對比較成熟的分類算法有KNN分類算法、貝葉斯分類算法、支持向量機分類算法、決策樹分類算法、神經網絡等分類算法[7]。這些都是比較成熟的傳統分本自動分類算法，很多學者基于上述方法對其改進能夠得到整體效率或者對于部分數據集效率一定程度提高的混合型算法。

文本針對傳統的KNN算法所面臨的不足點，創造性提出了自然鄰的思想，并將其應用到文本分類中，解決了KNN文本分類算法中K值無法確定問題，并提高了分類準確度。

1 文本分類定義與過程

文本分類屬于分類問題，是一種有監督的學習。它的任務是：根據已定義類標簽的訓練集將未定義類標簽的測試集中的每個文本分類到一個或者多個類標簽中。這里有三點需要注意，第一，用于分類的類標簽是已經定義好的，并且，訓練集都有屬于的類標簽，這樣才能從訓練文本中學習到規則，為測試文本分類。第二，測試文本集中的文本可以被分配到一個或者多個標簽中，而不是僅僅只能分配到一個標簽中。第三，文本分類的類標簽并不一定是主題信息，也就是說類標簽可以是文章性質，例如積極消極，寫作風格等。

文本分類一般過程可分為以下幾個步驟。文本預處理，特征提取，特征權重計算，訓練，分類預測[10]。如圖1給出了文本分類的一般流程圖。

2 基于KNN文本分類

2.1 KNN文本分類步驟

基于KNN的文本分類算法基本思想是：對于文本測試集中的每個文本向量，通過某種距離度量在訓練文本向量中找出與其最近的K個鄰居，并根據這K個鄰居的類別信息將測試文本歸類到相應的類別中，具體算法步驟見如下算法1：

算法1 KNN文本分類算法

輸入：訓練文本向量D，測試文本向量T，K

輸出：帶有預測類別的測試文本集

算法步驟：

Step1：對每個測試文本向量，計算距離訓練文本向量最近的K的鄰居

Step2：計算每個測試文本向量屬于每個類別的余弦相似度總和

Step3：將改測試樣本歸類到余弦相似度總和最大的類別中

Step4：遍歷所有的測試文本向量，完成并輸出分類結果

圖1 文本分類流程圖

2.2 KNN文本分類缺點

基于KNN的文本分類算法簡單、魯棒性好且易于實現，并且具有不錯的分類精度[9]。但是也和其他的算法一樣有其自身的缺點，主要缺點如下：

（1）K值不易確定

KNN分類時K值的設定不確定，需要嘗試不同的K值來找到最佳的K值，并且文本分類所使用的數據集不一樣時，又得重新尋找最佳的K值，這是比較麻煩的事情，如果K值設定過大，那么它的K個鄰居中可能包含很多和測試樣本類別不同的鄰居，這樣必定會影響分類結果。如果K值設定太小，它的鄰居數很小，很容易收到誤差點的影響。

（2）分類精度受數據集分類影響很大

導致這樣的主要原因是對于所有的測試文本向量，它所找的鄰居數都是K，也就是說無論是稀疏的點還是稠密的點，它所比較的鄰居數都是一樣的，這顯然有些不合理。

（3）計算復雜度大

KNN文本分類需要計算每個測試文本向量與訓練向量的距離，當訓練文本向量很大時，其計算復雜度會很大。

3 基于自然鄰的文本分類

3.1 自然鄰概念

基于傳統的K近鄰思想，本文提出了一種無尺度的近鄰度量方法即自然鄰方法。所謂自然鄰，顧名思義，即根據數據集自身的分布情況自適應的得到每個樣本點的鄰居。那么，如何獲取呢？其具體步驟為：以KNN為基礎，K值從1遞增，每次統計互為鄰居的數目是否達到自然穩定狀態，如果達到自然穩定狀態，認為那些互為鄰居的點便為各自的自然鄰居。具體算法如下。

算法1自然鄰居算法

輸入：數據集X

輸出：自然鄰居特征值λ自然鄰居鄰域圖邊集NaN_Edge

其中，λ表示自然鄰居特征值；NaN_Edge表示自然鄰居邊集；NaN_Num（xi）表示xi的自然鄰居數目；knnr（xi）表示xi的r近鄰；KNNr（xi）表示xi的r鄰域；

3.2 基于自然鄰的權重分配

下面文本根據上面提出的自然鄰算法，對文本訓練集中的數據進行訓練，得到訓練集中的每個文本向量的權重信息，使得有價值的文本向量具有較高的權重，而那些存在誤差的文本向量具有較低的權重信息，這樣對于后面測試文本的分類起到指導作用。

定義一：對于?dj∈NaN_Edge（di），如果di與dj的類標記相同，則dj就是di好的自然鄰居，好的自然鄰居的個數為G_NaN（di）。

定義二：對于?dj∈NaN_Edge（di），如果di與dj的類標記不相同，則dj就是di壞的自然鄰居，壞的自然鄰居的個數為B_NaN（di）。

定義三：dj的加權修正因子如下：

基于上述定義，基于自然鄰的權重分類算法如下：

算法2基于自然鄰的訓練集加權算法

輸入：訓練文本向量D

輸出：訓練文本集的權重矩陣W

算法步驟：

Step1：?di∈D，使用自然鄰居算法得到NaN_Edge（di）

Step2：?di∈D，遍歷它的自然鄰居，并根據上述定義計算出它的好的自然鄰居數G_NaN（di）和壞的自然鄰居數B_NaN（di）

Step3：根據上述定義三計算出di的權值w（di）

Step4：遍歷完所有的訓練集，完成計算，輸出W

3.3 基于自然鄰的文本分類

下面本文提出了基于自然鄰的文本分類算法，對于每個文本測試集中的向量，根據上述算法1找到它的自然鄰居，并結合算法2中訓練文本向量的權重信息，計算出每個文本測試向量與每個類別的加權相似度之和，將其歸類到相似度之和最大的類別中，具體算法步驟如下算法3所示。

算法3基于自然鄰的文本分類算法

輸入：訓練文本向量D，測試文本向量T，訓練文本向量集的權值矩陣W

輸出：帶有預測類別的測試集

算法步驟：

Step1：對每個測試文本向量，將其與訓練文本向量D合并為數據集Z

Step2：根據前面的自然鄰居算法，計算得到測試文本向量Ti的的自然鄰居NaN_Edge（Ti）和自然鄰居特征值λ和自然鄰居個數NaN_Num（Ti）

Step3：如果上述NaN_Num（Ti）=0，我們重新定義NaN_Num（Ti）=λ

Step4：計算Ti到其所有自然鄰居的余弦相似度

Step5：將上述得到的余弦相似度乘以對應的訓練樣本的權值矩陣W得到Ti與每個自然鄰居的加權相似度

Step6：統計Ti與每個類別的加權相似度之和，并將其分類到權值相似度最大的類別中

Step7：重復上述步驟（1）到步驟（6），直到所有的測試樣本都處理完

4 實驗結果與分析

本文所使用的數據集為Newsgroups數據集，選擇其中的10個類別，每個類別選擇400個文本文件，總共4000個文件，其中3600作為訓練集，400作為測試集。其原始文件如下：

表1 數據集

經數據預處理過后，對其進行特征提取，本文使用的是詞頻，為了不影響后面的分類精度，本文測試了不同詞頻下的文本特征數以及KNN文本分類算法的準確率，如下表2所示。

表2 不同特征KNN分類準確率

上述表中，詞頻項表示提取特征時使用的最小詞頻數，特征數表示大于等于此詞頻的總特征數，K值表示使用KNN算法時K的取值。

從上述表中我們的看到，隨著詞頻的增加，特征數的減少，分類準確率整體先穩定后減少，隨著K值的增大，分類準確率先增大，后趨于穩定，K值取40到60之間時，獲取最高的準確率。當詞頻取5時，既充分減少了特征數，也能保留文本的絕大部分信息。所以，本文進行特征選擇時，詞頻選擇大于等于5，此時的特征數為11976，在使用KNN算法與自然鄰做比較時，選擇的K值為40到60。

根據上述的分析進行對比實驗，使用十折交叉驗證，對比KNN與自然鄰的分類準確率和F1，其具體結果如下表3和表4所示。

表3 準確率對比

表4 F1值對比

根據上述表3和表4的對比結果，自然鄰算法無論在分類準確率和F1值都比傳統KNN算法的高，在準確率對比試驗中，只有第二個類別（Comp.graphics）KNN算法比自然鄰算法高，其他類別中都是自然鄰算法的準確率較高，在F1值對比試驗中，只有第二第三個類別中KNN算法比自然鄰算法高，其他類別都是自然鄰算法的F1值高。因此，實驗很好地驗證了自然鄰算法在分類精度上的準確性。

5 結語

在KNN文本分類中，K值的確定是一個難題，而且KNN算法對數據集比較敏感，基于此本文提出了自然鄰居的思想，很好地解決了上述兩個難題，并且提高了分類準確率。然而對于KNN算法時間復雜度比較高的難題仍然存在，仍有待解決。

[1]汪明.數據挖掘綜述[J].河北軟件職業技術學院學報，2012，14（1）:45-48.

[2]J.Han，M.Kanber.數據挖掘-概念與技術.范明，孟小峰等譯.北京：機械工業出版社，2001.

[3]湛燕.K近鄰、K均值及其在文本分類中的應用.碩士學位論文.河北大學，2003.

[4]王繼成，潘金貴，張福炎.Web文本挖掘技術研究.計算機研究與發展，2000，37（5）:513-520.

[5]王本年，高陽，陳世福等.Web智能研究現狀與發展趨勢.計算機研究與發展，2005，42（5）:721-727.

[6]侯漢清.分類法的發展趨勢簡論.北京:中國人民大學出版社，1981.

[7]張治平.Web信息精確獲取技術研究.碩士學位論文,國防科學技術大學，2004.

[8]獨立于語種的文本分類方法.2000 International Conference Multilingual Information Processing，2000:37-43.

[9]張海燕.基于分詞的中文文本自動分類研究與實現.碩士學位論文.湖南大學，2002.

[10]刁倩，王永成，張惠惠等.VSM中詞權重的信息嫡算法.情報學報，2000，19（4）:354-358.

[11]Y.Yang,J.Wilbur.Using Corpus Statistics to Remove Redundant Words in Text Categorization.Information Science,1996.

Application of Natural Neighbor in Text Classification

ZHU Qing-sheng，ZHANG Lang，ZHANG Cheng

（College of Computer Science，Chongqing University，Chongqing 400044）

In text classification,traditional KNN algorithm is affected by the uncertainty of K value and the unbalanced distribution of data sets.Proposes the idea of natural neighbor and applies it to text classification,which can overcome the disadvantages of KNN text classification. Firstly,the natural neighbor algorithm can automatically obtain the natural neighbor of the text vector according to the data set,and it is not necessary for human intervention.So it can solve the problem of uncertainty of K value.Secondly,for different data points,the number of neighbors may not be the same,it will automatically obtain their corresponding natural neighbors based on the distribution of the data set which can solve the problem of unbalanced distribution of data sets.In addition,according to the natural neighbor of the training set,designs a weight assignment algorithm,which makes the weight of the good neighbors larger and the weight of the bad neighbors smaller which improves the accuracy of the classification algorithm.

Text Classification;Natural Neighbor;KNN;Weight Assignment

1007-1423（2017）11-0042-05

10.3969/j.issn.1007-1423.2017.11.008

朱慶生（1957-），男，安徽當涂人，教授，博士，研究方向為面向服務的軟件工程、離群檢測、數據挖掘

2017-03-21

2017-04-10

重慶市研究生科研創新項目（No.CYS15029）、重慶市基礎科學與前沿研究計劃項目（No.cstc2013jcyjA40049）

張浪（1990-），男，江蘇淮安人，碩士研究生，研究方向為機器學習、數據挖掘

張程（1977-），男，重慶人，副教授，博士，研究方向為移動智能、無線自組網絡