基于非負(fù)矩陣分解的大規(guī)模異構(gòu)數(shù)據(jù)聯(lián)合聚類

申國偉 楊 武 王 巍 于 淼 董國忠

（哈爾濱工程大學(xué)信息安全研究中心 哈爾濱 150001）（shenguowei＠hrbeu．edu．cn）

基于非負(fù)矩陣分解的大規(guī)模異構(gòu)數(shù)據(jù)聯(lián)合聚類

申國偉 楊 武 王 巍 于 淼 董國忠

（哈爾濱工程大學(xué)信息安全研究中心 哈爾濱 150001）（shenguowei＠hrbeu．edu．cn）

異構(gòu)信息網(wǎng)絡(luò)中包含多類實(shí)體和關(guān)系．隨著數(shù)據(jù)規(guī)模增大時(shí)，不同類實(shí)體規(guī)模增長不平衡，異構(gòu)關(guān)系數(shù)據(jù)也變得異常稀疏，導(dǎo)致聚類算法的時(shí)間復(fù)雜度高、準(zhǔn)確率低．針對上述問題，提出了一種基于關(guān)聯(lián)矩陣分解的2階段聯(lián)合聚類算法FNMTF－CM．第1階段，抽取規(guī)模較小的一類實(shí)體中的關(guān)聯(lián)關(guān)系構(gòu)建關(guān)聯(lián)矩陣，通過對稱非負(fù)矩陣分解得到劃分指示矩陣．與原始關(guān)系矩陣相比，關(guān)聯(lián)矩陣的稠密度更高，規(guī)模更小．第2階段，將劃分指示矩陣作為關(guān)系矩陣三分解的輸入，進(jìn)而快速求解另一類實(shí)體的劃分指示矩陣．在標(biāo)準(zhǔn)測試數(shù)據(jù)集和異構(gòu)關(guān)系數(shù)據(jù)集上的實(shí)驗(yàn)表明，算法準(zhǔn)確率和性能整體優(yōu)于傳統(tǒng)的基于非負(fù)矩陣分解的聯(lián)合聚類算法．

隨著微博、社交網(wǎng)絡(luò)等異構(gòu)信息網(wǎng)絡(luò)的興起，異構(gòu)信息挖掘已經(jīng)成為當(dāng)前數(shù)據(jù)挖掘領(lǐng)域中的一個(gè)研究熱點(diǎn)．異構(gòu)網(wǎng)絡(luò)中包含多類實(shí)體，實(shí)體之間存在著復(fù)雜的交互關(guān)系．例如微博中包含用戶、消息、標(biāo)簽、詞等實(shí)體，用戶發(fā)布消息，消息由詞語組成，消息中還包含標(biāo)簽等．通過抽取實(shí)體間的關(guān)系數(shù)據(jù)進(jìn)行聚類分析，能夠挖掘出異構(gòu)網(wǎng)絡(luò)中不同實(shí)體間的潛在結(jié)構(gòu)關(guān)系．

聯(lián)合聚類能夠針對不同的實(shí)體同時(shí)進(jìn)行聚類分析［12］，因而應(yīng)用廣泛．傳統(tǒng)的聯(lián)合聚類算法包括基于信息理論的算法ITCC［3］、基于矩陣譜信息［4］和矩陣分解的方法．由于關(guān)系數(shù)據(jù)中一般都是非負(fù)元素，非負(fù)矩陣分解方法［5］成為目前最常用的方法．

傳統(tǒng)的非負(fù)矩陣分解僅僅處理同類節(jié)點(diǎn)之間的同質(zhì)關(guān)系聚類問題，Long等人［6］首次在二元關(guān)系矩陣上運(yùn)用塊值分解法實(shí)現(xiàn)矩陣分解．在此基礎(chǔ)上，提出了一系列改進(jìn)的非負(fù)矩陣分解方法實(shí)現(xiàn)聯(lián)合聚類［7－9］．采用半監(jiān)督的非負(fù)矩陣分解方法實(shí)現(xiàn)聯(lián)合聚類［1012］，算法SS－NMF［12］中融合肯定鏈接或否定鏈接等約束信息提高聯(lián)合聚類算法的準(zhǔn)確度，但是真實(shí)數(shù)據(jù)中通常很難獲取約束先驗(yàn)知識．

在處理關(guān)系數(shù)據(jù)時(shí)，Wang等人［13］提出了快速的非負(fù)矩陣三分解方法FNMTF實(shí)現(xiàn)快速的矩陣分解，進(jìn)而實(shí)現(xiàn)聯(lián)合聚類．非負(fù)矩陣分解在聯(lián)合聚類算法取得了很好的效果［14］，但是數(shù)據(jù)本身的幾何結(jié)構(gòu)會影響聚類的準(zhǔn)確性［15－16］．當(dāng)待分析的異構(gòu)數(shù)據(jù)規(guī)模增大時(shí)，關(guān)系數(shù)據(jù)結(jié)構(gòu)呈現(xiàn)明顯變化．主要存在以下問題：

1）非平衡問題．待分析的異構(gòu)數(shù)據(jù)規(guī)模增大時(shí)，異構(gòu)數(shù)據(jù)中不同類實(shí)體的規(guī)模并不呈現(xiàn)統(tǒng)一的增長模式．例如微博消息數(shù)量呈線性增長時(shí)，用戶、詞和標(biāo)簽等實(shí)體并不呈現(xiàn)線性增長模式．傳統(tǒng)的非負(fù)矩陣分解方法的時(shí)間復(fù)雜度都與矩陣的行和列規(guī)模相關(guān)，因此處理大規(guī)模異構(gòu)數(shù)據(jù)時(shí)計(jì)算時(shí)間復(fù)雜度較高．

2）稀疏性問題．真實(shí)異構(gòu)網(wǎng)絡(luò)中的關(guān)系數(shù)據(jù)比較稀疏，隨著待分析異構(gòu)數(shù)據(jù)規(guī)模進(jìn)一步增大，關(guān)系數(shù)據(jù)變得異常稀疏．例如微博中的消息內(nèi)容最多包含140個(gè)字，構(gòu)建的消息和詞之間的關(guān)系矩陣非常稀疏．當(dāng)消息規(guī)模進(jìn)一步增大時(shí)，由于中文常用詞的數(shù)量是一定的，因此消息和詞之間的關(guān)系矩陣變得異常稀疏，消息和用戶、標(biāo)簽的關(guān)系矩陣同樣如此．傳統(tǒng)的非負(fù)矩陣分解方法針對異常稀疏的關(guān)系矩陣進(jìn)行分解時(shí)得到的聚類效果并不理想．

本文針對大規(guī)模異構(gòu)數(shù)據(jù)分析時(shí)出現(xiàn)的非平衡和稀疏性2個(gè)問題進(jìn)行解決．針對非平衡增長問題，在非負(fù)矩陣分解時(shí)提出了2階段分解方法．首先，僅對關(guān)系矩陣中的規(guī)模較小的一類實(shí)體進(jìn)行分析．異構(gòu)實(shí)體之間的關(guān)系矩陣非常稀疏，但是同一類實(shí)體之間的關(guān)聯(lián)性比較強(qiáng)［17］，通過同類實(shí)體之間的關(guān)聯(lián)關(guān)系構(gòu)造的關(guān)聯(lián)矩陣能夠明顯提高矩陣的稠密度．其次，以較小規(guī)模的實(shí)體聚類結(jié)果直接作為第2階段的輸入，在確保大規(guī)模實(shí)體聚類結(jié)果的同時(shí)提高了整體處理效率．

綜上所述，本文將針對大規(guī)模異構(gòu)關(guān)系數(shù)據(jù)提出一種基于關(guān)聯(lián)矩陣的2階段快速聯(lián)合聚類算法，同時(shí)解決非平衡問題和稀疏性問題．

1 問題定義

異構(gòu)關(guān)系數(shù)據(jù)中包括多類實(shí)體，目前的聯(lián)合聚類算法主要針對二階異構(gòu)關(guān)系進(jìn)行聯(lián)合聚類分析，因此，本文以2類實(shí)體之間的異構(gòu)關(guān)系為例敘述．二階異質(zhì)關(guān)系數(shù)據(jù)采用二部圖G＝（V，E，W）進(jìn)行建模，其中V＝X1∪X2，X1和X2為異構(gòu)關(guān)系中的2類實(shí)體，實(shí)體X1和X2的數(shù)量分別為m和n，E為異構(gòu)關(guān)系對應(yīng)的邊集合，W為邊的權(quán)重．進(jìn)一步可將二部圖G表示成m×n的異構(gòu)關(guān)系矩陣R，由于大規(guī)模數(shù)據(jù)中的非平衡問題，可假設(shè)mn．

傳統(tǒng)的聯(lián)合聚類算法中將X1和X2分別劃分到k1和k2類（通常k1＝k2），本文將針對X1和X2的聯(lián)合聚類問題轉(zhuǎn)換成針對關(guān)系矩陣R的行和列同時(shí)進(jìn)行劃分的問題．

2 2階段非負(fù)矩陣分解框架

針對大規(guī)模異構(gòu)關(guān)系數(shù)據(jù)中的非平衡問題和稀疏性問題，本文提出了一個(gè)2階段的非負(fù)矩陣分解框架，如圖1所示．

對關(guān)系矩陣R的行和列同時(shí)聚類可將關(guān)系矩陣R分解為F，S，B三個(gè)矩陣，如圖1（a）所示，其中矩陣F，B分別為2類目標(biāo)實(shí)體的聚類指示矩陣，S為聯(lián)合類之間相關(guān)矩陣．本文不直接針對關(guān)系矩陣R進(jìn)行分解，而是分2階段實(shí)現(xiàn)．

第1階段針對實(shí)體數(shù)較少的一類實(shí)體X2進(jìn)行處理，其數(shù)量為n．從關(guān)系矩陣R中抽取同類實(shí)體間的關(guān)聯(lián)關(guān)系，進(jìn)而構(gòu)建關(guān)聯(lián)矩陣C，矩陣C的規(guī)模為n×n．對矩陣C進(jìn)行對稱非負(fù)矩陣分解，得到指示矩陣B，如圖1（b）所示．由于采用同類實(shí)體的關(guān)聯(lián)關(guān)系，構(gòu)建的同質(zhì)關(guān)系矩陣C比原來的關(guān)系矩陣R要稠密，在某種程度上能夠避免非負(fù)矩陣分解中的稀疏性問題，進(jìn)而提高非負(fù)矩陣分解的準(zhǔn)確性．

在第2階段中，將關(guān)聯(lián)矩陣C分解得到的指示矩陣B直接作為關(guān)系矩陣R三分解的指示矩陣，如圖1（c）所示．在矩陣B已知的情況下，可以很容易計(jì)算指示矩陣F和矩陣S．由問題定義可知，矩陣C的規(guī)模小于原始關(guān)系矩陣R的規(guī)模m×n，因此該框架能夠處理大規(guī)模異構(gòu)關(guān)系數(shù)據(jù)．

Fig．1 The framework of heterogeneous data co－clustering．圖1 異構(gòu)數(shù)據(jù)聯(lián)合聚類框架

3 基于關(guān)聯(lián)矩陣的稀疏聯(lián)合聚類

根據(jù)2階段非負(fù)矩陣分解框架，在異構(gòu)關(guān)系矩陣的基礎(chǔ)上，聯(lián)合聚類主要包括關(guān)聯(lián)矩陣構(gòu)造、關(guān)聯(lián)矩陣分解、基于關(guān)聯(lián)矩陣的異構(gòu)關(guān)系矩陣三分解3部分．

3．1 關(guān)聯(lián)矩陣構(gòu)造

在異構(gòu)關(guān)系數(shù)據(jù)中，選擇規(guī)模較小的一類實(shí)體X2，通過異構(gòu)關(guān)系矩陣R構(gòu)造X2對應(yīng)的關(guān)聯(lián)矩陣C．文中利用關(guān)聯(lián)強(qiáng)度Wi，j度量實(shí)體X2中任意2個(gè)實(shí)體xi，xj的關(guān)聯(lián)關(guān)系，其可通過2個(gè)實(shí)體xi，xj基于X1中實(shí)體的同現(xiàn)概率進(jìn)行計(jì)算，其計(jì)算方法如式（1）所示：

式（2）和式（3）中，N（xi，xj）為X2中的實(shí)體xi，xj基于X1中實(shí)體同時(shí)出現(xiàn)次數(shù)．

3．2 關(guān)聯(lián)矩陣分解

通過關(guān)聯(lián)關(guān)系構(gòu)造的關(guān)聯(lián)矩陣C，采用對稱非負(fù)矩陣分解方法進(jìn)行分解，其對應(yīng)的目標(biāo)函數(shù)為式（4）所示：

針對目標(biāo)函數(shù)J1，可通過非負(fù)最小二乘法進(jìn)行計(jì)算，其計(jì)算公式如式（5）所示．基于關(guān)聯(lián)矩陣C的分解結(jié)果為聚類指示矩陣B．

由于聚類指示矩陣中每一個(gè)實(shí)體只屬于一個(gè)聚類標(biāo)簽，因此，對矩陣B進(jìn)行二元化，即B中每一行的最大值對應(yīng)的聚類結(jié)果為1，其余對應(yīng)的都為0．二元化后的矩陣B將作為關(guān)系矩陣R三分解的輸入．

3．3 基于關(guān)聯(lián)矩陣的異構(gòu)關(guān)系矩陣三分解

傳統(tǒng)的非負(fù)矩陣分解通常采用的目標(biāo)函數(shù)如式（6）所示，該目標(biāo)函數(shù)中采用兩因子分解法．

兩因子分解法得到的近似低秩矩陣效果較差，因此Ding等人［18］提出了正交非負(fù)矩陣三分解，其對應(yīng)的目標(biāo)函數(shù)為式（7）所示，在目標(biāo)函數(shù)中引入了矩陣S，使得分解得到的矩陣F，B具有實(shí)際意義．

由于正交約束條件在某些情況下過于嚴(yán)格，本文中將采用無正交約束的目標(biāo)函數(shù)，如式（8）所示：

對于目標(biāo)函數(shù)J4，現(xiàn)有的方法中常采用乘法更新的迭代求解方法實(shí)現(xiàn)，但是其收斂速度較慢．本文將采用快速的迭代求解方法實(shí)現(xiàn)，關(guān)聯(lián)矩陣C對稱分解得到的矩陣B經(jīng)過二元化后，直接作為目標(biāo)函數(shù)J4的輸入，因此，只需迭代求解矩陣F和S．

在優(yōu)化求解矩陣S的過程中，固定矩陣F，矩陣S的求解方法如式（9）所示：

在優(yōu)化求解矩陣F的過程中，固定矩陣S．由于矩陣F為關(guān)系矩陣R的行劃分指示矩陣，F(xiàn)中的每一行有且只有一個(gè)元素為1，其余為0，因此求解矩陣F的優(yōu)化問題可按照行進(jìn)行處理，其轉(zhuǎn)換為式（10）的優(yōu)化問題．

其中fj·為行聚類指示向量，在該向量中，有且只有一個(gè)元素為1，其余的元素都為0，因此，式（10）的優(yōu)化問題可通過式（11）進(jìn)行快速求解．

其中珘bk·為SBT對應(yīng)的第k個(gè)行向量．式（10）可通過向量范式枚舉法快速求解，避免了使用矩陣乘法迭代更新求解，提高了算法處理速度．

面向大規(guī)模異構(gòu)數(shù)據(jù)的聯(lián)合聚類算法的整個(gè)過程總結(jié)如算法1所示．在關(guān)聯(lián)矩陣C對稱分解的基礎(chǔ)上對關(guān)系矩陣R進(jìn)行非負(fù)矩陣三分解，能夠同時(shí)解決非平衡和稀疏性問題．算法1中第④～⑨步為異構(gòu)關(guān)系矩陣迭代求解過程．

算法1．異構(gòu)數(shù)據(jù)聯(lián)合聚類算法FNMTF－CM．

輸入：R為關(guān)系矩陣，聚類數(shù)目k，Niter為最大迭代次數(shù)，δ為收斂閾值；

輸出：F為實(shí)體X1聚類指示矩陣，B為實(shí)體X2聚類指示矩陣．

4 實(shí)驗(yàn)及分析

本文所有實(shí)驗(yàn)都在Matlab下實(shí)現(xiàn)，硬件平臺為曙光8core服務(wù)器、8GB內(nèi)存．

實(shí)驗(yàn)中將分別對比算法SS－NMF，F(xiàn)NMTF和本文算法FNMTF－CM．每一組實(shí)驗(yàn)分別運(yùn)行10次，采用隨機(jī)初始化，最終實(shí)驗(yàn)結(jié)果中給出平均值．

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

本文首先將在聯(lián)合聚類算法的標(biāo)準(zhǔn)測試數(shù)據(jù)集［19］①上對算法進(jìn)行全面的評估．該數(shù)據(jù)集給出了2類實(shí)體的聚類標(biāo)簽，不僅能夠針對算法的準(zhǔn)確率等指標(biāo)值進(jìn)行對比分析，還能對算法在不同聚類難度等級的數(shù)據(jù)集下進(jìn)行對比分析．

數(shù)據(jù)集中共計(jì)36組數(shù)據(jù)，通過貝葉斯錯(cuò)誤率Error作為數(shù)據(jù)集的難度控制參數(shù)，包括5%，12%，20%共3個(gè)難度等級，其中5%是最容易聚類的數(shù)據(jù)集，20%是最難聚類的數(shù)據(jù)集．每1個(gè)難度等級分別對應(yīng)50，100，200，500共4種規(guī)模（行和列的規(guī)模相同），可針對節(jié)點(diǎn)規(guī)模進(jìn)行聚類算法對比分析．每一類節(jié)點(diǎn)規(guī)模的數(shù)據(jù)集分別對應(yīng)3，5，10共3種聚類數(shù)目，可針對不同的聚類數(shù)進(jìn)行對比分析．

為了驗(yàn)證FNMTF－CM算法在真實(shí)數(shù)據(jù)集上的效果，將在4個(gè)真實(shí)的異構(gòu)關(guān)系數(shù)據(jù)集上進(jìn)行對比實(shí)驗(yàn)．其中Title數(shù)據(jù)為Sogou提供的新聞標(biāo)題數(shù)據(jù)集②，構(gòu)建新聞標(biāo)題和詞之間的異構(gòu)關(guān)系數(shù)據(jù)集．Weibo數(shù)據(jù)集收集了2012年“闖紅燈”、“豐田汽車回收”、“美國總統(tǒng)大選”、“莫言獲得諾貝爾獎”、“我是特種兵”、“杭州煙花大會”、“中國好聲音”7個(gè)話題對應(yīng)的新浪微博消息，經(jīng)過預(yù)處理后得到8 023條微博和374個(gè)標(biāo)簽，構(gòu)建消息和標(biāo)簽之間的異構(gòu)關(guān)系數(shù)據(jù)集．DBLP1為論文與詞之間的關(guān)系數(shù)據(jù)集，DBLP2為論文與作者之間的關(guān)系數(shù)據(jù)集［20］，這2個(gè)數(shù)據(jù)集中分別提取了論文題目和摘要字?jǐn)?shù)超過100個(gè)、作者出現(xiàn)多于2次對應(yīng)的關(guān)系數(shù)據(jù)．4個(gè)數(shù)據(jù)集的詳細(xì)信息如表1所示：

①https：??www．hds．utc．fr?coclustering?doku．php

②http：??www．sogou．com?labs?dl?tce．html

Table 1 Heterogeneous Relational Dataset表1 異構(gòu)關(guān)系數(shù)據(jù)集

4．2 評估指標(biāo)

聯(lián)合聚類算法的度量指標(biāo)較多，本文中將采用常見的Purity［21］，NMI［22］，ARI［23］3個(gè)指標(biāo)作為度量標(biāo)準(zhǔn)．對于給定的異構(gòu)數(shù)據(jù)集，其中實(shí)體規(guī)模為n，算法得到的聚類結(jié)果為C＝｛c1，c2，…，cK｝，給定的聚類標(biāo)簽為R＝｛r1，r2，…，rL｝，則3個(gè)評估指標(biāo)分別定義如式（12）、式（13）和式（14）．

NMI值在0到1之間，越接近1，則說明聚類結(jié)果越好．

ARI（C，R）＝

該ARI值越大，則聚類結(jié)果越好．

4．3 人工數(shù)據(jù)集實(shí)驗(yàn)

在同一規(guī)模的數(shù)據(jù)集下評估算法受不同聚類數(shù)目K的影響情況，對比結(jié)果如圖2所示．所有的算法隨著K值的增加，準(zhǔn)確率都有所下降，但其他2個(gè)指標(biāo)影響較小．因此，在實(shí)際使用的過程中，需要根據(jù)數(shù)據(jù)中的真實(shí)情況給定聚類數(shù)據(jù)K．

圖3中為在不同數(shù)據(jù)規(guī)模下的對比結(jié)果．隨著規(guī)模的增加，算法的準(zhǔn)確率等指標(biāo)都隨之下降．由于該數(shù)據(jù)集中2類實(shí)體的數(shù)目一致，無法發(fā)揮FNMTFCM算法的優(yōu)勢，其聚類結(jié)果接近于FNMTF算法．

Fig．2 The results of algorithms on the different clustering number K（N＝200，Error＝12%）．圖2 算法在不同聚類數(shù)K下的對比結(jié)果（N＝200，Error＝12%）

Fig．3 The results of algorithms on the different data scale N（K＝5，Error＝12%）．圖3 算法在不同節(jié)點(diǎn)規(guī)模N下的對比結(jié)果（K＝5，Error＝12%）

針對標(biāo)準(zhǔn)測試數(shù)據(jù)集中不同聚類難度等級的數(shù)據(jù)集進(jìn)行算法的魯棒性對比實(shí)驗(yàn)，結(jié)果如圖4所示．本文算法在處理不同聚類難度等級的數(shù)據(jù)集時(shí)的魯棒性都優(yōu)于其他2種算法，這主要是在FNMTFCM算法中降低了數(shù)據(jù)集本身結(jié)構(gòu)的影響．

4．4 對比實(shí)驗(yàn)

為了驗(yàn)證本文算法的效果，在真實(shí)的異構(gòu)稀疏數(shù)據(jù)集上進(jìn)行對比實(shí)驗(yàn)，在該實(shí)驗(yàn)中，設(shè)置的聚類數(shù)目如表1中所示．

在4個(gè)不同的數(shù)據(jù)集上對比的實(shí)驗(yàn)結(jié)果分別如表2至表5所示，表中對應(yīng)的最好結(jié)果分別加粗表示．

由實(shí)驗(yàn)結(jié)果可知，F(xiàn)NMTF－CM算法在4個(gè)數(shù)據(jù)集上的結(jié)果整體優(yōu)于其他2個(gè)算法．在Title和Weibo兩個(gè)數(shù)據(jù)集上，F(xiàn)NMTF－CM算法的純度、NMI值和ARI值比其他算法都高．這主要得益于本文算法中基于關(guān)聯(lián)矩陣進(jìn)行分解，提高了待分解矩陣的稠密度，進(jìn)而提高了整體算法的準(zhǔn)確率．

Fig．4 The results of algorithms on the different clustering difficulty（N＝200，K＝5）．圖4 算法在不同聚類難度下的對比結(jié)果（N＝200，K＝5）

Table 2 The Result on Title Dataset表2 Title數(shù)據(jù)集上的對比結(jié)果

Table 3 The Result on Weibo Dataset表3 Weibo數(shù)據(jù)集上的對比結(jié)果

Table 4 The Result on DBLP1Dataset表4 DBLP1數(shù)據(jù)集上的對比結(jié)果

Table 5 The Result on DBLP2Dataset表5 DBLP2數(shù)據(jù)集上的對比結(jié)果

在數(shù)據(jù)集DBLP1和DBLP2上，SS－NMF算法的NMI值比本文算法要高，特別是在數(shù)據(jù)集DBLP2上，SS－NMF算法的ARI值也高于本文算法．通過分析可知，DBLP2數(shù)據(jù)集異常稀疏，該數(shù)據(jù)集中可能包含較多的奇異點(diǎn)．因此，本文算法在處理奇異點(diǎn)問題上仍有待進(jìn)一步改進(jìn)．

進(jìn)一步分析FNMTF－CM算法在不同聚類數(shù)目K值下的效果．在Title數(shù)據(jù)集中，真實(shí)的聚類數(shù)目K＝9．該實(shí)驗(yàn)中通過調(diào)整K值，得到的實(shí)驗(yàn)結(jié)果如圖5所示．由實(shí)驗(yàn)結(jié)果可知，F(xiàn)NMTF－CM算法在不同的K值下，純度和NMI值較為穩(wěn)定，但是在真實(shí)的聚類數(shù)目下并不是最佳的結(jié)果．因此，在實(shí)際應(yīng)用中，需要根據(jù)數(shù)據(jù)選擇恰當(dāng)?shù)木垲悢?shù)目．

為了說明算法在處理大規(guī)模異構(gòu)關(guān)系數(shù)據(jù)時(shí)的處理速度，在Weibo數(shù)據(jù)集上對3個(gè)算法的運(yùn)行時(shí)間進(jìn)行對比，結(jié)果如圖6所示．

FNMTF－CM算法的運(yùn)行時(shí)間要小于其他2種算法，主要因?yàn)镕NMTF－CM算法中選擇規(guī)模較小的一類實(shí)體對應(yīng)的關(guān)聯(lián)矩陣進(jìn)行分解，并且求解異構(gòu)關(guān)系矩陣時(shí)無需采用乘法更新迭代求解．在微博關(guān)系數(shù)據(jù)中，標(biāo)簽數(shù)目比消息數(shù)目小很多，因此關(guān)聯(lián)矩陣的規(guī)模比原始異構(gòu)關(guān)系矩陣小、處理速度更快．由于SS－NMF算法采用乘法更新迭代求解，收斂較慢，其運(yùn)行時(shí)間最長．

Fig．5 The results of algorithms on different clustering number Kwhen running on Title．圖5 在Title數(shù)據(jù)集上不同聚類數(shù)目K的對比結(jié)果

Fig．6 The running time of algorithms on Weibo．圖6 算法在Weibo數(shù)據(jù)集上的時(shí)間對比

5 結(jié) 論

本文針對大規(guī)模異構(gòu)數(shù)據(jù)中的非平衡問題和稀疏性問題提出了一種基于非負(fù)矩陣分解的聯(lián)合聚類算法．將傳統(tǒng)的聯(lián)合聚類算法轉(zhuǎn)換成基于關(guān)聯(lián)矩陣的對稱分解和基于關(guān)系矩陣的三分解，進(jìn)而實(shí)現(xiàn)快速的異構(gòu)數(shù)據(jù)聯(lián)合聚類．實(shí)驗(yàn)結(jié)果表明本文提出的算法在標(biāo)準(zhǔn)測試數(shù)據(jù)集和真實(shí)異構(gòu)數(shù)據(jù)上的效果整體優(yōu)于其他的算法．

本文算法主要考慮了較小規(guī)模實(shí)體對聚類的促進(jìn)作用，下一步將考慮2類實(shí)體的相互促進(jìn)作用．此外，本文只考慮了二階異構(gòu)關(guān)系，下一步將推廣到高階異構(gòu)關(guān)系數(shù)據(jù)聯(lián)合聚類．

［1］Tanay A，Sharan R，Shamir R．Biclustering algorithms：A survey［J］．IEEE Trans on Computational Biology and Bioinformatics，2004，1（1）：24 45

［2］Kemal E，Mehmet D，Onur K，et al A comparative analysis of biclustering algorithms for gene expression data［J］．Briefings in Bioinformatics，2013，14（3）：279 292

［3］Inderjit S D，Mallela S，Modha D S．Information－theoretic co－clustering［C］??Proc of the 9th ACM SIGKDD．New York：ACM，2003：89 98

［4］Inderjit S D．Co－clustering documents and words using bipartite spectral graph partitioning［C］??Proc of the 7th ACM SIGKDD．New York：ACM，2001：269 274

［5］Li Tao，Ding Chris．Non－Negative Matrix Factorizations for Clustering：A Survey［M］??Data Clustering：Algorithms and Applications．London：Chapman ＆Hall?CRC，2013：149 176

［6］Long Bo，Zhang Zhongfei，Yu P S．Co－clustering by block value decomposition［C］??Proc of the 11th ACM SIGKDD．New York：ACM，2005：635 640

［7］Tjhi W C，Chen Lihui，Minimum sum－squared residue for fuzzy co－clustering［J］．Intelligent Data Analysis，2006，10（3）：237 249

［8］Li Zhao，Wu Xindong．Weighted nonnegative matrix trifactorization for co－clustering［C］??Proc of the 23rd IEEE Int Conf on Tools with Artificial Intelligence．Piscataway，NJ：IEEE，2011：811 816

［9］Shang Fanhua，Jiao Licheng，Wang Fei．Graph dual regularization non－negative matrix factorization for coclustering［J］．Pattern Recognition，2002，45（6）：2237 2250

［10］Salunke A，Liu Xumin，Rege M．Constrained co－clustering with non－negative matrix factorisation［J］．Journal of Business Intelligence and Data Mining，2012，7（1?2）：60 79

［11］Chen Yanhua，Rege M，Dong M，et al．Non－negative matrix factorization for semi－supervised data clustering［J］．Knowledge and Information Systems，2008，17（3）：355 379

［12］Chen Yanhua，Wang Lijun，Dong Ming．Non－negative matrix factorization for semisupervised heterogeneous data coclustering［J］．IEEE Trans on Knowledge and Data Engineering，2010，22（10）：1459 1474

［13］Wang Hua，Nie Feiping，Huang Heng，et al．Fast nonnegative matrix tri－factorization for large－scale data coclustering［C］??Proc of the 22nd Int Joint Conf on Artificial Intelligence．Palo Alto，CA：AAAI，2011：1553 1558

［14］Li Tao，Ding Chris．The relationships among various nonnegative matrix factorization methods for clustering［C］?? Proc of the 6th Int Conf on Data Mining．Piscataway，NJ：IEEE，2006：362 371

［15］Gu Quanquan，Zhou Jie．Co－clustering on manifolds［C］?? Proc of the 15th ACM SIGKDD．New York：ACM，2009：359 368

［16］Li Ping，Bu Jiajun，Chen Chun，et al．Relational coclustering via manifold ensemble learning［C］??Proc of the 21st CIKM．New York：ACM，2012：1687 1691

［17］Yan Xiaohui，Guo Jiafeng，Liu Shenghua，et al．Learning topics in short texts by non－negative matrix factorization on term correlation matrix［C］??Proc of the SIAM Int Conf Data Mining．Philadelphia，PA：SIAM，2013：749 757

［18］Ding Chris，Li Tao，Peng Wei，et al．Orthogonal nonnegative matrix tri－factorizations for clustering［C］??Proc of the 12th ACM SIGKDD．New York：ACM，2006：126 135

［19］Lomet A，Govaert G，Grandvalet Y．Design of artificial data tables for co－clustering analysis［R］．Compiègne，F(xiàn)rance：Universitéde Technologie de Compiègne，2012

［20］Deng Hongbo，Han Jiawei，Zhao Bo，et al．Probabilistic topic models with biased propagation on heterogeneous information networks［C］??Proc of the 17th ACM SIGKDD．New York：ACM，2011：1271 1279

［21］Zhao Ying，Karypis G．Criterion functions for document clustering：Experiments and analysis，UMN CS 01－040［R］．Minnesota，AK：University of Minnesota，2001

［22］Strehl A，Ghosh J．Cluster ensembles—A knowledge reuse framework for combining multiple partitions［J］．Journal of Machine Learning Research，2003，3：583 617

［23］Hubert L，Arabie P．Comparing partitions［J］．Journal of Classification，1985，2（1）：193 218

Shen Guowei，born in 1986．PhD candidate at Harbin Engineering University．His main research interests include data mining，social computing，etc．

Yang Wu，born in 1974．Professor and PhD supervisor at Harbin Engineering University．His main research interests include data mining，information security，etc（yangwu＠hrbeu．edu．cn）．

Wang Wei，born in 1974．PhD and associate professor at Harbin Engineering University．His main research interests include data mining，information security，etc（w＿wei＠hrbeu．edu．cn）．

Yu Miao，born in 1987．PhD candidate at Harbin Engineering University．His main research interests include data mining，social computing，etc（yumiao＠hrbeu．edu．cn）．

Dong Guozhong，born in 1989．PhD candidate at Harbin Engineering University．His main research interests include data mining，social computing，etc（dongguozhong＠hrbeu．edu．cn）．

Large－Scale Heterogeneous Data Co－Clustering Based on Nonnegative Matrix Factorization

Shen Guowei，Yang Wu，Wang Wei，Yu Miao，and Dong Guozhong
（Research Center of Information Security，Harbin Engineering University，Harbin150001）

Heterogeneous information network contains multi－typed entities and interactive relations．Some co－clustering algorithms have been proposed to mine underlying structure of different entities．However，with the increase of data scale，the scale of different class entities are growing unbalanced，and heterogeneous relational data are becoming extremely sparse．In order to solve this problem，we propose a two steps co－clustering algorithm FNMTF－CM based on correlation matrix decomposition．In the first step，the correlation matrix is built with the correlation relationship of smaller－typed entities and decomposed into indicating matrix of smaller－typed entity based on symmetric nonnegative matrix factorization．Correlation matrix has higher dense degree and smaller size compared with the original heterogeneous relationship matrix，so our algorithm can process large－scale heterogeneous data and maintain a high precision．After that，the indicating matrix of smaller－typed can be used as the input directly，so the heterogeneous relational matrix tri－factorization is very fast．Experiments on artificial and real－world heterogeneous data sets show that the accuracy and performance of FNMTFCM algorithm are superior to the traditional co－clustering algorithms based on nonnegative matrix factorization．

heterogeneous network；co－clustering；nonnegative matrix factorization；large－scale data；correlation matrix

TP391

2014－11－24；

2015－03－26

國家“八六三”高技術(shù)研究發(fā)展計(jì)劃基金項(xiàng)目（2012AA012802）；國家自然科學(xué)基金項(xiàng)目（61170242）

This work was supported by the National High Technology Research and Development Program of China（863Program）（2012AA012802）and the National Natural Science Foundation of China（61170242）．

楊武（yangwu＠hrbeu．edu．cn）

關(guān)鍵詞 異構(gòu)網(wǎng)絡(luò)；聯(lián)合聚類；非負(fù)矩陣分解；大規(guī)模數(shù)據(jù)；關(guān)聯(lián)矩陣