基于K means聚类算法的研究.doc

基于K_means聚类算法的研究.doc: .
第35卷第1期
文章编号 “003-2843(2009)01-0198-03
基于K-means聚类算法的研究
步媛媛关忠仁2
(，四川成都 610225; ，四6W0纳)
摘要:原始的 k-means算法 ⑷是从样本点的集合中随机选取K个中心，这种选取具有盲目性和随意性，它在很大程度上
,应充分利用已有数据样本点的信息 .采取对数据进行预处理的方
，也提高了算法最终确定的聚类的精度 .
关键词:数据挖掘；聚类；k-means算法；聚类中心
中图分类号:TP392 文献标识码：A
1引言
聚类分析是数据挖掘中的一个重要功能，目前已应用于许多方面 ：数据挖掘和知识发现、模式识别和模式
类、数据压缩和向量量化 .关于聚类分析有很多种方法，这些方法包括分割与合并方法、随机化方法和神经网络
-means聚类算法是最流行和最受关注的一种聚类分析算法.
k-means是一种基于划分的聚类算法，它的思 想是当一个类确定后，将类中数据点的几何平均值取为类的
，图1是三个类的实际分布，图2
取了
较好的初始聚类中心(+字标记的数据对象是聚类中心)得到的结果，图 3是选取不大好的初始聚类中心得到的结
，图 2所示的类内部数据对象相似度和类与类之间的相异度均高于图3所示，最主要的体现是
3所示之类的选取聚类中心的k-means算法的
结果会导致聚类算法效率低 ，算法迭代次数较多 ，，从而获得
本文提出了一种寻找初始聚类中心的方法，使得初始聚类中心的分布尽可能体现数据的实际分布•实验表 明了这种算法的可行性和有效性
2原始的 k-means聚类算法⑷及改进的算法分析
-means聚类算法
收稿日期：2008-10-13
作者简介：步媛媛(1984-),女，成都信息工程学院计算机系在读硕士研究生;关忠仕(1957-),男，成都信息工程学院网络中心高级 工程师，硕士生导师.
_第 [—期 步媛媛等:基于K-means聚类算法 的研 究
199
设待聚类的数据集：X二—,X2,^Xn , k个聚类中心分别为Zi,i=1,2, „.. ：
定义1：两个数据对象间的欧几里德距离为 d I Xi2： x J2 I—L 而 Xjp
这里的i=(xn,Xi2,L,Xip )和j=(xr,Xj2,L,x jp)是謝个p维的数据对象.
定义2:准则函数E 2 2 2
V | p[ rrii |2
i 1 pDQ
这里的E是数据库中所有对象的平方误差的总和，p是空间中的点，表示给定的数据对象，m是簇 G的平均值.
这个准则试图使生成的结果簇尽可能地紧凑和独立.
算法主要有三个