基于相對熵的KNN文本分類方法的研究

崔東虎， 趙亞慧， 崔榮一

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

0 引言

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

1 相關理論

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

1.1 相對熵

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

(1)

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

1.2 KNN算法

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

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

2 分類器設計

2.1 分類處理流程

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

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

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

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

2.2 文本表示與KNN分類器訓練

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

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

(2)

測試樣本集可表示為：

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

(3)

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

(4)

其中:Pi j為第i個文本中第j個特征字出現的概率，Ni j為第i個文本中第j個特征字出現的次數，Ni為第i個文本包含的總字數，T為字典總字數.第i個文本的特征字概率向量可表示為：

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

(5)

KNN分類器的訓練數據可表示為矩陣：

(6)

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

2.3 分類算法

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

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

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

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

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

(7)

3 實驗結果與分析

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

3.1 計算文本相似度

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

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

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

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

3.2 分類實驗

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

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

3.3 算法驗證

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

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

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

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

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

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

表5 3種算法的分類效果

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

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

4 結論

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