基于Python的K-means算法實(shí)現(xiàn)方式對(duì)比研究

摘 ?要： 大數(shù)據(jù)時(shí)代的到來使Python語言受到越來越多的關(guān)注。在國際上，IEEE頒布的頂級(jí)編程語言交互排行榜中，Python已連續(xù)多年名列榜首，在國內(nèi)，Python已經(jīng)進(jìn)入義務(wù)教育階段小學(xué)課程。Python以其可讀性強(qiáng)、使用范圍廣受到越來越多計(jì)算機(jī)使用人員的歡迎。Python在數(shù)據(jù)處理方面光彩奪目的表現(xiàn)得益于和其他過程控制語言的巨大不同，本文以經(jīng)典K-means算法的實(shí)現(xiàn)為切入點(diǎn)，通過不同的編程方式實(shí)現(xiàn)同樣的聚類過程，在UCI和生成數(shù)據(jù)集上分別運(yùn)行不同程序，發(fā)現(xiàn)采用Numpy數(shù)據(jù)處理庫可以顯著提升程序運(yùn)行效率，減少運(yùn)行時(shí)間，展現(xiàn)出Python向量式數(shù)據(jù)計(jì)算的巨大優(yōu)勢。

關(guān)鍵詞： Python;K-means;Numpy;聚類

中圖分類號(hào)： TP301.6 ? ?文獻(xiàn)標(biāo)識(shí)碼： A ? ?DOI：10.3969/j.issn.1003-6970.2020.08.025

本文著錄格式：王習(xí)濤. 基于Python的K-means算法實(shí)現(xiàn)方式對(duì)比研究[J]. 軟件，2020，41（08）：87-88+128

【Abstract】： With the advent of the big data era， python language has attracted more and more attention. Internationally，in the top programming language interaction ranking released by IEEE， python has been ranked first for many years. In China， python has entered primary school. Python is widely used by more and more computer users because of its readability. However， Python's advantages in data processing are also shown out of the huge differences of other process control languages. This paper takes the implementation of the classic k-means algorithm as an examples， program the same clustering process by different programming methods， run the program ?on the UCI and generating data set respectively， we found that using numpy data processing library can significantly improve the running efficiency of the program and reduce the running time， so then show the huge advantages of Python vector data computing.

【Key words】： Python; K-means; Numpy; Cluster

0 ?引言

近年來，伴隨著電子信息技術(shù)的進(jìn)步，數(shù)據(jù)采集終端越來越普及，采集效率越來越高，大數(shù)據(jù)時(shí)代已經(jīng)到來。數(shù)據(jù)量爆炸式的增長對(duì)數(shù)據(jù)分析處理工作提出了更高要求，傳統(tǒng)的基于過程控制的編程語言使用循環(huán)、嵌套較多，對(duì)數(shù)據(jù)精細(xì)化操作較多，在大規(guī)模數(shù)據(jù)分析、開發(fā)上顯得捉襟見肘。

Python是一種簡單易學(xué)的解釋性語言，以簡潔為編程基本要求，擁有豐富的第三方庫，在web開發(fā)、網(wǎng)絡(luò)爬取、自動(dòng)化運(yùn)維、人工智能、數(shù)據(jù)分析等各個(gè)方面得到廣泛應(yīng)用。然而，作為一種解釋性程序語言，Python本身運(yùn)行速度較慢，如果只采用傳統(tǒng)編程方式編寫代碼，運(yùn)行速度將不可忍受。

為了展現(xiàn)Python與傳統(tǒng)過程控制語言在編程思想的巨大差別，本文以經(jīng)典K-means聚類算法為范例，分別采用傳統(tǒng)循環(huán)控制方式與Numpy庫編程方式實(shí)現(xiàn)K-means算法，在設(shè)置隨機(jī)種子保證初始簇中心一致的情況下，通過在不同規(guī)模數(shù)據(jù)集上運(yùn)行對(duì)比分析，證實(shí)使用Numpy庫編寫的數(shù)據(jù)處理程序不僅實(shí)現(xiàn)簡單、不易犯錯(cuò)且運(yùn)算效率極高，較傳統(tǒng)編程方式具有巨大優(yōu)勢。

1 ?K-means算法簡介

聚類是一種經(jīng)典、流行的數(shù)據(jù)挖掘技術(shù)，是一種無監(jiān)督學(xué)習(xí)方法，以“物以類聚”為指導(dǎo)思想，廣泛應(yīng)用于模式識(shí)別、機(jī)器學(xué)習(xí)、圖像處理等各個(gè)方面，尤其是伴隨著大數(shù)據(jù)時(shí)代的到來，大量未經(jīng)標(biāo)識(shí)的數(shù)據(jù)為聚類研究提供了新的舞臺(tái)。常見的聚類算法有基于劃分方法、基于層次方法、基于密度方法、基于網(wǎng)格方法和基于模型方法。其中K-means算法是一種經(jīng)典的基于劃分的聚類算法。

K-means算法是一種基于迭代求解的聚類分析算法，具有原理簡單，收斂速度快的優(yōu)點(diǎn)，在人為設(shè)定K值的基礎(chǔ)上隨機(jī)生成簇中心，通過優(yōu)化函數(shù)反復(fù)迭代生成新的簇中心，直到優(yōu)化函數(shù)收斂到可接受范圍。具體過程：（1）預(yù)設(shè)分類數(shù)K，隨機(jī)選取K個(gè)對(duì)象作為初始簇中心。（2）計(jì)算每個(gè)對(duì)象與各個(gè)簇中心的歐式距離，把每個(gè)對(duì)象分配給距離它最近的簇中心。（3）根據(jù)分類情況計(jì)算各類簇的均值中心，形成各簇新的簇中心。（4）重復(fù)第（2）、（3）步過程，直到簇中心不再發(fā)生變動(dòng)或各對(duì)象到所屬簇中心的歐式距離和不再縮小為止。

2 ?傳統(tǒng)編程方式編寫的K-means算法

傳統(tǒng)編程方式嚴(yán)格按照K-means算法定義循環(huán)計(jì)算每個(gè)對(duì)象與所有簇中心的距離，并為各數(shù)據(jù)對(duì)象打標(biāo)識(shí)，再根據(jù)新標(biāo)識(shí)進(jìn)行分類并生成新的簇中心。

Python常規(guī)編程方法實(shí)現(xiàn)K-means算法偽代碼

輸入：預(yù)設(shè)簇中心數(shù)目K;待分類的數(shù)據(jù)集。

輸出：K個(gè)分類數(shù)據(jù)集。

（1）選擇隨機(jī)簇中心

（2） ?For對(duì)每個(gè)數(shù)據(jù)點(diǎn)循環(huán)

（3） ? ?For對(duì)每個(gè)簇中心循環(huán)

（4） ? ? ?For對(duì)每個(gè)屬性值循環(huán)

（5） ? ? ? ?求解每個(gè)屬性值與簇中心對(duì)應(yīng)屬性值的差的平方

（6） ? ? ?對(duì)每個(gè)對(duì)象與簇中心的屬性值差平方求和并開平方，得到歐式距離

（7） ? ?將數(shù)據(jù)點(diǎn)歸屬到距離最近的簇中心

（8）根據(jù)對(duì)象歸屬生成新的簇中心

（9）重復(fù)2-8，直到各數(shù)據(jù)對(duì)象與簇中心的歐式距離不再變動(dòng)

3 ?Python+Numpy方式編寫的K-means算法

Python+Numpy編程首先使用Numpy包的tile函數(shù)實(shí)現(xiàn)數(shù)據(jù)擴(kuò)維，將分類數(shù)據(jù)和選定的初始簇中心分別擴(kuò)展到維度如（數(shù)據(jù)集樣本數(shù)目，簇中心點(diǎn)數(shù)目，屬性數(shù)目）的三維矩陣，通過矩陣間的向量運(yùn)算生成距離矩陣，再根據(jù)距離矩陣采用Numpy的argmin函數(shù)對(duì)距離矩陣求行向量的最小值索引（距離最近中心點(diǎn)的索引），按照索引對(duì)數(shù)據(jù)點(diǎn)進(jìn)行分類標(biāo)識(shí)，重復(fù)執(zhí)行生成新的均值中心、距離矩陣和分類結(jié)果，直到完成聚類運(yùn)算。

Python+Numpy方式實(shí)現(xiàn)K-means算法偽代碼

輸入：預(yù)設(shè)聚類中心數(shù)目K;待分類的數(shù)據(jù)集。

輸出：K個(gè)分類數(shù)據(jù)集。

（1）選擇隨機(jī)簇中心

（2）使用Numpy的tile函數(shù)將數(shù)據(jù)對(duì)象矩陣擴(kuò)展到簇中心個(gè)數(shù)維度

（3）使用Numpy的tile函數(shù)將簇中心矩陣擴(kuò)展到數(shù)據(jù)對(duì)象個(gè)數(shù)維度

（4）通過Numpy的transpose函數(shù)調(diào)整擴(kuò)展后的數(shù)據(jù)對(duì)象和簇中心三維矩陣

（5）將擴(kuò)展后的數(shù)據(jù)對(duì)象和簇中心矩陣執(zhí)行減法，求平方，并按屬性維度求和后再開平方

（6）得到對(duì)象與簇中心的歐式距離矩陣

（7）根據(jù)對(duì)象到簇中心的距離判斷對(duì)象歸屬

（8）根據(jù)對(duì)象歸屬生成新的簇中心

（9）重復(fù)2-8，直到各對(duì)象與簇中心的歐式距離不再變動(dòng)

4 ?仿真實(shí)驗(yàn)及分析

4.1 ?實(shí)驗(yàn)描述

為了對(duì)比不同編程方式對(duì)算法運(yùn)算效率的影響，在同樣的軟硬件設(shè)備環(huán)境下，通過設(shè)置隨機(jī)種子的方式，確保不同程序初始中心及運(yùn)行過程、結(jié)果完全一致，從而保證程序運(yùn)行時(shí)間具備可比性。并且為了進(jìn)一步降低偶然因素對(duì)程序運(yùn)行時(shí)間的影響，使程序循環(huán)運(yùn)行100次，對(duì)比總體運(yùn)行時(shí)間。采用的UCI數(shù)據(jù)集和合成數(shù)據(jù)集如表1所示。

實(shí)驗(yàn)環(huán)境為Windows7 64位操作系統(tǒng)，AMD A8 PRO-7600B 3.10 GHz CPU，4 GB內(nèi)存，軟件環(huán)境為Pycharm professional 2019.3 Python 3.6.5。

在UCI數(shù)據(jù)集和合成數(shù)據(jù)集上分別運(yùn)行程序100次，得到運(yùn)行時(shí)間如表2所示。

4.2 ?對(duì)比分析

從表2可以看出，在Python環(huán)境下，使用Numpy庫實(shí)現(xiàn)K-means算法較傳統(tǒng)編程方式時(shí)間優(yōu)勢明顯，并且伴隨著數(shù)據(jù)實(shí)例數(shù)和屬性數(shù)的增加時(shí)間差距會(huì)進(jìn)一步擴(kuò)大，究其原因是Python語言是解釋性語言，程序邊編譯邊運(yùn)行，運(yùn)行效率較低，而Numpy庫采用C語言編寫，并且已經(jīng)進(jìn)行了編譯，所以執(zhí)行效率有數(shù)量級(jí)的提高。進(jìn)一步研究可以發(fā)現(xiàn)，Numpy、Pandas等基于向量的運(yùn)算方式也為大數(shù)據(jù)計(jì)算揭開了帷幕，使以深度神經(jīng)網(wǎng)絡(luò)為代表的深度學(xué)習(xí)異軍突起，加速了圖像識(shí)別、語音識(shí)別、自動(dòng)翻譯、自動(dòng)駕駛等技術(shù)在各個(gè)方面的普及。

5 ?總結(jié)

Python編程語言異軍突起是時(shí)代發(fā)展的需求，同時(shí)也是因?yàn)镻ython順應(yīng)了大數(shù)據(jù)計(jì)算的新態(tài)勢，伴隨著電子信息產(chǎn)業(yè)的飛速發(fā)展，計(jì)算機(jī)運(yùn)算空間大幅拓展，Python基于向量式的多維矩陣運(yùn)算適當(dāng)其時(shí)，在人工智能領(lǐng)域依靠TensorFlow+高端顯卡的運(yùn)算模式為深度神經(jīng)網(wǎng)絡(luò)的應(yīng)用打開了帷幕，同時(shí)也預(yù)示著數(shù)據(jù)計(jì)算方式由傳統(tǒng)的循環(huán)、過程式跨越到批量、向量化的新時(shí)代，可以預(yù)見，在不遠(yuǎn)的未來，伴隨著5G時(shí)代的到來，分布與集中相配合的深度向量式運(yùn)算將深入生活的各個(gè)角落，同時(shí)也將改變?nèi)藗兯伎紗栴}的方式。

參考文獻(xiàn)

[1] 章永來， 周耀鑒. 聚類算法綜述[J]. 計(jì)算機(jī)應(yīng)用， 2019， 39（7）： 1869-1882.

[2] 張敏， 于劍. 基于劃分的模糊聚類算法[J]. 軟件學(xué)報(bào)， 2004， 15（6）： 858-868.

[3] 楊俊闖， 趙超. K-Means聚類算法研究綜述[J]. 計(jì)算機(jī)工程與應(yīng)用， 2019， 55（23）.

[4] 黃韜， 劉勝輝， 譚艷娜. 基于K-means聚類算法的研究[J]. 計(jì)算機(jī)技術(shù)與發(fā)展， 2011， 1（7）： 54-57， 62.

[5] 鄧濱玥. K均值優(yōu)化算法綜述[J]. 軟件， 2020， 41（2）： 188： 192.

[6] Pang-Ning Tan， Michael Steinbach， Vipin Kunmar著， 范明， 范宏建等譯. 數(shù)據(jù)挖掘?qū)д摚ㄍ暾妫M]. 人民郵電出版社， 2011.

[7] 劉鵬， 張燕著. 數(shù)據(jù)挖掘[M]. 電子工業(yè)出版社， 2018.

[8] 熊赟， 朱揚(yáng)勇， 陳志淵著. 大數(shù)據(jù)挖掘[M]. 上海科學(xué)技術(shù)出版社， 2016.

[9] Magnus Lie Hetland著， 袁國忠譯. Python基礎(chǔ)教程（第3版）[M]. 人民郵電出版社， 2018.

[10] Peter Harrington著， 李銳， 李鵬， 曲亞東， 王斌譯. 機(jī)器學(xué)習(xí)實(shí)戰(zhàn)[M]. 人民郵電出版社， 2013.