唐德玉，曹東，楊進(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)，提出一個改進(jìn)聚類初始中心點(diǎn)的加強(qiáng)FCM算法。新算法通過數(shù)據(jù)轉(zhuǎn)換及排序把數(shù)據(jù)劃分到合適的簇中，從而找到最好的聚類初始中心點(diǎn)。在給定聚類數(shù)目的條件下，通過UCI機(jī)器學(xué)習(xí)數(shù)據(jù)庫中的兩組數(shù)據(jù)集進(jìn)行實驗比較，結(jié)果表明采用加強(qiáng)FCM算法比傳統(tǒng)FCM算法收斂速度更快，有較高的準(zhǔn)確率和穩(wěn)定性。

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

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

0　引言

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

2.在第k步：使用U（k）計算中心向量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ù)比較多時，算法執(zhí)行很慢。為此我們提出一個加強(qiáng)FCM（enhancing FCM，以下簡稱eFCM算法）聚類算法。該方法是找到最好的初始中心點(diǎn)，改進(jìn)算法的時間復(fù)雜度，并提高算法的準(zhǔn)確性。

基本思路是計算數(shù)據(jù)集中所有樣本點(diǎn)與樣本原點(diǎn)的距離，把數(shù)據(jù)集中所有樣本點(diǎn)與樣本原點(diǎn)的距離排序。然后把所有排好序的數(shù)據(jù)樣本點(diǎn)平均劃分到K個子集。在這K個子集中的中間樣本點(diǎn)做為該集合的初始中心點(diǎn)。這些初始中心點(diǎn)會產(chǎn)生更好的唯一的聚簇結(jié)果。排序的算法我們考慮用快速排序算法，因為快速排序算法在最壞和最好情況下，平均時間復(fù)雜度為O （NlogN）。

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

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

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

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

輸入：

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

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

輸出：k個初始中心點(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.使用馬氏距離計算所有樣本點(diǎn)與樣本原點(diǎn)的距離。

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

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

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

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

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

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

3　仿真模擬實驗

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

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

本文實驗環(huán)境是，處理器頻率為2.10GHz，內(nèi)存3G，硬盤120G，使用Windows XP 32位操作系統(tǒng)。開發(fā)工具使用MATLAB 7.8。實驗初始化參數(shù)如下：隸屬度指數(shù)expo=2.0，簇數(shù)目clustern=3，迭代最大數(shù)目maxiter=100，目標(biāo)函數(shù)值誤差最小閾值為minimpro=1e-6。我們對Iris和Wine數(shù)據(jù)先對歸一化處理，以減少量綱不同對算法的影響。使用公式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)。

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

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

從表2中結(jié)果可以看出，我們提出的eFCM算法的準(zhǔn)確率高于普通FCM算法。Iris數(shù)據(jù)集和Wine數(shù)據(jù)集都有類標(biāo)號，每個數(shù)據(jù)集分為3個類（簇）（見表1）。準(zhǔn)確性的計算就是用聚類算法產(chǎn)生的三個簇中的樣本與已知的三個類（簇）中的樣本類別進(jìn)行比較，計算聚類產(chǎn)生的簇中正確分類的樣本總數(shù)。準(zhǔn)確率=同一簇中正確分類的樣本總數(shù)/同一簇已有樣本總數(shù)。比如，見表3，對于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）。

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

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

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

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

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

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

4　結(jié)語

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

[10]匡泰.FCM算法用于灰度圖像分割的初始化方法的研究[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-），男，廣東廣州人，博士，副教授，研究方向為數(shù)據(jù)挖掘、智能計算、網(wǎng)絡(luò)集成

曹東（1975-），男，博士，副院長

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

2016-09-13

2016-10-20