基于種子節(jié)點(diǎn)選擇的網(wǎng)絡(luò)環(huán)境下多標(biāo)簽分類(lèi)算法研究

吳信東，趙銀鳳，李 磊

(1.合肥工業(yè)大學(xué)計(jì)算機(jī)與信息學(xué)院，安徽合肥 230009； 2.佛蒙特大學(xué)計(jì)算機(jī)科學(xué)系，美國(guó)伯靈頓 VT05405)

?

基于種子節(jié)點(diǎn)選擇的網(wǎng)絡(luò)環(huán)境下多標(biāo)簽分類(lèi)算法研究

吳信東1,2，趙銀鳳1，李 磊1

(1.合肥工業(yè)大學(xué)計(jì)算機(jī)與信息學(xué)院，安徽合肥 230009； 2.佛蒙特大學(xué)計(jì)算機(jī)科學(xué)系，美國(guó)伯靈頓 VT05405)

多標(biāo)簽分類(lèi)在基因分類(lèi)，藥物發(fā)現(xiàn)和文本分類(lèi)等實(shí)際問(wèn)題中有著廣泛的應(yīng)用.已存在的多標(biāo)簽分類(lèi)算法，通常都是從網(wǎng)絡(luò)中隨機(jī)的選取節(jié)點(diǎn)作為訓(xùn)練集.然而，在分類(lèi)算法執(zhí)行的過(guò)程中，網(wǎng)絡(luò)中不同節(jié)點(diǎn)所起的作用不同.在給定訓(xùn)練集數(shù)目的情況下，選擇的訓(xùn)練集不同，分類(lèi)精度也會(huì)不同.所以我們引入了種子節(jié)點(diǎn)的概念，標(biāo)簽分類(lèi)從種子節(jié)點(diǎn)開(kāi)始，經(jīng)過(guò)不斷推理，得到網(wǎng)絡(luò)中其他所有節(jié)點(diǎn)的標(biāo)簽.本文提出了SHDA(Nodes Selection of High Degree from Each Affiliation)算法，即從網(wǎng)絡(luò)的每個(gè)社團(tuán)中，按比例的選取度數(shù)較大的節(jié)點(diǎn)，然后將其合并，處理后得到種子節(jié)點(diǎn).真實(shí)數(shù)據(jù)集上的實(shí)驗(yàn)表明，將種子節(jié)點(diǎn)用作訓(xùn)練集進(jìn)行多標(biāo)簽分類(lèi)，能夠提升網(wǎng)絡(luò)環(huán)境下多標(biāo)簽分類(lèi)的準(zhǔn)確率.

多標(biāo)簽分類(lèi)；網(wǎng)絡(luò)；種子節(jié)點(diǎn)；推理；社團(tuán)

1 引言

目前，多標(biāo)簽分類(lèi)問(wèn)題已經(jīng)取得了廣泛關(guān)注，并且在實(shí)際問(wèn)題中有很多應(yīng)用，比如：基因分類(lèi)，藥物發(fā)現(xiàn)和文本分類(lèi)[1].已存在的多標(biāo)簽分類(lèi)算法，通常都是隨機(jī)的選取節(jié)點(diǎn)作為訓(xùn)練集.然而，在分類(lèi)算法執(zhí)行的過(guò)程中，網(wǎng)絡(luò)中不同節(jié)點(diǎn)所起的作用不同.在給定訓(xùn)練集數(shù)目的情況下，選擇的訓(xùn)練集不同，分類(lèi)精度也會(huì)不同.所以隨機(jī)方法不能有效的利用網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)，導(dǎo)致節(jié)點(diǎn)的標(biāo)簽分類(lèi)結(jié)果不穩(wěn)定.

本文引入了種子節(jié)點(diǎn)的概念，分類(lèi)從種子節(jié)點(diǎn)開(kāi)始，通過(guò)不斷推理，得到網(wǎng)絡(luò)中其他節(jié)點(diǎn)的標(biāo)簽.應(yīng)該如何選擇種子節(jié)點(diǎn)，從而在給定的多標(biāo)簽分類(lèi)算法下獲得較高的分類(lèi)精度，是本文所要解決的問(wèn)題，例如：一個(gè)大學(xué)的所有學(xué)生組成了一個(gè)網(wǎng)絡(luò)，學(xué)生的標(biāo)簽代表他們的興趣愛(ài)好，如果用一部分學(xué)生的標(biāo)簽來(lái)預(yù)測(cè)其他學(xué)生的標(biāo)簽，那么我們要解決的問(wèn)題是，在網(wǎng)絡(luò)中應(yīng)該選擇什么樣的學(xué)生作為種子節(jié)點(diǎn)，從而使預(yù)測(cè)結(jié)果最好呢？

我們提出了SHDA算法來(lái)選擇種子節(jié)點(diǎn).首先使用EdgeCluster算法來(lái)獲取網(wǎng)絡(luò)中的節(jié)點(diǎn)之間潛在的社團(tuán)[2]，接著根據(jù)每個(gè)社團(tuán)中包含的節(jié)點(diǎn)數(shù)目大小，按比例的選取每個(gè)社團(tuán)中度數(shù)較高的一些節(jié)點(diǎn)，然后將其合并，處理后得到種子節(jié)點(diǎn).本文將種子節(jié)點(diǎn)用作訓(xùn)練集進(jìn)行多標(biāo)簽分類(lèi)來(lái)驗(yàn)證SHDA算法的有效性.

2 相關(guān)工作

網(wǎng)絡(luò)環(huán)境下的多標(biāo)簽分類(lèi)數(shù)據(jù)一般具有同質(zhì)性，即服從一階馬爾科夫假設(shè)，節(jié)點(diǎn)的標(biāo)簽傾向于與其直接鄰居的標(biāo)簽相同.關(guān)系學(xué)習(xí)利用對(duì)象之間的聯(lián)系來(lái)進(jìn)行多標(biāo)簽分類(lèi)，可以取得較好的分類(lèi)結(jié)果[3].集體推理可以進(jìn)一步改善分類(lèi)的性能，減少分類(lèi)錯(cuò)誤[3～5].wvRN(weighted-vote Relational Neighbor classifier)算法計(jì)算節(jié)點(diǎn)vi屬于類(lèi)c的概率，P(yi=c|vi)，是其鄰居中屬于類(lèi)c的概率的帶權(quán)平均值:

(1)

還有一種方法是利用標(biāo)簽間的相關(guān)性，鄭等提出了一種基于隨機(jī)游走模型的多標(biāo)簽分類(lèi)算法MLRW(Multi-Label Random Walk algorithm)[7].

然而傳統(tǒng)方法無(wú)法區(qū)分異質(zhì)網(wǎng)絡(luò)中對(duì)象和邊的類(lèi)型的差異.Ji等[8]提出了基于排序的迭代分類(lèi)模型(Rankclass)，提高了異質(zhì)網(wǎng)絡(luò)中的分類(lèi)性能.Kong等[9]通過(guò)挖掘異質(zhì)網(wǎng)絡(luò)中對(duì)象間和標(biāo)簽間的關(guān)系進(jìn)行多標(biāo)簽分類(lèi).Tang 等[2]提出了EdgeCluster算法，其以連接邊的節(jié)點(diǎn)作為特征，使用Scalable K-means Variant方法將網(wǎng)絡(luò)的邊聚類(lèi)成多個(gè)互不相交的集合，根據(jù)聚類(lèi)結(jié)果，構(gòu)建網(wǎng)絡(luò)的社會(huì)維度，將其作為特征，使用SVM(Support Vector Machines)算法進(jìn)行多標(biāo)簽分類(lèi).SCRN(multi-label iterative Relation Neighbor Classifier that employs Social features)算法[10]拓展了關(guān)系鄰居分類(lèi)器，其計(jì)算節(jié)點(diǎn)vi屬于類(lèi)c的概率為：

(2)

在種子節(jié)點(diǎn)選擇方面，Qian等通過(guò)在隱式社交網(wǎng)絡(luò)中選擇種子節(jié)點(diǎn)解決了網(wǎng)絡(luò)的影響力最大化問(wèn)題[12].Jankowski等通過(guò)選擇種子節(jié)點(diǎn)進(jìn)行社交網(wǎng)絡(luò)中的信息傳播[13].

3 SHDA算法

我們首先介紹一下種子節(jié)點(diǎn)的定義.

定義1(種子節(jié)點(diǎn)) 種子節(jié)點(diǎn)是網(wǎng)絡(luò)環(huán)境下多標(biāo)簽分類(lèi)的起點(diǎn)，通過(guò)整個(gè)網(wǎng)絡(luò)對(duì)標(biāo)簽的傳播和擴(kuò)散，可預(yù)測(cè)出網(wǎng)絡(luò)中其他節(jié)點(diǎn)的標(biāo)簽.

下面介紹本文提出的SHDA算法的步驟：

第1步：計(jì)算網(wǎng)絡(luò)中各節(jié)點(diǎn)的度數(shù).

第2步：使用EdgeCluster算法[2]提取網(wǎng)絡(luò)的社會(huì)維度.社會(huì)維度是節(jié)點(diǎn)對(duì)各個(gè)社團(tuán)從屬程度的描述，一個(gè)節(jié)點(diǎn)可以從屬于多個(gè)社團(tuán)[14].我們?nèi)コ總€(gè)社團(tuán)中屬于測(cè)試集的節(jié)點(diǎn)，計(jì)算η={η1,η2,…,ηN} ，即每個(gè)社團(tuán)中包含的節(jié)點(diǎn)數(shù)目，以節(jié)點(diǎn)度數(shù)由高到底的順序?qū)γ總€(gè)社團(tuán)中的節(jié)點(diǎn)進(jìn)行排序.

第3步：計(jì)算需要從每個(gè)社團(tuán)中選取的節(jié)點(diǎn)數(shù)目mi：

(3)

其中ntr代表訓(xùn)練集的大小，向上取整函數(shù)保證了mi是一個(gè)整數(shù).從每個(gè)社團(tuán)中選取前mi個(gè)節(jié)點(diǎn)，這些節(jié)點(diǎn)即是度數(shù)排在前mi個(gè)的節(jié)點(diǎn).

第4步：合并上述從每個(gè)社團(tuán)中所選的節(jié)點(diǎn)作為種子節(jié)點(diǎn)集合，由于一個(gè)節(jié)點(diǎn)可以從屬于多個(gè)社團(tuán)，導(dǎo)致節(jié)點(diǎn)的重復(fù)選取，同時(shí)向上取整函數(shù)也會(huì)導(dǎo)致節(jié)點(diǎn)選擇的增多，使得種子節(jié)點(diǎn)集合的數(shù)目與訓(xùn)練集大小不相等，所以要去除重復(fù)節(jié)點(diǎn)，然后調(diào)整種子節(jié)點(diǎn)集合大小.

去除重復(fù)節(jié)點(diǎn)后的種子節(jié)點(diǎn)集合大小記為nseed，若nseed>ntr，我們就從種子節(jié)點(diǎn)集合中隨機(jī)選取ntr個(gè)節(jié)點(diǎn)作為種子節(jié)點(diǎn)，若nseed

算法流程總結(jié)起來(lái)就是：無(wú)向圖G被劃分成多個(gè)社團(tuán)，在每個(gè)社團(tuán)中去除屬于測(cè)試集的節(jié)點(diǎn)，利用式(3)選取前mi個(gè)度數(shù)較大的節(jié)點(diǎn)，然后合并為種子節(jié)點(diǎn)集合，最后去除重復(fù)節(jié)點(diǎn)，調(diào)整種子節(jié)點(diǎn)集合大小后，得到種子節(jié)點(diǎn).

種子節(jié)點(diǎn)的標(biāo)簽是已知的，并且標(biāo)簽分類(lèi)從這些節(jié)點(diǎn)開(kāi)始，經(jīng)過(guò)不斷推理，得到網(wǎng)絡(luò)中其他節(jié)點(diǎn)的標(biāo)簽.選擇的種子節(jié)點(diǎn)度數(shù)都比較高，與其他節(jié)點(diǎn)的聯(lián)系比較緊密，同時(shí)種子節(jié)點(diǎn)在每個(gè)社團(tuán)上分布的比較均勻，有利于標(biāo)簽傳播過(guò)程中，更準(zhǔn)確的把標(biāo)簽擴(kuò)散至整個(gè)網(wǎng)絡(luò)，減少分類(lèi)錯(cuò)誤，改善多標(biāo)簽分類(lèi)的性能.

4 實(shí)驗(yàn)設(shè)計(jì)

我們選擇了3個(gè)真實(shí)數(shù)據(jù)集，DBLP、BlogCatalog 和YouTube進(jìn)行實(shí)驗(yàn)[2,10].關(guān)于數(shù)據(jù)集的詳細(xì)信息見(jiàn)表1.

我們使用SHDA算法選擇的種子節(jié)點(diǎn)作為訓(xùn)練集，并分別使用SCRN、wvRN和Edge(EdgeCluster)算法進(jìn)行網(wǎng)絡(luò)環(huán)境下的多標(biāo)簽分類(lèi)實(shí)驗(yàn)，記為SHDA+SCRN、SHDA+wvRN和SHDA+Edge.在對(duì)比算法中，我們隨機(jī)的從網(wǎng)絡(luò)中選擇節(jié)點(diǎn)作為訓(xùn)練集，分類(lèi)算法也采用SCRN、wvRN和Edge算法，記為randomly+SCRN、randomly+wvRN和randomly+Edge.通過(guò)比較SHDA+SCRN/wvRN/Edge和randomly+SCRN/wvRN/Edge方法的分類(lèi)評(píng)估結(jié)果，來(lái)驗(yàn)證SHDA算法的有效性.

我們將DBLP、BlogCatalog和YouTube數(shù)據(jù)集的社會(huì)特征的維數(shù)分別設(shè)置為1000、5000和1000[2,10]，訓(xùn)練集選擇的比例分別設(shè)置為5%到30%，10%到60%和1%到10%.我們采用網(wǎng)絡(luò)交叉驗(yàn)證NCV(Network Cross-Validation)方法[15]來(lái)減少測(cè)試樣本的重疊選取.評(píng)估指標(biāo)選用宏觀(guān)F1值，微觀(guān)F1值和漢明損失(Hamming Loss)[10].Micro-F1值和Macro-F1值越大，分類(lèi)性能越好，Hamming Loss值越小，分類(lèi)性能越好.實(shí)驗(yàn)結(jié)果取10次實(shí)驗(yàn)的平均值.

表1 數(shù)據(jù)集描述

5 實(shí)驗(yàn)結(jié)果與分析

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

實(shí)驗(yàn)結(jié)果記錄在表2～4中，代表randomly+SCRN/wvRN/Edge方法和SHDA+SCRN/wvRN/Edge方法在各個(gè)數(shù)據(jù)集上的多標(biāo)簽分類(lèi)結(jié)果.

YouTube數(shù)據(jù)集上的實(shí)驗(yàn)結(jié)果記錄在表2中，分析數(shù)據(jù)可知：在Micro-F1指標(biāo)下，SHDA+SCRN、SHDA+Edge和SHDA+wvRN方法分別比randomly+SCRN、randomly+Edge和randomly+wvRN方法提高了15.63%、3.16%和-6.45%.在Macro-F1指標(biāo)下，提高了46.78%、2.53%和4.42%.在Hamming Loss指標(biāo)下，降低了4.26%、1.15%和-4.47%.

BlogCatalog數(shù)據(jù)集上的實(shí)驗(yàn)結(jié)果記錄在表3中，分析結(jié)果可得：SHDA算法應(yīng)用于SCRN、EdgeCluster和wvRN算法分別比隨機(jī)方法應(yīng)用于這些算法，提高了9.08%、-0.68%和4.34%的Micro-F1值，提高了14.82%、-0.64%和5.32%的Macro-F1值，降低了2.81%、-0.30%和1.54%的Hamming Loss值.

DBLP數(shù)據(jù)集上的實(shí)驗(yàn)結(jié)果記錄在表4中，由結(jié)果可得：SHDA+SCRN、SHDA+Edge和SHDA+wvRN方法分別比randomly+SCRN、randomly+Edge和randomly+wvRN方法，提高了3.18%、5.89%和1.15%的Micro-F1值，提高了3.47%、7.92%和0.94%.的Macro-F1值，降低了3.69%、5.33%和1.18%的Hamming Loss值.

綜合所述，大部分情況下，SHDA算法在多標(biāo)簽分類(lèi)方法上的性能要比隨機(jī)方法好.某些情況下，SHDA

表2 YouTube數(shù)據(jù)集上實(shí)驗(yàn)結(jié)果

算法表現(xiàn)的不如隨機(jī)方法，可能是因?yàn)镾HDA算法在最后一步時(shí)，從集合G′中隨機(jī)選取ntr-nseed個(gè)節(jié)點(diǎn)并入訓(xùn)練集，導(dǎo)致SHDA算法在多標(biāo)簽分類(lèi)實(shí)驗(yàn)中表現(xiàn)的稍微不穩(wěn)定.但是從整體上來(lái)說(shuō)，SHDA算法由于利用了網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)，有助于提高網(wǎng)絡(luò)環(huán)境下多標(biāo)簽分類(lèi)的性能.

表3 BlogCatalog數(shù)據(jù)集上實(shí)驗(yàn)結(jié)果

表4 DBLP數(shù)據(jù)集上實(shí)驗(yàn)結(jié)果

5.2 算法迭代次數(shù)分析

SCRN和wvRN算法使用標(biāo)簽松弛法來(lái)進(jìn)行集體推理.在每一次迭代過(guò)程中，算法根據(jù)上一次的預(yù)測(cè)結(jié)果，逐次更新節(jié)點(diǎn)屬于各個(gè)類(lèi)的概率，更新類(lèi)的參考特征，更新類(lèi)的傳播概率，根據(jù)更新后的結(jié)果預(yù)測(cè)標(biāo)簽，直至預(yù)測(cè)出的節(jié)點(diǎn)標(biāo)簽趨于穩(wěn)定或者迭代次數(shù)到達(dá)最大值，算法終止.

我們?cè)赮ouTube、BlogCatalog和DBLP三個(gè)數(shù)據(jù)集上分別做了實(shí)驗(yàn)來(lái)討論SHDA+SCRN/wvRN 和randomly+SCRN/wvRN方法的實(shí)驗(yàn)結(jié)果隨著迭代次數(shù)的變化情況.EdgeCluster算法利用社會(huì)特征使用SVM算法進(jìn)行分類(lèi)，不在本部分討論的范圍之內(nèi).圖1～3記錄了YouTube、BlogCatalog和DBLP數(shù)據(jù)集上，訓(xùn)練集分別選擇2%、5%和20%時(shí)，實(shí)驗(yàn)結(jié)果隨著迭代次數(shù)的變化情況.

分析結(jié)果發(fā)現(xiàn)，SHDA+SCRN/wvRN方法的實(shí)驗(yàn)結(jié)果在迭代次數(shù)大于5的時(shí)候基本趨于穩(wěn)定.而randomly+SCRN/wvRN方法可能導(dǎo)致實(shí)驗(yàn)結(jié)果在迭代次數(shù)等于2的時(shí)候達(dá)到達(dá)最大值，然后隨著迭代次數(shù)的增加而下降.所以SHDA算法應(yīng)用于多標(biāo)簽分類(lèi)時(shí)有助于保持算法的穩(wěn)定性.

5.3 算法運(yùn)行效率分析

分析SHDA算法可知，該算法的執(zhí)行時(shí)間與社會(huì)特征的維數(shù)，網(wǎng)絡(luò)規(guī)模以及種子節(jié)點(diǎn)數(shù)目有關(guān).其中社會(huì)特征的維數(shù)對(duì)SHDA算法的影響最大.而隨機(jī)方法只與網(wǎng)絡(luò)的節(jié)點(diǎn)數(shù)和訓(xùn)練集大小相關(guān).我們?cè)贗ntel(R)雙核2.60GHz，32GB內(nèi)存的PC機(jī)上分別計(jì)算了SHDA算法和隨機(jī)方法應(yīng)用于多標(biāo)簽分類(lèi)時(shí)，各算法的運(yùn)行時(shí)間，結(jié)果記錄在表5～8中，單位時(shí)間為s.

分析結(jié)果可得：SHDA算法在BlogCatalog數(shù)據(jù)集上耗時(shí)最長(zhǎng)，其次是YouTube數(shù)據(jù)集，再次是DBLP數(shù)據(jù)集.SHDA算法由于利用了網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)，執(zhí)行的時(shí)間沒(méi)有隨機(jī)方法快，但是時(shí)間是在可以接受的范圍內(nèi)(10s以?xún)?nèi)).

與隨機(jī)方法相比，SHDA算法應(yīng)用于SCRN和wvRN算法時(shí)，降低了SCRN和wvRN算法的執(zhí)行時(shí)間.因?yàn)榉N子節(jié)點(diǎn)與網(wǎng)絡(luò)中其他節(jié)點(diǎn)的關(guān)聯(lián)性較強(qiáng)，能夠加快標(biāo)簽傳播和擴(kuò)散的速度.EdgeCluster算法在使用種子節(jié)點(diǎn)后，算法的執(zhí)行時(shí)間增大，因?yàn)镋dgeCluster算法利用節(jié)點(diǎn)的社會(huì)特征使用SVM分類(lèi)器進(jìn)行分類(lèi)，種子節(jié)點(diǎn)帶有的特征比一般節(jié)點(diǎn)多，使得算法需要花費(fèi)更多的時(shí)間來(lái)分類(lèi).

SHDA+EdgeCluster方法比randomly+EdgeCluster方法執(zhí)行的時(shí)間長(zhǎng).SHDA+SCRN/wvRN方法在BlogCatalog和You Tube數(shù)據(jù)集上比randomly+SCRN/wvRN方法執(zhí)行的時(shí)間短，在DBLP數(shù)據(jù)集上兩者執(zhí)行的時(shí)間大致相當(dāng).所以SHDA算法能夠提升網(wǎng)絡(luò)環(huán)境下多標(biāo)簽分類(lèi)的性能，還能提升部分多標(biāo)簽分類(lèi)算法的運(yùn)行速度.

表5 YouTube數(shù)據(jù)集上各算法的運(yùn)行時(shí)間

表6 YouTube數(shù)據(jù)集上各算法的運(yùn)行時(shí)間

表7 BlogCatalog數(shù)據(jù)集上各算法的運(yùn)行時(shí)間

表8 DBLP數(shù)據(jù)集上各算法的運(yùn)行時(shí)間

6 總結(jié)

在網(wǎng)絡(luò)環(huán)境下的多標(biāo)簽分類(lèi)中，給定訓(xùn)練集的節(jié)點(diǎn)數(shù)目，如果選擇的訓(xùn)練集不同，分類(lèi)精度也會(huì)不同.我們提出了SHDA算法，利用網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)來(lái)選擇種子節(jié)點(diǎn)，首先根據(jù)網(wǎng)絡(luò)中每個(gè)社團(tuán)的大小，按比例的選取每個(gè)社團(tuán)中度數(shù)較高的節(jié)點(diǎn)，然后將這些節(jié)點(diǎn)合并，處理后得到種子節(jié)點(diǎn)，將種子節(jié)點(diǎn)用作訓(xùn)練集進(jìn)行多標(biāo)簽分類(lèi).實(shí)驗(yàn)證明，相比于從網(wǎng)絡(luò)中隨機(jī)選取節(jié)點(diǎn)作為訓(xùn)練集，這種方法不僅有助于提高多標(biāo)簽分類(lèi)的性能，還能改善部分多標(biāo)簽分類(lèi)算法的運(yùn)行速率.

SHDA算法是從種子節(jié)點(diǎn)選擇的方面來(lái)提高多標(biāo)簽分類(lèi)的性能，我們今后的研究方向?qū)母纳贫鄻?biāo)簽分類(lèi)算法這方面，研究提高多標(biāo)簽分類(lèi)性能的更有效的方法.

[1]Yang S，Jiang Y.Zhou Z.Multi-label learning with weak label[A].Proceedings of the Twenty-Fourth AAAI Conference on Artificial Intelligence[C].Atlanta:AAAI,2010.593-598.

[2]Tang L,Liu H.Scalable learning of collective behavior based on sparse social dimensions[A].Proceedings of the 18th ACM Conference on Information and Knowledge Management[C].Hong Kong:ACM,2009.1107-1116.

[3]Macskassy S A,Provost F.A simple relational classifier[A].Proceedings of the Multi-relational Data Mining Workshop at the Ninth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining[C].Washington:ACM,2003.64-76.

[4]Lu Q,Getoor L.Link-based classification[A].Proceedings of the Twentieth International Conference on Machine Learning[C].Washington:JMLR,2003.496-503.

[5]Neville J,Jensen D.Relational dependency networks[J].Journal of Machine Learning Research,2007,8:653-692.

[6]Jensen D,Neville J,Gallagher B.Why collective inference improves relational classification[A].Proceedings of the tenth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining[C].Seattle:ACM,2004.593-598.

[7]鄭偉，王朝坤，劉璋，王建民.一種基于隨機(jī)游走模型的多標(biāo)簽分類(lèi)算法[J].計(jì)算機(jī)學(xué)報(bào)，2010,33(8):1418-1426.

Zheng Wei,Wang Chao-kun,Liu Zhang,Wang Jian-min.A multi-label classification algorithm based on random walk model[J].Chinese Journal of Computers,2010,33(8):1418-1426.(in Chinese)

[8]Ji M,Han J,Danilevsky M.Ranking-based classification of heterogeneous information networks[A].Proceedings of the 17th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining[C].San Diego:ACM,2011.1298-1306.

[9]Kong X,Cao B,Yu P S.Multi-label classification by mining label and instances correlations from heterogeneous information networks[A].Proceedings of the 19th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining[C].Chicago:ACM,2013.614-622.

[10]Wang X,Sukthankar G.Multi-label relational neighbor classification using social context features[A].Proceedings of the 15th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining[C].Chicago:ACM,2013.464-472.

[11]Zhou Y,Liu L.Activity-edge centric multi-label classification for mining heterogeneous information networks[A].Proceedings of the 20th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining[C].New York:ACM,2014.1276-1285.

[12]Qian T,Liu J.Influence maximization through identifying seed nodes from implicit social networks[A].Proceedings of the 4th International Conference on Ubiquitous Information Management and Communication[C].Suwon:ACM,2010.193-196.

[13]Jankowski J,Michalski R,Kazienko P.Compensatory seeding in networks with varying availability of nodes[A].Proceedings of the 2013 IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining[C].Niagara:ACM,2013.42-1249.

[14]Tang L,Liu H.Relational learning via latent social dimensions[A].Proceedings of the 15th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining[C].Paris:ACM,2009.817-825.

[15]Neville J,Gallagher B,et al.Correcting evaluation bias of relational classifiers with network cross validation[J].Knowledge and Information Systems,2012,30(1):32-52.

吳信東 男，1963年出生于安徽樅陽(yáng)，教授，博士生導(dǎo)師，IEEE Fellow，AAAS Fellow，主要研究方向?yàn)閿?shù)據(jù)挖掘，大數(shù)據(jù)分析，基于知識(shí)的系統(tǒng)和萬(wàn)維網(wǎng)信息探索.

E-mail:xwu@hfut.edu.cn

趙銀鳳 女，1990年出生于安徽淮北，碩士研究生，主要研究方向?yàn)閿?shù)據(jù)挖掘，社交網(wǎng)絡(luò).

E-mail:zhyinfeng@163.com

李 磊 男，1981年出生于遼寧鞍山，副教授，主要研究社會(huì)計(jì)算，數(shù)據(jù)挖掘和信任計(jì)算.

E-mail:lilei@hfut.edu.cn

Multi-label Classification in Network Environments via Seed Node Selection

WU Xin-dong1,2,ZHAO Yin-feng1,LI Lei1

(1.SchoolofComputerScienceandInformationEngineering,HefeiUniversityofTechnology,Hefei,Anhui230009,China；2.DepartmentofComputerScience,UniversityofVermont,BurlingtonVT05405,USA)

Multi-label classification is widely used in genetic classification,drug discovery and text classification.The existing multi-label classification algorithms usually select nodes randomly from the network as their training set.However,during multi-label classification,different nodes have different effects.Given the number of nodes in the training set,a different training sub-set can lead to different classification accuracy.Hence,we introduce the concept of seed nodes， the classification procedure starts from the seed nodes,and after continuous reasoning,the labels of other nodes are inferred in the network.We propose an SHDA algorithm (Nodes Selection of High Degree from Each Affiliation) in which the nodes of high degrees from each affiliation belonging to the network are selected and merged,and after processing,the seed nodes are obtained.Experiments on several real-world datasets demonstrate that taking seed nodes as the training set to classify multi-labeled data can improve the classification performance.

multi-label classification;network;seed nodes

2015-01-30;

2015-05-18;責(zé)任編輯：覃懷銀

國(guó)家重點(diǎn)基礎(chǔ)研究發(fā)展規(guī)劃(973計(jì)劃)項(xiàng)目(No.2013CB329604);教育部創(chuàng)新團(tuán)隊(duì)(No.IRT13059);國(guó)家自然科學(xué)基金項(xiàng)目(No.61229301，No.61503114)

TP181；TP391

A

0372-2112 (2016)09-2074-07

??學(xué)報(bào)URL:http://www.ejournal.org.cn

10.3969/j.issn.0372-2112.2016.09.008