兩重稀疏約束的多標記社團分類算法*

李 娜，潘志松，任義強，李國朋，蔣銘初

1.中國人民解放軍理工大學 指揮信息系統學院，南京 210007

2.中國電子科技集團公司 第三十二研究所，上海 201808

3.西門子電力自動化有限公司，南京 211100

4.西安通信學院，西安 710106

兩重稀疏約束的多標記社團分類算法*

李 娜1,2，潘志松1+，任義強3，李國朋1,4，蔣銘初1

1.中國人民解放軍理工大學 指揮信息系統學院，南京 210007

2.中國電子科技集團公司 第三十二研究所，上海 201808

3.西門子電力自動化有限公司，南京 211100

4.西安通信學院，西安 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.

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

多標記；標記關系；非負矩陣分解（NMF）；?1/?2范數；?1范數

1 引言

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

稀疏（sparsity）是最近幾年機器學習和計算機視覺領域對于高維數據的研究熱點之一[3]。也就是在一個足夠大的訓練樣本空間內，對于一個類別的物體，可以大致地由訓練樣本中同類的樣本子空間線性表示，因此當該物體由整個樣本空間表示時，其表示的系數是稀疏的。當前對于數據的稀疏表示，是將稀疏方法應用于數據的降維預處理過程中，并在圖像去噪、圖像復原等方面取得了重大成功。通過稀疏可以得到數據最為重要的屬性，然而對于標記的稀疏卻沒有找到合適的優化策略。

網絡的社團結構[4]指相互之間具有比較大的相似性而與網絡中的其他部分有著很大不同的節點的群。在社團內部，節點之間的聯系非常緊密，社團之間的聯系相對比較稀疏[5]。如在社會網絡中，某一社團的人們與其他社團有著不一樣的特質。對網絡中節點尋找社團結構并對其進行分析是了解現實生活中各種網絡組織的一種重要方法，并在多個領域有著重要的應用。然而社團結構在多標記數據集中的應用還不是很多，而多標記分類方法的應用卻越來越廣泛。在多標記分類算法中，現有算法已經越來越側重于對標記間相互關系的利用，對于標記關系的獲取形式也有多種[6]，多標記之間的相關性同樣可以構成具有標記節點關聯的網絡結構，并從該結構中分析標記之間隱含的相關信息。對待該網絡結構，可以應用現有的社團發現算法進行分析。

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

本文首先對兩重稀疏約束的多標記社團分類相關工作進行介紹，隨后詳細說明了基于兩重稀疏約束的多標記社團分類方法，并在已有數據集上將本文涉及內容與現有的一些方法進行對比，測試在多種實際數據集下的性能。最后進行總結。

2 相關工作介紹

2.1 多標記社團發現概念

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

2.2 非負矩陣分解

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

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

2.3 ?1范數與?1/?2范數正則化問題

稀疏是個經典話題，即是用少量重要元素代替大量的數據，使得大多數元素為0而少量元素不為0。由于在高維數據中對于數據的操作是非常費力的，而稀疏性對于解決高維度數據的計算量問題是非常有效的。機器學習中的一個規則化函數?2范數||W||2是應用較廣泛的一個優化函數，然而其在實際測試過程中不具有產生稀疏解的能力。而?0范數是指向量中非0的元素的個數，也就是用來找到方程解中具有最小數目的非零項，然而在求解過程中是一個NP問題。因此，引出了?1范數最小化問題，即用?1范數來代替?0與?2范數，以此來找到近似解。

大多數現有的稀疏學習工作是基于?1范數正則化的變種。由于?1范數正則化在應用中方便的凸性、強大的理論保證等，其應用越來越廣泛。現今該方法的應用已經促進了線性回歸[21]、線性判別分析[22]、偏最小二乘法[13]、邏輯回歸[14-15]等模型的稀疏化發展。?1范數正則化得到的目標函數通常描述如下：

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

近期在機器學習和數學統計領域，稀疏學習工作已經由?1范數正則化延伸到?1/?q的正則化[10-12]。當q＞1時，?1/?q正則化在產生的模型中能夠促進組稀疏，因此常常應用到分類和回歸問題中。圖1展示了該優化問題。

?1/?q范數正則化得到的目標函數通常描述如下：

Fig.1 Illustration of data matrixA,target matrixY, and weight matrixX圖1 數據矩陣A、目標矩陣Y與權重矩陣X關系展示

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

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

3 基于兩重稀疏約束的多標記社團分類方法

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

3.1 基于?1/?2范數稀疏性約束的多標記降維

定義1設多標記數據集為：

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

其中，A∈Rm×n為原始數據矩陣；Y∈Rm×k為目標標記矩陣。優化的目標就是尋找稀疏的權重矩陣X，從而得到使得A稀疏后的降維數據。詳見參考文獻[23]。

3.2 本文算法

利用NMF算法的稀疏性能夠快速提取網絡重要節點所屬社團這一特點，本文將稀疏性應用到社團發現工作中。主要對多標記社團劃分的工作進行改進，將多標記關系矩陣運用基于?1范數稀疏約束的非負矩陣分解算法，得到多標記的社團分類。基于兩重稀疏性約束的多標記社團分類方法步驟如下。

（1）輸入：多標記訓練數據集特征矩陣A，標記矩陣Y，正則化參數λ，訓練輪數T，MAHR訓練基分類器C。

（2）輸出：多標記所屬社團矩陣G。

（4）利用?1/?2范數正則化對多標記數據集A進行降維，得到稀疏后的降維矩陣A*。

（5）利用MAHR算法，對A*進行相應的訓練，得到綜合模型Z，標記關系矩陣所需權重β與α。

（6）根據Z、β與α，得出多標記間評分矩陣S，其中根據評分得到關系矩陣規范化并重組，得到多標記關系矩陣V。

（7）根據NMF規則，將矩陣V分解為三層結構，即V≈XSXT。

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

更新S：si+1=si+Δs。其中Δs為社團關系矩陣增量。

（8）從矩陣X中找到每個標記的最大值與所屬社團標號，得到多標記節點所屬社團C。

其中k代表社團數量，根據算法中系數矩陣X來找到多標記所屬的社團分類。矩陣X表示一個二維的數量為k的社團，行對應標記節點類別，列對應社團類別，矩陣X的每一行最大的元素所對應的列則可標識為對應標記所在的社團類別。

基于兩重稀疏性約束的多標記社團分類方法就是在原目標函數上增加約束條件來獲取盡可能稀疏的標記所屬社團的分類信息。鑒于當前工作中基于?1/?2范數稀疏約束的數據降維方法應用較廣，本文將工作重點放在多標記社團分類過程中。在前面的基礎上考慮對非負向量X加?1范數約束條件，即最小化轉換為矩陣的形式就是為了使矩陣X充分稀疏，最小化矩陣X中所有元素的和。

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

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

因此，將L分別對X和S*求導，得：

更新X、S的增量為：

最終得到了稀疏后的標記所屬社團關系矩陣。

4 實驗分析

4.1 實驗設置

本實驗共使用1個人工數據集和3個真實數據集，人工數據集為Data，是34×34維的0-1對稱關系矩陣，真實數據集包括郵件分析數據集Enron[26]、文獻管理數據集BibTex[27]和生物領域的基因數據集Genbase[28]，表1給出了這些數據集的統計信息。通過基于兩重稀疏性約束的多標記社團分類方法，首先得到降維后的多標記特征矩陣，再次根據MAHR算法得到多標記的評分矩陣，進而應用?1范數約束得到多標記社團關系，并對多標記所屬社團矩陣進行解釋。

Table 1 Experimental datasets表1 實驗數據集

實驗環境操作系統為Windows7，工具軟件為Matlab R2013a。

4.2 結果分析

本節列舉出根據加稀疏約束的多標記社團分類算法得到的標記所屬矩陣關系，并在4個數據集上進行實驗效果驗證。根據數據集的維數、標記數量等特點，將上述幾個數據集劃分為個數不同的社團，并且通過本文算法得到標記所屬社團矩陣。矩陣分解后的系數矩陣能反映分解的效果，因此對分解后的系數矩陣X及算法的一些指標進行分析，并比較多標記關系，獲取所需的訓練輪數與各項指標的關系。其中“↑”表示越大越好，“↓”代表越小越好，“·”表示在對應指標比較上，本文算法優于比較方法。

根據文獻[29]提出的稀疏度度量公式對分解后的基矩陣和系數矩陣進行度量，公式如下：

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

矩陣X的模塊度是目前常用的一種衡量網絡社區結構強度的方法[30-31]，值越接近1表示網絡劃分的社團結構強度越好。公式為：

其中，m為網絡中邊的總數；i、j分別為網絡中的節點；Vij表示i、j的鄰接關系；N為節點集合；ki為點i的度；Ci和Cj分別表示點i、j所在的兩個社區。

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

分解時間表示幾個算法在對多標記關系矩陣處理并進行矩陣分解過程中所需要的時間，時間越短表示算法處理速度越快。

4.2.1 性能比較

表2~表5分別統計了表1中幾個數據集的實驗結果。具體內容如下：將Data劃分為5個社團，Genbase的多標記關系劃分為3個社團，Enron數據集的多標記關系劃分為2個社團，BibTex劃分為22個社團。參加比較的算法有應用?2范數正則化的NMTFSQ[19]社團發現算法，應用KL距離（Kullback-Leibler divergence）的NMTFKL[19]社團發現算法以及不加任何稀疏約束的基于NMF的社團發現算法。

表2展示了人工數據集Data上的實驗結果。其中令本文算法中?1范數的正則化項λ=1.5，劃分的社團個數k=5。由于Data數據集已經是元素間的關系矩陣，那么對于基于?1/?q范數稀疏性約束的多標記數據降維步驟省略，直接進入社團發現過程。

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

從表2中可以看出，本文算法在模塊度、分解誤差、稀疏度3個指標上取得了比其他社團發現方法更優的效果。而在分解時間方面，NMTFSQ所用時間最長，而本文算法與其他算法的結果相差不大。

表3統計了上述幾個數據集上的實驗結果，展示了數據集Genbase在λ=1.5，社團個數k=3，多標記關系訓練輪數為4倍的樣本標記維數(rounds=108)情況下，本文算法同已有的多種非負矩陣算法的比較結果。

從表3中可以看出，本文算法同樣在模塊度、分解誤差、稀疏度3個指標上取得了比其他社團發現方法更優的效果。而在分解時間方面，NMTFSQ所用時間最長，而本文算法與其他算法的結果相差不大。

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

表4統計了上述幾個數據集上的實驗結果，展示了數據集Enron在λ=1.5，社團個數k=2，多標記關系訓練輪數為3倍的樣本標記維數(rounds=212)情況下，本文算法同已有的多種非負矩陣算法的比較結果。

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

從表4中可以看出，本文算法在Enron數據集上不是很理想，僅在模塊度和分解誤差兩個指標上表現良好。

表5統計了上述幾個數據集上的實驗結果，展示了數據集Bibtex在λ=1.5，社團個數k=22，多標記關系訓練輪數為3倍的樣本標記維數(rounds=477)情況下，本文算法同已有的多種非負矩陣算法的比較結果。

根據表5的結果不難看出，本文算法在除了分解時間指標以外的其余3個最有意義的指標上取得最好的效果，且優勢比較明顯。

因此，在4個常用的不同領域的數據集中，每個數據集在相同的實驗環境及參數設置條件下，同已有的非負矩陣分解算法相比，本文算法在模塊度、稀疏度方面達到了最優，而在分解時間與誤差值方面，同最優算法相比，均相差不大，根據模塊度最大選擇多標記社團分解算法才具有更高的準確率。同時，稀疏度越高表明得到的多標記所屬社團分類更明確。因為未加稀疏的公式簡便，所以從時間效果分析，未加稀疏的多標記社團發現算法時間最短，而本文算法相對于NMTFSQ和NMTFKL算法來說，在處理時間上顯著縮短。

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

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

由于本文是基于兩重稀疏約束的算法，那么在第一層稀疏即數據加入?1/?2范數約束對標記關系的影響需要驗證。圖2~圖7分別統計了表1中幾個數據集在不經過稀疏降維的情況下與基于?1/?2范數稀疏約束的情況下模塊度與稀疏度的對比結果，目的是為了驗證稀疏降維有無保留最重要的屬性以及對多標記關系的影響。設3個數據集在降維過程中的?1/?2范數正則化項λ12=0.02。

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

對于圖2~圖4，從模塊度方面講，原多標記的高維數據經過?1/?2范數稀疏降維后再進行社團劃分的方法，4個算法在數據集Genbase和BibTex上取得了比較好的效果，將不必要的屬性稀疏降維后，模塊度不僅沒有降低反而有所提高，說明降維之后剩余的特征屬性具有更明顯的特征，對多標記數據訓練過程中得到的相關性更有幫助，從而能夠更加明顯地展示出多標記的社團結構。而在Enron數據集上的表現并不令人滿意，模塊度成為負值，說明該數據集在稀疏降維后得到的標記關系失去了社團的性質。

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

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

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

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

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

總體來看，在3個數據集進行基于?1/?2范數稀疏約束后，在個別數據集的個別算法指標上有減弱的效果，但是整體來說趨于穩定，甚至模塊度、稀疏度都有增強，社團結構更加明顯。由此說明，在多標記數據集降維后，不僅沒有影響重要特征，反而保留了重要的特征，并能夠對標記關系的訓練產生影響，從而明確社團結構。標記社團的結果同完全由原始數據訓練得到的標記關系差別不大，同時預處理的訓練時間因為稀疏的作用而大幅度減少，更加簡便快捷，加入?1/?2范數降維后的數據處理更為優越。

4.2.3 標記關系訓練輪數的影響

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

由圖8~圖13可以得出，本文算法在3個數據集中的模塊度基本處于最高的狀態，且變化較為穩定。無論是在模塊度還是稀疏度方面，本文基于?1稀疏約束的社團發現算法要比不加稀疏約束的普通社團發現算法表現好。雖然在稀疏度方面4個算法表現有好有壞，但是可以明確的是，隨著多標記社團關系訓練輪數的增加，幾個算法的模塊度和稀疏度整體來說呈增加的趨勢。這樣的結果說明，訓練輪數增加，得到的多標記間的相關聯系就越緊密，關系矩陣更加突出，更有助于稀疏，有助于多標記社團關系基于稀疏進行分解。

Fig.8 Training rounds toQin Genbase圖8 Genbase中輪數對模塊度的影響

Fig.9 Training rounds toQin Enron圖9 Enron中輪數對模塊度的影響

Fig.10 Training rounds toQin BibTex圖10 BibTex中輪數對模塊度的影響

Fig.11 Training rounds to sparseness in Genbase圖11 Genbase中輪數對稀疏度的影響

Fig.12 Training rounds to sparseness in Enron圖12 Enron中輪數對稀疏度的影響

Fig.13 Training rounds to sparseness in BibTex圖13 BibTex中輪數對稀疏度的影響

同時，列舉了數據集BibTex在不同的訓練輪數下，在相同的社團劃分個數k=22時，隨著正則化項λ的改變，稀疏度的變化情況，如圖14所示。

Fig.14 Relationship between λand sparseness圖14 正則化項λ與稀疏度的關系

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

由上述實驗結果發現，在選取相同的實驗條件下，從矩陣結構來看，基于兩重稀疏表示的多標記社團分類方法結構更加清晰且運算簡便。經過多個性能指標的對比發現，基于稀疏約束的多標記社團分類算法得到了更好的稀疏性、實用性與可解釋性，在多項指標上有良好的效果。

5 結束語

針對已有的多標記社團發現樣本數目多，標記不單一且標記特征具有冗余的現狀，本文提出了基于兩重稀疏約束的多標記社團分類方法，針對多標記特征數據訓練繁瑣以及社團發現未考慮稀疏約束的問題，通過為多標記分類過程及矩陣分解過程中的原目標函數添加稀疏正則化項，從而達到將多標記關系矩陣稀疏的效果。與已有的多標記社團發現算法進行比較，本文算法不僅運算簡便，提高了訓練效率，同時也有效提高了數據分解后的稀疏度，增強了數據表達的可解釋性，保留了原始樣本中最重要的節點。實驗結果證明，本文算法是有效的，在保證最重要信息的基礎上，對處理大規模多標記數據有著較好的分類效果。

[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.

附中文參考文獻:

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

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

[4]汪小帆,劉亞冰.復雜網絡中的社團結構算法綜述[J].電子科技大學學報,2009,38(5):537-543.

[5]汪小帆.復雜網絡理論及其應用[M].北京:清華大學出版社,2006.

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

[25]張梁梁,潘志松,李國鵬,等.基于小波去噪的有向加權社團發現研究[J].數據采集與處理,2014,29(5):833-839.

[32]廖鋒,高興寶,楊軒.一種改進的非負矩陣分解算法[J].濟南大學學報:自然科學版,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—），女，河北保定人，解放軍理工大學指揮信息系統學院碩士研究生，主要研究領域為模式識別，機器學習等。

潘志松（1973—），男，江蘇南京人，2002年于解放軍理工大學指揮信息系統學院獲得博士學位，現為解放軍理工大學教授、博士生導師，CCF會員，主要研究領域為模式識別，機器學習等。

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.

任義強（1987—），男，河北保定人，西門子電力自動化有限公司工程師，主要研究領域為電力繼電保護，監控與數據采集系統等。

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.

李國朋（1983—），男，陜西興平人，解放軍理工大學指揮信息系統學院博士研究生，主要研究領域為模式識別,機器學習等。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—），男，江蘇淮安人，解放軍理工大學指揮信息系統學院碩士研究生，主要研究領域為模式識別，機器學習等。

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(國家自然科學基金).

Received 2016-02,Accepted 2016-04.

CNKI網絡優先出版:2016-04-18,http://www.cnki.net/kcms/detail/11.5602.TP.20160418.1031.002.html