崔東虎， 趙亞慧， 崔榮一

(延邊大學(xué) 工學(xué)院，吉林 延吉 133002)

0 引言

隨著全球互聯(lián)網(wǎng)絡(luò)的普及以及網(wǎng)絡(luò)信息的海量化，人們對文本自動分類技術(shù)愈加關(guān)注.近年來，基于機器學(xué)習(xí)的文本分類方法因具有人工干預(yù)少、分類速度快和精度高等優(yōu)點而受到學(xué)者們的廣泛關(guān)注[1-2].目前，較為成熟的文本分類方法有K近鄰(K-Nearest Neighbor,KNN)算法[3]、樸素貝葉斯(Naive Bayes,NB)算法、決策樹(Decision Tree, DT)算法、支持向量機(support vector machines, SVM)、深度學(xué)習(xí)模型[4]等，這些模型的主要分類流程為文本信息獲取、分詞處理、特征提取、文本向量表示、算法處理及性能評價[5-6].其中KNN算法雖然具有計算簡單、準(zhǔn)確率高的優(yōu)點[7-8]，但其只適合于描述低維度特征向量間的差異，難以滿足實際需要；而基于深度學(xué)習(xí)的分類模型雖然分類效果較好，但是需要大量的數(shù)據(jù)和訓(xùn)練時間[9-10].為了提高KNN算法在高維特征空間中的效果，本文以單字概率作為文本特征，提出了一種基于相對熵度量文本特征差異的KNN算法，并通過實驗驗證了本文分類方法的有效性.

1 相關(guān)理論

在本文中，文本特征用文字在文本中出現(xiàn)的概率來表示，用相對熵計算兩個樣本之間的概率差異.當(dāng)計算所得的相對熵差值較大時，說明兩個樣本的差異較大；當(dāng)計算所得的相對熵差值較小時，說明兩個樣本間的差異較小[11].

1.1 相對熵

相對熵(亦稱KL散度)雖然不是嚴(yán)格意義上的距離，但是它可以有效描述兩個概率分布之間的差異.設(shè)P(x)和Q(x)是隨機量X的兩個概率分布，則P對Q的相對熵的計算公式[12]為：

(1)

在具體的文本分類問題中，P為訓(xùn)練集文本中每個特征的概率分布，Q為測試集文本中每個特征的概率分布.本文采用式(1)度量樣本間的概率分布差異.

1.2 KNN算法

KNN算法[13]是一種基于實例的學(xué)習(xí)方法，該算法分為訓(xùn)練和分類兩個階段.在訓(xùn)練階段，算法對文本特征進行抽取，并將文本以特征向量的形式定義到實數(shù)域中，即將文本內(nèi)容形式化為向量空間中的點.在分類階段，首先按與訓(xùn)練階段同樣的方法將待分類文本表示為特征向量，然后計算該待分類文本與訓(xùn)練樣本集中每個文本的距離，最后找出與待分類文本最近的K個鄰居，并由這K個鄰居中的多數(shù)類別來決定待分類文本的類別.

KNN算法中的關(guān)鍵步驟是測量樣本間距離.歐氏距離[14]是測量樣本間距離的常用函數(shù)，該函數(shù)雖然具有計算簡單、方便的優(yōu)點，但是隨著特征維度的增加其區(qū)分不同特征的能力逐漸變?nèi)?，同時因值域大的變量在計算中占據(jù)主導(dǎo)作用，因此此時計算出的樣本間距離會出現(xiàn)較大誤差，進而影響分類的準(zhǔn)確率.為了克服歐氏距離的缺點，本文采用相對熵度量樣本之間的差異.

2 分類器設(shè)計

2.1 分類處理流程

本文采用數(shù)據(jù)預(yù)處理、模型訓(xùn)練、分類結(jié)果預(yù)測3個階段進行文本分類.分類的核心思想為：采用相對熵計算測試樣本與訓(xùn)練樣本間的差異，以此找出相對熵最小的K個值，并統(tǒng)計這K個樣本中的多數(shù)類別.主要處理步驟描述如下：

步驟1 構(gòu)造數(shù)據(jù)集.①對收集到的語料進行分字處理，并刪去停用字，以防止文本維度過大而導(dǎo)致計算消耗過大；②將文本向量化，向量的值是各特征字出現(xiàn)的概率；③將數(shù)據(jù)分為訓(xùn)練集和測試集.

步驟2 訓(xùn)練KNN分類器.將所有由特征字概率組成的訓(xùn)練樣本向量組合成矩陣.

步驟3 利用KNN算法對測試集進行分類.①計算測試樣本中各特征字出現(xiàn)的概率，并將測試樣本表示為特征字的概率向量；②計算測試樣本和每個訓(xùn)練集樣本的向量所對應(yīng)的相對熵，并統(tǒng)計相對熵中K個最小的相對熵所對應(yīng)的訓(xùn)練集樣本的類別個數(shù)；③將上述結(jié)果中的多數(shù)類別作為測試樣本的類別.

2.2 文本表示與KNN分類器訓(xùn)練

文本表示方法通常采用向量空間模型.向量空間模型采用TF-IDF方法來計算詞頻矩陣，但當(dāng)文本特征維度較大時，采用TF-IDF方法會導(dǎo)致計算消耗過大，進而會降低分類效率.由于以特征字作為文本特征可以有效減少特征維數(shù)，因此本文選取特征字作為特征，以此計算相對熵.訓(xùn)練樣本集可表示為：

D={(xi,ci)|i=1,2,…,n}.

(2)

測試樣本集可表示為：

Y={(yj)|j=1,2,…,n}.

(3)

由于在一個文本數(shù)據(jù)中可能不會出現(xiàn)字典中的所有字，因此概率矩陣中就有可能出現(xiàn)0.但由于計算相對熵時P或Q的概率不能為0，因此本文采用平滑的方法處理文本，以此避免零概率情況的發(fā)生.文本中的字概率可表示為：

(4)

其中:Pi j為第i個文本中第j個特征字出現(xiàn)的概率，Ni j為第i個文本中第j個特征字出現(xiàn)的次數(shù)，Ni為第i個文本包含的總字?jǐn)?shù)，T為字典總字?jǐn)?shù).第i個文本的特征字概率向量可表示為：

Pi=(Pi 1,Pi 2, …,Pi T)T.

(5)

KNN分類器的訓(xùn)練數(shù)據(jù)可表示為矩陣：

(6)

其中T為特征維數(shù)，n為樣本數(shù)量.式(6)中的每一行表示的是特定文檔的特征字概率行向量.

2.3 分類算法

本文利用相對熵判斷兩個樣本之間的概率差異，并據(jù)此選出特征字概率分布最近的K個文本，具體方法為：

1)在需要分類的文本中，利用式(4)計算出每個字的出現(xiàn)概率，并按式(5)把測試文本d表示為測試向量Pd；

2)計算測試向量Pd與式(6)訓(xùn)練集中每一行之間的相對熵，并將相對熵進行升序排序；

3)根據(jù)給定的K值取K個與測試文本相對熵最小的訓(xùn)練集文本，并統(tǒng)計其中的各類別數(shù)目.

測試樣本類別的表達式為：

(7)

3 實驗結(jié)果與分析

實驗所用的新聞數(shù)據(jù)集來源于搜狗數(shù)據(jù)實驗室的共3 000篇新聞文本，新聞類別分為體育、計算機、經(jīng)濟3類.

3.1 計算文本相似度

由于本文的分類實驗需要使用相對熵來度量文本間的差異，因此在分類前需要計算出測試文本與所有訓(xùn)練集文本之間的相對熵.表1為計算所得的某一測試文本(均包含5個文本)與3個新聞類別間的相對熵.由表1可以看出，測試文本與體育類新聞的相對熵相對最低，由此可判斷出該測試文本應(yīng)為體育類新聞.

表1 測試文本與不同新聞類別間的相對熵

圖1為表1中的測試文本與100個訓(xùn)練集文本間的相對熵的分布情況.從圖1中可以看出，體育類新聞所對應(yīng)的相對熵均低于經(jīng)濟類新聞、計算機類新聞所對應(yīng)的相對熵，由此可進一步判斷出上述測試文本應(yīng)為體育類新聞.

圖1 測試文本與100個訓(xùn)練集文本間的相對熵的分布情況

3.2 分類實驗

分類實驗的步驟為：①計算出測試樣本與所有訓(xùn)練樣本間的相對熵，然后對求出的相對熵進行升序排序；②按照排序結(jié)果找出相對熵最小的K個訓(xùn)練樣本；③統(tǒng)計K個樣本的類別，并根據(jù)公式(7)判斷測試文本的類別.取不同K值時基于相對熵的KNN算法的分類效果如表2所示.由表2可以看出，隨著K值的增大，分類的準(zhǔn)確度、精度、召回率、F1值均呈下降趨勢，所以本文選取K值為1.

表2 K取不同值時的分類效果

3.3 算法驗證

為了進一步驗證基于相對熵的KNN算法的分類效果，本文將該算法與傳統(tǒng)KNN方法(基于特征字概率歐氏距離的KNN算法和基于特征字字頻歐氏距離的KNN算法)、支持向量機(SVM)、決策樹(Decision Tree)、貝葉斯(Bayes)以及循環(huán)神經(jīng)網(wǎng)絡(luò)(RNN)等算法的分類效果進行對比.

1)與基于特征字概率歐氏距離的KNN算法進行對比.訓(xùn)練集為特征字概率矩陣，待分類文本為特征字概率向量.當(dāng)K取不同值時基于特征字概率歐氏距離的KNN算法的分類效果如表3所示.對比表2和表3可知，基于相對熵的KNN算法的分類效果在各指標(biāo)上均顯著優(yōu)于基于特征字概率歐氏距離的KNN算法的分類效果.

表3 K取不同值時基于特征字概率歐氏距離的KNN算法的分類效果

2)與基于特征字字頻歐氏距離的KNN算法進行對比.實驗中將特征字字頻矩陣作為訓(xùn)練集，待分類文本為特征字字頻向量.表4為K取不同值時基于特征字字頻歐式距離的KNN算法的分類效果.對比表4和表2可知，基于相對熵的KNN算法的分類準(zhǔn)確率在各指標(biāo)上依然高于基于特征字字頻歐氏距離的KNN算法的分類效果.

表4 K取不同值時基于特征字字頻歐氏距離的KNN算法的分類效果

3)與SVM、Decision Tree、樸素Bayes算法進行對比.實驗使用特征字字頻作為文本的特征表示.3種算法的分類效果見如表5.對比表5和表2可知，基于相對熵的KNN算法的分類效果最優(yōu).

表5 3種算法的分類效果

4)與RNN算法進行對比.圖2為基于相對熵的KNN算法與RNN算法在不同文本數(shù)據(jù)量時的分類效果.由圖2可以看出：當(dāng)文本數(shù)據(jù)小于2 700個時，基于相對熵的KNN算法的分類效果優(yōu)于RNN算法，并且數(shù)據(jù)量越少，基于相對熵的KNN算法的分類效果就越明顯；當(dāng)文本數(shù)據(jù)大于2 700個時，RNN算法的分類效果優(yōu)于KNN算法的分類效果，并且隨著文本數(shù)據(jù)量的增加，RNN算法分類效果的優(yōu)勢越為明顯.

圖2 基于相對熵的KNN算法與RNN算法在不同文本數(shù)據(jù)量時的分類效果

4 結(jié)論

研究表明，本文提出的基于相對熵的KNN算法的分類效果顯著優(yōu)于基于歐氏距離的KNN算法和SVM、Decision Tree、樸素Bayes算法的分類效果，并且在小樣本的情況下還顯著優(yōu)于RNN算法的分類效果，因此本文方法在文本分類中具有良好的應(yīng)用價值.本文在研究中使用的文本表示方法未能考慮特征間的重要性差異，因此在今后的研究中我們將對重要程度不同的特征進行加權(quán)處理，從而更好地進行文本表示，以提升本文方法的效果.