一種基于嵌入技術的異構信息網絡的快速聚類算法

陳麗敏 楊 靜 張健沛

?

一種基于嵌入技術的異構信息網絡的快速聚類算法

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

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

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

異構信息網絡；聚類；通勤距離；嵌入；加權距離總和

1 引言

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

異構信息網絡中，星型網絡模式非常流行，也非常重要。星型網絡模式由一個目標對象數據集和多個屬性對象數據集構成，關系只存在于目標對象與屬性對象之間，屬性對象之間不存在關系。

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

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

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

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

2.1 二部圖的通勤距離嵌入

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

設二部圖G有條邊，根據文獻[20]，定向G的邊，令

其中,是G的任意兩個結點，則是一個有向邊-點入射矩陣。設是由邊的權值構成的對角矩陣，則G的Laplace矩陣可表示為。

由性質1,G的任意兩個結點,的通勤距離c為

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

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

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

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

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

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

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

3 基于近似通勤距離嵌入的異構信息網絡聚類

3.1通用模型的構建

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

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

3.2 快速算法的推理

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

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

定理2

表2基于嵌入技術的異構信息網絡快速聚類算法

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

4 實驗

4.1 實驗數據

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

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

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

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

4.2 關系矩陣的確定

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

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

實驗的所有算法均采用相同的關系矩陣。

4.3 參數分析

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

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

4.3.2 迭代次數分析 取小數據集S1比較迭代次數對異構信息網絡數據聚類準確率的影響。迭代參數對papers及authors聚類準確率的影響如圖3，圖4所示。當時，算法就已經收斂，說明本文算法收斂速度非常快，本文其他實驗均取。

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

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

4.4聚類穩定性對比

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

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

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

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

4.6FCAET運行時間分析

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

表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 結束語

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

[1] 肖杰斌, 張紹武. 基于隨機游走和增量相關節點的動態網絡社團挖掘算法[J]. 電子與信息學報. 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] 陳季夢, 陳家俊, 劉杰, 等. 基于結構相似度的大規模社交網絡聚類算法[J]. 電子與信息學報. 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

國家自然科學基金(61370083, 61073043, 61073041)；高等學校博士學科點專項科研基金(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年生，副教授，博士生，研究方向為數據挖掘、機器學習.

楊 靜： 女，1962年生，教授，博士生導師，研究方向為數據庫與知識庫.

張健沛： 男，1956年生，教授，博士生導師，研究方向為數據庫與知識庫.