呂正萍，紀漢霖

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

0 引言

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

目前對聚類算法的研究及應用集中在兩個方面：

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

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

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

1 聚類原理

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

一般采用不同距離公式會得到不同分類結果，本文采用歐式距離進行分類。

2 SPSS聚類模型概述

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

2.1 K-means聚類

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

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

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

K-means聚類只能產生指定類數(shù)的聚類結果，在應用K-means聚類分析方法時，對于變量之間存在較大差異時，通常先采用標準化處理，再進行下一步聚類分析。因此，K-means聚類又分為K-means未標準化聚類和K-means標準化聚類。

2.2 系統(tǒng)聚類

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

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

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

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

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

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

2.3 兩步聚類

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

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

3 實驗

3.1 有效性指標

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

(1)

(2)

3.2 實驗描述

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

分析和計算步驟如下：

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

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

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

3.3 實驗結果

通過對比分析觀察聚類算法效率，得到對比結果。

3.3.1 K均值未標準化聚類與系統(tǒng)聚類方法比較

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

表1 32組K均值未標準化與系統(tǒng)聚類比較

表2 32組K均值未標準化與系統(tǒng)聚類對比

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

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

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

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

3.3.2 K均值標準化聚類與系統(tǒng)聚類方法比較

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

表4 29組K均值標準化聚類與系統(tǒng)聚類比較

表5 29組K均值標準化與系統(tǒng)聚類對比

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

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

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

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

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

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

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

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

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

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

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

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

3.4 實驗分析及建議

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

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

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

4 結語

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