李 娜，潘志松，任義強(qiáng)，李國(guó)朋，蔣銘初

1.中國(guó)人民解放軍理工大學(xué) 指揮信息系統(tǒng)學(xué)院，南京 210007

2.中國(guó)電子科技集團(tuán)公司 第三十二研究所，上海 201808

3.西門(mén)子電力自動(dòng)化有限公司，南京 211100

4.西安通信學(xué)院，西安 710106

兩重稀疏約束的多標(biāo)記社團(tuán)分類算法*

李 娜1,2，潘志松1+，任義強(qiáng)3，李國(guó)朋1,4，蔣銘初1

1.中國(guó)人民解放軍理工大學(xué) 指揮信息系統(tǒng)學(xué)院，南京 210007

2.中國(guó)電子科技集團(tuán)公司 第三十二研究所，上海 201808

3.西門(mén)子電力自動(dòng)化有限公司，南京 211100

4.西安通信學(xué)院，西安 710106

LI Na,PAN Zhisong,REN Yiqiang,et al.Multi-label community classification method based on double sparse representation.Journal of Frontiers of Computer Science and Technology,2017,11(6)：959-971.

在多標(biāo)記研究中，對(duì)于標(biāo)記間相關(guān)性的利用已經(jīng)越來(lái)越廣泛，從而標(biāo)記關(guān)系的展示就很有必要。相對(duì)以往的研究而言，由于多標(biāo)記數(shù)據(jù)的高維特征，在訓(xùn)練過(guò)程中極為繁瑣耗時(shí)，稀疏優(yōu)化就尤為關(guān)鍵；同時(shí)標(biāo)記相關(guān)性的內(nèi)涵沒(méi)有經(jīng)過(guò)深入挖掘，因此如何更方便有效地進(jìn)行多標(biāo)記分類以及研究所有標(biāo)記之間的相關(guān)性顯得尤為必要。提出了一種基于兩重稀疏約束的多標(biāo)記社團(tuán)分類算法，該算法首先將?1/?2正則化應(yīng)用到多標(biāo)記數(shù)據(jù)的稀疏表示過(guò)程，為后面的研究提供便利條件；其次在多標(biāo)記關(guān)系基礎(chǔ)上應(yīng)用基于?1范數(shù)正則化的社團(tuán)發(fā)現(xiàn)算法，有效地對(duì)標(biāo)記進(jìn)行社團(tuán)劃分，直觀展示出標(biāo)記關(guān)系的內(nèi)涵。實(shí)驗(yàn)證明該方法能夠快速、準(zhǔn)確地進(jìn)行多標(biāo)記分類，并且能夠準(zhǔn)確展示標(biāo)記關(guān)系。

多標(biāo)記；標(biāo)記關(guān)系；非負(fù)矩陣分解（NMF）；?1/?2范數(shù)；?1范數(shù)

1 引言

近年來(lái)，現(xiàn)實(shí)生活中的各式數(shù)據(jù)在不同領(lǐng)域構(gòu)成了各種各樣的網(wǎng)絡(luò)，如人員關(guān)系網(wǎng)、郵件系統(tǒng)網(wǎng)絡(luò)、分子結(jié)構(gòu)網(wǎng)絡(luò)等。不管是社會(huì)系統(tǒng)、信息系統(tǒng)，還是生物系統(tǒng)領(lǐng)域，這些網(wǎng)絡(luò)都真實(shí)地存在于人們的社會(huì)生活中。如今人們對(duì)于網(wǎng)絡(luò)的研究已經(jīng)轉(zhuǎn)向了實(shí)際的網(wǎng)絡(luò)，實(shí)際網(wǎng)絡(luò)通常由若干個(gè)社團(tuán)組成，人們通過(guò)對(duì)社團(tuán)的挖掘來(lái)獲取網(wǎng)絡(luò)中的隱含信息。與此同時(shí)，在現(xiàn)實(shí)生活中人們對(duì)于對(duì)象的研究也不斷深化，往往將對(duì)象賦予多種標(biāo)記，從而體現(xiàn)出對(duì)象的多重含義。比如對(duì)于一封郵件來(lái)說(shuō)，它的內(nèi)容可能同時(shí)包含了身份信息、個(gè)人情緒，以及與外界的相關(guān)聯(lián)系；對(duì)于一個(gè)分子來(lái)說(shuō)，它既可以按結(jié)構(gòu)標(biāo)識(shí)，亦可以按功能標(biāo)識(shí)。因此，對(duì)于現(xiàn)實(shí)生活中的事物來(lái)說(shuō)，它的標(biāo)記同樣具有關(guān)聯(lián)，能夠構(gòu)成網(wǎng)絡(luò)，形成某些社團(tuán)。在多標(biāo)記的研究中，一些標(biāo)記對(duì)于對(duì)象來(lái)說(shuō)可能并沒(méi)有重要的相關(guān)性，比如文本預(yù)處理過(guò)程中詞干的提取，一般文檔庫(kù)的文本中出現(xiàn)頻率超過(guò)80%的詞對(duì)檢索過(guò)程根本不起作用[1]，然而這些停用詞卻是出現(xiàn)最多的文字；又如在郵件系統(tǒng)Enron數(shù)據(jù)集[2]中，有些標(biāo)記在53個(gè)標(biāo)記中的作用遠(yuǎn)不如第45個(gè)標(biāo)記——保密顯得重要。因此，若能夠找到一種稀疏方法，將不必要的標(biāo)記過(guò)濾，同時(shí)找到最重要的標(biāo)記信息，那么就能對(duì)多標(biāo)記的社團(tuán)結(jié)構(gòu)進(jìn)行更快的研究，并且找到社團(tuán)中的骨干節(jié)點(diǎn)，這對(duì)于社團(tuán)的含義描述有著重要的意義。

稀疏（sparsity）是最近幾年機(jī)器學(xué)習(xí)和計(jì)算機(jī)視覺(jué)領(lǐng)域?qū)τ诟呔S數(shù)據(jù)的研究熱點(diǎn)之一[3]。也就是在一個(gè)足夠大的訓(xùn)練樣本空間內(nèi)，對(duì)于一個(gè)類別的物體，可以大致地由訓(xùn)練樣本中同類的樣本子空間線性表示，因此當(dāng)該物體由整個(gè)樣本空間表示時(shí)，其表示的系數(shù)是稀疏的。當(dāng)前對(duì)于數(shù)據(jù)的稀疏表示，是將稀疏方法應(yīng)用于數(shù)據(jù)的降維預(yù)處理過(guò)程中，并在圖像去噪、圖像復(fù)原等方面取得了重大成功。通過(guò)稀疏可以得到數(shù)據(jù)最為重要的屬性，然而對(duì)于標(biāo)記的稀疏卻沒(méi)有找到合適的優(yōu)化策略。

網(wǎng)絡(luò)的社團(tuán)結(jié)構(gòu)[4]指相互之間具有比較大的相似性而與網(wǎng)絡(luò)中的其他部分有著很大不同的節(jié)點(diǎn)的群。在社團(tuán)內(nèi)部，節(jié)點(diǎn)之間的聯(lián)系非常緊密，社團(tuán)之間的聯(lián)系相對(duì)比較稀疏[5]。如在社會(huì)網(wǎng)絡(luò)中，某一社團(tuán)的人們與其他社團(tuán)有著不一樣的特質(zhì)。對(duì)網(wǎng)絡(luò)中節(jié)點(diǎn)尋找社團(tuán)結(jié)構(gòu)并對(duì)其進(jìn)行分析是了解現(xiàn)實(shí)生活中各種網(wǎng)絡(luò)組織的一種重要方法，并在多個(gè)領(lǐng)域有著重要的應(yīng)用。然而社團(tuán)結(jié)構(gòu)在多標(biāo)記數(shù)據(jù)集中的應(yīng)用還不是很多，而多標(biāo)記分類方法的應(yīng)用卻越來(lái)越廣泛。在多標(biāo)記分類算法中，現(xiàn)有算法已經(jīng)越來(lái)越側(cè)重于對(duì)標(biāo)記間相互關(guān)系的利用，對(duì)于標(biāo)記關(guān)系的獲取形式也有多種[6]，多標(biāo)記之間的相關(guān)性同樣可以構(gòu)成具有標(biāo)記節(jié)點(diǎn)關(guān)聯(lián)的網(wǎng)絡(luò)結(jié)構(gòu)，并從該結(jié)構(gòu)中分析標(biāo)記之間隱含的相關(guān)信息。對(duì)待該網(wǎng)絡(luò)結(jié)構(gòu)，可以應(yīng)用現(xiàn)有的社團(tuán)發(fā)現(xiàn)算法進(jìn)行分析。

目前在有效的社團(tuán)組織發(fā)現(xiàn)方法中，非負(fù)矩陣分解（non-negative matrix factorization，NMF）[7-9]就是社團(tuán)發(fā)現(xiàn)方法的一個(gè)非常有用的工具，與其他矩陣分解方法相比，NMF特殊之處在于其通過(guò)將非負(fù)性約束引入矩陣分解過(guò)程中，利用非負(fù)的低維矩陣對(duì)高維矩陣進(jìn)行近似，這種約束會(huì)得到原始數(shù)據(jù)基于部分的表示，從而更好地反映原始數(shù)據(jù)的局部特征。若對(duì)標(biāo)記所屬社團(tuán)矩陣進(jìn)行稀疏優(yōu)化，則標(biāo)記的信息就會(huì)更明確，同時(shí)也能更好地理解標(biāo)記之間的相關(guān)性。因此，對(duì)于多標(biāo)記社團(tuán)發(fā)現(xiàn)算法，也能夠得到多標(biāo)記的社團(tuán)結(jié)構(gòu)，明確每個(gè)標(biāo)記社團(tuán)的含義。本文在稀疏表示的基礎(chǔ)上，針對(duì)多標(biāo)記數(shù)據(jù)高維冗余特點(diǎn)，以及多標(biāo)記社團(tuán)稀疏性解釋不強(qiáng)，矩陣效果不夠完善，非負(fù)矩陣分解工作沒(méi)有對(duì)標(biāo)記之間的相互關(guān)系進(jìn)行考慮，基于稀疏具有特征選擇與可解釋性的優(yōu)點(diǎn)，對(duì)多標(biāo)記的社團(tuán)信息采用兩重稀疏表示手段：由于多標(biāo)記數(shù)據(jù)集屬于高維數(shù)據(jù)，本身具有一定稀疏性，首先將稀疏優(yōu)化應(yīng)用到多標(biāo)記數(shù)據(jù)集降維過(guò)程中，采用了?1/?2范數(shù)正則化[10-12]優(yōu)化方法；其次在多標(biāo)記的社團(tuán)劃分中采用了第二重的稀疏表示方法——?1范數(shù)[13-15]，目的是使得多標(biāo)記社團(tuán)劃分結(jié)果更加明晰，社團(tuán)分類能夠更好地反映標(biāo)記之間的相關(guān)性與無(wú)關(guān)性。

本文首先對(duì)兩重稀疏約束的多標(biāo)記社團(tuán)分類相關(guān)工作進(jìn)行介紹，隨后詳細(xì)說(shuō)明了基于兩重稀疏約束的多標(biāo)記社團(tuán)分類方法，并在已有數(shù)據(jù)集上將本文涉及內(nèi)容與現(xiàn)有的一些方法進(jìn)行對(duì)比，測(cè)試在多種實(shí)際數(shù)據(jù)集下的性能。最后進(jìn)行總結(jié)。

2 相關(guān)工作介紹

2.1 多標(biāo)記社團(tuán)發(fā)現(xiàn)概念

現(xiàn)有的多標(biāo)記工作對(duì)于標(biāo)記相關(guān)性進(jìn)行了充分的學(xué)習(xí)。由于樣本數(shù)目較大，標(biāo)記數(shù)量并不單一，標(biāo)記間的關(guān)聯(lián)不明顯，目前已經(jīng)有許多工作嘗試挖掘和利用標(biāo)記之間的關(guān)系。在現(xiàn)有多標(biāo)記學(xué)習(xí)中，Huang等人在文獻(xiàn)[6]中提出了多標(biāo)記重用評(píng)分概念來(lái)有效反映標(biāo)記之間的關(guān)聯(lián)。該工作的多標(biāo)記重用（multi-label hypothesis reuse，MAHR）算法中，根據(jù)標(biāo)記間相互作用得到標(biāo)記間的評(píng)分矩陣S，該矩陣可以量化成為多標(biāo)記的關(guān)系矩陣，而社團(tuán)分解中的NMF算法正是根據(jù)節(jié)點(diǎn)間的關(guān)系矩陣對(duì)節(jié)點(diǎn)進(jìn)行劃分。由于現(xiàn)有多標(biāo)記學(xué)習(xí)工作并未明確指出多標(biāo)記社團(tuán)結(jié)構(gòu)內(nèi)涵，同時(shí)稀疏的社團(tuán)結(jié)構(gòu)對(duì)多標(biāo)記工作的意義也有待探索，于是本文希望能夠利用NMF算法挖掘出多標(biāo)記關(guān)系矩陣并揭示多標(biāo)記的社團(tuán)結(jié)構(gòu)，對(duì)標(biāo)記的社團(tuán)結(jié)構(gòu)作出明確解釋，使得對(duì)多標(biāo)記關(guān)系的研究更清晰且有意義。

2.2 非負(fù)矩陣分解

非負(fù)矩陣分解是一種常用的矩陣分解方法，它將一個(gè)元素非負(fù)的矩陣分解為兩個(gè)非負(fù)矩陣的乘積[7-9]。傳統(tǒng)NMF問(wèn)題具體描述為：原始非負(fù)矩陣V∈Rm×n，找到兩個(gè)適當(dāng)?shù)男碌姆秦?fù)矩陣Wm×r和Hr×n，使得V分解成為這兩個(gè)非負(fù)矩陣的乘積，即V≈WH，并且使分解誤差盡可能的小。其中W為矩陣的基矩陣，H為系數(shù)矩陣。r

自Lee和Seung提出NMF思想（文獻(xiàn)[8-9]），非負(fù)矩陣分解在科學(xué)界廣受關(guān)注并且不斷發(fā)展。文獻(xiàn)[16]中，Wang等人提出了基于有向和無(wú)向圖的新的社團(tuán)發(fā)現(xiàn)表達(dá)式中的一個(gè)點(diǎn)，表示x(i,j)屬于第j個(gè)社團(tuán)的權(quán)重，Sk×k表示各個(gè)社團(tuán)之間的相互關(guān)系。與以往算法分解成兩層矩陣不同的是，本算法分為三層，有助于得到社團(tuán)結(jié)構(gòu)。文獻(xiàn)[17]中，Nguyen等人針對(duì)文獻(xiàn)[18]對(duì)于有加權(quán)的有向圖性能不是很好的缺點(diǎn)，利用KL散度距離作為度量，提出了利用乘性更新（multiplicative update rules）的算法。然而，上述文獻(xiàn)都沒(méi)有考慮矩陣稀疏性的特點(diǎn)。Zhang等人[19]認(rèn)為，只有非負(fù)的約束并不能完全刻畫(huà)社團(tuán)結(jié)構(gòu)，他們利用?1范數(shù)描述矩陣的稀疏性，并利用坐標(biāo)下降法（coordinate descent）求解。該算法對(duì)有向加權(quán)圖求解性能較好，針對(duì)重疊結(jié)構(gòu)的社團(tuán)發(fā)現(xiàn)也有意義。上述方法雖然都對(duì)社團(tuán)的發(fā)現(xiàn)算法進(jìn)行了詳細(xì)討論，但是對(duì)于真實(shí)的社團(tuán)發(fā)現(xiàn)來(lái)講，除了連接關(guān)系，他們沒(méi)有考慮利用諸如標(biāo)簽、留言等其他的相互關(guān)系矩陣來(lái)實(shí)現(xiàn)社團(tuán)發(fā)現(xiàn)。Tang等人[20]針對(duì)社會(huì)網(wǎng)絡(luò)，利用標(biāo)簽等相互關(guān)系進(jìn)行社團(tuán)結(jié)構(gòu)的劃分，并利用交替迭代的方法求解。但是其對(duì)于有權(quán)重的矩陣來(lái)講性能不是很好。對(duì)于現(xiàn)實(shí)中的社團(tuán)結(jié)構(gòu)挖掘來(lái)看，這些方法忽視了對(duì)社團(tuán)之間關(guān)系的約束，導(dǎo)致算法的性能不是很穩(wěn)定。

2.3 ?1范數(shù)與?1/?2范數(shù)正則化問(wèn)題

稀疏是個(gè)經(jīng)典話題，即是用少量重要元素代替大量的數(shù)據(jù)，使得大多數(shù)元素為0而少量元素不為0。由于在高維數(shù)據(jù)中對(duì)于數(shù)據(jù)的操作是非常費(fèi)力的，而稀疏性對(duì)于解決高維度數(shù)據(jù)的計(jì)算量問(wèn)題是非常有效的。機(jī)器學(xué)習(xí)中的一個(gè)規(guī)則化函數(shù)?2范數(shù)||W||2是應(yīng)用較廣泛的一個(gè)優(yōu)化函數(shù)，然而其在實(shí)際測(cè)試過(guò)程中不具有產(chǎn)生稀疏解的能力。而?0范數(shù)是指向量中非0的元素的個(gè)數(shù)，也就是用來(lái)找到方程解中具有最小數(shù)目的非零項(xiàng)，然而在求解過(guò)程中是一個(gè)NP問(wèn)題。因此，引出了?1范數(shù)最小化問(wèn)題，即用?1范數(shù)來(lái)代替?0與?2范數(shù)，以此來(lái)找到近似解。

大多數(shù)現(xiàn)有的稀疏學(xué)習(xí)工作是基于?1范數(shù)正則化的變種。由于?1范數(shù)正則化在應(yīng)用中方便的凸性、強(qiáng)大的理論保證等，其應(yīng)用越來(lái)越廣泛?，F(xiàn)今該方法的應(yīng)用已經(jīng)促進(jìn)了線性回歸[21]、線性判別分析[22]、偏最小二乘法[13]、邏輯回歸[14-15]等模型的稀疏化發(fā)展。?1范數(shù)正則化得到的目標(biāo)函數(shù)通常描述如下：

其中，X∈Rm×n表示權(quán)重矩陣;λ為正則化參數(shù);X中的每一行都是一個(gè)特征向量。

近期在機(jī)器學(xué)習(xí)和數(shù)學(xué)統(tǒng)計(jì)領(lǐng)域，稀疏學(xué)習(xí)工作已經(jīng)由?1范數(shù)正則化延伸到?1/?q的正則化[10-12]。當(dāng)q＞1時(shí)，?1/?q正則化在產(chǎn)生的模型中能夠促進(jìn)組稀疏，因此常常應(yīng)用到分類和回歸問(wèn)題中。圖1展示了該優(yōu)化問(wèn)題。

?1/?q范數(shù)正則化得到的目標(biāo)函數(shù)通常描述如下：

Fig.1 Illustration of data matrixA,target matrixY, and weight matrixX圖1 數(shù)據(jù)矩陣A、目標(biāo)矩陣Y與權(quán)重矩陣X關(guān)系展示

其中，A為m×n維矩陣；Y=[y1,y2,…,yk]為m×k維矩陣；X=[x1,x2,…,xk]為n×k維矩陣；λ為?1/?q正則化系數(shù)。

本文研究的是多標(biāo)記數(shù)據(jù)分類問(wèn)題，因此采用的兩重稀疏方法是首先利用?1/?q范數(shù)正則化加入到多標(biāo)記數(shù)據(jù)降維中，根據(jù)終止-規(guī)范化-正則化的步驟，對(duì)高維的多標(biāo)記數(shù)據(jù)集進(jìn)行降維，通過(guò)正則化，稀疏的矩陣能夠顯著提高多標(biāo)記分類的效率。其次將?1范數(shù)正則化應(yīng)用到多標(biāo)記社團(tuán)分類中。在文獻(xiàn)[16]提到的NMF三層分解結(jié)構(gòu)中，通過(guò)向其中加入正則化稀疏項(xiàng)λ，并制定矩陣的更新規(guī)則，使得多標(biāo)記關(guān)系在進(jìn)行社團(tuán)結(jié)構(gòu)劃分時(shí)能夠取得更顯著的社團(tuán)效果及稀疏度，這有助于理解多標(biāo)記社團(tuán)結(jié)構(gòu)的含義。該類優(yōu)化問(wèn)題首先得到通過(guò)稀疏降維后的數(shù)據(jù)，再次得到多標(biāo)記所屬社團(tuán)的稀疏矩陣結(jié)構(gòu)，排除相關(guān)性不強(qiáng)的標(biāo)記干擾，使得每個(gè)社團(tuán)保留最有用的標(biāo)記信息。目標(biāo)是將多標(biāo)記數(shù)據(jù)充分稀疏，在目標(biāo)函數(shù)上增加稀疏約束條件，使分解后得到的基矩陣W盡可能的稀疏，從而更加節(jié)省存儲(chǔ)空間，結(jié)構(gòu)更加清晰，標(biāo)記相關(guān)性更能夠充分展示。

3 基于兩重稀疏約束的多標(biāo)記社團(tuán)分類方法

以下主要介紹在多標(biāo)記數(shù)據(jù)集中兩重稀疏約束方法作用的不同范圍與步驟，包括基于?1/?2范數(shù)稀疏性約束的多標(biāo)記數(shù)據(jù)降維與基于?1范數(shù)稀疏性約束的多標(biāo)記社團(tuán)分類。

3.1 基于?1/?2范數(shù)稀疏性約束的多標(biāo)記降維

定義1設(shè)多標(biāo)記數(shù)據(jù)集為：

其中，n表示多標(biāo)記數(shù)據(jù)集樣本維數(shù)；x表示樣本的特征向量；y表示樣本標(biāo)記向量，且y∈{-1,+1}。根據(jù)多標(biāo)記社團(tuán)發(fā)現(xiàn)算法的研究以及對(duì)矩陣分解稀疏性的研究，需要?1/?q正則化解決多分類的最小二乘問(wèn)題。這里令q=2，因此基于?1/?2范數(shù)正則化稀疏的多標(biāo)記數(shù)據(jù)集優(yōu)化函數(shù)通常描述如下：

其中，A∈Rm×n為原始數(shù)據(jù)矩陣；Y∈Rm×k為目標(biāo)標(biāo)記矩陣。優(yōu)化的目標(biāo)就是尋找稀疏的權(quán)重矩陣X，從而得到使得A稀疏后的降維數(shù)據(jù)。詳見(jiàn)參考文獻(xiàn)[23]。

3.2 本文算法

利用NMF算法的稀疏性能夠快速提取網(wǎng)絡(luò)重要節(jié)點(diǎn)所屬社團(tuán)這一特點(diǎn)，本文將稀疏性應(yīng)用到社團(tuán)發(fā)現(xiàn)工作中。主要對(duì)多標(biāo)記社團(tuán)劃分的工作進(jìn)行改進(jìn)，將多標(biāo)記關(guān)系矩陣運(yùn)用基于?1范數(shù)稀疏約束的非負(fù)矩陣分解算法，得到多標(biāo)記的社團(tuán)分類。基于兩重稀疏性約束的多標(biāo)記社團(tuán)分類方法步驟如下。

（1）輸入：多標(biāo)記訓(xùn)練數(shù)據(jù)集特征矩陣A，標(biāo)記矩陣Y，正則化參數(shù)λ，訓(xùn)練輪數(shù)T，MAHR訓(xùn)練基分類器C。

（2）輸出：多標(biāo)記所屬社團(tuán)矩陣G。

（4）利用?1/?2范數(shù)正則化對(duì)多標(biāo)記數(shù)據(jù)集A進(jìn)行降維，得到稀疏后的降維矩陣A*。

（5）利用MAHR算法，對(duì)A*進(jìn)行相應(yīng)的訓(xùn)練，得到綜合模型Z，標(biāo)記關(guān)系矩陣所需權(quán)重β與α。

（6）根據(jù)Z、β與α，得出多標(biāo)記間評(píng)分矩陣S，其中根據(jù)評(píng)分得到關(guān)系矩陣規(guī)范化并重組，得到多標(biāo)記關(guān)系矩陣V。

（7）根據(jù)NMF規(guī)則，將矩陣V分解為三層結(jié)構(gòu)，即V≈XSXT。

更新X：xi+1=xi+Δx。其中Δx為添加稀疏正則化項(xiàng)的稀疏基矩陣增量。

更新S：si+1=si+Δs。其中Δs為社團(tuán)關(guān)系矩陣增量。

（8）從矩陣X中找到每個(gè)標(biāo)記的最大值與所屬社團(tuán)標(biāo)號(hào)，得到多標(biāo)記節(jié)點(diǎn)所屬社團(tuán)C。

其中k代表社團(tuán)數(shù)量，根據(jù)算法中系數(shù)矩陣X來(lái)找到多標(biāo)記所屬的社團(tuán)分類。矩陣X表示一個(gè)二維的數(shù)量為k的社團(tuán)，行對(duì)應(yīng)標(biāo)記節(jié)點(diǎn)類別，列對(duì)應(yīng)社團(tuán)類別，矩陣X的每一行最大的元素所對(duì)應(yīng)的列則可標(biāo)識(shí)為對(duì)應(yīng)標(biāo)記所在的社團(tuán)類別。

基于兩重稀疏性約束的多標(biāo)記社團(tuán)分類方法就是在原目標(biāo)函數(shù)上增加約束條件來(lái)獲取盡可能稀疏的標(biāo)記所屬社團(tuán)的分類信息。鑒于當(dāng)前工作中基于?1/?2范數(shù)稀疏約束的數(shù)據(jù)降維方法應(yīng)用較廣，本文將工作重點(diǎn)放在多標(biāo)記社團(tuán)分類過(guò)程中。在前面的基礎(chǔ)上考慮對(duì)非負(fù)向量X加?1范數(shù)約束條件，即最小化轉(zhuǎn)換為矩陣的形式就是為了使矩陣X充分稀疏，最小化矩陣X中所有元素的和。

因此，加稀疏的多標(biāo)記社團(tuán)劃分為三層模式，V≈XSXT。V的轉(zhuǎn)置形式VT≈(XSXT)T=XSTXT。

其中，V表示有向加權(quán)圖的鄰接矩陣；S描述社區(qū)之間的權(quán)值關(guān)系；X描述節(jié)點(diǎn)屬于某個(gè)社區(qū)的權(quán)值，并且X中元素值在[0,1]之間。表示Frobenius范數(shù)代表能夠使得x中的元素更好地屬于某一社團(tuán)的?1范數(shù)模型，用來(lái)控制模型的稀疏度，讓節(jié)點(diǎn)盡可能被清晰地劃分。也就是說(shuō)，通過(guò)控制矩陣X中每一個(gè)多標(biāo)記元素x(i,j)屬于所有社團(tuán)的稀疏度（使得多標(biāo)記所屬社團(tuán)的權(quán)重盡可能多地為0），用來(lái)達(dá)到稀疏效果的最優(yōu)化。優(yōu)化目標(biāo)中的λ就能夠平衡矩陣X的稀疏性與精確性，使稀疏的結(jié)果準(zhǔn)確度更高。根據(jù)文獻(xiàn)[24]的方法，得到該算法的更新規(guī)則[25]，即：

因此，將L分別對(duì)X和S*求導(dǎo)，得：

更新X、S的增量為：

最終得到了稀疏后的標(biāo)記所屬社團(tuán)關(guān)系矩陣。

4 實(shí)驗(yàn)分析

4.1 實(shí)驗(yàn)設(shè)置

本實(shí)驗(yàn)共使用1個(gè)人工數(shù)據(jù)集和3個(gè)真實(shí)數(shù)據(jù)集，人工數(shù)據(jù)集為Data，是34×34維的0-1對(duì)稱關(guān)系矩陣，真實(shí)數(shù)據(jù)集包括郵件分析數(shù)據(jù)集Enron[26]、文獻(xiàn)管理數(shù)據(jù)集BibTex[27]和生物領(lǐng)域的基因數(shù)據(jù)集Genbase[28]，表1給出了這些數(shù)據(jù)集的統(tǒng)計(jì)信息。通過(guò)基于兩重稀疏性約束的多標(biāo)記社團(tuán)分類方法，首先得到降維后的多標(biāo)記特征矩陣，再次根據(jù)MAHR算法得到多標(biāo)記的評(píng)分矩陣，進(jìn)而應(yīng)用?1范數(shù)約束得到多標(biāo)記社團(tuán)關(guān)系，并對(duì)多標(biāo)記所屬社團(tuán)矩陣進(jìn)行解釋。

Table 1 Experimental datasets表1 實(shí)驗(yàn)數(shù)據(jù)集

實(shí)驗(yàn)環(huán)境操作系統(tǒng)為Windows7，工具軟件為Matlab R2013a。

4.2 結(jié)果分析

本節(jié)列舉出根據(jù)加稀疏約束的多標(biāo)記社團(tuán)分類算法得到的標(biāo)記所屬矩陣關(guān)系，并在4個(gè)數(shù)據(jù)集上進(jìn)行實(shí)驗(yàn)效果驗(yàn)證。根據(jù)數(shù)據(jù)集的維數(shù)、標(biāo)記數(shù)量等特點(diǎn)，將上述幾個(gè)數(shù)據(jù)集劃分為個(gè)數(shù)不同的社團(tuán)，并且通過(guò)本文算法得到標(biāo)記所屬社團(tuán)矩陣。矩陣分解后的系數(shù)矩陣能反映分解的效果，因此對(duì)分解后的系數(shù)矩陣X及算法的一些指標(biāo)進(jìn)行分析，并比較多標(biāo)記關(guān)系，獲取所需的訓(xùn)練輪數(shù)與各項(xiàng)指標(biāo)的關(guān)系。其中“↑”表示越大越好，“↓”代表越小越好，“·”表示在對(duì)應(yīng)指標(biāo)比較上，本文算法優(yōu)于比較方法。

根據(jù)文獻(xiàn)[29]提出的稀疏度度量公式對(duì)分解后的基矩陣和系數(shù)矩陣進(jìn)行度量，公式如下：

其中，n代表向量X的維度；m表示向量X的元素個(gè)數(shù)；xi代表向量X第i個(gè)元素的值。Sparseness(x)的值在[0,1]之間，并且值越接近1表示向量的稀疏度越高。本文對(duì)比的是X中所有列向量的稀疏度取平均值。

矩陣X的模塊度是目前常用的一種衡量網(wǎng)絡(luò)社區(qū)結(jié)構(gòu)強(qiáng)度的方法[30-31]，值越接近1表示網(wǎng)絡(luò)劃分的社團(tuán)結(jié)構(gòu)強(qiáng)度越好。公式為：

其中，m為網(wǎng)絡(luò)中邊的總數(shù)；i、j分別為網(wǎng)絡(luò)中的節(jié)點(diǎn)；Vij表示i、j的鄰接關(guān)系；N為節(jié)點(diǎn)集合；ki為點(diǎn)i的度；Ci和Cj分別表示點(diǎn)i、j所在的兩個(gè)社區(qū)。

分解誤差表示矩陣分解后與原矩陣的誤差，根據(jù)文獻(xiàn)[32]用Frobenius范數(shù)衡量，誤差值越小表示分離效果越好。公式為:

分解時(shí)間表示幾個(gè)算法在對(duì)多標(biāo)記關(guān)系矩陣處理并進(jìn)行矩陣分解過(guò)程中所需要的時(shí)間，時(shí)間越短表示算法處理速度越快。

4.2.1 性能比較

表2~表5分別統(tǒng)計(jì)了表1中幾個(gè)數(shù)據(jù)集的實(shí)驗(yàn)結(jié)果。具體內(nèi)容如下：將Data劃分為5個(gè)社團(tuán)，Genbase的多標(biāo)記關(guān)系劃分為3個(gè)社團(tuán)，Enron數(shù)據(jù)集的多標(biāo)記關(guān)系劃分為2個(gè)社團(tuán)，BibTex劃分為22個(gè)社團(tuán)。參加比較的算法有應(yīng)用?2范數(shù)正則化的NMTFSQ[19]社團(tuán)發(fā)現(xiàn)算法，應(yīng)用KL距離（Kullback-Leibler divergence）的NMTFKL[19]社團(tuán)發(fā)現(xiàn)算法以及不加任何稀疏約束的基于NMF的社團(tuán)發(fā)現(xiàn)算法。

表2展示了人工數(shù)據(jù)集Data上的實(shí)驗(yàn)結(jié)果。其中令本文算法中?1范數(shù)的正則化項(xiàng)λ=1.5，劃分的社團(tuán)個(gè)數(shù)k=5。由于Data數(shù)據(jù)集已經(jīng)是元素間的關(guān)系矩陣，那么對(duì)于基于?1/?q范數(shù)稀疏性約束的多標(biāo)記數(shù)據(jù)降維步驟省略，直接進(jìn)入社團(tuán)發(fā)現(xiàn)過(guò)程。

Table 2 Average performance for this paper method and compared methods in Data表2 Data數(shù)據(jù)集中本文算法與比較算法的平均性能

從表2中可以看出，本文算法在模塊度、分解誤差、稀疏度3個(gè)指標(biāo)上取得了比其他社團(tuán)發(fā)現(xiàn)方法更優(yōu)的效果。而在分解時(shí)間方面，NMTFSQ所用時(shí)間最長(zhǎng)，而本文算法與其他算法的結(jié)果相差不大。

表3統(tǒng)計(jì)了上述幾個(gè)數(shù)據(jù)集上的實(shí)驗(yàn)結(jié)果，展示了數(shù)據(jù)集Genbase在λ=1.5，社團(tuán)個(gè)數(shù)k=3，多標(biāo)記關(guān)系訓(xùn)練輪數(shù)為4倍的樣本標(biāo)記維數(shù)(rounds=108)情況下，本文算法同已有的多種非負(fù)矩陣算法的比較結(jié)果。

從表3中可以看出，本文算法同樣在模塊度、分解誤差、稀疏度3個(gè)指標(biāo)上取得了比其他社團(tuán)發(fā)現(xiàn)方法更優(yōu)的效果。而在分解時(shí)間方面，NMTFSQ所用時(shí)間最長(zhǎng)，而本文算法與其他算法的結(jié)果相差不大。

Table 3 Average performance for this paper method and compared methods in Genbase表3 Genbase數(shù)據(jù)集中本文算法與比較算法的平均性能

表4統(tǒng)計(jì)了上述幾個(gè)數(shù)據(jù)集上的實(shí)驗(yàn)結(jié)果，展示了數(shù)據(jù)集Enron在λ=1.5，社團(tuán)個(gè)數(shù)k=2，多標(biāo)記關(guān)系訓(xùn)練輪數(shù)為3倍的樣本標(biāo)記維數(shù)(rounds=212)情況下，本文算法同已有的多種非負(fù)矩陣算法的比較結(jié)果。

Table 4 Average performance for this paper method and compared methods in Enron表4 Enron數(shù)據(jù)集中本文算法與比較算法的平均性能

從表4中可以看出，本文算法在Enron數(shù)據(jù)集上不是很理想，僅在模塊度和分解誤差兩個(gè)指標(biāo)上表現(xiàn)良好。

表5統(tǒng)計(jì)了上述幾個(gè)數(shù)據(jù)集上的實(shí)驗(yàn)結(jié)果，展示了數(shù)據(jù)集Bibtex在λ=1.5，社團(tuán)個(gè)數(shù)k=22，多標(biāo)記關(guān)系訓(xùn)練輪數(shù)為3倍的樣本標(biāo)記維數(shù)(rounds=477)情況下，本文算法同已有的多種非負(fù)矩陣算法的比較結(jié)果。

根據(jù)表5的結(jié)果不難看出，本文算法在除了分解時(shí)間指標(biāo)以外的其余3個(gè)最有意義的指標(biāo)上取得最好的效果，且優(yōu)勢(shì)比較明顯。

因此，在4個(gè)常用的不同領(lǐng)域的數(shù)據(jù)集中，每個(gè)數(shù)據(jù)集在相同的實(shí)驗(yàn)環(huán)境及參數(shù)設(shè)置條件下，同已有的非負(fù)矩陣分解算法相比，本文算法在模塊度、稀疏度方面達(dá)到了最優(yōu)，而在分解時(shí)間與誤差值方面，同最優(yōu)算法相比，均相差不大，根據(jù)模塊度最大選擇多標(biāo)記社團(tuán)分解算法才具有更高的準(zhǔn)確率。同時(shí)，稀疏度越高表明得到的多標(biāo)記所屬社團(tuán)分類更明確。因?yàn)槲醇酉∈璧墓胶?jiǎn)便，所以從時(shí)間效果分析，未加稀疏的多標(biāo)記社團(tuán)發(fā)現(xiàn)算法時(shí)間最短，而本文算法相對(duì)于NMTFSQ和NMTFKL算法來(lái)說(shuō)，在處理時(shí)間上顯著縮短。

Table 5 Average performance for this paper method and compared methods in BibTex表5 BibTex數(shù)據(jù)集中本文算法與比較算法的平均性能

4.2.2 基于?1/?2范數(shù)稀疏約束的影響

由于本文是基于兩重稀疏約束的算法，那么在第一層稀疏即數(shù)據(jù)加入?1/?2范數(shù)約束對(duì)標(biāo)記關(guān)系的影響需要驗(yàn)證。圖2~圖7分別統(tǒng)計(jì)了表1中幾個(gè)數(shù)據(jù)集在不經(jīng)過(guò)稀疏降維的情況下與基于?1/?2范數(shù)稀疏約束的情況下模塊度與稀疏度的對(duì)比結(jié)果，目的是為了驗(yàn)證稀疏降維有無(wú)保留最重要的屬性以及對(duì)多標(biāo)記關(guān)系的影響。設(shè)3個(gè)數(shù)據(jù)集在降維過(guò)程中的?1/?2范數(shù)正則化項(xiàng)λ12=0.02。

圖2~圖4表示對(duì)于數(shù)據(jù)集Genbase、Enron、Bib-Tex，基于?1/?2范數(shù)稀疏約束進(jìn)行多標(biāo)記數(shù)據(jù)降維后與原特征數(shù)據(jù)在模塊度Q上的效果對(duì)比。圖5~圖7表示對(duì)于數(shù)據(jù)集Genbase、Enron、BibTex，基于?1/?2范數(shù)稀疏約束進(jìn)行多標(biāo)記數(shù)據(jù)降維后與原特征數(shù)據(jù)在稀疏度Sparseness上的效果對(duì)比。比較算法包含本文算法及其他3種算法。

對(duì)于圖2~圖4，從模塊度方面講，原多標(biāo)記的高維數(shù)據(jù)經(jīng)過(guò)?1/?2范數(shù)稀疏降維后再進(jìn)行社團(tuán)劃分的方法，4個(gè)算法在數(shù)據(jù)集Genbase和BibTex上取得了比較好的效果，將不必要的屬性稀疏降維后，模塊度不僅沒(méi)有降低反而有所提高，說(shuō)明降維之后剩余的特征屬性具有更明顯的特征，對(duì)多標(biāo)記數(shù)據(jù)訓(xùn)練過(guò)程中得到的相關(guān)性更有幫助，從而能夠更加明顯地展示出多標(biāo)記的社團(tuán)結(jié)構(gòu)。而在Enron數(shù)據(jù)集上的表現(xiàn)并不令人滿意，模塊度成為負(fù)值，說(shuō)明該數(shù)據(jù)集在稀疏降維后得到的標(biāo)記關(guān)系失去了社團(tuán)的性質(zhì)。

對(duì)于圖5~圖7，同樣可以看出?1/?2范數(shù)稀疏降維對(duì)稀疏度的影響。在數(shù)據(jù)集BibTex的結(jié)果中，除了在NMTFKL算法上稀疏度稍微減小以外，在其他算法上都有所提高，或者是提高幅度不明顯；在數(shù)據(jù)集Enron中，效果差強(qiáng)人意，稀疏度減小幅度并不大；在數(shù)據(jù)集Genbase中，本文算法和NMTFKL算法的稀疏度有所減小，而其余兩個(gè)增大。

Fig.4 Comparison ofQwhether using?1/?2-norm in BibTex圖4 BibTex中有無(wú)?1/?2范數(shù)模塊度比較

Fig.5 Comparison of sparseness whether using?1/?2-norm in Genbase圖5 Genbase中有無(wú)?1/?2范數(shù)稀疏度比較

Fig.6 Comparison of sparseness whether using?1/?2-norm in Enron圖6 Enron中有無(wú)?1/?2范數(shù)稀疏度比較

Fig.7 Comparison of sparseness whether using?1/?2-norm in BibTex圖7 BibTex中有無(wú)?1/?2范數(shù)稀疏度比較

總體來(lái)看，在3個(gè)數(shù)據(jù)集進(jìn)行基于?1/?2范數(shù)稀疏約束后，在個(gè)別數(shù)據(jù)集的個(gè)別算法指標(biāo)上有減弱的效果，但是整體來(lái)說(shuō)趨于穩(wěn)定，甚至模塊度、稀疏度都有增強(qiáng)，社團(tuán)結(jié)構(gòu)更加明顯。由此說(shuō)明，在多標(biāo)記數(shù)據(jù)集降維后，不僅沒(méi)有影響重要特征，反而保留了重要的特征，并能夠?qū)?biāo)記關(guān)系的訓(xùn)練產(chǎn)生影響，從而明確社團(tuán)結(jié)構(gòu)。標(biāo)記社團(tuán)的結(jié)果同完全由原始數(shù)據(jù)訓(xùn)練得到的標(biāo)記關(guān)系差別不大，同時(shí)預(yù)處理的訓(xùn)練時(shí)間因?yàn)橄∈璧淖饔枚蠓葴p少，更加簡(jiǎn)便快捷，加入?1/?2范數(shù)降維后的數(shù)據(jù)處理更為優(yōu)越。

4.2.3 標(biāo)記關(guān)系訓(xùn)練輪數(shù)的影響

在MAHR算法過(guò)程中，標(biāo)記關(guān)系是由算法訓(xùn)練迭代得到，表示了標(biāo)記的相互作用程度大小，因此可以用來(lái)量化標(biāo)記關(guān)系。圖8~圖13給出了數(shù)據(jù)集Genbase、Enron和BibTex在λ=1.5，社團(tuán)個(gè)數(shù)分別為k=3，k=2，k=22時(shí)，模塊度Q和稀疏度Sparseness同多標(biāo)記社團(tuán)關(guān)系的訓(xùn)練輪數(shù)的關(guān)系。

由圖8~圖13可以得出，本文算法在3個(gè)數(shù)據(jù)集中的模塊度基本處于最高的狀態(tài)，且變化較為穩(wěn)定。無(wú)論是在模塊度還是稀疏度方面，本文基于?1稀疏約束的社團(tuán)發(fā)現(xiàn)算法要比不加稀疏約束的普通社團(tuán)發(fā)現(xiàn)算法表現(xiàn)好。雖然在稀疏度方面4個(gè)算法表現(xiàn)有好有壞，但是可以明確的是，隨著多標(biāo)記社團(tuán)關(guān)系訓(xùn)練輪數(shù)的增加，幾個(gè)算法的模塊度和稀疏度整體來(lái)說(shuō)呈增加的趨勢(shì)。這樣的結(jié)果說(shuō)明，訓(xùn)練輪數(shù)增加，得到的多標(biāo)記間的相關(guān)聯(lián)系就越緊密，關(guān)系矩陣更加突出，更有助于稀疏，有助于多標(biāo)記社團(tuán)關(guān)系基于稀疏進(jìn)行分解。

Fig.8 Training rounds toQin Genbase圖8 Genbase中輪數(shù)對(duì)模塊度的影響

Fig.9 Training rounds toQin Enron圖9 Enron中輪數(shù)對(duì)模塊度的影響

Fig.10 Training rounds toQin BibTex圖10 BibTex中輪數(shù)對(duì)模塊度的影響

Fig.11 Training rounds to sparseness in Genbase圖11 Genbase中輪數(shù)對(duì)稀疏度的影響

Fig.12 Training rounds to sparseness in Enron圖12 Enron中輪數(shù)對(duì)稀疏度的影響

Fig.13 Training rounds to sparseness in BibTex圖13 BibTex中輪數(shù)對(duì)稀疏度的影響

同時(shí)，列舉了數(shù)據(jù)集BibTex在不同的訓(xùn)練輪數(shù)下，在相同的社團(tuán)劃分個(gè)數(shù)k=22時(shí)，隨著正則化項(xiàng)λ的改變，稀疏度的變化情況，如圖14所示。

Fig.14 Relationship between λand sparseness圖14 正則化項(xiàng)λ與稀疏度的關(guān)系

根據(jù)圖14，探索了在不同的訓(xùn)練輪數(shù)下，基于稀疏約束的正則化項(xiàng)λ取值同稀疏度的關(guān)系。由結(jié)果可以看出，在訓(xùn)練輪數(shù)為159次時(shí)，λ在取值為5.0左右稀疏度達(dá)到最大值0.966 6，隨后呈現(xiàn)遞減趨勢(shì)；在訓(xùn)練輪數(shù)為318次時(shí)，λ在取值為10.0左右稀疏度達(dá)到最大值0.955 7，隨后呈現(xiàn)下降趨勢(shì)；在訓(xùn)練輪數(shù)為477次時(shí)，λ在取值為15.0左右稀疏度達(dá)到最大值0.942 9，隨后呈現(xiàn)下降趨勢(shì)。由此可以看出，隨著λ的增大以及訓(xùn)練輪數(shù)的改變，稀疏度的大小是變化的，總體呈現(xiàn)先增后減的趨勢(shì)。也就是說(shuō)，稀疏度同增加的稀疏約束項(xiàng)息息相關(guān)，正則化項(xiàng)λ的變化影響到最后的稀疏程度，需要不斷測(cè)試找到一個(gè)合適的λ來(lái)達(dá)到需要的稀疏效果，但是要注意過(guò)擬合的發(fā)生。

由上述實(shí)驗(yàn)結(jié)果發(fā)現(xiàn)，在選取相同的實(shí)驗(yàn)條件下，從矩陣結(jié)構(gòu)來(lái)看，基于兩重稀疏表示的多標(biāo)記社團(tuán)分類方法結(jié)構(gòu)更加清晰且運(yùn)算簡(jiǎn)便。經(jīng)過(guò)多個(gè)性能指標(biāo)的對(duì)比發(fā)現(xiàn)，基于稀疏約束的多標(biāo)記社團(tuán)分類算法得到了更好的稀疏性、實(shí)用性與可解釋性，在多項(xiàng)指標(biāo)上有良好的效果。

5 結(jié)束語(yǔ)

針對(duì)已有的多標(biāo)記社團(tuán)發(fā)現(xiàn)樣本數(shù)目多，標(biāo)記不單一且標(biāo)記特征具有冗余的現(xiàn)狀，本文提出了基于兩重稀疏約束的多標(biāo)記社團(tuán)分類方法，針對(duì)多標(biāo)記特征數(shù)據(jù)訓(xùn)練繁瑣以及社團(tuán)發(fā)現(xiàn)未考慮稀疏約束的問(wèn)題，通過(guò)為多標(biāo)記分類過(guò)程及矩陣分解過(guò)程中的原目標(biāo)函數(shù)添加稀疏正則化項(xiàng)，從而達(dá)到將多標(biāo)記關(guān)系矩陣稀疏的效果。與已有的多標(biāo)記社團(tuán)發(fā)現(xiàn)算法進(jìn)行比較，本文算法不僅運(yùn)算簡(jiǎn)便，提高了訓(xùn)練效率，同時(shí)也有效提高了數(shù)據(jù)分解后的稀疏度，增強(qiáng)了數(shù)據(jù)表達(dá)的可解釋性，保留了原始樣本中最重要的節(jié)點(diǎn)。實(shí)驗(yàn)結(jié)果證明，本文算法是有效的，在保證最重要信息的基礎(chǔ)上，對(duì)處理大規(guī)模多標(biāo)記數(shù)據(jù)有著較好的分類效果。

[1]Lu Jianjiang,Zhang Yafei,Xu Weiguang,et al.Intelligentretrieval technology[M].Beijing:Science Press,2009.

[2]Klimt B,Yang Yiming.Introducing the Enron corpus[C]//Proceedings of the 1st Conference on Email and Anti-Spam, Mountain View,USA,Jul 30-31,2004.Menlo Park,USA: AAAI,2004.

[3]Duan Fei,Zhang Yujin.A new algorithm for maximum dictionary learning for sparse representation[J].Journal of Tsinghua University:Natural Science Edition,2012,52(4):566-570.

[4]Wang Xiaofan,Liu Yabing.A survey of community structure in complex networks[J].Journal of University of Electronic Science and Technology of China,2009,38(5):537-543.

[5]Wang Xiaofan.Complex network theory and its application [M].Beijing:Tsinghua University Press,2006.

[6]Huang Shengjun,Yu Yang,Zhou Zhihua.Multi-label hypothesis reuse[C]//Proceedings of the 18th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining,Beijing,Aug 12-16,2012.New York:ACM,2012: 525-533.

[7]Huang Gangshi,Zhang Yafei,Lu Jianjiang,et al.A constrained non negative matrix factorization method[J].Journal of Southeast University:Natural Science Edition,2004,34(2):189-193.

[8]Lee D D,Seung H S.Learning the parts of objects by nonnegative matrix factorization[J].Nature,1999,401(6755): 788-791.

[9]Lee D D.Algorithms for non-negative matrix factorization [J].Advances in Neural Information Processing Systems, 2001,13(6):556-562.

[10]Argyriou A,Evgeniou T,Pontil M.Convex multi-task feature learning[J].Machine Learning,2008,73(3):243-272.

[11]Bach F R.Consistency of the group lasso and multiple kernel learning[J].Journal of Machine Learning Research,2007,9 (2):1179-1225.

[12]Berg E V D,Schmidt M,Friedlander M P,et al.Group sparsity via linear-time projection[R].UBC,2008.

[13]Lê Cao K A,Rossouw D,Robert-Granié C,et al.A sparse PLS for variable selection when integrating omics data[J]. Statistical Applications in Genetics&Molecular Biology, 2008,7(1):35.

[14]Koh K,Kim S J,Boyd S.An interior-point method for large-scale L1-regularized logistic regression[J].Journal of Machine Learning Research,2007,8(3):1519-1555.

[15]Liu Jun,Chen Jianhui,Ye Jieping.Large-scale sparse logistic regression[C]//Proceedings of the 15th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining,Paris,Jun 28-Jul 1,2009.New York:ACM,2009: 547-556.

[16]Wang Fei,Li Tao,Wang Xin,et al.Community discovery using nonnegative matrix factorization[J].Data Mining& Knowledge Discovery,2011,22(3):493-521.

[17]Nguyen N P,Frank C,Moltz C C,et al.Aspiration rate following chemoradiation for head and neck cancer:an underreported occurrence[J].Radiotherapy and Oncology,2006, 80(3):302-306.

[18]Brunet J P,Tamayo P,Golub T R.et al.Metagenes and molecular pattern discovery using matrix factorization[J].Proceedings of the National Academy of Sciences,2004,101 (12):4164-4169.

[19]Zhang Yu,Yeung D Y.Overlapping community detection via bounded nonnegative matrix tri-factorization[C]//Proceedings of the 18th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining,Beijing, Aug 12-16,2012.New York:ACM,2012:606-614.

[20]Tang Jiliang,Liu Huan.Unsupervised feature selection for linked social media data[C]//Proceedings of the 18th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining,Beijing,Aug 12-16,2012.New York: ACM,2012:904-912.

[21]Tibshirani R.Regression shrinkage and selection via the Lasso [J].Journal of the Royal Statistical Society:Series B Methodological,1996,58(1):267-288.

[22]Ye Jieping,Chen Jianhui,Janardan R,et al.Developmental stage annotation of drosophila gene expression pattern images via an entire solution path for LDA[J].ACM Transactions on Knowledge Discovery from Data,2008,2(1):1-21.

[23]Golub T R,Slonim D K,Tamayo P,et al.Molecular classification of cancer:class discovery and class prediction by gene expression monitoring[J].Science,1999,286(5439):531-537.

[24]Wang Dingding,Li Tao,Zhu Shenghuo,et al.Multi-document summarization via sentence-level semantic analysis and symmetric matrix factorization[C]//Proceedings of the 31st Annual International ACM SIGIR Conference on Research and Development in Information Retrieval,Singapore,Jul 20-24,2008.New York:ACM,2008:307-314.

[25]Zhang Liangliang,Pan Zhisong,Li Guopeng,et al.Weighteddirected community detection method based on Wavelet denoising[J].Journal of Data Acquisition and Processing, 2014,29(5):833-839.

[26]Klimt B,Yang Yiming.The Enron corpus:a new dataset for Email classification research[C]//LNCS 3201:Proceedings of the 15th European Conference on Machine Learning,Pisa, Sep 20-24,2004.Berlin,Heidelberg:Springer,2014:217-226.

[27]Katakis I,Tsoumakas G,Vlahavas I.Multilabel text classification for automated tag suggestion[C]//Proceedings of the ECML/PKDD 2008 Workshop on Discovery Challenge,Antwerp,Belgium,Sep 15-19,2008.

[28]Diplaris S,Tsoumakas G,Mitkas PA,et al.Protein classification with multiple algorithms[C]//LNCS 3746:Proceedings of the 10th Panhellenic Conference on Informatics,Volas, Greece,Nov 11-13,2005.Berlin,Heidelberg:Springer,2005: 448-456.

[29]Zhang Wei,Liu Ju,Sun Jiande,et al.A new two-stage approach to underdetermined blind source separation using sparse representation[C]//Proceedings of the 2007 International Conference on Acoustics,Speech and Signal Processing, Honolulu,USA,Apr 16-20,2007.Piscataway,USA:IEEE, 2007:953-956.

[30]Newman M E.Fast algorithm for detecting community structure in networks[J].Physical Review E,2004,69(6):279-307.

[31]Guillaume J L,Lambiotte R.Fast unfolding of communities in large networks[J].Journal of Statistical Mechanics Theory &Experiment,2008,30(2):155-168.

[32]Liao Feng,Gao Xingbao,Yang Xuan.An improved non negative matrix factorization algorithm[J].Journal of University of Jinan:Natural Science Edition,2008,22(2):193-196.

附中文參考文獻(xiàn):

[1]陸建江,張亞非,徐偉光,等.智能檢索技術(shù)[M].北京:科學(xué)出版社,2009.

[3]段菲,章毓晉.一種面向稀疏表示的最大問(wèn)隔字典學(xué)習(xí)算法[J].清華大學(xué)學(xué)報(bào):自然科學(xué)版,2012,52(4):566-570.

[4]汪小帆,劉亞冰.復(fù)雜網(wǎng)絡(luò)中的社團(tuán)結(jié)構(gòu)算法綜述[J].電子科技大學(xué)學(xué)報(bào),2009,38(5):537-543.

[5]汪小帆.復(fù)雜網(wǎng)絡(luò)理論及其應(yīng)用[M].北京:清華大學(xué)出版社,2006.

[7]黃鋼石,張亞非,陸建江,等.一種受限非負(fù)矩陣分解方法[J].東南大學(xué)學(xué)報(bào):自然科學(xué)版,2004,34(2):189-193.

[25]張梁梁,潘志松,李國(guó)鵬,等.基于小波去噪的有向加權(quán)社團(tuán)發(fā)現(xiàn)研究[J].數(shù)據(jù)采集與處理,2014,29(5):833-839.

[32]廖鋒,高興寶,楊軒.一種改進(jìn)的非負(fù)矩陣分解算法[J].濟(jì)南大學(xué)學(xué)報(bào):自然科學(xué)版,2008,22(2):193-196.

LI Na was born in 1990.She is an M.S.candidate at College of Command Information Systems,PLA University of Science and Technology.Her research interests include pattern recognition and machine learning,etc.

李娜（1990—），女，河北保定人，解放軍理工大學(xué)指揮信息系統(tǒng)學(xué)院碩士研究生，主要研究領(lǐng)域?yàn)槟Ｊ阶R(shí)別，機(jī)器學(xué)習(xí)等。

潘志松（1973—），男，江蘇南京人，2002年于解放軍理工大學(xué)指揮信息系統(tǒng)學(xué)院獲得博士學(xué)位，現(xiàn)為解放軍理工大學(xué)教授、博士生導(dǎo)師，CCF會(huì)員，主要研究領(lǐng)域?yàn)槟Ｊ阶R(shí)別，機(jī)器學(xué)習(xí)等。

REN Yiqiang was born in 1987.He is an engineer at SIEMENS Power Automation Co.,Ltd..His research interests include relay protection of power systems,supervisory control and data acquisition system,etc.

任義強(qiáng)（1987—），男，河北保定人，西門(mén)子電力自動(dòng)化有限公司工程師，主要研究領(lǐng)域?yàn)殡娏^電保護(hù)，監(jiān)控與數(shù)據(jù)采集系統(tǒng)等。

LI Guopeng was born in 1983.He is a Ph.D.candidate at College of Command Information Systems,PLA University of Science and Technology.His research interests include pattern recognition and machine learning,etc.

李國(guó)朋（1983—），男，陜西興平人，解放軍理工大學(xué)指揮信息系統(tǒng)學(xué)院博士研究生，主要研究領(lǐng)域?yàn)槟Ｊ阶R(shí)別,機(jī)器學(xué)習(xí)等。JIANG Mingchu was born in 1989.He is an M.S.candidate at College of Command Information Systems,PLA University of Science and Technology.His research interests include pattern recognition and machine learning,etc.蔣銘初（1989—），男，江蘇淮安人，解放軍理工大學(xué)指揮信息系統(tǒng)學(xué)院碩士研究生，主要研究領(lǐng)域?yàn)槟Ｊ阶R(shí)別，機(jī)器學(xué)習(xí)等。

Multi-Label Community Classification Method Based on Double Sparse Representation*

LI Na1,2,PAN Zhisong1+,REN Yiqiang3,LI Guopeng1,4,JIANG Mingchu1
1.College of Command Information Systems,PLAUniversity of Science and Technology,Nanjing 210007,China
2.The 32nd Research Institute of China Electronic Technology Group Corporation,Shanghai 201808,China
3.SIEMENS PowerAutomation Co.,Ltd.,Nanjing 211100,China
4.Xi?an Communications Institute,Xi?an 710106,China
+Corresponding author:E-mail:panzs@nuaa.edu.cn

In multi-label learning,the correlation between labels has been more and more widely used,and it is necessary to show the relationship between them.Compared with previous studies,training process is extremely complicated and time-consuming due to the high dimensionality feature of multi-label data,so sparse optimization becomes essential;meanwhile,the relationship among labels has not been thoroughly excavated,so how to learn multi-label classification and study the correlation between all markers more effectively and conveniently becomes a necessity. This paper presents a method constraint on double sparse representation in multi-label classification,which first uses?1/?2-norm regularization to sparse multi-label data to convenient for following researches,and then applies?1-norm into community detection to effectively detect communities.By this it shows the deep meaning of label relationship.Experiments show that this method can rapidly and accurately study and train multiple labels,and accurately display label connection at the same time.

multi-label;label relation;non-negative matrix factorization(NMF);?1/?2-norm;?1-norm

ng was born in 1973.He

the Ph.D.degree from PLA University of Science and Technology in 2002.Now he is a professor and Ph.D.supervisor at PLA University of Science and Technology,and the member of CCF.His research interests include pattern recognition and machine learning,etc.

A

TP391

*The National Natural Science Foundation of China under Grant No.61473149(國(guó)家自然科學(xué)基金).

Received 2016-02,Accepted 2016-04.

CNKI網(wǎng)絡(luò)優(yōu)先出版:2016-04-18,http://www.cnki.net/kcms/detail/11.5602.TP.20160418.1031.002.html