王 浩，張 贊，李 磊，汪 萌

(合肥工業(yè)大學(xué)計算機與信息學(xué)院，安徽合肥 230009)

?

一種基于多階鄰居的網(wǎng)絡(luò)環(huán)境下多標簽分類算法

王 浩，張 贊，李 磊，汪 萌

(合肥工業(yè)大學(xué)計算機與信息學(xué)院，安徽合肥 230009)

隨著標簽分類應(yīng)用的增長，社交網(wǎng)絡(luò)環(huán)境下多標簽分類已成為一個重要的數(shù)據(jù)挖掘研究領(lǐng)域.關(guān)系分類模型基于一階鄰居做標簽分類，其性能優(yōu)于傳統(tǒng)的多標簽分類器.但現(xiàn)有的關(guān)系分類模型也存在問題：第一，僅利用一階鄰居做分類，未能充分使用鄰居信息.第二，網(wǎng)絡(luò)數(shù)據(jù)通常包含大量不連通的孤立部分，其標簽無法利用現(xiàn)有的關(guān)系分類模型分類.考慮基于共引規(guī)則為非孤立節(jié)點挖掘二階鄰居和基于節(jié)點特征向量相似度為孤立節(jié)點挖掘高階鄰居，本文提出一種新的基于多階鄰居的網(wǎng)絡(luò)數(shù)據(jù)多標簽分類算法，稱為MORN算法.在多個真實數(shù)據(jù)集上將MORN與現(xiàn)有的關(guān)系分類模型作對比，實驗表明，MORN算法能夠?qū)W習(xí)到更多節(jié)點的標簽且精度優(yōu)于傳統(tǒng)關(guān)系分類方法.

社交網(wǎng)絡(luò)；關(guān)系學(xué)習(xí)；多標簽分類

1 引言

近年來，隨著社交網(wǎng)絡(luò)(social networks)的發(fā)展和相關(guān)領(lǐng)域應(yīng)用的不斷深入，網(wǎng)絡(luò)數(shù)據(jù)分類(networked data classification)已成為數(shù)據(jù)挖掘(data mining)的一個重要研究方向.區(qū)別于傳統(tǒng)數(shù)據(jù)，網(wǎng)絡(luò)數(shù)據(jù)包含相互聯(lián)系的實體，不遵循實例獨立性假設(shè).實例和實例之間可以被多種多樣的方式連接到一起.本文研究基于網(wǎng)絡(luò)數(shù)據(jù)的多標簽分類問題.

傳統(tǒng)的關(guān)系分類模型[1]基于社交網(wǎng)絡(luò)同質(zhì)性及一階馬爾科夫假設(shè)，通過群體分類(collective classification)[2]，可以分類網(wǎng)絡(luò)數(shù)據(jù)的標簽.其基本假設(shè)是：一個節(jié)點的標簽依賴于網(wǎng)絡(luò)中與它直接相連的鄰居的標簽[3].因此關(guān)系分類模型處理網(wǎng)絡(luò)數(shù)據(jù)優(yōu)于傳統(tǒng)標簽分類模型[4～6].但傳統(tǒng)關(guān)系分類模型也存在兩個問題:

(1)傳統(tǒng)關(guān)系分類模型僅依賴與待分類節(jié)點直接相連的鄰居節(jié)點，往往因為鄰居中訓(xùn)練節(jié)點占比較少，影響分類精度.

(2)關(guān)系網(wǎng)絡(luò)通常包含大量的孤立部分.其節(jié)點的標簽無法利用現(xiàn)有的關(guān)系分類模型分類[7].

2 相關(guān)工作

2.1 傳統(tǒng)多標簽分類方法

解決傳統(tǒng)多標簽分類問題，通常基于兩大類方法：第一類是將多標簽分類問題拆解成多個單標簽分類問題，例如Hullermeier等[8]提出的基于標簽對比的方法.第二類是將單標簽分類方法轉(zhuǎn)化為多標簽分類方法.Zhang等[9]提出的MLKNN算法就屬此類.鄭等[10]將隨機游走模型引入多標簽學(xué)習(xí)，提出了基于隨機游走模型的多標簽分類方法.

傳統(tǒng)的多標簽分類算法處理網(wǎng)絡(luò)數(shù)據(jù)存在問題：第一，數(shù)據(jù)不滿足獨立同分布的假設(shè)；第二，無法有效利用實例之間連接關(guān)系；第三，通常需要使用實例的特征向量作為算法輸入.綜上三點，傳統(tǒng)多標簽分類方法不適合網(wǎng)絡(luò)環(huán)境多標簽分類.

2.2 網(wǎng)絡(luò)數(shù)據(jù)多標簽分類方法

Tang[11]等提出了基于社會特征提取的EdgeCluster算法，以解決當(dāng)網(wǎng)絡(luò)數(shù)據(jù)缺少特征向量時，難以使用傳統(tǒng)多標簽分類方法的問題.該算法的整體架構(gòu)屬于傳統(tǒng)多標簽分類方法.

關(guān)系分類模型基于網(wǎng)絡(luò)中的連接，充分發(fā)掘?qū)嵗g和標簽之間的依賴關(guān)系，再通過群體分類，估計所有未知標簽節(jié)點的標簽，經(jīng)過重復(fù)迭代，最終獲得一個穩(wěn)定狀態(tài)以最小化鄰居節(jié)點間標簽的不一致[12].關(guān)系分類模型代表算法有wvRN[13]和SCRN[3].

3 MORN算法

3.1 二階鄰居發(fā)現(xiàn)

共引性(citation regularity)是社會科學(xué)研究的重要現(xiàn)象[ 14,15],相似的實體傾向于連接到相同的事物.基于共引性，如果兩個節(jié)點有較多的共同鄰居，我們認為這兩個節(jié)點存在相似性.在多標簽分類計算中，我們引入了二階鄰居.

發(fā)掘二階鄰居的方法是：

(3)設(shè)定閾值T，當(dāng)Numui-vi≥T時，我們認為ui是vi的二階鄰居.

下面我們用DBLP數(shù)據(jù)集中一個例子來說明引入二階鄰居的必要性，該數(shù)據(jù)集的詳細介紹在4.1節(jié).以圖1為例，假設(shè)7344號節(jié)點是待分類節(jié)點.這5個節(jié)點的實際標簽在表1中.

表1 7344號、2926號、3440號、7342和7775號節(jié)點的實際標簽

接下來，我們給出wvRN算法的模型：

wvRN統(tǒng)計鄰居節(jié)點具有標簽λ的平均值P(Yi=λ|vi)作為節(jié)點vi具有標簽λ的概率：

(1)

7344號節(jié)點的一階鄰居的權(quán)重都為1.根據(jù)式(1)，7344號節(jié)點具有各標簽的概率為：

wvRN默認已知7344號標簽數(shù)目為2.依據(jù)各標簽概率(在概率相等情況下，wvRN算法默認按標簽順序)，7344號節(jié)點的標簽分類結(jié)果是：Y7344={λ9,λ13}，與實際情況不相符.

我們?yōu)?344號節(jié)點發(fā)掘到二階鄰居即7343號節(jié)點.其實際標簽是Y7343={λ13,λ14}.

此時為7344號節(jié)點和7343號節(jié)點建立新連接(圖中虛線).使用wvRN算法，7344號節(jié)點具有各標簽的概率為：

此時，7344號節(jié)點的標簽分類結(jié)果是：Y7344={λ13,λ14}，與實際情況相符.此例說明引入二階鄰居可以更充分地利用鄰居信息以利分類.

3.2 高階鄰居發(fā)現(xiàn)

基于社會特征相似度，從已知標簽節(jié)點集中尋找與孤立節(jié)點相似的節(jié)點集，該集合中的節(jié)點即為該孤立節(jié)點的高階鄰居節(jié)點.相似度越大，說明孤立節(jié)點與該高階鄰居的標簽集相似度越高，會被分配越高的權(quán)重.

挖掘高階鄰居的具體步驟如下：

(1)依據(jù)已知標簽節(jié)點集的分布，識別出孤立節(jié)點集合Visolated，具體使用的工具在4.3節(jié)介紹.

(2)刪除孤立節(jié)點vi∈Visolated與各一階鄰居的邊，因為vi的一階鄰居都是孤立節(jié)點，對標簽分類不起作用.

(3)我們用Tang等提出的邊聚類算法[11]提取所有節(jié)點的社會特征向量SF(Social Features).該算法在網(wǎng)絡(luò)結(jié)構(gòu)上使用聚類刻畫節(jié)點的特征向量，可以在無連接的情況下使度量節(jié)點間的關(guān)系成為可能.

(4)計算孤立節(jié)點vi與每一個已知標簽節(jié)點vj∈Vm的社會特征向量的相似度Sim(SFvi,SFvj).

(5)我們選取與目標節(jié)點vi相似度數(shù)值大于0的已知標簽的節(jié)點作為vi的高階鄰居.

(6)在網(wǎng)絡(luò)G中，為每個目標節(jié)點vi與其高階鄰居建立新的邊連接，邊的權(quán)重為歸一化后的相似度值.

下面我們舉例說明高階鄰居挖掘.如圖2所示，圖中左半部分顯示網(wǎng)絡(luò)G由左右兩個子網(wǎng)絡(luò)G1和G2構(gòu)成.假設(shè)已知標簽節(jié)點集Vm=(v3440,v7342,v7344).我們想預(yù)測G2中包含的節(jié)點的標簽.因G2中不含已知標簽節(jié)點，我們得出G2是孤立部分，在圖2中以灰色點表示.

在確認v1848是孤立節(jié)點后，刪除它與v1849的連接.計算v1848與Vm中每一個節(jié)點的社會特征向量相似度.選取相似度大于0的節(jié)點作為v1848的高階鄰居.假設(shè)發(fā)掘到的v1848的高階鄰居是v7342和v7344.我們分別為節(jié)點對(v1848,v7342)和(v1848,v7344)建立連接邊.孤立節(jié)點v1849和v8647發(fā)掘高階鄰居的過程與v1848的發(fā)掘過程一致.

綜合二階鄰居發(fā)現(xiàn)方法和高階鄰居發(fā)現(xiàn)方法，重新構(gòu)建網(wǎng)絡(luò)結(jié)構(gòu)和鄰居關(guān)系，調(diào)用SCRN算法作為基礎(chǔ)分類器給出MORN算法，如下所示.

算法1 基于多階鄰居的多標簽分類算法MORN

輸入：網(wǎng)絡(luò)G，標簽集Y，訓(xùn)練集Vm，測試集Vtest，最大迭代次數(shù)Max-Iter

輸出：Vtest中所有節(jié)點的標簽

1. 使用文獻[6]中的方法為G中每一個節(jié)點提取社會特征向量SF(vi)

2. 基于Vm的分布，計算得到孤立節(jié)點集合Visolated

3. for eachvi∈Vtestdo

4. ifvi?Visolated

5. 發(fā)掘vi的二階鄰居 //3.1節(jié)

6. ifvi∈Visolated

7. 發(fā)掘vi的高階鄰居 //3.2節(jié)

8. 跟據(jù)上述3～7步，重新構(gòu)建網(wǎng)絡(luò)，得到G′

9. while iterations≤Max-Iterand predictions have not converged to stable values

10. 基于G′，調(diào)用SCRN算法作為底層分類器

11. endwhile

12. 得到Vu中節(jié)點的標簽，從中提取出Vtest中節(jié)點的標簽，即為測試集節(jié)點分類結(jié)果

4 實驗

4.1 數(shù)據(jù)集

本文采用的DBLP數(shù)據(jù)集[3]，提取自DBLP網(wǎng)站.IMDb數(shù)據(jù)集[3]提取自在線視頻數(shù)據(jù)庫IMDb，我們從中選取了10000個節(jié)點.DBLP數(shù)據(jù)集和IMDb數(shù)據(jù)集統(tǒng)計信息如表2所示.

表2 數(shù)據(jù)集統(tǒng)計信息

4.2 度量標準

本文使用2個經(jīng)典的標簽分類度量標準Macro-F1值和Micro-F1值[3,8,16]度量分類精度.

本文在度量各算法分類精度的基礎(chǔ)上，提出預(yù)測比例PR(Prediction Ratio)指標來度量最終測試集內(nèi)有多少比例的節(jié)點獲得了分類標簽.

(2)

4.3 實驗結(jié)果與分析

我們基于Matlab實現(xiàn)MORN算法.采用的對比算法是SCRN、wvRN和EdgeCluster.

本文使用邊聚類方法提取節(jié)點的社會特征向量.我們采用GHI[3]來計算特征向量相似度.我們基于Matlab BGL工具包識別孤立節(jié)點.依據(jù)文獻[3]和文獻[11]，DBLP數(shù)據(jù)集的社會特征向量維度設(shè)置為1000，IMDb數(shù)據(jù)集的社會特征向量維度設(shè)置為10000，其它均采用默認參數(shù).

對比實驗使用網(wǎng)絡(luò)交叉驗證(Network Cross-Validation,NCV)[16]對結(jié)果進行驗證，以減小測試集的重疊.

4.3.1 二階鄰居發(fā)現(xiàn)中閾值T對實驗結(jié)果的影響

在DBLP上做實驗，比較T取不同值，Micro-F1的變化.訓(xùn)練集規(guī)模設(shè)定為10%，實驗結(jié)果如圖3所示.通過實驗發(fā)現(xiàn)，T值取1時，Micro-F1值最大，為57.02%.當(dāng)T值增大到2，Micro-F1值降低到56.59%，降幅非常明顯.隨著T值進一步擴大，Micro-F1值變化極小.因此，在后續(xù)實驗中，我們設(shè)定T值為1.

4.3.2 MORN算法和SCRN算法運算時間對比分析

我們對比兩個算法在標簽預(yù)測上開銷的時間.MORN算法和SCRN算法在標簽預(yù)測階段，迭代次數(shù)Max_Iter都設(shè)為10.由表3的實驗結(jié)果可知，雖然MORN需要挖掘新的鄰居，運算時間多于SCRN，但在可接受范圍之內(nèi).

表3 MORN算法和SCRN算法在DBLP數(shù)據(jù)集上的運算時間

4.3.3 標簽分類結(jié)果與分析

從表4和表5可知，MORN、SCRN和wvRN的精度高于EdgeCluster.MORN在DBLP上的精度高于SCRN和wvRN.在IMDb上，MORN的精度高于wvRN，但在訓(xùn)練集占1%—2%時，MORN的精度低于SCRN.原因是訓(xùn)練集過少，發(fā)掘到的二階鄰居和多階鄰居數(shù)量都非常少.隨著訓(xùn)練集增大到3%以上，MORN在IMDb上精度好于SCRN和wvRN.對比實驗說明MORN的精度比SCRN和wvRN更高.

表4 各算法在DBLP數(shù)據(jù)集上的分類精度

表5 各算法在IMDb數(shù)據(jù)集上的分類精度

從表6和表7可知，MORN在PR值上好于SCRN和wvRN，在DBLP上領(lǐng)先13%-15%；在IMDb上領(lǐng)先8%-15%.實驗結(jié)果說明，MORN可以有效地學(xué)習(xí)到孤立節(jié)點的標簽.隨著訓(xùn)練集規(guī)模擴大，MORN在PR值上接近100%，但沒有達到100%.原因是少數(shù)孤立節(jié)點與所有的訓(xùn)練集節(jié)點的特征向量相似度都為0，無法為其找到相似的節(jié)點.

表6 關(guān)系分類方法在DBLP數(shù)據(jù)集上的預(yù)測比例

表7 關(guān)系分類方法在IMDb數(shù)據(jù)集上的預(yù)測比例

5 結(jié)論

本文分析了現(xiàn)有關(guān)系分類模型在處理網(wǎng)絡(luò)環(huán)境下多標簽分類存在的問題.針對現(xiàn)有關(guān)系分類模型僅利用一階鄰居做分類并且無法學(xué)習(xí)孤立節(jié)點標簽的不足，提出了一種基于多階鄰居的網(wǎng)絡(luò)數(shù)據(jù)多標簽分類MORN算法.理論分析和實驗都證明了MORN算法能夠有效解決網(wǎng)絡(luò)環(huán)境下多標簽分類問題.

[1]S Macskassy,F Provost.A simple relational classifier[A].Proceedings of the Second Workshop on Multi-Relational Data Mining at ACM SIGKDD[C].Washington DC,USA:ACM,2003.64-76.

[2]P SEN,G Namata,M Bilgic,L Getoor,B Gallagher,T Eliassi-Rad.Collective classification in network data[J].AI Magazine,2008,29(3):93-106.

[3]X Wang,G Sukthankar.Multi-label relational neighbor classification using social context features[A].Proceedings of the ACM SIGKDD[C].Chicago,USA:ACM,2013.464-472.

[4]J Neville,D Jensen,L Friedland,M Hay.Learning relational probability trees[A].Proceedings of the ACM SIGKDD[C].Washington DC,USA:ACM,2003.625-630.

[5]B Taskar,P Abbeel,D Koller.Discriminative probabilistic models for relational data[A].Proceedings of the UAI[C].Edmonton,Canada:Morgan Kaufmann,2002.485-492.

[6]M Zhang,K Zhang.Multi-label learning by exploiting label dependency[A].Proceedings of the ACM SIGKDD[C].Washington DC,USA:ACM,2010.999-1007.

[7]C Aggarwal.Social Network Data Analytics[M].Berlin:Springer,2011.115-148.

[8]E Hullermeier,J Furnkranz,W Cheng,K Brinker .Label ranking by learning pairwise preferences[J].Artificial Intelligence,2008,172(16):1897-1916.

[9]M Zhang,Z Zhou.A k-nearest neighbor based algorithm for multi-label classification[A].Proceedings of the IEEE International Conference on Granular Computing[C].Beijing,China:IEEE,2005.718-721.

[10]鄭偉,王朝坤,劉璋,王建民.一種基于隨機游走模型的多標簽分類算法[J].計算機學(xué)報,2010,33(8):1418-1426.

W Zheng,C Wang ,Z Liu,J Wang.A multi-label classification algorithm based on random walk model[J].Chinese Journal of Computers,2010,33(8):1418-1426.(in Chinese)

[11]L Tang,H Liu.Scalable learning of collective behavior based on sparse social dimensions[A].Proceedings of the ACM CIKM[C].Hong Kong,China:ACM,2009.1107-1116.

[12]J Neville,D Jensen.Iterative classification in relational data[A].Proceedings of the AAAI Workshop on Learning Statistical Models from Relational Data[C].Austin,USA:AAAI,2000.42-49.

[13]S Macskassy,F Provost.Classification in networked data:a toolkit and a univariate case study[J].Journal of Machine Learning,2007,8(5):935-983.

[14]M Newman.Networks:An Introduction[M].Oxford:Oxford University Press,2010.

[15]M McPherson,L Smith-lovin,J Cook.Birds of a feather:Homophily in social networks[J].Annual Review of Sociology,2001,27(1):415-444.

[16]J Neville,B Gallagher,T Eliassi-Rad,T Wang,Correcting evaluation bias of relational classifiers with network cross validation[J].Knowledge and Information Systems,2012,30(1):31-55.

王 浩 男，1962年生，江蘇泰州人.合肥工業(yè)大學(xué)計算機與信息學(xué)院教授，博士生導(dǎo)師.1984年于上海交通大學(xué)獲工學(xué)學(xué)士學(xué)位，1989年和1997年于合肥工業(yè)大學(xué)獲工學(xué)碩士和工學(xué)博士學(xué)位.主要研究方向為智能計算理論與軟件、分布式智能系統(tǒng)、復(fù)雜系統(tǒng)理論與建模等.

張 贊 男，1987年生，安徽馬鞍山人.2009年于東北電力大學(xué)獲管理學(xué)學(xué)士學(xué)位，2013年于合肥工業(yè)大學(xué)獲工學(xué)碩士學(xué)位.現(xiàn)為合肥工業(yè)大學(xué)博士研究生.主要研究方向為社交網(wǎng)絡(luò)行為的預(yù)測和分類研究.

E-mail:zhangzan99@163.com

A Multi-Order Neighbor Based Multi-Label Classification Algorithm in Network Environments

WANG Hao,ZHANG Zan,LI Lei,WANG Meng

(SchoolofComputerandInformation,HefeiUniversityofTechnology,Hefei,Anhui230009,China)

Multi-label classification in network environments is becoming a key area of data mining research as its applications are increasing dramatically.Relational classification models,which predict class labels of linked neighbors according to the ones of the given nodes,have been shown to outperform traditional multi-label classifiers.However,existing relational classification models neither make full use of neighbor information,nor predict the isolated nodes’ labels,which are popularly existing in relational networks.In this paper,we present a multi-label relational classifier (MORN) that mines both second-order neighbors for non-isolated nodes and high-order neighbors for isolated nodes.MORN has been conducted on real datasets and it demonstrates that our proposed classifier outperforms existing relational classification models.

social networks;relational learning;multi-label classification

2015-01-31;

2015-07-31;責(zé)任編輯：李勇鋒

國家973重點基礎(chǔ)研究發(fā)展計劃(No.2013CB329604);國家自然科學(xué)基金(No.61070131，No.61175051);安徽省自然科學(xué)基金(No.1408085QF130);中央高?；究蒲袠I(yè)務(wù)費專項(No.2015HGCH0012)

TP311

A

0372-2112 (2016)10-2330-05

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

10.3969/j.issn.0372-2112.2016.10.007