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

李 娜 潘志松 施 蕾 薛 膠 任義強(qiáng)

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

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

李 娜1,2潘志松1施 蕾1薛 膠1,2任義強(qiáng)3

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

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

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

引 言

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

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

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

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

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

隨著信息社會(huì)的高度發(fā)展，各種海量數(shù)據(jù)以及信息觸手可及。在物質(zhì)世界中，各種事物和各類現(xiàn)象基本上可由具備多種屬性的海量數(shù)據(jù)表示。在多標(biāo)記學(xué)習(xí)框架下，每個(gè)樣本由一個(gè)特征向量表示，但此樣本可能同時(shí)隸屬于多個(gè)類別標(biāo)記，這樣做的目的就是通過學(xué)習(xí)給定的多標(biāo)記訓(xùn)練集從而能夠有效預(yù)測未知樣本的類別標(biāo)記。然而，在傳統(tǒng)的監(jiān)督學(xué)習(xí)框架下，待學(xué)習(xí)樣本是具有明確的而單一的類別標(biāo)記，即每個(gè)樣本只隸屬于一個(gè)標(biāo)記，因此難以處理真實(shí)世界的多義性對(duì)象。針對(duì)上述問題，自20世紀(jì)90年代末起，機(jī)器學(xué)習(xí)領(lǐng)域的研究者們不斷關(guān)注如何對(duì)多標(biāo)記對(duì)象有效建模，多標(biāo)記學(xué)習(xí)[5-7]框架應(yīng)運(yùn)而生，并成為一個(gè)具有挑戰(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è)計(jì)多標(biāo)記學(xué)習(xí)算法處理多標(biāo)記數(shù)據(jù)，即改編一些著名的算法來直接處理多標(biāo)記數(shù)據(jù)[10]。無論是PTM或是AAM，多標(biāo)記學(xué)習(xí)算法都面臨著一個(gè)相同且關(guān)鍵的問題，即如何利用標(biāo)記之間的關(guān)系[4]，這對(duì)于解決維度災(zāi)難有重要的意義。隨著對(duì)機(jī)器學(xué)習(xí)理論和應(yīng)用的研究日益深入，多標(biāo)記學(xué)習(xí)近年來已經(jīng)逐漸成為機(jī)器學(xué)習(xí)和模式識(shí)別領(lǐng)域的熱門課題，大量的公開數(shù)據(jù)集以及專門針對(duì)多標(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í)的最主要特點(diǎn)就是不同標(biāo)記之間存在相互關(guān)系。根據(jù)標(biāo)記之間的關(guān)系就能使得其中有價(jià)值信息互相幫助，提高學(xué)習(xí)效率。比如標(biāo)記之間的促進(jìn)和互斥關(guān)系能夠有效避免不必要的訓(xùn)練和測試。另外在樣本不足情況下，標(biāo)記也可以利用其他具有足夠樣本的相關(guān)標(biāo)記上的信息來幫助自身學(xué)習(xí)。因?yàn)?，多個(gè)標(biāo)記之所以同時(shí)與一個(gè)樣本關(guān)聯(lián)，意味著這些標(biāo)記之間本身也存在著一定的相關(guān)性，于是如何利用標(biāo)記關(guān)系來幫助學(xué)習(xí)是多標(biāo)記學(xué)習(xí)的關(guān)鍵任務(wù)。

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

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

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

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

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

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

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

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

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

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

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

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

(1)

式中：n表示多標(biāo)記數(shù)據(jù)集樣本維數(shù)；xi=[xi1,xi2,…,xin]表示第i個(gè)示例；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)記社團(tuán)發(fā)現(xiàn)算法

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

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

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

(9) end

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

(2)

式中：Zt,k為第t輪更新標(biāo)記yk上的綜合模型[4]。為了優(yōu)化的方便，引入-Zt,k，表示一個(gè)輸出與Zt,k正好相反的模型。最后，將由T個(gè)基分類器綁定得到的綜合模型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ù)文獻(xiàn)[4]可知，可以用重用的多少來衡量標(biāo)記之間關(guān)系的強(qiáng)弱，并將重用評(píng)分矩陣作為標(biāo)記的關(guān)系矩陣。如果兩個(gè)標(biāo)記是獨(dú)立的，那么不同標(biāo)記上模型的預(yù)測則可能產(chǎn)生較大的錯(cuò)誤率，因此算法會(huì)自動(dòng)地賦予該模型一個(gè)很小的權(quán)重。相反，如果標(biāo)記之間是相關(guān)的，各自的模型提供的信息對(duì)于預(yù)測其他的標(biāo)記具有重要作用，那么算法就會(huì)賦予其較大的權(quán)重。于是通過標(biāo)記重用的權(quán)重ω來度量標(biāo)記關(guān)系。兩個(gè)標(biāo)記間的作用有正有負(fù)，在更新權(quán)重ω被約束為正的情況下，用ωt,i(-Z*,j)來反映yj對(duì)yi的負(fù)作用。當(dāng)兩個(gè)標(biāo)記的負(fù)作用大于正作用時(shí)，標(biāo)記關(guān)系就表現(xiàn)為負(fù)[4]。而對(duì)于NMF來說，要求輸入的關(guān)系矩陣為非負(fù)矩陣，因此將重用評(píng)分S(i,j)分解為Splus(i,j)和Sminus(i,j)，分別表示標(biāo)記間的正作用和負(fù)作用。具體定義yj到標(biāo)記yi的重用評(píng)分S(i,j)如式(4)所示。

定義4 重用評(píng)分

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

(4)

其中

(5)

(6)

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

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

(7)

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

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

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

定義5 非負(fù)矩陣分解形式

(8)

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

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

2.2 多標(biāo)記社團(tuán)節(jié)點(diǎn)特征分析

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

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

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

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

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

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

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

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

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

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

Tab.1 Experimental data sets

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

表6 Image社團(tuán)包含標(biāo)記及符號(hào)

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

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

所屬社團(tuán)標(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社團(tuán)包含標(biāo)記及符號(hào)(重要性位于前5的標(biāo)記)

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

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

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

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

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

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

4 結(jié)束語

本文的多標(biāo)記社團(tuán)發(fā)現(xiàn)算法是在文獻(xiàn)[4]中MAHR算法基礎(chǔ)上，通過重用相關(guān)的標(biāo)記上已經(jīng)訓(xùn)練好的模型來幫助自身的學(xué)習(xí)，并通過最小化每個(gè)標(biāo)記上的損失來自動(dòng)優(yōu)化重用的權(quán)重來自動(dòng)發(fā)掘標(biāo)記關(guān)系，將標(biāo)記關(guān)系重組，得到多標(biāo)記的關(guān)系矩陣，并基于NMF算法通過迭代方式來挖掘標(biāo)記關(guān)系的社團(tuán)結(jié)構(gòu)，得到多標(biāo)記的社團(tuán)關(guān)系矩陣并分析節(jié)點(diǎn)重要性排名，得到節(jié)點(diǎn)的主從關(guān)系。這樣的方式實(shí)現(xiàn)了多標(biāo)記學(xué)習(xí)與社團(tuán)發(fā)現(xiàn)工作的融合，同時(shí)得到了多標(biāo)記的社團(tuán)結(jié)構(gòu)，為多標(biāo)記關(guān)系的研究分析提供了有效的支持，并以此提高學(xué)習(xí)效率。通過大量的多標(biāo)記樣本實(shí)驗(yàn)，本文也證實(shí)了多標(biāo)記社團(tuán)關(guān)系的合理性與有效性。但是由于多標(biāo)記數(shù)據(jù)集信息的局限性，實(shí)驗(yàn)部分還缺少更多的多標(biāo)記數(shù)據(jù)進(jìn)行驗(yàn)證，下階段將尋找更多不同領(lǐng)域的數(shù)據(jù)進(jìn)行社團(tuán)分析，將本文的實(shí)驗(yàn)結(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]何志芬, 楊明, 劉會(huì)東. 多標(biāo)記分類和標(biāo)記相關(guān)性的聯(lián)合學(xué)習(xí)[J]. 軟件學(xué)報(bào), 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ò)中的社團(tuán)結(jié)構(gòu)算法綜述[J]. 電子科技大學(xué)學(xué)報(bào), 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]李樂, 章毓晉. 非負(fù)矩陣分解算法綜述[J]. 電子學(xué)報(bào), 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)社團(tuá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)資助項(xiàng)目。

2015-03-12；

2016-06-02

TP391

A

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

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

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

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

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