聚類(lèi)就是按照某個(gè)特定標(biāo)準(zhǔn)（如距離準(zhǔn)則，即數(shù)據(jù)點(diǎn)之間的距離）把一個(gè)數(shù)據(jù)集分割成不同的類(lèi)或簇，使得同一個(gè)簇內(nèi)的數(shù)據(jù)對(duì)象的相似性盡可能大，同時(shí)不在同一個(gè)簇中的數(shù)據(jù)對(duì)象的差異性也盡可能地大。我們可以具體地理解為，聚類(lèi)后同一類(lèi)的數(shù)據(jù)盡可能聚集到一起，不同類(lèi)數(shù)據(jù)盡量分離。

聚類(lèi)技術(shù)正在蓬勃發(fā)展，對(duì)此有貢獻(xiàn)的研究領(lǐng)域包括數(shù)據(jù)挖掘、統(tǒng)計(jì)學(xué)、機(jī)器學(xué)習(xí)、空間數(shù)據(jù)庫(kù)技術(shù)、生物學(xué)以及市場(chǎng)營(yíng)銷(xiāo)等。各種聚類(lèi)方法也被不斷提出和改進(jìn)，而不同的方法適合于不同類(lèi)型的數(shù)據(jù)，因此對(duì)各種聚類(lèi)方法、聚類(lèi)效果的比較成為值得研究的課題。

聚類(lèi)分析法是理想的多變量統(tǒng)計(jì)技術(shù)，主要有分層聚類(lèi)法和迭代聚類(lèi)法。 聚類(lèi)分析也稱(chēng)群分析、點(diǎn)群分析，是研究分類(lèi)的一種多元統(tǒng)計(jì)方法。

例如，我們可以根據(jù)各個(gè)銀行網(wǎng)點(diǎn)的儲(chǔ)蓄量、人力資源狀況、營(yíng)業(yè)面積、特色功能、網(wǎng)點(diǎn)級(jí)別、所處功能區(qū)域等因素情況，將網(wǎng)點(diǎn)分為幾個(gè)等級(jí)，再比較各銀行之間不同等級(jí)網(wǎng)點(diǎn)數(shù)量對(duì)比狀況。

聚類(lèi)算法的分類(lèi)

目前，有大量的聚類(lèi)算法。而對(duì)于具體應(yīng)用，聚類(lèi)算法的選擇取決于數(shù)據(jù)的類(lèi)型、聚類(lèi)的目的。如果聚類(lèi)分析被用作描述或探查的工具，可以對(duì)同樣的數(shù)據(jù)嘗試多種算法，以發(fā)現(xiàn)數(shù)據(jù)可能揭示的結(jié)果。

主要的聚類(lèi)算法可以劃分為如下幾類(lèi)：劃分方法、層次方法、基于密度的方法、基于網(wǎng)格的方法以及基于模型的方法。

目前，聚類(lèi)問(wèn)題的研究不僅僅局限于上述的硬聚類(lèi)，即每一個(gè)數(shù)據(jù)只能被歸為一類(lèi)，模糊聚類(lèi)［10］也是聚類(lèi)分析中研究較為廣泛的一個(gè)分支。模糊聚類(lèi)通過(guò)隸屬函數(shù)來(lái)確定每個(gè)數(shù)據(jù)隸屬于各個(gè)簇的程度，而不是將一個(gè)數(shù)據(jù)對(duì)象硬性地歸類(lèi)到某一簇中。目前已有很多關(guān)于模糊聚類(lèi)的算法被提出，如著名的FCM算法等，此方法后面會(huì)提及。

常用的聚類(lèi)方法

1.k-mean聚類(lèi)分析 適用于樣本聚類(lèi)；

2.分層聚類(lèi) 適用于對(duì)變量聚類(lèi)；

3.兩步聚類(lèi) 適用于分類(lèi)變量和連續(xù)變量聚類(lèi)；

4.基于密度的聚類(lèi)算法；

5.基于網(wǎng)絡(luò)的聚類(lèi)；

6.機(jī)器學(xué)習(xí)中的聚類(lèi)算法；

前3種，可用spss簡(jiǎn)單操作實(shí)現(xiàn)；

四種常用聚類(lèi)算法研究

k-means聚類(lèi)算法

k-means是劃分方法中較經(jīng)典的聚類(lèi)算法之一。由于該算法的效率高，所以在對(duì)大規(guī)模數(shù)據(jù)進(jìn)行聚類(lèi)時(shí)被廣泛應(yīng)用。目前，許多算法均圍繞著該算法進(jìn)行擴(kuò)展和改進(jìn)。

k-means算法目標(biāo)是，以k為參數(shù)，把n個(gè)對(duì)象分成k個(gè)簇，使簇內(nèi)具有較高的相似度，而簇間的相似度較低。

k-means算法的處理過(guò)程如下：首先，隨機(jī)地 選擇k個(gè)對(duì)象，每個(gè)對(duì)象初始地代表了一個(gè)簇的平均值或中心;對(duì)剩余的每個(gè)對(duì)象，根據(jù)其與各簇中心的距離，將它賦給最近的簇;然后重新計(jì)算每個(gè)簇的平均值。 這個(gè)過(guò)程不斷重復(fù)，直到準(zhǔn)則函數(shù)收斂。通常，采用平方誤差準(zhǔn)則，其定義如下：

這里E是數(shù)據(jù)庫(kù)中所有對(duì)象的平方誤差的總和，p是空間中的點(diǎn)，mi是簇Ci的平均值［9］。該目標(biāo)函數(shù)使生成的簇盡可能緊湊獨(dú)立，使用的距離度量是歐幾里得距離，當(dāng)然也可以用其他距離度量。k-means聚類(lèi)算法的算法流程如下：

輸入：包含n個(gè)對(duì)象的數(shù)據(jù)庫(kù)和簇的數(shù)目k；

輸出：k個(gè)簇，使平方誤差準(zhǔn)則最小。

步驟：

（1） 任意選擇k個(gè)對(duì)象作為初始的簇中心；

（2） repeat；

（3） 根據(jù)簇中對(duì)象的平均值，將每個(gè)對(duì)象（重新）賦予最類(lèi)似的簇；

（4） 更新簇的平均值，即計(jì)算每個(gè)簇中對(duì)象的平均值；

（5） until不再發(fā)生變化。

總結(jié)：

優(yōu)點(diǎn)：簡(jiǎn)單直接（體現(xiàn)在邏輯思路以及實(shí)現(xiàn)難度上），易于理解，在低維數(shù)據(jù)集上有不錯(cuò)的效果（簡(jiǎn)單的算法不見(jiàn)得就不能得到優(yōu)秀的效果）。

缺點(diǎn)：對(duì)于高維數(shù)據(jù)（如成百上千維，現(xiàn)實(shí)中還不止這么多），其計(jì)算速度十分慢，主要是慢在計(jì)算距離上（參考?xì)W幾里得距離，當(dāng)然并行化處理是可以的，這是算法實(shí)現(xiàn)層面的問(wèn)題），它的另外一個(gè)缺點(diǎn)就是它需要我們?cè)O(shè)定希望得到的聚類(lèi)數(shù)k，若我們對(duì)于數(shù)據(jù)沒(méi)有很好的理解，那么設(shè)置k值就成了一種估計(jì)性的工作。

層次聚類(lèi)算法

根據(jù)層次分解的順序是自底向上的還是自上向下的，層次聚類(lèi)算法分為凝聚的層次聚類(lèi)算法和分裂的層次聚類(lèi)算法。

凝聚型層次聚類(lèi)的策略是先將每個(gè)對(duì)象作為一個(gè)簇，然后合并這些原子簇為越來(lái)越大的簇，直到所有對(duì)象都在一個(gè)簇中，或者某個(gè)終結(jié)條件被滿(mǎn)足。絕大多數(shù)層次聚類(lèi)屬于凝聚型層次聚類(lèi)，它們只是在簇間相似度的定義上有所不同。四種廣泛采用的簇間距離度量方法如下：

這里給出采用最小距離的凝聚層次聚類(lèi)算法流程：

（1） 將每個(gè)對(duì)象看作一類(lèi)，計(jì)算兩兩之間的最小距離；

（2） 將距離最小的兩個(gè)類(lèi)合并成一個(gè)新類(lèi)；

（3） 重新計(jì)算新類(lèi)與所有類(lèi)之間的距離；

（4） 重復(fù)（2）、（3），直到所有類(lèi)最后合并成一類(lèi)。

總結(jié)：

優(yōu)點(diǎn)：

1，距離和規(guī)則的相似度容易定義，限制少；

2，不需要預(yù)先制定聚類(lèi)數(shù)；

3，可以發(fā)現(xiàn)類(lèi)的層次關(guān)系（在一些特定領(lǐng)域如生物有很大作用）；

缺點(diǎn)：

1，計(jì)算復(fù)雜度太高（考慮并行化）；

2，奇異值也能產(chǎn)生很大影響；

3，算法很可能聚類(lèi)成鏈狀（一層包含著一層）；

4，算法不需要預(yù)定聚類(lèi)數(shù)，但是我們選擇哪個(gè)層次的聚類(lèi)作為我們需要的聚類(lèi)效果，這需要我們按照實(shí)際客觀情況以及經(jīng)驗(yàn)來(lái)完成，畢竟就凝聚聚類(lèi)來(lái)說(shuō)，從最底層的每個(gè)個(gè)體作為一個(gè)個(gè)體，到最頂層所有個(gè)體合并為一個(gè)個(gè)體，其中的聚類(lèi)結(jié)果可能有許許多多種。

當(dāng)然針對(duì)這個(gè)問(wèn)題也有許多解決方案，其中一個(gè)常用的就是凝聚到某個(gè)程度其聚類(lèi)之間的距離都大于某個(gè)閾值k，就停止凝聚。

SOM聚類(lèi)算法

SOM神經(jīng)網(wǎng)絡(luò)［11］是由芬蘭神經(jīng)網(wǎng)絡(luò)專(zhuān)家Kohonen教授提出的，該算法假設(shè)在輸入對(duì)象中存在一些拓?fù)浣Y(jié)構(gòu)或順序，可以實(shí)現(xiàn)從輸入空間（n維）到輸出平面（2維）的降維映射，其映射具有拓?fù)涮卣鞅３中再|(zhì)，與實(shí)際的大腦處理有很強(qiáng)的理論聯(lián)系。

SOM網(wǎng)絡(luò)包含輸入層和輸出層。輸入層對(duì)應(yīng)一個(gè)高維的輸入向量，輸出層由一系列組織在2維網(wǎng)格上的有序節(jié)點(diǎn)構(gòu)成，輸入節(jié)點(diǎn)與輸出節(jié)點(diǎn)通過(guò)權(quán)重向量連接。 學(xué)習(xí)過(guò)程中，找到與之距離最短的輸出層單元，即獲勝單元，對(duì)其更新。同時(shí)，將鄰近區(qū)域的權(quán)值更新，使輸出節(jié)點(diǎn)保持輸入向量的拓?fù)涮卣鳌?/p>

算法流程：

（1） 網(wǎng)絡(luò)初始化，對(duì)輸出層每個(gè)節(jié)點(diǎn)權(quán)重賦初值；

（2） 將輸入樣本中隨機(jī)選取輸入向量，找到與輸入向量距離最小的權(quán)重向量；

（3） 定義獲勝單元，在獲勝單元的鄰近區(qū)域調(diào)整權(quán)重使其向輸入向量靠攏；

（4） 提供新樣本、進(jìn)行訓(xùn)練；

（5） 收縮鄰域半徑、減小學(xué)習(xí)率、重復(fù)，直到小于允許值，輸出聚類(lèi)結(jié)果。

FCM聚類(lèi)算法

1965年美國(guó)加州大學(xué)柏克萊分校的扎德教授第一次提出了‘集合’的概念。經(jīng)過(guò)十多年的發(fā)展，模糊集合理論漸漸被應(yīng)用到各個(gè)實(shí)際應(yīng)用方面。為克服非此即彼的分類(lèi)缺點(diǎn)，出現(xiàn)了以模糊集合論為數(shù)學(xué)基礎(chǔ)的聚類(lèi)分析。用模糊數(shù)學(xué)的方法進(jìn)行聚類(lèi)分析，就是模糊聚類(lèi)分析［12］。

FCM算法是一種以隸屬度來(lái)確定每個(gè)數(shù)據(jù)點(diǎn)屬于某個(gè)聚類(lèi)程度的算法。該聚類(lèi)算法是傳統(tǒng)硬聚類(lèi)算法的一種改進(jìn)。

算法流程：

（1） 標(biāo)準(zhǔn)化數(shù)據(jù)矩陣；

（2） 建立模糊相似矩陣，初始化隸屬矩陣；

（3） 算法開(kāi)始迭代，直到目標(biāo)函數(shù)收斂到極小值；

（4） 根據(jù)迭代結(jié)果，由最后的隸屬矩陣確定數(shù)據(jù)所屬的類(lèi)，顯示最后的聚類(lèi)結(jié)果。

總結(jié)：

優(yōu)點(diǎn)：相比起前面的”硬聚類(lèi)“，F(xiàn)CM方法會(huì)計(jì)算每個(gè)樣本對(duì)所有類(lèi)的隸屬度，這給了我們一個(gè)參考該樣本分類(lèi)結(jié)果可靠性的計(jì)算方法，我們可以這樣想，若某樣本對(duì)某類(lèi)的隸屬度在所有類(lèi)的隸屬度中具有絕對(duì)優(yōu)勢(shì)，則該樣本分到這個(gè)類(lèi)是一個(gè)十分保險(xiǎn)的做法，反之若該樣本在所有類(lèi)的隸屬度相對(duì)平均，則我們需要其他輔助手段來(lái)進(jìn)行分類(lèi)。

缺點(diǎn)：KNN的缺點(diǎn)基本它都有。

四種聚類(lèi)算法試驗(yàn)

試驗(yàn)數(shù)據(jù)

實(shí)驗(yàn)中，選取專(zhuān)門(mén)用于測(cè)試分類(lèi)、聚類(lèi)算法的國(guó)際通用的UCI數(shù)據(jù)庫(kù)中的IRIS［13］數(shù)據(jù)集，IRIS數(shù)據(jù)集包含150個(gè)樣本數(shù)據(jù)，分別取自三種不同 的鶯尾屬植物setosa、versicolor和virginica的花朵樣本，每個(gè)數(shù)據(jù)含有4個(gè)屬性，即萼片長(zhǎng)度、萼片寬度、花瓣長(zhǎng)度，單位為cm。 在數(shù)據(jù)集上執(zhí)行不同的聚類(lèi)算法，可以得到不同精度的聚類(lèi)結(jié)果。

試驗(yàn)結(jié)果說(shuō)明

文中基于前面所述各算法原理及算法流程，用matlab進(jìn)行編程運(yùn)算，得到表1所示聚類(lèi)結(jié)果。

如表1所示，對(duì)于四種聚類(lèi)算法，按三方面進(jìn)行比較：

（1）聚錯(cuò)樣本數(shù)：總的聚錯(cuò)的樣本數(shù)，即各類(lèi)中聚錯(cuò)的樣本數(shù)的和；

（2）運(yùn)行時(shí)間：即聚類(lèi)整個(gè) 過(guò)程所耗費(fèi)的時(shí)間，單位為s；

（3）平均準(zhǔn)確度：設(shè)原數(shù)據(jù)集有k個(gè)類(lèi)，用ci表示第i類(lèi)，ni為ci中樣本的個(gè)數(shù)，mi為聚類(lèi)正確的個(gè)數(shù)，則mi/ni為 第i類(lèi)中的精度，則平均精度為：

試驗(yàn)結(jié)果分析

四種聚類(lèi)算法中，在運(yùn)行時(shí)間及準(zhǔn)確度方面綜合考慮，k-means和FCM相對(duì)優(yōu)于其他。但是，各個(gè)算法還是存在固定缺點(diǎn)：k-means聚類(lèi)算法的初始點(diǎn)選擇不穩(wěn)定，是隨機(jī)選取的，這就引起聚類(lèi)結(jié)果的不穩(wěn)定，本實(shí)驗(yàn)中雖是經(jīng)過(guò)多次實(shí)驗(yàn)取的平均值，但是具體初始點(diǎn)的選擇方法還需進(jìn)一步研究；層次聚類(lèi)雖然 不需要確定分類(lèi)數(shù)，但是一旦一個(gè)分裂或者合并被執(zhí)行，就不能修正，聚類(lèi)質(zhì)量受限制；FCM對(duì)初始聚類(lèi)中心敏感，需要人為確定聚類(lèi)數(shù)，容易陷入局部最優(yōu) 解；SOM與實(shí)際大腦處理有很強(qiáng)的理論聯(lián)系。但是處理時(shí)間較長(zhǎng)，需要進(jìn)一步研究使其適應(yīng)大型數(shù)據(jù)庫(kù)。