劉 云 肖 添 肖 雪

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

1 引言

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

Elisseeff 等［9］提出一種向量機(jī)的多標(biāo)簽分類算法（a Ranking Multi-class Support Vector Machine，RankSVM），此方法中利用排序函數(shù)計(jì)算值決定順序排名，求解二次規(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í)例概率函數(shù)，計(jì)算貝葉斯類先驗(yàn)概率和類條件概率預(yù)測測試實(shí)例的類標(biāo)簽集合。

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

2 模型建立

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

3 SMLC算法

3.1 算法描述

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

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

式中|fk(x)表示未知測試實(shí)例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ù)雜度分析

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

4 仿真分析

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

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

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

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

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

對于任何p，指標(biāo)函數(shù)Ⅱ[ ]p=1 且p 成立，否則為0。ED(f)=0 時(shí)性能最佳，該指標(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算法進(jìn)行仿真分析的結(jié)果統(tǒng)計(jì)于表2和表3中。

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

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

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

5 結(jié)語

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