邢娟韜 白金牛

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

關(guān)鍵詞：多標記學習;ML-KNN;最近鄰;聚類;距離權(quán)重

中圖分類號：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 概述

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

2 方法描述

2.1 ML-KNN算法

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

2.2 改進ML-KNN算法

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

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

輸入：訓練數(shù)據(jù)集、測試數(shù)據(jù)集。

輸出：分類結(jié)果。

（1）利用k-means聚類算法將訓練數(shù)據(jù)和測試數(shù)據(jù)分別分為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對應的簇作為新的訓練數(shù)據(jù)，記為NewX;

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

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

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

（9）利用新的分類函數(shù)2式計算每一個zv∈NewY擁有l(wèi)i的后驗概率，得到終極結(jié)果。

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

3.1 數(shù)據(jù)集和文本預處理

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

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

3.2 評價指標

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

3.3 實驗結(jié)果分析

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

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

表3 數(shù)據(jù)集上不同聚類簇數(shù)的影響

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

4 結(jié)束語

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

參考文獻：

[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