一种改进的K-means聚类算法*

周爱武，崔丹丹，肖 云

(安徽大学 计算机科学与技术学院，安徽 合肥 230039)

聚类分析[1](clustering)是数据挖掘研究的重要领域，借助聚类分析将大量的数据对象聚成不同的类簇，使不同簇之间的相似度低，簇内的相似度高，它是一种无监督的学习算法。为了实现对数据对象的聚类，人们提出了不同的聚类算法。聚类算法主要分成基于划分、基于密度、基于分层、基于网格和基于模型的五大类[2]。K-means(均值)聚类算法是典型的基于划分的聚类算法，同时也是应用最广泛的一种聚类算法。K-means聚类算法[3]主要针对处理大数据集，不但处理快速简单，而且算法具有高效性以及可伸缩性。但是K-means聚类算法存在K值需要事先指定、随机选择初始聚类中心等的局限性。人们针对K-means聚类算法的这些局限性提出了不同的改进算法。刘涛等人[4]提出了基于半监督学习的K-means聚类算法的研究，用粒子群算法以及迭代搜索的思想找到优质的聚类中心进行聚类；李飞等人[5]提出了基于遗传算法的全局搜索能力来解决初始聚类中心选择的敏感性问题。

K-means聚类算法由于初始聚类中心是随机选择的，容易造成算法会陷入局部最优解甚至是无解的情况，而聚类结果的好坏直接取决于初始聚类中心的选择。因此初始聚类中心的选择十分重要。本文主要针对随机选择初始聚类中心这一缺点，提出了一种新的改进的K-means聚类算法。

1 传统的K-means聚类算法

K-means聚类算法是解决聚类问题的一种经典算法，该算法具有简单、快速并且能够有效处理大数据集的特点。K-means聚类算法首先从n个数据对象中任意选取k个对象作为初始聚类中心；而对于所剩下的其他对象，则根据它们与这些聚类中心的相似度(距离)，分别将它们分配给与其最相似的类簇；然后计算该类簇中所有对象的均值；不断重复这一过程直到标准准则函数开始收敛为止。具体步骤如下[6]：

输入：k，data[n]；输出：k个簇的集合，满足聚类准则函数收敛。

(1)任意选择k个对象作为初始中心点，例如c[0]=data[0]，…c[k-1]=data[k-1]；

(2)根据簇中对象的均值，将每个对象指派给最相似的簇；

(3)更新簇均值，即计算每个簇中对象的均值；

(4)重复步骤(2)和步骤(3)，直到准则函数不再发生变化。

2 改进K-means算法描述

2.1 相关定义

定义1 数据对象 xi(xi1，xi2，…，xip)T、xj(xj1，xj2，… ，xjp)T之间的距离用欧氏距离d(xi，xj)表示如下：

定义2 二维数据样本点中心 center(xi，xj)：

2.2 改进算法的思想及基本步骤

影响K-means聚类算法性能的主要原因有：样本集中孤立点以及随机选择初始聚类中心而造成聚类结果的不稳定以及不准确。针对K-means的这种不足，本文提出了一种新的思想：首先将样本点中影响聚类结果的孤立点去除，然后利用坐标平移的思想来确定初始聚类中心，利用K-means算法进行聚类，最终得到可以满足平方误差准则函数收敛的聚类结果。

算法具体步骤：

首先排除样本点中的孤立点：

(1)输入样本点，利用unique函数排除样本点中重复的数据；

(2)计算每个样本点与其余样本点之间的距离存入矩阵cid中；

(3)指定孤立点的个数acnodenum，执行孤立点查找程序，即计算每个点与其余点的距离之和，找出距离最大的前acnodenum个点，即为孤立点；排除孤立点，将孤立点存入集合acnode中，并将这些点从原始数据集中删除得到新的数据集datanew，即为本文算法第一次去除孤立点之后的样本点集合。在第一次去除了孤立点之后，可以得到新的样本点集合datanew。

其次对datanew样本进行处理，从中找出k个初始聚类中心：

(4)求出样本点集合datanew中的两两之间的距离存入矩阵D中；

(5)从矩阵D中找出距离最大的两个点A和B，其最大距离记为maxinD，根据式(2)计算其中心 center和半径(r=maxinD/2)；

(6)第二次去除孤立点：求datanew中的每个样本点与center的距离，将大于r的样本点加入到集合acnode中并将其从datanew中去除得到第二次去除孤立点之后的样本点datanewsec；

(7)利用坐标平移的思想求解初始聚类中心：

①将步骤(5)中求出的A、B中的任一点加入初始聚类中心集合nc中作为第一个初始聚类中心；

②循环k-1次实现以center为参照点，将A坐标顺时针移动圆心角等于2×pi/k的度数；

利用T-text分析是否已经发表A类文章的研究生对于初级知识、中级知识、高级知识、初级技能、中级技能、高级技能、态度的差异情况，经过分析，是否已经发表A类文章的研究生在初级知识、中级知识、高级知识、初级技能、中级技能、高级技能、态度因素的P值均大于0.05，没有显著性差异。

③最终得到包含A在内的k个点，将这个k个点作为初始的聚类中心存入矩阵nc中；

(8)利用步骤(7)中求得的初始的聚类中心nc，用K-means算法进行聚类得出满足聚类准则函数收敛的聚类结果。

(9)计算acnode中的每个点与每个初始聚类中心的距离，将acnode中的点加入到距离初始聚类中心最近的簇中。

3 实验结果及分析

3.1 实验数据及实验环境

为了便于对比分析与计算，本实验采用的是二维数据，并且数据类型是数值型的。实验采用了两组测试数据：一组是随机数据，一组是UCI数据库中的标准数据集Iris数据集。实验工具采用MATLAB环境编程实现。

3.2 实验方案

3.2.1 采用随机数据

采用传统的随机选择初始聚类中心的K-means算法将本文的改进算法对随机产生的80个样本进行聚类，聚类的簇数设为k=4，比较其聚类结果图。

第 1 组 ： (0.660 2，0.207 1)、(0.342 0，0.607 2)、(0.289 7， 0.629 9)、(0.341 2，0.370 5)。

第 2 组 ： (0.767 6，0.274 6)、 (0.261 0，0.193 1)、(0.719 7，0.827 6)、(0.315 8，0.620 6)。

第 3 组 ： (0.580 8，0.104 6)、 (0.815 8，0.400 6)、(0.211 4，0.445 7)、(0.623 2，0.807 5)。

第 4 组 ： (0.568 1，0.846 9)、 (0.781 2，0.575 2)、(0.211 4，0.445 7)、(0.628 6，0.122 5)。

图1 针对随机数据的选取四种初始聚类中心的结果图

采用改进算法选出的初始聚类中心为(0.231 1，0.956 8)、 (0.999 6，0.795 7)、(0.8385，0.0272)和(0.0700，0.188 3)，其聚类结果如图2所示。

由图 1、图 2可以看出，利用本文改进算法选出的初始聚类中心进行聚类，其聚类结果比较接近数据分布。

图2 针对随机数据的改进算法聚类结果

3.2.2 采用Iris数据集

Iris数据集是UCI数据库中的一个标准数据集，包含有4个属性，150个数据对象，可分为3类。选用Iris数据集中间二维的数据进行聚类，分别用原算法和改进算法进行实验。对实验结果从运行时间以及准确度上进行分析，实验结果汇总以及分析如表1所示。

从表1可以看出，改进算法的运行时间比传统K-means算法的运行时间要小，尤其当数据集比较大时，其运行时间小得多。从图3中可以看出，采用改进算法其准确度明显提高。

本文提出的改进算法虽然在查找孤立点以及计算样本点之间的距离方面，会增加时间消耗，但是改进算法准确度较高，聚类效果较好。实验证明该算法是切实可行的，与传统的K-means算法相比较，有较好的聚类结果。

表1 K-means算法与本文改进算法准确率与运行时间比较

图3 两种算法的准确率以及运行时间的比较

[1]Han Jiawei，KAMBER M.Dataminingconceptsand techniques， second edition[M].Elsevier(Singapore)Pte Ltd，2006：251-263.

[2]张建辉.K-means聚类算法的研究与应用 [D].武汉：武汉理工大学，2007：10-14.

[3]冯超.K-means聚类算法的研究[D].大连：大连理工大学，2007：15-19.

[4]刘涛，尹红健.基于半监督学习的K-均值聚类算法的研究[J].计算机应用研究，2010，27(3)：913-917.

[5]李飞，薛彬，黄亚楼.初始中心优化的 K-Means聚类算法[J].计算机科学，2002，29(7)：94-96.

[6]Shi Na， Liu Xumin， Guan Yong.Research on k-means clustering algorithm[C].Third International Symposium on Intelligent Information Technology and Security Informatics，2010：63-67.