基于Python的K—means算法及其應用

薛芯菊

【摘 要】k-means 算法是一種無監督的簡單機械學習算法的一種，也是數據挖掘中一個非常有用的聚類分析方法.現在社會中聚類算法對于各個方面分類問題可以進行分析求解求其最優解.本文采用了python這一語言環境進行研究，使用了UCI中的真實數據來進行實驗分析.使用python對K-means算法進行編寫，通常我們用k-means算法進行運算時K值是規定的，本文使用肘部法則確定其K.有的數據無法直接使用，所以通過pca降維是數據可以更好的展示出來，再通過python編譯環境對真實數據進行可視化操作，形成了真實數據和我們所選取的數據的可視化圖像。

【關鍵詞】k-means；Python；聚類

中圖分類號： TP18 文獻標識碼： A 文章編號： 2095-2457（2018）24-0141-002

DOI：10.19694/j.cnki.issn2095-2457.2018.24.067

【Abstract】The k-means algorithm is a kind of unsupervised simple mechanical learning algorithm， and it is also a very useful cluster analysis method in data mining. The clustering algorithm implemented by the k-means algorithm in the society can be used in various aspects to analyze the clustering problem and find the optimal solution.This paper uses the python language environment for research， and uses the real data in UCI for experimental analysis. Using python to write K-means algorithm， usually we use the k-means algorithm to calculate the K value is specified， this article uses the elbow rule to determine its K. Some data can not be used directly， so the data can be better displayed through dimensional reduction by pca.

【Key words】Python； K-means； Clustering

聚類分析的算法分為劃分法、層次法、基于密度的方法、基于網格的方法、基于模型的方法，并且聚類分析也可以作為數據挖掘算法中其他分析算法的一個預處理步驟[1-2].可以運用數學與計算機的研究模式進行運算，根據數據庫中的多條信息進行大致的概括，然后進行區分，分為多個元素一一進行更加深入的研究分析.與K-means算法極為相似的一個算法為K中心算法也是就K-Mediods算法[3]，數據挖掘又被人們稱為數據庫中的知識發現，數據挖掘就是擁有潛在的大量信息價值的重要發覺過程[4].

1 k-means算法

1.1 k-means算法的研究思路

層次法[5]是一種對與給定的數據，進行數據分析處理的一種方法，當我們是用層次法滿足我們給定的一些條件時，聚類算法可以進行運行.以下的兩種條件是構建起來我們聚類的基本條件.

1.2 確定K值的方法

對于不確定的K值我們還可以使用肘部法則進行確定K值來，但是隨著K的不斷增大，我們可以看到平均畸變程度會不斷的減少，導致在K值的增大.

同時，還有一種方法對一個我們所選用的樣本數據集合進行兩次采集產生兩個數據樣本集，再用一樣的聚類算法對我們算選用的樣本數據集合進行聚類，產生相應的聚類結果，計算分布情況.這種方式就是我們不斷進行實驗計算所取得的最適合的K值.這就是我們剛才所介紹的穩定性確定K值的方法.

1.3 pca降維

在理解我們所用的數據的時候可能數據的維數較多.[15]所以我們使用數據的時候往往會產生維度災難.我們可以使用這種方法對于相關的高維數的變量合成線性無關的低維變量.

PCA降維：

第一步：使用所給出的樣本數據減去樣本均值.

第二步：計算數據的主要樣本成分，計算矩陣數據協方差矩陣.

第三步：咱們要形成一個轉換矩陣來進行映射同時轉換成為我們數據運算的主要成分.

2 基于python語言的實驗分析

2.1 python基礎概念

Python是一個開元自由的高性能語言，源代碼和解釋器CPython遵循 GPL協議，Python語法構造十分方便使用清晰明了，他最大的特色就是是強制使用空格作為語句縮進的一種手段[9].

2.2 在python下的k-means算法分析實驗

第一步：先從指定的所需數據樣本對象中選取相應的對象作為初始單位的中心點.

第二步：再根據所求的每個聚類對象的值，計算我們所使用的值與所算質心的真實距離.

第三步：根據最小距離重新對相應的對象進行歸類劃分.

第四步：從x個對象中選取的μ個對象作為初始中心點也就是所謂的質心，剩下的則根據距離進行相似聚類運算.

第五步：將他們跟他們最為相似的點進行歸類處理.

第六步開始會出現一些偏差，之后進行不斷的迭代不停地運算使得算法越來越接近標準的數值收斂到一定程度后，繼續運算的結果會趨近以一個數值不變.

同時在K-means算法的目標函數中插入一個新的數據項，該數據項用于估測其他與其接近的聚類中心點與當前聚類中心點的真實距離的平方和，并引入了一個權值，用于調節數據項在全部目標函數中所占據的比例.[10]所求簇的簇內相似度的結果，以及所求簇間相似度的結果最后得出全部的類簇簇內似度都小于閾值[11].

2.3 稍加改進的k-means算法

進行改進后使用二分法進行實驗：

在距離公式的選取上我們可以使用歐氏距離來進行確定各個點對于質心的真實距離.[12]同時它也是我們所運用的2，3維空間中的點與點之間的真實距離.

公式如下：

2.4 K-means算法在真實數據的算法分析應用實驗

第一步：從數據庫中調出合集，正規化，進行處理.然后通過肘方法的運算來確定我們所進行實驗運用的K值.

第二步計算每一個樣本和數據集合中所有樣本的歐式距離的平方，也就是點與點之間的平方數據.

第三步：對所有樣本進行聚類，設置K的數值，對于搜友樣本隨機選取得到質心，不斷進行迭代，查看是否收斂.

第四步：迭代以后，若是聚類中心沒有發生明顯的變化了，就說明聚類中心已經開始收斂了，我們就可以退出迭代.

第五步：輸出所構造的圖形.

可以看出圖像中還有極少量個孤立點，我們知道孤立點對于k-means算法的影響是很大的，對于孤立點可能使得k-means算法產生局部的解而不是全局的解，所以我們要對孤立點進行處理.

2.5 基于鳶尾花的數據實驗分析

實驗二是使用當時著名的鳶尾花數據進行編寫，我們已使用150個數據，而且數據集中還有兩種花的種類之分，本次實驗不對種類進行考慮.直觀上無法對4維數據進行可視化，所以我們為了更好的使用數據進行處理，我們首先使用pca對多維數據進行降維，然后再進行可視化操作實驗.首先使用肘部法則進行運算得出最適合該數據的K值為3，所以我們取K=3時進行聚類.

我們對這組真實數據進行聚類分析，進行類比得到與真實數據一樣的結果，我們進行實驗取得4個屬性的后兩個進行聚類實驗，將我們的聚類結果進行可視化，也有一定的數據點為孤立點，對孤立點進行處理時采取距離和的思想，排除孤立點的影響.

3 總結

通過對與大數據云計算的理解，分類方式的了解，python環境的用，k-means算法等等知識的學習，對于k-means算法的一個應用實現.本篇論文中詳細的解釋了python的具體知識k-means分類算法的重要思想，各個模塊的步驟的仔細設計與聯系方式，在python的開發環境中實現了一些基本算法.

【參考文獻】

[1]丁睿，基于高斯分布隨機樣本生成的小樣本聚類算法[J].電腦知識與技術，2013（29）：6609-6611.

[2]王淋銥，基于關聯規則的教務分析系統的設計與研究[D].計算機技術，2015-01-01.

[3]馬仕玉，聚類算法及其在校園網用戶行為分析中的應用[D].計算機系統結構，2015-01-01.

[4]郭虎升，王文劍，基于主動學習的模式類別挖掘模型[M].計算機研究與發展，2014，51（10）：2148-2159.

[5]Zhang T.Ramakriahnan R.Linvy M.BIRCH：An efficient data clustering method for very large databases.In：Jagadish HV，Mumick IS，eds.Proc.of the ACM SIGMOD Intl Conf.on Management of Data.New York；ACM Press.1988.73-84.