龙源期刊网 http://www.qikan.com.cn
一种基于Python的K—means聚类算法分析
作者：陈伟 李红 王维
来源：《数字技术与应用》2017年第10期
摘要：聚类是数据挖掘核心技术之一，是一门新兴的学科。聚类技术要使一个类簇内的实体是相似的，不同类簇的实体是相异的。从聚类研究现状谈起， 描述聚类概念和分类方法，介绍K-means算法的思想，并利用K-mean算法实现了iris数据集的分类，完成相关测试和实验验证。
关键词：聚类分析；K-Means算法；数据挖掘
中图分类号：TP301.6 文献标识码：A 文章编号：1007-9416（2017）10-0118-02
聚类是数据挖掘技术中一个非常重要的分支，它是在没有任何先验知识的前提下，从海量数据中提取出有价值的、未知的数据。实现满足要求的簇的集合。 1 聚类分析研究现状
聚类分析是一个将数据集划分成若干个子集的过程，并使同一集合内的数据对象具有较高的相似度，而不同集合中的数据对象不相似。国内外对聚类分析的研究已经有很多年，学者们研究的主要内容是基于距离的聚类分析，K-Medoids算法、K-Means算法以及其他的聚类算法的挖掘工具在众多的统计软件或者系统中得到广泛的应用。
1967年，MacQueen首次提出K均值聚类算法（K-means算法）。迄今为止，很多聚类任务都选择该经典算法。该算法的核心思想是找出K个聚类中心、，…，，使得每一个数据点和与其最近的聚类中心的平方距离和被最小化。
1998年，Huang为克服K-Means算法仅适合于数值属性数据聚类的局限性，提出了一种适合分类属性数据聚类的K-Modes算法，该算法对K-Means算法进行了3点扩展：引入了处理分类对象的新的相异性度量方法，使用modes代替means，并在聚类过程中使用基于频度的方法修正modes，以使聚类代价函数值最小。
2002年，Sun等人将Bradley等人的迭代初始点集求精算法应用于K-Modes算法。尽管Huang的K-Modes算法能够聚类分类数据，但它需要预先决定或随机选择类的初始modes，并且初始modes的差异常常会导致截然不同的聚类结果。文中，Sun等人给出了一个关于应用Bradley等人的迭代初始点求精算法于K-Modes聚类的实验研究。
龙源期刊网 http://www.qikan.com.cn
2010年，李卫平[7]提出对K-Means算法进行改进。他针对K-Means算法对初值的依赖性，基于最小生成树原理选择聚类中心进行聚类。根据寻找最优初值的思想提出了一种改进K-Means算法，并将卡斯克鲁尔算法以及贪心算法的思想引入到K-Means算法中。 2 聚类分析算法 2.1 划分法
K-MEANS算法、K-Medoids算法是典型的划分法（partitioning methods）。算法的处理思路基本是：给定一个类库D，D中含有N个数据对象，用户输入需要获得的类簇个数K，将类库D中N个数据对象划分成K个分组或者簇，然后通过迭代的方式更新簇的中心，当整体的差异收敛时结束处理过程。使得簇内的相似度更高（更相似），簇间的相异性更高（差异更大）。
划分法的代表算法有：K-Medoids算法、CLARANS算法、K-Means算法。 2.2 层次法
对给定的数据，进行层次分解，直到某种条件满足。层次法构建聚类的方法有分为两种： （1）凝聚层次法（自底向上法）：首先将类库中的每一个数据划分每一个单独的类，通过递归的方法，将相似的或者相近的类合并成为一个类，最后使得一个类中所包含的数据或者分类结果满足某种条件。
（2）分裂层次法（自顶向上法）：开始将所有的对象划分成为一个类，然后将总类划分成为若干个子类，接着在划分出子类的子类，一直迭代划分，直到获得满意的聚类结构。 2.3 基于密度的方法
基于密度的方法是假定每个簇中的数据对象点是按照一个特定的概率分布绘制的，数据的整体分布被假设成为几个分布的混合体，这种方法是识别出簇以及他们的分布函数。基于密度方法的思想：对于一个给定的簇，这个簇持续的增长，直至周围的密度（对象的数目或者说是数据点的数目）大于一个阀值时为止。 2.4 基于模型的方法
基于模型的方法（model-basedmethods）给每一个聚类假定一个模型，然后试图去寻找能很好的满足这个模型的数据集。该方法识别对象的组别，可以很快地发现每个组的特征描述，每组代表一个概念或者是一个类。最常用的方法有决策树和神经网络法。 2.5 基于网格的方法
龙源期刊网 http://www.qikan.com.cn
基于网格的方法（grid-basedmethods）是将所有的数据划分为若干个有限数据细胞单元格，从而形成一个可以进行聚类操作的网格结构，这样的分割，是所有的数据对象都可以在数据网络格上进行操作，和原始数据本身无关。基于网络的方法最主要的优点是其快速的处理速度。
基于网格的方法的主要算法有：STING算法、CLIQUE算法、WAVE-CLUSTER算法。 3 K-means算法
K-means算法是根据聚类中的均值进行聚类划分的聚类算法。 输入：聚类个数，以及包含个数据对象的数据； 输出：满足方差最小标准的个聚类； 处理流程：
Step1：从个数据对象任意选择个对象作为初始聚类中心； Step2：循环Step 3到Step 4直到每个聚类不再发生变化为止；
Step3：根据每个聚类对象的均值（中心对象），计算每个对象与这些中心对象的距离，并根据最小距离重新对相应对象进行划分；
Step4：重新计算每个（有变化）聚类的均值（中心对象）k-means算法的工作过程说明如下：首先从个数据对象任意选择个对象作为初始聚类中心，而对于所剩下的其它对象，则根据它们与这些聚类中心的相似度（距离），分别将它们分配给与其最相似的（聚类中心所代表的）聚类；然后，再计算每个所获新聚类的聚类中心（该聚类中所有对象的均值），不断重复这一过程直到标准测度函数开始收敛为止。一般都采用均方差作为标准测度函数，具体定义如下：
（公式1.1）
（：数据库中所有对象的均方差和；：对象的空间中的一个点；：聚类的均值（和均是多维的））
4 改进K-means算法
二分K-均值算法的伪代码形式如下： 将所有的点看成一个簇。