自然鄰在文本分類中的應(yīng)用

朱慶生，張浪，張程

（重慶大學(xué)計(jì)算機(jī)學(xué)院，重慶 400044）

自然鄰在文本分類中的應(yīng)用

朱慶生，張浪，張程

（重慶大學(xué)計(jì)算機(jī)學(xué)院，重慶 400044）

在文本分類中，傳統(tǒng)的KNN算法面臨K值不確定，數(shù)據(jù)集分布不平衡等缺點(diǎn)的影響?；诖颂岢鲎匀秽彽乃枷耄⑵鋺?yīng)用到文本分類中，很好地克服KNN文本分類的缺點(diǎn)。首先，自然鄰算法能夠根據(jù)數(shù)據(jù)集自動獲取文本向量的自然鄰居，不需要人為干預(yù)，解決K值不確定問題。其次，對于不同的數(shù)據(jù)點(diǎn)其鄰居數(shù)可能不一樣，它會根據(jù)數(shù)據(jù)集的分布自動獲取其對應(yīng)的自然鄰居，很好地克服數(shù)據(jù)集分布不平衡問題。并且，根據(jù)訓(xùn)練集的自然鄰居設(shè)計(jì)一種權(quán)重分配算法，使得好鄰居的權(quán)值較大，壞鄰居的權(quán)值較小，進(jìn)一步提高分類算法的精確度。

文本分類；自然鄰居；KNN；權(quán)重分配

0 引言

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

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

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

對于文本分類，相對比較成熟的分類算法有KNN分類算法、貝葉斯分類算法、支持向量機(jī)分類算法、決策樹分類算法、神經(jīng)網(wǎng)絡(luò)等分類算法[7]。這些都是比較成熟的傳統(tǒng)分本自動分類算法，很多學(xué)者基于上述方法對其改進(jìn)能夠得到整體效率或者對于部分?jǐn)?shù)據(jù)集效率一定程度提高的混合型算法。

文本針對傳統(tǒng)的KNN算法所面臨的不足點(diǎn)，創(chuàng)造性提出了自然鄰的思想，并將其應(yīng)用到文本分類中，解決了KNN文本分類算法中K值無法確定問題，并提高了分類準(zhǔn)確度。

1 文本分類定義與過程

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

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

2 基于KNN文本分類

2.1 KNN文本分類步驟

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

算法1 KNN文本分類算法

輸入：訓(xùn)練文本向量D，測試文本向量T，K

輸出：帶有預(yù)測類別的測試文本集

算法步驟：

Step1：對每個測試文本向量，計(jì)算距離訓(xùn)練文本向量最近的K的鄰居

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

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

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

圖1 文本分類流程圖

2.2 KNN文本分類缺點(diǎn)

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

（1）K值不易確定

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

（2）分類精度受數(shù)據(jù)集分類影響很大

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

（3）計(jì)算復(fù)雜度大

KNN文本分類需要計(jì)算每個測試文本向量與訓(xùn)練向量的距離，當(dāng)訓(xùn)練文本向量很大時，其計(jì)算復(fù)雜度會很大。

3 基于自然鄰的文本分類

3.1 自然鄰概念

基于傳統(tǒng)的K近鄰思想，本文提出了一種無尺度的近鄰度量方法即自然鄰方法。所謂自然鄰，顧名思義，即根據(jù)數(shù)據(jù)集自身的分布情況自適應(yīng)的得到每個樣本點(diǎn)的鄰居。那么，如何獲取呢？其具體步驟為：以KNN為基礎(chǔ)，K值從1遞增，每次統(tǒng)計(jì)互為鄰居的數(shù)目是否達(dá)到自然穩(wěn)定狀態(tài)，如果達(dá)到自然穩(wěn)定狀態(tài)，認(rèn)為那些互為鄰居的點(diǎn)便為各自的自然鄰居。具體算法如下。

算法1自然鄰居算法

輸入：數(shù)據(jù)集X

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

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

3.2 基于自然鄰的權(quán)重分配

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

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

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

定義三：dj的加權(quán)修正因子如下：

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

算法2基于自然鄰的訓(xùn)練集加權(quán)算法

輸入：訓(xùn)練文本向量D

輸出：訓(xùn)練文本集的權(quán)重矩陣W

算法步驟：

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

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

Step3：根據(jù)上述定義三計(jì)算出di的權(quán)值w（di）

Step4：遍歷完所有的訓(xùn)練集，完成計(jì)算，輸出W

3.3 基于自然鄰的文本分類

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

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

輸入：訓(xùn)練文本向量D，測試文本向量T，訓(xùn)練文本向量集的權(quán)值矩陣W

輸出：帶有預(yù)測類別的測試集

算法步驟：

Step1：對每個測試文本向量，將其與訓(xùn)練文本向量D合并為數(shù)據(jù)集Z

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

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

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

Step5：將上述得到的余弦相似度乘以對應(yīng)的訓(xùn)練樣本的權(quán)值矩陣W得到Ti與每個自然鄰居的加權(quán)相似度

Step6：統(tǒng)計(jì)Ti與每個類別的加權(quán)相似度之和，并將其分類到權(quán)值相似度最大的類別中

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

4 實(shí)驗(yàn)結(jié)果與分析

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

表1 數(shù)據(jù)集

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

表2 不同特征KNN分類準(zhǔn)確率

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

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

根據(jù)上述的分析進(jìn)行對比實(shí)驗(yàn)，使用十折交叉驗(yàn)證，對比KNN與自然鄰的分類準(zhǔn)確率和F1，其具體結(jié)果如下表3和表4所示。

表3 準(zhǔn)確率對比

表4 F1值對比

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

5 結(jié)語

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

[1]汪明.數(shù)據(jù)挖掘綜述[J].河北軟件職業(yè)技術(shù)學(xué)院學(xué)報(bào)，2012，14（1）:45-48.

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

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

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

[5]王本年，高陽，陳世福等.Web智能研究現(xiàn)狀與發(fā)展趨勢.計(jì)算機(jī)研究與發(fā)展，2005，42（5）:721-727.

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

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

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

[9]張海燕.基于分詞的中文文本自動分類研究與實(shí)現(xiàn).碩士學(xué)位論文.湖南大學(xué)，2002.

[10]刁倩，王永成，張惠惠等.VSM中詞權(quán)重的信息嫡算法.情報(bào)學(xué)報(bào)，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-），男，安徽當(dāng)涂人，教授，博士，研究方向?yàn)槊嫦蚍?wù)的軟件工程、離群檢測、數(shù)據(jù)挖掘

2017-03-21

2017-04-10

重慶市研究生科研創(chuàng)新項(xiàng)目（No.CYS15029）、重慶市基礎(chǔ)科學(xué)與前沿研究計(jì)劃項(xiàng)目（No.cstc2013jcyjA40049）

張浪（1990-），男，江蘇淮安人，碩士研究生，研究方向?yàn)闄C(jī)器學(xué)習(xí)、數(shù)據(jù)挖掘

張程（1977-），男，重慶人，副教授，博士，研究方向?yàn)橐苿又悄堋o線自組網(wǎng)絡(luò)