ＤＥＮＧＥＮＥ：一種高精度的基于密度的適用于基因表達數據的聚類算法

DENGENE:一種高精度的基于密度的適用于基因表達數據的聚類算法孫亮趙芳王永吉1中國科學院 軟件研究所 互聯網軟件技術實驗室， 北京 100080； 2.香港理工大學 計算學系 生物識別中心， 香港； 3.中國科學院 軟件研究所 計算機科學重點實驗室， 北京 100080； 4.中國科學院 研究生院， 北京 10004958，59，60，61，

摘要：根據基因表達數據的特點，提出一種高精度的基于密度的聚類算法DENGENE。DENGENE通過定義一致性檢測和引進峰點改進搜索方向，使得算法能夠更好地處理基因表達數據。為了評價算法的性能，選取了兩組廣為使用的測試數據，即啤酒酵母基因表達數據集對算法來進行測試。實驗結果表明，與基于模型的五種算法、CAST算法、K均值聚類等相比，DENGENE在濾除噪聲和聚類精度方面取得了顯著的改善。

關鍵詞：基因表達數據； 聚類分析； 基于密度的聚類； 一致性檢測； 峰點

中圖分類號：TP18； TP3016文獻標志碼：A

文章編號：10013695(2007)04005804

0引言

DNA微陣列技術(DNA Microarray Technology)的迅速發展導致了基因表達數據(Gene Expression Data)的爆炸性增長。因此有效地分析這些基因表達數據成為當前生物信息學面臨的主要問題之一。一般來講，基因表達數據是一個矩陣。矩陣的每一行代表一個基因的表達向量，即該基因在多種實驗條件下測得的表達數據;每一列對應于一種實驗條件下測得的所有基因的表達值。

目前，聚類分析已廣泛應用于基因表達數據分析中^[1]。聚類分析將表達模式相似的基因聚在一起，從而有助于基因的分析。①表達模式相似的基因具有相同的功能。從而能夠從屬于同一聚類的某些已知功能的基因推斷該聚類中其他基因的功能^[2]。②具有相似表達模式的基因更有可能處于相同的細胞過程中。因此聚類結果有助于基因轉錄調控網絡中調控機理的研究^[1]。

在對基因表達數據聚類時，必須充分考慮基因表達數據本身的特點。一般來講，對基因表達數據進行聚類分析時有如下特點：

（1）與數據挖掘中的聚類算法相比，在對基因表達數據進行處理時更關注于算法的有效性(Effectiveness)而非效率(Efficiency)。基因表達數據的規模一般為數千級或數萬級，完全可在主存中處理。注意，并不是說忽視效率，而是指在效率允許的情況下盡量提高算法精度。

（2）基因數據中存在大量噪聲，所以好的基因聚類算法必須能對噪聲具有很強的魯棒性。在基因表達數據分析中，聚類的目的并不是為了得到所有對象的相互關系(如層次聚類所作)，而是取得那些基本有用的數據，所以噪聲必須去除。

對基因表達數據進行處理時，要求算法能夠有效地濾除噪聲并取得高精度的聚類結果。

根據基因表達數據的以上特點，基于密度的聚類算法(Densitybased Clustering)是一種較好的解決方案。在數據挖掘領域中，已有大量的基于密度的聚類算法。其中以DBSCAN^[3]最為經典。此類方法能夠得到任意形狀的聚類，并且可以很方便地處理噪聲數據。但是DBSCAN最大的缺陷是要求指定全局密度閾值。當閾值過大時，僅能算出最主要的幾個聚類而將其他點視為噪聲；閾值過小時，又易于合并不應合并的聚類。在基因表達數據分析中，經常存在聚類相交或嵌入的情況，使得直接將DBSCAN應用于基因表達數據的效果并不理想。當使用DBSCAN處理一組該領域內經典的啤酒酵母基因表達數據^[2]時，如果密度閾值太小，則兩個主要的聚類，即具有糖酵解(Glycolysis)功能的聚類和具有蛋白質合成(Protein Synthesis)功能的聚類則會合并在一起；如果密度閾值較大，雖然能夠分開上述兩個聚類，但是大量其他基因均被當成噪聲濾除了。

本文根據基因表達數據的特點，提出了一種高精度的基于密度的聚類算法(Densitybased Clustering Using Homogeneity Test，DENGENE)。其基本思想如下：①用密度(Density)來勾勒數據分布的疏密程度，使之能夠合理地處理噪聲。②規定密度大于某一閾值的點為核心點(Core Point)。因為核心點是聚類的骨架，這樣算法能夠得到任意形狀的聚類。③DENGENE通過使用一致性檢測(Homogeneity Test)有效提高了聚類結果的精確度，克服了DBSCAN關于全局閾值的缺陷。④定義了峰點(Peak Point)，也就是密度比給定鄰域內點都大的核心點。聚類時不像DBSCAN一樣可從任意一個核心點出發，而是只能從峰點出發，且聚類的每次擴展均只能沿密度最大的方向進行擴展。

為了評價算法性能，選取了兩組在此領域內非常經典的啤酒酵母基因表達數據集^[2，4]來進行測試。由于啤酒酵母基因的功能已知，且其基因表達數據和功能都可在公共數據庫中得到，是廣為使用的測試數據。測試結果顯示DENGENE相比以往的算法性能有很大的提高。

1DENGENE算法

進行聚類處理的基因表達數據是一個m×n維矩陣X，它表示m個基因在n種不同條件下測得基因表達值，即每個基因可以認為是n維空間內的一個點，m個點組成集合D，點p和q的距離表示為dist(p， q)。

1.1基本思想

基于密度的聚類算法將聚類看成是數據空間中被低密度區域分割開的高密度區域。下面介紹DENGENE的主要思想。（1）DENGENE用密度來勾勒數據分布的疏密程度。有如下定義：

定義1(eps鄰域)點p的eps鄰域定義為Neps(p)={q∈D|dist(p，q)≤eps}

定義2(點的密度)對D中任意點p和距離eps，p的eps鄰域內的點數稱為點p基于距離eps的密度，記為density(p，eps)，即density(p，eps)=|Neps(p)|。在規定了eps時，可簡寫為density(p)。

（2）密度大于某一閾值t的點稱為核心點(Core Point)。使用核心點來代表聚類，從而能夠得到任意形狀的聚類。事實上，核心點是聚類的骨架。聚類時主要集中在核心點的處理上。對于非核心點，計算它到離它最近核心點的距離。如果大于鄰域半徑則視為噪聲；否則將它合并到離它最近核心點所對應的聚類中。這種利用骨架進行聚類擴展的原理使得基于密度的方法能夠得到任意形狀的聚類，即

定義3(核心點)對于給定的鄰域半徑eps，密度大于等于MinPts的點稱為核心點。

（3）DENGENE通過使用一致性檢測有效提高聚類結果的精確度。如前所述，在處理基因表達數據時，基于密度的算法的最大優點就是可以有效濾除噪聲。但是傳統的基于密度的算法(如DBSCAN)并不能滿足高精度的要求，在引言中也提到了DBSCAN處理典型的基因表達數據集的問題。這里用一個二維數據分布的簡單例子來說明這個問題，如圖1所示。圖1中有三個聚類C1、C2、C3。其中C1、C2的密度較大，C3的密度較小。當使用較大的全局密度閾值時，只有聚類C1和C2可以被檢測出來，C3則被視為噪聲；如果用較小的全局密度閾值使得C3能檢測出來，C1和C2則合并為一個聚類。這就是使用DBSCAN處理基因表達數據的常見問題。

DENGENE使用一致性檢測克服了上述缺陷，能夠精確地同時檢測出C1、C2和C3。當使用較小的密度閾值檢測出C3時，點P1也成為核心點。但是可以清楚看到，P1與相鄰聚類C1、C2的性質明顯不一樣。事實上可用一些指標來度量C1及C2的性質。由于P1～P3并不具有與C1、C2一致的性質，不應將P1～P3加入C1、C2中。這樣C1和C2就不會合并。這里將檢查新的核心點是否具有與要加入的聚類同一性質的措施，稱為一致性檢測。在具體實施一致性檢測時，首先要提取出能度量聚類一致性的具體指標。同時，為了更好地得到聚類性質，規定生成聚類時必須從密度較大的地方開始，再向密度較低的地方擴展，且每一步擴展均必須沿當前密度最大的方向。這樣能夠更加準確地獲取聚類的性質。事實上，在DENGENE框架下可有多種方式來定義聚類的一致性。下面列出兩種具體措施，并假設當前聚類為C，進行一致性測試的核心點為P。

措施1通過定義聚類的當前平均密度來度量一致性

①計算C的當前平均密度：

avDensity(C)=∑p∈Cdensity(p)/|C|

②如果density(P)≥α×avDensity(C)，則將P加入C中；否則不加入。這里α是系數，由用戶設定。

由于DENGENE是基于密度的算法，計算聚類C的平均密度簡單易行、計算復雜度低。α的值越小，則聚類擴張的區域越大，反之亦然。一般地，為了能夠擴張，要求α＜1。事實上α=0就是DBSCAN算法。在圖1的例子中，雖然P1在較小的密度閾值下成為核心點，但是它的密度值與C1、C2的平均密度值都相差甚遠，即P1不能通過一致性檢測，不應將P1合并到C1或C2中。這樣DENGENE得到了三個聚類：C1、C2和C3。

措施2通過考查核心點P的鄰域中已合并入C的點數來進行一致性檢測

①計算點P的eps鄰域中已合并入C的點數N。

②如果N/density(P)≥β，則將點P合并到C中；否則不予合并。這里β是系數，由用戶設定。

措施2的基本原理如下:根據密度的定義，density(P)實際上是點P的eps鄰域內的所有點的數目。由于聚類首先都是從最密的地方開始生成，如果P與C聯系較緊密，則P的鄰域中已有相當數量的點被合并入聚類C中。這里用β作為閾值(要求β<1)，β的值越小，則聚類擴張的區域越大，反之亦然。事實上β=0就是DBSCAN算法。

注意，DENGENE只在聚類擴展的過程中對新的核心點做處理時才進行一致性檢測。在具體使用DENGENE時，可采用措施1或2，或兩者并用。

（4）DENGENE定義了峰點，以適應新的搜索方式。峰點是密度比給定鄰域內的點都大的核心點。DENGENE從峰點開始進行聚類擴展，將相互距離小于eps且通過一致性檢測的核心點合并進該聚類中，完成骨架的聚類。如果沒有相應的核心點可再進行擴展，則結束該聚類的處理，轉入下一個聚類的處理。這樣有如下定義:

定義4(峰點)滿足以下兩個條件的點p稱為峰點：

①p是核心點;

②不存在核心點q使得density(q)>density(p)且q∈Nk(p)。Nk(p)是p的鄰域，用來確定峰點比較范圍。

峰點就是Nk(p)內密度最大的核心點。

1.2算法實現

這里用偽代碼來描述算法的具體實現：

算法首先設置好相關參數。其中參數MinPts和eps用來計算密度及確認核心點；Nk(p)用來確定峰點時的比較范圍(參見定義4)；α為進行一致性檢測的控制參數。D表示所有點組成的集合。D.size用來表示該集合中點的總數。算法為每個點計算了相應的eps鄰域，但必須先計算每對點之間的距離。其復雜度為O(m2)。由于數據規模不大，且每個點的eps鄰域所包含的點不多(一般只有幾個)，為每個點保存了其eps鄰域。clusterId用來存儲聚類結果：clusterId[k]=0表示基因k是噪聲，clusterId[k]=j(j＞0)表示基因k屬于第j個聚類。最初通過clusterId[all]=0將所有基因都初始化為0。clusterNo用來表示當前聚類的編號，coreList用來表示聚類擴張時核心點的集合。c=maxDensity(coreList)表示從coreList中找出密度最大的核心點c。homogeneity_test(c)表示對點c進行一致性檢測，結果為True表示通過，False表示沒有通過。

每次聚類都是從峰點出發，如果其已經被聚類則不予處理；否則將其加入coreList中。每步從coreList中取出密度最大的核心點作為當前處理的核心點，這樣保證了聚類的擴展始終沿著密度最大的方向進行。程序中將c視為當前處理的核心點，NC是c的eps鄰域，Nu表示NC中未處理的點，Nuc表示NC中未處理的核心點。程序將Nuc加入到coreList中，以便將來用于擴展聚類，并將當前核心點鄰域內所有未處理的點合并入當前聚類中。當沒有相應的可以擴張的核心點時則While循環結束，即該聚類完成，進入下一個聚類的處理中。

設D中核心點的數目為N，由于While循環每次執行從coreList中刪除一個核心點，While的執行次數最多為N。且由于記錄了每個點的eps鄰域，其計算復雜度很低。前面計算距離和各點的eps鄰域的復雜度是O(m2)，則算法總的復雜度是O(m2)。這里m是待處理的基因總數，這在處理基因表達數據時是可接受的。

2測試數據描述及算法性能評價

為了評價算法性能，采用了兩組廣為使用的啤酒酵母基因表達數據集對算法進行測試，并對DENGENE、K均值算法^[5]、基于模型的五種算法^[6]和CAST^[7]算法進行了性能比較。第一組數據含有大量噪聲，通過比較DENGENE和K均值算法對該組數據的處理，著重說明DENGENE對于噪聲的魯棒性;第二組數據所含噪聲較少但分類明確，通過比較DENGENE和基于模型的五種算法、CAST算法對該組數據的聚類結果，著重說明DENGENE所得的聚類結果的高精確度。在對基因表達數據的處理中，DENGENE的一致性檢測只采用了措施1，其控制參數為α。

2.1 測試數據描述

第一組數據是文獻[2]中使用的數據集，該數據集是2 467個基因在79種實驗條件下測得的表達數據。其中的基因都有相應的功能注解。該數據集可在http://genomewww.stanford.edu/clustering/下載。該數據集的特點是含有大量噪聲；其生物學特征是該數據集中存在大量基因；其功能與其他基因截然不同。換言之，將這些基因放到任何一個聚類中都沒有生物學上的顯著意義，所以可將其視為噪聲。

第二組數據集是文獻[4]中使用的數據集。本文使用的是文獻[6]中提取的一個注釋完全的子集。該組數據的特點是噪聲少且分類明確：它是384個在不同時間點達到峰值的基因，在17個時間點的基因表達數據。該數據集對應細胞周期的五個不同階段，因而可根據基因達到峰點所在細胞周期的不同將該子集劃分為五個聚類。由于該組數據的第10、11時間點的數據測量不可靠，通常的處理是將這些不可靠的數據刪去^[5]，以提高聚類效果。本文在預處理時也刪除這兩列。在http://www.cs.washington.edu/homes/kayee/model可下載這兩個子集。

為簡化起見，將第一個數據集合稱為Eisen2000，將第二個數據集稱為Cho384。

2.2實驗結果比較和分析

221Eisen2000數據

刪去Eisen2000數據集中表達值為空的基因，得到進一步處理的對象：605基因在79個時間點的表達值。

在使用DENGENE對Eisen2000進行處理時，設eps=15，MinPts=4，查找峰點的區域Nk半徑是Neps半徑(即eps)的06倍，α=07，得到10個聚類。在使用K均值算法對Eisen2000進行處理時，將聚類數目K設置為30。

本文著重分析兩種算法處理結果對應的生物學意義。在DENGENE生成的10個聚類中，聚類1基本上是蛋白質合成功能;聚類4全是染色質結構(Chromatin Structure)功能;聚類6基本上是糖酵解功能;聚類8是ATP合成(ATP Synthesis)及氧化磷酸化(Oxidative Phosphorylatio)功能;聚類9全是蛋白質降解(Protein Degradation)功能;聚類10全是蛋白質合成功能。其成功地找出了文獻[2]中用手工方法找出的聚類。而在K均值算法生成的30個聚類中，只有2個聚類中基因的功能大體相同。事實上，K均值算法得到的聚類中大部分被噪聲污染了，而DENGENE由于濾除了噪聲，得到的聚類基本上具有對應的生物學功能。

222Cho384和Cho237數據

由于已知Cho384和Cho237的真正分類結果，則可用修正的Rand指數(Adjusted Rand Index)^[8]來衡量算法的精確度。修正的Rand指數值越高，則聚類結果越接近真正的分類結果，算法的精確度越高。

圖2是基于模型的五種算法(包括EI、VI、VVV、Diagonal、EEE)^[6]對Cho384的聚類結果。文獻[9]通過比較層次聚類算法、K均值算法和CAST算法，認為CAST算法的性能最優。圖2中也列出了CAST算法。圖2的橫坐標是聚類的數目，縱坐標是修正的Rand指數值，每條曲線表示相應的算法性能。對于具體算法，使得其修正的Rand指數最大的聚類數目就是對該算法最合適的聚類數目。在圖2列出的各算法中，CAST算法和基于模型的算法EI表現最好，并在取6個聚類時得到最好的聚類結果，對應的修正Rand指數稍大于05。

由于在使用DENGENE時無須設置聚類數目，圖2中沒有列出DENGENE的性能曲線，而在圖3中給出了DENGENE處理Cho384的結果。圖3顯示了參數設置為eps＝01～02，MinPts=4～7，將Nk(p)設置為Neps(p)，α=07時的處理結果。圖3中的橫坐標是eps值，縱坐標是對應的修正Rand指數之值，四條不同的曲線對應于MinPts=4～7時的處理結果。圖3中DENGENE所得的聚類結果對應的修正Rand指數基本上都在045以上。最好的聚類結果是當eps=01，MinPts=5時，將Cho384分為5個聚類，其修正的Rand指數為0666。

通過圖2和3的比較，DENGENE相比基于模型的五種算法和CAST算法，聚類結果對應的修正Rand指數大為提高，充分顯示了DENGENE算法的高精確度。

2.3參數設置

一般的，eps的取值可以參照DBSCAN算法^[5]。結合基因表達數據處理的實際情況，MinPts=4～6均可滿足實際需要。在上述實驗中，一致性檢測的方式都是采取第一種措施，參數α=0.7都可以取得較好的效果。事實上由于聚類擴張時是從最密的地方開始，為了能夠順利擴張聚類，α的取值一般小于1。對于峰點半徑，一般取稍微小于eps即可。

3結束語

本文根據基因表達數據分析的特點，提出了一種高精度的基于密度的聚類算法DENGENE。算法從峰點出發進行聚類的擴展，同時引入同一性檢測以判定是否將當前核心點加入到當前聚類中。與已有的適用于基因表達數據的聚類算法相比，DENGENE能有效地從高噪聲的基因表達數據中提取出生物學信息，同時具有較高的精確度。在兩組經典的啤酒酵母基因表達數據集上的測試也證實了上述結論。

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