一种k-means聚类的改进算法与实现
开篇：润墨网以专业的文秘视角，为您筛选了一篇一种k-means聚类的改进算法与实现范文，如需获取更多写作素材，在线客服老师一对一协助。欢迎您的阅读与分享！
摘 要：传统的k-means算法作为一种动态聚类法，是聚类方法中常用的一种划分方法，其应用领域非常广泛。但该方法存在初始k值不确定、时间复杂度大等缺点。针对这些缺点，改进了聚类初值的随机性问题，简化了算法，降低了时间复杂度，提高了k-means算法的性能，并给出了具体的代码实现。
关键词：动态聚类； k-means 算法；初值
中图分类号：TP312 文献标识码：A 文章编号：1672-7800（2012）003-0066-05
基金项目：广东省自然科学基金项目（9151170003000017）
作者简介：冯能山（1972-），男，广西大新人，硕士，东莞理工学院讲师，研究方向为人工智能、软件工程。
0 引言
当今社会，数据挖掘作为一种新的技术，吸引了信息产业的普遍关注，其主要原因是数据越来越多，急需将这些数据转换成有用的信息和知识。聚类是指将抽象对象的集合分成由类似的对象组成的多个类的过程。由聚类所生成的簇是一组数据对象的集合，这些对象与同一个簇中的对象彼此相似，与其它簇中的对象相异。聚类分析又称群分析，它是研究（样品或指标）分类问题的一种统计分析方法。聚类的分析研究需要我们给出新的算法来推动数据挖掘技术的发展。
信息技术的迅猛发展给数据挖掘技术带来了新的机遇和挑战，而聚类算法作为数据挖据主要方法之一，自然也越来越受到人们关注。k-means 算法作为聚类的一种典型算法，是根据函数准则进行分类的聚类算法，基于使聚类准则函数最小化，是应用最为广泛的聚类算法之一。该算法以各样本的质心代表该类，适用于数字属性数据的聚类，对球形和凸形数据有很好的聚类效果。但k-means 算法还存在一些不足之处，比如：受到多个因素的影响；制定的聚类中心的个数是否符合模式的实际分布；所选聚类中心的初值；模式样本分布的几何性质；样本读入次序等等。为此，本文从优化初值的角度提出一个解决方案，并给出该方案的C代码实现。
1 算法及问题
1.1 k-means算法
k-means算法是一个简单而有效的统计聚类技术。其步骤如下：①选择一个k值，用以确定簇的总数；②在数据集中任意选择k个实例，它们是初始的簇中心；③使用简单的欧氏距离，计算簇中点到中心的距离；④得出新簇，并同前面的簇比较，相同就停止迭代，不同就继续迭代，直到相同为止，得出的簇就是最后的聚类结果。
不妨假设有下面几个平面的坐标点，如图1所示。
具体数据如表1所示。
1.2 该算法存在的问题
(1) 算法的初始簇随机性太大，由于算法是一个不断的迭代过程，这时初值的作用就很大。
(2) 算法开始要给定一个初值k，来确定这一系列数据到底要被分成几类，很多数据我们不知道到底存在着几类，因此初值k选取很多时候会影响到挖掘结果的理想程度。
(3) 由于算法是一个不断迭代的分簇过程，如果数据很多，算法的时间复杂度就很大。
1.3 问题的解决
1.3.1 算法初值分析
使用k-means算法进行聚类，无论数据多少，都要选取k个点作为初始聚类中心，然后进行反复的迭代。由于初始簇选择具有一定的随意性，初始聚类中心不同，算法的时间空间复杂度就不同，在上面例子中，如果随机选取的簇为C\-1={b,d,f}，C\-2={a,c,e}的话，只需要一次迭代就把问题给解决了，因此需要在算法的初值处改进。
1.3.2 算法改进
由于使用k-means算法开始的簇是随机选取的，这样会给程序带来不可预测的算法复杂度，因此这里我们算法开始的簇不随机选择，而是根据一定的规则来选取。假设先选取一个点作为初始点，在计算数据集中每个点到这个点的距离，选出距离最短的点作为一个簇，这样就可以减少迭代的次数，减少算法的执行时间空间复杂度。
1.3.3 算法的具体步骤
①根据k值和点N的个数，确定初值簇中每个簇的个数，理论上每个簇中点的个数为N/k个，余数单独加入到最后得出的那个簇中；②随机选取一个点a，作为算法的初始点，然后开始计算数据中每一个点到点a的欧氏距离；③用一个排序算法，按照从小到大的方式把数据排列好，然后从中选取N/k-1个数据再加上点a，就构成了一个簇；④再把余下的N-N/k个点按照从①-③的办法一次选出一个簇，N/k如果有余数，就把余数的簇放入到最后的那个簇中；⑤经过上述步骤，就完成了初值簇的选取。
2.2 源代码中几个关键函数
(1) Void sequence()：排序函数。在这个函数里面，把初始点到其他点的距离进行由大到小的排序，方便后面程序的使用。
(2) Int RandDot()：随机函数。随机取得一个点，用来初始化点使用。
(3) Float distance()：求两点间的距离函数。求两点间的欧氏距离。
(4) Void Select()：点的选取函数。通过N/k的值，来确定每个簇中需要的点的个数，然后根据sequence( )函数选出的前N/k个值作为一个簇，N/k的数据留着继续下次计算使用。
3 结束语
k-means 算法首先需要根据初始聚类中心来确定一个初始划分，然后对初始划分进行优化，这个初始聚类中心的选择对聚类结果有较大的影响，一旦初始值选择得不好，可能无法得到有效的聚类结果，所以对该问题的研究成为k-means 算法的热点。本文给出的算法是在传统算法的基础上，在初值设定方面作了一种改进，并给出了这种改进的C代码实现，有助于提高传统的k-means算法的性能。
参考文献：
\[1\] 张云涛.数据挖掘原理与技术\[M\].北京：电子工业出版社，2004.
\[2\] JIAWEI HAN，MICHELINE KAMBER.数据挖掘概念与技术\[M\]．范明，孟小峰，译.北京：机械工业出版社，2001.
\[3\] 谭勇，荣秋生.一个基于k-means的聚类算法的实现\[J\].湖北民族学院学报，2004(1).
\[4\] 范森淼，程晓青.数量关联规则发现中的聚类方法研究\[J\].计算机学报，2000(8).
\[5\] 王实，高文.数据挖掘中的聚类算法\[J\].计算机科学,2000(4).
\[6\] 齐敏，李大健，郝重阳.模式识别导论\[M\].北京：清华大学出版社，2009.
\[7\] 万小军，杨建武，陈小鸥.文档聚类中k-means算法的一种改进算法［J］.计算机工程，2003(2).
\[8\] 王林，吴海桥，郑友石.一种改进的k均值聚类算法\[J\].科技信息，2010(2).
\[9\] 岑咏华，王晓蓉，吉雍慧.一种基于改进k-means的文档聚类算法的实现研究［J］.现代图书情报技术，2011(12).
An Improved K-Means Clustering Algorithm and Its Implementation
Abstract:As a dynamic clustering method, the traditional algorithms of k-means is a common way of division in clustering with its wide applications in a range of fields. However, this means is flawed for a series of shortcomings with it including the uncertain initial value in k and the high degree of time complexity. In order to overcome these problems, this paper contributes to make improvements in the resolution of the random problem of initial value for clustering and the simplification for the algorithm as well as the reduction in the degree of time complexity. Furthermore,the paper also enhances the performance of the algorithms of k-means and provides a concrete code for implementation.
Key Words: Dynamic Clustering; K-Means Algorithm; Initial Value