韓存鴿 葉球?qū)O

(1. 武夷學(xué)院數(shù)學(xué)與計算機學(xué)院， 福建 武夷山 354300；2. 認(rèn)知計算與智能信息處理福建省高校重點實驗室， 武夷山 354300)

聚類分析是數(shù)據(jù)挖掘研究中一個非常活躍的研究領(lǐng)域。數(shù)據(jù)挖掘的一個重要任務(wù)是發(fā)現(xiàn)眾多數(shù)據(jù)中的積聚現(xiàn)象，然后對其進(jìn)行定量化描述。聚類分析是在對數(shù)據(jù)不作任何假設(shè)的條件下，用數(shù)學(xué)方法研究和處理所給對象的分類以及各類之間的親疏程度，其目標(biāo)是要將具有相似特征的樣本數(shù)據(jù)歸為一類，并使得類內(nèi)差異小、類間差異大。聚類與分類不同。在分類模型中存在樣本數(shù)據(jù)，這些數(shù)據(jù)的類標(biāo)號是已知的，分類的目的是從訓(xùn)練樣本集中提取出分類的規(guī)則，用于對其他類標(biāo)號未知的對象進(jìn)行類表示。聚類是在不知道目標(biāo)數(shù)據(jù)的有關(guān)類的信息的情況下，以某種度量為標(biāo)準(zhǔn)將所有的數(shù)據(jù)對象劃分到各個簇中。聚類分析因此又被稱為無監(jiān)督的學(xué)習(xí)[1]。聚類算法的目的是要尋找數(shù)據(jù)中潛在的自然分組結(jié)構(gòu)和特定的關(guān)系。目前已經(jīng)存在許多聚類算法。本次研究，將通過實驗對幾種常用的聚類算法進(jìn)行比較分析。

1 常用的幾種聚類算法概述

不同的聚類算法在進(jìn)行決策樹分析時存在一定的差異。評價聚類算法性能的指標(biāo)主要有3個：一是正確預(yù)測的能力，即預(yù)測的準(zhǔn)確率；二是可解釋性，產(chǎn)生的有關(guān)模型要易于理解；三是速度，即產(chǎn)生規(guī)則的時間越短越好[2]。另外，與人工判斷的吻合度是最直觀的評判準(zhǔn)則之一。在眾多的聚類算法中，基于劃分的K-means算法、基于模型的EM算法、基于密度的DBSCAN算法和基于分層的FarthestFirst算法是比較常用的算法，我們主要比較分析這4種聚類算法的性能。

1.1 K-means算法

1.1.1 K-means的原理及流程

1967年由J.B.Macqueen提出的K-means算法，目前已經(jīng)成為數(shù)理統(tǒng)計、模式識別、機器學(xué)習(xí)和數(shù)據(jù)挖掘等領(lǐng)域應(yīng)用最普遍的一種聚類算法，并有多種變形算法，組成了K-means算法家族。

按照K-means算法，先是進(jìn)行粗略的分類，然后根據(jù)某種最優(yōu)的原則修改不合理的分類，直到類分比較合理，形成最終的分類結(jié)果。因此，首先需要隨機地選擇k個對象，每個對象初始代表一個簇的平均值或中心。接著將剩余的每個對象，根據(jù)其與各個簇均值的距離，分派給最近的簇；然后計算每個簇的新均值。這個過程不斷重復(fù)，直到準(zhǔn)則函數(shù)收斂。通常采用平方誤差準(zhǔn)則，其定義如下[3]：

其中：p是空間中的點，表示給定的數(shù)據(jù)對象；mi是簇ci的平均值。

K-means均值劃分算法的流程如下。

Input：K(簇的數(shù)目)，D(包含n個對象的數(shù)據(jù)集)

Output：K個簇的集合

方法：(1)從D中任意選擇k個對象作為初始簇中心；(2)repeat；(3)根據(jù)簇中對象的均值，將每個對象指派到最相似的簇；(4)更新簇均值，即計算每個簇中對象的均值；(5)簇均值不再發(fā)生變化，則結(jié)束。

1.1.2 K-means應(yīng)用舉例

坐標(biāo)上有5個點{x1，x2，x3，x4，x5}，進(jìn)行聚類分析。5個二維樣本為：x1=(0，0)，x2=(5，2)，x3=(1.5，0)，x4=(0，2)，x5=(5，0)。假設(shè)k=2。

Step 1：隨機分為2個簇，計算質(zhì)心M。

C1=(x1，x2，x3)C2=(x4，x5)

M1={0+5+1.5/3，0+2+0/3}={2.17，0.67}

M2={0+5/2，2+2/2}={2.5，1}

(2-0.67)2+(1.5-2.17)2+(0-0.67)2]=15.83

e2=15.83+14.5=30.33

step 2：計算質(zhì)心到樣本的距離，并取距離最小的重新分配到簇。

d(M1，x1)=[(0-2.17)2+(0-0.67)2]1/2=2.27

d(M2，x1)=2.69=>x1∈C1

d(M1，x2)=3.12

d(M2，x2)=2.69=>x2∈C2

d(M1，x3)=0.95

d(M2，x3)=1.414=>x3∈C1

d(M1，x4)=2.54

d(M2，x4)=2.69=>x4∈C1

d(M1，x5)=2.91

d(M2，x5)=2.69=>x5∈C2

step 3：根據(jù)重新分配的簇，計算新質(zhì)心。

C1=(x1，x3，x4)C2=(x2，x5)

M1={0.5，0.67}M2={5，1}

相應(yīng)的方差是：e2=4.166 7+2=6.166 7

第一次迭代后，總體誤差顯著減小(由30.33減小到6.166 7)，算法終止。

1.2 EM算法

EM算法(Expectation Maximization Algorithm)[4]是一種逐次逼近算法，包括計算期望值和求極大值，主要運用高斯混合模型的參數(shù)估計。該模型可以解決聚類分析、機器學(xué)習(xí)等領(lǐng)域中的許多實際問題。該算法的步驟如下：

Input：觀測數(shù)據(jù)(y1，y2，…，yn)，高斯混合模型

Output：高斯混合模型參數(shù)

(1) 取參數(shù)的初始值，開始迭代。

(2) 求期望值。依據(jù)當(dāng)前模型參數(shù)，計算lgP(y,γα|θ)的期望，即Q(θ,θ(i))=E[lgP(y,γ|θ|)|y,θ(i)]。

(3) 求極大值。求函數(shù)Q(θ,θ(i))對θ的極大值，即計算新一輪迭代的模型參數(shù)：θ( i +1)=argmaxQ(θ,θ( i))。

(4) 重復(fù)第(2)步和第(3)步，直至收斂，即直到對數(shù)似然函數(shù)值θ不再有明顯的變化為止。

1.3 DBSCAN和FarthestFirst算法

DBSCAN(Density-Based Spatial Clustering Application with Noise)算法是一種經(jīng)典的基于密度的聚類算法，用于過濾噪聲數(shù)據(jù)，實現(xiàn)快速發(fā)現(xiàn)任意形狀的類的分析[5]。執(zhí)行流程：掃描數(shù)據(jù)庫，找到每個點的鄰居個數(shù)e。如果e大于閾限值，則該記錄作為中心記錄，隨即以這個記錄為中心的類就產(chǎn)生了[6]。DBSCAN算法使用歐式距離度量，確定哪些實例屬于哪個簇。與K均值算法不同，DBSCAN算法可以自動確定簇的數(shù)目，發(fā)現(xiàn)任意形狀的簇，并納入離群概念。

FarthestFirst算法是快速地近似K均值的聚類算法，每一次取最遠(yuǎn)的那個點。該算法主要包括2個部分：FarthestFirst遍歷和層次聚類。FarthestFirst遍歷的思想類似于構(gòu)造一棵最小生成樹(針對點到集合)。算法過程如下[7]：

Input：n data points with a distance metric d(.,.)

Pick a point and label it 1

Fori=2,3,…,n

Fint the point furthest from {1,2,…,i-1} and label iti.

Let π(i)=argminj

LetRi=d(i,π(i))

2 WEKA平臺下的聚類過程

懷卡托智能分析環(huán)境(Waikato Environment for Knowledge Analysis，縮寫為“WEKA”)，是一種使用Java語言編寫的數(shù)據(jù)挖掘機器學(xué)習(xí)軟件，其中包括處理標(biāo)準(zhǔn)數(shù)據(jù)挖掘問題的所有方法，如分類、回歸、聚類、關(guān)聯(lián)規(guī)則以及在新的交互式界面上的可視化。WEKA是開放源代碼，新編寫的算法只要符合其接口規(guī)范，就可以嵌入其中，從而擴充其原有算法。

以K-means算法為例，介紹在WEKA平臺下如何聚類。WEKA平臺把K-means算法的實現(xiàn)命名為“SimpleKMeans”算法，位于weka.clusterers.SimpleKMeans包中。以此構(gòu)建聚類器，包括以下4個環(huán)節(jié)[8]：

(1) 讀入樣本數(shù)據(jù)；

(2) 初始化聚類器，采用setDistanceFunction(DistanceFunction df)函數(shù)計算距離；

(3) 使用聚類算法對樣本進(jìn)行聚類；

(4) 打印聚類結(jié)果。

3 算法性能分析實驗

以K-means算法為例。實驗中的數(shù)據(jù)來自于UCI數(shù)據(jù)集中的鳶尾花數(shù)據(jù)(Iris)，這是用于模式識別的數(shù)據(jù)集，常用來測試和比較數(shù)據(jù)挖掘算法。鳶尾花數(shù)據(jù)集定義了5個屬性：sepal length、sepal width、petal length、petal width、class。其中，前4個屬性均為數(shù)值型，單位cm；只有class為類屬性。有 Iris Setosa、Iris Versicolour、Iris Virginica等3類，分別代表山鳶尾、變色鳶尾、維基亞鳶尾。每個類別都有50個實例，共有150條實例數(shù)據(jù)。使用WEKA平臺中的現(xiàn)有算法SimpleKMeans、DBSCAN、EM、FarthestFirst對此數(shù)據(jù)集進(jìn)行聚類測試，實驗是在 Window 10 操作系統(tǒng)下進(jìn)行的。

3.1 實驗步驟

WEKA為用戶提供了Explorer(探索者)、Experimenter(實驗者)、Knowledge Flow(知識流)、Simple CLI(命令行)4種用戶界面。我們使用Explorer圖形用戶界面對Iris數(shù)據(jù)集進(jìn)行聚類分析實驗。實驗步驟如下：

(1) 在Preproccess選項卡中選open file按鈕，導(dǎo)入Iris.arff數(shù)據(jù)集。

(2) 選擇Explorer界面下的cluster選項卡，選擇打開SimpleKMeans，設(shè)置參數(shù)。

displayStdDevs參數(shù)，用于是否顯示數(shù)值屬性標(biāo)準(zhǔn)差和分類屬性個數(shù)。選擇false，不顯示。

distanceFunction參數(shù)，用來計算距離函數(shù)。使用WEKA默認(rèn)的EuclideanDistance函數(shù)。

dontReplaceMissingValues參數(shù)，用來表示是否使用均值/眾數(shù)替代缺失值。選擇false。

maxIterations即最大迭代次數(shù)，設(shè)為500。

numClusters即聚類的簇數(shù)，設(shè)置為3，就是把150條實例聚成3類。

在preserveInstancesOrder下選擇false，表示沒有預(yù)先排列實例順序。

Seed(種子數(shù))，設(shè)置為10。

(3) 為了驗證算法的正確率，實驗采用監(jiān)督模式(Classes to vlusters evalution)進(jìn)行測試。監(jiān)督屬性為class。

(4) 點擊start按鈕，運行程序。

3.2 實驗結(jié)果分析

SimpleKMeans算法的聚類分析結(jié)果如圖1所示，監(jiān)督模式的運行信息如圖2所示，可視化簇分配如圖3所示。錯分實例為17個，占總數(shù)的11.3%。Cluster Instances信息欄，列出了各個簇中實例數(shù)目及百分比。Iris數(shù)據(jù)集的數(shù)據(jù)被預(yù)測成3個簇。其中，Cluster 0有61條實例，占實例總數(shù)的41%；Cluster 1有50條實例，占實例總數(shù)的33%；Cluster 2有39條實例，占實例總數(shù)的26%。采用監(jiān)督模式進(jìn)行驗證，Cluster 0代表Iris Versicolour，Cluster 1代表Iris Setosa，Cluster 2代表Iris Virginica。該算法對Iris Setosa的預(yù)測分組與實際一致，對Iris Versicolour和Iris Virginica的預(yù)測分組與實際存在偏差，誤差的平方和(SSE)為6.998。實驗表明，該算法能夠很好地對抽象的事物進(jìn)行分組。Cluster centroids 列出了sepal width、sepal length、petal width、petal length等4個屬性簇中心的位置。

圖2 SimpleKMeans算法監(jiān)督模式信息

圖3 可視化簇分配

圖3是以sepal width為橫軸、以petal width為縱軸的可視化簇分配結(jié)果。其中，左側(cè)為散點圖，圖中的符號×表示實例，□代表錯誤的聚類實例，顏色由實例的簇類別決定。從中可以看出，SimpleKMeans發(fā)現(xiàn)了3個簇：顯示為藍(lán)色的Iris Versicolour、顯示為紅色的Iris Setosa和顯示為綠色的Iris Virginica。右側(cè)的條狀圖顯示了sepal width、sepal length、petal width、petal length屬性值的隨機分布情況，其中紅色的X和Y分別表示當(dāng)前以sepal width為橫軸、以petal width為縱軸。條狀圖中，實例被放置在水平位置，所顯示的顏色由所在簇類別決定，其中的點代表屬性值的分布情況。

3.3 實驗結(jié)果對比

評價聚類分析結(jié)果的優(yōu)劣，最直觀的方法就是看它與人工判斷結(jié)果的吻合度。為了驗證SimpleKMeans決策樹算法的分類效果，分別采用DBSCAN、EM、FarthestFirst等3種聚類分析算法對Iris數(shù)據(jù)集進(jìn)行了聚類實驗。實驗結(jié)果見表1。

表1 幾種算法的聚類分析實驗結(jié)果

從聚類形成簇的個數(shù)看，SimpleKMeans、EM和FarthestFirst算法都是形成3個簇，與人工判斷一致。從誤判率來看，SimpleKMeans算法的誤判率最低，為11.3%。從建模的速度看，SimpleKMeans算法和FarthestFirst算法的運行時間最短，其次是DBSCAN算法，而用時最長的是EM算法。從迭代次數(shù)看，SimpleKMeans的迭代次數(shù)最少，且明顯低于其他幾種聚類算法的迭代次數(shù)。實驗結(jié)果證明，對數(shù)值型屬性采用SimpleKMeans算法得到的聚類效果比較好。

4 結(jié) 語

在WEKA中采用SimpleKMeans算法構(gòu)建聚類器，并在WEKA平臺上采用K-means算法對Iris數(shù)據(jù)集進(jìn)行了聚類分析實驗。結(jié)果顯示，Iris數(shù)據(jù)集被預(yù)測成Cluster 0、Cluster 1、Cluster 2等3個簇，運行時間僅0.02 s，誤判率只有11.3%。與DBSCAN、EM、FarthestFirst等聚類算法相比，K-means算法在誤判率、運行時間、生成簇數(shù)、迭代次數(shù)等方面，與人工判斷的吻合度最高。