基于馬氏距離的模糊聚類(lèi)優(yōu)化算法

祖志文 李秦

摘要：為了解決以歐氏距離作為相似性準(zhǔn)則的傳統(tǒng)模糊聚類(lèi)算法對(duì)多維數(shù)據(jù)處理不利的問(wèn)題，采用馬氏距離代替歐氏距離，對(duì)基于馬氏距離的模糊聚類(lèi)算法進(jìn)行優(yōu)化研究，以增強(qiáng)基于馬氏距離的模糊聚類(lèi)算法的聚類(lèi)效果和能力。通過(guò)構(gòu)造啟發(fā)式搜索與kmeans算法結(jié)合的初始優(yōu)化方法，利用可以自動(dòng)調(diào)節(jié)最佳聚類(lèi)數(shù)的有效性函數(shù)，提出了一種優(yōu)化算法KMFCM，并將此新算法與FCM，F(xiàn)CMM，MFCM聚類(lèi)算法在3個(gè)標(biāo)準(zhǔn)數(shù)據(jù)集上進(jìn)行了實(shí)驗(yàn)。結(jié)果表明，KMFCM算法有效，聚類(lèi)精度比FCM，F(xiàn)CMM，MFCM高，對(duì)高維數(shù)據(jù)聚類(lèi)識(shí)別能力強(qiáng)，具有全局優(yōu)化作用，并且聚類(lèi)個(gè)數(shù)無(wú)需提前設(shè)定。新算法可為基于馬氏距離的模糊聚類(lèi)算法的優(yōu)化提供參考。

關(guān)鍵詞：算法理論；模糊聚類(lèi)；馬氏距離；初始優(yōu)化；聚類(lèi)個(gè)數(shù)

中圖分類(lèi)號(hào)：TP301.6文獻(xiàn)標(biāo)志碼：A

收稿日期：20171224；修回日期：20180220；責(zé)任編輯：張軍

基金項(xiàng)目：國(guó)家自然科學(xué)基金（11262009）

第一作者簡(jiǎn)介：祖志文（1993—），女，河北保定人，碩士研究生，主要從事智能算法方面的研究。

通信作者：李秦教授。Email：liq@mail.lzjtu.cn

祖志文，李秦.基于馬氏距離的模糊聚類(lèi)優(yōu)化算法——KMFCM[J].河北科技大學(xué)學(xué)報(bào)，2018，39（2）：159165.

ZU Zhiwen， LI Qin. KMFCM： A fuzzy clustering optimization algorithm based on Mahalanobis distance[J]. Journal of Hebei University of Science and Technology， 2018， 39（2）：159165.KMFCM： A fuzzy clustering optimization algorithm

based on Mahalanobis distance

ZU Zhiwen， LI Qin

（College of Mathematics and Physics， Lanzhou Jiaotong University， Lanzhou， Gansu 730070， China）

Abstract：The traditional fuzzy clustering algorithm uses Euclidean distance as the similarity criterion， which is disadvantageous to the multidimensional data processing. In order to solve this situation， Mahalanobis distance is used instead of the traditional Euclidean distance， and the optimization of fuzzy clustering algorithm based on Mahalanobis distance is studied to enhance the clustering effect and ability. With making the initialization means by Heuristic search algorithm combined with kmeans algorithm， and in terms of the validity function which could automatically adjust the optimal clustering number， an optimization algorithm KMFCM is proposed. The new algorithm is compared with FCM algorithm， FCMM algorithm and MFCM algorithm in three standard data sets. The experimental results show that the KMFCM algorithm is effective. It has higher clustering accuracy than FCM， FCMM and MFCM， recognizing highdimensional data clustering well. It has global optimization effect， and the clustering number has no need for setting in advance. The new algorithm provides a reference for the optimization of fuzzy clustering algorithm based on Mahalanobis distance.

Keywords：algorithm theory； fuzzy clustering； Mahalanobis distance； initial optimization； clustering number

聚類(lèi)是數(shù)據(jù)處理的重要方法。模糊聚類(lèi)建立了數(shù)據(jù)樣本對(duì)于類(lèi)別的不確定性的描述，表達(dá)了樣本類(lèi)屬的模糊性，能夠更客觀(guān)地反映現(xiàn)實(shí)世界，具有較強(qiáng)的聚類(lèi)效果與數(shù)據(jù)表達(dá)能力。

關(guān)于模糊聚類(lèi)的研究應(yīng)用最廣的是基于目標(biāo)函數(shù)的模糊聚類(lèi)方法，此方法把聚類(lèi)問(wèn)題描述為一個(gè)帶約束的優(yōu)化問(wèn)題，通過(guò)求解優(yōu)化問(wèn)題的解來(lái)確定數(shù)據(jù)集的模糊劃分和聚類(lèi)結(jié)果。FCM算法是最經(jīng)典的基于目標(biāo)函數(shù)的模糊聚類(lèi)算法，但也存在一些問(wèn)題，因此基于FCM算法的改進(jìn)算法和應(yīng)用被研究者所關(guān)注。蔡靜穎[1]為改進(jìn)FCM算法不能處理非球形簇且未考慮樣本矢量各特征重要程度、處理高相關(guān)數(shù)據(jù)集時(shí)錯(cuò)誤率增加的缺點(diǎn)，使用馬氏距離得到FCMM算法及MFFCM算法；蔡威[2]提出自適應(yīng)距離度量的GK算法。NATACHA等[3]研究了用馬氏距離和閔可夫斯基距離來(lái)取代歐氏距離的模糊聚類(lèi)的方法，以提高聚類(lèi)檢測(cè)能力，并對(duì)聚類(lèi)結(jié)果進(jìn)行了可視化分析。在應(yīng)用方面，張敏等[4]將馬氏距離和模糊c均值聚類(lèi)結(jié)合，研究摳圖算法；康韋曉[5]將基于馬氏距離的PFCM算法應(yīng)用于非線(xiàn)性系統(tǒng)故障診斷；趙泉華等[6]將馬氏距離的模糊聚類(lèi)算法用于遙感圖像分割。河北科技大學(xué)學(xué)報(bào)2018年第2期祖志文，等：基于馬氏距離的模糊聚類(lèi)優(yōu)化算法——KMFCM 另外，通過(guò)對(duì)FCM的初始化方法的改進(jìn)研究逐漸形成了山峰函數(shù)法或勢(shì)函數(shù)法[7]、減法聚類(lèi)[8]等方法，進(jìn)一步實(shí)現(xiàn)了快速減法聚類(lèi)的模糊聚類(lèi)算法，及基于密度函數(shù)的近似初始化方法[9]。上述文獻(xiàn)中基于馬氏距離的模糊聚類(lèi)算法的研究多是對(duì)協(xié)方差估算方面的改進(jìn)，并且已有的初始化方法對(duì)基于馬氏距離的模糊聚類(lèi)算法并不適用。為此，本研究通過(guò)對(duì)經(jīng)典聚類(lèi)算法和馬氏距離特性的分析，提出具有新初始化方法的基于馬氏距離模糊聚類(lèi)的優(yōu)化算法。

1經(jīng)典模糊聚類(lèi)算法與馬氏距離

1.1經(jīng)典模糊聚類(lèi)算法（FCM）

在基于目標(biāo)函數(shù)的模糊聚類(lèi)算法中，模糊c均值算法（fuzzy cmeans，F(xiàn)CM）的理論最為完善，應(yīng)用最為廣泛。FCM類(lèi)型的算法最早是由“硬”聚類(lèi)算法HCM導(dǎo)出的[10]，DUNN[11]把它的目標(biāo)函數(shù)J1=∑ci=1 ∑nj=1uij‖xj-vi‖2，uij∈{0，1}擴(kuò)展到隸屬度屬于模糊情形的類(lèi)內(nèi)加權(quán)平均誤差和函數(shù)J2=∑ci=1 ∑nj=1uij‖xj-vi‖2，uij∈[0，1]。后來(lái)BEZDEK[12]又引入了一個(gè)參數(shù)m，把J2推廣到一個(gè)目標(biāo)函數(shù)的無(wú)限簇，并給出了交替優(yōu)化算法，即形成了經(jīng)典的模糊c均值算法。

FCM算法的核心思想如下：設(shè)X={x1，x2，…，xi，…，xn}為n元數(shù)據(jù)集合。FCM聚類(lèi)方法就是把X劃分為c個(gè)子集S1，S2，…，Si，…，Sc，若用V={v1，v2，…，vi，…，vc}表示這c個(gè)子集的聚類(lèi)中心，uij表示元素xj對(duì)Si的隸屬度，則FCM算法的優(yōu)化目標(biāo)函數(shù)為

JmFCM（U，V，X）=∑ci=1 ∑nj=1umijd2ij=∑ci=1 ∑nj=1umij‖xj-vi‖2，（1）

uij滿(mǎn)足如下約束條件：

∑ci=1uij=1，1≤j≤n，uij≥0，1≤i≤c，i≤j≤n，（2）

這里U={uij}為c×n矩陣，V={v1，v2，…，vi，…，vc}為s×c矩陣，dij為xj與vj的距離，經(jīng)典的FCM算法里使用的是歐氏距離，推薦使用m=2。通過(guò)如上設(shè)定，最佳聚類(lèi)結(jié)果可使得目標(biāo)函數(shù)取得極小值。

FCM算法的具體步驟如下：

步驟1設(shè)定聚類(lèi)個(gè)數(shù)c（10；令迭代次數(shù)L=0，給出迭代數(shù)目的最大值Lmax。

步驟2根據(jù)uij=1∑ck=1（dijdkj）2m-1來(lái)計(jì)算U（L+1）。

步驟3用Vi=∑nj=1（uij）mXj∑nj=1（uij）m計(jì)算聚類(lèi)中心矩陣V（L+1），令L=L+1。

步驟4判斷2次聚類(lèi)中心矩陣的歐氏距離與給定閾值的大小，如果滿(mǎn)足終止條件：‖V（L）-V（L-1）‖≤ε，L≥1，或者迭代次數(shù)不小于給定的最大迭代次數(shù)，則迭代停止，否則，重復(fù)步驟2和步驟3。

在對(duì)比實(shí)驗(yàn)中，F(xiàn)CM聚類(lèi)的運(yùn)行相對(duì)于HCM算法速度較慢，但聚錯(cuò)樣本數(shù)明顯減少，并且該算法的收斂性已經(jīng)得以證明。但是由于經(jīng)典模糊聚類(lèi)算法就是反復(fù)修改聚類(lèi)中心矩陣和隸屬度矩陣的分類(lèi)過(guò)程，并且FCM對(duì)聚類(lèi)中心的初始化依賴(lài)，使得經(jīng)典模糊聚類(lèi)算法不能確保得到全局最優(yōu)解。另一方面，與HCM算法一樣，需要預(yù)先指定聚類(lèi)數(shù)目c，而實(shí)際中聚類(lèi)數(shù)目通常都是未知的，并且使用歐氏距離只適于發(fā)現(xiàn)球狀類(lèi)型等非凸面形狀的簇，不能處理橢球形結(jié)構(gòu)簇，在處理高維數(shù)據(jù)時(shí)效果欠佳。

1.2馬氏距離

歐氏距離只適用于樣本的屬性在相互獨(dú)立的條件下同等對(duì)待每個(gè)屬性對(duì)聚類(lèi)影響的情形。當(dāng)屬性之間相關(guān)時(shí)，對(duì)相關(guān)的屬性計(jì)算歐氏距離時(shí)將產(chǎn)生重復(fù)數(shù)據(jù)，影響了聚類(lèi)效果和最佳聚類(lèi)數(shù)的確定。同時(shí)，歐氏距離受屬性量綱的影響，對(duì)多維數(shù)據(jù)的處理是不利的。針對(duì)樣本向量中各維特征對(duì)模式分類(lèi)的不同影響，李潔等[13]提出了基于特征加權(quán)的模糊聚類(lèi)新算法，但收斂速度有所下降。用馬氏距離來(lái)取代歐式距離，可以有效解決以上困擾。馬氏距離是一種有效計(jì)算2個(gè)未知樣本集相似度的方法，與歐氏距離不同的是它考慮到各種特性之間的聯(lián)系，并且是與尺度無(wú)關(guān)的。在文獻(xiàn)＼[14＼]中說(shuō)明了當(dāng)聚類(lèi)算法在用于入侵檢測(cè)[15]時(shí)，馬氏距離比歐式距離具有明顯的優(yōu)勢(shì)，并且馬氏距離的模糊聚類(lèi)在圖像分割上也比歐氏距離的效果更優(yōu)[16]。

設(shè)樣本集合為X={x1，x2，…，xi，…，xm}，共有m個(gè)樣本，xi是n維特征矢量，i∈{1，2，…，m}，令X代表m×n的輸入矩陣，每行為一個(gè)樣本，則樣本的均值、自相關(guān)矩陣和協(xié)方差矩陣可用矩陣表示為

μ=E{X}=XT（1m）m×1；S=（1m）XTX；Σ=E{（X-μ）T}=1mXTX-μμT，

其中（1m）m×1代表元素均為1m的m維列矢量。

樣本Xi到樣本總體X的馬氏距離定義為d2（Xi-X）=（xi-μ）TΣ-1i（xi-μ）。

由于對(duì)于聚類(lèi)樣本的總體分布通常是未知的，而樣本協(xié)方差是總體協(xié)方差的無(wú)偏估計(jì)，常用樣本協(xié)方差矩陣代替總體協(xié)方差：Σi=1n∑ni=1（xi-）（xi-）′，=1n∑ni=1xi。若協(xié)方差矩陣是奇異的，將導(dǎo)致無(wú)法直接求馬氏距離，故大量文獻(xiàn)對(duì)基于馬氏距離的研究多是對(duì)計(jì)算其數(shù)據(jù)協(xié)方差的逆不存在的情況提出解決方案，王振麗[17]為改進(jìn)馬氏距離使用加權(quán)MP馬氏距離進(jìn)行研究；吳香華等[18]對(duì)馬氏距離聚類(lèi)分析中協(xié)方差矩陣的估算進(jìn)行改進(jìn)；趙小強(qiáng)等[19]通過(guò)改進(jìn)協(xié)方差矩陣的估計(jì)來(lái)提高馬氏距離聚類(lèi)分析效率。

基于馬氏距離的聚類(lèi)算法有如下特點(diǎn)。

1）協(xié)方差矩陣本身的意義是在多維向量之間找出一個(gè)自適應(yīng)的權(quán)重，即馬氏距離的計(jì)算是建立在總體樣本基礎(chǔ)上的，有利于加強(qiáng)聚類(lèi)的準(zhǔn)確性。

2）在計(jì)算馬氏距離過(guò)程中，要求總體樣本個(gè)數(shù)大于樣本的維數(shù)，否則得到的總體樣本協(xié)方差逆矩陣不存在。

3）在實(shí)際應(yīng)用中，“總體樣本個(gè)數(shù)大于樣本的維數(shù)”這個(gè)條件很容易滿(mǎn)足，即在絕大多數(shù)的情況下，馬氏距離是可以順利計(jì)算的，從而有關(guān)基于馬氏距離的模糊聚類(lèi)的優(yōu)化可以先忽略協(xié)方差問(wèn)題，針對(duì)高維大樣本的數(shù)據(jù)做出優(yōu)化的改進(jìn)算法。但是馬氏距離的計(jì)算是不穩(wěn)定的，不穩(wěn)定來(lái)源于協(xié)方差矩陣，這也是馬氏距離與歐氏距離的最大差異之處，故在研究中應(yīng)注意結(jié)合用加強(qiáng)穩(wěn)定性的優(yōu)化方案來(lái)彌補(bǔ)馬氏距離的不足。

針對(duì)以上問(wèn)題，在基于馬氏距離的模糊聚類(lèi)算法的研究基礎(chǔ)上，本研究并不側(cè)重對(duì)馬氏距離協(xié)方差問(wèn)題的優(yōu)化，而是另辟蹊徑，提出了新的初始化優(yōu)化方法，形成一種具有全局優(yōu)化性能、利于處理高維數(shù)據(jù)的、新的基于馬氏距離的模糊聚類(lèi)算法。

2模糊聚類(lèi)優(yōu)化算法——KMFCM

2.1新的聚類(lèi)初始化方法

由于基于山峰函數(shù)和減法聚類(lèi)的初始化方法的實(shí)現(xiàn)性并不令人滿(mǎn)意，近幾年對(duì)初始化方法的研究出現(xiàn)了結(jié)合進(jìn)化及生物仿生算法進(jìn)行的初始化方法，李靜[20]結(jié)合粒子群算法初始聚類(lèi)中心，使得聚類(lèi)結(jié)果以較快收斂速度接近最優(yōu)解，并且無(wú)需給定聚類(lèi)數(shù)目，但其缺點(diǎn)是引入了其他參數(shù)；NAIK等[21]使用基于教學(xué)學(xué)習(xí)（TLBO）的優(yōu)化算法，聚類(lèi)結(jié)果以較快收斂速度接近最優(yōu)解，但是局限于歐氏距離且需要給定聚類(lèi)數(shù)目。

還有一種聚類(lèi)初始化方法是將已有的復(fù)雜度低的聚類(lèi)算法結(jié)果作為模糊聚類(lèi)的初始聚類(lèi)中心，如直接運(yùn)用kmeans算法選出初始聚類(lèi)中心[9]；結(jié)合概率抽樣方法的kmeans++算法[2223]是比前者初始效果更好的聚類(lèi)初始化方法，但引入了一個(gè)缺乏理論支撐的參數(shù)p。

考慮到基于馬氏距離的模糊聚類(lèi)算法比經(jīng)典的模糊聚類(lèi)算法運(yùn)行速度慢，為減少算法速度負(fù)擔(dān)，在此提出的初始化方法也是將kmeans聚類(lèi)算法結(jié)果作為模糊聚類(lèi)的初始聚類(lèi)中心。由于kmeans對(duì)聚類(lèi)中心初始化敏感，易陷入局部最優(yōu)且需給定聚類(lèi)數(shù)，故給出基于啟發(fā)式搜索算法與kmeans算法結(jié)合的聚類(lèi)初始化方法，對(duì)基于馬氏距離的模糊算法進(jìn)行優(yōu)化。

新的初始化方法主要思想如下。為實(shí)現(xiàn)全局優(yōu)化并且避免重復(fù)初始聚類(lèi)中心，首先考慮在一定的聚類(lèi)個(gè)數(shù)范圍內(nèi)用啟發(fā)式搜索聚類(lèi)中心，然后利用kmeans聚類(lèi)算法得出初始聚類(lèi)中心。最佳聚類(lèi)數(shù)通常滿(mǎn)足cmax≤n，n為樣本數(shù)據(jù)個(gè)數(shù)，本研究也作這樣的設(shè)定。

新的初始化方法的具體步驟如下。

第1步：求出樣本集合O中兩兩樣本之間的距離，找出距離最小的一對(duì)較小樣本x1，x2；

第2步：把x1，x2放到新的集合A1中，并將它們從樣本集合O中刪除；

第3步：計(jì)算A1中樣本的均值a1，求出a1與O中每個(gè)樣本的距離，找出O中與a1最近的較小樣本x3，將x3并入集合A1，且從O中刪除，如此重復(fù)，直到A1中樣本個(gè)數(shù)達(dá)到n3n的向下取整值；

第4步：再把O中現(xiàn)有樣本中距離最小的一對(duì)較小樣本x′1，x′2放入新的集合A1中，并將它們從O中刪除，重復(fù)第3步的過(guò)程，直到形成m個(gè)集合A1，A2，…，Am，m預(yù)設(shè)成比n大的值，n為數(shù)據(jù)集樣本的個(gè)數(shù)，這里設(shè)定成m=3n；

第5步：分別求出A1，A2，…，An的均值1，2，…，n，對(duì)數(shù)據(jù)集{1，2，…，n}運(yùn)用kmeans算法，得到的n個(gè)聚類(lèi)中心作為用于模糊聚類(lèi)算法的初始聚類(lèi)中心。

針對(duì)每個(gè)聚類(lèi)數(shù)目進(jìn)行模糊聚類(lèi)時(shí)，都要重新初始化所造成的聚類(lèi)數(shù)目不穩(wěn)定的情況，經(jīng)過(guò)算法迭代后，采用合并聚類(lèi)中心的方式。這使得聚類(lèi)個(gè)數(shù)自適應(yīng)，無(wú)需給定聚類(lèi)數(shù)目c。

2.2KMFCM算法

首先，在聚類(lèi)相似性準(zhǔn)則方面，在經(jīng)典FCM算法的目標(biāo)函數(shù)中用馬氏距離替代歐氏距離，并且在目標(biāo)函數(shù)上引進(jìn)一個(gè)協(xié)方差調(diào)節(jié)因子：-ln|Σ-1i|，得到的優(yōu)化目標(biāo)函數(shù)為

Jm（U，C，X）=∑ci=1 ∑nj=1umij[（xj-ci）′Σ-1i（xj-ci）-ln|Σ-1i|]，

s.t.uij∈[0，1]； ∑ci=1uij=1；0<∑nj=1uij

該優(yōu)化問(wèn)題的拉格朗日乘子式為

J=∑ci=1 ∑nj=1umij[（xj-ci）′Σ-1i（xj-ci）-ln|Σ-1i|]+∑nj=1λj（1-∑ci=1uij），

最小化J，對(duì)ci，uij，Σi求偏導(dǎo)，并令其結(jié)果等于零，得：

uij=[∑cs=1[（xj-ci）′Σ-1i（xj-ci）（xj-cs）′Σ-1i（xj-cs）]1m-1]-1，i=1，2，…，c；j=1，2，…，n， （3）

ci=[∑nj=1umij]-1[∑nj=1umijxj]，i=1，2，…，c，（4）

Σi=∑nj=1umij（xj-ci）（xj-ci）′∑nj=1umij，i=1，2，…，c 。

其次，在交替優(yōu)化方面，結(jié)合新的聚類(lèi)初始化方法，并引用文獻(xiàn)＼[9＼]中的利用粒度分析原理的GD有效性準(zhǔn)則函數(shù)在算法循環(huán)中合并聚類(lèi)方法，得到基于馬氏距離的模糊聚類(lèi)優(yōu)化算法——KMFCM。

1） 取定最大初始聚類(lèi)個(gè)數(shù)cmax=data_n，data_n為樣本數(shù)據(jù)個(gè)數(shù)，模糊加權(quán)指數(shù)m=2，迭代停止閾值Lmin=1×10-5，權(quán)重因子α=0.6，最大迭代次數(shù)Lmax=100，并令迭代計(jì)數(shù)器L=0；

2） 由設(shè)定的初始聚類(lèi)個(gè)數(shù)cmax，運(yùn)用新的初始化方法，得到初始聚類(lèi)中心結(jié)果矩陣C并輸出；

3） 用式（3）計(jì)算隸屬矩陣U；

4） 用式（4）更新聚類(lèi)中心矩陣C；

5） 若聚類(lèi)中心達(dá)到迭代停止閾值，則輸出模糊分類(lèi)隸屬矩陣U和聚類(lèi)中心C，若未達(dá)到迭代停止閾值，則令L= L+1，轉(zhuǎn)向步驟3）；

6）計(jì)算有效性函數(shù)GD（C）=αCD（C）+（1-α）1SD（C），

其中：

CD（C）=1n∑ci=1 ∑nj=1umijd2ij，i=1，2，…，c；j=1，2，…，n，

SD（C）=∑ci，s=1，i≠sd2is[c（c-1）]/2，i，s=1，2，…，c，

將GD值保存起來(lái)；

7）將類(lèi)間兩兩之間的距離最小的兩類(lèi)合并為一類(lèi)，得到c-1個(gè)聚類(lèi)中心；

8）令c=c-1，若c<2，則轉(zhuǎn)向步驟9），否則轉(zhuǎn)向步驟3），直到達(dá)到最大迭代次數(shù)Lmax=100；

9）選擇最小值GD對(duì)應(yīng)的聚類(lèi)結(jié)果，即為最佳聚類(lèi)結(jié)果，算法結(jié)束。

3結(jié)果與分析

為了證明應(yīng)用本研究提出的初始化優(yōu)化后的KMFCM算法比FCM算法及未優(yōu)化的基于馬氏距離的模糊聚類(lèi)算法FCMM[1]，MFCM[19]在多屬性的樣本聚類(lèi)實(shí)驗(yàn)中具有優(yōu)勢(shì)，筆者將FCM，F(xiàn)CMM，MFCM，KMFCM算法應(yīng)用于來(lái)自UCI數(shù)據(jù)庫(kù)的Iris，Wine和Pima等3個(gè)標(biāo)準(zhǔn)數(shù)據(jù)集。Iris數(shù)據(jù)集由4維空間的150個(gè)樣本組成，分為3個(gè)類(lèi)別，第1類(lèi)與其他2類(lèi)完全分離，而第2類(lèi)與第3類(lèi)之間有交叉，有很多學(xué)者認(rèn)為Iris數(shù)據(jù)也可以分為兩類(lèi)[2425]；Wine數(shù)據(jù)由13維空間的178個(gè)樣本組成，分為3個(gè)完全分離的類(lèi)別；Pima數(shù)據(jù)集由8維空間的768個(gè)樣本組成，分為2個(gè)相互交疊的類(lèi)別。

分別使用FCM，F(xiàn)CMM，MFCM聚類(lèi)算法與KMFCM聚類(lèi)算法對(duì)Iris數(shù)據(jù)各進(jìn)行20次實(shí)驗(yàn)，取20次實(shí)驗(yàn)的平均值。其中，F(xiàn)CM，F(xiàn)CMM，MFCM聚類(lèi)算法設(shè)定聚類(lèi)類(lèi)別數(shù)，4種算法實(shí)驗(yàn)中相同參數(shù)設(shè)置如下：隸屬度矩陣的指數(shù)m=2，最大迭代次數(shù)Lmax=100，迭代停止準(zhǔn)則為L(zhǎng)min=1×10-5。對(duì)3種數(shù)據(jù)集的4種聚類(lèi)算法比較分別如表1，表2和表3所示。

由表1可知，KMFCM算法對(duì)低維屬性的Iris數(shù)據(jù)集進(jìn)行聚類(lèi)是有效的；由表2可知，在高維屬性的模糊聚類(lèi)中，F(xiàn)CM的聚類(lèi)效果明顯下降，而其他基于馬氏距離的模糊聚類(lèi)算法聚類(lèi)精度較高，KMFCM算法聚錯(cuò)個(gè)數(shù)明顯減少；由表3可知，KMFCM算法在有交疊的、類(lèi)邊界并不清晰的較大樣本Pima數(shù)據(jù)集上聚類(lèi)效果依然良好。對(duì)于3個(gè)不同的數(shù)據(jù)集，從時(shí)間上來(lái)看，由于文獻(xiàn)＼[1＼]中的FCMM算法并未使用優(yōu)化技巧，運(yùn)行速度大于文獻(xiàn)＼[19＼]中用到數(shù)據(jù)標(biāo)準(zhǔn)化處理、總體協(xié)方差估計(jì)優(yōu)化方法的MFCM算法以及本研究提出的KMFCM算法。但是，經(jīng)過(guò)初始化優(yōu)化的KMFCM算法聚類(lèi)精度比其他3種聚類(lèi)算法的聚類(lèi)精度都要好，誤分個(gè)數(shù)少，具有全局優(yōu)化效果，并且無(wú)需設(shè)定聚類(lèi)個(gè)數(shù)。在20次實(shí)驗(yàn)中，由于馬氏距離的不穩(wěn)定性，并且未進(jìn)行協(xié)方差奇異問(wèn)題處理，KMFCM算法在有交疊樣本數(shù)據(jù)中的聚類(lèi)穩(wěn)定性有待進(jìn)一步研究。

4結(jié)語(yǔ)

通過(guò)對(duì)經(jīng)典聚類(lèi)算法和馬氏距離特性的研究，以及觀(guān)察關(guān)于初始化方法改進(jìn)的最新動(dòng)態(tài)，本研究給出了適用于馬氏距離模糊聚類(lèi)算法的初始化方法，提出基于馬氏距離模糊聚類(lèi)的優(yōu)化算法KMFCM。用馬氏距離替換經(jīng)典的模糊聚類(lèi)算法中的歐氏距離，采用啟發(fā)式搜索與kmeans算法結(jié)合的初始化方法，與FCM，F(xiàn)CMM，MFCM等3種算法在3個(gè)標(biāo)準(zhǔn)數(shù)據(jù)集上進(jìn)行仿真對(duì)比實(shí)驗(yàn)，驗(yàn)證了新的算法的有效性和全局優(yōu)化作用。研究結(jié)果可為基于馬氏距離的模糊聚類(lèi)算法的優(yōu)化提供參考。

參考文獻(xiàn)/References：

[1]蔡靜穎.模糊聚類(lèi)算法及應(yīng)用[M].北京：冶金工業(yè)出版社，2015.

[2]蔡威. 模糊聚類(lèi)算法在數(shù)據(jù)挖掘中的應(yīng)用研究[D]. 蘭州：蘭州交通大學(xué)，2012.

CAI Wei. Research on the Application of Fuzzy Clustering Algorithm in Data Mining[D]. Lanzhou：Lanzhou Jiaotong University，2012.

[3]NATACHA G， IREN V， GEORGE G， et al. Fuzzy Cmeans clustering with mahalanobis and minkowski distance metrics[J]. Procedia Computer Science， 2017，114： 224233.

[4]張敏，閔樂(lè)泉，張群，等. 基于馬氏距離和模糊C均值聚類(lèi)的摳圖算法與應(yīng)用[J].北京科技大學(xué)學(xué)報(bào)，2014，36（5）：688694.

ZHANG Min， MIN Lequan， ZHANG Qun， et al. Matting algorithm and application based on Mahalanobis distance and the fuzzy Cmeans clustering algorithm[J]. Journal of University of Science and Technology Beijing， 2014，36（5）：688694.

[5]康韋曉. 基于馬氏距離的PFCM算法的非線(xiàn)性系統(tǒng)故障診斷方法[D]. 哈爾濱：哈爾濱工業(yè)大學(xué)，2016.

KANG Weixiao.Fault Diagnosis Method for Nonlinear System based on PECM Algorithm with Mahalanobis Distance[D]. Harbin：Harbin Institute of Technology， 2016.

[6]趙泉華，李曉麗，趙雪梅，等. 結(jié)合馬氏距離的區(qū)域化模糊聚類(lèi)遙感圖像分割[J]. 中國(guó)礦業(yè)大學(xué)學(xué)報(bào)，2017，46（1）：222228.

ZHAO Quanhua， LI Xiaoli， ZHAO Xuemei， et al. Remote sensing image segmentation algorithm with regional fuzzy cluster and Mahalanobis distance[J]. Journal of China University of Mining & Technology， 2017， 46（1）： 222228.

[7]YAGER R R， FILEV D P.Approximate clustering via the mountain method[J]. IEEE Transaction on Systems Man & Cybemetics， 2002， 24（8）： 12791284.

[8]CHIU S L. Fuzzy model identification based on cluster estimation[J]. Journal of Intelligent and Fuzzy System， 1994，2（3）：267278.

[9]陳東輝. 基于目標(biāo)函數(shù)的模糊聚類(lèi)算法關(guān)鍵技術(shù)研究[D]. 西安：西安電子科技大學(xué)，2012.

CHEN Donghui. Research of Key Techniques in Fuzzy Clustering Based on Objective Function[D]. Xian：Xidian University， 2012.

[10]陳新泉.聚類(lèi)算法中的優(yōu)化方法應(yīng)用[M].成都：電子科技大學(xué)出版社，2014.

[11]DUNN J C.Wellseparated clusters and optimal fuzzy partitions[J].Journal of Cybernetics，1974，4（1）：95104.

[12]BEZDEK J C.Pattern Recognition with Fuzzy Objective Function Algorithms[M].New York：Plenum Press， 1981.

[13]李潔， 高新波， 焦李成.基于特征加權(quán)的模糊聚類(lèi)新算法[J].電子學(xué)報(bào)， 2006， 34（1）： 8992.

LI Jie， GAO Xinbo， JIAO Licheng. A new feature weighted fuzzy clustering algorithm[J]. Acta Electronica Sinica， 2006，34（1）： 8992.

[14]易倩，滕少華，張巍. 基于馬氏距離的K均值聚類(lèi)算法的入侵檢測(cè)[J]. 江西師范大學(xué)學(xué)報(bào)（自然科學(xué)版），2012，36（3）：284287.

YI Qian， TENG Shaohua， ZHANG Wei. Mahalanobis distancebased on Kmeans clustering algorithm for intrusion detection [J]. Journal of Jiangxi Normal University （Natural Science）， 2012， 36（3）： 284287.

[15]LIU J， CHEN H， ZHONG Z， et al. Intrusion detection algorithm for the wormhole attack in Ad Hoc network[C]// Proceedings of International Conference on Computer Science and Information Technology Advances in Intelligent Systems and Computing[S.l.]：[s.n.].2014：147157.

[16]LIU H C， JENG B C， YlH J M， et al. Fuzzy Cmeans algorithm based on standard Mahalanobis distances[C]. Proc of the 2009 international Symposium on Information Processing. Huangshan：[s.n.]， 2009：422427.

[17]王振麗. 基于加權(quán)MP馬氏距離的GS方法研究[D]. 南京：南京理工大學(xué)，2016.

WANG Zhenli. Research about GS Method Based on the Weighted MP Mahalanobis Distance[D]. Nanjing：Nanjing University of Science & Technology， 2016.

[18]吳香華，牛生杰，吳誠(chéng)鷗，等. 馬氏距離聚類(lèi)分析中協(xié)方差矩陣估算的改進(jìn)[J]. 數(shù)理統(tǒng)計(jì)與管理，2011，30（2）：240245.

WU Xianghua， NIU Shengjie， WU Chengou， et al. An improvement on estimating covariance matrix during clusteranalysis using mahalanobis distance[J]. Journal of Applied Statistics and Management， 2011， 30（2）： 240245.

[19]趙小強(qiáng)，李雄偉. 基于改進(jìn)馬氏距離的模糊C聚類(lèi)研究[J]. 中南大學(xué)學(xué)報(bào)（自然科學(xué)版），2013，44（sup2）：195198.

ZHAO Xiaoqiang， LI Xiongwei. A fuzzy Cmeans clustering algorithm based on improved Mahalanobis distance[J]. Journal of Central South University （Science and Technology）， 2013， 44（sup2）： 195198.

[20]李靜. 模糊聚類(lèi)算法的研究及應(yīng)用[D]. 無(wú)錫：江南大學(xué)，2014.

LI Jing. Research and Application of Fuzzy Clustering Algorithm[D].Wuxi：Jiangnan University， 2014.

[21]NAIK A，SATAPATHY S C，PARVATH K. Improvement of initial cluster center of Cmeans using teaching learning based optimization[J]. Procedia Technology， 2012，6（4）：428435.

[22]CELEBI M E， KINGRAVI H A，VELA P A. A comparative study of efficient initialization methods for the kmeans clustering algorithm[J]. Expert Systems with Applications，2013， 40（1）： 200210.

[23]STETCO A， ZENG Xiaojun， KEANE J. Fuzzy Cmeans++： Fuzzy Cmeans with effective seeding initialization[J]. Expert Systems with Applications， 2015，42（21）：75417548.

[24]汪西莉， 焦李成.一種基于馬氏距離的支持向量快速提取算法[J].西安電子科技大學(xué)學(xué)報(bào)（自然科學(xué)版），2004， 31（4）：639643.

WANG Xili， JIAO Licheng. A fast algorithm for extracting the support vector on the Mahalanobis distance[J]. Journal of Xidian University， 2004， 31（4）： 639643.

[25]RUIZ A， LPEZDETERUEL P E. Nonlinear kernelbased statistical pattern analysis[J]. IEEE Trans Neural Netw， 2001，12 （1）：1632.第39卷第2期河北科技大學(xué)學(xué)報(bào)Vol.39，No.2