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

陳偉++李紅++王維

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

關鍵詞：聚類分析；K-Means算法；數據挖掘

中圖分類號：TP301.6 文獻標識碼：A 文章編號：1007-9416（2017）10-0118-02

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

1 聚類分析研究現狀

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

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

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

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

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

2 聚類分析算法

2.1 劃分法

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

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

2.2 層次法

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

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

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

2.3 基于密度的方法

基于密度的方法是假定每個簇中的數據對象點是按照一個特定的概率分布繪制的，數據的整體分布被假設成為幾個分布的混合體，這種方法是識別出簇以及他們的分布函數。基于密度方法的思想：對于一個給定的簇，這個簇持續的增長，直至周圍的密度（對象的數目或者說是數據點的數目）大于一個閥值時為止。

2.4 基于模型的方法

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

2.5 基于網格的方法

基于網格的方法（grid-basedmethods）是將所有的數據劃分為若干個有限數據細胞單元格，從而形成一個可以進行聚類操作的網格結構，這樣的分割，是所有的數據對象都可以在數據網絡格上進行操作，和原始數據本身無關。基于網絡的方法最主要的優點是其快速的處理速度。

基于網格的方法的主要算法有：STING算法、CLIQUE算法、WAVE-CLUSTER算法。

3 K-means算法

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

輸入：聚類個數，以及包含個數據對象的數據；

輸出：滿足方差最小標準的個聚類；

處理流程：

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

Step2：循環Step 3到Step 4直到每個聚類不再發生變化為止；

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

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

（公式1.1）

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

4 改進K-means算法

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

將所有的點看成一個簇。

當簇數目小于K時。

對于每一個簇：

計算總誤差。

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

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

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

5 算法實現與分析

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

根據上述K-Means算法在IRIS數據集中的應用，可得到兩個結論：

（1）初始均值設置的不同會影響迭代的次數以及各次迭代所產生的聚類中心，但它不會影響最后的分類結果。

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

（3）采用二分K-Means算法，避免了局部最優的結果的出現。

通過改進K-means算法實現中離群點的設置、K值等可以提高K-means算法的執行效果。

參考文獻

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

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

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

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

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