基于K - means聚类算法的研究

西南民族大学学报·自然科学版 第 35卷第 Jan. 2009

Journal of Southwest University for Nationalities?Natural Science Edition ___________________________________________________________________ 1期

文章编号 : 1003-2843(2009)01-0198-03

基于 K-means聚类算法的研究

步媛媛 1, 关忠仁 2

(1.成都信息工程学院计算机系,四川 成都 610225; 2.成都信息工程学院网络中心 610225) , 四

川 成都摘要:原始的 k-means算法 [4]是从 样本点的集合 中随机选取 K个中心 ,这种选取具有盲目性和随意性, 它在 很大程

度上

决定了算法的有 效性.为消除选取初始中心的盲目 性,应充分利用已有数据样本 点的信息 .采取对数据进行 预处理的方 式来 选取初始中心 .实验 证明新的初始 点的选 取不仅提高了算法的计 算效率 ,也提高了算法最终确定的聚 类的精度 . 关键词:数据挖掘 ;聚类; k-means算法 ; 聚类中心 中图分类号: TP392 文献标识码: A

1 引言

聚类分析是数据挖掘中 的一个重要功能 ,目前已应用于许多方面 :数据挖掘和知识发 现、模式 识别式 分

类、数据压缩和向 量量化 .关于聚类分析有很多种方法,这些方法包括分割与合并方法、随机化方法和神经 网络 方法.其中在欧氏 空间 中的k-means聚类算法是最流行和最受关注的一种聚类分析算法.

k-means是一种基于划分的聚类算法,它的思 想是当 一个类确定后,将类中数据点的几何 平均值取为类的

中心.其中初始聚类中心的选择对聚类结果的影响是很大的.如图所示 ,图 1是三个类的实际

布 ,图 2 是选取了

较好的初始聚类中心(+字标记的数据对 象是聚类中心)得到的结果,图 3是选取不大好的初始聚类中心的结 现是

结果会导致聚类算法效率低 ,算法迭代次数较多 , CPU运行时间 较长.因此怎样找到一组初始中心点, 获得

一个较好的聚类效果并提高聚类结果的精确度对 k-means算法具有重要意义 .

果.从中可以看到 ,图 2所示的类内部数据对 象相似度和类与类之间 的相异度均高 于图 3所示 , 最主要

数据分布 稠密.因此合理地选择初始聚类中心是很关键的.类似图 3所示之类的选取聚类中心的k-means 算法

图 1 三个类的实际分布 图 2 选取了较好中心的聚类结果 图 3 选取不好聚类中心的结果

本文提出了一种寻找初始聚类中心的方法,使得初始 聚类中心的分布尽可能体现数据的实际 分布 . 实验 表 明了这种算法的可行性和有效性 .

2 原始的 k-means聚类算法[4]及改进的算法分析

2.1 原始 k-means聚类算法

___________________________

收稿日期：2008-10-13

作者简介：步媛媛(1984-),女,成都信息工程学院计算机系在读 硕士研究生;关忠仕(1957-),男,成都信息工程学院网络中心高级

工程师,硕士生导师.

_第__1_期____________________步媛媛等:基于_____________________199__

man聚类算法

__________________的研__究

设待 聚类的数据集 : X=?x1,x2,L,xn?, k个聚类中心分别为 zi , i=1, 2, ....n.有如下定义 :

定义1:两个数据对象间的欧几里德距离为 | xd(i, i1????x j1 | ??| xi2????x j2 | ?L???| xip????x jp |

j)=

2 2 2 这里的i=( xi1,xi2,L,xip )和j=( x j1,x j2,L,x jp )是两个 p维的数据对象. 定义2:准则函数E

E=

k

????????| p???m

i?1 p??C I

i

|

2

这里的E是数据库中所有对象的平方 误差的总和, p是空 间中的点 ,表示给定的数据对象 , mi是簇 Ci的平均值

这个准则试图使生成的结果 簇尽可能 地紧凑和独立 .

算法 主要有三个过程组成 :首先是选取 初始的聚类中心 ;其次是样本 点分类;最后是聚类中心的调整 其

中后两个过程迭代交替进行 .下面是 k-means算法 的流程描述 : 输入簇的数目k和包含n个对象的数据库. 输出 :: k个簇 ,使平方误差准则最小. 方

法 任意选择 : Step1 k个对象作为初始的簇 Step2 中心; Step3 repeat 根据簇中对象的平均值,将每个对象重新赋给最类似的Step4 簇 ;

Step5 更新簇的平均值,即计算每 个簇中对象的平均值;

until 不再发生变化 对初始聚类中心的选择 是随意 的和盲目的,这种选取 方法很大程度上决定了算法 的有 原始的 k-means算法

效性和精确度.因此对初始中心的选择 进行改进既很有意义也很有必要.本文的主要目的就是在 欧几里德距离

的意义下,确定相隔最远的两个数据点之间的距离 ,然后将数据集均分为 k个段 ,在每段内取中心作为 初始 的中心.也就是改进上述 算法2.2改进的 k-means聚类算法 中的step1.

定义1:数据集中相隔最远的两个数据点之间的距离 M M=max{d(i, j)} 定义2: d=M/k

定义3:假设一参 照点为 o,数据集中与点 o之间的距离最大的点记为数据集中的大者 mi , i=1, 2, …, (k-1). 两个数据对象间的距离 d( xi,x j ),比较得出 M. 计算任意Step1

Step2 计算 d;

Step3 X 1???X ;求出点 m1;

C1={ X 1中与点 m1的距离小于d的点 1 Um };

Step4 X 2 =X-C1;求出点

m ; C2 2 ={ X 2中与点 m2的距离小于d的点 2 Um };

……

Step5

X k??1 =X-Ck??2 ;求出点 ; m??1 Ckk??1 ={ X k??1中与点 mk??1的距离小于点 d的点 Umk??1 };

Step7

U U 计算中心 zi?? = ?L C

|C1I |

j

I

k??1

x j , i=1, 2, …, k.

Step6 C K k=X-(C1UC2 ); Step8 从这个聚类中心出发,应用k-means聚类算法 的步 Step2, Step3, Step4, Step5,得到聚类. x ??C2.3两种算法的比较分析 2.3.1简单例子证明

为了说明改进的k-means聚类算法 与原始的 k-means聚类算法 的不同,举一简单 例子进行分析比较.

_2_0_0_____________________西__南_民_族__大_学__学_报_·_自__然_科__学_版__________

例设有 一数据样本集合为 X={1, 5, 10, 9, 26, 32, 16, 21, 14},将X聚为 3类,即k=3.分别用两种算法来 执行 . (1) 原始的 k-means聚类算法如表 1所示 : 表 1原始的 k-means聚类算法

步 1 2 3 4 5

z1

1 1 1 1 3

z2

5 5 8 9.5 12.3

z3

10 18.3 21.8 23.8 26.3

C1

{1} {1} {1} {1, 5} {1, 5}

C2

{5} {5, 10, 9} {5, 10, 9, 14} {10, 9, 14, 16} {10, 9, 14, 16}

C3

{10, 9, 26, 32, 16, 21, 14} {26, 32, 16, 21, 14} {26, 32, …… 此处隐藏：3905字，全部文档内容请下载后查看。喜欢就下载吧 ……