基于Python的K—means算法及其應(yīng)用

薛芯菊

【摘 要】k-means 算法是一種無(wú)監(jiān)督的簡(jiǎn)單機(jī)械學(xué)習(xí)算法的一種，也是數(shù)據(jù)挖掘中一個(gè)非常有用的聚類分析方法.現(xiàn)在社會(huì)中聚類算法對(duì)于各個(gè)方面分類問(wèn)題可以進(jìn)行分析求解求其最優(yōu)解.本文采用了python這一語(yǔ)言環(huán)境進(jìn)行研究，使用了UCI中的真實(shí)數(shù)據(jù)來(lái)進(jìn)行實(shí)驗(yàn)分析.使用python對(duì)K-means算法進(jìn)行編寫，通常我們用k-means算法進(jìn)行運(yùn)算時(shí)K值是規(guī)定的，本文使用肘部法則確定其K.有的數(shù)據(jù)無(wú)法直接使用，所以通過(guò)pca降維是數(shù)據(jù)可以更好的展示出來(lái)，再通過(guò)python編譯環(huán)境對(duì)真實(shí)數(shù)據(jù)進(jìn)行可視化操作，形成了真實(shí)數(shù)據(jù)和我們所選取的數(shù)據(jù)的可視化圖像。

【關(guān)鍵詞】k-means；Python；聚類

中圖分類號(hào)： TP18 文獻(xiàn)標(biāo)識(shí)碼： A 文章編號(hào)： 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

聚類分析的算法分為劃分法、層次法、基于密度的方法、基于網(wǎng)格的方法、基于模型的方法，并且聚類分析也可以作為數(shù)據(jù)挖掘算法中其他分析算法的一個(gè)預(yù)處理步驟[1-2].可以運(yùn)用數(shù)學(xué)與計(jì)算機(jī)的研究模式進(jìn)行運(yùn)算，根據(jù)數(shù)據(jù)庫(kù)中的多條信息進(jìn)行大致的概括，然后進(jìn)行區(qū)分，分為多個(gè)元素一一進(jìn)行更加深入的研究分析.與K-means算法極為相似的一個(gè)算法為K中心算法也是就K-Mediods算法[3]，數(shù)據(jù)挖掘又被人們稱為數(shù)據(jù)庫(kù)中的知識(shí)發(fā)現(xiàn)，數(shù)據(jù)挖掘就是擁有潛在的大量信息價(jià)值的重要發(fā)覺(jué)過(guò)程[4].

1 k-means算法

1.1 k-means算法的研究思路

層次法[5]是一種對(duì)與給定的數(shù)據(jù)，進(jìn)行數(shù)據(jù)分析處理的一種方法，當(dāng)我們是用層次法滿足我們給定的一些條件時(shí)，聚類算法可以進(jìn)行運(yùn)行.以下的兩種條件是構(gòu)建起來(lái)我們聚類的基本條件.

1.2 確定K值的方法

對(duì)于不確定的K值我們還可以使用肘部法則進(jìn)行確定K值來(lái)，但是隨著K的不斷增大，我們可以看到平均畸變程度會(huì)不斷的減少，導(dǎo)致在K值的增大.

同時(shí)，還有一種方法對(duì)一個(gè)我們所選用的樣本數(shù)據(jù)集合進(jìn)行兩次采集產(chǎn)生兩個(gè)數(shù)據(jù)樣本集，再用一樣的聚類算法對(duì)我們算選用的樣本數(shù)據(jù)集合進(jìn)行聚類，產(chǎn)生相應(yīng)的聚類結(jié)果，計(jì)算分布情況.這種方式就是我們不斷進(jìn)行實(shí)驗(yàn)計(jì)算所取得的最適合的K值.這就是我們剛才所介紹的穩(wěn)定性確定K值的方法.

1.3 pca降維

在理解我們所用的數(shù)據(jù)的時(shí)候可能數(shù)據(jù)的維數(shù)較多.[15]所以我們使用數(shù)據(jù)的時(shí)候往往會(huì)產(chǎn)生維度災(zāi)難.我們可以使用這種方法對(duì)于相關(guān)的高維數(shù)的變量合成線性無(wú)關(guān)的低維變量.

PCA降維：

第一步：使用所給出的樣本數(shù)據(jù)減去樣本均值.

第二步：計(jì)算數(shù)據(jù)的主要樣本成分，計(jì)算矩陣數(shù)據(jù)協(xié)方差矩陣.

第三步：咱們要形成一個(gè)轉(zhuǎn)換矩陣來(lái)進(jìn)行映射同時(shí)轉(zhuǎn)換成為我們數(shù)據(jù)運(yùn)算的主要成分.

2 基于python語(yǔ)言的實(shí)驗(yàn)分析

2.1 python基礎(chǔ)概念

Python是一個(gè)開(kāi)元自由的高性能語(yǔ)言，源代碼和解釋器CPython遵循 GPL協(xié)議，Python語(yǔ)法構(gòu)造十分方便使用清晰明了，他最大的特色就是是強(qiáng)制使用空格作為語(yǔ)句縮進(jìn)的一種手段[9].

2.2 在python下的k-means算法分析實(shí)驗(yàn)

第一步：先從指定的所需數(shù)據(jù)樣本對(duì)象中選取相應(yīng)的對(duì)象作為初始單位的中心點(diǎn).

第二步：再根據(jù)所求的每個(gè)聚類對(duì)象的值，計(jì)算我們所使用的值與所算質(zhì)心的真實(shí)距離.

第三步：根據(jù)最小距離重新對(duì)相應(yīng)的對(duì)象進(jìn)行歸類劃分.

第四步：從x個(gè)對(duì)象中選取的μ個(gè)對(duì)象作為初始中心點(diǎn)也就是所謂的質(zhì)心，剩下的則根據(jù)距離進(jìn)行相似聚類運(yùn)算.

第五步：將他們跟他們最為相似的點(diǎn)進(jìn)行歸類處理.

第六步開(kāi)始會(huì)出現(xiàn)一些偏差，之后進(jìn)行不斷的迭代不停地運(yùn)算使得算法越來(lái)越接近標(biāo)準(zhǔn)的數(shù)值收斂到一定程度后，繼續(xù)運(yùn)算的結(jié)果會(huì)趨近以一個(gè)數(shù)值不變.

同時(shí)在K-means算法的目標(biāo)函數(shù)中插入一個(gè)新的數(shù)據(jù)項(xiàng)，該數(shù)據(jù)項(xiàng)用于估測(cè)其他與其接近的聚類中心點(diǎn)與當(dāng)前聚類中心點(diǎn)的真實(shí)距離的平方和，并引入了一個(gè)權(quán)值，用于調(diào)節(jié)數(shù)據(jù)項(xiàng)在全部目標(biāo)函數(shù)中所占據(jù)的比例.[10]所求簇的簇內(nèi)相似度的結(jié)果，以及所求簇間相似度的結(jié)果最后得出全部的類簇簇內(nèi)似度都小于閾值[11].

2.3 稍加改進(jìn)的k-means算法

進(jìn)行改進(jìn)后使用二分法進(jìn)行實(shí)驗(yàn)：

在距離公式的選取上我們可以使用歐氏距離來(lái)進(jìn)行確定各個(gè)點(diǎn)對(duì)于質(zhì)心的真實(shí)距離.[12]同時(shí)它也是我們所運(yùn)用的2，3維空間中的點(diǎn)與點(diǎn)之間的真實(shí)距離.

公式如下：

2.4 K-means算法在真實(shí)數(shù)據(jù)的算法分析應(yīng)用實(shí)驗(yàn)

第一步：從數(shù)據(jù)庫(kù)中調(diào)出合集，正規(guī)化，進(jìn)行處理.然后通過(guò)肘方法的運(yùn)算來(lái)確定我們所進(jìn)行實(shí)驗(yàn)運(yùn)用的K值.

第二步計(jì)算每一個(gè)樣本和數(shù)據(jù)集合中所有樣本的歐式距離的平方，也就是點(diǎn)與點(diǎn)之間的平方數(shù)據(jù).

第三步：對(duì)所有樣本進(jìn)行聚類，設(shè)置K的數(shù)值，對(duì)于搜友樣本隨機(jī)選取得到質(zhì)心，不斷進(jìn)行迭代，查看是否收斂.

第四步：迭代以后，若是聚類中心沒(méi)有發(fā)生明顯的變化了，就說(shuō)明聚類中心已經(jīng)開(kāi)始收斂了，我們就可以退出迭代.

第五步：輸出所構(gòu)造的圖形.

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

2.5 基于鳶尾花的數(shù)據(jù)實(shí)驗(yàn)分析

實(shí)驗(yàn)二是使用當(dāng)時(shí)著名的鳶尾花數(shù)據(jù)進(jìn)行編寫，我們已使用150個(gè)數(shù)據(jù)，而且數(shù)據(jù)集中還有兩種花的種類之分，本次實(shí)驗(yàn)不對(duì)種類進(jìn)行考慮.直觀上無(wú)法對(duì)4維數(shù)據(jù)進(jìn)行可視化，所以我們?yōu)榱烁玫氖褂脭?shù)據(jù)進(jìn)行處理，我們首先使用pca對(duì)多維數(shù)據(jù)進(jìn)行降維，然后再進(jìn)行可視化操作實(shí)驗(yàn).首先使用肘部法則進(jìn)行運(yùn)算得出最適合該數(shù)據(jù)的K值為3，所以我們?nèi)=3時(shí)進(jìn)行聚類.

我們對(duì)這組真實(shí)數(shù)據(jù)進(jìn)行聚類分析，進(jìn)行類比得到與真實(shí)數(shù)據(jù)一樣的結(jié)果，我們進(jìn)行實(shí)驗(yàn)取得4個(gè)屬性的后兩個(gè)進(jìn)行聚類實(shí)驗(yàn)，將我們的聚類結(jié)果進(jìn)行可視化，也有一定的數(shù)據(jù)點(diǎn)為孤立點(diǎn)，對(duì)孤立點(diǎn)進(jìn)行處理時(shí)采取距離和的思想，排除孤立點(diǎn)的影響.

3 總結(jié)

通過(guò)對(duì)與大數(shù)據(jù)云計(jì)算的理解，分類方式的了解，python環(huán)境的用，k-means算法等等知識(shí)的學(xué)習(xí)，對(duì)于k-means算法的一個(gè)應(yīng)用實(shí)現(xiàn).本篇論文中詳細(xì)的解釋了python的具體知識(shí)k-means分類算法的重要思想，各個(gè)模塊的步驟的仔細(xì)設(shè)計(jì)與聯(lián)系方式，在python的開(kāi)發(fā)環(huán)境中實(shí)現(xiàn)了一些基本算法.

【參考文獻(xiàn)】

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

[2]王淋銥，基于關(guān)聯(lián)規(guī)則的教務(wù)分析系統(tǒng)的設(shè)計(jì)與研究[D].計(jì)算機(jī)技術(shù)，2015-01-01.

[3]馬仕玉，聚類算法及其在校園網(wǎng)用戶行為分析中的應(yīng)用[D].計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)，2015-01-01.

[4]郭虎升，王文劍，基于主動(dòng)學(xué)習(xí)的模式類別挖掘模型[M].計(jì)算機(jī)研究與發(fā)展，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.