本節書摘來自華章出版社《異構資訊網絡挖掘： 原理和方法(1)》一書中的第2章，第2.3節，作者［美］孫藝洲（yizhou sun）韓家炜（jiawei han），更多章節内容可以通路雲栖社群“華章計算機”公衆号檢視
我們解決的第二項聚類任務是針對包含更多類型的對象和連結、更一般性的異構資訊網絡，對各個類型對象實作軟聚類。在異構資訊網絡中，具有星型網絡模式的網絡普遍存在且重要，例如以論文為中心的文獻網絡（例26），以帶标簽事件為中心的标簽網絡（例如，http：//deliciouscom）。事實上，任何n元關系集合，例如關系資料庫的記錄可以映射到一個星型網絡，其中關系中每條元組都是中心對象，所有屬性實體與之相連。
例26(星型文獻資訊網絡)
一個文獻網絡包含了豐富的研究成果發表資訊，并由論文（d）、作者（a）、術語（t）、刊物（v）這四種類型的節點構成。從語義上講，每篇論文都由一組作者撰寫，使用一組術語，發表在某個刊物（會議或期刊）。作者與論文之間的連結有“寫”與“被寫”關系，論文與術語之間的連結有“含有”和“被含有”的關系，刊物與論文之間的連結有“發表”和“被發表”的關系。圖28的左半部分示例了一個文獻網絡的拓撲結構，該結構形成了一個以論文為中心，其他類型（稱為屬性類型）對象通過論文連接配接在一起的星型網絡模式。網絡記為
g=（，，w），其中=a∪v∪t∪d，連結〈xi，xj〉的權值wxixj定義如下：
定義27給定資訊網絡g=（，，w）擁有t+1種類型對象（即={xt}tt=0），若g滿足e=〈xi,xj〉∈,xi∈x0∩xj∈xt(t≠0)，則被稱為帶有星型網絡模式，反之亦然。稱g為星型網絡，類型x0是中心類型（也稱為目标類型），類型xt（t≠0）為屬性類型。
與傳統聚類定義不同，我們提出netclus來檢測包含多種類型對象，滿足初始網絡模式（每個對象可以柔性地屬于多個聚類）的網絡聚類。例28給出了一個網絡聚類的例子。
例28(資料庫領域的網絡聚類)
資料庫領域的網絡聚類包含了一組資料庫刊物、作者、術語、論文，以及這些對象術語資料庫領域的（非平凡）機率。相應地，我們可以給屬性對象（如刊物、作者、術語等）一個在其類型中的排名分數。根據排名分布，使用者可以輕易地獲知領域中的重要對象。表25列出了在dblp四個領域（資料庫、資料挖掘、資訊檢索和人工智能）（參見235節）的20個刊物子網絡，使用netclus所得到的“資料庫”領域中排名靠前的刊物、作者和術語。
netclus被設計用于帶有星型網絡模式的異構網絡。與rankclus的思想一樣，netclus也是一個基于排名的疊代方法，即利用排名提升聚類。與rankclus不同的是：隻要網絡是星型的，netclus能夠處理任意數量的類型對象，而且産生的聚類結果也不是對單個類型對象的集合，而是具有相同拓撲結構的輸入網絡的子網絡集合。對于一個給定的星型網絡和指定的聚類數量k。netclus輸出k個網絡聚類結果（見圖28）。每個網絡聚類都是一個代表網絡社群概念的子層，它是由聚集的目标對象所生成的網絡，并且附帶了每個對象的統計資訊。
計算兩兩對象間的相似性非常耗時并且難以在異構網絡中定義，取而代之，netclus将每個目标對象從中心類型映射為一個k維向量，其中k是使用者設定的聚類數目。對于每個網絡聚類中目标對象的機率生成模型是基于排名的，該模型将一個網絡聚類分解為t個獨立的成分，其中t是屬性類型的數目。在這一節，我們使用例26介紹的星型文獻網絡來闡述netclus算法。
在221節，我們介紹了排名函數，現在我們将重新審視兩個處理帶星型網絡模式的文獻網絡的排名函數，并闡述兩個用于簡單
3(屬性)類型星型網絡的排名方法的性質。
1簡單排名
簡單排名就是對每個對象根據其類型歸一化後簡單地統計出現次數。給定網絡g，每個對象的屬性類型的排名分布定義如下：
其中，x是類型tx的一個對象，ng（x）是x在g中的鄰居集合。例如，在文獻網絡中，對刊物使用簡單排名計算的排名分數成比例于論文發表數量。
2權威排名
對每個對象進行權威排名實質上是一個考慮對象權威性在整個網絡中傳播的排名函數。與雙類型資訊網絡不同，我們需要考慮排名分數在異構資訊網絡中某條路徑上的傳播。對于一個一般性的星型網絡g，從類型x通過中心類型z到類型y的權威分數傳播的定義如下。
其中，wxy和wzx是兩個相對應的對象類型間的權重矩陣，必要時可以進行歸一化。總的來說，一個對象類型的權值分數可能由不同對象類型的分數組合得到。例如poprank［51］中提出的方法。已有研究表明，通過選擇網絡中的一條遊走路徑（或多條路徑的組合）計算排名分布的疊代方法是計算表示特定類型對象兩兩間強度的方陣的主特征向量的有力工具。關于該路徑更系統化的定義請參見第4章有關基于元路徑的概念。
在dblp資料集中，依據規則：（1）排名靠前的刊物接受了很多排名靠前的作者的論文；（2）排名靠前的作者在排名靠前的刊物發表了很多好論文，我們定義如下疊代式。
其中，為了歸一化，dda和ddv是對角值與wda和wdv行之和相等的對角陣。歸一化意味着如果一篇論文有多個作者，在計算刊物的排名分數時，就應該考慮這些作者的平均排名分數。由于所有這些矩陣都是稀疏的，在實際操作時，對象的排名分數僅需要根據它有限個數的鄰居進行疊代計算。
3內建先驗知識于排名函數
在這兩個排名函數中，可以內建特定類型對象中不同聚類的先驗分布。例如，使用者可能給出幾個具有代表性的對象作為先驗知識，例如每個研究領域的術語和刊物。先驗給定的類型x表達為pp（x|tx，k） (k=1，2，…，k)的形式。首先，先驗在網絡中按個性化的pagerank［86］方式将分數傳播給先驗範圍以外的對象。然後，傳播的先驗與由給定排名函數計算得到的排名分布在參數λp∈［0,1］下線性結合在一起，λp值越大，最終的條件排名分布越依賴于先驗。
首先，我們介紹netclus的總體架構，并在随後章節詳細介紹算法的每個部分。給定聚類數目k，netclus算法的總體思想由以下步驟構成。
步驟0：産生目标對象的初始劃分，并根據這些劃分生成初始網絡聚類，即{c0k}kk=1。
步驟1：對每個網絡聚類建構基于排名的機率生成模型，即{p(x|ctk)}kk=1。
步驟2：計算每個目标對象的後驗機率（p(ctk|x)），然後根據聚類後驗機率定義的新評價來調整對象的聚類配置設定。
步驟3：重複步驟1和步驟2直到所有聚類都不再有顯著變化。即，{c*k}kk=1={ctk}kk=1={ct-1k}kk=1。
步驟4：計算每個網絡聚類中各個屬性對象的後驗機率（p(c*k|x)）。
總的來說，netclus的時間複雜度與網絡中連結個數（||）線性相關。當網絡非常稀疏時——大多數應用的真實情況，時間複雜度與網絡中對象個數近似線性相關。
根據現有研究［4；20；50］，在許多真實網絡中節點的連結是有偏的，這意味着一個度越高（即高出現頻率）的對象被連結的機率越高，高出現頻率的對象也容易與更多對象相連結。如在dblp資料集中，764%的高産作者發表了全部論文的742%，其中5672%的論文在862%的刊物發表，這說明大量的刊物和高産作者通過論文連在一起。我們使用代表對象在網絡中重要性的排名分數替代對象的度來擴充獲得的啟發。符合這個直覺的例子有：被很多低排名網頁所連結的（高的度但低排名）網頁不大有機會獲得來自真正重要網頁的連結，在低級别刊物發表許多論文，不會提高這個作者在頂級刊物發表論文的機率。
基于這個觀測，我們提出目标對象的機率生産模型來簡化網絡結構，其中排名高的屬性對象更可能共同出現來産生一個中心對象。為了解釋這個想法，我們使用星型文獻資訊網絡作為一個執行個體來示範模型是如何發揮作用的。我們假設每種類型中不相同的對象的數目分别為|a|、|v|、|t|和|d|，每個類型對象的集合記為：a={a1，a2，…，a|a|}，v={v1，v2，…，v|v|}，t={t1，t2，…，t|t|}，以及d={d1，d2，…，d|d|}。
為了簡化含有多種類型對象的複雜網絡，我們嘗試将不同類型的屬性對象的影響進行因子分解，然後對目标對象的生成行為模組化。對網絡因子分解的主要思想是：假設給定網絡g，不同屬性類型通路對象的機率互相獨立。同時，另一個獨立性假設：在相同類型對象間，通路不同對象的機率互相獨立：
p（xi，xj|tx，g）=p（xi|tx，g）×p（xj|tx，g）
其中，xi，xj??tx并且tx是某個屬性類型。
現在，給定屬性對象在網絡g中的排名分布，我們來建立目标對象的生成模型。繼續以文獻網絡為例，每篇論文di由多個作者完成，在一個刊物發表，其題目包含了多個術語。是以，論文di由多個屬性對象，記為xi1,xi2,…,xini所确定，其中ni是di連結的數目。論文di的生成機率等于以邊的權值為出現次數生成這些屬性對象的機率。基于我們所做出的獨立性假設，在網絡g中生成論文di的機率定義如下。
其中，ng（di）是對象di在網絡g中的鄰居，tx表示對象x的類型。直覺地，如果一篇論文發表的刊物、作者、題目包含的術語以很高的機率屬于一個聚類，那麼這篇論文也有很高的機率屬于該聚類。
一旦獲得了每個網絡聚類的生成模型，我們就可以計算每個目标對象的後驗機率。現在的問題是假設我們知道了聚類
k（k=1，2，…，k）中每個目标對象的生成機率，那麼由聚類k生成的後驗機率是多少？這裡，k是使用者設定聚類數量。由于一些目标對象可能不屬于任何網絡聚類，我們對每個目标對象計算k+1個後驗機率而不僅是k個，其中前k個後驗機率是對每個真實存在的網絡聚類c1，c2，…，ck計算的，最後一個實際是對初始網絡g計算的。現在，g中的目标對象的生成模型充當了一個隐藏模型，與任何聚類都不相關的目标對象在隐藏模型中會得到一個大的後驗機率。這一節，我們将介紹計算目标對象和屬性對象的後驗機率的方法。
根據目标對象的生成模型，目标類型為d的目标對象d在子網絡gk的生成機率由子網屬性類型的條件排名分布計算得到：
其中，ngk(d)表示子網gk中對象d的鄰域。在式（213）中，為了避免條件排名分數中機率為0的情況，每個條件排名分數首先使用全局排名進行平滑：
其中，參數λs表示從全局排名中使用排名分布的程度。
平滑［82］是資訊檢索中一個常用的技術。在語言模型中使用平滑的原因之一是解決文檔中術語缺失導緻的0機率問題。當使用基于排名的生成模型計算目标對象的生成機率時，我們會遇到類似的問題。例如，網絡聚類中的一篇論文可能連結了該聚類中多個排名分數為0的對象。如果我們簡單地将目标對象在這個聚類中的機率賦為0，我們會丢失由其他對象提供的資訊。事實上，在聚類過程的初始階段，對象很可能被配置設定到錯誤的聚類，如果我們不使用平滑技術，就很難将這些對象重新分到正确聚類中。
一旦在輸入網絡g有了聚類，記為c1，c2，…，ck，我們可以很容易地根據貝葉斯規則：πi,k∝p(di|k)×p(k)，計算每個目标對象（論文di）的後驗機率，其中πi，k是在目前給定生成模型下，論文di由聚類k生成的機率，p（k）表示聚類k的相對大小，即論文屬于聚類k的機率，其中k=1，2，…，k，k+1。
為了獲得每個聚類k的可能聚類規模p（k），我們選擇使得對數似然最大化的聚類規模p（k）來生成整個論文集合，然後使用em算法獲得p（k）的局部最大。
我們利用如下兩個疊代公式，通過em算法獲得p（k），設定初始值
當計算好每個聚類ck中的目标對象的後驗機率，每個目标對象d可以被表示為一個k維向量：v→(di)=(πi,1,πi,2,…,πi,k)。每個聚類ck的中心可以表示為聚類中所有目标對象在新評價下的平均向量。接下來，我們計算每個目标對象和每個聚類中心的餘弦相似度，并且将目标對象配置設定給最近的聚類中心。現在，目标對象隻屬于一個聚類，如果di被劃分到聚類k，則令p（k|di）為1，反之為0。一個新的子網gk可以由目前屬于聚類k的目标對象生成。整個調整是一個疊代過程，直到目标對象的聚類标簽在目前評估下不再有顯著的變化。注意，當我們評價目标對象時，我們沒有使用隐藏模型的後驗機率。我們這麼做有兩個原因：首先，隐藏模型後驗機率的絕對值不應該影響目标對象之間的相似性；其次，前k個後驗機率之和反映了一個對象對确定聚類中心的重要性。
屬性對象x∈a∪v∪t的後驗機率可由如下式子計算得到：
這說明了一個刊物屬于聚類ck的機率等于在這個刊物上發表論文的平均後驗機率，對作者和其他屬性對象也有類似性質。
我們研究netclus的有效性并将之與幾個最先進的基準算法進行比較。
資料集我們依據例26從dblp中建構了星型文獻網絡。對兩個不同規模的網絡開展研究：一個是較大（“全領域”）的資料集，覆寫了dblp中所有的刊物、作者、論文和術語；另一個較小的（從dblp提取的）資料集，包含了來自資料庫、資料挖掘、資訊檢索以及人工智能這4個領域的20個刊物。（這個資料集也被稱為“四領域”資料集）網絡中包含了所有在這20個刊物上發表過論文的作者、所有發表的論文以及出現在論文标題中的術語。通過使用“四領域”資料集，我們可以比較不同方法的聚類準确性。
案例學習首先，我們展示在“全領域”資料集上發現的網絡聚類的排名分布。我們對刊物和作者使用權威排名，并将刊物的類型視為已知資訊，聚類數目為8。表26展示了其中4個網絡聚類。同樣，可以對子網絡疊代地使用netclus算法來生成更精細的網絡聚類。表27列出了從資料庫子網絡中提取的關于xml領域的精細網絡聚類中排名最靠前的5個作者。
排名函數研究在231節，我們提出了兩種排名方法，分别是簡單排名和權威排名。這裡，我們研究從排名分布中獲得的低次元評價是如何提高聚類結果，以及聚類結果如何又反過來提高該評價（圖29）。在本研究中，術語由簡單排名方法來排名，刊物和作者由權威排名或簡單排名（兩種不同的設定）來進行排名。
第一，我們對各個屬性類型x計算每個條件排名分布和全局排名分布之間的平均kl散度avgkl（x），用以測量不同條件排名分布之間的相似度：
第二，為了評價在采用排名函數f時每一輪聚類結果的品質，我們計算目前聚類下類内相似度與類間相似度的平均比值作為緊密度cf來進行評價：
第三，我們跟蹤目标對象在每輪疊代中聚類結果的準确性，定義如下：
換句話說，我們計算被正确聚類的論文的百分比。然而，即便隻是在“四領域”資料集中，|d|值也很大，是以我們随機地人工标注了100篇論文到4個聚類，并使用這些論文來計算準确性。
第四，我們跟蹤了聚類疊代中生成模型的對數似然式（215）。如圖29所示，權威排名在各種評價下都優于簡單排名。
準确性研究在這一節，我們将我們的算法與另外兩個算法進行比較。一個算法是僅使用文檔術語資訊的主題模型算法plsa［25］；另一個算法是隻适用于雙類型網絡的rankclus算法。因為這兩種算法都不可以直接用于星型模式的異構資訊網絡，我們對網絡進行必要的簡化。對于plsa，僅用網絡中的術語類型和論文類型，并且使用netclus中同樣的術語先驗知識。表28列出了對論文進行聚類的結果的準确性。
由于rankclus隻能對刊物聚類，我們以刊物聚類的準确性來作比較。對于netclus，聚類标簽依最大後驗機率獲得，并采用标準化互資訊（nmi）來評價準确性。因為大多數作者隻發表了很少的論文，并且其中可能有不利于正确聚類刊物的噪聲，是以我們對rankclus設定不同的門檻值來篩選作者子集合。表29給出了結果，其中，d（a）>n意味着我們選擇了有超過n篇論文發表的作者來建構雙類型文獻網絡。所有結果都基于算法20次運作。
可以看出，随着網絡中對象類型的增多，netclus的執行結果比另外兩種隻使用了網絡部分資訊的算法更好。