一种优化初始聚类中心的K_means聚类算法

一种优化初始聚类中心的K-means 聚类算法*

周爱武，崔丹丹，潘勇

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

要：针对K-means 算法中的初始聚类中心是随机选择这一缺点进行改进，利用提出的新算

法选出初始聚类中心，并进行聚类。这种算法比随机选择初始聚类中心的算法性能有所提高，具有更高的准确性。

关键词：欧氏距离；K-means ；优化初始中心

中图分类号：TP301.6

文献标识码：A

文章编号：1674-7720(2011)13-0001-03

摘

An optimization initial clustering center of K-means clustering algorithm

Zhou Aiwu ，Cui Dandan ，Pan Yong

(Collegeof Computer Science and Technology ，Anhui University ，Hefei 230039，China)

Abstract ：This article is an improvement aiming at the defect that the initial algorithm center of K-means is a random choice. Using this improved algorithm to select new clustering center to do clustering. After analysis ，this new algorithm improves performance and accuracy better than the algorithm that random selection of initial clustering center.

Key words ：Euclidean distance ；K-means ；optimization initial clustering center 数据挖掘技术研究不断深入与发展，作为数据挖掘技术中的聚类分析，也越来越被人们关注与研究。聚类分析是数据挖掘中一个非常活跃的研究领域，并且具有广泛的应用。聚类就是将数据集划分成若干簇或者类的一个过程[1]。经过聚类之后，使得同一簇中的数据对象相似度最大，而不同簇之间的相似度最小。

聚类是一种无监督的学习算法，即把数据对象聚成不同的类簇，从而使不同类之间的数据相似度低，而同一个类中的相似度高，并且将要划分的类是之前不知道的，其形成由数据驱动。聚类算法[1]分成基于划分的、密度的、分层的、网格的、模型的。其中基于划分的聚类算法中的K -均值算法(K-means 算法) 是最常用的一种聚类算法，同时也是应用最广泛的一种算法。K -means 聚类算法主要针对处理大数据集时[2]，处理快速简单，并且算法具有高效性和可伸缩性。但是K -means 算法也有一定的局限性[3]，如K 值必须事先给定，只能处理数值型数据，初始聚类的中心是随机选择的，而其聚类结果的好坏直接取决于初始聚类中心的选择。并且由于初始聚类中心随机选择，容易造成算法陷入局部最

*基金项目：安徽省教育厅重点项目(KJ2009A57)

优解。因此初始聚类中心的选择十分重要。

本文针对随机选择初始聚类中心的缺点，提出了一种新的改进的K-means 聚类算法。该算法产生的初始聚类中心不是随机的，能够很好地体现数据的分布情况，使得初始中心尽可能地趋向于比较密集的范围内，从而进行更好的聚类，最终消除了传统K-means 算法中由于初始聚类中心选择是随机的而产生的缺点。最后实验证明了这种算法的有效性与可行性。

1传统K-means 算法

1.1传统K-means 算法的思想

传统的K-means 算法的工作流程[1，4]：首先从n 个数据对象任意选择k 个对象作为初始聚类中心；而对于

所剩下其他对象，则根据它们与这些聚类中心的相似度

(距离) ，分别将它们分配给与其最相似的(聚类中心所代表的) 聚类；然后再计算每个所获新聚类的聚类中心(该聚类中所有对象的均值) 。不断重复这一过程直到标准

测度函数开始收敛为止。一般都采用均方差作为标准测度函数。其准则函数定义如下：E =Σi =1Σp ∈C |i 2。其

i

K

中，E 为数据集中的对象与该对象所在簇中心的平方误

与z 1之间的距离，与Meandist 进行判断。如果小于

差的综合，E 越大说明对象与聚类中心的距离越大，簇内的相似性越低，反之则说明相似性越高；p 是簇内的一个对象，C i 表示第i 个簇，i 是簇C i 的中心，k 是簇的个数。

传统的K-means 算法具体描述如下[5]：输入：k ，data[n ]；输出：K 个簇的集合。

Meandist ，则将此样本点加入A 中，再求第三距离小的样

本点，重复步骤(3)；如果大于Meandist ，则求出此中心存入Center 。

(4)Until集合Center 中的个数等于k ，初始聚类中心

全部找到。

(5)用找到的初始聚类中心进行K-means 聚类。

算法举例：

如图1所示，假设有20个点数据集，并且已经将孤立点排除，需要将其聚成k =3类。首先计算两两之间的距离，利用定义2求出Meandist ，并找出最小的距离(如图中的x1、x2) ；然后求出其中心，用红色表示；找出距离次小的距离(如图中的x3、x4) ，计算出x3、x4的中心，并加一步判断。如果这个中心与前面求出的一个聚类中心之间的距离小于Meandist ，那么就排除这个聚类中心，接着执行找第三小的距离，并求其中心，直到找到K 个初始聚类中心为止；反之，则求下一个初始聚类中心，直到找到k 个初始聚类中心为止。

1.00.90.80.70.60.50.40.30.20.100

x 19

x 4x 20x 3

x 2

x 11

x 12x 1

x 18

x 15

x 5

x 6x 13

x 9

x 16

x 17

x 7

x 8x 10

x 14

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

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

的簇。

(3)更新簇均值，即计算每个簇中对象的均值。(4)重复步骤(2)、(3)，直到不再发生变化。1.2传统K-means 算法的局限性

传统的K -means 算法中对于K 个中心点的选取是随机的[3]，而初始点选取的不同会导致不同的聚类结果。为了减少这种随机选取初始聚类中心而导致的聚类结果的不稳定性，本文提出了一种关于初始聚类中心选取的方法，用来改变这种不稳定性。

2优化初始聚类中心的改进K-means 算法

2.1基本定义

设需要聚类的数据集：X ={x i |xi ∈R P ，i =1，2，…，n ) ，

k 个聚类中心分别用z 1，z 2，z 3，…z k 表示。有如下定义：

定义1

2个p 维向量x i =(x i 1，x i 2，…，x ip ) T 和x j =(x j 1，

x j 2，…，x jp ) T 数据对象间的距离用欧氏距离[6]表示：

d (x i -x j )=|x j -x i |=

定义2

二维数据样本点中心center(x i ，x j ) [6]：

姨

Σ|x

k =1

ik

-x jk |2

x +xx +x

center(x i ，x j )=(i 1j 1，i 2j 2)

22

定义3

样本点之间的平均距离Meandist ：

0.10.20.30.40.50.60.70.80.91.0

图1改进算法聚类举例

Meandist=

Σd (x

c

2n

i ，j

x )

3实验分析

为了便于分析与计算，本文采用的是二维数据，并且数据类型是实型的，实验环境为MATLAB 。为了进行对比，分别采用了传统的K -means 算法与本文改进的

即所有样本点的两两之间的距离之和除以样本点n 的组合数。

K-means 算法进行比较。

本文实验采用了两组实验进行验证，一组是随机数据，一组是标准数据库集。

2.2改进算法流程

本算法的改进建立在没有离群点的数据集上，针对没有离群点的数据进行分析。

输入：样本点，初值k 。

输出：k 个簇的聚类结果，使平方误差准则最小。步骤：

(1)采用随机数据

本文用随机产生的80个样本分别采用传统的K -

means 算法进行聚类与本文的改进算法进行聚类，比较

其聚类结果图。

传统算法采用随机选取初始聚类中心有(0.9501，

(1)求出两两样本点之间的距离存入矩阵D 中。

(2)初始化集合A 以及中心点集合Center ，最小距离的样本点放入集合A 中，并求出其中心最为第一个初

始的聚类中心z 1。

0.7948) 、(0.2311，0.9568) 、(0.6068，0.5226) ，其聚类结果如图2所示。

采用改进算法的初始聚类中心有(0.3399、0.0284) ，

(3)求出次小距离的样本点的中心，然后求出此中心(0.2007，0.5914) 、(0.7248，0.3819) ，其聚类结果如图3所示。

图2针对随机数据的传统的K-means

聚类结果

图4Iris 数据集传统K-means

算法聚类结果

图3

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

图5Iris 数据集改进算法聚类结果

(2)采用标准数据集：Iris 数据集

本文采用了Iris 数据集，它是UCI 数据库中的一个标准数据集。Iris 数据集包含有4个属性，150个数据对象，可分为三类。选用Iris 数据集前二维的数据进行聚类。分别用传统算法和改进算法进行聚类，其中分别用实心点、圈实心点以及五角星表示这三类。

传统算法采用随机选取初始聚类中心有(0.9501，

表1两种算法不同数据集的执行时间比较

数据集随机数据

算法

执行时间/s

K-means 改进算法

1.4840.5167.4232.168

Iris K-means 改进算法

法，但是由于其初始中心的选择是随机的，从而影响了聚类结果，使得聚类结果不稳定。本文主要是针对传统

0.5828) ，(0.2311，0.4235) 、(0.6068，0.5155) ，其聚类

结果如图4所示。

采用改进算法的初始聚类中心有(0.0099，0.0150) 、

K-means 算法的这一缺点，提出了一种新的改进算法，

即基于平均距离的思想，进行初始聚类中心的选择。实验证明，该算法是切实可行的，与传统的K -means 算法比较，有较好的聚类结果以及较短的运行时间。但本文算法是基于先将噪声点排除掉之后应用此改进算法进行聚类、且是在点的分布比较均匀的前提下应用，才有良好的效果。如果对于具有噪声点的数据集有一定的局限性、而且是比较密集的点的情况下，这将在以后的学习研究中进行探讨

。

(下转第9页)

(0.2942，0.6392) 、(0.6512，0.1905) ，其聚类结果如图5

所示。

对比这两幅图的聚类结果可以看出，采用改进算法产生聚类结果比较稳定准确。

运用K -means 算法和本文改进算法针对随机数据和Iris 数据分别实验得出的时间如表1所示。

K-means 算法是应用最为广泛的一种基于划分的算

学生学号、学生姓名。

Software Technology

用UML 对选课这一特定需求的应用进行了建模，给出了软件开发各阶段的模型，使软件系统的开发更加高效。从选课系统数据库的概念结构(E-R图) 、逻辑结构

编号、课程名称、教师编号、教师姓名、面向专业编号、

3开发和运行环境设计[4]

(1)开发平台搭建：由于开发的是服务器端的程序，

计算机安装的网络操作系统采用微软公司的Windows

(表结构) 及物理实现(表、视图及其连接) 进行了详细阐

述。随着高校教学的不断改革，会出现新的教学模式，因此，更先进的选课系统也会随之开发出来。参考文献

[1]张龙详.UML 与系统分析设计[M].北京：人民邮电出版

社，2001.

server2003，配置IIS6.0，并安装.NET Framework 为ASP. NET 应用程序提供运行平台。开发环境采用微软开发的Visual Studio.NET 2005，数据库管理系统采用SQL server 2005。

(2)运行环境：该系统运行的硬件环境主要有Web 服务器、数据库服务器、客户机；软件环境有在Web 服

务器上安装的Windows Server 2003网络操作系统及其

[2]BLAHA M ，RUMBAUGH J. UML 面向对象建模与设

计[M].车皓阳，杨眉译. 北京：人民邮电出版社，2007.

[3]赵杰，李涛，朱慧.SQLServer 数据库管理、设计与实现

[M].北京：清华大学出版社，2004.

[4]白兆庆. 基于B/S模式的选课系统的设计与实现[D].青

岛：中国海洋大学，2009.

Internet 信息服务组；数据库服务器上安装SQL Server2005数据库；Web 客户端安装Windows 2000、Windows XP 、Vista 、Windows 7等Windows 系列的操作系统；客户端浏览器安装Internet Explore 、遨游等浏览器并

能上互联网。

本文详细介绍了在UML 建模语言为指导下的一种基于.NET 框架的网上选课系统的分析、设计的全过程。

(收稿日期：2011-01-07)

作者简介：

李玲选，男，1975年生，讲师，主要研究方向：网络工程。

(上接第3页) 参考文献

[1]HAN J ，KAMBER M. 数据挖掘概念与技术[M].范明，盂小

峰，等译. 北京：机械工业出版社，2006.

[6]袁方，周志勇，宋鑫. 初始聚类中心优化的k-means 算法[J].计

算机工程，2007，33(3)：65-66.

(收稿日期：2011-03-13)

作者简介：

周爱武，女，1965年生，副教授，主要研究方向：数据库与Web 技术、数据仓库与数据挖掘、信息系统安全。

崔丹丹，女，1986年生，硕士生，主要研究方向：数据库与Web 技术、数据挖掘。

潘勇，男，1985年生，硕士生，主要研究方向：数据库与

[2]孟海东，张玉英，宋飞燕. 一种基于加权欧氏距离聚类方法的

研究[J].计算机应用，2006，26(22)：152-153.

[3]包颖. 基于划分的聚类算法研究与应用[D].大连：大连理工大

学，2008：18-20.

[4]李业丽，秦臻. 一种改进的K-means 算法[J].北京印刷学院学

报，2007，15(2)：63-65.

[5]张玉芳，毛嘉莉，熊忠阳. 一种改进的K-means 算法[J].计算机

应用，2003，23(8)：31-33.

Web 技术、数据挖掘。

(上接第6页)

虚拟实验是开展网络教学的一个瓶颈，而其中最关键的是没能较好地解决交互性的问题。利用VRML 技术，结合支持VRML 的开发工具构建一个虚拟实验环境，并利用Java 提供的支持VRML 的开发包，实现了用户与虚拟环境之间的交互，可以满足数码摄影虚拟实验教学的需要。实验常常是一种协作性的活动，合作是实验过程中一个至关重要的环节，因此，要充分利用现代网络技术，增强对虚拟实验的协同操作，进一步体现网上实验的优势[4]。参考文献

[1]田茵. 基于虚拟现实的三维产品展示[J].计算机教育，

2009(6).

[2]张枝军. 电子商务网站中商品三维虚拟展示技术研究[J].

商场现代化，2008(11).

[3]孙永丽. 三维虚拟仿真数码单反相机的设计与实现[J].

软件导刊，2010(8).

[4]张民. 远程虚拟实验平台及LabVIEW 实验研究[D].太

原：太原理工大学，2010.

(收稿日期：2011-03-03)

作者简介：

孙永丽，女，1979年生，讲师，硕士研究生，主要研究方向：数字化教学资源的设计与开发。