附加問題與算法課件

1、聚類分析：附加的問題與算法第9章聚類分析：附加的問題與算法目錄數(shù)據(jù)、簇和聚類算法的特征基于原型的聚類基于密度的聚類基于圖的聚類（重點）可伸縮的聚類生物學(xué)應(yīng)用（重點）比較k均值和DBSCANK均值聚類所有對象，而DBSCAN丟棄噪聲對象。K均值使用簇的基于原型的概念，而DBSCAN基于密度的概念。DBSCAN可以處理不同大小和形狀的簇。K均值不能。DBSCAN不太受噪聲的影響K均值時間復(fù)雜度是O（m），而DBSCAN的時間復(fù)雜度是O（m2）。K均值可以用于稀疏的高維數(shù)據(jù)。DBSCAN不對數(shù)據(jù)的分布做任何假定。k均值假定簇來自球形高斯分布。K均值可以發(fā)現(xiàn)不是明顯分離的簇，但是DBSCAN會合并有重

2、疊的簇。DBSCAN產(chǎn)生相同的結(jié)果，而k均值通常使用隨機初始化質(zhì)心，不會產(chǎn)生相同的結(jié)果。DBSCAN自動地確定簇個數(shù)；對于k均值，簇個數(shù)需要作為參數(shù)指定。對聚類分析有很強影響的數(shù)據(jù)特性高維性維度增加，體積迅速增加。除非點的個數(shù)也增加，否則密度將趨向于0.處理該問題的一個方法是使用維歸約技術(shù)規(guī)模如何處理大型數(shù)據(jù)集稀疏性稀疏數(shù)據(jù)通常由非對稱的屬性組成，其中零值沒有非零值重要。噪聲和離群點可能降低聚類算法的性能，特別是基于原型的算法屬性和數(shù)據(jù)集類型不同的近鄰性和密度度量適合于不同類型的數(shù)據(jù)。尺度不同的屬性，如高度和重量，可能用不同的尺度度量。簇特性數(shù)據(jù)分布不同形狀、大小和密度無明顯分離的簇當(dāng)簇接觸或

3、重疊模糊聚類可以處理這一問題簇之間的聯(lián)系在大部分聚類技術(shù)中，都不考慮簇之間的聯(lián)系，如簇的相對位置自組織映射（SOM）。子空間簇簇可能只在維（屬性）的一個子集中存在。聚類算法的一般特征次序依賴性簇的質(zhì)量和個數(shù)可能因數(shù)據(jù)處理的次序不同而顯著地變化。如SOM非確定性每次運行產(chǎn)生不同的結(jié)果。變換聚類問題到其他領(lǐng)域?qū)⒕垲悊栴}映射到一個不同的領(lǐng)域。如，基于圖的聚類可伸縮性數(shù)據(jù)集大時，聚類算法能應(yīng)對。不能總是假定數(shù)據(jù)放在內(nèi)存。這樣的算法對于大型數(shù)據(jù)集是不可行的。參數(shù)選擇選擇合適的參數(shù)值可能是困難的；因此，通常的態(tài)度是“參數(shù)越少越好”。將聚類作為最優(yōu)化問題處理聚類常常被看作優(yōu)化問題。將點劃分成簇，根據(jù)用戶指定

4、的目標函數(shù)度量，最大化結(jié)果簇集合的優(yōu)良度。如k均值試圖發(fā)現(xiàn)簇的集合，使得每個點到最近的簇質(zhì)心距離的平方和最小。目錄數(shù)據(jù)、簇和聚類算法的特征基于原型的聚類基于密度的聚類基于圖的聚類（重點）可伸縮的聚類生物學(xué)應(yīng)用（重點）基于原型的聚類模糊聚類（難點）使用混合模型的聚類自組織映射模糊簇1965年，Lotfi Zadeh引進模糊集合論（fuzzy set theory）和模糊邏輯（fuzzy logic）。模糊集合論允許對象以0和1之間的某個隸屬度屬于一個集合，而模糊邏輯允許一個陳述以0和1之間的確定度為真。假定我們有一個數(shù)據(jù)點的集合X=x1,x2,xm，其中每個點xi是一個n維點，即xi=（xi1,

5、xi2,xin) 。模糊簇集C1,C2,Ck是X的所有可能模糊子集的一個子集。每個點xi和每個簇Cj，隸屬權(quán)值（度）wij已經(jīng)賦予0和1之間的值。模糊偽劃分（fuzzy psuedo-partition）給定點xi的所有權(quán)值之和為1：每個簇Cj以非零權(quán)值至少包含一個點，但不以權(quán)值1包含所有的點模糊c均值算法：FCM算法9.1 基本模糊c均值算法選擇一個初始模糊偽劃分，即對所有的wij賦值Repeat 使用模糊偽劃分，計算每個簇的質(zhì)心 重新計算模糊偽劃分，即wijUntil 質(zhì)心不發(fā)生變化計算質(zhì)心更新模糊偽劃分例子：三個圓形簇上的模糊c均值優(yōu)點與局限性FCM產(chǎn)生指示任意點屬于任意簇程度的聚類。K

6、均值可以看作FCM的特例。它比K均值算法計算復(fù)雜性高。除此之外，它與k均值算法具有相同的優(yōu)點和缺點?；谠偷木垲惸：垲悾y點）使用混合模型的聚類自組織映射混合模型的聚類算法估計數(shù)據(jù)分布：確定分布：一般假設(shè)數(shù)據(jù)取自高斯混合分布。然后，對分布的參數(shù)進行估計：利用EM算法進行最大似然估計利用直方圖估計分布對分布進行劃分、分離。每個分布對應(yīng)于一個簇。例子簇1簇2優(yōu)點和缺點混合模型比k均值或模糊c均值更一般，因為它可以使用各種類型的分布。利用簡單的估計分布的方法（如直方圖）可能會錯誤估計數(shù)據(jù)的原始分布，導(dǎo)致結(jié)果不好。利用復(fù)雜的方法（如EM算法），計算復(fù)雜性會大大增加。基于原型的聚類模糊聚類（難點）使

7、用混合模型的聚類自組織映射自組織映射Kohonen自組織特征映射（SOFM或SOM）是一種基于神經(jīng)網(wǎng)絡(luò)觀點的聚類和數(shù)據(jù)可視化技術(shù)。盡管SOM源于神經(jīng)網(wǎng)絡(luò)，但是它可以表示成一種基于原型聚類的變形。與其他基于質(zhì)心的聚類技術(shù)一樣，SOM的目標是發(fā)現(xiàn)質(zhì)心的集合，并將數(shù)據(jù)集中的每個對象指派到提供該對象最佳近似的質(zhì)心。用神經(jīng)網(wǎng)絡(luò)的術(shù)語，每個質(zhì)心都與一個神經(jīng)元相關(guān)聯(lián)。SOM算法初始化質(zhì)心。Repeat 選擇下一個對象 確定到該對象最近的質(zhì)心 更新該質(zhì)心和附近的質(zhì)心，即在一個特定鄰域 內(nèi)的質(zhì)心Until 質(zhì)心改變不多或超過某個域值指派每個對象到最近的質(zhì)心，并返回質(zhì)心和簇使用SOM胚胎發(fā)育過程聚類SOM-SVD

8、 聚類目錄數(shù)據(jù)、簇和聚類算法的特征基于原型的聚類基于密度的聚類基于圖的聚類（重點）可伸縮的聚類生物學(xué)應(yīng)用（重點）基于密度的聚類基于網(wǎng)格的聚類（重點）子空間聚類DENCLUE例子基于網(wǎng)格的聚類算法（重點）定義一個網(wǎng)格單元集將對象指派到合適的單元，并計算每個單元的密度刪除密度低于指定的閾值的單元由鄰近的稠密單元形成簇定義網(wǎng)格單元和密度（重點）定義網(wǎng)格單元對于連續(xù)屬性，定義網(wǎng)格單元相當(dāng)于連續(xù)屬性離散化。網(wǎng)格單元的密度該區(qū)域中的點數(shù)除以區(qū)域的體積。如果使用具有相同體積的網(wǎng)格單元，使得每個單元的點數(shù)直接度量單元的密度。優(yōu)點與局限性算法運行速度較快，可達o(mlogm)。這使得它成為許多聚類算法的基礎(chǔ)，如

9、STING、GRIDCLUS、waveCluster、Bang-Clustering、CLIQUE和MAFIA。網(wǎng)格單元形狀選擇影響聚類效果。如矩形網(wǎng)格單元不能準確地捕獲圓形邊界區(qū)域的密度。不適合高維數(shù)據(jù)。密度閾值的選擇對算法效果影響較大。如圖9-10和表9-2，如果密度閾值為9，則大簇的4個部分將丟失?；诿芏鹊木垲惢诰W(wǎng)格的聚類（重點）子空間聚類DENCLUECLIQUE算法找出每個屬性的一維空間的所有稠密區(qū)域。K2Repeat 由稠密的k-1維單元產(chǎn)生候選稠密k維單元 刪除點數(shù)少于域值的單元 kk+1Until 不存在候選稠密k維單元通過取鄰接的、高密度的單元的并發(fā)現(xiàn)簇CLIQUE的優(yōu)點

10、與局限性CLIQUE最大特點是，它提供了一種搜索子空間發(fā)現(xiàn)簇的有效技術(shù)。由于這種方法基于關(guān)聯(lián)分析的先驗原理，它的性質(zhì)能夠被很好地解釋。CLIQUE的局限性與其他基于密度的方法和Apriori算法相同。如，CLIQUE發(fā)現(xiàn)的簇可以共享對象。允許簇重疊可能大幅度增加簇的個數(shù)，并使得解釋更加困難。Apriori具有指數(shù)級的復(fù)雜度?；诿芏鹊木垲惢诰W(wǎng)格的聚類（重點）子空間聚類DENCLUE基于密度聚類的一種基于核的方案DENCLUE(DENsity CLUstEring)算法對數(shù)據(jù)點占據(jù)的空間推導(dǎo)密度函數(shù)識別局部最大點（即密度吸引點）通過沿密度增長最大的方向移動，將每個點關(guān)聯(lián)到一個密度吸引點與特定的

11、密度吸引點相關(guān)聯(lián)的那些點構(gòu)成簇丟棄密度吸引點的密度小于閾值的簇合并通過密度大于或等于閾值的點路徑連接的簇核密度估計核密度估計用函數(shù)描述數(shù)據(jù)的分布。每個點對總密度函數(shù)的貢獻用一個核函數(shù)表示?？偯芏群瘮?shù)僅僅是與每個點相關(guān)聯(lián)的核函數(shù)之核高斯函數(shù)常用作核函數(shù)：基于網(wǎng)格的技術(shù)來處理該問題DENCLUE的優(yōu)點與局限性DENCLUE具有堅實的理論基礎(chǔ)（核密度函數(shù)和核密度估計）。因此，提供了比其他基于網(wǎng)格的聚類技術(shù)和DBSCAN更加靈活、更加精確的計算密度的方法。（DBSCAN是DENCLUE的特例）基于核函數(shù)的方法是計算昂貴的，但DENCLUE使用基于網(wǎng)格的技術(shù)來處理該問題。盡管如此，DENCLUE比其他基

12、于密度的聚類計算開銷更大。DENCLUE具有其他基于密度的方法的優(yōu)缺點。目錄數(shù)據(jù)、簇和聚類算法的特征基于原型的聚類基于密度的聚類基于圖的聚類（重點）可伸縮的聚類生物學(xué)應(yīng)用（重點）基于圖的聚類稀疏化最小生成樹聚類OPOSSUMChameleonJarvis-Patrick聚類算法基于SNN密度的聚類稀疏化m個數(shù)據(jù)點的mm鄰近度矩陣可以用一個稠密圖表示，每個節(jié)點與其他所有點相連，權(quán)值反映鄰近性。盡管每個對象與其他每個對象都有某種程度的近鄰性，但是對于大部分數(shù)據(jù)集，對象只與少量對象高度相似，而與大部分其他對象的相似性很弱。這一性質(zhì)用來稀疏化鄰近度圖。稀疏化可以這樣進行：斷開相似度低于指定閾值的邊、或

13、僅保留連接到點的k個近鄰的邊。稀疏化是聚類算法的初始化步驟。m個數(shù)據(jù)點的mm鄰近度矩陣可以用一個稠密圖表示，每個節(jié)點與其他所有點相連，權(quán)值反映鄰近性。稀疏化可以這樣進行：斷開相似度低于指定閾值的邊、或僅保留連接到點的k個近鄰的邊。稀疏化的好處壓縮了數(shù)據(jù)量可以更好的聚類降低了噪聲和離群點的影響，增強了簇之間的差別。可以使用圖劃分算法基于圖的聚類稀疏化最小生成樹聚類OPOSSUMChameleonJarvis-Patrick聚類算法基于SNN密度的聚類最小生成樹聚類（minimum spanning tree，MST）計算相異度圖的最小生成樹Repeat 斷開對應(yīng)于最大相異度的邊，創(chuàng)建一個新的簇U

14、ntil 只剩下單個簇最小生成樹聚類它是一種基于分裂的層次聚類算法它可以看作用稀疏化找出簇的方法基于圖的聚類稀疏化最小生成樹聚類OPOSSUMChameleonJarvis-Patrick聚類算法基于SNN密度的聚類OPOSSUM：使用METIS的稀疏相似度最優(yōu)劃分OPOSSUM（Optimal Partitioning of Sparse Similarities Using METIS）是一種專門為諸如文檔或購物籃數(shù)據(jù)等稀疏、高維數(shù)據(jù)設(shè)計的聚類技術(shù)。OPOSSUM聚類算法1：計算稀疏化的相似度圖2：使用METIS，將相似度圖劃分成k個不同的分支（簇）METIS圖劃分程序?qū)⑾∈鑸D劃分為k個不

15、同的分支，其中k是用戶指定的參數(shù)，旨在（1）最小化分支之間邊的權(quán)值（2）實現(xiàn)平衡約束。OPOSSUM使用如下兩種約束中的一種：（1）每個簇中的對象個數(shù)必須粗略相等，或（2）屬性值的和必須粗略相等。優(yōu)點與缺點OPOSSUM簡單、速度快。它將數(shù)據(jù)劃分大小粗略相等的簇。根據(jù)聚類的目標這可能看作優(yōu)點或缺點。它類似于Chameleon聚類過程的初始化步驟?；趫D的聚類稀疏化最小生成樹聚類OPOSSUMChameleonJarvis-Patrick聚類算法基于SNN密度的聚類聚類難題Closeness schemes will merge (a) and (b)(a)(b)(c)(d)Average co

16、nnectivity schemes will merge (c) and (d)Chameleon算法構(gòu)造k-最近鄰圖使用多層圖劃分算法劃分圖Repeat 合并相對互連性和相對接近性，最好 地保持自相似性的簇Until 不再有可以合并的簇確定合并哪些簇相對接近度（relative closeness，RC）：mi和mj分別是簇ci和cj的大小。SEC(ci,cj)是連接簇ci和cj的邊的平均權(quán)值；SEC(ci)是二分簇ci的邊的平均權(quán)值；EC表示割邊；簇中的點之間的接近程度幾乎與原來的每個簇一樣。相對互連度（relative interconnectivity, RI）：其中，EC(Ci,C

17、j)是連接簇Ci和Cj的邊之和；EC(Ci)是二分簇Ci的割邊的最小和；EC(Cj)是二分簇Cj的割邊的最小和。簇中的點之間的連接幾乎與原來的每個簇一樣強，兩個簇合并。聚類效果聚類效果優(yōu)點與局限性Chameleon是一種凝聚聚類技術(shù)，它將數(shù)據(jù)的初始劃分與一種新穎的層次聚類方案相結(jié)合。使用接近性和互連性概念以及簇的局部建模。關(guān)鍵思想是：僅當(dāng)合并后的結(jié)果簇類似于原來的兩個簇時，這兩個簇才合并。Chameleon能夠有效地聚類空間數(shù)據(jù)，即便存在噪聲和離群點，并且簇具有不同的形狀、大小和密度。當(dāng)劃分過程未產(chǎn)生子簇時，chameleon有問題，對于高維數(shù)據(jù)，常常出現(xiàn)這種情況?；趫D的聚類稀疏化最小生成樹

18、聚類OPOSSUMChameleonJarvis-Patrick聚類算法基于SNN密度的聚類共享最近鄰相似性SNN（shared nearest neighbor）SNN相似度計算：找出所有點的k-近鄰If 兩個點x和y不是相互在對方的k-最近鄰中 then similarity(x,y) 0Else similarity(x,y)共享的近鄰個數(shù)End ifijij4消除對象碰巧接近和處理變密度！SSN相似度特點能處理一個對象碰巧與另一對象相對接近，但屬于不同的類。在這種情況下，對象一般不共享許多近鄰，SNN相似度低。能處理變密度簇的問題。一對點之間的SNN相似度只依賴于兩個對象共享的最近鄰的

19、個數(shù)。Jarvis-Patrick（JP）聚類算法計算SNN相似度圖使用相似度閾值，稀疏化SNN相似度圖找出稀疏化的SNN相似度圖的連通分支優(yōu)點與局限性因為JP聚類基于SNN相似度概念，它擅長于處理噪聲和離群點，并且能夠處理不同大小、形狀和密度的簇。該算法對高維數(shù)據(jù)效果良好。JP聚類脆弱：它把簇定義為SNN相似度圖的連通分支,數(shù)據(jù)對象集分裂成兩個簇還是作為一個簇留下，可能依賴于一條鏈?；趫D的聚類稀疏化最小生成樹聚類OPOSSUMChameleonJarvis-Patrick聚類算法基于SNN密度的聚類基于SNN密度的聚類算法：計算SNN相似度圖以用戶指定的參數(shù)Eps和MinPts，使用DBS

20、CAN聚類例子：解釋該算法處理高維數(shù)據(jù)能力SNN Clusters of SLP.SNN Density of Points on the Globe.41年期間，在2.5度的經(jīng)緯度網(wǎng)格的每個點上的月平均海平面氣壓（SLP）優(yōu)點與局限性基于SNN密度的聚類的優(yōu)點與局限性類似于JP聚類。SNN聚類算法比JP聚類或DBSCAN更加靈活。它可以用于高維數(shù)據(jù)和簇具有不同密度的情況。不象JP聚類簡單地使用域值，然后取連通分支作為簇，基于SNN密度的聚類使用基于SNN密度和核心點概念的方法。習(xí)題稀疏化的好處OPOSSUM聚類算法中重要一個步驟是稀疏化，敘述該稀疏化方法Chameleon算法使用接近性和互連

21、性概念以及簇的局部建模。關(guān)鍵思想是：使用_和_概念，僅當(dāng)合并后的結(jié)果簇_原來的兩個簇時，這兩個簇才合并。Jarvis-Patrick（JP）聚類算法首先計算_圖，然后使用相似度閾值，稀疏化該圖找出稀疏化圖的連通分支。基于SNN密度的聚類不象JP聚類簡單地使用域值，然后取_作為簇，基于SNN密度的聚類使用基于SNN密度和_方法。SNN密度的優(yōu)勢。目錄數(shù)據(jù)、簇和聚類算法的特征基于原型的聚類基于密度的聚類基于圖的聚類（重點）可伸縮的聚類生物學(xué)應(yīng)用（重點）CURE如果運行時間長得不可接受，或者需要的存儲量太大，即使最好的聚類算法也沒有多大價值?？缮炜s性可以通過如下技術(shù)實現(xiàn)：多維或空間存取方法抽樣劃分數(shù)

22、據(jù)對象匯總并行與分布計算CURE算法由數(shù)據(jù)集抽取一個隨機樣本集。將樣本集劃分成p個大小相同的劃分。使用層次聚類算法，將每個劃分中的點聚類成m/pq個簇，得到總共m/q個簇。（注：簇增長緩慢，刪除離群點）使用層次聚類算法對上一步發(fā)現(xiàn)的m/q個簇進行聚類，直到只剩下k個簇。（注：刪除離群點）將所有剩余的數(shù)據(jù)點指派到最近的簇。K是期望的簇個數(shù)，m是點的個數(shù)，p是劃分的個數(shù)，而q是一個劃分中的點的期望壓縮CURE層次聚類CURE使用簇中的多個代表點來表示一個簇。第一個代表點選擇離簇中心最遠，而其余點選擇離所有已經(jīng)選取的點最遠的點。以因子a向簇中心收縮。減輕離群點的影響。兩個簇之間距離是任意兩個代表點之

23、間的最短距離。如果a=0，基于質(zhì)心的層次聚類；a=1時，它與單鏈層次聚類大致相同。目錄數(shù)據(jù)、簇和聚類算法的特征基于原型的聚類基于密度的聚類基于圖的聚類（重點）可伸縮的聚類生物學(xué)應(yīng)用（重點）目錄生物分子網(wǎng)絡(luò)連通組分模塊基于hub的模塊完全圖模塊介數(shù)中心性聚類BCC模塊化測度最大化模塊化測度的聚類CPM模塊社會網(wǎng)絡(luò)的K-clique模塊生物分子網(wǎng)絡(luò)轉(zhuǎn)錄調(diào)控網(wǎng)絡(luò)蛋白質(zhì)網(wǎng)絡(luò)代謝網(wǎng)絡(luò)信號轉(zhuǎn)導(dǎo)網(wǎng)絡(luò)蛋白質(zhì)互作網(wǎng)絡(luò)酵母雙雜交（Yeast Two Hybrid，Y2H） 蛋白質(zhì)互作網(wǎng)絡(luò)蛋白質(zhì)互作數(shù)據(jù)庫1. BIND數(shù)據(jù)庫 http:/bind.ca/ 主要記錄蛋白質(zhì)互作在內(nèi)的生物分子間的相互作用信息，并將其中的

24、信息分為經(jīng)過人工檢查的可信信息和高通量數(shù)據(jù)信息。 代謝網(wǎng)絡(luò)和信號轉(zhuǎn)導(dǎo)網(wǎng)絡(luò)代謝通路 是指細胞中代謝物在酶的作用下轉(zhuǎn)化為新的代謝物過程中所發(fā)生的一系列生物化學(xué)反應(yīng)。信號轉(zhuǎn)導(dǎo) 是指細胞將一種類型的生物信號或刺激轉(zhuǎn)換為其它生物信號最終激活細胞反應(yīng)的過程。丙酮酸丙酮酸激酶2-磷酸甘油酸磷酸烯醇式丙酮酸烯醇化酶丙酮酸磷酸烯醇式丙酮酸丙酮酸激酶2-磷酸甘油酸磷酸烯醇式丙酮酸烯醇化酶1 0 ATPADP主要反應(yīng)物多個生物反應(yīng)的組合成代謝通路丙酮酸丙酮酸激酶2-磷酸甘油酸磷酸烯醇式丙酮酸烯醇化酶葡萄糖6-磷酸葡萄糖6-磷酸果糖1,6-雙磷酸果糖3-磷酸甘油醛1,3-二磷酸甘油酸3-二磷酸甘油酸Detail: h

25、ttp:/www.genome.jp/kegg-bin/show_pathway?org_name=rn&mapno=00010&mapscale=1.0&show_description=show磷酸化激活綁定/相關(guān)http:/www.genome.jp/kegg/pathway/hsa/hsa04010.html非代謝通路（信號轉(zhuǎn)導(dǎo)通路等）通過這些詳細的互作關(guān)系，我們能夠更清晰的了解通路！http:/www.genome.jp/kegg/document/help_pathway.htmlhttp:/www.genome.jp/kegg/xml/docs/Detail：結(jié)點間的各種關(guān)系泛素

26、化去磷酸化抑制激活磷酸化綁定/相關(guān)http:/www.genome.jp/kegg/pathway/hsa/hsa04630.html/ ERGOBioCyc/ GeneDB/ KEGG 其它通路數(shù)據(jù)庫：/ReactomeGWT/entrypoint.htmlReactomewikipathways/index.php/WikiPathwaysbiocarta/http:/www.genome.jp/kegg/代謝網(wǎng)絡(luò)和信號轉(zhuǎn)導(dǎo)網(wǎng)絡(luò)數(shù)據(jù)庫KEGG數(shù)據(jù)庫是關(guān)于基因、蛋白、生化反應(yīng)以及通路的綜合生物信息數(shù)據(jù)庫。 連通組分（connected components）模塊 模塊（module）；簇（c

27、luster）；社區(qū)（community）；子圖（subgraph）算法：計算圖的所有連通組分，即連通子圖。每個連通組分形成一個模塊。該網(wǎng)絡(luò)有兩個連通組分！案例：癌癥基因互作網(wǎng)絡(luò)的功能模塊分析從KEGG通路數(shù)據(jù)庫，獲得癌癥基因互作網(wǎng)絡(luò) 將網(wǎng)絡(luò)導(dǎo)入到cytocape網(wǎng)絡(luò)可視化分析軟件中選擇plugins-cluster-Connected components cluster點擊Create cluster按鈕，將得到結(jié)果顯示結(jié)果。選擇所有節(jié)點，點擊Data Panel，然后選cancer_gene_global_network.txt_CC_cluster選項。選擇：Connected com

28、ponents cluster點擊：greate clusters點擊Data Panel，然后選擇cancer_gene_global_network.txt_CC_cluster基于hub的模塊（Hub-based modules） 計算網(wǎng)絡(luò)中的每個節(jié)點的度定義度高于指定閾值（如：大于10）的節(jié)點為hub節(jié)點每個hub和與它距離小于d的節(jié)點形成一個模塊?；趆ub的模塊http:/biit.cs.ut.ee/graphwebGraphweb基于hub的模塊（Hub-based modules） 在蛋白質(zhì)網(wǎng)絡(luò)中的hub與致死性（lethality）有關(guān)，并且與相同的hub連接的蛋白質(zhì)一般具有

29、相似的功能。完全圖模塊（Cliques modules） 完全圖是每對節(jié)點都直接連接的圖。在蛋白質(zhì)網(wǎng)絡(luò)中的完全圖經(jīng)常對應(yīng)蛋白質(zhì)混合物和共同的功能。這種模塊也反應(yīng)了共表達基因的簇。介數(shù)中心性聚類BCC該方法也稱為GN算法，由Girvan和Newman開發(fā)而得名。算法：計算在網(wǎng)絡(luò)中的所有邊的介數(shù)。刪除最高介數(shù)的邊。重新計算網(wǎng)絡(luò)中的所有邊的介數(shù)。重復(fù)步驟2，3直到?jīng)]有任何邊存在。介數(shù)（betweenness）介數(shù)定義為： 有B，A，D，C，A，D，D，A，C，E以及它們的逆序路徑共6條最短路徑通過節(jié)點A，節(jié)點A的介數(shù)為6。模塊化（modularity） 一個好的劃分方案得到的結(jié)果應(yīng)該使得模塊內(nèi)的邊更多而模塊間的邊更少。如果最小化模塊間的連接（或最大化模塊內(nèi)的連接），那么最優(yōu)的劃分方案是形成一個單一模塊，那樣模塊間沒有任何連接。模塊化（modularity）測度能夠解決這個問題。 是模塊的數(shù)量，L表示在網(wǎng)絡(luò)中邊的數(shù)量， 代表在模塊s中的邊數(shù)量，