一種適應(yīng)于非完備標簽數(shù)據(jù)和標簽關(guān)聯(lián)性的多標簽分類方法

張麗娜 ，戴靈鵬 ，匡泰

（1.浙江安防職業(yè)技術(shù)學院信息工程系，浙江 溫州 325016；2.溫州大學生命與環(huán)境科學學院，浙江 溫州 325035）

一種適應(yīng)于非完備標簽數(shù)據(jù)和標簽關(guān)聯(lián)性的多標簽分類方法

張麗娜1，2，戴靈鵬2，匡泰1

（1.浙江安防職業(yè)技術(shù)學院信息工程系，浙江 溫州 325016；2.溫州大學生命與環(huán)境科學學院，浙江 溫州 325035）

多標簽分類已在很多領(lǐng)域得到了實際應(yīng)用，所用標簽大多具有很強的關(guān)聯(lián)性，甚至存在非完備標簽或部分標簽遺失。然而，現(xiàn)有的多標簽分類算法難以同時處理這兩種情況。基于此，提出一種新的概率模型處理方法，實現(xiàn)同時對具有標簽關(guān)聯(lián)性和遺失標簽情況進行多標簽分類。該方法可以自動獲知和掌握多標簽的關(guān)聯(lián)性。此外，通過整合遺失的標簽信息，該方法能夠提供一個自適應(yīng)策略來處理遺失的標簽。在完備標簽和非完備標簽的數(shù)據(jù)上進行實驗，結(jié)果表明，與現(xiàn)有的多標簽分類算法相比，提出的方法得到了較好的分類預(yù)測評價值。

非完備標簽；標簽關(guān)聯(lián)性；多標簽分類；概率模型

1 引言

在傳統(tǒng)的標簽數(shù)據(jù)分類問題中，一個樣點通常只分配一個標簽。但在實際應(yīng)用中，大部分都涉及多標簽分類，即一個樣點可分配多個標簽，如文本分類、圖像標注以及基因方程的分析［1］等。正是由于該類問題的不斷出現(xiàn)，也吸引了越來越多的學者進行多標簽分類問題的研究。

經(jīng)過多年的研究和發(fā)展，目前已出現(xiàn)了大量的多標簽分類方法，最為經(jīng)典且應(yīng)用最廣泛的是問題轉(zhuǎn)換類方法［2，3］。在此類方法中，較常用的一種方法是二值相關(guān)（binary relevance，BR）［4］算法。該方法建立在標簽之間相互獨立假設(shè)的基礎(chǔ)上，當標簽存在很大的關(guān)聯(lián)性時，該方法的效果不佳。針對BR方法的局限性，一種解決方案是假定標簽的關(guān)聯(lián)性是一種先驗信息或很容易被估計，如Read等人［5］提出了一種鏈式分類器（classifier chain，CC）算法，該方法以一定的次序?qū)⒁幌盗蠦R分類器串聯(lián)起來，后一個分類器的結(jié)果總是依賴于前一個分類器，這樣便考慮了標簽的關(guān)聯(lián)性。然而，其弊端是如果前一個分類器存在誤差，這種關(guān)聯(lián)也會將誤差進行傳遞積累。孫霞等人［6］提出了一種基于Haddoop框架的傳播算法，該方法能適應(yīng)大規(guī)模數(shù)據(jù)，但誤差同樣會在迭代算法中傳播。在Hariharan等人［7］提出的最大邊界多標簽分類器（max-margin multi-label classifier，M3L）中，標簽的關(guān)聯(lián)性被從訓練集中計算出的成對標簽關(guān)聯(lián)所代替，取得了不錯的效果，但該方法在樣本數(shù)量較少時會出現(xiàn)一些誤差。此外，一些方法通過標簽轉(zhuǎn)換進行去標簽關(guān)聯(lián)，即對去關(guān)聯(lián)的標簽進行分離學習，如Hsu等人［8］提出的利用隨機矩陣進行標簽轉(zhuǎn)換、在標簽矩陣中采用奇異值分解法的主標簽空間轉(zhuǎn)換 （principal label space transformation，PLST）［9］、在標簽矩陣和輸入樣本矩陣中均采用奇異值分解法的條件主標簽空間轉(zhuǎn)換（conditional principal label space transformation，CPLST）［10］以及在最小二乘回歸基礎(chǔ)上利用SVD技術(shù)的多標簽分類算法［11］，經(jīng)過這些方法轉(zhuǎn)換后的標簽都可以單獨進行處理。再有，一些學者在方法的精度等方面也做了一些研究，如李遠航等人［12］、許美香等人［13］通過主動學習的方法提高分類器的精度和效率；徐曉丹等人［14］通過對數(shù)據(jù)進行預(yù)處理來提高分類器的精度。

在多標簽分類算法中，另一個重要的問題是標簽遺失。針對此問題，一些學者也提出了相應(yīng)的解決方案。其中一種解決方法是丟棄所有沒有標簽的樣本，但會損失大量的標簽信息。另一種方法是估算遺失的標簽，尤其是正標簽，如群索引多標簽排序 （multi-label ranking with group lasso，MLRGL）［15］算法，它將分類問題轉(zhuǎn)化為雙邊排序 問 題進 行 解 決 ；快 速 圖 像 標 記［16］（fast image tagging，F(xiàn)astTag）法，它假設(shè)標簽一致性被破壞，該方法能對可能遺失的正標簽進行恢復(fù)，但不能有效地處理標簽關(guān)聯(lián)性問題，且只能對正標簽進行恢復(fù)。Yu等人［17］根據(jù)經(jīng)驗誤差最小化，提出了一種對遺失標簽的分析方法，該方法也沒有準確考慮標簽的關(guān)聯(lián)性，限制了它的應(yīng)用。

針對目前大部分方法分別在處理標簽關(guān)聯(lián)和標簽遺失問題中存在的缺陷以及難以對這兩個問題同時進行處理的情況，提出一個新的概率模型，該模型能同時處理標簽關(guān)聯(lián)和標簽遺失問題，它不需準確地找出標簽轉(zhuǎn)換，只需將概率模型重新表述成原始的標簽空間，在原始標簽空間中自動獲知和掌握標簽的關(guān)聯(lián)性。此外，通過對遺失的標簽信息進行整合，以提供一種自適應(yīng)的方法來處理遺失標簽。最后，在具有完備標簽和遺失標簽數(shù)據(jù)上進行試驗，結(jié)果表明，該方法所獲得的效果優(yōu)于現(xiàn)有經(jīng)典方法。

2 提出的方法

第2節(jié)主要介紹同時處理非完備標簽數(shù)據(jù)和標簽關(guān)聯(lián)性的多標簽分類方法。首先進行最基本的步驟，即標簽轉(zhuǎn)換，在此基礎(chǔ)上，提出一個新的概率模型，對標簽關(guān)聯(lián)和遺失標簽同時進行處理，并給出優(yōu)化子問題的推導(dǎo)過程。

2.1 標簽轉(zhuǎn)換

在多標簽分類問題中，對于一個給定的訓練集{（x，y）}，其中，x∈Rd是輸入，y∈{0，1}m是對應(yīng)的輸出，其中，m 是樣點數(shù)，d是樣點維度。標簽轉(zhuǎn)換［9，10］是指將每一個 y轉(zhuǎn)換成=Py，其中是轉(zhuǎn)換矩陣，經(jīng)轉(zhuǎn)換之后的標簽是不相關(guān)的，即可以單獨對待。首先，采用一個線性模型作為初始模型（加權(quán)為，偏差為），即被假定為：是噪聲方差。注意：用于標簽轉(zhuǎn)換的高斯噪聲一般是實值（盡管原始值是二值）。式（1）可改寫為如下形式：其中，

2.2 標簽關(guān)聯(lián)處理

第2.1節(jié)主要介紹了標簽轉(zhuǎn)換的基本方法，接下來將建立一個模型，利用該模型對標簽關(guān)聯(lián)性進行處理。

2.2.1 模型建立及分析

首先，建立一個概率模型。通過使用式（2）和式（4）以及和轉(zhuǎn)換標簽時編碼原始標簽的誤差以得到，在對式（4）中z進行湊整之前的多標簽預(yù)測遵從下列正態(tài)分布：

其中，λ1，λ2＞0 是兩個自由參數(shù)，用來增加-1的稀疏度和收縮性，-1指精度矩陣，表示標簽i和標簽j之間 部 分 相 關(guān)［18］。增 加-1的 稀 疏 度 意 味 著 大 部 分 的 標 簽 是條件不相關(guān)的。這里，p（）是根據(jù)-1表述，而不是。為了模擬從z到二值預(yù)測y的湊整誤差，通過下面的正態(tài)分布來近似：

其中，λ0＞0。

其中，β1，β2＞0。圖 1 是代表整個模型的一個圖解表示，可清楚呈現(xiàn)其建立過程。具體地，首先通過自由參數(shù)λ1和λ2根據(jù)式（6）來獲得的信息；同時，通過參數(shù) β1和 β2根據(jù)式（11）來獲得的信息，進而得到的分布。根據(jù)式（5），通過已知的訓練集x、偏差b以及得到的W和來得到z，進而根據(jù)式（7）通過給定的參數(shù)λ0來獲得y。提出的模型相較傳統(tǒng)方法模型的優(yōu)勢在于：現(xiàn)有的部分方法未考慮標簽間的關(guān)聯(lián)性，或考慮了相關(guān)性，但由于串聯(lián)分類器存在誤差或樣本數(shù)量較少等原因，其關(guān)聯(lián)會將誤差傳遞積累，進而導(dǎo)致更多的誤差。而提出的模型不需要準確地找出標簽轉(zhuǎn)換，只需將概率模型重新表述成原始的標簽空間，在原始標簽空間中自動獲知和掌握標簽的關(guān)聯(lián)性，目標是獲得能夠?qū)崿F(xiàn)同時對具有標簽關(guān)聯(lián)性和遺失標簽情況進行多標簽分類求解模型 （具體求解處理見第2.2.2節(jié)和第2.3節(jié)）。

圖1 提出模型的一個圖解表示

2.2.2 模型推導(dǎo)求解

對建立的模型進行推導(dǎo)求解。對于給定的N個樣點，令研究表明，湊整會導(dǎo)致編碼誤差為對應(yīng)的標簽矩陣。其中，上標（i）表示第i個樣點。當

下面，使用交替最大化方法［23］對式（11）進行求解，交替獲得后驗信息最大值，即在式（13）中每次固定其他變量而求一個變量的最大值。這里，每一個子問題是凸性的，且容易求解，具體如下。

（1）固定其他變量，求解Z

最優(yōu)化子問題是：

顯然，每一個 z（i）都可以單獨求解。令 z（i）的導(dǎo)數(shù)為 0，可以得到：

（2）固定其他變量，求解W和b

最優(yōu)化子問題為：

令W的導(dǎo)數(shù)為0，可以得到一個封閉形式的解：，對于 b，令其導(dǎo)數(shù)為 0，可以得到：

根據(jù)式（6）的先驗信息，最優(yōu)化子問題為：

2.3 遺失標簽處理

基于提出的模型，對遺失標簽情況進行處理。如前所說，標簽向量也許會有一些遺失記錄。假設(shè)樣點x（i）具有l(wèi)i個 觀 測 標 簽 以 及 ui=m-li個 遺 失 標 簽 ，可 將 y（i）和 z（i）分 別 記為和，其中，。同樣，對每一個i，通過將第li行／列與首次觀測的標簽進行對應(yīng)，可將-1記為其中，

不同于直接估算遺失標簽值的方法［15］，這里所獲得的信息直接來源于觀測標簽，類似于式（13），可以得到：

則仍然滿足正態(tài)分布［24］：是W的子矩陣，W的列對應(yīng)于li觀測標簽。注意：每一個在整個矩陣中相對于是獨立的。因此，盡管有遺失標簽存在，推理過程仍然可以利用標簽關(guān)聯(lián)信息。

如第2.2.2節(jié)所示，本節(jié)也將使用交替最大化法來求解式（21）中的后驗信息最大值。對于的最大化子問題與之前相同，因此其校正不變。

最優(yōu)化子問題為：

（2）固定其他變量，求解W和b

最優(yōu)化子問題為：

不同于式（16），這里無法對該凸問題得到封閉解，而需要通過降低梯度對W進行最優(yōu)化，即對b可得到一個封閉解：

最優(yōu)化子問題為：

通過軟閾值迭代算法［25］進行求解，將式（28）分解為兩部分：

梯度降；

其中，τ=λ2η，η 是梯度降的補償。

3 實驗效果與分析

在第 3節(jié)中，對 Guillaumin等人［26］采用的 4個圖像標注的數(shù)據(jù)集（表1）進行試驗。對每一個圖像都提取1 000個SIFT特征。

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

將提出的處理非完備數(shù)據(jù)和標簽關(guān)聯(lián)的多標簽分類方法 （multi-label classification with incomplete labeled data and label relevance，ILDLR）與下列經(jīng)典方法進行對比分析：

· 二值相關(guān)（BR）算法［4］；

· 條件的主標簽空間轉(zhuǎn)換（CPLST）法［10］；

· 具有群索引的多標簽排序（MLRGL）法［15］；

· 快速圖像標記（FastTag）法［16］。

由于在CPLST方法中的轉(zhuǎn)換標簽是實際值，因此，使用脊回歸作為其初始模型。所有方法的參數(shù)調(diào)整都基于一個已驗證的集合，該集合通過對實驗數(shù)據(jù)采樣25%獲得。下面兩個參數(shù)被廣泛的用于多標簽分類的效果評價［26］：

其中，macro_F1和micro_F1值越大，效果越好。

3.1 在完備標簽數(shù)據(jù)上的實驗

在4組完備數(shù)據(jù)集上進行實驗，并與其他幾種方法進行對比?；?0折交叉驗證方法，對數(shù)據(jù)進行分類及F1值評價，結(jié)果見表2，其中，“±”表示10次驗證計算的 F1評價值的浮動范圍?？梢钥吹?，在完備標簽的情況下，提出的ILDLR方法對所有的數(shù)據(jù)處理效果都比其他方法要好。對于 MLRGL方法，在 COREL5K、ESPGAME和IAPRTCL12 3個數(shù)據(jù)集上的處理效果與其他幾種方法的效果差距較大。

3.2 在非完備標簽數(shù)據(jù)上的實驗

通過以下方式生成遺失標簽。之前提及有m個標簽，對每一個訓練樣本集，選擇其中的一半作為觀測值，其余的為遺失值。由于每個樣點都普遍具有極少的正標簽，且標簽進行隨機拆分有可能導(dǎo)致僅僅觀測到負標簽，因此，對每一個樣點，保證有k=1，2，3個觀測到的正標簽（如果一個樣本的正標簽數(shù)少于k個，那么它所有的正標簽將被挑選出來）。將ILDLR、MLRGL、FastTag和BR 4種方法進行比較，這4種方法都能處理遺失標簽。

表3呈現(xiàn)的是10折交叉驗證的結(jié)果，可以看到，ILDLR的效果要優(yōu)于其他方法（除了在MIRFLICKR數(shù)據(jù)集中當k=2時）。當遺失標簽的數(shù)量遠大于k的最大值時，效果并不會隨著k的增大而變好。并且當k=1時，通過ILDLR獲得的F1與表2中具有完備標簽所獲得的值很接近。對于數(shù)據(jù)COREL5K，ILDLR在標簽遺失的情況下反而效果更好，其原因是：對于完備標簽，需要學習m×n的標簽矩陣Z。而當標簽遺失時，只需要學習觀測標簽矩陣Z對應(yīng)的子矩陣。這樣，盡管式（22）依賴于分布的結(jié)果，且可能會引進一些誤差，但減少了自由參數(shù)的個數(shù)。因此，提出的ILDLR方法在標簽遺失的情況下也會得到很好的處理效果。

表2 具有完備標簽數(shù)據(jù)的結(jié)果

4 結(jié)束語

對多標簽分類提出了一個概率模型，然后受標簽轉(zhuǎn)換方法的啟發(fā)，此模型在原始標簽空間而不是在轉(zhuǎn)換標簽空間進行表述，這可以靈活地處理標簽相關(guān)和遺失標簽情況，并且推導(dǎo)過程簡單。在完備的數(shù)據(jù)和具有非完備的遺失標簽數(shù)據(jù)上的實驗都表明，提出的方法比現(xiàn)有的其他經(jīng)典方法效果更好。

［1］ZHANG M L，ZHOU Z H.A review on multi-label learning algorithms ［J］.IEEE Transactions on Knowledge and Data Engineering，2014，26（8）：1819-1837.

［2］MADJAROV G，KOCEV D，GJORGJEVIKJ D，et al.An extensive experimental comparison of methods for multi-label learning［J］.Pattern Recognition，2012，45（9）：3084-3104.

［3］王霄，周李威，陳耿，等.一種基于標簽相關(guān)性的多標簽分類算法［J］.計算機應(yīng)用研究，2014，31（9）：2609-2614.WANG X，ZHOU L W，CHEN G，et al.Correlation label-based multi-label classification algorithm.［J］.Application Research of Computers，2014，31（9）：2609-2614.

［4］TSOUMAKAS G， KATAKIS I， VLAHAVAS I.Mining multi-label data［M］.New York：Springer，2010：667-685.

表3 10折交叉驗證結(jié)果

［5］READ J，PFAHRINGER B，HOLMES G，et al.Classifier chains for multi-labelclassification ［C］／／European Conference on Machine Learning，June 14-18，2009，Montreal，Canada.New Jersey：IEEE Press，2009：254-269.

［6］孫霞，張敏超，馮筠，等.Hadoop框架下的多標簽傳播算法［J］.西安交通大學學報，2015，49（5）：134-139.SUN X，ZHANG M C，F(xiàn)ENG J，et al.A label propagation algorithm for multi-label classification ［J］.Journal of Xi’an Jiaotong University，2015，49（5）：134-139.

［7］HARIHARAN B，ZELNIK M L，VISHWANATHAN S，et al.Large scale max-margin multi-label classification with priors［C］／／27th International Conference on Machine Learning，June 21-24，2010，Haifa，Isreal.New Jersey：IEEE Press，2010：423-430.

［8］HSU D，KAKADE S，LANGFORD J，et al.Multi-label prediction via compressed sensing［J］.Computer Science，2009：772-780.

［9］ TAI F，LIN H.Multi-label classification with principal label space transformation ［J］.Neural Computation，2012，24 （9）：2508-2542.

［10］CHEN Y N，LIN H T.Feature-aware label space dimension reduction for multi-label classification ［J］.Advances in Neural Information Processing Systems ，2012（2）：1538-1546.

［11］馬宗杰，劉華文.基于奇異值分解-偏最小二乘回歸的多標簽分類算法［J］.計算機應(yīng)用，2014，34（7）：2058-2061.MA Z J，LIU H W.Multi-label classification based on singular value decomposition-partial least squares regression［J］.Journal of Computer Applications，2014，34（7）：2058-2061.

［12］李遠航，劉波，唐僑.面對多標簽圖數(shù)據(jù)的主動學習［J］.計算機科學，2014，41（11）：260-264.LIYH，LIUB，TANGQ.Activelearningformulti-label classification on graphs［J］.Computer Science，2014，41（11）：260-264.

［13］許美香，孫福明，李豪杰.主動學習的多標簽圖像分類在線分類［J］.中國圖像圖形學報，2015，20（2）：237-244.XU M X，SUN F M，LI H J.Online multi-label image classification with active learning ［J］.Journal of Image and Graphics，2015，20（2）：237-244.

［14］徐曉丹，姚明海，劉華文，等.基于kNN的多標簽分類預(yù)處理方法［J］.計算機科學，2015，42（5）：106-108.XU X D，YAO M H，LIU H W，et al.Pre-processing method of multi-label classification based on kNN［J］.Computer Science，2015，42（5）：106-108.

［15］BUCK S，JIN R，JAIN A.Multi-label learning with incomplete class assignments ［C］／／IEEE Conference on Computer Vision and Pattern Recognition，June 20-25，2011，Providence，RI，USA.New Jersey：IEEE Press，2012：2801-2808.

［16］CHEN M，ZHENG A，WEINBERGER K Q.Fast image tagging［C］／／30th International Conference on Machine Learning，June 16-21，2013，Atlanta，GA，USA.New Jersey：IEEE Press，2013：1274-1282.

［17］YU H F，JAIN P，DHILLON I S.Large-scale multi-label learning with missing labels［C］／／31st International Conference on Machine Learning，June 21-26，2014，Beijing，China.New Jersey：IEEE Press，2014：593-601.

［18］PETTERSON J，CAETANO T.Submodular multi-label learning［J］.Advances in Neural Information Processing Systems，2011：1512-1520.

［19］GUPTA A，NAGAR D.Matrix variate distributions ［M］.Boca Raton：Chapmanamp;Hall／CRC Press，2000.

［20］RAI P，KUMAR A，III H D.Simultaneously leveraging output and task structures for multiple-output regression［C］／／Advances in Neural Information Processing Systems，December 3-8，2012，South Lake Tahoe，USA.New Jersey：IEEE Press，2012：3194-3202.

［21］ROTHMAN A J，LEVINA E，ZHU J.Sparse multivariate regression with covariance estimation［J］.Journal of Computational and Graphical Statistics，2010，19（4）：947-962.

［22］ZHANG Y，YEUNG D Y.A convex formulation for learning task relationships in multi-task learning ［C］／／26th Conference on Uncertainty in Artificial Intelligence，July 8-11，2010，Los Angeles，USA.New Jersey：IEEE Press，2010：733-742.

［23］BERTSEKAS D P.Nonlinear programming ［M］.Nashua：Athena Scientific，1999.

［24］BISHOP C M.Pattern recognition and machine learning［M］.New York：Springer-Verlag，2006：125-153.

［25］BECK A，TEBOULLE M.A fast iterative shrinkage-thresholding algorithm for linear inverse problem［J］.SIAM Journal on Imaging Sciences，2009，2（1）：183-202.

［26］GUILLAUMIN M，MENSINK T，VERBEEK J，et al.Tagprop：discriminative metric learning in nearest neighbor models for image auto-annotation ［C］／／International Conference on Computer Vision，September 29-October 2，2009，Kyoto，Japan.New Jersey：IEEE Press，2009：309-316.

A multi-label classification method for disposing incomplete labeled data and label relevance

ZHANG Lina1，2，DAI Lingpeng2，KUANG Tai1
1.Department of Information Engineering，Zhejiang College of Security Technology，Wenzhou 325016，China 2.College of Life and Environmental Science，Wenzhou University，Wenzhou 325035，China

Multi-label classification methods have been applied in many real-world fields，in which the labels may have strong relevance and some of them even are incomplete or missing.However，existing multi-label classification algorithms are unable to handle both issues simultaneously.A new probabilistic model that can automatically learn and exploit multi-label relevance was proposed on label relevance and missing label classification simultaneously.By integrating out the missing information，it also provides a disciplined approach to handle missing labels.Experiments on a number of real world data sets with both complete and incomplete labels demonstrated that the proposed method can achieve higher classification and prediction evaluation scores than the existing multi-label classification algorithms.

incomplete label，label relevance，multi-label classification，probabilistic model

s： Education Science Department Foundation of Zhejiang Province（No.2016SCG188），The Natural Science Foundation of Zhejiang Province of China （No.LY14C03007）

TP311

A

10.11959／j.issn.1000-0801.2016197

2016-05-04；

2016-07-10

張麗娜，zln_zcst@163.com

浙江省教育科學規(guī)劃基金資助項目（No.2016SCG188）；浙江省自然科學基金資助項目（No.LY14C03007）

張麗娜（1980-），女，浙江安防職業(yè)技術(shù)學院信息工程系講師，主要研究方向為數(shù)據(jù)挖掘、圖像處理、模式識別。

戴靈鵬（1975-），男，博士，溫州大學生命與環(huán)境科學學院副教授，主要研究方向為模式識別。

匡泰（1964-），男，浙江安防職業(yè)技術(shù)學院信息工程系副教授，主要研究方向為大數(shù)據(jù)、人工智能。