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

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

關(guān)鍵詞：屬性—鏈接聚類； 鏈接結(jié)構(gòu)； 聚類算法

中圖分類號：TP391文獻(xiàn)標(biāo)志碼：A

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

0引言

隨著信息技術(shù)的發(fā)展，越來越多的數(shù)據(jù)被收集和整合在一起，大規(guī)模異質(zhì)數(shù)據(jù)集不斷涌現(xiàn)，建立一個大的社會網(wǎng)絡(luò)成為可能。實(shí)際上，社會網(wǎng)絡(luò)是一個抽象概念，它并不一定必須是社會的[1]。在現(xiàn)實(shí)世界中，有許多科技、商業(yè)、經(jīng)濟(jì)和生物的社會網(wǎng)絡(luò)實(shí)例，包括電力網(wǎng)絡(luò)、萬維網(wǎng)、引用網(wǎng)絡(luò)、流行病學(xué)網(wǎng)絡(luò)、食物網(wǎng)絡(luò)等。

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

傳統(tǒng)的聚類算法認(rèn)為數(shù)據(jù)集是由同類、相互獨(dú)立、等概率分布的實(shí)體組成的[3，4]，只側(cè)重于研究單一實(shí)體屬性，而忽略實(shí)體間的相互作用關(guān)系，必然不能很好地從中發(fā)現(xiàn)知識。社會網(wǎng)絡(luò)數(shù)據(jù)顯然不滿足這樣的假設(shè)。因而，在對社會網(wǎng)絡(luò)數(shù)據(jù)進(jìn)行挖掘的過程中，必須注意同時考慮行動者的屬性及其與其他行動者之間的聯(lián)系。社會網(wǎng)絡(luò)數(shù)據(jù)中蘊(yùn)涵了大量的聯(lián)系信息，充分挖掘這些信息是數(shù)據(jù)挖掘的重要目標(biāo)。因而，不但不能簡單假設(shè)樣本是獨(dú)立的，還要充分利用這些聯(lián)系來建立更加準(zhǔn)確的模型。

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

屬性—鏈接聚類已經(jīng)成為目前比較熱門的研究領(lǐng)域，它彌補(bǔ)了傳統(tǒng)的基于屬性的聚類方法，忽略了結(jié)構(gòu)信息的弱點(diǎn)和基于圖的聚類算法，忽略了屬性信息的弱點(diǎn)。目前，屬性—鏈接聚類主要是針對超文本信息檢索、互聯(lián)網(wǎng)社區(qū)發(fā)現(xiàn)、實(shí)體識別等方面的研究。本文將把屬性—鏈接聚類方法大致分為基于相似度、基于概率模型和基于譜聚類三種方法。

1基于相似度的方法

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

1．2M－S算法

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

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

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

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

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

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

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

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

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

1．3距離相似算法

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

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

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

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))表示對象組集之間的距離；α是兩個相鄰對象之間的權(quán)重；G(r)表示對象r或它的副本r′所在的組的集合。

兩個組集G(ri)與G（rj）之間的距離是以兩個組g1與g2之間的距離為基礎(chǔ)的。為了計算兩個組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)稱為組細(xì)微距離。

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

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

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

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

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

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

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

此外，還有許多研究致力于將內(nèi)容信息、用戶瀏覽信息甚至超文本文檔結(jié)構(gòu)信息與鏈接拓?fù)浣Y(jié)構(gòu)信息加以整合，提出了一般的聚類模型。

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

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



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

2基于統(tǒng)計模型的方法

所有的傳統(tǒng)統(tǒng)計模型中都給出類條件獨(dú)立的樸素假定。給定樣本的類標(biāo)號，假定屬性值相互條件獨(dú)立，即在屬性間不存在依賴關(guān)系。針對傳統(tǒng)的統(tǒng)計模型的不足，近年來研究人員提出了一些改進(jìn)的方法，適用于解決對象之間的相關(guān)問題。這些方法是將統(tǒng)計的方法和數(shù)據(jù)的關(guān)系表示結(jié)合起來的一類算法。它關(guān)注數(shù)據(jù)的聯(lián)合概率分布。基于統(tǒng)計的算法往往因?yàn)樾枰獌?yōu)化的參數(shù)較多，計算開銷相對較大。本文介紹一種比較有代表性的C－H算法。

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

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

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

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

在E步，使用每一組觀測到的數(shù)據(jù)得到潛在主題變量z的后驗(yàn)概率。概率公式為

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

此外，還有其他一些算法。Taskar等人[15]在2001年提出根據(jù)對象屬性和鏈接結(jié)構(gòu)信息，使用概率關(guān)系模型（PRMs）去聚類關(guān)系數(shù)據(jù)。他們描述了對于關(guān)系數(shù)據(jù)聚類的概率模型；給定對象集與對象之間的關(guān)系集；概率關(guān)系模型對于對象的屬性定義了一個聯(lián)合概率分布。PRMs的優(yōu)點(diǎn)是提出了一個簡潔的圖形化表示，在實(shí)現(xiàn)和學(xué)習(xí)上更有效。

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

3基于譜聚類的方法

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

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

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

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

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

此算法具有與譜聚類相同的優(yōu)點(diǎn)和缺點(diǎn)。譜聚類可以對非凸形數(shù)據(jù)進(jìn)行聚類，算法執(zhí)行效果非常好，一般情況下運(yùn)算速度比較快。算法的缺點(diǎn)是每一次分割必須把網(wǎng)絡(luò)分解成兩個部分，通過重復(fù)調(diào)用算法來完成多個社區(qū)的分割。由于不能判斷整個網(wǎng)絡(luò)被分解為多少個社區(qū)合適，算法很難達(dá)到滿意的分割效果。此算法的聚類過程是自動的。

4結(jié)束語

本文介紹的屬性—鏈接聚類已經(jīng)成為當(dāng)今一個非常具有挑戰(zhàn)性和前景性的研究領(lǐng)域，它可以提高聚類的準(zhǔn)確性，比傳統(tǒng)的聚類方法更能體現(xiàn)社會網(wǎng)絡(luò)集團(tuán)性質(zhì)的實(shí)際意義。本文較為詳細(xì)地分析了幾種具有代表性的聚類算法的基本思想和具體實(shí)現(xiàn)的過程，并對算法的性能進(jìn)行了評價。

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

時間復(fù)雜性和準(zhǔn)確性仍是大規(guī)模社會網(wǎng)絡(luò)的屬性—鏈接聚類算法面臨的兩個主要問題。如何針對不同類型網(wǎng)絡(luò)的特點(diǎn)，找到快速且可靠的網(wǎng)絡(luò)集團(tuán)結(jié)構(gòu)分析算法，仍然是今后需要解決的主要問題。

參考文獻(xiàn)：

［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．

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