數(shù)種基于SPSS統(tǒng)計(jì)工具的聚類算法效率對(duì)比

呂正萍，紀(jì)漢霖

(上海理工大學(xué) 管理學(xué)院，上海 200093)

0 引言

隨著大數(shù)據(jù)技術(shù)的發(fā)展，數(shù)據(jù)挖掘技術(shù)備受關(guān)注，作為其重要組成部分的聚類分析技術(shù)已廣泛用于數(shù)據(jù)分析、圖像處理、市場(chǎng)研究等多種領(lǐng)域[1-3]。聚類分析根據(jù)數(shù)據(jù)特征將其進(jìn)行分類，盡可能突顯類與類之間的差距，使類的數(shù)據(jù)差距盡可能相近，即擁有相似特征的數(shù)據(jù)被聚為一類。聚類分析同時(shí)也是一種無監(jiān)督的學(xué)習(xí)過程，很難選擇最佳聚類分析方法并達(dá)到有效聚類個(gè)數(shù)。

目前對(duì)聚類算法的研究及應(yīng)用集中在兩個(gè)方面：

(1)聚類算法改進(jìn)。眾多專家和學(xué)者對(duì)數(shù)據(jù)聚類方法算法進(jìn)行了改進(jìn)和創(chuàng)新，包括K-means聚類、系統(tǒng)聚類、兩步聚類，以提高算法精確性與穩(wěn)定性，改善聚類性能。改進(jìn)方法主要分為3種：①通過對(duì)聚類初始中心的選擇，改善聚類有效性。程艷云、周鵬[4]提出動(dòng)態(tài)分配聚類中心的改進(jìn)K均值聚類算法，該算法改進(jìn)了K均值初始聚類中心的選取方法，直接有效地選擇出最佳初始聚類中心并進(jìn)行K均值聚類計(jì)算；周鹿揚(yáng)等[5]提出一種基于聚類中心的快速聚類算法，該方法選擇一組高密度分布的聚類中心，將聚類中心周圍的對(duì)象劃分到離其最近的聚類中心形成子簇，再根據(jù)子簇之間的連通性完成子簇合并；②對(duì)聚類過程中最佳聚類個(gè)數(shù)的研究。劉飛等[6]采用SSE對(duì)簇個(gè)數(shù)進(jìn)行度量，提出一種能夠自動(dòng)確定聚類個(gè)數(shù)的聚類方法。費(fèi)賢舉等[7]通過改寫軟子空間聚類算法的目標(biāo)函數(shù)，并結(jié)合數(shù)據(jù)簇大小對(duì)各個(gè)數(shù)據(jù)簇的影響，使聚類結(jié)果與初始聚類個(gè)數(shù)和初始聚類中心無關(guān)，達(dá)到有效的聚類分析結(jié)果；③通過對(duì)聚類算法的改進(jìn)與優(yōu)化，改善聚類有效性。朱林等[8]提出基于數(shù)據(jù)流的軟子空間聚類算法，利用模糊的可擴(kuò)展聚類算法策略，將軟子空間聚類方法應(yīng)用于流數(shù)據(jù)聚類分析，以有效應(yīng)用于高維數(shù)據(jù)流或者大規(guī)模數(shù)據(jù)的聚類研究中心。楊揚(yáng)等[9]提出基于屬性值變化程度定權(quán)的聚類算法，該算法考慮了聚類對(duì)象各屬性值對(duì)聚類劃分的影響程度，并通過ratio值對(duì)其進(jìn)行量化，從而提高聚類運(yùn)算精確度。

(2)聚類分析方法的應(yīng)用。統(tǒng)計(jì)分析軟件SPSS中三大聚類方法(K-means聚類、系統(tǒng)聚類、兩步聚類)被廣泛應(yīng)用于交通管制、圖像處理、環(huán)境監(jiān)測(cè)、商業(yè)市場(chǎng)分析等領(lǐng)域，根據(jù)聚類結(jié)果給出相關(guān)建設(shè)性建議或提出有效算法[10]。例如，楊越等[11]在簡化航路網(wǎng)中，采用歐氏距離相似性度量，對(duì)不同航路點(diǎn)的時(shí)間序列進(jìn)行系統(tǒng)聚類，劃設(shè)應(yīng)急航路，減累地面空管單位的管制壓力。夏晨木等[12]通過運(yùn)用K-means聚類方法，將裂縫表面的三角網(wǎng)格進(jìn)行分類，實(shí)現(xiàn)與普通孔隙表面三角網(wǎng)格分離和區(qū)分的結(jié)果，以此提出一種新的巖石三維圖像裂縫提取算法。孫亞男等[13]應(yīng)用聚類分析方法研究長三角地區(qū)大氣污染的城市聯(lián)動(dòng)及動(dòng)態(tài)交互影響，以提升大氣污染聯(lián)防聯(lián)控成效。還有研究將聚類方法應(yīng)用于投資者P2P網(wǎng)貸平臺(tái)的選擇[14]、商品精確營銷[15]、圖像分割處理[16]等。以上研究關(guān)注于聚類方法的應(yīng)用及聚類與其它方法的結(jié)合，并沒有對(duì)不同聚類方法的有效性進(jìn)行比較。

本文以SPSS為聚類工具，使用EXCEL中VBA計(jì)算分析數(shù)據(jù)點(diǎn)之間的距離，對(duì)比分析各種聚類算法之間的優(yōu)劣，并給出相應(yīng)結(jié)論。

1 聚類原理

聚類分析是一種建立分類的多元統(tǒng)計(jì)分析方法，能將一批樣本(或變量)數(shù)據(jù)根據(jù)其諸多特征，在沒有先驗(yàn)知識(shí)的情況下,按照性質(zhì)的親疏程度進(jìn)行自動(dòng)分類，產(chǎn)生多個(gè)分類結(jié)果，其結(jié)果是同一個(gè)類之內(nèi)的個(gè)體特征具有相似性，不同類的個(gè)體特征差異性較大。

一般采用不同距離公式會(huì)得到不同分類結(jié)果，本文采用歐式距離進(jìn)行分類。

2 SPSS聚類模型概述

SPSS是一款成熟的統(tǒng)計(jì)軟件，其聚類模型在業(yè)內(nèi)具有典型的代表意義，SPSS目前采用K-means、系統(tǒng)聚類、兩步聚類3種聚類方法。

2.1 K-means聚類

K-means聚類方法也稱快速聚類，是一種應(yīng)用廣泛的經(jīng)典聚類算法，將數(shù)據(jù)看成K維空間上的點(diǎn)，以歐式距離作為測(cè)度個(gè)體“親疏程度”的指標(biāo)，模型收斂速度快，算法簡單，并能有效處理大數(shù)據(jù)集，不過該方法只能處理連續(xù)的樣本數(shù)據(jù)。形式最簡單的算法包括以下3個(gè)步驟：

(1)將所有變量分成K個(gè)初始聚類。

(3)重復(fù)步驟(2)，直到所有類的核心不再改變?yōu)橹埂?/p>

K-means聚類只能產(chǎn)生指定類數(shù)的聚類結(jié)果，在應(yīng)用K-means聚類分析方法時(shí)，對(duì)于變量之間存在較大差異時(shí)，通常先采用標(biāo)準(zhǔn)化處理，再進(jìn)行下一步聚類分析。因此，K-means聚類又分為K-means未標(biāo)準(zhǔn)化聚類和K-means標(biāo)準(zhǔn)化聚類。

2.2 系統(tǒng)聚類

系統(tǒng)聚類(Hierarchical Clustering)分析法又稱層次聚類分析法，是根據(jù)觀察值或變量之間的親疏程度，將最相似的對(duì)象結(jié)合在一起，以逐次聚類的方式將觀察值分類，直到最后所有樣本都聚成一類。該方法既可以處理連續(xù)變量，也可用于名義變量的處理。

系統(tǒng)聚類過程[17]為：

(1)假設(shè)總共有n個(gè)變量，將每個(gè)變量獨(dú)自聚為一類，共有n類。

(2)根據(jù)變量距離公式，把距離較近的兩個(gè)變量聚合為一類，其它變量仍各自聚為一類，共聚成n～1類。

(3)將“距離”最近的兩個(gè)類進(jìn)一步聚成一類，共聚成n～2類。

以上步驟持續(xù)進(jìn)行，直到聚合的數(shù)目達(dá)到預(yù)定為止。進(jìn)行系統(tǒng)聚類之前，需要定義類間距離，根據(jù)類間距離定義的不同，形成不同的聚類方法，常用的類間距離定義有類平均法、可變類平均法、可變法、最短距離法、最長距離法、中間距離法和離差平方和法。本文運(yùn)用離差平方和法，該方法又稱Ward法，其原理是同類變量的離差平方和應(yīng)當(dāng)較小，類與類的離差平方和較大，按常規(guī)將數(shù)值標(biāo)準(zhǔn)化到Z分?jǐn)?shù)，以增強(qiáng)常用方法的可比較性。

2.3 兩步聚類

兩步聚類法(Two Step Clustering, TSC)又稱兩階聚類法，當(dāng)數(shù)據(jù)樣本中有名義變量時(shí)，可選擇該聚類方法，與SPSS中K-means和系統(tǒng)聚類法不同的是該方法采用數(shù)的極大似然估計(jì)值度量變量之間的距離，并能根據(jù)施瓦茲貝葉斯準(zhǔn)則(BIC)或Akaike信息準(zhǔn)則(AIC)等指標(biāo)自動(dòng)確定最佳聚類個(gè)數(shù)[18]。

該方法分為兩階段：①預(yù)聚類階段：采用BIRCH算法中CF樹生長的思想，逐個(gè)讀取數(shù)據(jù)集中數(shù)據(jù)點(diǎn)，在生成CF樹的同時(shí)，預(yù)先聚類密集區(qū)數(shù)據(jù)點(diǎn)，形成諸多小的類：②聚類階段：逐個(gè)合成子類，直至達(dá)到期望的類數(shù)量。

3 實(shí)驗(yàn)

3.1 有效性指標(biāo)

聚類有效性評(píng)價(jià)指標(biāo)分為外部評(píng)價(jià)指標(biāo)和內(nèi)部評(píng)價(jià)指標(biāo)兩大類，常用的外部評(píng)價(jià)指標(biāo)包括F_measure指數(shù)、Rand指數(shù)和Jaccard系數(shù)，常用的內(nèi)部評(píng)價(jià)指標(biāo)包括Cophenetic相關(guān)系數(shù)和Huberts 統(tǒng)計(jì)指標(biāo)[19]。Davies等[20]提出聚類有效性指標(biāo)DB(-)，該有效性指標(biāo)以類內(nèi)樣本點(diǎn)到其聚類中心的距離估計(jì)類內(nèi)緊致性，用聚類中心之間的距離表示類間分離性。本文參考該指標(biāo)，以類內(nèi)樣本各個(gè)點(diǎn)到其聚類各中心的距離平均值作為比較類內(nèi)的緊致性指標(biāo)(指標(biāo)1)，以聚類各個(gè)中心之間的距離平均值作為比較類間的分離性指標(biāo)(指標(biāo)2)。計(jì)算公式為：

(1)

(2)

3.2 實(shí)驗(yàn)描述

為比較統(tǒng)計(jì)分析軟件SPSS中3種聚類方法對(duì)數(shù)據(jù)的處理效率和效果，本文隨機(jī)選取了99組數(shù)據(jù)，將數(shù)據(jù)分為3組，其中32組數(shù)據(jù)用于K-means聚類、系統(tǒng)聚類之間的比較，29組數(shù)據(jù)用于K-means標(biāo)準(zhǔn)化聚類與系統(tǒng)聚類的比較，38組數(shù)據(jù)用于兩步聚類與系統(tǒng)聚類的比較，并使用SPSS軟件和VBA編程語言對(duì)比分析K-means聚類、K-means標(biāo)準(zhǔn)化聚類、兩步聚類、系統(tǒng)聚類的算法效率。

分析和計(jì)算步驟如下：

步驟1：用SPSS軟件把樣本聚類處理為3個(gè)類、4個(gè)類、5個(gè)類，每一行數(shù)據(jù)都有其分類號(hào)，將分類后的結(jié)果(.sav文件)存為excel文件；

步驟2：在保存數(shù)據(jù)的excel文件中，用VBA(Excel內(nèi)嵌的編程語言)計(jì)算各個(gè)類中心點(diǎn)之間的距離平均值(類之間離得足夠遠(yuǎn)——見3.1節(jié)中的指標(biāo)2 )、各個(gè)類的點(diǎn)到中心點(diǎn)距離的平均值(類里的距離足夠小——見3.1節(jié)中的指標(biāo)1)。

步驟3：根據(jù)指標(biāo)1和指標(biāo)2，對(duì)比分析在不同數(shù)據(jù)特征下，何種SPSS聚類算法效率更高。

3.3 實(shí)驗(yàn)結(jié)果

通過對(duì)比分析觀察聚類算法效率，得到對(duì)比結(jié)果。

3.3.1 K均值未標(biāo)準(zhǔn)化聚類與系統(tǒng)聚類方法比較

由表1可以看出，通過對(duì)32組數(shù)據(jù)進(jìn)行K-means未標(biāo)準(zhǔn)化聚類和系統(tǒng)聚類方法處理，分別得到為3個(gè)類的聚類、4個(gè)類的聚類、5個(gè)類的聚類，分類增強(qiáng)實(shí)驗(yàn)結(jié)果的可比性，3種分類中K均值未標(biāo)準(zhǔn)化的指標(biāo)1明顯小于系統(tǒng)聚類的指標(biāo)1，而且K均值未標(biāo)準(zhǔn)化指標(biāo)2明顯大于系統(tǒng)聚類的指標(biāo)2，因此K-means未標(biāo)準(zhǔn)化聚類方法明顯優(yōu)于系統(tǒng)聚類。此外系統(tǒng)聚類方法的指標(biāo)1隨著聚類個(gè)數(shù)增加，由467 426.131 9逐步降到417 052.567 1，指標(biāo)2由381 995.229 4逐步增加到489 344.832 1，因此得出，系統(tǒng)聚類有效性隨著系統(tǒng)聚類個(gè)數(shù)的增加越來越好。

表1 32組K均值未標(biāo)準(zhǔn)化與系統(tǒng)聚類比較

表2 32組K均值未標(biāo)準(zhǔn)化與系統(tǒng)聚類對(duì)比

此外，由表2占比統(tǒng)計(jì)可以看出，K均值未標(biāo)準(zhǔn)化絕對(duì)優(yōu)于系統(tǒng)聚類方法，不論數(shù)據(jù)本身大小如何，在K均值未標(biāo)準(zhǔn)化聚類方法與系統(tǒng)聚類之間選擇時(shí)，首選K均值未標(biāo)準(zhǔn)化聚類方法。

根據(jù)32組數(shù)據(jù)的統(tǒng)計(jì)特征進(jìn)行劃分，如表3所示將數(shù)據(jù)分為數(shù)據(jù)1和數(shù)據(jù)2，數(shù)據(jù)1的樣本數(shù)據(jù)規(guī)模小于數(shù)據(jù)2。本文類似表格還有表6、表9。

表3 32組K均值未標(biāo)準(zhǔn)化與系統(tǒng)聚類數(shù)據(jù)統(tǒng)計(jì)特征

由表3可以看出，在考慮數(shù)據(jù)規(guī)模時(shí)，只有數(shù)據(jù)取值范圍很小且數(shù)據(jù)變動(dòng)也很小時(shí)，可以任意選擇K均值未標(biāo)準(zhǔn)化或系統(tǒng)聚類方法，即兩者在數(shù)據(jù)處理上無差別；而在數(shù)據(jù)規(guī)模較大時(shí)，則應(yīng)選擇K均值未標(biāo)準(zhǔn)化聚類方法。因此也驗(yàn)證了表2的結(jié)論：不論數(shù)據(jù)規(guī)模如何，都應(yīng)選擇K均值未標(biāo)準(zhǔn)化聚類方法。

3.3.2 K均值標(biāo)準(zhǔn)化聚類與系統(tǒng)聚類方法比較

由表4可以看出，通過對(duì)29組數(shù)據(jù)進(jìn)行K-means標(biāo)準(zhǔn)化聚類和系統(tǒng)聚類處理，分別得到3個(gè)類的聚類、4個(gè)類的聚類、5個(gè)類的聚類，通過分類增強(qiáng)實(shí)驗(yàn)結(jié)果可比性，3種分類中K-means標(biāo)準(zhǔn)化聚類方法指標(biāo)1要比系統(tǒng)聚類指標(biāo)1小，且K-means標(biāo)準(zhǔn)化聚類方法指標(biāo)2也要比系統(tǒng)聚類指標(biāo)2大。從表中可以看出，系統(tǒng)聚類方法的指標(biāo)1隨著聚類個(gè)數(shù)增加，由289 158.442 8逐步降到267 296.610 8，指標(biāo)2由278 197.103 3逐步增加到302 074.593 5，因此系統(tǒng)聚類有效性隨系統(tǒng)聚類個(gè)數(shù)的增加越來越好，但K-means標(biāo)準(zhǔn)化聚類方法一直優(yōu)于系統(tǒng)聚類。

表4 29組K均值標(biāo)準(zhǔn)化聚類與系統(tǒng)聚類比較

表5 29組K均值標(biāo)準(zhǔn)化與系統(tǒng)聚類對(duì)比

由表4還可以看出，K均值標(biāo)準(zhǔn)化聚類方法比系統(tǒng)聚類方法有效，且隨著聚類個(gè)數(shù)的增加，系統(tǒng)聚類與K均值標(biāo)準(zhǔn)化聚類方法的差距將縮小。從兩類指標(biāo)的占比可以看出，K均值標(biāo)準(zhǔn)化聚類的有效性高于系統(tǒng)聚類方法，但隨著聚類個(gè)數(shù)的增加，差距有縮小的趨勢(shì)，指標(biāo)1由原來的72.414%降到51.724%和55.172%，指標(biāo)2由原來的72.414%降到51.724%和62.069%。由此可以得出，K均值標(biāo)準(zhǔn)化聚類的有效性會(huì)一直優(yōu)于系統(tǒng)聚類方法。

根據(jù)以上結(jié)果，本實(shí)驗(yàn)對(duì)這29組數(shù)據(jù)進(jìn)行數(shù)據(jù)特征比較，結(jié)果如表6所示。

表6 29組K均值標(biāo)準(zhǔn)化聚類與系統(tǒng)聚類的數(shù)據(jù)統(tǒng)計(jì)特征

因此，在選擇均值標(biāo)準(zhǔn)化和系統(tǒng)聚類時(shí)，如果數(shù)據(jù)規(guī)模比較小，可以選擇任意一種方式；而在數(shù)據(jù)規(guī)模比較大時(shí)，則應(yīng)選擇K均值標(biāo)準(zhǔn)化聚類方法。

3.3.3 兩步聚類與系統(tǒng)聚類方法比較

表7 38組兩步聚類與系統(tǒng)聚類比較

由表3可以看出，通過對(duì)38組數(shù)據(jù)進(jìn)行兩步聚類和系統(tǒng)聚類處理，分別得到為3個(gè)類的聚類、4個(gè)類的聚類、5個(gè)類的聚類，通過如此分類增強(qiáng)實(shí)驗(yàn)結(jié)果可比性，而這三種分類的系統(tǒng)聚類方法指標(biāo)1都小于兩步聚類的指標(biāo)1，系統(tǒng)聚類方法的指標(biāo)2大于兩步聚類的指標(biāo)2，由此可以得出，系統(tǒng)聚類方法明顯比兩步聚類有效。

同時(shí)，由表8可以看出，系統(tǒng)聚類方法的總體有效性要優(yōu)于兩步聚類方法，并且隨著聚類個(gè)數(shù)的增加，指標(biāo)1由3個(gè)類的78.95%增加到5個(gè)類的92.11%，指標(biāo)2由3個(gè)類的84.21%增加到5個(gè)類的94.74%。由此可見，系統(tǒng)聚類的有效性隨著聚類個(gè)數(shù)的增加將越來越優(yōu)于兩步聚類方法。

表8 38組兩步聚類與系統(tǒng)聚類對(duì)比

根據(jù)以上結(jié)果，本實(shí)驗(yàn)對(duì)這38組數(shù)據(jù)進(jìn)行數(shù)據(jù)特征比較，結(jié)果如表9所示。

表9 38組兩步聚類與系統(tǒng)聚類數(shù)據(jù)統(tǒng)計(jì)特征

由表9可知，在選擇兩步聚類和系統(tǒng)聚類時(shí)，如果數(shù)據(jù)規(guī)模比較小，則可以選擇兩步聚類；而在數(shù)據(jù)規(guī)模比較大時(shí)，則應(yīng)該選擇系統(tǒng)聚類方法。

3.4 實(shí)驗(yàn)分析及建議

本文通過對(duì)數(shù)據(jù)進(jìn)行兩兩聚類分析比較，分為3個(gè)類、4個(gè)類、5個(gè)類，一方面說明數(shù)據(jù)可比性，另一方面也驗(yàn)證數(shù)據(jù)可靠性。此外，本文通過兩項(xiàng)指標(biāo)(類間距、類內(nèi)距)綜合說明實(shí)驗(yàn)結(jié)果的優(yōu)良性。

綜上分析可知：①在判斷數(shù)據(jù)類型、確認(rèn)使用的聚類分析方法后，發(fā)現(xiàn)K-means聚類(K均值未標(biāo)準(zhǔn)化、K均值標(biāo)準(zhǔn)化)效果明顯優(yōu)于系統(tǒng)聚類效果，系統(tǒng)聚類也明顯優(yōu)于兩步聚類；②只有系統(tǒng)聚類分析方法隨著聚類個(gè)數(shù)的增加而越來越有效，K-means聚類和兩步聚類無該趨勢(shì)。

由此，本文給出以下建議：①在進(jìn)行聚類分析時(shí)，根據(jù)變量的連續(xù)特征，在K-means聚類與系統(tǒng)聚類之間選擇時(shí)，首選K-means聚類方法。根據(jù)數(shù)據(jù)規(guī)模大小，規(guī)模較小時(shí)則可以任意選擇，而規(guī)模較大時(shí)選擇K-means聚類方法；②當(dāng)數(shù)據(jù)中含有不連續(xù)變量、在兩部聚類和系統(tǒng)聚類之間選擇時(shí)，若數(shù)據(jù)規(guī)模較小，可選擇兩步聚類；若數(shù)據(jù)規(guī)模較大，則應(yīng)選擇系統(tǒng)聚類方法；③進(jìn)行系統(tǒng)聚類分析時(shí)，盡可能選擇較多的聚類個(gè)數(shù)，能有效提高聚類精確度。

4 結(jié)語

本文通過對(duì)99組數(shù)據(jù)進(jìn)行聚類分析比較，最后得出優(yōu)先選擇何種聚類方法的條件和規(guī)則，為如何選擇更合適的SPSS方法給出了有價(jià)值的參考。在判斷聚類分析方法效率時(shí)選用兩個(gè)指標(biāo)，很好地說明了變量之間的親疏，對(duì)其它數(shù)據(jù)挖掘工具的使用也有一定啟發(fā)。限于SPSS軟件本身的缺點(diǎn)，如導(dǎo)入數(shù)據(jù)規(guī)模有限，不能對(duì)數(shù)據(jù)規(guī)模進(jìn)行詳細(xì)劃分，亦不能處理海量數(shù)據(jù)，因此，如何對(duì)海量數(shù)據(jù)進(jìn)行聚類分析，并達(dá)到有效的聚類效果將是下一步研究方向。