基于改進ML-KNN算法的文本分類研究

邢娟韜 白金牛

摘? 要：由于傳統ML-KNN算法數據集中每個特征具有相同權重，與事實上的不同特征具有不同權重相違背，故提出對ML-KNN算法的改進，用ML-KNN來構建分類模型進行分類。為驗證該算法的分類效果，選取算法常用的衡量標準與其他兩種算法比較，結果表明由改進ML-KNN算法構造的模型要優于其他兩種算法，能有效表達多領域數據集分類問題，算法效果更好。

關鍵詞：多標記學習;ML-KNN;最近鄰;聚類;距離權重

中圖分類號：TP311? ? ? ? ?文獻標志碼：A? ? ? ? ?文章編號：2095-2945（2020）09-0025-03

Abstract： Because each feature in the data set of the traditional ML-KNN algorithm has the same weight， which is contrary to the fact that different features have different weights， an improvement to the ML-KNN algorithm is proposed， which uses ML-KNN to build a classification model for classification. In order to verify the classification effect of the algorithm， the commonly used criteria of the algorithm are compared with the other two algorithms. The results show that the model constructed by the improved ML-KNN algorithm is better than the other two algorithms， and can effectively express the classification problem of multi-domain data sets， and the effect of the algorithm is better.

Keywords： multi-marker learning; ML-KNN; nearest neighbor; clustering; distance weight

1 概述

傳統的單標記分類任務是將一個樣本映射到單個類別標簽L（L=1）中;當L=2，該分類問題就是“二類分類”;當L>2，該分類就是“多類分類”，也稱為多標記分類問題[1-2]。該方法已應用到很多新的領域，如音樂分類[3]、蛋白質功能分類[4]、Web挖掘[5]以及圖像和視頻的語義分類[6-9]。ML-KNN（Multi-Label K-Nearest Neighbor）就是典型的多標簽分類算法。在ML-KNN算法中的數據集，每個特征具有相同的特征權重。事實上，對于數據集中的每一個樣本，它的k個近鄰的標簽集合理論上應該跟它自身的標簽集合有一定程度上的相似，這種相似度會隨著近鄰到樣本距離的改變而改變，而且距離大，相似度越小。故不同特征所承擔不同權重，ML-KNN算法并沒有講這一問題，故提出對ML-KNN算法的改進。

2 方法描述

2.1 ML-KNN算法

ML-KNN算法思想：給定一個分類預測點x，計算預測點到訓練數據集中所有點的距離。采用交叉驗證方法得到最優K值，結合貝葉斯方法并運用最大化后驗概率，由式（1）得到預測點x的預測結果Y。

2.2 改進ML-KNN算法

基于上文提出的ML-KNN算法弊端，利用權重來解決這一問題。提出新的分類函數：

其中：w表示由x的最近鄰到x的距離所轉換而來的權重，也是x的最近鄰在本文改進算法中的權重;1-w則表示x的k個近鄰的權重;NNx（li）表示x的最近鄰樣本是否含有li標簽，可能為0可能為1。w取最合適的高斯函數：w=a？鄢e■，a和c是常數;d表示歐式距離。算法具體步驟如下：

輸入：訓練數據集、測試數據集。

輸出：分類結果。

（1）利用k-means聚類算法將訓練數據和測試數據分別分為r（R1，R2，...Rr）個聚類中心，t（T1，T2，...，Tr）個聚類中心;

（2）計算Ti到Rj的歐式距離D（Ti，Rj），其中i=1，2，...，t，j=1，2，...，r;

（3）取2步驟中最短的歐式距離記為Rj，其中j=1，2，...，r;

（4）將Ti對應的簇作為新的測試集，記為NewY;

（5）將3步得到的Rj對應的簇作為新的訓練數據，記為NewX;

（6）對于每一個xu∈NewX，計算每一個li∈L的先驗概率：

（7）采用交叉驗證法得到xu的K個近鄰，獲取最近鄰距離d，并運用上文提及的高斯函數轉化為w;

（8）計算li∈L的后驗概率：

（9）利用新的分類函數2式計算每一個zv∈NewY擁有li的后驗概率，得到終極結果。

3 實驗結果與分析

3.1 數據集和文本預處理

本文實驗數據來自新浪微博平臺，通過爬蟲獲得，共計4000多條，其中訓練樣本3000條，測試樣本1000條，訓練樣本集包含時尚、娛樂、體育、新聞、影視、科技、美食、人文、醫藥、護膚、情感、歷史、經濟、健康、游戲15個標簽類別。具體如下：

本文使用jieba中文分詞模塊對樣本博文進行分詞，可以有效處理未登錄詞語的識別問題，能夠適應市場需求，使用TP-IDF方法實現文本的特征提取。

3.2 評價指標

本文選取5個常用的多標簽評價指標：漢明損失、1-錯誤率、覆蓋率、排序損失、平均精度。其中，漢明損失、1-錯誤率、覆蓋率、排序損失的值越小表示分類性能越好，平均精度的值越大表示分類性能越好。

3.3 實驗結果分析

由上述算法的描述可知，有最近鄰K 值、高斯函數a、c兩個參數、訓練數據r個聚類簇數、測試樣本t個聚類簇數。其中K值由交叉驗證法取15，a、c取值如表2，為了驗證改進ML-KNN算法的性質，將改進ML-KNN算法記為：AML-KNN，文獻[10]中提出的改進算法稱為BML-KNN，在MATLAB上實現。

由表2可知：當a=10、c=1/2時，算法效果最好。同時由上述算法易知：不同聚類簇數對本文算法也有至關重要的影響，如表3所示，當a、c確定時，聚類簇數不同對算法性能的影響。

表3 數據集上不同聚類簇數的影響

由表3可知，本文所選數據集在r=2，t=2效果最好。

4 結束語

針對ML-KNN算法中的數據集，每個特征具有相同的特征權重這一問題，對ML-KNN算法優化，結合聚類和最近鄰距離權重，本文提出的改進ML-KNN算法在實驗結果上，取得了很好的分類效果，并且在多標簽評價指標上也優于其他兩種算法。

參考文獻：

[1]Gao Sheng，Wu Wen，Lee C H，et al.A MFoM learning approach to robust multiclass multi-label text categorization[C]//Proc of the 21st International Conference on Machine Learning.San Francisco：Morgan Kaufmann Publisher，2004：329-336.

[2]Zhang Minling， Zhang Kun. Multi-label learning by exploiting label dependency[C]//Proc of the 16th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. New York： ACM Press， 2010：999-1007.

[3]Li Tao，Ogihara M.Toward intelligent music information retrieval[J].IEEE Trans on Multimedia，2006，8（3）：564-574.

[4]Zhang Minling，Zhou Zhihua.Multi-label neural networks with applications to functional genomics and text categorization[J].IEEE Trans on Knowledge and Data Engineering，2006，18（10）：1338-1351.

[5]Tang Lei，Rajan S， Narayanan V K. Large scale multi-label classification via metalabeler[C]//Proc of the 19th International