李 娜 潘志松 施 蕾 薛 膠 任義強

(1.解放軍理工大學(xué)指揮信息系統(tǒng)學(xué)院，南京，210007； 2.中國電子科技集團公司第三十二研究所，上海，201808； 3.西門子電力自動化有限公司，南京，211100)

基于標(biāo)記關(guān)系的多標(biāo)記社團發(fā)現(xiàn)算法*

李 娜1,2潘志松1施 蕾1薛 膠1,2任義強3

(1.解放軍理工大學(xué)指揮信息系統(tǒng)學(xué)院，南京，210007； 2.中國電子科技集團公司第三十二研究所，上海，201808； 3.西門子電力自動化有限公司，南京，211100)

真實世界的對象具有多義性，具有非單一的多種標(biāo)記。對于多標(biāo)記的學(xué)習(xí)，現(xiàn)階段的工作雖然能夠利用標(biāo)記間的重用評分分析多標(biāo)記間的關(guān)系，但是尚不能直觀挖掘出多標(biāo)記的關(guān)系結(jié)構(gòu)，也不能準(zhǔn)確掌握多標(biāo)記的主從關(guān)系以及多標(biāo)記的重要性排名情況。而非負矩陣分解(Nonnegative matrix factorization，NMF)方法能對有關(guān)聯(lián)的節(jié)點進行有效的社團劃分，發(fā)掘關(guān)聯(lián)節(jié)點的潛在關(guān)系，因此利用NMF方法對多標(biāo)記關(guān)系進行社團結(jié)構(gòu)分解成為有價值的研究內(nèi)容。本文提出多標(biāo)記社團發(fā)現(xiàn)算法，有效地對多標(biāo)記進行挖掘，發(fā)現(xiàn)其中的社團結(jié)構(gòu),得到多標(biāo)記的社團關(guān)系，并且能夠?qū)Χ鄻?biāo)記節(jié)點的重要程度排序，分析多標(biāo)記的主從結(jié)構(gòu)，驗證多標(biāo)記關(guān)系算法的有效性，挖掘出其中隱藏的價值，這對于多標(biāo)記的研究具有重要意義。

多標(biāo)記;標(biāo)記關(guān)系;非負矩陣分解;社團發(fā)現(xiàn)

引 言

在監(jiān)督學(xué)習(xí)框架中，每一個訓(xùn)練的樣本都具有一個類別標(biāo)記來表示其語義信息，學(xué)習(xí)的目標(biāo)則是從訓(xùn)練樣本中獲得標(biāo)記的概念，使得學(xué)習(xí)模型能夠給未見過的樣本預(yù)測正確的標(biāo)記。然而生活中具有多種語義信息的學(xué)習(xí)對象非常常見，傳統(tǒng)的監(jiān)督學(xué)習(xí)總是假設(shè)真實世界的對象同它相對應(yīng)的描述以及它的概念標(biāo)記之間是完全一對一的關(guān)系。然而在物質(zhì)世界中，各種事物和各類現(xiàn)象基本上可由多種語義標(biāo)記表示，如在文本分析領(lǐng)域的論文分類問題中，每篇論文可同時屬于多個研究領(lǐng)域；在多媒體理解領(lǐng)域如視頻檢索過程中，每段視頻包含了多種語義類別；在生物信息學(xué)領(lǐng)域，一種蛋白質(zhì)可以有多種功能的分類。隨著多標(biāo)記學(xué)習(xí)[1]的出現(xiàn)，利用相關(guān)標(biāo)記上的有用信息互相幫助能減少學(xué)習(xí)任務(wù)的難度。同時，相關(guān)標(biāo)記上的語義信息之間存在著一定聯(lián)系，結(jié)構(gòu)明顯，隨著社團工作的開展，多標(biāo)記中的社團結(jié)構(gòu)也逐漸引起人們的興趣。社團發(fā)現(xiàn)[2](Communities detection)最早來源于Girvan和Newman提出的基于邊介數(shù)的經(jīng)典社團劃分GN算法，起源于對社會網(wǎng)絡(luò)的研究，并逐漸成為該領(lǐng)域特殊而新穎的研究方向。以往的工作很少將多標(biāo)記學(xué)習(xí)與社團發(fā)現(xiàn)聯(lián)系起來，而對于多標(biāo)記的社團結(jié)構(gòu)也沒有過明確的表示。由于標(biāo)記間的相關(guān)性越來越多地被應(yīng)用到多標(biāo)記學(xué)習(xí)領(lǐng)域，標(biāo)記間的關(guān)系不斷受到研究人員的重視。文獻[3]指出，多標(biāo)記分類的任務(wù)是基于訓(xùn)練數(shù)據(jù)學(xué)習(xí)一個分類器，從而在面對未知樣本時，能夠通過此分類來預(yù)測其他可能的樣例，因此標(biāo)記是可能聯(lián)系在一起的，并且每個標(biāo)記占的比重是不平均的。針對多標(biāo)記的這些特征，若將社團發(fā)現(xiàn)方法作用于多標(biāo)記關(guān)系上，其社團結(jié)構(gòu)不僅能夠驗證其相關(guān)性，還能夠得到標(biāo)記所占的比重。

本文的多標(biāo)記社團發(fā)現(xiàn)算法是在已有工作的基礎(chǔ)上，根據(jù)文獻[4]提出的多標(biāo)記學(xué)習(xí)方法——多標(biāo)記假設(shè)重用(Multi-label algorithm of hypothesis reuse,MAHR)方法，在學(xué)習(xí)過程中自動地挖掘出標(biāo)記之間的關(guān)系并輸出對標(biāo)記關(guān)系的有效估計結(jié)果，經(jīng)過重組得到多標(biāo)記關(guān)系矩陣，在非負矩陣分解(Nonnegative matrix factorization，NMF)算法基礎(chǔ)上，根據(jù)標(biāo)記關(guān)系矩陣得到標(biāo)記的社團結(jié)構(gòu)。該方法的目的是得到多標(biāo)記社團結(jié)構(gòu)，并根據(jù)社團結(jié)構(gòu)來評估標(biāo)記的重要性，得出標(biāo)記重要性排名。文獻[4]的MAHR算法基于Boosting框架，基分類器采用Boosting框架中最常見的決策樹樁(Decision Stump)算法來訓(xùn)練，通過假設(shè)重用的方式來得到標(biāo)記的促進關(guān)系與互斥關(guān)系評分，組合得到的矩陣作為標(biāo)記關(guān)系矩陣。在多標(biāo)記社團發(fā)現(xiàn)算法中，用迭代更新規(guī)則對分解矩陣進行優(yōu)化求解，最終得到標(biāo)記的社團關(guān)系矩陣。通過近幾年的發(fā)展，在多標(biāo)記學(xué)習(xí)和社團發(fā)現(xiàn)工作上已經(jīng)積累了一些優(yōu)秀的思想和成果，本文對其進行全面的分析與融合，為今后的發(fā)展提供幫助和借鑒。

1 多標(biāo)記社團發(fā)現(xiàn)背景

1.1 多標(biāo)記學(xué)習(xí)

1.1.1 多標(biāo)記學(xué)習(xí)概念

隨著信息社會的高度發(fā)展，各種海量數(shù)據(jù)以及信息觸手可及。在物質(zhì)世界中，各種事物和各類現(xiàn)象基本上可由具備多種屬性的海量數(shù)據(jù)表示。在多標(biāo)記學(xué)習(xí)框架下，每個樣本由一個特征向量表示，但此樣本可能同時隸屬于多個類別標(biāo)記，這樣做的目的就是通過學(xué)習(xí)給定的多標(biāo)記訓(xùn)練集從而能夠有效預(yù)測未知樣本的類別標(biāo)記。然而，在傳統(tǒng)的監(jiān)督學(xué)習(xí)框架下，待學(xué)習(xí)樣本是具有明確的而單一的類別標(biāo)記，即每個樣本只隸屬于一個標(biāo)記，因此難以處理真實世界的多義性對象。針對上述問題，自20世紀90年代末起，機器學(xué)習(xí)領(lǐng)域的研究者們不斷關(guān)注如何對多標(biāo)記對象有效建模，多標(biāo)記學(xué)習(xí)[5-7]框架應(yīng)運而生，并成為一個具有挑戰(zhàn)性的課題。

目前已提出的多標(biāo)記學(xué)習(xí)算法大致可以分成兩大類[4,8,9]:問題轉(zhuǎn)化方法(Problem transformation methods，PTM)和算法適應(yīng)方法(Algorithm adaptation methods，AAM)。PTM將多標(biāo)記學(xué)習(xí)問題轉(zhuǎn)化為其他已知的學(xué)習(xí)問題，例如兩類問題、多類問題和標(biāo)記排序問題等。AAM是直接設(shè)計多標(biāo)記學(xué)習(xí)算法處理多標(biāo)記數(shù)據(jù)，即改編一些著名的算法來直接處理多標(biāo)記數(shù)據(jù)[10]。無論是PTM或是AAM，多標(biāo)記學(xué)習(xí)算法都面臨著一個相同且關(guān)鍵的問題，即如何利用標(biāo)記之間的關(guān)系[4]，這對于解決維度災(zāi)難有重要的意義。隨著對機器學(xué)習(xí)理論和應(yīng)用的研究日益深入，多標(biāo)記學(xué)習(xí)近年來已經(jīng)逐漸成為機器學(xué)習(xí)和模式識別領(lǐng)域的熱門課題，大量的公開數(shù)據(jù)集以及專門針對多標(biāo)記學(xué)習(xí)的工具箱為多標(biāo)記學(xué)習(xí)的深入研究提供了有力支持。

1.1.2 標(biāo)記間相互關(guān)系

多標(biāo)記學(xué)習(xí)區(qū)分于傳統(tǒng)監(jiān)督學(xué)習(xí)的最主要特點就是不同標(biāo)記之間存在相互關(guān)系。根據(jù)標(biāo)記之間的關(guān)系就能使得其中有價值信息互相幫助，提高學(xué)習(xí)效率。比如標(biāo)記之間的促進和互斥關(guān)系能夠有效避免不必要的訓(xùn)練和測試。另外在樣本不足情況下，標(biāo)記也可以利用其他具有足夠樣本的相關(guān)標(biāo)記上的信息來幫助自身學(xué)習(xí)。因為，多個標(biāo)記之所以同時與一個樣本關(guān)聯(lián)，意味著這些標(biāo)記之間本身也存在著一定的相關(guān)性，于是如何利用標(biāo)記關(guān)系來幫助學(xué)習(xí)是多標(biāo)記學(xué)習(xí)的關(guān)鍵任務(wù)。

文獻[4]針對以往多標(biāo)記學(xué)習(xí)方法需要事先獲得標(biāo)記關(guān)系，在缺乏外界知識源時易過擬合的缺陷，提出了一種不需事先獲得標(biāo)記關(guān)系就能有效學(xué)習(xí)并能產(chǎn)生標(biāo)記關(guān)系估計結(jié)果的MAHR算法。該方法通過自動重用不同標(biāo)記的分類模型，通過重用權(quán)重計算出標(biāo)記之間的相關(guān)值，不僅可產(chǎn)生強泛化能力的多標(biāo)記學(xué)習(xí)器，還能輸出對標(biāo)記關(guān)系的估計結(jié)果，提高多標(biāo)記學(xué)習(xí)系統(tǒng)的泛化性能[10]。

MAHR算法基于Boosting框架，通過假設(shè)重用的方式來實現(xiàn)。它為每一個標(biāo)記訓(xùn)練一個Boosting分類器，在該算法每一輪訓(xùn)練中，某個標(biāo)記上的基分類器是由該標(biāo)記上訓(xùn)練好的模型及其他標(biāo)記上已經(jīng)訓(xùn)練好的模型加權(quán)求和得到。在此過程中，各個標(biāo)記所對應(yīng)的權(quán)重可通過最小化訓(xùn)練集上的損失函數(shù)(Hamming loss)自動確定，因此有幫助信息標(biāo)記上的模型就會被賦予較大的權(quán)重，從而能夠自動地挖掘出標(biāo)記之間的關(guān)系[4，9]。

1.2 社團發(fā)現(xiàn)

1.2.1 社團發(fā)現(xiàn)背景

社團發(fā)現(xiàn)是數(shù)據(jù)挖掘領(lǐng)域另一熱門課題，即在網(wǎng)絡(luò)中找出一些“稠密”的子圖。在大規(guī)模網(wǎng)絡(luò)中，所有節(jié)點之間的相互作用和相互連接不是無規(guī)律和隨機的，而是形成許多社團結(jié)構(gòu)，社團結(jié)構(gòu)是復(fù)雜網(wǎng)絡(luò)的基本特征之一[11]。隨著互聯(lián)網(wǎng)的迅速發(fā)展，各種社會網(wǎng)絡(luò)成為人們生活中不可或缺的一部分。目前社會網(wǎng)絡(luò)研究的難點主要是最有價值的信息往往隱藏在海量數(shù)據(jù)之中，通過對這些數(shù)據(jù)的分析與挖掘，可以增進對社會網(wǎng)絡(luò)上消息傳播的認識。網(wǎng)絡(luò)的社團結(jié)構(gòu)是指相互之間具有較大相似性而與網(wǎng)絡(luò)中的其他部分有著很大不同的節(jié)點的群[12,13]。隨著對各種網(wǎng)絡(luò)關(guān)系研究的深入，很多實際網(wǎng)絡(luò)都具有社團結(jié)構(gòu)。

1.2.2 多標(biāo)記中社團結(jié)構(gòu)

在多標(biāo)記的社團發(fā)現(xiàn)方面，本文基于NMF方法對多標(biāo)記進行社團劃分，從而使標(biāo)記間的關(guān)聯(lián)更加明確，結(jié)構(gòu)一目了然，主從關(guān)系亦清晰可見，并且對于數(shù)據(jù)中隱藏含義的分析有突出貢獻，并且能起到化繁為簡的作用[14]。隨著多標(biāo)記數(shù)據(jù)集中標(biāo)記數(shù)量的不斷增多，多標(biāo)記關(guān)系也越來越廣泛地應(yīng)用到多標(biāo)記學(xué)習(xí)框架當(dāng)中去，并且有效地提高了算法分類的精度與效率。由于多標(biāo)記數(shù)據(jù)集中的標(biāo)記節(jié)點眾多，結(jié)構(gòu)較單標(biāo)記數(shù)據(jù)更為復(fù)雜，而且標(biāo)記間的關(guān)系有正有負，標(biāo)記間的正作用一般代表友好、信任等信息，而負作用則常常應(yīng)用于否認、排斥等方面。正是由于標(biāo)記間的這種作用，其正相關(guān)與負相關(guān)的信息才有了明顯的區(qū)分，比如在圖像分類中沙漠與海洋一般不會同時出現(xiàn)。然而標(biāo)記間的相關(guān)性千絲萬縷，文本分類中一則正面的新聞可能牽涉到一個負面消息，此時尋找標(biāo)記關(guān)系的準(zhǔn)確結(jié)構(gòu)，將其中的關(guān)系直觀準(zhǔn)確展現(xiàn)出來就顯得尤為必要，因此需要一種方法針對多標(biāo)記數(shù)據(jù)集的網(wǎng)絡(luò)結(jié)構(gòu)與特征進行分析。近來隨著對海量數(shù)據(jù)分析不斷深入，探索數(shù)據(jù)中的社團結(jié)構(gòu)逐漸成為研究熱點。在復(fù)雜網(wǎng)絡(luò)的社團內(nèi)部，節(jié)點之間的聯(lián)系緊密，社團之間的聯(lián)系相對比較稀疏[15]，可以表示包含大量個體和個體之間相互作用的系統(tǒng)。然而社團結(jié)構(gòu)在多標(biāo)記數(shù)據(jù)集中的應(yīng)用還不是很廣泛，由于多標(biāo)記學(xué)習(xí)中現(xiàn)有算法已經(jīng)越來越側(cè)重于對標(biāo)記間相互關(guān)系的利用，而多標(biāo)記之間的相關(guān)性亦可以表示成由標(biāo)記節(jié)點形成的網(wǎng)絡(luò)結(jié)構(gòu)，因此，對于多標(biāo)記的節(jié)點結(jié)構(gòu)與特征分析就有了突破口，從而能夠利用社團發(fā)現(xiàn)算法分析標(biāo)記之間的隱含意義。

本文在多標(biāo)記假設(shè)重用方法基礎(chǔ)上，將大量多標(biāo)記數(shù)據(jù)集樣本應(yīng)用該方法有效估計標(biāo)記關(guān)系，并得到標(biāo)記的評分關(guān)系矩陣來量化標(biāo)記關(guān)系的估計結(jié)果，對標(biāo)記關(guān)系進行分析與研究，并將標(biāo)記關(guān)系重組，根據(jù)此結(jié)果利用基于NMF的多標(biāo)記社團發(fā)現(xiàn)方法得到數(shù)據(jù)集樣本中所有標(biāo)記間的社團結(jié)構(gòu)，度量出標(biāo)記的重要程度并作重要性排序，最后驗證其真實性和有效性。

2 多標(biāo)記社團發(fā)現(xiàn)模型和節(jié)點特征分析

由于樣本標(biāo)記數(shù)目較大，并且標(biāo)記間的關(guān)聯(lián)不明顯，所以目前已經(jīng)有許多工作嘗試挖掘和利用標(biāo)記之間的關(guān)系。對于標(biāo)記關(guān)系矩陣，它表示各個節(jié)點之間的相互作用關(guān)系，且這種節(jié)點間的相互作用并不是對稱的[4，9]?，F(xiàn)有的社團發(fā)現(xiàn)算法往往針對的是節(jié)點間有聯(lián)系的0-1鄰接矩陣，或是加權(quán)的鄰接矩陣，通過計算節(jié)點的度來獲得節(jié)點社團關(guān)系與重要程度。然而，對于多標(biāo)記的關(guān)系矩陣，標(biāo)記間存在著正負作用，這種作用就用節(jié)點的權(quán)重來表示，且這種作用并不是完全相互的。同時，多標(biāo)記節(jié)點的重要性不僅與度的大小有關(guān)，而且與該節(jié)點相鄰的節(jié)點特征有很大關(guān)聯(lián)。本文嘗試利用基于NMF的多標(biāo)記社團發(fā)現(xiàn)算法挖掘多標(biāo)記關(guān)系矩陣并揭示多標(biāo)記的社團結(jié)構(gòu)，這對于了解標(biāo)記結(jié)構(gòu)、分析標(biāo)記關(guān)系、理解標(biāo)記含義、發(fā)現(xiàn)標(biāo)記中隱藏的規(guī)律和預(yù)測數(shù)據(jù)集的標(biāo)記都尤為重要，而揭示社團結(jié)構(gòu)的方法就是利用標(biāo)記中所已知的特性和信息，將看似無規(guī)律的標(biāo)記劃分出隱藏在其中的結(jié)構(gòu)。文獻[15]中提出了針對有向加權(quán)節(jié)點的社團劃分方法，定義節(jié)點貢獻比與節(jié)點重要性排名兩個節(jié)點特征指標(biāo)，有效地反映標(biāo)記節(jié)點的特征。本文認為，根據(jù)已知的標(biāo)記關(guān)系矩陣所劃分出的多標(biāo)記社團結(jié)構(gòu)對于多標(biāo)記關(guān)系的研究更具針對性與明確性。在本文中所提到的多標(biāo)記社團結(jié)構(gòu)是指根據(jù)多標(biāo)記社團發(fā)現(xiàn)算法按照某種規(guī)則劃分出多標(biāo)記社團關(guān)系矩陣，該結(jié)構(gòu)對所給出的標(biāo)記關(guān)系有著特殊意義。

2.1 多標(biāo)記社團發(fā)現(xiàn)模型

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

(1)

式中：n表示多標(biāo)記數(shù)據(jù)集樣本維數(shù)；xi=[xi1,xi2,…,xin]表示第i個示例；yi=[yi1,yi2,…yim]為樣本xi的標(biāo)記向量，其中yij∈{-1,+1}，yij=+1表示xi具有標(biāo)記yi，yij=-1表示xi不具有標(biāo)記yi。

算法1 多標(biāo)記社團發(fā)現(xiàn)算法

(2) 輸出：多標(biāo)記社團關(guān)系矩陣Com。

(5) end while(步驟4詳見文獻[4])。

(6) 根據(jù)Zl(x)分別得出多標(biāo)記間正作用與負作用評分Splus，Sminus。

(9) end

定義2 模型候選集合[4,9]

(2)

式中：Zt,k為第t輪更新標(biāo)記yk上的綜合模型[4]。為了優(yōu)化的方便，引入-Zt,k，表示一個輸出與Zt,k正好相反的模型。最后，將由T個基分類器綁定得到的綜合模型ZT,k作為標(biāo)記yl的分類器。

定義3 重用函數(shù)(Reuse function)R[4,9]

(3)

2.1.1 標(biāo)記相關(guān)性

由于算法1在標(biāo)記之間重用彼此已經(jīng)得到的模型，因此根據(jù)文獻[4]可知，可以用重用的多少來衡量標(biāo)記之間關(guān)系的強弱，并將重用評分矩陣作為標(biāo)記的關(guān)系矩陣。如果兩個標(biāo)記是獨立的，那么不同標(biāo)記上模型的預(yù)測則可能產(chǎn)生較大的錯誤率，因此算法會自動地賦予該模型一個很小的權(quán)重。相反，如果標(biāo)記之間是相關(guān)的，各自的模型提供的信息對于預(yù)測其他的標(biāo)記具有重要作用，那么算法就會賦予其較大的權(quán)重。于是通過標(biāo)記重用的權(quán)重ω來度量標(biāo)記關(guān)系。兩個標(biāo)記間的作用有正有負，在更新權(quán)重ω被約束為正的情況下，用ωt,i(-Z*,j)來反映yj對yi的負作用。當(dāng)兩個標(biāo)記的負作用大于正作用時，標(biāo)記關(guān)系就表現(xiàn)為負[4]。而對于NMF來說，要求輸入的關(guān)系矩陣為非負矩陣，因此將重用評分S(i,j)分解為Splus(i,j)和Sminus(i,j)，分別表示標(biāo)記間的正作用和負作用。具體定義yj到標(biāo)記yi的重用評分S(i,j)如式(4)所示。

定義4 重用評分

S(i,j)=Splus(i,j)-Sminus(i,j)

(4)

其中

(5)

(6)

同時，Splus(i,j)和Sminus(i,j)分別為正值，且由Splus和Sminus得到的關(guān)系矩陣Rplus和Rminus均為n×n的方陣(n為標(biāo)記個數(shù))。

設(shè)標(biāo)記關(guān)系矩陣

(7)

式中：G中的元素被約束為非負值，且G為2n×2n的方陣。這樣的方式既能保留所有標(biāo)記之間的相互作用，又能保證關(guān)系矩陣為非負矩陣，并且沒有降低關(guān)系矩陣的維數(shù)。根據(jù)算法得出的標(biāo)記關(guān)系是非對稱的，這在實際工作中有較大意義。

2.1.2 多標(biāo)記中的非負矩陣分解

NMF是一種聚類和降維技術(shù)，具體定義如式(8)所示。

定義5 非負矩陣分解形式

(8)

式中：矩陣G，Com，H分別表示3個非負矩陣。G中的列向量都可以用H中的行向量乘以矩陣Com來表示，其含義是多標(biāo)記關(guān)系矩陣G可用維數(shù)更少的基向量Com來表示。從物理意義上講，由于H是n×k維，Com是k×n維，可利用H將原來矩陣G中的n個節(jié)點聚成k個類，H中每行的值表示節(jié)點對k個社團的隸屬度[15，16]。

算法1可求解出多標(biāo)記社團矩陣Com，其中k作為輸入量，表示定義社團個數(shù)，矩陣Com(0

2.2 多標(biāo)記社團節(jié)點特征分析

在社會網(wǎng)絡(luò)中，社團中的結(jié)點由于豐富的交互性而相互扮演者不同的角色。通常，只有幾個節(jié)點是整個網(wǎng)絡(luò)的中心節(jié)點，而其他節(jié)點對網(wǎng)絡(luò)的影響并不大。對于社交網(wǎng)絡(luò)，頂點的度可以部分反映節(jié)點的重要性，但它不能找出社團中節(jié)點特性的差異。實際工作中，節(jié)點的重要性不僅取決于它的度，也依賴于它的鄰接節(jié)點以及“朋友”關(guān)系。此外，由于網(wǎng)絡(luò)中節(jié)點眾多，這就更有必要研究社團中節(jié)點的特性。通過算法2，在計算得到節(jié)點所屬社團的矩陣Com中，可發(fā)現(xiàn)多標(biāo)記節(jié)點的某些屬性。

算法2 節(jié)點特征算法流程示意圖如圖1所示。

圖1 多標(biāo)記節(jié)點特征算法流程Fig.1 Process of multi-label nodes characteristics algorithm

對于網(wǎng)絡(luò)節(jié)點社團關(guān)系矩陣Com，多標(biāo)記社團的節(jié)點貢獻比描述了節(jié)點對于構(gòu)成各個社團所提供的支持力度。Ci越大，說明多標(biāo)記社團節(jié)點活動集中在某社團，反之則說明沒有明顯的社團特征。異常節(jié)點的活動相對穩(wěn)定，不會集中在某一個固定的社團內(nèi)，與其他節(jié)點尚未形成明顯的社團特征，其Ci值就會比較小。而多標(biāo)記社團節(jié)點重要程度排序Ri就是分別計算每個節(jié)點的貢獻比[15]，進而根據(jù)大小排序。

事實上，在社團工作中，并非所有的節(jié)點都同等重要，對于社團的建立只有少數(shù)節(jié)點發(fā)揮主要作用。傳統(tǒng)的社交網(wǎng)絡(luò)利用節(jié)點度的大小及中心性等概念來判別重要節(jié)點。根據(jù)節(jié)點重要性排序(Ri)可以找到社團中節(jié)點即標(biāo)記的重要性。根據(jù)Ri結(jié)果，第一個節(jié)點在社區(qū)具有最大的Ci，是中心節(jié)點，具有較低的Ci節(jié)點是邊界節(jié)點，并且最低的被定義為在社區(qū)最遠的節(jié)點[15]。中心節(jié)點在社團中起重要作用，而邊界節(jié)點對于社團影響較小。在社團結(jié)構(gòu)中，有時可以只考慮中心節(jié)點，有的邊界節(jié)點就可以忽略。在多標(biāo)記研究中，一些邊界的標(biāo)記對于多標(biāo)記網(wǎng)絡(luò)的影響微乎其微，諸如郵件標(biāo)記中的無用郵件，對于分析郵件內(nèi)容沒有意義，因此可根據(jù)Ri網(wǎng)絡(luò)評估節(jié)點的重要性。

3 實驗分析

3.1 實驗設(shè)置

通過算法1首先得到多標(biāo)記的評分矩陣，其中基分類器使用決策樹樁(Decision stump)，訓(xùn)練輪數(shù)T為2*n(n為特征維數(shù))，進而得到多標(biāo)記的社團結(jié)構(gòu)矩陣。

本實驗中共使用5個數(shù)據(jù)集，包括圖像分類數(shù)據(jù)集Image[17]，Scene[18]，基因功能預(yù)測數(shù)據(jù)集Yeast[19]，郵件分析數(shù)據(jù)集Enron[20]和文獻管理數(shù)據(jù)集BibTex[21]，表1給出了這些數(shù)據(jù)集的統(tǒng)計信息，包括樣本個數(shù)，標(biāo)記個數(shù)，特征維度和平均每個樣本的相關(guān)標(biāo)記個數(shù)。其中Bibtex數(shù)據(jù)集在多標(biāo)記關(guān)系得到過程中已經(jīng)預(yù)先劃分好訓(xùn)練集和測試集，對于其他數(shù)據(jù)集，隨機選擇1 500個樣本作為多標(biāo)記關(guān)系得到過程中的訓(xùn)練集，剩下的樣本作為測試集，并將數(shù)據(jù)的隨機劃分重復(fù)30次。最終利用多標(biāo)記社團發(fā)現(xiàn)算法挖掘5個數(shù)據(jù)集的多標(biāo)記關(guān)系矩陣的社團結(jié)構(gòu)，從而得到標(biāo)記的社團關(guān)系并圖示。

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

Tab.1 Experimental data sets

數(shù)據(jù)集樣本數(shù)量特征維數(shù)標(biāo)記數(shù)量Image20001355Scene24072946Yeast241710314Enron1702100153BibTex73951836159

3.2 多標(biāo)記社團結(jié)構(gòu)驗證

本節(jié)列舉出算法1中的多標(biāo)記關(guān)系矩陣，并展示出多標(biāo)記的社團關(guān)系圖。由于數(shù)據(jù)集標(biāo)記數(shù)目過多，這里只列出兩個標(biāo)記適中的數(shù)據(jù)集的評分矩陣。

算法1在Scene數(shù)據(jù)集上輸出的標(biāo)記之間關(guān)系矩陣G，其中G表示為正作用評分和負作用評分組合的2n×2n方陣，所得的Scene多標(biāo)記關(guān)系矩陣和社團關(guān)系如表2所示。

通過得到的多標(biāo)記關(guān)系矩陣得知，每個社團中除了包含正作用的標(biāo)記元素外，還包含著負作用的標(biāo)記元素。由于標(biāo)記元素是不變的，變化的只是標(biāo)記之間的關(guān)系是正作用還是負作用，因此在標(biāo)記社團結(jié)構(gòu)中，可以同時考慮正作用和負作用的標(biāo)記關(guān)系。根據(jù)文獻[22]，可將正作用的標(biāo)記看作是朋友與信任的促進關(guān)系，而將負作用的標(biāo)記看作是敵人與不信任的排斥關(guān)系。如果在一個社團中既有正作用矩陣中的標(biāo)記，又存在負作用矩陣中的標(biāo)記，那么可以認為負作用標(biāo)記就是正作用標(biāo)記的敵人，即負作用標(biāo)記為正作用標(biāo)記的排斥節(jié)點，而社團發(fā)現(xiàn)就可以看成是在同一個社團結(jié)構(gòu)中找出共同的排斥標(biāo)記，有同一個排斥標(biāo)記的正作用標(biāo)記便可以結(jié)盟形成一個社團(以社團關(guān)系矩陣最終得到的正負作用標(biāo)記個數(shù)為準(zhǔn)，正作用標(biāo)記個數(shù)多，則正作用標(biāo)記形成社團，負作用標(biāo)記個數(shù)多，則負作用形成一個社團。一般社團中的排斥標(biāo)記即負作用標(biāo)記是少數(shù))，因此多標(biāo)記之間相關(guān)性并不是對稱的，而且標(biāo)記之間具有一定的負相關(guān)性。如Sunset(日落)與Fall foliage(秋葉景色)，因為有sunset的景色一般以平原居多，而不是樹木多的Fall foliage。因此若把上述標(biāo)記分為兩類，則得到的多標(biāo)記社團劃分結(jié)果如表3所示。

表2 Scene數(shù)據(jù)集多標(biāo)記關(guān)系矩陣

由表3看出，每一個社團中均包含正作用的標(biāo)記和負作用的標(biāo)記，如果兩個標(biāo)記一定不相關(guān)，那么不會在同一個社團中。如Beach與mountain，有beach的圖片信息中一般不會出現(xiàn)Mountain，反而是出現(xiàn)Sunset較多，因此Beach，Sunset同相反作用的Mountain等劃分為同一社團，以此也能說明Beach與Sunset相關(guān)性強，mountain，F(xiàn)all foliage相關(guān)性強，取兩個社團中都是正作用的標(biāo)記，于是得到最終的多標(biāo)記社團劃分如表4所示。

Scene數(shù)據(jù)集包含6個標(biāo)記：Beach，Sunset，F(xiàn)all foliage，F(xiàn)ield，Mountain和Urban。最終通過多標(biāo)記關(guān)系矩陣作出的社團關(guān)系圖如圖2所示(其中橫線上的數(shù)據(jù)代表歸一化統(tǒng)一處理后的標(biāo)記與標(biāo)記之間相互作用的大小)。社團1{Beach，Sunset}，社團2{Fall foliage，F(xiàn)ield，Mountain，Urban}，在社團1中，Beach與Sunset有很強的相關(guān)性，而Beach與Fall foliage，F(xiàn)ield，Mountain等一般不會同時在一幅圖中出現(xiàn)，甚至有負作用。同時得到兩個社團中最重要的標(biāo)記Beach和Fall foliage，說明兩個標(biāo)記對社團中其他標(biāo)記提供的幫助最多。在Image數(shù)據(jù)集中這種關(guān)系也能夠很好地展現(xiàn)，表5為將Image數(shù)據(jù)集中的標(biāo)記劃分為3個社團的結(jié)果。

表3 Scene數(shù)據(jù)集多標(biāo)記社團結(jié)構(gòu)的初步分析

Tab.3 Preliminary analysis of multi-label community structure of Scene data set

所屬社團包含標(biāo)記正作用負作用1Beach,SunsetFallfoliage,Field,Mountain,Urban2Fallfoliage,Field,Mountain,UrbanSunset,Beach

圖2 Scene數(shù)據(jù)集的多標(biāo)記社團結(jié)構(gòu)Fig.2 Multi-label community structure of Scene data set

所屬社團包含標(biāo)記正作用負作用1Mountain,TreeSunset,Desert2DesertSea3Sea,SunsetMountain,Tree

在Image數(shù)據(jù)集中，將多標(biāo)記劃分為3個社團，可以看到經(jīng)過劃分后，社團1中正作用的Mountain，Tree和負作用的Sunset屬于一個社團，也就是在正常情況下，Mountain，Tree和Sunset沒有太大的相關(guān)性。同理，社團2中Desert和Sea的關(guān)系，以及社團3中Sea，Sunset與Mountain和Tree的關(guān)系正好印證了這一結(jié)果。同樣取3個社團中均為正作用的標(biāo)記形成最終的社團結(jié)構(gòu)，結(jié)果如表6所示。多標(biāo)記社團結(jié)構(gòu)如圖3所示(圖中聯(lián)系為去除冗余聯(lián)系，將標(biāo)記間關(guān)系二值化結(jié)果)。

圖3 Image數(shù)據(jù)集的多標(biāo)記社團結(jié)構(gòu)Fig.3 Multi-label community structure of Image data set

Enron數(shù)據(jù)集由安然公司員工的電子郵件組成，有53個類標(biāo)。由于Enron數(shù)據(jù)集中標(biāo)記的負作用不明顯，因此可單純分析標(biāo)記間的正相關(guān)性。同時，由于Enron數(shù)據(jù)集標(biāo)記較多，只展示排名位于前5的標(biāo)記其重要性大小(表7)。其相應(yīng)的Enron社團包括標(biāo)記及符號如表8所示(受表格大小限制，本表只展示標(biāo)記序號而非標(biāo)記含義)。

表6 Image社團包含標(biāo)記及符號

表7 Enron數(shù)據(jù)集多標(biāo)記社團結(jié)構(gòu)及節(jié)點重要性排名(重要性位于前5的標(biāo)記)

Tab.7 Multi-label community structure and importance rank (top five nodes shown) of Enron data set

所屬社團標(biāo)記數(shù)量No.1No.2No.3No.4No.51170.01660.01610.01470.01370.01332120.01470.01470.01280.01170.00963120.01760.01720.01670.01380.01244120.01890.01740.01700.01490.0124

表8 Enron社團包含標(biāo)記及符號(重要性位于前5的標(biāo)記)

Tab.8 Labels and signs in Enron community (top five nodes shown)

所屬社團包含標(biāo)記表示符號11752274421◆21950393315■32074151▲4458113649●

由表7，8看出，在本數(shù)據(jù)集53個標(biāo)記中，將其劃分為4個社團，根據(jù)重要性排名得到屬于最大的社團貢獻比的標(biāo)記是處于中心位置的標(biāo)記，4個社團的重要標(biāo)記分別為：17-鄙視情緒；19-關(guān)注；20-感激之情；45-保密，其中，45-保密具有最高的重要性排名得分。這4個重要標(biāo)記分別代表了4個社團的主要信息。其中社團1包括不喜歡、欽佩和公司形象等標(biāo)記，代表了員工的某種情緒；社團2包含了關(guān)注、支持、公司業(yè)務(wù)戰(zhàn)略等，體現(xiàn)了員工對公司的某種態(tài)度；社團3包括感激、談話紀要、轉(zhuǎn)發(fā)的郵件和友情等，體現(xiàn)了公司內(nèi)部員工之間的聯(lián)系及良好的關(guān)系；社團4包括保密、文檔、競爭和通訊等，表現(xiàn)出公司最重要、最有價值和最需要謹慎對待的信息。使用表8中對應(yīng)的圖形符號表示相應(yīng)社團的分類，為區(qū)分標(biāo)記的重要性程度，用較大的圖形符號表示社團中最重要的標(biāo)記，最終得到的社團關(guān)系矩陣圖如圖4所示。

圖4 Enron數(shù)據(jù)集的多標(biāo)記社團結(jié)構(gòu)Fig.4 Multi-label community structure of Enron data set

本文已經(jīng)通過該算法得到多標(biāo)記關(guān)系矩陣，通過關(guān)系矩陣可以得到標(biāo)記間兩兩相互作用的強弱，然而，僅有相互作用的關(guān)系矩陣對于多標(biāo)記關(guān)聯(lián)的研究與多標(biāo)記潛在含義的理解沒有太大的幫助。通過本文算法得到的上述結(jié)果，能很明顯知道每一封郵件所屬類別與情感傾向，并區(qū)分出哪些是重要郵件，哪些是無用郵件，可以根據(jù)多標(biāo)記社團發(fā)現(xiàn)結(jié)果對與公司業(yè)務(wù)相關(guān)的郵件進行仔細甄別，從而發(fā)現(xiàn)公司存在的安全漏洞與業(yè)務(wù)疏漏，對與情緒有關(guān)的郵件進行分析可發(fā)現(xiàn)員工的態(tài)度，最終對公司業(yè)務(wù)等獎評績效做出調(diào)整。同時根據(jù)中心標(biāo)記也能挖掘出公司近期的運作情況，員工的態(tài)度是消極還是積極性占主要地位。

通過上述的結(jié)果可以得知，利用多標(biāo)記社團發(fā)現(xiàn)方法不僅能夠得到多標(biāo)記的關(guān)系，同時根據(jù)標(biāo)記關(guān)系將多標(biāo)記進行社團劃分，經(jīng)挖掘?qū)⒂芯o密內(nèi)在關(guān)聯(lián)的標(biāo)記劃分到同一社團，并且得到社團的貢獻率以及多標(biāo)記的重要性排名情況。通過得到上述結(jié)果，多標(biāo)記的主從關(guān)系得以明確的展現(xiàn)，單個標(biāo)記的重要程度也得以體現(xiàn)。相較于文獻[4]通過MAHR算法單純得到的多標(biāo)記關(guān)系，本文最終得到的多標(biāo)記社團結(jié)構(gòu)表示的多標(biāo)記關(guān)系更直觀，社團中的標(biāo)記關(guān)系更強烈，表示的含義更豐富，對于事例的研究更有價值。對于剩余數(shù)據(jù)集的實驗結(jié)果，雖然實驗得到了多標(biāo)記社團結(jié)構(gòu)以及標(biāo)記節(jié)點特征，但是現(xiàn)階段上述數(shù)據(jù)標(biāo)記的具體含義仍舊未知，因此對于社團劃分的結(jié)果不能夠盲目分析其準(zhǔn)確的含義，但是通過上述理論與實驗分析，得到的結(jié)果可為以后的研究提供依據(jù)。

4 結(jié)束語

本文的多標(biāo)記社團發(fā)現(xiàn)算法是在文獻[4]中MAHR算法基礎(chǔ)上，通過重用相關(guān)的標(biāo)記上已經(jīng)訓(xùn)練好的模型來幫助自身的學(xué)習(xí)，并通過最小化每個標(biāo)記上的損失來自動優(yōu)化重用的權(quán)重來自動發(fā)掘標(biāo)記關(guān)系，將標(biāo)記關(guān)系重組，得到多標(biāo)記的關(guān)系矩陣，并基于NMF算法通過迭代方式來挖掘標(biāo)記關(guān)系的社團結(jié)構(gòu)，得到多標(biāo)記的社團關(guān)系矩陣并分析節(jié)點重要性排名，得到節(jié)點的主從關(guān)系。這樣的方式實現(xiàn)了多標(biāo)記學(xué)習(xí)與社團發(fā)現(xiàn)工作的融合，同時得到了多標(biāo)記的社團結(jié)構(gòu)，為多標(biāo)記關(guān)系的研究分析提供了有效的支持，并以此提高學(xué)習(xí)效率。通過大量的多標(biāo)記樣本實驗，本文也證實了多標(biāo)記社團關(guān)系的合理性與有效性。但是由于多標(biāo)記數(shù)據(jù)集信息的局限性，實驗部分還缺少更多的多標(biāo)記數(shù)據(jù)進行驗證，下階段將尋找更多不同領(lǐng)域的數(shù)據(jù)進行社團分析，將本文的實驗結(jié)果應(yīng)用于更廣泛的數(shù)據(jù)挖掘領(lǐng)域。

[1] Zhang Minling, Zhou Zhihua. A review on multi-label learning algorithms[J]. IEEE Transactions on Knowledge & Data Engineering, 2014, 26(8):1819-1837.

[2] Girvan M, Newman M E J. Community structure in social and biological networks[J]. Proceedings of the National Academy of Sciences of the United States of America, 2002, 99(12):7821-7826.

[3] Gibaja E. A tutorial on multi-label learning[J]. ACM Computing Surveys, 2015, 47(3):1-38.

[4] 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. New York, USA: ACM, 2012: 525-533.

[5] McCallum A. Multi-label text classification with a mixture model trained by EM[C]∥AAAI′99 Workshop on Text Learning. Palo Alto,USA: AAAI,1999: 1-7.

[6] Schapire R E, Singer Y. BoosTexter: A boosting-based system for text categorization[J]. Machine Learning, 2000, 39(2/3): 135-168.

[7] 張敏靈. 偏標(biāo)記學(xué)習(xí)研究綜述[J]. 數(shù)據(jù)采集與處理, 2015, 30(1):77-87.

Zhang Minling. Research on partial label learning[J]. Journal of Data Acquisition and Processing, 2015, 30(1):77-87.

[8] Zhou Zhihua. Exploitation of label relationship in multi-label learning[C]∥ Proceedings of the 2012 IEEE International Conference on Granular Computing (GrC-2012). New Orleans, LA, USA: IEEE Computer Society, 2012:19.

[9] 黃圣君. 多標(biāo)記學(xué)習(xí)中標(biāo)記關(guān)系利用的研究[D]. 南京:南京大學(xué),2014.

Huang Shengjun. Research on label relationship exploitation in multi-label learning[D]. Nanjing: Nanjing University,2014.

[10]何志芬, 楊明, 劉會東. 多標(biāo)記分類和標(biāo)記相關(guān)性的聯(lián)合學(xué)習(xí)[J]. 軟件學(xué)報, 2014，25(9):1967-1981.

He Zhifen, Yang Ming, Liu Huidong. Joint learning of multi-label classification and label correlations[J]. Journal of Software, 2014, 25(9):1967-1981.

[11]Newman M E J. Detecting community structure in networks[J]. The European Physical Journal B, 2004,38(2):321-330.

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

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

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

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

[14]李樂, 章毓晉. 非負矩陣分解算法綜述[J]. 電子學(xué)報, 2008, 36(4): 737-743.

Li Le, Zhang Yujin. A survey on algorithms of non-negative matrix factorization[J]. Acta Electronica Sinica, 2008, 36(4): 737-743.

[15]Li Guopeng, Pan Zhisong, Xiao Bo, et al. Community discovery and importance analysis in social network[J]. Intelligent Data Analysis, 2014, 18(3):495-510.

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

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

[17]Zhang Minling, Zhou Zhihua. ML-KNN: A lazy learning approach to multi-label learning[J]. Pattern Recognition, 2007, 40(7):2038-2048.

[18]Boutell M R, Luo J, Shen X, et al. Learning multi-label scene classification[J]. Pattern Recognition, 2004, 37(9):1757-1771.

[19]Elisseeff A, Weston J. A kernel method for multi-labeled classification[J]. Advances in Neural Information Processing Systems, 2001,14(2):681-687.

[20]Klimt B, Yang Y. Introducing the Enron corpus[C]∥ CEAS 2004-First Conference on Email and Anti-Spam, Mountain View. California, USA:[s.n.], 2004: 30-31.

[21]Katakis I, Tsoumakas G, Vlahavas I. Multilabel text classification for automated tag suggestion[J]. ECML PKDD Discovery Challenge, 2008, 75(1):83-91.

[22]Fortunato S, Barthélemy M. Resolution limit in community detection[J]. Proceedings of the National Academy of Sciences, 2007, 104(1): 36-41.

Multi-label Community Detection Algorithm based on Multi-label Relationship

Li Na1,2, Pan Zhisong1, Shi Lei1, Xue Jiao1,2, Ren Yiqiang3

(1.College of Command Information Systems, PLA University of Science and Technology, Nanjing, 210007, China; 2.The 32th Research Institute of China Electronic Technology Group Corporation, Shanghai, 201808, China; 3.SIEMENS Power Automation Co, Ltd., Nanjing, 211100, China)

The objects of the real world can be assigned multiple meaning, with a variety of non-single labels. As to multi-label learning, although the related current work may take advantage of the reuse score to analyze the relationship between multiple labels, it still can find neither the label structure nor the main labels and importance rankings. The nonnegative matrix factorization (NMF) method can divide associated nodes into societies effectively, and explore the potential relationship between them. Consequently, it is worth studying how to use NMF in multi-label community detection. Here, an algorithm is proposed for multi-label community detection, which can analysis labels effectively and discover the community structure inside, and then obtain relations community. Besides, these multi-label nodes can be sorted according to their importance scores, and then the master-slave structure of these marked nodes can be obtained and the effectiveness of this algorithm is thus verified, which helps us learn the hidden information.

multi-label; label relations; nonnegative matrix factorization; community detection

國家自然科學(xué)基金(61473149)資助項目。

2015-03-12；

2016-06-02

TP391

A

李娜(1990-)，女，碩士研究生，研究方向：模式識別與機器學(xué)習(xí)，E-mail：idafighting@163.com。

薛膠(1990-)，男，碩士研究生，研究方向：模式識別與機器學(xué)習(xí)。

潘志松(1973-)，男，教授，博士生導(dǎo)師，研究方向：模式識別與機器學(xué)習(xí)。

任義強(1987-)，男，工程師,研究方向：電力繼電保護及SCADA。

施蕾(1981-)，女，博士，講師，研究方向：計算機軟件理論、數(shù)據(jù)挖掘。