一種基于Python的K—means聚類算法分析

陳偉++李紅++王維

摘要：聚類是數(shù)據(jù)挖掘核心技術(shù)之一，是一門新興的學(xué)科。聚類技術(shù)要使一個類簇內(nèi)的實體是相似的，不同類簇的實體是相異的。從聚類研究現(xiàn)狀談起， 描述聚類概念和分類方法，介紹K-means算法的思想，并利用K-mean算法實現(xiàn)了iris數(shù)據(jù)集的分類，完成相關(guān)測試和實驗驗證。

關(guān)鍵詞：聚類分析；K-Means算法；數(shù)據(jù)挖掘

中圖分類號：TP301.6 文獻(xiàn)標(biāo)識碼：A 文章編號：1007-9416（2017）10-0118-02

聚類是數(shù)據(jù)挖掘技術(shù)中一個非常重要的分支，它是在沒有任何先驗知識的前提下，從海量數(shù)據(jù)中提取出有價值的、未知的數(shù)據(jù)。實現(xiàn)滿足要求的簇的集合。

1 聚類分析研究現(xiàn)狀

聚類分析是一個將數(shù)據(jù)集劃分成若干個子集的過程，并使同一集合內(nèi)的數(shù)據(jù)對象具有較高的相似度，而不同集合中的數(shù)據(jù)對象不相似。國內(nèi)外對聚類分析的研究已經(jīng)有很多年，學(xué)者們研究的主要內(nèi)容是基于距離的聚類分析，K-Medoids算法、K-Means算法以及其他的聚類算法的挖掘工具在眾多的統(tǒng)計軟件或者系統(tǒng)中得到廣泛的應(yīng)用。

1967年，MacQueen首次提出K均值聚類算法（K-means算法）。迄今為止，很多聚類任務(wù)都選擇該經(jīng)典算法。該算法的核心思想是找出K個聚類中心、，…，，使得每一個數(shù)據(jù)點和與其最近的聚類中心的平方距離和被最小化。

1998年，Huang為克服K-Means算法僅適合于數(shù)值屬性數(shù)據(jù)聚類的局限性，提出了一種適合分類屬性數(shù)據(jù)聚類的K-Modes算法，該算法對K-Means算法進行了3點擴展：引入了處理分類對象的新的相異性度量方法，使用modes代替means，并在聚類過程中使用基于頻度的方法修正modes，以使聚類代價函數(shù)值最小。

2002年，Sun等人將Bradley等人的迭代初始點集求精算法應(yīng)用于K-Modes算法。盡管Huang的K-Modes算法能夠聚類分類數(shù)據(jù)，但它需要預(yù)先決定或隨機選擇類的初始modes，并且初始modes的差異常常會導(dǎo)致截然不同的聚類結(jié)果。文中，Sun等人給出了一個關(guān)于應(yīng)用Bradley等人的迭代初始點求精算法于K-Modes聚類的實驗研究。

2010年，李衛(wèi)平[7]提出對K-Means算法進行改進。他針對K-Means算法對初值的依賴性，基于最小生成樹原理選擇聚類中心進行聚類。根據(jù)尋找最優(yōu)初值的思想提出了一種改進K-Means算法，并將卡斯克魯爾算法以及貪心算法的思想引入到K-Means算法中。

2 聚類分析算法

2.1 劃分法

K-MEANS算法、K-Medoids算法是典型的劃分法（partitioning methods）。算法的處理思路基本是：給定一個類庫D，D中含有N個數(shù)據(jù)對象，用戶輸入需要獲得的類簇個數(shù)K，將類庫D中N個數(shù)據(jù)對象劃分成K個分組或者簇，然后通過迭代的方式更新簇的中心，當(dāng)整體的差異收斂時結(jié)束處理過程。使得簇內(nèi)的相似度更高（更相似），簇間的相異性更高（差異更大）。

劃分法的代表算法有：K-Medoids算法、CLARANS算法、K-Means算法。

2.2 層次法

對給定的數(shù)據(jù)，進行層次分解，直到某種條件滿足。層次法構(gòu)建聚類的方法有分為兩種：

（1）凝聚層次法（自底向上法）：首先將類庫中的每一個數(shù)據(jù)劃分每一個單獨的類，通過遞歸的方法，將相似的或者相近的類合并成為一個類，最后使得一個類中所包含的數(shù)據(jù)或者分類結(jié)果滿足某種條件。

（2）分裂層次法（自頂向上法）：開始將所有的對象劃分成為一個類，然后將總類劃分成為若干個子類，接著在劃分出子類的子類，一直迭代劃分，直到獲得滿意的聚類結(jié)構(gòu)。

2.3 基于密度的方法

基于密度的方法是假定每個簇中的數(shù)據(jù)對象點是按照一個特定的概率分布繪制的，數(shù)據(jù)的整體分布被假設(shè)成為幾個分布的混合體，這種方法是識別出簇以及他們的分布函數(shù)?；诿芏确椒ǖ乃枷耄簩τ谝粋€給定的簇，這個簇持續(xù)的增長，直至周圍的密度（對象的數(shù)目或者說是數(shù)據(jù)點的數(shù)目）大于一個閥值時為止。

2.4 基于模型的方法

基于模型的方法（model-basedmethods）給每一個聚類假定一個模型，然后試圖去尋找能很好的滿足這個模型的數(shù)據(jù)集。該方法識別對象的組別，可以很快地發(fā)現(xiàn)每個組的特征描述，每組代表一個概念或者是一個類。最常用的方法有決策樹和神經(jīng)網(wǎng)絡(luò)法。

2.5 基于網(wǎng)格的方法

基于網(wǎng)格的方法（grid-basedmethods）是將所有的數(shù)據(jù)劃分為若干個有限數(shù)據(jù)細(xì)胞單元格，從而形成一個可以進行聚類操作的網(wǎng)格結(jié)構(gòu)，這樣的分割，是所有的數(shù)據(jù)對象都可以在數(shù)據(jù)網(wǎng)絡(luò)格上進行操作，和原始數(shù)據(jù)本身無關(guān)?；诰W(wǎng)絡(luò)的方法最主要的優(yōu)點是其快速的處理速度。

基于網(wǎng)格的方法的主要算法有：STING算法、CLIQUE算法、WAVE-CLUSTER算法。

3 K-means算法

K-means算法是根據(jù)聚類中的均值進行聚類劃分的聚類算法。

輸入：聚類個數(shù)，以及包含個數(shù)據(jù)對象的數(shù)據(jù)；

輸出：滿足方差最小標(biāo)準(zhǔn)的個聚類；

處理流程：

Step1：從個數(shù)據(jù)對象任意選擇個對象作為初始聚類中心；

Step2：循環(huán)Step 3到Step 4直到每個聚類不再發(fā)生變化為止；

Step3：根據(jù)每個聚類對象的均值（中心對象），計算每個對象與這些中心對象的距離，并根據(jù)最小距離重新對相應(yīng)對象進行劃分；

Step4：重新計算每個（有變化）聚類的均值（中心對象）k-means算法的工作過程說明如下：首先從個數(shù)據(jù)對象任意選擇個對象作為初始聚類中心，而對于所剩下的其它對象，則根據(jù)它們與這些聚類中心的相似度（距離），分別將它們分配給與其最相似的（聚類中心所代表的）聚類；然后，再計算每個所獲新聚類的聚類中心（該聚類中所有對象的均值），不斷重復(fù)這一過程直到標(biāo)準(zhǔn)測度函數(shù)開始收斂為止。一般都采用均方差作為標(biāo)準(zhǔn)測度函數(shù)，具體定義如下：

（公式1.1）

（：數(shù)據(jù)庫中所有對象的均方差和；：對象的空間中的一個點；：聚類的均值（和均是多維的））

4 改進K-means算法

二分K-均值算法的偽代碼形式如下：

將所有的點看成一個簇。

當(dāng)簇數(shù)目小于K時。

對于每一個簇：

計算總誤差。

在給定的簇上面進行K-均值聚類（k=3）。

計算將該簇一分為二的總誤差。

選擇使得誤差最小的那個簇進行劃分操作。

5 算法實現(xiàn)與分析

Iris數(shù)據(jù)集是以鳶尾花的花瓣長度、花瓣寬度、花萼長度、花萼寬度作為數(shù)據(jù)源，數(shù)據(jù)集中包含了150個數(shù)據(jù)對象，由3種不同類型的鳶尾花的50個樣本數(shù)據(jù)構(gòu)成。

根據(jù)上述K-Means算法在IRIS數(shù)據(jù)集中的應(yīng)用，可得到兩個結(jié)論：

（1）初始均值設(shè)置的不同會影響迭代的次數(shù)以及各次迭代所產(chǎn)生的聚類中心，但它不會影響最后的分類結(jié)果。

（2）數(shù)據(jù)的輸入順序不同，同樣影響迭代次數(shù)，而對聚類結(jié)果沒有太大的影響。

（3）采用二分K-Means算法，避免了局部最優(yōu)的結(jié)果的出現(xiàn)。

通過改進K-means算法實現(xiàn)中離群點的設(shè)置、K值等可以提高K-means算法的執(zhí)行效果。

參考文獻(xiàn)

[1]孟海東，宋飛燕，宋宇辰.面向復(fù)雜簇的聚類算法研究與實現(xiàn)[J].計算機應(yīng)用與軟件，2008，10：162-165.

[2]張琳，陳燕，汲業(yè)，張金松.一種基于密度的k-means算法研究[J].計算機應(yīng)用與軟件，2011，28（11）：4073-4085.

[3]李曼，趙松林.K—means聚類算法分析應(yīng)用研究[J].魅力中國，2011，（7）：243-243.

[4]李衛(wèi)平.對k-means聚類算法的改進研究[J].中國西部科技，2010，（24）：49-50.

[5]王娟.一種高效的K-means聚類算法[J].科技信息，2012，（25）：168-168.endprint