一種基于嵌入技術(shù)的異構(gòu)信息網(wǎng)絡(luò)的快速聚類算法

陳麗敏 楊 靜 張健沛

?

一種基于嵌入技術(shù)的異構(gòu)信息網(wǎng)絡(luò)的快速聚類算法

陳麗敏*①②楊 靜①張健沛①

①(哈爾濱工程大學(xué)計算機科學(xué)與技術(shù)學(xué)院 哈爾濱 150001)②(牡丹江師范學(xué)院計算機系 牡丹江 157012)

異構(gòu)信息網(wǎng)絡(luò)聚類分析是當前的熱點研究問題之一。利用異構(gòu)信息網(wǎng)絡(luò)的稀疏性，該文提出一種基于嵌入技術(shù)的星型模式的異構(gòu)信息網(wǎng)絡(luò)的快速聚類算法。首先從相容的角度將異構(gòu)信息網(wǎng)絡(luò)轉(zhuǎn)化為若干個相容的二部圖，使用隨機映射和一種線性時間求解程序快速計算出每個二部圖的近似通勤距離嵌入，每個嵌入都存在一個子集指示目標數(shù)據(jù)集；然后，使用這些指示子集構(gòu)建一個通用的聚類模型；最后，將所有指示子集的類設(shè)置標號，通過計算指示同一目標對象的指示數(shù)據(jù)與標號相同類的中心點的加權(quán)距離總和，同時劃分所有的指示子集，從而快速獲得通用模型的極小值。通過理論分析及實驗驗證，該文算法聚類速度快，聚類準確率高。

異構(gòu)信息網(wǎng)絡(luò)；聚類；通勤距離；嵌入；加權(quán)距離總和

1 引言

信息網(wǎng)絡(luò)普遍存在，如社會信息網(wǎng)絡(luò)、DBLP書目網(wǎng)絡(luò)等。同構(gòu)信息網(wǎng)絡(luò)是由一種類型數(shù)據(jù)構(gòu)成的，異構(gòu)信息網(wǎng)絡(luò)則是由多種類型數(shù)據(jù)構(gòu)成的。目前，同構(gòu)信息網(wǎng)絡(luò)的聚類研究已經(jīng)非常豐富[1,2]，但異構(gòu)信息網(wǎng)絡(luò)的聚類研究還不多，而異構(gòu)信息網(wǎng)絡(luò)聚類分析能更好地理解網(wǎng)絡(luò)的隱藏結(jié)構(gòu)以及每個類中的數(shù)據(jù)所代表的角色[3,4]。

異構(gòu)信息網(wǎng)絡(luò)中，星型網(wǎng)絡(luò)模式非常流行，也非常重要。星型網(wǎng)絡(luò)模式由一個目標對象數(shù)據(jù)集和多個屬性對象數(shù)據(jù)集構(gòu)成，關(guān)系只存在于目標對象與屬性對象之間，屬性對象之間不存在關(guān)系。

基于相容二部圖的思想解決多種異構(gòu)數(shù)據(jù)之間的復(fù)雜關(guān)系是行之有效的，從相容的角度出發(fā)，人們先后設(shè)計了多種算法解決了多種異構(gòu)數(shù)據(jù)協(xié)同聚類的問題，其中比較經(jīng)典的算法有基于半正定的規(guī)劃算法[5]，基于信息論的算法[6]以及譜聚類算法[7]。這類算法比較通用，但對于異構(gòu)信息網(wǎng)絡(luò)而言這些算法的復(fù)雜度太高。

基于概率模型的異構(gòu)信息網(wǎng)絡(luò)聚類算法NetClus[8]雖然聚類效率較高，但不具有通用性，而且算法的收斂性也不是很穩(wěn)定，基于概率模型的思想還被用于網(wǎng)絡(luò)服務(wù)聚類[9,10]。ComClus[11]算法是NetClus的衍生算法，面向包含同構(gòu)關(guān)系與異構(gòu)關(guān)系的信息網(wǎng)絡(luò)，仍然離不開具體的應(yīng)用領(lǐng)域，不具有通用性。基于密度的異構(gòu)網(wǎng)絡(luò)的子空間聚類算法計算速度較慢[12]，使用語義路徑相似性與傳統(tǒng)算法結(jié)合的異構(gòu)網(wǎng)絡(luò)聚類[13,14]也與具體應(yīng)用領(lǐng)域相關(guān)。

異構(gòu)網(wǎng)絡(luò)鏈接推理[15]時，往往需要最初的聚類劃分更精確一些，因此高準確率的聚類是十分必要的，但是當網(wǎng)絡(luò)的數(shù)據(jù)量非常大時，計算速度又不能太慢。文獻[16]在同構(gòu)數(shù)據(jù)上使用近似通勤距離嵌入聚類取得了非常好的效果。星型網(wǎng)絡(luò)模式的異構(gòu)信息網(wǎng)絡(luò)能夠轉(zhuǎn)換成若干個相容的二部圖，使用通勤距離度量二部圖各結(jié)點之間的關(guān)系，能夠提高聚類準確率。異構(gòu)信息網(wǎng)絡(luò)規(guī)模大，但是很稀疏，所以可以使用隨機映射和線性時間求解程序[17,18]快速計算出每個二部圖的近似通勤距離嵌入。每個嵌入都存在一個子集指示目標數(shù)據(jù)集，使用這些指示子集構(gòu)建一個通用的聚類模型。然后將所有指示子集的類設(shè)置標號，通過計算每個目標對象的所有指示數(shù)據(jù)與標號相同的類的中心點的加權(quán)距離總和，同時劃分所有的指示子集，從而快速獲得該通用模型的極小值。本文算法是一個通用的異構(gòu)信息網(wǎng)絡(luò)聚類算法，計算速度快，聚類準確率高。

2 二部圖的近似通勤距離嵌入

2.1 二部圖的通勤距離嵌入

是二部圖G的權(quán)重總和，即,是第個元素為1的單位列向量，即

設(shè)二部圖G有條邊，根據(jù)文獻[20]，定向G的邊，令

其中,是G的任意兩個結(jié)點，則是一個有向邊-點入射矩陣。設(shè)是由邊的權(quán)值構(gòu)成的對角矩陣，則G的Laplace矩陣可表示為。

由性質(zhì)1,G的任意兩個結(jié)點,的通勤距離c為

則c是空間第個列向量與第個列向量的歐式距離的平方，稱為二部圖G的通勤距離嵌入。是G的兩個結(jié)點間的平均路徑長度，而不是兩結(jié)點間的最短路徑，因此使用通勤距離度量結(jié)點間的關(guān)系，能夠捕獲復(fù)雜的類，聚類有噪音的數(shù)據(jù)，魯棒性更好。那么，使用通勤距離嵌入聚類也能夠捕獲復(fù)雜的類。

2.2二部圖的近似通勤距離嵌入

引理1[21]給定向量和,是行向量獨立同分布的隨機矩陣，其中等概率，。則，至少存在概率滿足

定理1 給定二部圖G,，矩陣, 則，至少存在概率滿足

似通勤距離嵌入，二部圖的近似通勤距離嵌入(Approximate Commute Distance Embedding of bipartite graph, ACDE)算法如表1所示。

表1二部圖的近似通勤距離嵌入

0與1的數(shù)據(jù)對象映射到了一個共同的子空間。的前0個列向量指示數(shù)據(jù)集0，后1個列向量指示數(shù)據(jù)集1。稀疏矩陣有個非零元素，第(1)步計算與及的時間復(fù)雜度為。因為稀疏矩陣有2個非零元素，對角矩陣有個非零元素，故第(2)步計算的時間復(fù)雜度為。使用STSolve方法[17,18]計算方程組的一個解需要花費時間，故第(3)步構(gòu)造的時間為。則算法ACDE的時間復(fù)雜度為++=。后續(xù)實驗證明，在不同的數(shù)據(jù)集上k取值都很小。

3 基于近似通勤距離嵌入的異構(gòu)信息網(wǎng)絡(luò)聚類

3.1通用模型的構(gòu)建

目標數(shù)據(jù)集0與屬性數(shù)據(jù)集構(gòu)成一個二部圖，一個二部圖對應(yīng)一個關(guān)系矩陣。由算法ACDE計算二部圖的近似通勤距離嵌入，其中的前0個數(shù)據(jù)指示目標數(shù)據(jù)集0，表示為，后n個數(shù)據(jù)指示屬性數(shù)據(jù)集X，表示為，稱與為指示子集。指示0的第個對象，稱為指示數(shù)據(jù)，。的指示數(shù)據(jù)與0的對象一一對應(yīng)。包含個二部圖，個二部圖對應(yīng)個近似通勤距離嵌入，則目標數(shù)據(jù)集0被個指示子集所指示，0的每個對象被個指示數(shù)據(jù)所指示。

從相容的角度，式(1)目標函數(shù)取得最小值，則目標數(shù)據(jù)集0聚類達到最佳。顯然，式(1)的全局最優(yōu)解是NP難問題。

3.2 快速算法的推理

3.2.2加權(quán)距離總和0的一個對象被個指示數(shù)據(jù)所指示，這個指示數(shù)據(jù)到各自嵌入子集的類的中心點的距離都影響著該目標對象所屬類的分配。指示數(shù)據(jù)到中心點的距離的權(quán)重由其指示子集的權(quán)重決定，指示子集的權(quán)重就是相應(yīng)的關(guān)系矩陣的權(quán)重。

3.2.3的極小值求解可以進一步表示為

定理2

表2基于嵌入技術(shù)的異構(gòu)信息網(wǎng)絡(luò)快速聚類算法

由算法1的時間復(fù)雜度分析可知算法2第(1)步的時間復(fù)雜度為，其中是異構(gòu)信息網(wǎng)絡(luò)的二部圖的數(shù)目，k是指示子集數(shù)據(jù)的維度，n與s是第個二部圖的結(jié)點數(shù)與邊數(shù)。第(2)步僅僅花費()時間，是常量。第(3)步花費(uTKkn0)時間，其中是聚類數(shù)目，0是0的對象數(shù)目，是式(3)收斂的迭代次數(shù)。所以算法FCAET的時間復(fù)雜度為+(uTKkn0)，其中k,都很小，而與是常量。

4 實驗

4.1 實驗數(shù)據(jù)

從DBLP選取真實數(shù)據(jù)建立實驗數(shù)據(jù)集，DBLP是一個典型的異構(gòu)信息網(wǎng)絡(luò)，其中包括4種類型數(shù)據(jù)對象，分別命名為papers, authors, terms和venues。首先抽取一個小數(shù)據(jù)集S1，即文獻[8]使用的稱為“four-area dataset”的數(shù)據(jù)集。小數(shù)據(jù)集S1選取了4個學(xué)術(shù)區(qū)域，這4個區(qū)域為：database, data mining, information retrieval及machine learning。每個區(qū)域取5個有代表性的會議，共20個會議，20個會議的所有authors, papers及出現(xiàn)在論文題目中的所有terms。

本文又抽取2008~2012年的8個學(xué)術(shù)區(qū)域的DBLP數(shù)據(jù)作為另外一個測試數(shù)據(jù)集，這8個學(xué)術(shù)區(qū)域為：databases, data mining & machine learning, information retrieval, computer graphics, computer network, information security, computer architecture, software engineering & programming language。數(shù)據(jù)集共包括80個venues(每個區(qū)域選取10個venues), 21,271個papers, 45, 576個authors及42, 962個terms。這個大的數(shù)據(jù)集稱為S2。

當分析papers時，papers作為目標數(shù)據(jù)集，其他為屬性數(shù)據(jù)集。因為DBLP提供了非常有限的引用信息，故papers之間不設(shè)置直接的鏈接。當分析authors時， authors 作為目標數(shù)據(jù)集，papers 與venues 作為屬性數(shù)據(jù)集。由于合作關(guān)系，authors之間存在直接的鏈接。故authors還作為目標數(shù)據(jù)集的另外一個屬性數(shù)據(jù)集。

本文算法均采用文獻[22]的一種近乎線性時間的求解程序計算算法中的嵌入數(shù)據(jù)集，該方法用于對角占優(yōu)矩陣，網(wǎng)址http://www.cs.cmu.edu/~ jkoutis/cmg.html。實驗的運行環(huán)境為Inter Pentium III處理器，2 GB內(nèi)存，Windows XP操作系統(tǒng)，Matlab編程。

4.2 關(guān)系矩陣的確定

當papers為目標數(shù)據(jù)集, authors, venues 和terms 為屬性數(shù)據(jù)集。0表示目標數(shù)據(jù)集papers,1,2與3分別表示屬性數(shù)據(jù)集authors, venues與terms。0與的關(guān)系矩陣為，其中的元素為

當authors為目標數(shù)據(jù)集, papers 和 venues 為屬性數(shù)據(jù)集。因為作者之間存在合作關(guān)系，authors也是另外一個屬性數(shù)據(jù)集。0表示authors,1與2分別表示papers與venues。為0與X的關(guān)系矩陣，。其中的元素為

實驗的所有算法均采用相同的關(guān)系矩陣。

4.3 參數(shù)分析

4.3.1參數(shù)k分析k在不同的數(shù)據(jù)集上取值都非常小[16]。文獻[16]實驗證明對同構(gòu)數(shù)據(jù)集，當時，準確率曲線已經(jīng)很平滑。取小數(shù)據(jù)集S1來比較參數(shù)k的變化對異構(gòu)信息網(wǎng)絡(luò)數(shù)據(jù)聚類準確率的影響。使用算法FCAET聚類papers時，的權(quán)重分別取,,。聚類authors時，的權(quán)重分別取,,。迭代次數(shù)。k對算法準確率的影響如圖1，圖2所示。

實驗說明當k>50時準確率曲線已經(jīng)趨于平滑。因此取k=60是很適合的。k很小，且對算法FCAET的計算速度基本沒有影響。這也是算法FCAET的一個優(yōu)點，即在準確性方面對參數(shù)k不敏感。其他實驗也取相同的關(guān)系矩陣權(quán)重及k=60。

4.3.2 迭代次數(shù)分析 取小數(shù)據(jù)集S1比較迭代次數(shù)對異構(gòu)信息網(wǎng)絡(luò)數(shù)據(jù)聚類準確率的影響。迭代參數(shù)對papers及authors聚類準確率的影響如圖3，圖4所示。當時，算法就已經(jīng)收斂，說明本文算法收斂速度非?？?，本文其他實驗均取。

圖1 kr對papers的影響　　　　　　　　　　　　　　　　　　圖2 kr對authors的影響

圖3 u對papers的影響　　　　　　　　　　　　　　　　　　圖4 u對authors的影響

4.4聚類穩(wěn)定性對比

本文選擇復(fù)雜度較低的通用算法CIT[6]，基于排序的算法NetClus[8]與本文算法FCAET做穩(wěn)定性比較。算法ComClus是NetClus的衍生算法，性質(zhì)類似，這里不做分析。本次實驗在小數(shù)據(jù)集S1上聚類目標數(shù)據(jù)集papers，以比較3個算法CIT,NetClus及FCAET的穩(wěn)定性。3個算法的10次實驗準確率如圖5所示，雖然算法FCAET和算法NetClus的計算速度都很快，但圖5的實驗數(shù)據(jù)說明本文算法FCAET的穩(wěn)定性更好，初始中心點的選擇對聚類結(jié)果影響不大，而算法NetClus不是很穩(wěn)定，初始類的劃分對算法NetClus的函數(shù)及收斂速度影響非常大。當異構(gòu)信息網(wǎng)絡(luò)稀疏時，算法CIT的收斂速度比較慢，當?shù)螖?shù)很小時，聚類精度并不高。

圖5 3個算法10次實驗聚類準確率比較

4.5聚類準確率及計算速度的對比

基于半正定的規(guī)劃算法[5]以及譜聚類算法[7]時間復(fù)雜度過高，不適合聚類規(guī)模較大的異構(gòu)信息網(wǎng)絡(luò)。本文選擇復(fù)雜度較低的通用算法CIT[6]，基于排序的算法NetClus[8]，及NetClus的衍生算法ComClus[11]與本文算法FCAET做準確率及計算速度的比較。算法NetClus, ComClus的參數(shù)均取文獻[8]給定的實驗參數(shù)。每個算法都涉及到初始劃分，初始劃分影響聚類結(jié)果，因此，對于每個目標數(shù)據(jù)集，所有算法均做3次實驗，3次實驗中聚類準確率最高的一次作為該算法的準確率，本次實驗的計算速度作為該算法的計算速度。聚類準確率對比結(jié)果如表3所示，表3數(shù)據(jù)說明本文算法的聚類準確率高于其他算法。算法CIT計算復(fù)雜度(2)，當異構(gòu)信息網(wǎng)絡(luò)稀疏時，算法CIT的收斂速度比較慢，故聚類精度并不高。算法NetClus只使用了異構(gòu)數(shù)據(jù)關(guān)系，故聚類精度較低。算法ComClus利用了同構(gòu)數(shù)據(jù)的關(guān)系，聚類精度高于NetClus的聚類精度，但也增加了計算復(fù)雜度。本文算法是一種基于圖嵌入技術(shù)的聚類算法，而且采用通勤距離度量能夠更加充分表現(xiàn)數(shù)據(jù)之間的關(guān)系，并且收斂性速度不受關(guān)系矩陣的稀疏性影響，同時也能夠利用目標數(shù)據(jù)集的同構(gòu)關(guān)系，故聚類精度高。計算速度對比結(jié)果如表4所示，表4數(shù)據(jù)說明本文算法的計算時間基本等同于算法NetClus的計算時間。但本文算法FCAET通用性更強，可以用于任何一個星型網(wǎng)絡(luò)模式的異構(gòu)信息網(wǎng)絡(luò)的聚類。而算法NetClus及ComClus需要根據(jù)具體應(yīng)用領(lǐng)域設(shè)計函數(shù)，依賴于數(shù)據(jù)特性，不具有普遍性。

4.6FCAET運行時間分析

算法FCAET在兩個數(shù)據(jù)集上的運行時間分布情況如表5所示，實驗說明本文算法的運行效率是很高的。3個指示子集的串行計算速度占程序運行時間50%左右。若并行計算3個指示子集，速度會更快。求解模型極小值也可采用并行執(zhí)行以提高計算速度。

表3聚類準確率比較(%)

目標對象CITNetClusComClusFCAET S1的papers73.9171.5472.8378.87 S1的authors74.4169.1374.9181.33 S2的papers70.8471.2872.9376.36 S2的authors71.0268.2973.0177.94

表4計算速度比較(s)

目標對象CITNetClusComClusFCAET S1的papers 78.5 37.3 40.3 37.1 S1的authors 79.8 36.9 39.8 38.3 S2的papers1459.3792.6817.3798.4 S2的authors1474.7733.7771.4764.9

表5算法FCAET運行時間分配情況(s)

目標對象嵌入計算時間聚類時間時間總和 S1的papers 19.6 17.5 37.1 S1的authors 18.1 20.2 38.3 S2的papers393.8405.6798.4 S2的authors376.4388.5764.9

5 結(jié)束語

本文提出的異構(gòu)信息網(wǎng)絡(luò)快速聚類算法不同于以往的異構(gòu)數(shù)據(jù)聚類算法，本文算法根據(jù)每個關(guān)系矩陣先求解指示目標數(shù)據(jù)集的每個指示數(shù)據(jù)集，然后根據(jù)指示數(shù)據(jù)之間的關(guān)系建立模型，從而得到目標數(shù)據(jù)集的劃分。本文算法通用性強、穩(wěn)定性好，同時計算速度快而且聚類準確率高，非常適合異構(gòu)信息網(wǎng)絡(luò)的聚類。而以往的聚類算法要么時間復(fù)雜度過高，要么通用性不強，聚類結(jié)果不穩(wěn)定。通過理論分析及實驗驗證，本文算法的計算速度和聚類準確率滿足要求。本文算法中各關(guān)系矩陣的權(quán)重影響著目標數(shù)據(jù)集的劃分，這些權(quán)重還不能自適應(yīng)確定，需要進一步研究。當異構(gòu)數(shù)據(jù)關(guān)系不再稀疏，網(wǎng)絡(luò)模式不再是星型的，如何快速劃分任意模式的大規(guī)模異構(gòu)信息網(wǎng)絡(luò)，都是亟待解決的問題。

[1] 肖杰斌, 張紹武. 基于隨機游走和增量相關(guān)節(jié)點的動態(tài)網(wǎng)絡(luò)社團挖掘算法[J]. 電子與信息學(xué)報. 2013, 35(4): 977-981.

Xiao Jie-bin and Zhang Shao-wu. An algorithm of integrating random walk and increment correlative vertexes for mining community of dynamic networks[J].&, 2013, 35(4): 977-981.

[2] 陳季夢, 陳家俊, 劉杰, 等. 基于結(jié)構(gòu)相似度的大規(guī)模社交網(wǎng)絡(luò)聚類算法[J]. 電子與信息學(xué)報. 2015, 37(2): 449-454.

Chen Ji-meng, Chen Jia-jun, Liu Jie,.. Clustering algorithms for large-scale social networks based on structural similarity[J].&, 2015, 37(2): 449-454.

[3] Sun Y and Han J. Mining heterogeneous information networks: principles and methodologies[J].:,2012, 3(2): 1-159.

[4] Huang Y and Gao X. Clustering on heterogeneous networks [J].:, 2014, 4(3): 213-233.

[5] Gao B, Liu T Y, Zheng X,.. Consistent bipartite graph co-partitioning for star-structured high-order heterogeneous data co-clustering[C]. Proceedings of the 11th ACM SIGKDD International Conference on Knowledge Discovery in Data Mining, Chicago, 2005: 41-50.

[6] Gao B, Liu T, and Ma W-Y. Star-structured high-order heterogeneous data co-clustering based on consistent information theory[C]. Proceedings of the 6th International Conference on Data Mining (ICDM 2006), Hong Kong, 2006: 880-884.

[7] Long B, Zhang Z M, Wu X,.. Spectral clustering for multi-type relational data[C]. Proceedings of the 23rd International Conference on Machine Learning, Pittsburgh, 2006: 585-592.

[8] Sun Y, Yu Y, and Han J. Ranking-based clustering of heterogeneous information networks with star network schema[C]. Proceedings of the 15th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, Paris, 2009: 797-806.

[9] Li P, Wen J, and Li X. SNTClus: a novel service clustering algorithm based on network analysis and service tags[J]., 2013, 89(1): 208-210.

[10] Li P, Chen L, Li X,.. RNRank: Network-Based Ranking on Relational Tuples[M]. Boston: Behavior and Social Computing, Springer International Publishing, 2013: 139-150.

[11] Wang R, Shi C, Philip S Y,.. Integrating Clustering and Ranking on Hybrid Heterogeneous Information Network[M]. Berlin: Advances in Knowledge Discovery and Data Mining, Springer Berlin Heidelberg, 2013: 583-594.

[12] Boden B, Ester M, and Seidl T. Density-Based Subspace Clustering in Heterogeneous Networks[M]. Berlin: Machine Learning and Knowledge Discovery in Databases, Springer Berlin Heidelberg, 2014: 149-164.

[13] Meng Q, Tafavogh S, and Kennedy P J. Community detection on heterogeneous networks by multiple semantic- path clustering[C]. 2014 6th IEEE International Conference on Computational Aspects of Social Networks (CASoN), Porto, 2014: 7-12.

[14] Meng X, Shi C, Li Y,.. Relevance Measure in Large-scale Heterogeneous Networks[M]. Boston: Web Technologies and Applications, Springer International Publishing, 2014: 636-643.

[15] Aggarwal C C, Xie Y, and Philip S Y. On dynamic link inference in heterogeneous networks[C]. SIAM International Conference on Data Mining, Anaheim, 2012: 415-426.

[16] Khoa N L D and Chawla S. Large Scale Spectral Clustering Using Resistance Distance and Spielman-teng Solvers[M]. Berlin:Discovery Science, Springer Berlin Heidelberg, 2012: 7-21.

[17] Spielman D A and Teng S H. Nearly-linear time algorithms for graph partitioning, graph sparsification, and solving linear systems[C]. Proceedings of the 36th Annual ACM Symposium on Theory of Computing, Chicago, 2004: 81-90.

[18] Spielman D A and Teng S H. Nearly linear time algorithms for preconditioning and solving symmetric, diagonally dominant linear systems[J]., 2014, 35(3): 835-885.

[19] Fouss F, Pirotte A, Renders J M,.. Random-walk computation of similarities between nodes of a graph with application to collaborative recommendation[J]., 2007, 19(3): 355-369.

[20] Spielman D A and Srivastava N. Graph sparsification by effective resistances[J]., 2011, 40(6): 1913-1926.

[21] Achlioptas D. Database-friendly random projections[C]. Proceedings of the 20th ACM Sigmod-Sigact-Sigart Symposium on Principles of Database Systems, New York, 2001: 274-281.

[22] Koutis I, Miller G L, and Tolliver D. Combinatorial preconditioners and multilevel solvers for problems in computer vision and image processing[J]., 2011, 115(12): 1638-1646.

A Fast Clustering Algorithm Based on Embedding Technology for Heterogeneous Information Networks

Chen Li-min①②Yang Jing①Zhang Jian-pei①

①(,,150001,)②(,,157012,)

Research on clustering heterogeneous information networks is one of the current hotspots. Taking advantages of the sparsity of heterogeneous information networks, a fast clustering algorithm based on embedding technology for heterogeneous information networks of star network schema is proposed in this paper. First, the heterogeneous information network is transformed into some compatible bipartite graphs from the point of compatible view. Then, the approximate commute distance embedding of each bipartite graph is computed via random mapping and a linear time solver, and an indicator subset in each embedding indicates the target dataset. At last, a general model is formulated via all the indicator subsets, and a minimum value of the model is derived by simultaneously clustering all of the indicator subsets using the sum of the weighted distances for all indicators for an identical target object. This proposed algorithm is effective by theory analysis and experimental verification.

Heterogeneous information network; Clustering; Commute distance; Embedding; Sum of weighted distances

TP311

A

1009-5896(2015)11-2634-08

10.11999/JEIT150106

2015-01-21；改回日期：2015-07-16；

2015-08-25

陳麗敏 chenlimin_clm@126.com

國家自然科學(xué)基金(61370083, 61073043, 61073041)；高等學(xué)校博士學(xué)科點專項科研基金(20112304110011, 20122304110012)

The National Natural Science Foundation of China (61370083, 61073043, 61073041); The National Research Foundation for the Doctoral Program of Higher Education of China (20112304110011, 20122304110012)

陳麗敏： 女，1970年生，副教授，博士生，研究方向為數(shù)據(jù)挖掘、機器學(xué)習(xí).

楊 靜： 女，1962年生，教授，博士生導(dǎo)師，研究方向為數(shù)據(jù)庫與知識庫.

張健沛： 男，1956年生，教授，博士生導(dǎo)師，研究方向為數(shù)據(jù)庫與知識庫.