黃細(xì)鳳

（中國電子科技集團(tuán)公司第十研究所 成都 610036）

1 引言

如何對文本進(jìn)行更高效和準(zhǔn)確的分類是目前計(jì)算機(jī)領(lǐng)域?qū)W者們探究的熱點(diǎn)。隨著網(wǎng)絡(luò)訊息日益增長，對文本分類任務(wù)的性能需求也在不斷提升。就目前而言，廣泛應(yīng)用于文本分類工作的分類方法主要有人工神經(jīng)網(wǎng)絡(luò)［1～2］、KNN［3～5］、決策樹［6～7］、支持向量機(jī)［8～9］以及樸素貝葉斯［10］等。

文本分類的核心思想為通過已知類別的文本，將待分類文本進(jìn)行歸類操作，使其從屬于類別中的某一類或幾類。而KNN 因其算法的理論成熟、易于理解等優(yōu)點(diǎn)，在實(shí)際分類工作中應(yīng)用廣泛。針對傳統(tǒng)KNN 在訓(xùn)練集樣本規(guī)模宏大或樣本維度較高時(shí)計(jì)算開銷巨大的問題，殷亞博等［11］提出了基于卷積神經(jīng)網(wǎng)絡(luò)的文本分類算法CKNN，首先從短文本中獲取更多的抽象特征值，之后再進(jìn)行文本的相關(guān)分類工作。胡元等［12］提出了基于劃分區(qū)域的KNN算法，首先確定待測樣本與各區(qū)域的聯(lián)系密切程度，其次運(yùn)用KNN 對其進(jìn)行相應(yīng)的歸類。張著英等［13］提出了基于粗糙集的KNN 算法，以屬性約簡的方式，對樣本空間中的向量進(jìn)行降維，進(jìn)而提升對文本進(jìn)行歸類的效率。史淼等［14］提出了一種新的分類算法PCA&KNN，采用較小的鄰居集來進(jìn)行KNN 分類，有效降低了分類計(jì)算的復(fù)雜度。譚學(xué)清等［15］提出了一種新判定方式下的KNN 算法，待測樣本所屬類別由其與訓(xùn)練集各類別中所有文本的相似度均值來確定，使時(shí)間復(fù)雜度有效降低，得到一種適合在大數(shù)據(jù)文本分類情況下的分類算法。

可見，對算法的優(yōu)化可以是多方面和多角度的。由此，本文采取將聚類與KNN 相結(jié)合的方式，形成一種新的用來對文本進(jìn)行分類的算法框架，K-medoids［16］由 K-means 優(yōu)化而來，簡單高效且實(shí)用性強(qiáng)，所以，為更好地服務(wù)于后續(xù)相關(guān)分類工作，本文將傳統(tǒng)K-medoids 聚類思想與遺傳算法相融合形成新的聚類方式K-GA-medoids，再將其與KNN 相結(jié)合用于文本分類。經(jīng)驗(yàn)證，本文提出的算法框架能夠在確保分類結(jié)果的精確率的情況下，有效減少計(jì)算開銷。

2 相關(guān)概念

本文主要涉及到的算法有遺傳算法、K-medoids和KNN，下面分別進(jìn)行簡單介紹。

2.1 遺傳算法

遺傳算法基本框架如圖1 所示，首先依據(jù)實(shí)際問題對個(gè)體進(jìn)行編碼表示，再進(jìn)行初始種群集合的隨機(jī)產(chǎn)生，得到多個(gè)初始可行解。種群中所有個(gè)體均有相應(yīng)的適應(yīng)度值，以對其優(yōu)良程度進(jìn)行評價(jià)。根據(jù)選優(yōu)淘劣的準(zhǔn)則，從現(xiàn)有的種群中挑選優(yōu)秀的個(gè)體進(jìn)行后續(xù)的變異、遺傳等操作。對于后續(xù)產(chǎn)生的種群，循環(huán)執(zhí)行選擇、交叉及變異操作，當(dāng)滿足終止條件時(shí)，算法結(jié)束，得到實(shí)際問題的近似最優(yōu)解。

圖1 遺傳算法流程圖

2.2 K-medoids聚類算法

K-medoids 算法在進(jìn)行聚類時(shí)始終選擇最靠近簇心的樣本點(diǎn)作為聚類中心，旨在最大限度降低各種異常點(diǎn)、離群點(diǎn)等對于聚類中心選取的影響。其算法思路：首先選取K 個(gè)初始聚類中心樣本點(diǎn)，剩余樣本則依次歸類于與其距離最近的聚類中心所對應(yīng)的簇。其次，選取非聚類中心樣本點(diǎn)對當(dāng)前聚類中心進(jìn)行替換，根據(jù)替換所需代價(jià)，判別是否更新當(dāng)前聚類中心集合，如此循環(huán)，當(dāng)聚類中心集合不再發(fā)生變化時(shí)，算法收斂。

2.3 KNN算法

KNN 是一種理論成熟且易于理解的分類算法，其核心思想為一個(gè)待分類樣本類別與其K 個(gè)最鄰近樣本組成的樣本集中占比權(quán)重最大的類別相同。即KNN 主要是通過遍歷樣本空間進(jìn)行相似度大小的計(jì)算，得到與待分類文本相距最近的K 個(gè)樣本，再根據(jù)最鄰近的K 個(gè)樣本對其類別進(jìn)行判別的一種算法。

3 算法框架介紹

K-medoids 由K-means 算法優(yōu)化而來，極大降低了噪聲、異常點(diǎn)等對于最終聚類效果的影響，但其對初始聚類中心的選取依舊較為敏感，針對此問題本文將遺傳算法與K-medoids 算法思想相融合，得到新的聚類方式K-GA-medoids，旨在更好地提升前期聚類效果，之后將其與KNN 相結(jié)合，形成一種基于聚類的新的文本分類算法框架，該框架在分類前期對訓(xùn)練樣本集進(jìn)行聚類，在分類階段依據(jù)待分類文本與簇心之間的距離大小來對訓(xùn)練集進(jìn)行縮減，從而克服傳統(tǒng)KNN 算法在樣本規(guī)模較大的情況下，分類效率將嚴(yán)重下降，缺乏有效性的問題。

3.1 K-GA-medoids算法

K-GA-medoids 由遺傳算法與K-medoids 聚類核心思想相融合而成，在遺傳算法的適應(yīng)度函數(shù)設(shè)計(jì)部分融合K-medoids 尋找簇內(nèi)中心點(diǎn)的思想，以距離作為適應(yīng)度函數(shù)設(shè)定的核心，旨在通過遺傳迭代找出更靠近簇心的聚類中心點(diǎn)集合，具體如下：

其中，Ci為聚類結(jié)果的第i個(gè)簇，Ni是第i個(gè)簇的大小，Mi表示簇心，|P-Mi|是樣本P到簇心Mi的距離，Si為第i個(gè)簇內(nèi)所有樣本點(diǎn)到簇心的距離的平均值。

K為當(dāng)前簇心選取個(gè)數(shù)，F(xiàn)it為當(dāng)前個(gè)體適應(yīng)度值，由式（2）可知，F(xiàn)it值越小，聚類效果越好，二者定義為反相關(guān)的關(guān)系。

算法迭代前首先隨機(jī)生成一定數(shù)目可行解的集合作為種群初代，根據(jù)適應(yīng)度函數(shù)對本代種群中的個(gè)體進(jìn)行優(yōu)良程度的判定，其次對本代種群中的個(gè)體執(zhí)行相應(yīng)遺傳操作，以保證種群的不斷進(jìn)化和擴(kuò)展，為尋找更優(yōu)的可行解提供選擇，具體流程如下：

1）設(shè)置參數(shù)：聚類中心個(gè)數(shù)K，初始種群大小N，選擇存優(yōu)比例p1，交叉概率p2，變異概率p3，最大迭代次數(shù)T，種群平均適應(yīng)度變化閾值ε；

2）種群初始化：依據(jù)K值對初代個(gè)體進(jìn)行編碼，得到種群規(guī)模為N的初始群體；

3）根據(jù)式（2）對當(dāng)代個(gè)體進(jìn)行優(yōu)良程度的判定，并保留迄今為止最優(yōu)個(gè)體；

4）根據(jù)3）的判定結(jié)果以及參數(shù)p1、p2、p3對種群個(gè)體執(zhí)行相應(yīng)遺傳操作，得到一輪迭代后新一代的種群；

5）判斷當(dāng)代種群平均適應(yīng)度值與父代相比差值是否小于閾值ε，若符合，則算法終止，輸出結(jié)果；否則，轉(zhuǎn)向第3）步。

3.2 基于K-GA-medoids聚類樣本縮減

在運(yùn)用KNN 算法對文本進(jìn)行歸類時(shí)，采用距離公式得到的K 個(gè)最鄰近文本正常來說與待測文本的類別同屬或接近，若尋找最鄰近文本過程中盡可能的在待測文本本身所屬類別或周圍類別樣本集中進(jìn)行搜尋，則可極大減少計(jì)算開銷。對樣本集的縮減力度較大時(shí)，在分類效率得到提升的同時(shí)分類結(jié)果的準(zhǔn)確率必然會(huì)受到一定程度的影響而有所下降，縮減力度較小時(shí)則對分類效率的提升并不明顯。針對此問題，本文在準(zhǔn)確率與計(jì)算開銷之間進(jìn)行了折中考慮，提出了基于K-GA-medoids 聚類的樣本縮減方法。

定義訓(xùn)練樣本集為S，包含C1、C2，C3，…，Cm共m個(gè)類別M個(gè)文本。在分類前首先采用K-GA-medoids 算法將其劃分為n個(gè)簇，Oi表示對應(yīng)簇的簇心(0 ＜i≤n)，樣本之間的相似度距離定義為D(si，sj)，縮減步驟描述如下。

1）設(shè)定K-GA-medoids 相應(yīng)參數(shù)，首先對訓(xùn)練樣本集S執(zhí)行聚類操作，將其劃分為指定的n個(gè)簇，之后對每個(gè)待測文本d執(zhí)行如下2、3、4）操作；

2）計(jì)算d與Oi(0 ＜i≤n)之間的相似度距離大小，遍歷簇心進(jìn)行計(jì)算并記錄最大距離Dmax及最小距離Dmin；

3）折中計(jì)算獲取待測文本d的樣本縮減度量距離Dend=(Dmax+Dmin)/2；

4）定義當(dāng)前待測文本d縮減后訓(xùn)練集為Snew，若d與Oi的相似度距離Di≤Dend，則說明d與Oi對應(yīng)簇內(nèi)的文本較為相似，將其內(nèi)文本納入Snew，否則，將對應(yīng)簇予以舍棄。

3.3 改進(jìn)聚類與KNN結(jié)合的算法框架

在進(jìn)行正式KNN 分類工作之前，采用K-GA-medoids算法對訓(xùn)練樣本集進(jìn)行聚類得到多個(gè)簇，在分類階段，根據(jù)各待測文本與各簇心之間的相似度距離大小獲取對應(yīng)樣本縮減度量距離，從而縮減訓(xùn)練集，減少計(jì)算開銷。相應(yīng)算法框架流程及圖示如下。

1）讀取訓(xùn)練集及測試集樣本數(shù)據(jù)，本文所涉及數(shù)據(jù)均為英文文本，對其進(jìn)行分詞、去停用詞以及統(tǒng)計(jì)詞頻工作；

2）采用TF-IDF計(jì)算方法來計(jì)算各個(gè)特征詞的權(quán)重大小，得到未降維的文本向量；

3）采用信息增益方法對文本特征向量進(jìn)行降維，保留增益值較大的特征項(xiàng)；

4）對訓(xùn)練空間中的文本向量執(zhí)行K-GA-medoids聚類操作，將其劃分為內(nèi)聚度較高的多個(gè)簇；

5）對于測試空間中的每個(gè)待測文本d，采用3.2 節(jié)樣本縮減方法對訓(xùn)練空間進(jìn)行縮減，得到與其對應(yīng)的新的訓(xùn)練空間Snew；

6）采用KNN 算法對待測文本d進(jìn)行分類，在Snew中查找其K 個(gè)最鄰近樣本，并將d歸屬于占比權(quán)重最大的樣本類別。

圖2 分類算法框架流程圖

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

本節(jié)所有實(shí)驗(yàn)均是在配置2.20GHz Intel Core i5、8GB 內(nèi)存的 PC 上進(jìn)行，操作系統(tǒng)為 Win7，算法程序采用Python 語言進(jìn)行編寫，在Python3 中編程實(shí)現(xiàn)。實(shí)驗(yàn)結(jié)果所涉及到的評價(jià)指標(biāo)包括精確率（precision）、召回率（recall）以及F 值，相應(yīng)計(jì)算公式定義如下：

其中TP表示預(yù)測為正且實(shí)際為正的數(shù)目，F(xiàn)N表示預(yù)測為負(fù)但實(shí)際為正的數(shù)目，F(xiàn)P表示預(yù)測為正但實(shí)際為負(fù)的數(shù)目。

4.1 K-GA-medoids聚類效果分析

為驗(yàn)證K-GA-medoids 聚類的有效性，本文將對K-medoids 和K-GA-medoids 在同等數(shù)據(jù)集上做實(shí)驗(yàn)對比。實(shí)驗(yàn)采用的是經(jīng)典的文本聚類集合mini_newsgroups，共包括 20 個(gè)大類共計(jì) 2000 個(gè)數(shù)據(jù)文本。在實(shí)驗(yàn)前，對文本執(zhí)行預(yù)處理操作，包括去停用詞、TF-IDF 權(quán)重計(jì)算、特征選擇等，進(jìn)而得到文本特征矩陣。最后針對不同測試集Group 在K-medoids 和K-GA-medoids 算法上進(jìn)行實(shí)驗(yàn)。本實(shí)驗(yàn)相關(guān)參數(shù)設(shè)置如下：初始種群規(guī)模N為測試集總數(shù)的0.1，選擇存優(yōu)比例p1為0.1，交叉概率p2為0.6，變異概率p3為0.1，最大迭代次數(shù)T為300，種群平均適應(yīng)度變化閾值ε為0.05，實(shí)驗(yàn)測試集相關(guān)說明及具體實(shí)驗(yàn)結(jié)果如下。

表1 測試集說明及聚類實(shí)驗(yàn)數(shù)據(jù)

圖3 聚類效果F值對比

以上實(shí)驗(yàn)所得數(shù)據(jù)均為多次實(shí)驗(yàn)求得的均值，由結(jié)果可知，K-GA-medoids 算法在聚類效果的精確率、召回率及F 值上較一般K-medoids 算法均有較為明顯提升，五次實(shí)驗(yàn)F值平均提升2.94%，在進(jìn)行文本聚類時(shí)表現(xiàn)更佳，說明本文將GA 與K-medoids 算法思想相融合衍生出的全新聚類方法K-GA-medoids在實(shí)際應(yīng)用中是客觀有效的。

4.2 文本分類算法框架效果分析

為驗(yàn)證本文算法框架的有效性，本節(jié)將其與傳統(tǒng)KNN 算法在相同數(shù)據(jù)集上進(jìn)行實(shí)驗(yàn)對比。由于mini_newsgroups數(shù)據(jù)集單個(gè)類別樣本數(shù)較少，無法較好的保證分類工作前期訓(xùn)練集的多樣和全面性，所以本小節(jié)實(shí)驗(yàn)數(shù)據(jù)集采用網(wǎng)絡(luò)爬取的5 類新聞文本數(shù)據(jù)，測試時(shí)將其劃分為不同的測試集Group，K-GA-medoids算法參數(shù)設(shè)定同4.1節(jié)，實(shí)驗(yàn)測試集相關(guān)說明及具體實(shí)驗(yàn)結(jié)果如下所示。

表2 測試集說明及分類實(shí)驗(yàn)數(shù)據(jù)

圖4 分類效果P值對比

由以上圖表可得，本文算法框架較傳統(tǒng)KNN算法而言，在5個(gè)測試集實(shí)驗(yàn)中，精確率P值同比平均增長1.72%，文本分類效率平均提升7.29%，說明本文提出的算法框架在保證分類精確率有所提升的前提下，有效加快了文本的分類效率，較傳統(tǒng)KNN 算法而言，在分類效果上表現(xiàn)更佳，具備優(yōu)越性。

5 結(jié)語

本文針對KNN 在進(jìn)行文本分類時(shí)，需遍歷樣本空間做相似度計(jì)算，導(dǎo)致計(jì)算開銷巨大的問題，提出采用聚類算法與KNN 相結(jié)合的方式形成新的文本分類算法框架，目的在于對訓(xùn)練樣本集進(jìn)行合理的縮減以降低計(jì)算開銷。與此同時(shí)，為更好地提升前期對于訓(xùn)練集文本的聚類效果，本文將遺傳算法與K-medoids 算法思想相融合，形成新的聚類算法K-GA-medoids，實(shí)驗(yàn)表明，其聚類效果較傳統(tǒng)K-medoids而言有較為明顯提升，將其與KNN 相結(jié)合形成的分類算法框架在分類表現(xiàn)上較KNN 算法而言更佳且效率更高。但是對樣本集進(jìn)行縮減的方式也不可避免地造成了樣本信息的損失，所以如何更有效地對訓(xùn)練集樣本進(jìn)行縮減仍是我們今后需要進(jìn)行探索和研究的方向。