超木日力格，于　劍+，朱　杰,2

1.北京交通大學(xué) 計(jì)算機(jī)與信息技術(shù)學(xué)院 交通數(shù)據(jù)分析與挖掘北京市重點(diǎn)實(shí)驗(yàn)室，北京 100044

2.中央司法警官學(xué)院 信息管理系，河北 保定 071000

結(jié)合Total-Bregman距離的模糊聚類算法*

超木日力格1，于劍1+，朱杰1,2

1.北京交通大學(xué) 計(jì)算機(jī)與信息技術(shù)學(xué)院 交通數(shù)據(jù)分析與挖掘北京市重點(diǎn)實(shí)驗(yàn)室，北京 100044

2.中央司法警官學(xué)院 信息管理系，河北 保定 071000

Chaomurilige,YU Jian,ZHU Jie.Fuzzy clustering algorithm based on Total-Bregman divergence.Journal of Frontiers of Computer Science and Technology,2016,10(2):220-229.

模糊C均值（fuzzy C-means,FCM）聚類算法是一種常用的基于目標(biāo)函數(shù)最小化的聚類算法。目前已經(jīng)提出了相當(dāng)數(shù)量的聚類算法是對(duì)模糊C均值聚類算法的改進(jìn)，例如AFCM算法、GK算法等。對(duì)最近發(fā)表的基于Bregman距離的模糊聚類算法進(jìn)行了改進(jìn)，通過在FCM模糊聚類框架中引入Total-Bregman距離提升了聚類算法的聚類性能。同時(shí)對(duì)基于Total-Bregman距離的模糊聚類算法的收斂性質(zhì)進(jìn)行了理論分析。實(shí)驗(yàn)部分對(duì)來自UCI數(shù)據(jù)庫的幾個(gè)數(shù)據(jù)集進(jìn)行了聚類，證明了算法的有效性和收斂性。

聚類算法；模糊聚類；Total-Bregman距離

1　引言

近年來，隨著網(wǎng)絡(luò)和多媒體的蓬勃發(fā)展，收集到的海量文本信息、圖像信息、視頻信息、音頻信息等數(shù)據(jù)使得人工處理這些數(shù)據(jù)變得越來越難。機(jī)器學(xué)習(xí)研究的崛起使得人們有可能通過機(jī)器學(xué)習(xí)的方式處理這些數(shù)據(jù)。機(jī)器學(xué)習(xí)研究中，聚類作為一種無監(jiān)督學(xué)習(xí)方式，得到了來自各個(gè)領(lǐng)域研究者的關(guān)注。數(shù)據(jù)聚類算法在許多領(lǐng)域受到廣泛應(yīng)用，包括機(jī)器學(xué)習(xí)、數(shù)據(jù)挖掘、模式識(shí)別、圖像分析和生物信息。在聚類算法的發(fā)展歷程中，研究工作者們嘗試從不同角度來描述聚類問題，并提出了許多基于不同理論且適用于不同應(yīng)用的聚類算法[1]。

相對(duì)于有監(jiān)督的分類問題，聚類是一種在沒有任何先驗(yàn)信息的條件下將無標(biāo)記數(shù)據(jù)進(jìn)行歸類的過程。對(duì)于聚類算法，迄今為止都沒有一個(gè)學(xué)術(shù)界公認(rèn)的定義。Everitt[2]于1974年給出了關(guān)于聚類的定義：一個(gè)類簇內(nèi)的樣例是相似的，不同類簇的樣例是不相似的；一個(gè)類簇是測(cè)試空間中點(diǎn)的會(huì)聚，同一類簇的任意兩個(gè)點(diǎn)間的距離小于不同類簇的任意兩個(gè)點(diǎn)間的距離；類簇可以描述一個(gè)包含密度相對(duì)較高的點(diǎn)集的多維空間中的聯(lián)通區(qū)域，它們借助包含密度相對(duì)較低的點(diǎn)集的區(qū)域與其他區(qū)域（類簇）相分離。由聚類算法的定義可知，聚類的關(guān)鍵問題是相似度或相異度的度量[3]，即怎樣計(jì)算點(diǎn)（樣例為測(cè)試空間中的一點(diǎn)）與點(diǎn)間的距離。只要定義了相似度或相異度的度量，就可以挖掘出數(shù)據(jù)的內(nèi)在結(jié)構(gòu)，為進(jìn)一步的數(shù)據(jù)分析提供信息。因此，聚類結(jié)果直接依賴于相似度或相異度度量，對(duì)于模糊聚類算法亦是如此。

模糊集的概念由Zadeh于1965提出之后[4]，即成為軟劃分聚類有力的分析工具。軟劃分聚類算法中，數(shù)據(jù)可能同時(shí)屬于若干個(gè)類，而其隸屬于某個(gè)類的程度是根據(jù)隸屬度來定義的。模糊C均值算法（fuzzy C-means,FCM）自Dunn在1973年提出[5-6]之后隨即成為了應(yīng)用最廣、最靈活的一種模糊聚類算法，它是對(duì)硬C均值聚類算法的一種改進(jìn)算法。之后為了克服FCM算法只對(duì)球形數(shù)據(jù)的聚類結(jié)果較為理想的缺點(diǎn)，Gustafson和Kessel等人將馬氏距離引入模糊C均值聚類算法框架中，給出了GK模糊聚類算法[7-8]。該算法的優(yōu)點(diǎn)在于，對(duì)非球形的簇，尤其是橢圓形的簇，聚類效果非常好。Yang等人在FCM模糊聚類算法的框架中引入高斯核，使得算法對(duì)于離群點(diǎn)和噪聲更加魯棒[9]。之后，Yang等人又在FCM算法的框架下結(jié)合類間離散度和類內(nèi)緊致度提出了另一種模糊聚類算法[10]。2012年，Xiong等人提出，所有適用于FCM算法框架的距離表達(dá)均可由連續(xù)可微的凸函數(shù)導(dǎo)出。文章核心思想為，當(dāng)且僅當(dāng)距離為P2C-D距離（即Bregman距離）時(shí)，該距離適用于FCM聚類算法框架[11]。這類算法稱之為基于Bregman距離的模糊聚類算法。

本文將Total-Bregman距離與FCM模糊聚類框架相結(jié)合，提出了結(jié)合模糊C均值聚類框架與Total-Bregman距離的模糊聚類算法，并證明了該算法的收斂性等性質(zhì)。

本文組織結(jié)構(gòu)如下：第2章重點(diǎn)回顧FCM算法；第3章重點(diǎn)介紹基于Bregman距離的模糊聚類算法；第4章介紹Total-Bregman距離和結(jié)合模糊C均值聚類框架與Total-Bregman距離的模糊聚類算法；最后給出一些實(shí)驗(yàn)結(jié)果，并展望未來的工作。

2　模糊C均值聚類算法

模糊C均值聚類算法由Dunn在1973年提出，目前在很多領(lǐng)域得到了廣泛的應(yīng)用。該聚類算法允許數(shù)據(jù)點(diǎn)同時(shí)屬于兩個(gè)甚至多個(gè)類，而每個(gè)數(shù)據(jù)點(diǎn)屬于某個(gè)類的程度用隸屬度進(jìn)行約束，從而達(dá)到數(shù)據(jù)分類的目的。

首先，定義X數(shù)據(jù)集中第k個(gè)樣本xk和第i個(gè)聚類中心vi之間的誤差平方和（歐式距離）：

在FCM算法中，樣本到聚類中心的距離是通過歐氏距離定義的。

Dunn對(duì)每個(gè)數(shù)據(jù)點(diǎn)與每個(gè)聚類中心的距離用其隸屬度平方加權(quán)，得到類內(nèi)加權(quán)平方和目標(biāo)函數(shù)為：

受限條件為：

式（2）中，m為模糊指數(shù)，用以控制聚類結(jié)果的模糊程度。將滿足所有受限條件的矩陣集合記為：

通過使用拉格朗日乘數(shù)法，可以得到FCM算法的迭代公式如下：

模糊C均值聚類算法是一個(gè)簡單的迭代過程，具體的實(shí)現(xiàn)框架如下：

算法1 FCM模糊聚類算法框架

上述算法也可以先初始化聚類中心，然后再執(zhí)行迭代過程。不論采用何種方法，整個(gè)計(jì)算過程就是反復(fù)更新聚類中心和劃分矩陣，因此這種方法又稱為動(dòng)態(tài)聚類或交替優(yōu)化聚類法。

模糊C-均值算法是目前應(yīng)用較廣的一種聚類算法，但也存在著很多的問題。例如FCM算法需要事先確定數(shù)據(jù)集的分類數(shù)c；需要初始化聚類中心和加權(quán)指數(shù)m等。但與此相比，F(xiàn)CM聚類算法最大的挑戰(zhàn)在于，算法采用歐幾里德距離作為相似度度量，該距離度量只適用于處理類內(nèi)緊密、類間分散的數(shù)據(jù)以及球形數(shù)據(jù)，不能處理非凸形狀的數(shù)據(jù)。文獻(xiàn)中很多的聚類算法均是通過改進(jìn)FCM聚類算法框架中的距離度量方式，從而提升算法的性能。例如，Gustafson和Kessel等人將歐式距離度量方式改為馬氏距離度量方式，提出了GK模糊聚類算法使得算法對(duì)非球形尤其是橢圓形的簇聚類效果更佳[7-8]。Yang等人利用高斯核對(duì)于離群點(diǎn)和噪聲魯棒的特性，結(jié)合FCM模糊聚類算法的框架，提出了AFCM聚類算法[9]。類似的例子數(shù)不勝數(shù)，這里不多做贅述。下文著重描述基于Bregman距離的模糊聚類算法，并給出了適用于FCM交替優(yōu)化過程的距離函數(shù)的一般定義。

3　基于Bregman距離的模糊聚類算法

上文主要介紹了FCM算法及交替迭代優(yōu)化框架。根據(jù)文中給出的交替迭代方式，可以得到目標(biāo)函數(shù)的極小值。但這個(gè)結(jié)果建立在一個(gè)重要的前提下：距離的度量方式為平方歐式距離（例如二范數(shù)）或者其直接擴(kuò)展得到的內(nèi)積度量（例如馬氏距離）等。自然地，就會(huì)有以下兩個(gè)問題：（1）還有沒有其他的距離度量方式適用于FCM聚類框架中，并且可以使得目標(biāo)函數(shù)達(dá)到極小值；（2）這種距離的充分必要條件是什么。

針對(duì)以上問題，Xiong等人[11]將FCM算法推廣到更為一般的情況。假設(shè)FCM算法框架中的距離度量方式為任意的距離函數(shù) f(xk,vi)，可以得到基于廣義距離的FCM目標(biāo)函數(shù)（general-distance based fuzzy clustering algorithm,GD-FCM）[11]：

受限條件為：

其中，f為距離函數(shù)；dom2(f)為函數(shù) f的值域；Mfc為矩陣集合；m為模糊指數(shù)，。那么當(dāng)且僅當(dāng)距離 f使得目標(biāo)函數(shù)單調(diào)下降時(shí)，該距離度量可以直接在FCM模糊距離框架中使用。

定理1S?Rd為一個(gè)非空凸集。假設(shè)連續(xù)可微函數(shù) f:S×S?R+滿足：（1）f(x,x)=0,?x∈S；（2）fyj(x,y)在xl上連續(xù)可微，1≤j,l≤d。如果距離 f(x,y)適用于GD-FCM，該距離度量滿足 f(x,y)=φ(x)-φ(y)-(x-y)T?φ(y)，即Bregman距離，其中φ(·)為任意凸函數(shù)。

證明 首先，證明d=1時(shí)的情形。令λk≡u(píng)mik，當(dāng)距離度量適用于GD-FCM時(shí)，應(yīng)存在極值點(diǎn)：

當(dāng)且僅當(dāng)y*=xk時(shí)?yf(xk,y*)=0，因此當(dāng)且僅當(dāng)存在唯一的λk＞0。假設(shè)存在兩個(gè)不同的系數(shù)λ1,λ2＞0，那么令，有：

由Δ+=Δ-且?yf在x上連續(xù)可微，對(duì)于任意k≠k′，得到。記?y?xf(x,y)=-h(y)，對(duì)其積分得到?yf(x,y)=-h(y)x+I(y)。帶入式（7）得到 I(y)=h(y)y。因此得到

上述只是對(duì)一維情況下的推導(dǎo)。若將其擴(kuò)展到高維的情況，則得到距離 f(x,y)適用于GD-FCM，那么它應(yīng)該滿足 f(x,y)=φ(x)-φ(y)-(x-y)T?φ(y)，其中φ(·)為任意凸函數(shù)。

與FCM算法一樣，優(yōu)化目標(biāo)函數(shù)minJmf(U,V)得到隸屬度矩陣U和聚類中心V的迭代公式（與式（3）、式（4）相同）。此時(shí)，通過迭代更新隸屬度及聚類中心，可以達(dá)到目標(biāo)函數(shù)的極小化。

固定聚類中心V，Jmf(U)的全局最小可以通過式（4）的隸屬度迭代更新得到。在文獻(xiàn)[12]中，Bezdek等人已證明上述命題在歐式距離條件下是成立的。同理，在給定凸函數(shù)的情況下，也可給出類似證明。

上述的分析，是在固定聚類中心或者隸屬度的情況下，迭代更新公式可以取得最優(yōu)解。因此，在實(shí)際中，可以通過迭代更新（即固定一個(gè)更新另一個(gè)）的方式，對(duì)目標(biāo)函數(shù)進(jìn)行優(yōu)化。但一般算法會(huì)收斂至局部最優(yōu)解，有時(shí)會(huì)收斂至鞍點(diǎn)。

綜上所述，Bregman距離測(cè)度可以直接用于FCM聚類框架，并且通過迭代更新保證算法可以找到目標(biāo)函數(shù)的局部最小值。除此之外，Bregman距離也在其他聚類算法中得到了廣泛應(yīng)用[13-15]。但結(jié)合FCM聚類框架與Bregman距離測(cè)度的聚類算法，即基于Bregman距離的模糊聚類算法，也存在一些的缺點(diǎn)，例如對(duì)噪聲和異常點(diǎn)不魯棒等。下文介紹的結(jié)合模糊C均值聚類框架與Total-Bregman距離的模糊聚類算法，是對(duì)基于Bregman距離的模糊聚類算法的改進(jìn)。

4　Total-Bregman距離和結(jié)合FCM聚類框架與Total-Bregman距離的模糊聚類算法

4.1Total-Bregman距離

與Bregman距離不同，Total-Bregman距離通過衡量兩點(diǎn)間的正交距離作為兩點(diǎn)間的距離測(cè)度。Total-Bregman距離源于總體最小二乘法，與最小二乘法不同，總體最小二乘法是通過最小化正交距離的平方和尋找數(shù)據(jù)的最佳函數(shù)匹配[16]。相對(duì)于歐氏距離來說，正交距離不會(huì)隨著坐標(biāo)系的尺度變化或旋轉(zhuǎn)而改變，穩(wěn)定性優(yōu)于Bregman距離。

圖1給出了Total-Bregman距離和Bregman距離間差別的幾何圖解。其中 f(x,y)為點(diǎn)到線的Bregman距離，δ(x,y)為點(diǎn)到線的Total-Bregman距離。當(dāng)坐標(biāo)軸發(fā)生旋轉(zhuǎn)，如圖1右圖所示時(shí)，Total-Bregman距離對(duì)旋轉(zhuǎn)更為魯棒。

Fig.1　Total-Bregman and Bregman divergences圖1　Total-Bregman距離與Bregman距離

Total-Bregman距離的定義如下：φ(·)為任意凸函數(shù)，點(diǎn)x與y間的Total-Bregman距離δ(x,y)等于：

與Bregman距離一樣，Total-Bregman距離也可直接用于FCM算法框架（或GD-FCM算法）中。

4.2結(jié)合FCM聚類框架與Total-Bregman距離的模糊聚類算法

假設(shè)FCM算法框架中的距離度量方式為Total-Bregman距離δ(xk,vi)，那么可以得到基于Total-Bregman距離的FCM聚類算法（Total-Bregman divergence based fuzzy clustering algorithm,TBD-FCM）的目標(biāo)函數(shù)如下：

受限條件為：

通過采用拉格朗日乘子法最小化目標(biāo)函數(shù)，可得新的目標(biāo)函數(shù)如下：

其中λ1,λ2,...,λn是拉格朗日乘子，通過求導(dǎo)，可得到聚類中心vk和隸屬度U的迭代公式如下：

下面來證明通過式（11）、式（12）的迭代優(yōu)化，可以得到目標(biāo)函數(shù)的極小值。首先，給出兩個(gè)定理。

定理2固定聚類中心V，Jmδ(U)的全局最小可以通過式（12）的隸屬度迭代更新得到。

證明 TBD-FCM算法的隸屬度迭代更新公式與FCM算法的迭代更新公式一樣。但在凸函數(shù)沒有給定的情況下，無法給出統(tǒng)一的證明。在歐氏距離條件下，該證明與FCM算法的證明類似[11-12]。□

定理3固定隸屬度U，Jmδ(V)的全局最小可以通過式（11）的迭代更新公式得到。

因此，通過式（11）、式（12）的迭代優(yōu)化，可以得到目標(biāo)函數(shù)的極小值。換句話說，通過固定隸屬度或聚類中心，其中一個(gè)更新另一個(gè)逐步減小目標(biāo)函數(shù)值直至其最小值，一般算法會(huì)收斂至目標(biāo)函數(shù)的局部最優(yōu)解（或鞍點(diǎn)）。

最后，給出結(jié)合模糊C均值聚類框架與Total-Bregman距離的模糊聚類算法的實(shí)現(xiàn)框架。

算法2 TBD-FCM聚類算法

其中，不同的凸函數(shù)φ(·)將導(dǎo)致不同的聚類算法。例如當(dāng)φ(x)=xTx，則得到聚類中心的迭代更新公式為v。下文將給出一些實(shí)驗(yàn)結(jié)果，以證明算法的有效性。

5　實(shí)驗(yàn)分析

本文將展示一些實(shí)驗(yàn)結(jié)果。實(shí)驗(yàn)主要圍繞兩個(gè)主題：（1）TBD-FCM算法的收斂性質(zhì)；（2）算法的聚類結(jié)果分析。

5.1實(shí)驗(yàn)設(shè)置

實(shí)驗(yàn)數(shù)據(jù)：使用一些來自UCI數(shù)據(jù)庫的實(shí)際數(shù)據(jù)。UCI數(shù)據(jù)庫是加州大學(xué)歐文分校（University of California Irvine）提出的用于機(jī)器學(xué)習(xí)的數(shù)據(jù)庫，這個(gè)數(shù)據(jù)庫是一個(gè)常用的標(biāo)準(zhǔn)測(cè)試數(shù)據(jù)集。表1列出了實(shí)驗(yàn)中使用的數(shù)據(jù)集。其中“CV”表示數(shù)據(jù)集的變異系數(shù)，該系數(shù)表示數(shù)據(jù)的類不平衡度。

實(shí)驗(yàn)工具：用Matlab作為實(shí)驗(yàn)平臺(tái)。首先，對(duì)隨機(jī)初始化隸屬度矩陣、隨機(jī)初始化聚類中心和用戶指定聚類中心這3種初始化方式進(jìn)行篩選，最終決定隨機(jī)初始化隸屬度矩陣，而后通過迭代更新對(duì)隸屬度和聚類中心進(jìn)行求解。其次，對(duì)于算法的迭代停止條件，采用Bezdek提出的迭代停止條件[17]，當(dāng)時(shí)，迭代停止。其中ε為迭代停止閾值，一般設(shè)為10-5或10-6。本文用Matlab R2010a作為編程環(huán)境實(shí)現(xiàn)算法。

Table 1　Data sets used in experiment表1　實(shí)驗(yàn)中使用數(shù)據(jù)集

Table 2　Distance measure used in experiment表2　實(shí)驗(yàn)中使用距離度量

聚類結(jié)果度量：使用來自UCI數(shù)據(jù)庫的一些實(shí)際數(shù)據(jù)集，因此這些數(shù)據(jù)是有類標(biāo)的。目前通過一個(gè)普遍適用的NVI指數(shù)（normalized variation of information）可以衡量聚類結(jié)果的準(zhǔn)確率[18]。假設(shè)包含n個(gè)數(shù)據(jù)的數(shù)據(jù)集X本身包含c′個(gè)類，實(shí)驗(yàn)中指定分類個(gè)數(shù)為c。根據(jù)得到的劃分矩陣U*，求解求和矩陣Z*：

其中，Cj′表示實(shí)際的第j類。令，NVI指數(shù)定義為：

5.2收斂性質(zhì)的分析

第4章從理論角度分析了TBD-FCM算法的收斂性質(zhì)。從結(jié)論中可以看出，在FCM聚類框架中使用Total-Bregman距離可以保證算法收斂到局部最優(yōu)值。本節(jié)通過實(shí)驗(yàn)驗(yàn)證TBD-FCM算法的收斂性。采用來自UCI數(shù)據(jù)庫的數(shù)據(jù)集（如表1所示）進(jìn)行驗(yàn)證。實(shí)驗(yàn)中主要驗(yàn)證凸函數(shù)為||x||2、xlnx和||x||時(shí)的TBD-FCM算法的收斂性。為了減少隨機(jī)初始化聚類中心帶來的影響，實(shí)驗(yàn)中對(duì)于每個(gè)凸函數(shù)每個(gè)數(shù)據(jù)集聚類10次，選擇最優(yōu)的聚類結(jié)果。實(shí)驗(yàn)最大迭代次數(shù)為50，模糊指數(shù)m=2。

表3顯示了目標(biāo)函數(shù)隨著迭代次數(shù)變化的趨勢(shì)。表中用不同顏色的曲線表示使用不同凸函數(shù)時(shí)TBD-FCM算法的目標(biāo)函數(shù)。例如，凸函數(shù)為||x||2時(shí)使用藍(lán)色線條，而凸函數(shù)為xlnx時(shí)使用紅色線條。

從表3中可以看出，TBD-FCM算法的目標(biāo)函數(shù)在這些數(shù)據(jù)集上均表現(xiàn)出單調(diào)下降的趨勢(shì)。實(shí)驗(yàn)中，對(duì)每個(gè)數(shù)據(jù)集每種凸函數(shù)均聚類10次，每次結(jié)果中，目標(biāo)函數(shù)都呈單調(diào)遞減趨勢(shì)。這也表示，TBD-FCM算法對(duì)于大多數(shù)的數(shù)據(jù)而言，具有較好的收斂性。

5.3TBD-FCM算法的聚類結(jié)果分析

上節(jié)從實(shí)驗(yàn)角度證明了TBD-FCM算法具有收斂性，可以通過迭代更新收斂到局部最優(yōu)點(diǎn)。但在實(shí)際的聚類過程中，人們更為關(guān)心算法的聚類結(jié)果。

下面對(duì)TBD-FCM算法的聚類結(jié)果進(jìn)行分析。仍然采用表3中的數(shù)據(jù)集進(jìn)行聚類分析。然后用式（14）給出的NVI指數(shù)對(duì)聚類結(jié)果進(jìn)行評(píng)價(jià)，NVI越大表明聚類結(jié)果越差。結(jié)果在表4中展示。通過對(duì)比基于Bregman距離的模糊聚類算法以及結(jié)合模糊C均值聚類框架與Total-Bregman距離的模糊聚類算法的聚類結(jié)果可以看出，通過將Bregman距離改為Total-Bregman距離，可以提升聚類的精確度。在大多數(shù)情況下，使用同樣的凸函數(shù)對(duì)同樣的數(shù)據(jù)集進(jìn)行聚類，TBD-FCM算法聚類結(jié)果的NVI值比GD-FCM算法聚類結(jié)果的NVI值小，說明使用Total-Bregman距離比使用Bregman距離有更好的聚類效果。

Table 3　Convergence properties of TBD-FCM algorithm表3　TBD-FCM算法收斂性質(zhì)分析

Table 4　Clustering result of TBD-FCM algorithm and GD-FCM algorithm表4　TBD-FCM算法和GD-FCM算法聚類結(jié)果分析

6　結(jié)束語

聚類算法在很多科學(xué)領(lǐng)域均得到了非常廣泛的應(yīng)用，同時(shí)，怎樣提升聚類結(jié)果的精確度，也成為機(jī)器學(xué)習(xí)研究的熱點(diǎn)。近年來，專家學(xué)者們對(duì)原有的聚類算法進(jìn)行改進(jìn)或提出新的聚類算法，為更好地對(duì)數(shù)據(jù)進(jìn)行聚類做出了顯著的貢獻(xiàn)。本文旨在介紹結(jié)合模糊C均值聚類框架與Total-Bregman距離的模糊聚類算法，分析其優(yōu)劣性質(zhì)，并從理論和實(shí)驗(yàn)角度證明算法的收斂性，為更好地應(yīng)用該聚類算法提供參考。并且通過實(shí)驗(yàn)驗(yàn)證了提出的TBD-FCM算法較GD-FCM算法有更好的聚類效果。當(dāng)然，本文沒有對(duì)所有的結(jié)合模糊C均值聚類框架與Total-Bregman距離的模糊聚類算法進(jìn)行分析，只對(duì)其中一部分的算法進(jìn)行了分析和實(shí)驗(yàn)驗(yàn)證，以后會(huì)繼續(xù)研究結(jié)合模糊C均值聚類框架與Total-Bregman距離的模糊聚類算法，對(duì)更多的距離度量下的算法性能進(jìn)行分析。

References:

[1]Bai Xue,Luo Siwei,Huang Yaping.Similarity measures in cluster analysis and its applications[D].Beijing:Beijing Jiaotong University,2012.

[2]Everitt B S.Cluster analysis[M].London:Halstead Press, 1974.

[3]Zhang Li,Zhou Weida,Jiao Licheng.Kernel clustering algorithm[J].Chinese Journal of Computers,2002,25(6):587-590.

[4]Zadeh L A.Fuzzy sets[J].Information and Control,1965,8 (3):338-353.

[5]Dunn J C.A fuzzy relative of the ISODATA process and its use in detecting compact well separated clusters[J].Journal of Cybernetics,1974,3(3):32-57.

[6]Lu Qiugen.The research and realization of fuzzy clustering algorithm[J].Computer Knowledge and Technology,2008, 3(9):1987-1990.

[7]Gustafson D E,Kessel W C.Fuzzy clustering with a fuzzy covariance matrix[C]//Proceedings of the 1978 IEEE Conference on Decision and Control,San Diego,USA,Jan 10-12,1979.Piscataway,USA:IEEE,1979:761-766.

[8]Krishnapuram R,Kim J.A note on the Gustafson-Kessel and adaptive fuzzy clustering algorithms[J].IEEE Transactions on Fuzzy Systems,1999,7(4):453-461.

[9]Wu K L,Yang M S.Alternative C-means clustering algorithms[J].Pattern recognition,2002,35(10):2267-2278.

[10]Yang M S,Wu K L,Yu J.Anovel fuzzy clustering algorithm [C]//Proceedings of the 2003 IEEE International Symposium on Computational Intelligence in Robotics and Automation.Piscataway,USA:IEEE,2003,2:647-652.

[11]Wu Junjie,Xiong Hui,Liu Chen,et al.A generalization of distance functions for fuzzy C-means clustering with centroids of arithmetic means[J].IEEE Transactions on Fuzzy Systems,2012,20(3):557-571.

[12]Hathaway R,Bezdek J,Tucker W.An improved convergence theory for the fuzzy C-means clustering algorithms[J]. Analysis of Fuzzy Information,1987,3:123-131.

[13]Shen Guowei,Yang Wu,Wang Wei,et al.Agglomerative hier-archical co-clustering based on bregman divergence[M]// Recent Advances on Soft Computing and Data Mining.Berlin:Springer International Publishing,2014:389-398.

[14]Nielsen F,Nock R.Optimal interval clustering:application to Bregman clustering and statistical mixture learning[J]. arXiv:1403.2485,2014.

[15]Iyer R,Bilmes J A.The Lovász-Bregman divergence and connections to rank aggregation,clustering,and Web ranking[J]. arXiv:1408.2062,2014.

[16]Groen P D.An introduction to total least squares[J].Nieuw Archief voor Wiskunde,1996,14(4):237-253.

[17]Bezdek J C.Pattern recognition with fuzzy objective function algorithms[M].[S.l.]:Springer US,1981. [18]Wu Junjie,Xiong Hui,Chen Jian.Adapting the right measures for k-means clustering[C]//Proceedings of the 15th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining,Paris,France,Jun 28-Jul 1, 2009.New York,USA:ACM,2009:877-886.

附中文參考文獻(xiàn)：

[1]白雪,羅四維,黃雅平.聚類分析中的相似性度量及其應(yīng)用研究[D].北京:北京交通大學(xué),2012.

[3]張莉,周偉達(dá),焦李成.核聚類算法[J].計(jì)算機(jī)學(xué)報(bào),2002, 25(6):587-590.

[6]盧秋根.模糊聚類算法的研究與實(shí)現(xiàn)[J].電腦知識(shí)與技術(shù),2008,3(9):1987-1990.

Chaomurilige was born in 1988.She is a Ph.D.candidate at School of Computer and Information Technology,Beijing Jiaotong University.Her research interests include machine learning and clustering analysis,etc.

超木日力格（1988—），女，內(nèi)蒙古通遼人，北京交通大學(xué)計(jì)算機(jī)與信息技術(shù)學(xué)院博士研究生，主要研究領(lǐng)域?yàn)闄C(jī)器學(xué)習(xí)，聚類分析等。

于劍（1969—），男，山東人，2000年于北京大學(xué)應(yīng)用數(shù)學(xué)專業(yè)獲得博士學(xué)位，現(xiàn)為北京交通大學(xué)計(jì)算機(jī)與信息技術(shù)學(xué)院教授、博士生導(dǎo)師，交通數(shù)據(jù)分析與挖掘北京市重點(diǎn)實(shí)驗(yàn)主任，CCF高級(jí)會(huì)員，主要研究領(lǐng)域?yàn)闄C(jī)器學(xué)習(xí)，圖像處理，模式識(shí)別等。

ZHU Jie was born in 1982.He is a Ph.D.candidate at School of Computer and Information Technology,Beijing Jiaotong University.His research interests include machine learning and computer vision,etc.

朱杰（1982—），男，河北保定人，北京交通大學(xué)計(jì)算機(jī)與信息技術(shù)學(xué)院博士研究生，主要研究領(lǐng)域?yàn)闄C(jī)器學(xué)習(xí)，機(jī)器視覺等。

Fuzzy ClusteringAlgorithm Based on Total-Bregman Divergence*

Chaomurilige1,YU Jian1+,ZHU Jie1,2
1.Beijing Key Lab of Traffic Data Analysis and Mining,School of Computer and Information Technology,Beijing Jiaotong University,Beijing 100044,China
2.Department of Information Management,The Central Institute for Correctional Police,Baoding,Hebei 071000,China
+Corresponding author:E-mail:jianyu@bjtu.edu.cn

The fuzzy C-means(FCM)clustering algorithm is one of the widely used clustering algorithms based on the minimization of objective function.Several clustering algorithms,such as AFCM algorithm and GK algorithm, are the extension and improvement of FCM clustering algorithm.This paper introduces Total-Bregman divergence into the FCM clustering framework and proposes an algorithm named fuzzy clustering algorithm based on total-Bregman divergence(TBD-FCM),which is an improvement of the fuzzy clustering algorithm based on Bregman divergence.Then this paper analyzes the convergence properties of this algorithm.In experiment part,several clustering results on the datasets from the UCI repository have been shown to prove the effectiveness and the convergence properties of clustering algorithm.

clustering algorithm;fuzzy clustering;Total-Bregman divergence

2015-05,Accepted 2015-08.

YU Jian was born in 1969.He the Ph.D.degree in applied mathematics from Peking University in 2000. Now he is a professor and Ph.D.supervisor at Beijing Jiaotong University,the director of the Beijing Key Lab of Traffic Data Analysis and Mining,and the senior member of CCF.His research interests include machine learning, image processing and pattern recognition,etc.

10.3778/j.issn.1673-9418.1505054

*The National Natural Science Foundation of China under Grant No.61370129(國家自然科學(xué)基金);the Specialized Research Fund for the Doctoral Program of Higher Education of China under Grant No.20120009110006(高等學(xué)校博士學(xué)科點(diǎn)專項(xiàng)科研基金).

CNKI網(wǎng)絡(luò)優(yōu)先出版：2015-08-12,http://www.cnki.net/kcms/detail/11.5602.tp.20150812.1636.007.html

A

TP301