基于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]. 上海科学技术出版社， 2016.
　　[9] Magnus Lie Hetland著， 袁国忠译. Python基础教程（第3版）[M]. 人民邮电出版社， 2018.
　　[10] Peter Harrington著， 李锐， 李鹏， 曲亚东， 王斌译. 机器学习实战[M]. 人民邮电出版社， 2013.
转载注明来源:https://www.xzbu.com/8/view-15321725.htm