基于屬性—鏈接的聚類算法綜述

摘要：首先總結了鏈接挖掘中基于屬性—鏈接聚類算法的研究現狀；然后把它大體分為三類，對每一類中具有代表性的算法進行了詳細介紹、分析和評價；最后指出了該領域進一步的研究方向。

關鍵詞：屬性—鏈接聚類； 鏈接結構； 聚類算法

中圖分類號：TP391文獻標志碼：A

文章編號：1001－3695(2008)06－1622－04

0引言

隨著信息技術的發展，越來越多的數據被收集和整合在一起，大規模異質數據集不斷涌現，建立一個大的社會網絡成為可能。實際上，社會網絡是一個抽象概念，它并不一定必須是社會的[1]。在現實世界中，有許多科技、商業、經濟和生物的社會網絡實例，包括電力網絡、萬維網、引用網絡、流行病學網絡、食物網絡等。

近幾年在實證研究中，人們已經發現大多數的社會網絡都存在集團結構[2]。集團內部存在比較緊密的聯系，集團之間的聯系相對比較松散。這些聯系之中包含了很多信息，在實際中有著重要意義。對于集團結構的深入研究可以幫助人們分析和了解實際網絡的特性和結構。尋找社會網絡中潛在集團的思路與社會學中對圖的分割思想十分近似，而且可以看做是把網絡中節點（節點表示對象）分成不同的簇，同一簇中的對象之間具有較高的相似度，而不同簇中的對象差別較大的聚類問題。

傳統的聚類算法認為數據集是由同類、相互獨立、等概率分布的實體組成的[3，4]，只側重于研究單一實體屬性，而忽略實體間的相互作用關系，必然不能很好地從中發現知識。社會網絡數據顯然不滿足這樣的假設。因而，在對社會網絡數據進行挖掘的過程中，必須注意同時考慮行動者的屬性及其與其他行動者之間的聯系。社會網絡數據中蘊涵了大量的聯系信息，充分挖掘這些信息是數據挖掘的重要目標。因而，不但不能簡單假設樣本是獨立的，還要充分利用這些聯系來建立更加準確的模型。

圖的分割算法是完全利用圖的結構特點去發現具有高度連通性的子圖。它關注圖的結構，使用最優的最小規范切（minimum cutsize）或最大連通性（maximum connectivity）來把圖中節點分成若干個簇[4]，忽略了實體的屬性信息。因此，既強調實體間的相互作用關系，又考慮實體的屬性信息的聚類（本文稱為屬性—鏈接聚類），會更好地挖掘出以前未曾發現的潛在集團。這種潛在的集團也許會更接近社會網絡結構的實際情況。

屬性—鏈接聚類已經成為目前比較熱門的研究領域，它彌補了傳統的基于屬性的聚類方法，忽略了結構信息的弱點和基于圖的聚類算法，忽略了屬性信息的弱點。目前，屬性—鏈接聚類主要是針對超文本信息檢索、互聯網社區發現、實體識別等方面的研究。本文將把屬性—鏈接聚類方法大致分為基于相似度、基于概率模型和基于譜聚類三種方法。

1基于相似度的方法

數據挖掘中有許多方法是基于相似度度量，如k近鄰算法，其本質是在一些排序任務中給出一個評價標準。相似度的定義是這類算法中的核心步驟。相似度的定義和問題是相關的，同一個數據集在不同的任務下最佳的相似度定義很有可能是不同的。很多時候很難選取一個適合的相似度度量，尤其當屬性數目多，并且與目標任務的關系不明確的時候。但是，如果能夠給出合適的相似度度量，這類算法具有很好的直觀解釋。本文介紹的基于相似度的方法是考慮了超文本的內容和超文本的鏈接結構兩個方面來定義相似度的方法。其中，具有代表性的算法有HyPursuit算法、M－S算法和距離相似算法。

1．2M－S算法

Modha和Spangler[6]在2000年提出一種用于超文本文檔聚類的算法。此算法的基本出發點與文獻[5]比較接近，都是將文本信息和結構信息分別表示為獨立的向量，再通過算法模型對它們加以整合。但在算法模型的選擇、相似性的度量以及聚類的表示上，與文獻[5]存在較大的差別。

Modha等人提出的相似性度量考慮了文檔的三個參數：超文本中包含的詞、超文本的出鏈及超文本的入鏈。每一個超文本文檔可以三元組(D，F，B)表示。其中：D表示文檔中包含的詞向量；F表示文檔的出鏈向量；B表示文檔的入鏈向量。假設W表示整個網，Ω表示W的一個子集，該子集是通過搜索引擎查詢得到的超文本。下面介紹文檔中包含的詞向量、文檔的出鏈向量和入鏈向量的構建方法。

1）詞向量的構建其基本思想是找出Ω集合中所有文檔出現的詞構成詞典。如果一個詞僅出現在一個文檔中，那么就從詞典中去掉該詞。假設經過這種刪除之后得到d個獨特的詞，把它們用數字標志符標出。對于每一個文檔x就可以得到一個d維的向量，向量的第j列表示第j個詞在文檔x中出現的次數。

2）出鏈向量的構建其基本思想是在集合W\\Ω和集合Ω中所有的超文本中建立出鏈字典，字典中的文檔包括Ω中的文檔指向的文檔和Ω中的每一個文檔。為了使用統一的方式處理W\\Ω和Ω中的文檔，此算法把Ω集合中的文檔增加一個自己指向自己的環。如果一個文檔被Ω集合中文檔指向的文檔數小于兩個，那么它就從出鏈字典中刪除。假如經過此刪除步驟，出鏈字典得到f個文檔，那么Ω集合中的每一個文檔表示成f維的向量。向量中第j列表示文檔x指向出鏈字典中保留文檔的文檔數。

3）入鏈向量的構建其基本思想是在集合W\\Ω和集合Ω中所有的超文本中建立入鏈字典，字典中的文檔包括指向Ω集合中文檔的所有文檔和Ω中的每一個文檔。為了使用統一的方式處理W\\Ω和Ω中的文檔，此算法把Ω集合中的文檔增加一個自己指向自己的環。如果一個文檔指向Ω集合中文檔的文檔數小于兩個，那么它就從入鏈字典中刪除。假如經過此刪除步驟，入鏈字典得到b個文檔，那么Ω集合中的每一個文檔x表示成b維向量。向量中第j列表示出鏈字典中保留文檔指向文檔x的文檔數。

假設Ω集合中有n個文檔，每一個文檔都可以表示成xi=(Di，Fi，Bi)；1≤i≤n。給定兩個文檔的向量x=(D，F，B)和=(，，)，它們之間的相似度定義為

S(x，)=αdDT+αfFT+αbBT（3）

其中：αd+αf+αb=1；αd、αf、αb都是非負數。

Modha等人根據式（3）定義的相似度采用k均值算法進行聚類，算法的復雜度是O(n)。其中：n是超文本的數目。該算法很好地將超文本內容與鏈接結構兩者結合在一起，并給出一個定量的計算方法，同時聚類過程是自動的。

1．3距離相似算法

現實世界中的實體在不同的數據源中常常有多個表達，在數據集成時經常要判斷不同數據源中的表達是否代表現實世界中的同一實體。語法上相同或相似的不同記錄可能代表現實世界中的同一實體。Bhattacharya和Getoor[7]在2004年首次提出用迭代的方法來解決作者識別的問題。這種利用實體之間相關信息的思想為識別疑難重復記錄對象提供了一條好的途徑。

根據實體之間的距離來決定它們是否互為副本。給定的實體對象r的集合去構建關系dup(ri，rj)。這個關系是對稱的和自反的，即每一個對象都是其自身的副本。如果兩個實體對象之間的距離小于給定的閾值，那么其中一個就是另一個的副本。用數學表達式表示為：如果d(ri，rj)t，那么dup(ri，rj)=true；否則，dup(ri，rj)=1。其中：t為給定的閾值。距離的度量函數d(ri，rj)是由帶權重的實體屬性距離和帶權重實體所在簇之間的距離相結合構成的。實體以及它的副本所屬的組的集合稱為組集。Bhattacharya提出了兩種將實體間關系的相似性結合實體本身屬性的相似性來判斷兩個實體引用是否指向同一個實體的距離函數。這兩種距離主要用于組集之間的距離度量。下面分別來介紹它們。

1）組細微距離dgroup（group detail distance）它考慮了所有觀察到的信息。根據組細微距離，兩個實體對象之間的距離公式為

d(ri，rj)=(1-α)×dattr(ri，rj)+α×dgroup(G(ri)，G(rj))(4)

其中：dattr(ri，rj)表示兩個對象之間的屬性距離；dgroup(G(ri)，G(rj))表示對象組集之間的距離；α是兩個相鄰對象之間的權重；G(r)表示對象r或它的副本r′所在的組的集合。

兩個組集G(ri)與G（rj）之間的距離是以兩個組g1與g2之間的距離為基礎的。為了計算兩個組g1與g2之間的距離d(g1，g2)，定義了兩個組之間的相似性：

sim(g1，g2)=|common(g1，g2)|/max(|g1|，|g2|)(5)

common(g1，g2)={(r1，r2)|dup(r1，r2)}；r1∈g1，r2∈g2(6)

兩個組g1與g2之間的距離為

d(g1，g2)=1-sim(g1，g2)（7）

最后，兩個組集合G1和G2之間的距離為：G1中的所有組g與G2的距離的平均， G2中的所有組g與G1的距離的平均，兩個平均再求平均，即

d(G1，G2)=[gi∈G1d(gi，G2)+gj∈G2d(gj，G1)]/2（8）

其中：g與G的距離定義為g與G中所有組g′的距離中最短的，即d(g，G)=ming′∈G d(g，g′)。本文把這種距離d(G1，G2)稱為組細微距離。

2）組概要距離dgsum（group summary distance）雖然組細微距離比較有用，但由組細微距離的定義可以看出，它不僅要計算G1中每一個組與G2的距離，還要計算G2中的每一個組與G1的距離，因此計算時間開銷比較昂貴。

Bhattacharya和Getoor又提出一種可替代、易于處理的方法——稱為組概要距離dgsum。此方法用比較簇Ck之間的距離來替代實體ri之間的距離。一個組g是由天然形成的實體r組成。一個實體及其副本集合稱為一個簇Ck。一個簇Ck所包含的組是指這個簇中的實體及其副本所在組的集合，用集合形式表示為G(ck)={g(ri)|ri∈ck}。根據簇的定義，簇的組概要gsum用集合形式表示為gsum(ck)={ci|ci∈gi，gi∈G(ck)}。兩個簇的組概要gsum之間的距離稱為dgsum。因此，求兩個實體之間的距離轉換為簇之間的距離，距離公式為

d(ci，cj)=(1-α)×dattr(ci，cj)+α×dgsum(ci，cj)(9)

其中：dattr為簇之間的屬性距離；dgsum為簇之間的概要距離。

該算法的過程大致為：在算法開始時，每一個實體都認為是一個單獨的簇，并且所有簇之間的組概要距離dgsum都等于零。初始簇形成后就選擇候選簇對（可能為同一個實體的簇稱為候選簇對）。通過設定的距離閾值來選取候選集。在每一迭代中，算法對候選集重新計算距離，選擇距離最近的一對簇進行合并；然后更新屬性值和簇的組概要，直到候選集選完為止。

實驗結果顯示，隨著數據量的增大，組概要距離聚類的時間是平穩上升的。基于組概要或組細微距離的聚類比基于屬性的聚類質量有一個很大的提高，但計算的時間要付出大約一倍。眾所周知，數據庫數據清洗工作一般不可能很頻繁地進行。為了質量較高的數據質量，稍微偏大的計算時間是可以接受的。但此方法對于不存在明顯類別的數據集來說不一定是很好的聚類效果。 

1．4其他基于相似度算法

此外，還有許多研究致力于將內容信息、用戶瀏覽信息甚至超文本文檔結構信息與鏈接拓撲結構信息加以整合，提出了一般的聚類模型。

Pirolli等人[8]在1996年使用了網頁節點的入鏈和出鏈以及其他文檔信息來計算文檔的類別。他們將網頁文檔分為幾種類別，對于每個網頁計算其文檔大小、出鏈數、入鏈數、用戶點擊頻率等幾個特征，并且將其組織成這一網頁的特征向量v。不同的網頁文檔種類對不同的網頁特征有不同的權值wij。這些權值組成矩陣W。算法計算網頁的類型向量c=W×v，并可以根據c來判斷網頁類型。一個網頁可以同時屬于多種類型。

Chen[9]在1997年提出了一種一般化的相似度分析方法（generalised similarity analysis，GSA），用于整合超文本的內容信息、鏈接特征以及瀏覽模式。為了簡單起見，它沒有考慮節點的父節點和子節點的情況。Chen給出了一個比較復雜的用于文檔中詞的權重的計算公式，而且根據用戶的瀏覽模式給出了使用模式相似的計算公式。



Mukherjea[10]在2000年提出了一種同時利用結構和內容的交互式超文本聚類算法。在該模型中，用戶可以精確地描述他們的信息需求，而所有的節點都包含一些內容及其子圖結構的信息。但是，這種聚類的過程是半自動的。

2基于統計模型的方法

所有的傳統統計模型中都給出類條件獨立的樸素假定。給定樣本的類標號，假定屬性值相互條件獨立，即在屬性間不存在依賴關系。針對傳統的統計模型的不足，近年來研究人員提出了一些改進的方法，適用于解決對象之間的相關問題。這些方法是將統計的方法和數據的關系表示結合起來的一類算法。它關注數據的聯合概率分布。基于統計的算法往往因為需要優化的參數較多，計算開銷相對較大。本文介紹一種比較有代表性的C－H算法。

Cohn和Hoffman[11]在2001年提出了一個結合文檔內容和超鏈接的聯合概率模型聚類算法。該算法使用文檔內容和它的引用情況決定其主題。它是針對PLSA[12]和PHITS[13]算法中的不足提出的。PLSA算法只考慮文檔的文字內容，而忽略了文檔之間的鏈接信息；PHITS算法正好相反，沒有考慮文檔的文字內容信息，僅考慮文檔之間的鏈接信息。

由于PLSA和PHITS的概率模型中都有一個潛在的因子或主題z影響文檔d到c的一個鏈接，他們進一步假定，給定因子z，文檔c的條件分布P(c|z)存在，并且給定文檔d，因子z的條件分布P(c|z)也存在。而且PLSA和PHITS都使用了概率P(z|d)來進行分解，P(z|d)表示文檔d 取潛在類別主題z的概率，因此，Cohn和Hoffman合理地將兩種分析方法融合在一起，建立了一個聯合概率模型，用來描述文檔內容與文檔之間的鏈接信息。其聯合概率模型為

對給定每一個主題zk的條件下，存在文檔dl的鏈接條件概率P(cl|zk)和詞ti出現次數的條件概率P(ti|zk)。這個聯合概率模型的優點是從基本原理出發，將文檔內容與鏈接整合在一起。利用式（10）（11）構建了一個帶有相對權重α的對數似然函數（log－likelihood function）：

利用Dempster等人提出的EM（expectation maximization）[14]算法，通過對對數似然函數L求最大值的方法來得到參數估計。

在E步，使用每一組觀測到的數據得到潛在主題變量z的后驗概率。概率公式為

根據參數P(zk|dj)的最大值來確定每個文檔dj所屬的類zk，此聚類模型可以看做是一種無監督的貝葉斯分類器。此算法具有線性收斂速度。

此外，還有其他一些算法。Taskar等人[15]在2001年提出根據對象屬性和鏈接結構信息，使用概率關系模型（PRMs）去聚類關系數據。他們描述了對于關系數據聚類的概率模型；給定對象集與對象之間的關系集；概率關系模型對于對象的屬性定義了一個聯合概率分布。PRMs的優點是提出了一個簡潔的圖形化表示，在實現和學習上更有效。

Kubica等人[16]在2002年提出了一種基于圖中成員關系的關系生成概率模型。這種模型同時考慮了所有觀察到的聯系數據和實體的特征信息，通過極大似然的方式來估計模型參數，并給出了幾種啟發式搜索策略來優化參數。

3基于譜聚類的方法

譜聚類算法的思想來源于譜圖劃分理論。它將聚類問題看成是一個無向圖的多路劃分問題。定義一個有效的圖劃分判據——規范切判據（normalized cut）[17]。最優化這一判據使得同一類內的點具有較高的相似性，而不同類之間的點具有較低的相似性。由于圖劃分問題的組合本質，求圖劃分判據的最優解是一個NP難問題。一個很好的求解方法是將原問題轉換成求圖Laplace矩陣的譜分解。因此將這類方法統稱為譜聚類。可以認為譜分解是對圖劃分判據的逼近[18]。

He Xiao－feng等人[19]在2001年提出了一種在網頁集中自動獲取識別主題使用的譜圖分割算法。他們考慮了網頁之間的超鏈接結構、網頁的文本信息和引用關系，并給出了網頁之間相似性的度量方法。然后尋求規范切判據最小的分割點來劃分圖。規范切判據的定義為

c)求矩陣(D-W)y=λDy的第二個最小特征值對應的特征向量f 。

d)檢查f的N個空間分割點，找出滿足J(A，B)最小的切割點。

e)如果J(A，B)的值小于給定的閾值，則接受這種劃分。

此算法具有與譜聚類相同的優點和缺點。譜聚類可以對非凸形數據進行聚類，算法執行效果非常好，一般情況下運算速度比較快。算法的缺點是每一次分割必須把網絡分解成兩個部分，通過重復調用算法來完成多個社區的分割。由于不能判斷整個網絡被分解為多少個社區合適，算法很難達到滿意的分割效果。此算法的聚類過程是自動的。

4結束語

本文介紹的屬性—鏈接聚類已經成為當今一個非常具有挑戰性和前景性的研究領域，它可以提高聚類的準確性，比傳統的聚類方法更能體現社會網絡集團性質的實際意義。本文較為詳細地分析了幾種具有代表性的聚類算法的基本思想和具體實現的過程，并對算法的性能進行了評價。

目前，屬性—鏈接聚類主要集中在對超文本信息檢索、互聯網社區發現、實體識別等方面的研究，而對于其他的社會網絡如電力網絡、電信社群網、流行病學網絡、細胞與新陳代謝網絡等的研究相對較少。因此，對其他社會網絡的聚類研究將成為一個很好的研究方向。挖掘社會網絡中潛在的集團，并分析集團的特性，以便更好地解釋不同社會網絡的特征。

時間復雜性和準確性仍是大規模社會網絡的屬性—鏈接聚類算法面臨的兩個主要問題。如何針對不同類型網絡的特點，找到快速且可靠的網絡集團結構分析算法，仍然是今后需要解決的主要問題。

參考文獻：

［1］HAN Jia－wei，KAMBER M.Data mining:concepts and techniques[M].2nd ed.San Francisco:Morgan Kaufmann Publish，2005:556－557.

[2]GIRVAN M，NEWMAN M E J.Community structure in social and biological network [C]//Proc of National Academy of Science.2002:7821－7826.

[3]GETOOR L.Link mining:a new data mining challenge[C]//Proc ofACM SIGKDD Explorations.2003:84－89．

[4]NEVILLEJ，ADLER M，JENSEN D.Clustering relational data using attribute and link information[C]//Proc ofthe 18th International Joint Conference on Artificial Intelligence，Text Mining and Link Analysis Workshop.2003.

[5]WEISS R，VELEZ B，SHELDON M，et al.Hypursuit: a hierarchical network search engine that exploits contentlink hypertext clustering[C]//Proc ofthe 7th ACM Conference on Hypertext. Washington DC:[s.n.]，1996.

[6]MODHA D，SPANGLERW.Clustering hypertext with applications to Web searching [C]//Proc of the 11th ACM Conference on Hypertext and Hypermedia.2000.

[7]BHATTACHARYA I，GETOOR L.Iterative record linkage for cleaning and integration[C]//Proc of the 9th ACM SINGMOD Workshop on Research Issues on Data Mining and Knowledge Discovery. Paris:[s.n.]，2004:11－18．

[8]PIROLLI P，PITKOW J，RAO R.Silk from sow’s ear:extracting useable structures from the Web [C]//Proc of the CHI’96 Conference on Human Factors in Computing Systems.Vancouver: ACM Press， 1996:118－125.

[9]CHEN Chao－mei.Structuring and visualizing the WWW by generalized similarity analysis [C]//Proc ofthe 8th ACM Conference on Hypertext． Southampton: ACM Press， 1997:177－186.

[10]MUKHERJEA S.WTMS:a system for collecting and analyzing topic－specified Web information [C]//Proc of the 9th ACM－WWW International Conference.Amsterdam: ACM Press， 2000:457－471.

[11]COHN D，HOFMANN T.The missing link: a probabilistic model of document content and hypertext connectivity[C]//Proc ofAdvances in Neural Information Processing Systems．2000.

[12]HOFMANN T.Probabilistic latent semantic analysis[C]//Proc of the 15th Conference on Uncertainty in AI. 1999:289－296.

[13]COHN D，CHANG H.Learning to probabilistically identify authoritative documents [C]//Proc of the 17th International Conference on Machine Learning.2000．

[14]DEMPSTER A P，LAIRD N M，RUBIN D B.Maximum likelihood from incomplete data via the EM algorithm[J]. Journal of the Royal Statistical Society:Series B(Methodological)，1997，39(1):1－38.

[15]TASKAR B，SEGAL E，KOLLER D.Probabilistic clustering in relational data[C]//Proc of the 17th International Joint Conference on Artificial Intelligence.2001:870－887.

[16]KUBICA J，MOORE A，SCHNEIDER J，et al.Stochastic link and group detection[C]//Proc of the 18th National Conference on Artifical Intelligence.2002:798－804.

[17]SHI Jian－bo，MALIK J.Normalized cuts and image segmentation[J].IEEE Trans on Pattern Analysis and Machine Intelligence，2000，22(8):888－905.

[18]GU Ming，ZHA Hong－yuan，DING C，et al.Spectral relaxation models and structure analysis for k－way graph clustering and bi－clustering，Technical Report CSE－01－007[R].Pennsylvania:Department of Computer Science and Engineering， Pennsylvania State University，2001．

[19]HE Xiao－feng， DING C H Q，ZHA Hong－yuan，et al.Automatic topic identification using webpages clustering [C]//Proc of IEEE Int’l Conf on Data Mining． San Jose:[s.n.]，2001:195－202．

注：本文中所涉及到的圖表、注解、公式等內容請以PDF格式閱讀原文