文 武，李培強(qiáng)

(1.重慶郵電大學(xué) 通信新技術(shù)應(yīng)用研究中心，重慶 400065；2.重慶信科設(shè)計(jì)有限公司，重慶 400065)

0 引 言

目前文本分類[1]的方法大多是基于統(tǒng)計(jì)學(xué)習(xí)的，運(yùn)用機(jī)器學(xué)習(xí)領(lǐng)域的分類模型進(jìn)行自動(dòng)分類[2]，常用分類模型有：Rocchio算法[3]、樸素貝葉斯(NB)[4]、支持向量機(jī)(SVM)[5]、K近鄰(KNN)[6]等。其中對(duì)KNN算法來(lái)說(shuō)，由于其理論成熟，思想簡(jiǎn)單，而且對(duì)數(shù)據(jù)沒(méi)有假設(shè)，準(zhǔn)確度高，在文本分類領(lǐng)域得到了廣泛的應(yīng)用。Nirmala Devi M等[7]提出了一種將利用K-means算法去除不完整和模糊數(shù)據(jù)的方法，以此來(lái)提高分類的準(zhǔn)確率和效率。張雪萍等[8]將K-Medoids與MapReduce平臺(tái)相結(jié)合來(lái)提高文本的分類速率，提高了文本的分類效率。羅賢鋒等[9]提出了一種基于K-Medoids聚類的樣本裁剪方法，先通過(guò)K-Medoids算法對(duì)文本聚類，并通過(guò)計(jì)算每個(gè)樣本的相似度與閥值對(duì)比，如果相似度小于設(shè)定閥值，則將該文本直接刪除，然后運(yùn)用KNN算法對(duì)待測(cè)樣本進(jìn)行判別，提高了分類速率。謝娟英等[10]提出了基于K近鄰的密度峰值的搜索分類算法，通過(guò)搜索和發(fā)現(xiàn)樣本的密度峰值，以峰值點(diǎn)樣本作為初始類簇中心，最終利用K近鄰算法對(duì)待測(cè)文本進(jìn)行分類，提高了文本分類的準(zhǔn)確性。黃賢英等[11]提出了利用文本詞性相似度和KNN算法結(jié)合的方法對(duì)文本數(shù)據(jù)進(jìn)行分類，通過(guò)對(duì)文本數(shù)據(jù)詞性相似度的計(jì)算，分給每個(gè)詞性信息的不同的權(quán)重值，最后利用KNN算法對(duì)待測(cè)文本類別進(jìn)行判斷，提高了短文本分類的準(zhǔn)確率。

從上述研究發(fā)現(xiàn)，現(xiàn)在部分分類算法主要是利用文本相似度或者結(jié)合某種平臺(tái)進(jìn)行文本分類，只是單一考慮了文本分類的準(zhǔn)確率，沒(méi)有同時(shí)顧及到文本分類的準(zhǔn)確率和分類速率?；诖耍疚脑趥鹘y(tǒng)的KNN算法的基礎(chǔ)上，提出基于K中心點(diǎn)和粗糙集的KNN文本分類算法。該算法的主要思想是：首先通過(guò)K中心點(diǎn)算法對(duì)文本數(shù)據(jù)進(jìn)行聚類，然后利用粗糙集理論對(duì)已分類的簇集進(jìn)行分割，得到上下近似集和邊界區(qū)域近似集，僅對(duì)分割得到的邊界區(qū)域數(shù)據(jù)通過(guò)KNN算法進(jìn)行判斷最終的所屬類別，并對(duì)無(wú)用信息進(jìn)行了篩選，這樣不僅大大減少了文本的計(jì)算量，提高了文本分類速率，同時(shí)也保證了文本分類的準(zhǔn)確率。

1 相關(guān)工作

1.1 K最近鄰算法

K近鄰算法(K-nearest neighbor，KNN)是分類算法中的一種，是基于空間向量模型[12](VSM)的分類算法之一。KNN通過(guò)計(jì)算待測(cè)樣本數(shù)據(jù)與訓(xùn)練樣本數(shù)據(jù)中不同類別數(shù)據(jù)點(diǎn)間的相似度，然后根據(jù)相似度大小對(duì)待測(cè)樣本進(jìn)行分類。即通過(guò)與待測(cè)樣本點(diǎn)最鄰近的K個(gè)樣本點(diǎn)來(lái)對(duì)待測(cè)樣本進(jìn)行分類和預(yù)測(cè)。對(duì)一文本訓(xùn)練集S，該訓(xùn)練集有m個(gè)類別，S的總文本數(shù)為N。C1,C2，…,CN，S的總文本數(shù)為N。在訓(xùn)練階段對(duì)訓(xùn)練集S進(jìn)行分詞降維，然后將訓(xùn)練集文本表示為特征向量：Di={X1，X2，…,Xn}T(0

KNN算法的具體步驟可描述為：

(1)對(duì)文本訓(xùn)練集進(jìn)行分詞。

(2)提取特征詞并降維。

(3)利用VSM將訓(xùn)練樣本向量化。

(4)對(duì)待測(cè)文本進(jìn)行(1)～(3)處理。

(5)利用余弦相似度公式計(jì)算待測(cè)文本與訓(xùn)練文本的相似度，公式為

(1)

(6)選出與待測(cè)文本D相似度最大的K個(gè)文本組成樣本集。

(7)根據(jù)(6)中得到的K個(gè)最近鄰樣本集，計(jì)算測(cè)試樣本D屬于每個(gè)類別Cm的權(quán)重W，計(jì)算過(guò)程如公式所示

(2)

其中，類別屬性函數(shù)如公式所示

(3)

(8)將待測(cè)樣本D歸入到權(quán)重最大的類別Cm中。

1.2 K中心點(diǎn)樣本剔除算法

在文本分類中，當(dāng)對(duì)較大的數(shù)據(jù)樣本進(jìn)行聚類時(shí)，傳統(tǒng)的聚類算法如K-Means算法雖然聚類精度高，但只能在簇的平均值確定的情況下才能使用，而且通過(guò)均值得到的中心點(diǎn)存在偏差，準(zhǔn)確性較低[13]。而K中心點(diǎn)算法[14]不采用簇中對(duì)象的平均值作為參照點(diǎn)，而是選用簇中位置最中心的對(duì)象，即中心點(diǎn)作為參照點(diǎn)，在分類過(guò)程中具有較強(qiáng)的魯棒性。

K中心點(diǎn)算法的主要思想是：對(duì)于樣本訓(xùn)練集S，首先將其劃分K個(gè)不同的類簇，為每個(gè)簇隨機(jī)選擇選擇一個(gè)樣本對(duì)象作為初始簇心Oi(0

(4)

1.3 粗糙集理論

粗糙集(rough set)理論是波蘭學(xué)者Z.Pawlak提出的處理模糊不清和不確定性問(wèn)題的新型數(shù)學(xué)理論。該理論能夠在浩瀚的數(shù)據(jù)中找出有用的信息,將信息去粗取精,在縮減計(jì)算量的同時(shí),也能提高分類的準(zhǔn)確率,這也是本文選用粗糙集理論來(lái)進(jìn)行文本分類的價(jià)值所在，具體粗糙集理論請(qǐng)參見文獻(xiàn)[15]。

定義IND(P)是數(shù)據(jù)庫(kù)P=(U,R)中所有等價(jià)關(guān)系的簇，對(duì)于一個(gè)子集對(duì)象集合X?U和等價(jià)關(guān)系R?IND(P),可得出集合X關(guān)于等價(jià)關(guān)系R的下近似集R下(X)和上近似集R上(X)的定義分別為式(5)和式(6)所示

R下(X)=U{Y?U/R|Y?X}

(5)

R上(X)=U{Y?U/R|Y∩X≠φ}

(6)

其中，下近似集R下(X)表示由關(guān)系R得出的U中一定屬于集合X的所有對(duì)象的集合；上近似集R上(X)表示由關(guān)系R得出的U中可能屬于集合X的所有對(duì)象的集合。下近似集R下(X)和上近似集R上(X)可以定義3個(gè)概念，即集合X的正域、負(fù)域和邊界域，計(jì)算公式分別為式(7)～式(9)所示

POSR(X)=R下(X)

(7)

NEGR(X)=U-R下(X)

(8)

BNR(X)=R上-R下

(9)

其中，正域POSR(X)即下近似集R下(X)；負(fù)域NEGR(X)表示在U中肯定不屬于集合X的所有對(duì)象集合；邊界域BNR(X)表示在U中不能明確判斷是否一定屬于或者一定不屬于集合X的所有對(duì)象集合。

2 KRS-KNN文本分類算法

2.1 模型表示-向量空間模型(VSM)

空間向量模型(vector space model，VSM)，VSM是一種簡(jiǎn)便、高效的文本表示模型[16]。VSM的關(guān)鍵在于怎樣選取較大相似度的特征詞和有效的計(jì)算權(quán)重值。在向量空間模型中，一篇文檔由提取出的特征詞和該詞權(quán)重由向量的形式表示出來(lái)，權(quán)重的大小，反映了特征詞在一篇文檔中的地位；而在分類階段之前，一個(gè)文檔數(shù)據(jù)集的類別都是由帶有權(quán)重的特征詞所表示。本文采用權(quán)重計(jì)算公式TF-IDF[17](term frequency-inverse document frequency)，在文本分類中TF-IDF是一種經(jīng)典的特征詞權(quán)重值計(jì)算方法，且一直受到人們歡迎。

根據(jù)TF-IDF的基本思想，在待測(cè)文本D中，特征詞ti的權(quán)重計(jì)算公式如公式所示

(10)

(11)

其中，特征詞ti在文檔中出現(xiàn)的頻率用tfi表示，訓(xùn)練集中所有文檔的數(shù)目用N表示，包含特征詞ti的文檔出現(xiàn)的頻率用dfti表示。

2.2 KRS-KNN算法

KRS-KNN算法的主要思想是：對(duì)于一批新的文本數(shù)據(jù)，首先對(duì)該數(shù)據(jù)集進(jìn)行預(yù)處理，利用K中心點(diǎn)算法算法對(duì)其進(jìn)行聚類，然后調(diào)用粗糙集理論聚類的簇集進(jìn)行上下分割，根據(jù)粗糙集理論的判斷原理對(duì)分割得到的數(shù)據(jù)進(jìn)行判斷，對(duì)于邊界區(qū)域的文本數(shù)據(jù)需要通過(guò)KNN算法進(jìn)一步判斷其所屬類別。KRS-KNN算法的分類流程如圖1所示。

圖1 KRS-KNN算法分類流程

(1)首先將數(shù)據(jù)集分為測(cè)試集和訓(xùn)練集，并采用中科院分詞系統(tǒng)ICTCLAS對(duì)中文文檔進(jìn)行分詞、去停用詞。

(2)采用文檔頻率方法對(duì)特征降維。

(3)利用TF-IDF權(quán)重公式計(jì)算特征詞的權(quán)重值，進(jìn)而由VSM對(duì)特征詞向量化。

(4)將(3)中處理過(guò)的數(shù)據(jù)集通過(guò)K中心點(diǎn)算法對(duì)其聚類為簇，并將最后每個(gè)簇類中心的代價(jià)值設(shè)為閥值Ei。

(5)將(4)中每個(gè)簇類的非簇心樣本計(jì)算它們?cè)诟髯灶惔氐南喈惗炔⑴c最后設(shè)定的閥值比較，將相異度大于閥值的數(shù)據(jù)樣本點(diǎn)從其所屬類別中剔除。

(6)對(duì)于(5)中得到的每個(gè)簇，通過(guò)式(5)、式(6)分別計(jì)算這些簇的上下近似集，并運(yùn)用式(7)、式(8)、式(9)計(jì)算每簇的正域、負(fù)域和邊界域。

(7)對(duì)于已經(jīng)分割好的簇，根據(jù)粗糙集理論判斷數(shù)據(jù)樣本i屬于哪一域。

1)如果數(shù)據(jù)樣本i出現(xiàn)在K-Medoids類簇正域即下近似集，則該樣本一定屬于該類簇，無(wú)需再判斷。

2)如果數(shù)據(jù)樣本i出現(xiàn)在K-Medoids類簇負(fù)域，則直接將數(shù)據(jù)樣本i從其所屬類簇中刪除。

3)如果數(shù)據(jù)樣本i出現(xiàn)在K-Medoids類簇邊界，則轉(zhuǎn)到步驟(8)執(zhí)行。

(8)運(yùn)用式(1)計(jì)算數(shù)據(jù)樣本i與K-Medoids的簇類中心Oi的余弦相似度，并有相似度大小計(jì)算出數(shù)據(jù)樣本i與所有類簇中心Oi的K個(gè)最近鄰。

(9)根據(jù)數(shù)據(jù)對(duì)象i的K個(gè)最近鄰，由式(2)計(jì)算待測(cè)文本數(shù)據(jù)對(duì)象i屬于K-Medoids類簇的權(quán)重W，并將數(shù)據(jù)樣本i分到權(quán)重最大的類別Cm中。

KRS-KNN算法的優(yōu)勢(shì)：在基于K-Medoids算法的基礎(chǔ)上，保證了文本分類的準(zhǔn)確性，將代價(jià)值較大的數(shù)據(jù)樣本剔除降低了文本的數(shù)據(jù)規(guī)模，減少了計(jì)算量，同時(shí)在運(yùn)用粗糙集理論時(shí)對(duì)已經(jīng)確定類別的數(shù)據(jù)樣本不再對(duì)其判斷其所屬類別再一次減少了文本數(shù)據(jù)的計(jì)算規(guī)模，縮減了文本的處理的計(jì)算時(shí)間，有效提高了文本的分類效率。

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

3.1 實(shí)驗(yàn)環(huán)境與評(píng)估指標(biāo)

針對(duì)提出的KRS-KNN文本分類算法進(jìn)行了實(shí)驗(yàn)驗(yàn)證，本實(shí)驗(yàn)平臺(tái)采用Windows 7 64位操作系統(tǒng)、CPU為Intel(R)-i5-4210M-2.6 GHz、物理內(nèi)存為4 G和Eclipse集成開發(fā)環(huán)境，實(shí)驗(yàn)數(shù)據(jù)來(lái)自于搜狗實(shí)驗(yàn)室，選取其分類語(yǔ)料庫(kù)的標(biāo)準(zhǔn)數(shù)據(jù)集-SogouC作為樣本數(shù)據(jù)，其中包括財(cái)經(jīng)、互聯(lián)網(wǎng)、健康、教育、軍事、旅游、體育、文化、招聘9個(gè)類別，各1990篇共17 910篇文檔。對(duì)分類效果的評(píng)價(jià)采用精確率(precision)、召回率(recall)和綜合評(píng)價(jià)指標(biāo)(F1-measure)。定義如下

(12)

(13)

(14)

其中，TP表示分類時(shí)將正類預(yù)測(cè)為正類的數(shù)目，F(xiàn)N表示將正類預(yù)測(cè)為負(fù)類數(shù)，F(xiàn)P將負(fù)類預(yù)測(cè)為正類數(shù)，TN為將分類預(yù)測(cè)為負(fù)類數(shù)，精確率衡量的是類別的查準(zhǔn)率，召回率衡量的是類別的查全率，F(xiàn)1-measure對(duì)查準(zhǔn)率、召回率進(jìn)行綜合考察，以及對(duì)它們的偏向程度，且F1綜合了P和R的結(jié)果，所以當(dāng)F1越高則越能說(shuō)明實(shí)驗(yàn)方法比較有效，和分類器具有較強(qiáng)的分類能力。

3.2 K值的確定

K值的大小對(duì)分類準(zhǔn)確率和分類速率的有較大影響，為保證分類器具有最大的分類能力，對(duì)K值的選取進(jìn)行了實(shí)驗(yàn)。在文獻(xiàn)[18]中，先設(shè)定K值為9依次遞增來(lái)選取最優(yōu)，最后通過(guò)平均值來(lái)確定K值，本文通過(guò)交叉驗(yàn)證的方法得出由最優(yōu)K值，同時(shí)F1值綜合了精確率、召回率，所以本文選取F1值與K值的關(guān)系進(jìn)行實(shí)驗(yàn)驗(yàn)證。

由圖2可以看出F1值與K值選取的關(guān)系：

(1)當(dāng)0

(2)當(dāng)K≥20時(shí)，F(xiàn)1值隨著K值的遞增而降低。

由此次實(shí)驗(yàn)結(jié)果可以得出最優(yōu)K值，即K值取19時(shí)，分類器的分類效果最優(yōu)。

圖2 K值與F1值關(guān)系

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

為驗(yàn)證本文提出的KRS-KNN算法的有效性，在保證同樣數(shù)據(jù)集的情況下進(jìn)行了10次實(shí)驗(yàn)，與傳統(tǒng)的KNN分類算法和基于K-Medoids聚類改進(jìn)的KNN文本分類算法進(jìn)行了比較，表1給出了在同一數(shù)據(jù)集下3種不同算法分類耗時(shí)時(shí)間。利用式(12)、式(13)、式(14)分別計(jì)算出精確率、召回率和F1值，見表2。

通過(guò)表1可以看出在同一數(shù)據(jù)集下提出的KRS-KNN算法的時(shí)間消耗比傳統(tǒng)的KNN算法和基于K-Means的KNN算法要少的多，與傳統(tǒng)的KNN算法相比平均減少了274 s，與基于K-Means的KNN算法相比均值上減少了116 s，發(fā)現(xiàn)提出的KRS-KNN算法與基于K-Means的KNN算法時(shí)間減少的幅度沒(méi)有比傳統(tǒng)的KNN算法的大，這是因?yàn)樵诰垲愅瓿珊鬄榱吮ＷC分類的準(zhǔn)確性，在粗糙集上下割分時(shí)還需要對(duì)樣本對(duì)象進(jìn)行類別的劃分，區(qū)分樣本對(duì)象的正負(fù)域和計(jì)算邊界域，這需要消耗一定時(shí)間，但從總體上來(lái)說(shuō)分類速率得到了明顯的提升，說(shuō)明了本文提出的算法的有效性。

表1 3種算法的消耗時(shí)間對(duì)比

從表2對(duì)3種算法進(jìn)行對(duì)比可以看出，KRS-KNN分類算法在精確率、召回率、F1值上都有明顯的提升。其中，提出的KRS-KNN算法相比于傳統(tǒng)的KNN算法和基于K-Means的KNN算法分別在準(zhǔn)確率上平均提高了4.19%、3.36%，除了在軍事、體育、財(cái)經(jīng)少數(shù)類別上，召回率都得到了提高，平均值上相比于其它兩個(gè)算法召回率分別提高了1.74%和3.06%。從F1值上來(lái)看，KRS-KNN算法在財(cái)經(jīng)上比傳統(tǒng)的KNN算法降低了0.57%,在文化上降低了9.63%，這主要是因?yàn)槲幕?、?cái)經(jīng)類內(nèi)容廣泛，特征詞權(quán)重值相差無(wú)幾不易于區(qū)分，而體育類則內(nèi)容相對(duì)集中，具有較高的區(qū)分度，所以相比于兩個(gè)算法KRS-KNN算法在體育類的F1值上提升效果明顯，但從總體上來(lái)說(shuō)F1值相比于其它兩個(gè)算法來(lái)說(shuō)都得到了一定提高，分別提高了0.15%、1.43%，總體上提高了文本的分類效率。

表2 實(shí)驗(yàn)結(jié)果對(duì)比

4 結(jié)束語(yǔ)

本文針對(duì)KNN算法在文本分類中，分類效率受計(jì)算相似度時(shí)間消耗大導(dǎo)致分類效率低下的問(wèn)題，提出了基于K-Medoids和粗糙集的KRS-KNN文本分類算法。該算法首先通過(guò)K-Medoids算法對(duì)文本數(shù)據(jù)集聚類成簇，然后利用粗糙集理論對(duì)已分好的簇進(jìn)行上下近似分割，對(duì)分割得到的類簇進(jìn)行判斷處理，最后利用KNN算法對(duì)處理后的樣本數(shù)據(jù)做最后的類別判斷。通過(guò)實(shí)驗(yàn)結(jié)果可知本文提出的KRS-KNN算法在保證較高的準(zhǔn)確性和魯棒性前提下，能有效提高分類模型對(duì)文本數(shù)據(jù)的分類效率。然而，通過(guò)對(duì)比實(shí)驗(yàn)發(fā)現(xiàn)，分類效率雖然能得到有效提高，但在對(duì)數(shù)據(jù)對(duì)象運(yùn)用代價(jià)函數(shù)對(duì)相異度較大的數(shù)據(jù)樣本剔除和利用粗糙集理論進(jìn)行數(shù)據(jù)處理時(shí)，會(huì)導(dǎo)致一定的數(shù)據(jù)信息丟失，怎樣在保證數(shù)據(jù)信息不丟失的情況下更有效地提高文本分類速率是下一步的工作重點(diǎn)。