唐德玉，曹東，楊進(jìn)

（1.廣東藥科大學(xué)醫(yī)藥信息工程學(xué)院，廣州　510006；2.廣州中醫(yī)藥大學(xué)醫(yī)學(xué)信息工程學(xué)院，廣州　510006）

一種改進(jìn)初始中心點(diǎn)的FCM算法

唐德玉1，曹東2，楊進(jìn)1

（1.廣東藥科大學(xué)醫(yī)藥信息工程學(xué)院，廣州510006；2.廣州中醫(yī)藥大學(xué)醫(yī)學(xué)信息工程學(xué)院，廣州510006）

傳統(tǒng)FCM算法存在聚類初始中心點(diǎn)敏感及迭代次數(shù)多的缺點(diǎn)，提出一個(gè)改進(jìn)聚類初始中心點(diǎn)的加強(qiáng)FCM算法。新算法通過(guò)數(shù)據(jù)轉(zhuǎn)換及排序把數(shù)據(jù)劃分到合適的簇中，從而找到最好的聚類初始中心點(diǎn)。在給定聚類數(shù)目的條件下，通過(guò)UCI機(jī)器學(xué)習(xí)數(shù)據(jù)庫(kù)中的兩組數(shù)據(jù)集進(jìn)行實(shí)驗(yàn)比較，結(jié)果表明采用加強(qiáng)FCM算法比傳統(tǒng)FCM算法收斂速度更快，有較高的準(zhǔn)確率和穩(wěn)定性。

模糊C-均值；目標(biāo)函數(shù)；聚類初始點(diǎn)；數(shù)據(jù)劃分

廣東省財(cái)政專項(xiàng)“中醫(yī)藥防治重大疾病臨床科研信息一體化平臺(tái)建設(shè)項(xiàng)目”、廣東省自然基金項(xiàng)(2016A030310300）、基于協(xié)同智能優(yōu)化的藥物-靶標(biāo)相互作用預(yù)測(cè)方法研究

0　引言

K-Means算法是1967年由Mac Queen提出的聚類算法。K-Means方法是一個(gè)劃分方法，把數(shù)據(jù)劃分到K個(gè)組[1-2]。將模糊數(shù)學(xué)應(yīng)用到K-Means算法，從而發(fā)展到使用模糊理論的劃分方法，也就是目前很流行的模糊C-均值（簡(jiǎn)稱FCM）[7]聚類算法。該算法已經(jīng)應(yīng)用在數(shù)據(jù)挖掘、模式識(shí)別、計(jì)算機(jī)視覺(jué)、醫(yī)學(xué)圖像等領(lǐng)域，具有重要的理論與實(shí)際應(yīng)用價(jià)值。但是K-Means和FCM算法還存在很多共同的問(wèn)題亟待解決[8]。如聚類數(shù)目難確定，初始中心點(diǎn)敏感，迭代次數(shù)多，容易陷入局部極值，難以取得全局最優(yōu)。

針對(duì)上述問(wèn)題，有很多學(xué)者提出改進(jìn)K-Means算法初始中心點(diǎn)的方法[3-6]。而對(duì)于FCM算法也出現(xiàn)了很多解決方法。

張慧哲[9]等提出一種計(jì)算所有樣本點(diǎn)的距離，先找到最近的兩個(gè)樣本點(diǎn)的中心點(diǎn)做為第一個(gè)初始中心點(diǎn)，然后根據(jù)設(shè)置的閾值α，求大于α的所有樣本點(diǎn)距離，并求剩下樣本點(diǎn)的最小值，做為第二個(gè)中心點(diǎn)，重復(fù)下去，找到所有初始中心點(diǎn)。

匡泰[10]等人為了解決FCM算法初始點(diǎn)不確定，迭代次數(shù)多等問(wèn)題，提出了基于多項(xiàng)式確定初始中心點(diǎn)的算法，該算法的思想是把類中心看成是多項(xiàng)式的根，通過(guò)求多項(xiàng)式的解來(lái)確定初始中心點(diǎn)。

還有一些方法，例如采用模擬退火算法進(jìn)行全局優(yōu)化，首先產(chǎn)生一個(gè)初始解作為當(dāng)前解，然后在當(dāng)前解的領(lǐng)域中，以概率P（T）選擇一個(gè)非局部最優(yōu)解，并令這個(gè)解再重復(fù)下去，從而保證不會(huì)陷入局部最優(yōu)。開始時(shí)允許隨著參數(shù)的調(diào)整，目標(biāo)函數(shù)偶爾向增加的方向發(fā)展，以利于跳出局部極小區(qū)域。

也有使用遺傳算法提高FCM對(duì)高維數(shù)據(jù)的聚類效果，可以設(shè)置遺傳算法的適應(yīng)度函數(shù)f=1/（1+J）其中J為FCM目標(biāo)函數(shù)，采用編碼方式表示染色體為A= （a1，a2，a3，…，ac），其中ai為一個(gè)聚類中心。確定聚類中心數(shù)目，群的大小，交叉概率，突變概率，遺傳次數(shù)，計(jì)算隸屬度和目標(biāo)函數(shù)，求出適應(yīng)度函數(shù)。循環(huán)執(zhí)行三種遺傳操作：復(fù)制，交叉，突變。直到最后獲得最佳聚類中心。該方法可以獲得近似全局解。但其缺點(diǎn)是常?！斑^(guò)早收斂”，不能保證完全獲得最優(yōu)解，而且執(zhí)行時(shí)間比較長(zhǎng)。

此外有根據(jù)樣本點(diǎn)與聚類中心相似關(guān)系加權(quán)提高FCM準(zhǔn)確性的方法，其思想是根據(jù)相似性理論，為每一個(gè)樣本加一個(gè)特殊權(quán)值讓不同的樣本在聚類中心中起不同的作用。并對(duì)歐氏距離加權(quán)。使用合并函數(shù)求最大聚類數(shù)，其思想是提出一個(gè)合并函數(shù)，使得（c-1）類的類中心依賴于c類的類中心。保證FCM算法相對(duì)穩(wěn)定，執(zhí)行速度比普通FCM算法稍快，但不是很明顯。給出的方法，算法過(guò)于復(fù)雜，不適合大數(shù)據(jù)量應(yīng)用。

1　傳統(tǒng)FCM模糊聚類算法

給定數(shù)據(jù)集：X={x1，x2，…，xn}，其中每個(gè)樣本xi包含d個(gè)屬性。

模糊聚類就是要將X劃分為c個(gè)類（簇）（2≤c≤n），v={v1，v2，…，vc}為c個(gè)聚類中心。在模糊劃分中，每一個(gè)樣本不能嚴(yán)格地被劃分到某一類（簇），而是以一定的隸屬度屬于某一類（簇）。令U=（uij），i=1，2，…，n，j=1，2，…，c為隸屬度矩陣。

FCM算法基于求解下面的目標(biāo)函數(shù)的最小值：

其中m是任意一個(gè)大于等于2的實(shí)數(shù)，uij是在j簇中心的隸屬度，是第i樣本點(diǎn)，vj是簇的中心。

為了獲得Jm最小值，運(yùn)用Lagrange乘數(shù)法求極值，得：

對(duì)于（1）式，其中vj為第j個(gè)聚類中心點(diǎn)，||xi-vj||表示樣本點(diǎn)xi到中心點(diǎn)vj的歐氏距離。顯然，對(duì)于樣本點(diǎn)xi到第j個(gè)聚類中心vj距離越近，則uij越大。且滿足如下條件：

算法的執(zhí)行步驟如下：

1.初始化U=[uij]矩陣，U（0）.

2.在第k步：使用U（k）計(jì)算中心向量V（k）=[vj]，由（2）算得。

3.更新U（k），獲得U（k+1）。Uij由公式（1）算得。

2　提出的算法

傳統(tǒng)FCM算法是隨機(jī)產(chǎn)生[0，1]的隸屬度矩陣，根據(jù)隸屬度使用公式（2）找到初始中心點(diǎn)。由于初始中心點(diǎn)是隨機(jī)產(chǎn)生的，所以傳統(tǒng)FCM算法迭代次數(shù)比較多，當(dāng)數(shù)據(jù)比較多時(shí)，算法執(zhí)行很慢。為此我們提出一個(gè)加強(qiáng)FCM（enhancing FCM，以下簡(jiǎn)稱eFCM算法）聚類算法。該方法是找到最好的初始中心點(diǎn)，改進(jìn)算法的時(shí)間復(fù)雜度，并提高算法的準(zhǔn)確性。

基本思路是計(jì)算數(shù)據(jù)集中所有樣本點(diǎn)與樣本原點(diǎn)的距離，把數(shù)據(jù)集中所有樣本點(diǎn)與樣本原點(diǎn)的距離排序。然后把所有排好序的數(shù)據(jù)樣本點(diǎn)平均劃分到K個(gè)子集。在這K個(gè)子集中的中間樣本點(diǎn)做為該集合的初始中心點(diǎn)。這些初始中心點(diǎn)會(huì)產(chǎn)生更好的唯一的聚簇結(jié)果。排序的算法我們考慮用快速排序算法，因?yàn)榭焖倥判蛩惴ㄔ谧顗暮妥詈们闆r下，平均時(shí)間復(fù)雜度為O （NlogN）。

首先我們檢查數(shù)據(jù)集中數(shù)據(jù)有沒(méi)有負(fù)值[17]，如果數(shù)據(jù)集中沒(méi)有負(fù)值，那我們不需要數(shù)據(jù)轉(zhuǎn)換；但如果這個(gè)數(shù)據(jù)集里有負(fù)值，那么我們必須把數(shù)據(jù)集里所有數(shù)據(jù)的負(fù)值轉(zhuǎn)換到正值空間里。轉(zhuǎn)換的方法是先找到數(shù)據(jù)集中所有屬性中的數(shù)據(jù)的最小值（負(fù)值），然后讓數(shù)據(jù)集中所有數(shù)據(jù)減去最小值。這個(gè)轉(zhuǎn)換是必須的，因?yàn)槲覀兲岢龅倪@個(gè)算法，就是要計(jì)算數(shù)據(jù)集所有樣本點(diǎn)與坐標(biāo)樣本原點(diǎn)的距離。對(duì)于不同的數(shù)據(jù)樣本點(diǎn)，我們可以獲得幾乎不同的距離。如圖1中a），可以看出在二維空間中四個(gè)點(diǎn)（x1，y1），（x2，y2），（x3，y3），（x4，y4）在四個(gè)象限中，四個(gè)點(diǎn)與原點(diǎn)（0，0）的距離幾乎相等；而數(shù)據(jù)進(jìn)行轉(zhuǎn)換后，四個(gè)點(diǎn)全部放在第一象限。此時(shí)，四個(gè)點(diǎn)與原點(diǎn)（0，0）的距離明顯不同。

圖1　數(shù)據(jù)轉(zhuǎn)換

雖然歐氏距離對(duì)球形結(jié)構(gòu)聚類有一定的優(yōu)勢(shì)，但在解決高緯數(shù)據(jù)問(wèn)題時(shí)，存在一些計(jì)算上的弊端。而馬氏（Mahalanobis）距離計(jì)算僅涉及協(xié)方差矩陣的求逆，不再和特征矢量的維數(shù)有關(guān)，而是和樣本數(shù)目有關(guān)，因此在高緯特征空間中帶來(lái)計(jì)算上的優(yōu)勢(shì)，在無(wú)窮維特征空間中解決了計(jì)算上存在的問(wèn)題。所以我們?cè)谶M(jìn)行數(shù)據(jù)劃分時(shí)，采納馬氏距離計(jì)算樣本原點(diǎn)與數(shù)據(jù)樣本的距離，然后平均劃分為K個(gè)子集。

下一步，求初始中心點(diǎn)。加強(qiáng)FCM算法步驟如下：

輸入：

D={x1，x2，x3，…，xi，…，xm}//m個(gè)樣本數(shù)據(jù)點(diǎn)

d={d1，d2，d3，…，di，…，dn}//一個(gè)樣本數(shù)據(jù)點(diǎn)的n個(gè)屬性k//需要的簇的數(shù)目

輸出：k個(gè)初始中心點(diǎn)

步驟如下：

1.給定的數(shù)據(jù)集D，如果包括負(fù)值和正值的屬性值，那么程序跳轉(zhuǎn)到2，否則跳轉(zhuǎn)到4。

2.找到數(shù)據(jù)集D中屬性值的最小值。

3.數(shù)據(jù)集D中的所有數(shù)據(jù)點(diǎn)的值減去最小值。

4.使用馬氏距離計(jì)算所有樣本點(diǎn)與樣本原點(diǎn)的距離。

5.根據(jù)第4步獲得的距離進(jìn)行排序。

6.把排好序的數(shù)據(jù)點(diǎn)分成K個(gè)相等的子集合。

7.在每個(gè)子集中找到離樣本原點(diǎn)距離為中等的樣本點(diǎn)做為該子集的聚類初始中心點(diǎn)。

8.根據(jù)獲得的聚類初始中心點(diǎn)使用公式（1）計(jì)算隸屬度。

9.根據(jù)獲得的隸屬度使用公式（2）計(jì)算新的聚類中心點(diǎn)。

10.計(jì)算目標(biāo)函數(shù)值，并計(jì)算誤差，如果誤差小于閾值，程序結(jié)束。否則跳到8。

3　仿真模擬實(shí)驗(yàn)

為了驗(yàn)證提出的算法的有效性和準(zhǔn)確性，我們使用UCI機(jī)器學(xué)習(xí)中的Iris和Wine數(shù)據(jù)進(jìn)行仿真實(shí)驗(yàn)，然后對(duì)傳統(tǒng)FCM算法和eFCM算法進(jìn)行比較。實(shí)驗(yàn)源數(shù)據(jù)表如表1：

表1　數(shù)據(jù)源信息

本文實(shí)驗(yàn)環(huán)境是，處理器頻率為2.10GHz，內(nèi)存3G，硬盤120G，使用Windows XP 32位操作系統(tǒng)。開發(fā)工具使用MATLAB 7.8。實(shí)驗(yàn)初始化參數(shù)如下：隸屬度指數(shù)expo=2.0，簇?cái)?shù)目clustern=3，迭代最大數(shù)目maxiter=100，目標(biāo)函數(shù)值誤差最小閾值為minimpro=1e-6。我們對(duì)Iris和Wine數(shù)據(jù)先對(duì)歸一化處理，以減少量綱不同對(duì)算法的影響。使用公式Y(jié)=（Ymax-Ymin）*（X -Xmin）/（Xmax-Xmin）+Ymin，X為數(shù)據(jù)原始樣本值，Y為數(shù)據(jù)規(guī)范化后的數(shù)據(jù)，我們使用Ymin=0，Ymax=1，使所有數(shù)據(jù)落在[0，1]范圍內(nèi)。

為了保證實(shí)驗(yàn)的準(zhǔn)確性，我們對(duì)傳統(tǒng)FCM算法做了7次實(shí)驗(yàn)，計(jì)算算法的迭代次數(shù)，運(yùn)行時(shí)間及準(zhǔn)確率的平均值。而對(duì)eFCM算法做了7次實(shí)驗(yàn)，計(jì)算運(yùn)行時(shí)間的平均值。

表2　傳統(tǒng)FCM算法與eFCM算法的比較

從表2中結(jié)果可以看出，我們提出的eFCM算法的準(zhǔn)確率高于普通FCM算法。Iris數(shù)據(jù)集和Wine數(shù)據(jù)集都有類標(biāo)號(hào)，每個(gè)數(shù)據(jù)集分為3個(gè)類（簇）（見表1）。準(zhǔn)確性的計(jì)算就是用聚類算法產(chǎn)生的三個(gè)簇中的樣本與已知的三個(gè)類（簇）中的樣本類別進(jìn)行比較，計(jì)算聚類產(chǎn)生的簇中正確分類的樣本總數(shù)。準(zhǔn)確率=同一簇中正確分類的樣本總數(shù)/同一簇已有樣本總數(shù)。比如，見表3，對(duì)于Iris數(shù)據(jù)集中的分類1（簇1），同一簇已有樣本總數(shù)=50，F(xiàn)CM聚類產(chǎn)生的同一簇中正確分類的樣本總數(shù)=46，其準(zhǔn)確率為46/50約為92%;eFCM聚類產(chǎn)生的同一簇中正確分類的樣本總數(shù)=50，其準(zhǔn)確率為50/50等于100%。總的準(zhǔn)確率=所有簇中正確分類的樣本總數(shù)/所有簇中已有樣本總數(shù)（見表2）。

對(duì)于模糊C-Means算法而言，目標(biāo)值越小，說(shuō)明聚類的越好。傳統(tǒng)FCM算法產(chǎn)生的第一個(gè)初始聚類中心點(diǎn)與穩(wěn)定后的聚類中心點(diǎn)有很大偏離；eFCM算法產(chǎn)生的第一個(gè)初始聚類中心點(diǎn)與最后的聚類中心點(diǎn)接近，所以目標(biāo)值也很小。對(duì)于IRIS數(shù)據(jù)集中從圖2和圖3可以看出，F(xiàn)CM算法產(chǎn)生的第一個(gè)目標(biāo)值（4.5112），而eFCM算法的第一個(gè)目標(biāo)值（0.6811）。對(duì)于Wine數(shù)據(jù)集中，F(xiàn)CM算法產(chǎn)生的第一個(gè)目標(biāo)值（0.21），而eFCM算法的第一個(gè)目標(biāo)值（0.0843）。這也說(shuō)明eFCM算法選擇的初始中心點(diǎn)的有效性。加強(qiáng)的eFCM算法比傳統(tǒng)的FCM算法相比，數(shù)據(jù)樣本分類的準(zhǔn)確率有所提高，簇與簇之間的分類清晰，簇內(nèi)數(shù)據(jù)樣本更加緊湊，聚類效果更好。如表3可見eFCM算法對(duì)3個(gè)類正確分類的能力有提高。

表3　傳統(tǒng)FCM算法與eFCM算法的比較

特別是eFCM算法的運(yùn)行速度很快。對(duì)于Iris數(shù)據(jù)加強(qiáng)FCM算法只需要迭代7次，而傳統(tǒng)FCM算法要迭代15次；對(duì)于Wine數(shù)據(jù)，eFCM算法只需要迭代12次，而傳統(tǒng)FCM算法要迭代20次。使用MATLAB畫圖顯示了兩個(gè)算法目標(biāo)函數(shù)的迭代情況。如圖2和圖3。

圖2　Iris數(shù)據(jù)FCM算法和eFCM算法的迭代情況

圖3　Wine數(shù)據(jù)FCM算法和eFCM算法的迭代情況

最后，我們對(duì)于傳統(tǒng)FCM和eFCM算法的時(shí)間復(fù)雜度進(jìn)行分析，對(duì)于傳統(tǒng)FCM算法來(lái)說(shuō)，最大迭代次數(shù)需要循環(huán)maxiter次，隸屬度計(jì)算需要執(zhí)行clustern*datan*datam次循環(huán)，中心點(diǎn)計(jì)算也要執(zhí)行clustern*datan*datam次循環(huán)，目標(biāo)函數(shù)是計(jì)算所有樣本與中心點(diǎn)的距離，要執(zhí)行clustern*datan*datam次循環(huán)。所以總的執(zhí)行時(shí)間為O（maxiter*clustern*datan*datam）。而目標(biāo)函數(shù)的誤差值小于指定最小值時(shí)，程序可以在小于maxiter次循環(huán)停止。由于傳統(tǒng)FCM算法初始中心點(diǎn)是隨機(jī)產(chǎn)生的，所以要找到最佳的聚類中心點(diǎn)，迭代次數(shù)一般都比較多，很多情況下是要maxiter次迭代，而這是循環(huán)執(zhí)行最多的情況。而對(duì)于我們提出的eFCM算法在執(zhí)行時(shí)間要O（miniter*clustern*datan *datam），其中miniter<

4　結(jié)語(yǔ)

FCM算法也是目前很流行的聚類算法，但FCM算法由于初始中心點(diǎn)是隨機(jī)產(chǎn)生的，使得FCM算法執(zhí)行比較慢，準(zhǔn)確性也有所降低。我們提供的eFcm算法與傳統(tǒng)FCM算法相比，更加高效和準(zhǔn)確。該方法找到最好的初始中心點(diǎn)，把所有的樣本數(shù)據(jù)點(diǎn)分配到合適的簇中。而這個(gè)數(shù)據(jù)劃分機(jī)制所需要時(shí)間復(fù)雜度僅為O （NlogN），eFCM算法的時(shí)間復(fù)雜度為O（miniter*clustern*datan*datam），miniter<

[1]A.M.Fahim，A.M.Salem，F(xiàn).A.Torkey，M.A.Ramadan.An Efficient Enhanced K-Means Clustering Algorithm.Journal of Zhejiang University，10（7）:1626-1633，2006.

[2]K.A.Abdul Nazeer，M.P.Sebastian.Improving the Accuracy and Efficiency of the K-Means Clustering Algorithm.In International Conference on Data Mining and Knowledge Engineering（ICDMKE），Proceedings of the World Congress on Engineering（WCE-2009），Vol 1，July 2009，London，UK.

[3]Chen Zhang，Shixiong Xia.K-Means Clustering Algorithm with Improved Initial Center.in Second International Workshop on Knowledge Discovery and Data Mining（WKDD），pp.790-792，2009.

[4]F.Yuan，Z.H.Meng，H.X.Zhangz，C.R.Dong.A New Algorithm to Get the Initial Centroids.Proceedings of the 3rd International Conference on Machine Learning and Cybernetics，pp.26-29，August 2004.

[5]Koheri Arai,Ali Ridho Barakbah.Hierarchical K-Means:an Algorithm for Centroids Initialization for K-Means.Department of Information Science and Electrical Engineering Politechnique in Surabaya，F(xiàn)aculty of Science and Engineering，Saga University，Vol.36，No.1，2007.

[6]S.Deelers and S.Auwatanamongkol.Enhancing K-Means Algorithm with Initial Cluster Centers Derived from Data Partitioning along the Data Axis with the Highest Variance.International Journal of Computer Science，Vol.2，Number 4.

[7]Bezdek J C.Pattem Recogition with Fuzzy Objective Function Algorithms[M].NY:Plenum，1981.

[8]Duda R，HartP，Stork D.Pattern Classification（2 nd Edition）[M].New York，USA;John Wiley&Sons，2001.

[9]張慧哲.基于初始聚類中心選取的改進(jìn)FCM聚類算法[J].計(jì)算機(jī)科學(xué)，2009，26（6）；206-209.

[10]匡泰.FCM算法用于灰度圖像分割的初始化方法的研究[J].計(jì)算機(jī)應(yīng)用，2006，26（4）；784-786.

The traditional FCM algorithm has the defection of sensitivity to the initial cluster center and iterate so more,proposes an enhancing FCM algorithm by improved cluster initial center.A novel algorithm can partition data set into suited clusters through data conversion and sorting,and then find a best initial center.Given the number of cluster,test and compare by two group data set of UCI machining study database,results demonstrate that enhancing FCM algorithm has fast convergence,enhancing accuracy and stability than traditional FCM. Keywords：

Fuzzy C-Means;Objective Functiong;Initial Cluster Center;Data Partitioning

A FCM Algorithm Based on Improved Initial Cluster Center

TANG De-yu1，CAO Dong2，YANG Jin1

（1.Guangdong Pharmaceutical University，College of Medical Information and Engineering，Guangzhou 510006；2.Guangzhou University of Chinese Medicine，Guangzhou 510006）

唐德玉（1978-），男，廣東廣州人，博士，副教授，研究方向?yàn)閿?shù)據(jù)挖掘、智能計(jì)算、網(wǎng)絡(luò)集成

曹東（1975-），男，博士，副院長(zhǎng)

楊進(jìn)（1977-），男，廣東廣州人，碩士，講師，研究方向?yàn)閿?shù)據(jù)挖掘、智能計(jì)算

2016-09-13

2016-10-20