基于相似度的多標簽分類算法優化*

劉 云 肖 添 肖 雪

（昆明理工大學信息工程與自動化學院 昆明 650500）

1 引言

近年來，多標簽分類問題被廣泛研究，不同于傳統分類問題，多標簽分類的每個樣本實例同時包含兩個及兩個以上標簽數量。因此，這些標簽不再互斥［1～2］。為了更深入研究多標簽分類問題，很多學者提出了許多多標簽分類方法，主要包括基于支持向量機［3］，神經網絡［4］，樸素貝葉斯［5］，決策樹［6］，K 近鄰（KNN）［7］等方法。現存的分類算法存在分類精度不高，不能有效處理類別不均衡數據等問題［8］。

Elisseeff 等［9］提出一種向量機的多標簽分類算法（a Ranking Multi-class Support Vector Machine，RankSVM），此方法中利用排序函數計算值決定順序排名，求解二次規劃的凸目標函數得出類標簽集合。Zhang［10］等研究了一種多標簽K 近鄰算法（Multi-label K Nearest Neighbor Algorithm，ML-KNN），此方法的目標是尋找每類訓練樣本的近鄰標簽數，對構建實例概率函數，計算貝葉斯類先驗概率和類條件概率預測測試實例的類標簽集合。

本文提出基于相似度的多標簽分類算法（Multi-label Classification based on Similarity，SMLC），首先對實例進行相似度函數的構建，同時進行并行計算，然后利用決策函數加權或學習閾值函數預測實例類標簽集合。仿真結果表明，與RankSVM 和ML-KNN 算法進行對比分析，SMLC 算法在多標簽分類任務中的各性能指標上表現最優。

2 模型建立

式中·,· 代表兩個實例向量的內積，d表示多項式次數，c 表示代價函數多項式由高階項轉化為低階項的正則項。計算測試實例xi的標簽權重f(xi)，xi所包含的標簽集標簽權重計算公式如下式所示：

3 SMLC算法

3.1 算法描述

為進一步預測實例標簽集，本文研究提出一種

根據訓練數據D'={(x1,y1),…,(xN,yN)}，預測未知實例xi的類標簽集合。首先，根據前文的相似度多項式函數（4）可知每個訓練實例(xj,yj)∈D′相似度為Φ(xi,xj)（1 ≤j≤N），若訓練實例屬于同一個標簽集k∈y′（即大小相同），則實例相似性可通過加權計算。相同類標簽k∈y′的訓練數據D′的實例xi的相似性可通過式（6）表示：

式中|fk(x)表示未知測試實例xi標簽k∈y的置信度。假設線性模型t(x)=w,f(x) +b（t(·)為閾值函數），給定訓練集D，可根據式（10）學習閾值函數：

上式中，

3.2 復雜度分析

計算訓練實例xi中每個非零元素xj的相似度值，并且計算對應測試實例特征值時間復雜度僅為

4 仿真分析

4.1 數據集和評價指標

為了評估本文研究的多標簽分類算法有效性，選取了著名的Mulan Library［12］多標簽數據集進行仿真測試，表1描述了測試數據集的具體信息。

表1 仿真數據集

在多標簽分類任務中，其性能評價指標比單標簽分類更為復雜和全面，下面對算法評價指標進行定義，給定測試數據集D，測試實例xi∈RM，需預測標簽集為h:χ→2K，多標簽學習算法輸出函數f:χ×y→R，其中fk( )xi為標簽k∈y對于未知測試實例xi的置信度，多標簽分類中把有效預測最大標簽集合作為評價一個分類算法好壞。為了證明算法的有效性，選取了多標簽分類的常用評價指標如下［13～15］。

1）漢明損失（Hamming Loss，HL）：

對于任何p，指標函數Ⅱ[ ]p=1 且p 成立，否則為0。ED(f)=0 時性能最佳，該指標評估排名最高的標簽不在相關標簽集中的次數。該指標值越小則說明算法性能越好。該指標衡量測試樣本平均包含多少標簽。指標值越大表明算法性能越優。

4.2 仿真分析

將所提出的SMLC算法與Rank-SVM、ML-KNN算法進行仿真分析的結果統計于表2和表3中。

表2 在emotions數據集中性能分析

表3 在CLA500數據集中性能分析

從上表2、3 可看出，與RankSVM 和ML-KNN算法對比，SMLC 算法在漢明損失、1-錯誤率、覆蓋率、排名損失、平均準確率五個多標簽分類性能指標上表現最優。

5 結語

有效提高多標簽分類準確度成為重要研究方向。本文提出基于相似度的多標簽分類算法SMLC，該算法首先構建實例相似度函數，再采用并行計算方式算出相似值，最后通過加權計算類標簽集合權重或者學習閾值方法預測類標簽集合。仿真結果表明，對比RankSVM、ML-KNN 算法，SMLC算法在多標簽分類任務中多個評價指標上表現更好。