基于Python的K-means算法實現方式對比研究

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

關鍵詞： Python;K-means;Numpy;聚類

中圖分類號： TP301.6 ? ?文獻標識碼： A ? ?DOI：10.3969/j.issn.1003-6970.2020.08.025

本文著錄格式：王習濤. 基于Python的K-means算法實現方式對比研究[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 ?引言

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

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

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

1 ?K-means算法簡介

聚類是一種經典、流行的數據挖掘技術，是一種無監督學習方法，以“物以類聚”為指導思想，廣泛應用于模式識別、機器學習、圖像處理等各個方面，尤其是伴隨著大數據時代的到來，大量未經標識的數據為聚類研究提供了新的舞臺。常見的聚類算法有基于劃分方法、基于層次方法、基于密度方法、基于網格方法和基于模型方法。其中K-means算法是一種經典的基于劃分的聚類算法。

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

2 ?傳統編程方式編寫的K-means算法

傳統編程方式嚴格按照K-means算法定義循環計算每個對象與所有簇中心的距離，并為各數據對象打標識，再根據新標識進行分類并生成新的簇中心。

Python常規編程方法實現K-means算法偽代碼

輸入：預設簇中心數目K;待分類的數據集。

輸出：K個分類數據集。

（1）選擇隨機簇中心

（2） ?For對每個數據點循環

（3） ? ?For對每個簇中心循環

（4） ? ? ?For對每個屬性值循環

（5） ? ? ? ?求解每個屬性值與簇中心對應屬性值的差的平方

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

（7） ? ?將數據點歸屬到距離最近的簇中心

（8）根據對象歸屬生成新的簇中心

（9）重復2-8，直到各數據對象與簇中心的歐式距離不再變動

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

Python+Numpy編程首先使用Numpy包的tile函數實現數據擴維，將分類數據和選定的初始簇中心分別擴展到維度如（數據集樣本數目，簇中心點數目，屬性數目）的三維矩陣，通過矩陣間的向量運算生成距離矩陣，再根據距離矩陣采用Numpy的argmin函數對距離矩陣求行向量的最小值索引（距離最近中心點的索引），按照索引對數據點進行分類標識，重復執行生成新的均值中心、距離矩陣和分類結果，直到完成聚類運算。

Python+Numpy方式實現K-means算法偽代碼

輸入：預設聚類中心數目K;待分類的數據集。

輸出：K個分類數據集。

（1）選擇隨機簇中心

（2）使用Numpy的tile函數將數據對象矩陣擴展到簇中心個數維度

（3）使用Numpy的tile函數將簇中心矩陣擴展到數據對象個數維度

（4）通過Numpy的transpose函數調整擴展后的數據對象和簇中心三維矩陣

（5）將擴展后的數據對象和簇中心矩陣執行減法，求平方，并按屬性維度求和后再開平方

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

（7）根據對象到簇中心的距離判斷對象歸屬

（8）根據對象歸屬生成新的簇中心

（9）重復2-8，直到各對象與簇中心的歐式距離不再變動

4 ?仿真實驗及分析

4.1 ?實驗描述

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

實驗環境為Windows7 64位操作系統，AMD A8 PRO-7600B 3.10 GHz CPU，4 GB內存，軟件環境為Pycharm professional 2019.3 Python 3.6.5。

在UCI數據集和合成數據集上分別運行程序100次，得到運行時間如表2所示。

4.2 ?對比分析

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

5 ?總結

Python編程語言異軍突起是時代發展的需求，同時也是因為Python順應了大數據計算的新態勢，伴隨著電子信息產業的飛速發展，計算機運算空間大幅拓展，Python基于向量式的多維矩陣運算適當其時，在人工智能領域依靠TensorFlow+高端顯卡的運算模式為深度神經網絡的應用打開了帷幕，同時也預示著數據計算方式由傳統的循環、過程式跨越到批量、向量化的新時代，可以預見，在不遠的未來，伴隨著5G時代的到來，分布與集中相配合的深度向量式運算將深入生活的各個角落，同時也將改變人們思考問題的方式。

參考文獻

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

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

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

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

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

[6] Pang-Ning Tan， Michael Steinbach， Vipin Kunmar著， 范明， 范宏建等譯. 數據挖掘導論（完整版）[M]. 人民郵電出版社， 2011.

[7] 劉鵬， 張燕著. 數據挖掘[M]. 電子工業出版社， 2018.

[8] 熊赟， 朱揚勇， 陳志淵著. 大數據挖掘[M]. 上?？茖W技術出版社， 2016.

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

[10] Peter Harrington著， 李銳， 李鵬， 曲亞東， 王斌譯. 機器學習實戰[M]. 人民郵電出版社， 2013.