基于相似度的多標(biāo)簽分類算法優(yōu)化*

劉 云 肖 添 肖 雪

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

1 引言

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

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

本文提出基于相似度的多標(biāo)簽分類算法（Multi-label Classification based on Similarity，SMLC），首先對實例進行相似度函數(shù)的構(gòu)建，同時進行并行計算，然后利用決策函數(shù)加權(quán)或?qū)W習(xí)閾值函數(shù)預(yù)測實例類標(biāo)簽集合。仿真結(jié)果表明，與RankSVM 和ML-KNN 算法進行對比分析，SMLC 算法在多標(biāo)簽分類任務(wù)中的各性能指標(biāo)上表現(xiàn)最優(yōu)。

2 模型建立

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

3 SMLC算法

3.1 算法描述

為進一步預(yù)測實例標(biāo)簽集，本文研究提出一種

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

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

上式中，

3.2 復(fù)雜度分析

計算訓(xùn)練實例xi中每個非零元素xj的相似度值，并且計算對應(yīng)測試實例特征值時間復(fù)雜度僅為

4 仿真分析

4.1 數(shù)據(jù)集和評價指標(biāo)

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

表1 仿真數(shù)據(jù)集

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

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

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

4.2 仿真分析

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

表2 在emotions數(shù)據(jù)集中性能分析

表3 在CLA500數(shù)據(jù)集中性能分析

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

5 結(jié)語

有效提高多標(biāo)簽分類準(zhǔn)確度成為重要研究方向。本文提出基于相似度的多標(biāo)簽分類算法SMLC，該算法首先構(gòu)建實例相似度函數(shù)，再采用并行計算方式算出相似值，最后通過加權(quán)計算類標(biāo)簽集合權(quán)重或者學(xué)習(xí)閾值方法預(yù)測類標(biāo)簽集合。仿真結(jié)果表明，對比RankSVM、ML-KNN 算法，SMLC算法在多標(biāo)簽分類任務(wù)中多個評價指標(biāo)上表現(xiàn)更好。