k-平均算法及程序说明
需积分: 9 176 浏览量
2009-11-18
11:17:06
上传
评论
收藏 46KB DOC 举报
K-MEANS 算法实现介绍
1 ．算法说明流程
输入：聚类个数 k，以及包含 c 个数据对象的数据库。
输出：满足方差最小标准的 k 个聚类。
处理流程：
（1） 从 c 个数据对象任意选择 k 个对象作为初始聚类中心；
（2） 循环（3）到（4）直到每个聚类不再发生变化为止
（3） 根据每个聚类对象的均值（中心对象），计算每个对象与这些中心对象
的距离；并根据最小距离重新对相应对象进行划分；
（4） 重新计算每个（有变化）聚类的均值（中心对象）
k-means 算法接受输入量 k ；然后将 c 个数据对象划分为 k 个聚类以便使
得所获得的聚类满足：同一聚类中的对象相似度较高；而不同聚类中的对象相
似度较小。聚类相似度是利用各聚类中对象的均值所获得一个“中心对象”来进
行计算的。
k-means 算法的工作过程说明如下：首先从 c 个数据对象任意选择 k 个对
象作为初始聚类中心；而对于所剩下其它对象，则根据它们与这些聚类中心的
相似度（距离），分别将它们分配给与其最相似的（聚类中心所代表的）聚类；
然后再计算每个所获新聚类的聚类中心（该聚类中所有对象的均值）；不断重
复这一过程直到标准测度函数开始收敛为止。一般都采用均方差作为标准测度
函数. k 个聚类具有以下特点：各聚类本身尽可能的紧凑，而各聚类之间尽可能
的分开。
2 ．标准测度函数
聚类法的目的是希望尽量减小每一点与类（簇）中心的距离平方差（square
error）。 一般都采用均方差作为标准测度函数。
假设我们现在有一组包含 c 个点的数据，其中第 k 个类（簇）可以用集合
G
k
来表示，假设 G
k
包含 n
k
个数据点{x
1
, x
2
, …, x
nk
}，此类的中心（均值）为
y
k
，则该类的平方差 e
k
可以定义为：
e
k
=
i
|x
i
-y
k
|
2
，其中 x
i
是属于第 k 类的数据点。
而这 c 个类的总的平方差的和 E 便是每个类（簇）的平方差总和：
资源评论
