基于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.