基于共享子空間的多標(biāo)簽數(shù)據(jù)學(xué)習(xí)模型研究

鄒　珊（北京交通大學(xué)計(jì)算機(jī)與信息技術(shù)系，北京100044）

基于共享子空間的多標(biāo)簽數(shù)據(jù)學(xué)習(xí)模型研究

鄒珊
（北京交通大學(xué)計(jì)算機(jī)與信息技術(shù)系，北京100044）

在多標(biāo)簽分類問題中，多個(gè)標(biāo)簽共享同一個(gè)輸入空間，而且同一個(gè)實(shí)例的不同標(biāo)簽之間也存在一定的相關(guān)性，所以在研究此類問題的時(shí)候，標(biāo)簽之間的關(guān)聯(lián)性研究就顯得尤為重要?，F(xiàn)有的多標(biāo)簽學(xué)習(xí)對于標(biāo)簽之間的相關(guān)的研究均是在原始數(shù)據(jù)上進(jìn)行的，而我們希望對原始數(shù)據(jù)進(jìn)行重表示，從原始輸入空間中提煉出高層的語義信息將高維的數(shù)據(jù)映射到一個(gè)低維的子空間中，在類標(biāo)信息作指導(dǎo)的情況下體現(xiàn)類標(biāo)之間的共享信息的特點(diǎn)。再利用已有的分類方法進(jìn)行多標(biāo)簽的分類。對多個(gè)網(wǎng)頁分類任務(wù)進(jìn)行實(shí)驗(yàn)，結(jié)果表明此種方法在一定程度上提高分類效果。

多標(biāo)簽學(xué)習(xí)；共享空間；數(shù)據(jù)重表示

1　問題的提出

在機(jī)器學(xué)習(xí)中，研究最多應(yīng)用最廣泛的監(jiān)督學(xué)習(xí)（Traditional Supervised Learning）通過分析訓(xùn)練數(shù)據(jù)集獲得輸入特征空間和輸出標(biāo)簽空間之間的一個(gè)映射函數(shù)。該傳統(tǒng)方法在待學(xué)習(xí)對象具有明確的、單一的語義時(shí)（即對象標(biāo)簽唯一），已經(jīng)取得了巨大的成功。然而，真實(shí)世界的對象往往具有多義性，即一個(gè)樣本可能同時(shí)屬于多個(gè)類別。例如，在文檔分類問題中[1～2]，每篇文檔可能屬于多個(gè)預(yù)定義的主題；在圖片分類中，每個(gè)圖片可能含有不同的語義；在生物信息學(xué)問題中[3]，每個(gè)基因可能同時(shí)具有多種功能等。

在處理多義性對象時(shí)，上述只考慮明確、單一語義對象的傳統(tǒng)監(jiān)督學(xué)習(xí)方法難以取得好的效果。于是，研究者提出了多標(biāo)簽學(xué)習(xí)（Multi-label Learning）方法。該方法能夠處理具有多個(gè)類別標(biāo)記的對象，其學(xué)習(xí)目標(biāo)是將所有適合的類別標(biāo)記賦予待分析的對象。早期，多標(biāo)簽學(xué)習(xí)的研究主要集中于文檔分類中遇到的多義性問題。經(jīng)過近十年來的發(fā)展，多標(biāo)簽學(xué)習(xí)技術(shù)已在多媒體內(nèi)容自動標(biāo)注、生物信息學(xué)、Web挖掘、信息檢索、個(gè)性化推薦等領(lǐng)域得到了廣泛的應(yīng)用。

多標(biāo)簽學(xué)習(xí)已經(jīng)得到眾多學(xué)者的關(guān)注[4]，最普遍的方法是將該學(xué)習(xí)問題分解為多個(gè)二分類問題求解[4～5]，由于此方法效率高且容易實(shí)現(xiàn)，在實(shí)際應(yīng)用中得到了廣泛的應(yīng)用。然而，這種方法完全忽略了標(biāo)簽之間的相關(guān)性；而隨著多標(biāo)簽學(xué)習(xí)的研究的不斷深入，出現(xiàn)了許多基于多標(biāo)簽之間相關(guān)性的學(xué)習(xí)方法[6～7]，這些方法直接對原始數(shù)據(jù)進(jìn)行處理。然而在實(shí)際應(yīng)用中，原始數(shù)據(jù)具有高維性，且含有噪聲或冗余的特征。因此在多標(biāo)簽分類之前，需要對原始數(shù)據(jù)進(jìn)行處理，從而使分類過程更加有效。

數(shù)據(jù)降維技術(shù)是一項(xiàng)常見的數(shù)據(jù)處理技術(shù)［8～9］。數(shù)據(jù)降維是指通過線性或者非線性映射將高維數(shù)據(jù)轉(zhuǎn)變成低維數(shù)據(jù)。數(shù)據(jù)降維的目標(biāo)是在保持原始數(shù)據(jù)的分類和決策能力的前提下去掉數(shù)據(jù)中的冗余信息。通過數(shù)據(jù)降維可以消除冗余，去掉高維空間中不相關(guān)屬性，解決由維度災(zāi)難引起的問題，促進(jìn)高維數(shù)據(jù)的分類和壓縮［10］。目前已經(jīng)提出了許多降維方法，包括主成分分析（PCA）、典型相關(guān)性分析（CCA）等。PCA［11］是一種典型的線性降維方法，通過對原始變量的相關(guān)矩陣進(jìn)行研究，用少數(shù)幾個(gè)綜合變量表示原屬的多個(gè)變量，進(jìn)而達(dá)到降維的目的。CCA研究兩組變量之間相關(guān)性的一種多元統(tǒng)計(jì)分析方法，它將兩組變量分別映射到與它們最大限度的相關(guān)的低維度的空間中。這種方法雖然同時(shí)對兩組變量進(jìn)行降維處理，但在降維的過程中，并沒有考慮兩組變量之間的相關(guān)性。

針對上述問題，我們提出了一個(gè)基于多標(biāo)簽共享信息的數(shù)據(jù)表示學(xué)習(xí)模型，該模型通過從原始數(shù)據(jù)信息中提煉出更高層的語義信息，即將高維的原始數(shù)據(jù)映射到一個(gè)低維的子空間中。同時(shí)為了充分利用標(biāo)簽信息，模型考慮了標(biāo)簽與低維子空間的關(guān)系，該關(guān)系有效地展示標(biāo)簽之間共享信息，即分別對標(biāo)簽信息和原始數(shù)據(jù)信息進(jìn)行降維處理。在此基礎(chǔ)上，還考慮了標(biāo)簽信息與數(shù)據(jù)屬性特征之間的線性相關(guān)性。利用上述方法對原始數(shù)據(jù)進(jìn)行重表示后，再利用已有的分類方法進(jìn)行多標(biāo)簽的分類學(xué)習(xí)。在實(shí)際多標(biāo)簽文本數(shù)據(jù)上的實(shí)驗(yàn)結(jié)果證明我們所提出的模型對數(shù)據(jù)進(jìn)行重表示后，分類效果較原有方法在一定程度上有所提高。

2　算法實(shí)現(xiàn)

在上述式子中，W∈Rd×r用來表示數(shù)據(jù)與共享空間r的關(guān)系，這里因?yàn)橛玫筋悇e標(biāo)簽的指示矩陣Y，故引入變量P∈Rm×r用來表示類別標(biāo)簽與共享空間的關(guān)系。根據(jù)此模型學(xué)習(xí)到數(shù)據(jù)與共享空間之間的關(guān)系W，從而達(dá)到將高維的數(shù)據(jù)映射到低維的共享空間上，然后利用變量W對原始數(shù)據(jù)進(jìn)行重表示，再利用已有的分類方法重新進(jìn)行多標(biāo)簽的分類學(xué)習(xí)。

3　算法優(yōu)化

在求解W時(shí)，將P看作是已知量，即：

根據(jù)上述公式對W求導(dǎo)，并將其置為0可以得到：

同在求解P時(shí)，將W看作是已知量，即：

根據(jù)上述公式對P求導(dǎo)，并將其置為0可以得到：

根據(jù)等式（5）、（7），利用K-T（Kuhn-Tucker）條件αijwij=0和βijpij=0可以得出對于W，P的更新規(guī)則：

在迭代求解W，P時(shí)，涉及到兩個(gè)關(guān)鍵的問題，W和P的初始值及循環(huán)迭代的終止條件。W表示數(shù)據(jù)與共享空間的關(guān)系，在初始化時(shí)隨機(jī)賦給W一個(gè)d×r矩陣，根據(jù)P所表示的含義，即類別標(biāo)簽與共享空間的關(guān)系，在初始化的時(shí)候我們將P置為1/r，即認(rèn)為最初每個(gè)類標(biāo)在共享空間所占比例相同。對于循環(huán)終止條件，根據(jù)上文提出的模型可以知道，若迭代次數(shù)較少，可能導(dǎo)致W，P學(xué)習(xí)到的值不夠理想；而迭代次數(shù)過多，不僅使整個(gè)實(shí)驗(yàn)耗時(shí)較長影響實(shí)驗(yàn)效率，而且還會影響最終的分類性能。于是，在實(shí)驗(yàn)中，采用變量迭代前后兩次差值的F-范數(shù)大于設(shè)定的閾值，這里設(shè)置為10-3作為循環(huán)迭代的終止條件。

通過上述方法計(jì)算出低維度的數(shù)據(jù)與共享空間的關(guān)系W，然后將原始數(shù)據(jù)映射到共享空間中，即對輸入的數(shù)據(jù)進(jìn)行重表示，然后再利用已有的分類方法進(jìn)行分類。對于多標(biāo)簽的分類，目前已經(jīng)有很多的分類方法[20]，例如支持向量機(jī)（Support Vector Machine，SVM）、基于多任務(wù)的迭代優(yōu)化模型算法（Alternating Structure Optimization，ASO）等。在本文中，我們分別對現(xiàn)有的幾種不同的方法，如ASO、SVM分別進(jìn)行了實(shí)驗(yàn)，從而驗(yàn)證所提出的模型的優(yōu)越性。

在上述優(yōu)化算法中，我們可以看出對于W和P的計(jì)算是一個(gè)反復(fù)迭代的過程，由更新規(guī)則可以得出，對于P的更新的計(jì)算復(fù)雜度為O（mnd+m2n+t（3mdr+m2r）），對于W的更新的計(jì)算復(fù)雜度為O（mnd+m2n+t（3mdr+ m2r+2d2r））。由前面的介紹我們可以知道，r＜＜d且m＜＜d，因此，CSI算法整體的計(jì)算復(fù)雜度為O（nd+t（d2+d）），其中t為迭代次數(shù)。

4　實(shí)驗(yàn)結(jié)果

實(shí)驗(yàn)中選用多主題的網(wǎng)頁集合[12～14]作為實(shí)驗(yàn)數(shù)據(jù)，這些數(shù)據(jù)是通過對“yahoo.com”領(lǐng)域的11個(gè)頂級集合編譯而來。通過刪除主題不到100的網(wǎng)頁，出現(xiàn)次數(shù)少于5次的詞，以及沒有主題的網(wǎng)頁來對數(shù)據(jù)進(jìn)行預(yù)處理。然后使用TF-IDF編碼來表示網(wǎng)頁，每個(gè)網(wǎng)頁都?xì)w一化為統(tǒng)一的長度。在本文中我們選取Science和Health兩個(gè)數(shù)據(jù)集進(jìn)行實(shí)驗(yàn)驗(yàn)證。在經(jīng)過上述預(yù)處理后，我們通過采用文檔頻率（Document Frequency，DF）方法對數(shù)據(jù)進(jìn)行了特征選擇，以減少計(jì)算量提高實(shí)驗(yàn)效率。這兩個(gè)數(shù)據(jù)集的統(tǒng)計(jì)如表1所示，其中m、d、N分別表示經(jīng)過預(yù)處理后的標(biāo)簽數(shù)、數(shù)據(jù)維度和總的實(shí)例數(shù)。

表1：Yahoo數(shù)據(jù)集合的統(tǒng)計(jì)信息，m、d、N分別表示經(jīng)過預(yù)處理后的標(biāo)簽數(shù)，數(shù)據(jù)維度和總的實(shí)例數(shù)?！癕axNPI/MinNPI”表示每一個(gè)標(biāo)簽（label）包含的最大/最小的實(shí)例數(shù)。

表1　

實(shí)驗(yàn)中分別采用Science數(shù)據(jù)集和Health數(shù)據(jù)集對實(shí)驗(yàn)結(jié)果進(jìn)行驗(yàn)證。表2、表3分給出了輸入數(shù)據(jù)為Science數(shù)據(jù)集和Health數(shù)據(jù)集時(shí)的實(shí)驗(yàn)結(jié)果。

表2　輸入數(shù)據(jù)為Science的實(shí)驗(yàn)結(jié)果對比

表3　輸入數(shù)據(jù)為Health的實(shí)驗(yàn)結(jié)果對比

表2、表3中粗體數(shù)據(jù)和帶有下劃線的數(shù)據(jù)分別表示對應(yīng)的值最大和次之的數(shù)據(jù)。通過上述兩個(gè)表格所列出的對比數(shù)據(jù)可以看出，CSI-SVM和CSI-ASO兩種方法的分類性能較優(yōu)，也就是說在通過我們所提出新模型的學(xué)習(xí)，并對原始數(shù)據(jù)進(jìn)行重表示后，能有效地提升已有多標(biāo)簽分類方法的分類效果。由公式（1）可以知道，我們在提出模型時(shí)，不僅考慮了從原始數(shù)據(jù)提煉出高層語義的信息，并使用相應(yīng)的標(biāo)簽信息作指導(dǎo)來對數(shù)據(jù)進(jìn)行重表示，充分體現(xiàn)了多標(biāo)簽之間含有共享信息的特點(diǎn)。

5　結(jié)語

本文基于多標(biāo)簽之間的共享信息提出了一個(gè)新的模型，經(jīng)過此模型的學(xué)習(xí)，可以得到一個(gè)低維的數(shù)據(jù)與標(biāo)簽之間的共享空間的關(guān)系變量，即從原始數(shù)據(jù)中提取出高層的語義信息。通過學(xué)習(xí)到的這個(gè)變量，將原始數(shù)據(jù)映射到一個(gè)低維的共享空間中，即對原始數(shù)據(jù)進(jìn)行重表示，將重表示后的數(shù)據(jù)利用已有的多標(biāo)簽分類方法進(jìn)行分類學(xué)習(xí)。經(jīng)過實(shí)驗(yàn)可以知道，將數(shù)據(jù)進(jìn)行重表示后，在一定程度上提高了多標(biāo)簽學(xué)習(xí)的分類效果，從而也驗(yàn)證了標(biāo)簽之間的共享信息對于多標(biāo)簽分類的重要性。

隨著多標(biāo)簽學(xué)習(xí)技術(shù)的不斷發(fā)展，多標(biāo)簽分類被應(yīng)用到各個(gè)領(lǐng)域。如何更好地挖掘和使用標(biāo)簽之間的共享信息，從而提高分類效果，是未來主要的研究課題。

[1]SchapireRE,SingerY.BoosTexter:a Boosting-Based System for Text Categorization.Machine Learning,2000,39（2-3）:135～168

[2]McCallum A.Multi-Label Text Classification with a Mixture Model Trained by EM.In:Working Notes of the AAAI'99 Workshop on Text Learning.MenloPark,CA:AAAI Press,1999

[3]ElisseeffA,Weston J.A Kernel Method for Multi-Labelled Classification.In:Dietterich TG,BeckerS,GhahramaniZ,eds.Advances in Neural Information Processing Systems14.Cambridge,MA:MIT Press,2002：681～687

[4]Min-Ling Zhang.Learning from Multi-Label Data.School of Computer Science&Engineering,Southeast University,China

[5]Grigorios Tsoumakes,IoannisKatakis.Multi-Label Classification:An Overview.Deptofinformatics,Aristotle University of Thessaloniki, 54124,Greece

[6]S.Ji,L.Tang,S.Yu,J.Ye.Extracting Shared Subspace for Multi-Label Classification.In Proceedings of the 14th ACM SIGKDD Conference on Knowledge Discovery and Data Mining,Las Vegas,NV,2008:381～389

[7]M.-L.Zhang，KZhang.Multi-Label Learning by Exploiting Label Dependency.in Proceedings of the 16th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining,Washington D.C.,2010：999～1007

[8]M-L Zhang,KZhang.Multi-Label Learning by Exploiting Label Dependency.InProceedings of the 16th ACM SIGKDD International Conference on Knowledge Discover and Data Mining,KDD`10

[9]On Label Dependence and Loss Minimization in Multi-Label Classification.Machine Learning,vol.88,no.1-2,pp.5-45,2012

[10]Y.Yang，J.O.Pedersen.A Comparative Study on Feature Selection in Text Categorization.In Proceedings of the Fourteenth International Conference on Machine Learning,pages 412～420,1997

[11]Lewis P M.The Characteristic Selection Problem in Recognition System[J].IRE Transaction on Information Theory,1962,8:171～178

[12]N.Ueda，K.Saito.Parametric Mixture Models for Multi-Labeled Text.In Advances in Neural Information Processing Systems 15, pages 721～728.2002

[13]H.Kazawa,T.Izumitani,H.Taira,E.Maeda.Maximal Margin Labeling for Multi-Topic Text Categorization.In Advances in Neural Information Processing Systems 17,pages 649～656，2005

[14]N.Ueda，K.Saito.Single-Shot Detection of Multiple Categories of Text Using Parametric Mixture Models.In Proceedings of the Eighth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining,pages 626～631,2002

Multi-Label Learning;Shared Subspaces;Data Representation

Research on the Multi-Label Learning Model Based on Shared Subspaces

ZOU Shan
（Institute of Computer and Information Technology，Beijing Jiaotong University，Beijing 100044）

In the multi-label classification problems,multiple labels share the same input space,but there are some correlations between different instances of the same label,so in the study of such problems,correlation studies between labels become particularly important.Existing multi-label learning for relevant research between the labels are on the original data,and we hope to re-represent the original data,highlevel semantic information extracted from high-dimensional data,mapping from the original input space to a low-dimensional subspace, in the case of class standard reflects the characteristics of the information as a guide to share information between class standard.Then uses the existing multi-label classification method to classify.Multiples Web classification tasks,experimental results show that this method is to some extent improve the classification results.

1007-1423（2015）14-0033-04

10.3969/j.issn.1007-1423.2015.14.008

鄒珊（1990-），女，內(nèi)蒙古赤峰人，碩士研究生，研究方向?yàn)闄C(jī)器學(xué)習(xí)

2015-03-20

2015-04-22