焦存德

（陽泉師范高等?？茖W(xué)校數(shù)學(xué)系， 山西 陽泉 045200）

1 序言

聚類是根據(jù)一定的標(biāo)準(zhǔn) （通常是距離標(biāo)準(zhǔn)）將一個(gè)數(shù)據(jù)集劃分為不同的類， 使類內(nèi)的相似性盡可能大， 類間的差異性盡可能大。 FCM（Fuzzy C-means） 聚類是一種與數(shù)據(jù)挖掘、 模式識(shí)別等研究方向相關(guān)的重要研究內(nèi)容之一。 聚類算法的聚類結(jié)果是不可預(yù)測(cè)的。 在實(shí)際應(yīng)用中，應(yīng)根據(jù)數(shù)據(jù)類型選擇合適的相似度測(cè)量方法， 便于有相對(duì)更合適的聚類效果［1］。 當(dāng)然不一樣的相似性度量方式又對(duì)應(yīng)著不一樣的距離準(zhǔn)則， 所以研究不同距離下的FCM 算法比較有著重要意義［2-4］。

2 正文

設(shè)X=（x1， x2， …， xn）， b=（y1， y2， …， yn）為被分類對(duì)象的全體， 設(shè)每一組對(duì)象由一組特征數(shù)據(jù) （xi1， xi2， …， xim） 來表征。 X 的模糊c-劃分指的是由模糊c-劃分矩陣A=（A1， A2， …，An）T=（aij）cn， aij∈［0， 1］

決定的劃分{Ai|i=1， 2， …， c} 的劃分， 滿

所有模糊c-劃分組成模糊c-劃分空間。

最優(yōu)模糊c-劃分使下面的J（A， V） 取得最小值：

其中， 參數(shù)r 不小于1， r 越大分類越模糊；vi是Ai類的聚類中心， 定義為

構(gòu)造下面的目標(biāo)函數(shù)， 可得到 （*） 式達(dá)到最小值的必要條件：

記

這里λj， j=1， 2…n 是（*） 的n 個(gè)約束式的拉格朗日乘子［5］。

對(duì)所有參變量求導(dǎo)， 是 （**） 達(dá)到最小值的必要條件為

則J （A， V） 取得最小值， 即此時(shí)可得到最優(yōu)模糊c-劃分。

（2） 當(dāng)距離標(biāo)準(zhǔn)為曼哈頓距離時(shí)， 則J （A，

得最小值， 即此時(shí)可得到最優(yōu)模糊c-劃分。

得最小值， 即此時(shí)可得到最優(yōu)模糊c-劃分。

（4） 當(dāng)距離標(biāo)準(zhǔn)為閔可夫斯基距離時(shí)， J （A，

即此時(shí)可得到最優(yōu)模糊c-劃分。

V）取得最小值， 即此時(shí)可得到最優(yōu)模糊c-劃分。

J（A， V） 取得最小值， 即此時(shí)可得到最優(yōu)模糊c-劃分

則J（A， V）取得最小值， 即此時(shí)可得到最優(yōu)模糊c-劃分

通過上面的分析我們可以得到FCM 算法是一個(gè)簡單的迭代過程。 所以在實(shí)現(xiàn)Matlab 仿真時(shí)， 我們采用迭代算法。 在Matlab 中， 已經(jīng)有基于歐氏距離的FCM 算法， 我們查找到了該程序的源代碼， 并找到其中決定算法結(jié)果的距離函數(shù)， 將其先后替換為前文中提到的幾種距離， 進(jìn)行了實(shí)驗(yàn)分析仿真。 同時(shí)， 我們聚類的對(duì)象有兩個(gè)， 一是隨機(jī)分布的數(shù)據(jù)， 一是高斯分布的數(shù)據(jù)。 對(duì)這兩種數(shù)據(jù)的聚類算法分別如下：

（一） 基于隨機(jī)分布的數(shù)據(jù)的最優(yōu)c-劃分

步驟1： 產(chǎn)生隨機(jī)分布的數(shù)據(jù)， 即隨機(jī)數(shù)；

步驟2： 任選c 個(gè)數(shù)據(jù)對(duì)象為初始類中心，

步驟3： 重復(fù)

①計(jì)算每個(gè)數(shù)據(jù)到各類中心的距離， 并將其分配到距離最小的類中；

②計(jì)算新的類的中心 （可以不是被聚類的數(shù)據(jù)）， 直到J（A， V） 相對(duì)上次J（A， V） 的改變量小于某個(gè)閥值 （在本文中我們選擇該值為10-5）， 則循環(huán)停止；

步驟4： 繪圖， 使聚類結(jié)果更直觀地表現(xiàn)出來。

本文將采用的實(shí)驗(yàn)方法基于隨機(jī)生成的隨機(jī)分布的二維數(shù)組 （共生成20 組）， 分別使用上述7 種距離對(duì)每組測(cè)試數(shù)據(jù)采取FCM 聚類， 同時(shí)記錄在不同距離下的聚類結(jié)果， 利用統(tǒng)計(jì)方法分析比較了聚類方法在7 個(gè)距離下的性能。 下圖為同一組測(cè)試數(shù)據(jù)在聚類數(shù)c=2 或3 下的聚類結(jié)果。

圖1 c=2 時(shí)7 種距離下隨機(jī)數(shù)據(jù)的聚類結(jié)果

圖2 c=3 時(shí)7 種距離下隨機(jī)數(shù)據(jù)的聚類結(jié)果

當(dāng)c=2 時(shí)， 根據(jù)同一點(diǎn)的分布區(qū)域的特點(diǎn)，本文對(duì)20 個(gè)測(cè)試數(shù)據(jù)集進(jìn)行了聚類。 結(jié)果分為4類， 分別定義為A 類、 B 類、 C 類和D 類， 每種類型的分布如圖3 所示。

圖3 c=2 時(shí)聚類結(jié)果的4 種類型

同樣， 當(dāng)測(cè)c=3 時(shí)， 所有20 個(gè)測(cè)試數(shù)據(jù)集的聚類結(jié)果根據(jù)其概括根據(jù)相似點(diǎn)的形狀的不同， 可分為6 類， 分別被定義為類型A、 B、 C、D、 E、 F， 其分布圖如圖4 所示。

圖4 c=3 時(shí)聚類結(jié)果的6 種類型

根據(jù)上述分類方法， 對(duì)所有測(cè)試數(shù)據(jù)的聚類結(jié)果進(jìn)行分類并記錄。

表1 不同距離下的FCM （c=2） 聚類結(jié)果統(tǒng)計(jì)

表2 不同距離下的FCM （c=3） 聚類結(jié)果統(tǒng)計(jì)

表1 和表2 表明無論聚類分類數(shù)是2 或3，所有依據(jù)形狀相似距離為聚類結(jié)果的都?xì)w為同種類型中。 因此形狀相似距離在解決基于隨機(jī)分布的數(shù)據(jù)的最優(yōu)c-劃分的問題更有優(yōu)勢(shì)。

（二） 基于高斯分布的數(shù)據(jù)的最優(yōu)c-劃分

仿照隨機(jī)分布的實(shí)驗(yàn)方法， 在這一部分， 我們用MATLAB 產(chǎn)生高斯分布的二維數(shù)組作為測(cè)試數(shù)據(jù)（共生成20 組）， 用標(biāo)準(zhǔn)FCM 聚類算法，分別采用7 種距離對(duì)每組測(cè)試數(shù)據(jù)采取FCM 聚類， 同時(shí)記錄在不同距離下的聚類結(jié)果， 利用統(tǒng)計(jì)方法分析比較了聚類方法在7 個(gè)距離下的性能。 本文規(guī)定分類數(shù)c=2 或3。

圖5 c=2 時(shí)7 種距離下高斯分布的聚類結(jié)果

圖6 c=3 時(shí)7 種距離下高斯分布的聚類結(jié)果

（3） 結(jié)果分析

由上面的圖5 和圖6 可以看到無論是c=2 還是3， 不同距離下的高斯分布數(shù)據(jù)集的聚類結(jié)果并無大差異。

3 結(jié)論

本文給出了歐式距離、 曼哈頓距離、 切比雪夫距離、 閔可夫斯基距離、 標(biāo)準(zhǔn)化歐式距離、 馬式距離和形狀相似距離的FCM 算法公式。 為了比較這些算法的好壞， 我們使用Matlab 本文的算法應(yīng)用于兩種類型的數(shù)據(jù)分別進(jìn)行聚類， 并分析結(jié)果。 本文的主要結(jié)論是當(dāng)數(shù)據(jù)是隨機(jī)分布的，形狀相似性距離可分為結(jié)合對(duì)象大小和形狀相似性的兩個(gè)因素。 因此， 在這種情況下， 形狀相似的距離比其他距離更合適。 然而， 不同距離的高斯數(shù)據(jù)集聚類結(jié)果沒有顯著差異。