K-MEANS算法(K均值算法).doc

k-means算法
一．算法简介
k-means算法，也被称为k-平均或k-均值，是一种得到最广泛使用的聚类算法。 它是将各个聚类子集内的所有数据样本的均值作为该聚类的代表点，算法的主要思想是通过迭代过程把数据集划分为不同的类别，使得评价聚类性能的准如此函数达到最优，从而使生成的每个聚类内紧凑，类间独立。这一算法不适合处理离散型属性，但是对于连续型具有较好的聚类效果。
二．划分聚类方法对数据集进展聚类时包括如下三个要点：
〔1〕选定某种距离作为数据样本间的相似性度量
k-means聚类算法不适合处理离散型属性，对连续型属性比拟适合。因此在计算数据样本之间的距离时，可以根据实际需要选择欧式距离、曼哈顿距离或者明考斯距离中的一种来作为算法的相似性度量，其中最常用的是欧式距离。下面我给大家具体介绍一下欧式距离。
假设给定的数据集 ，X中的样本用d个描述属性A1,A2…Ad来表示，并且d个描述属性都是连续型属性。数据样本xi=(xi1,xi2,…xid), xj=(xj1,xj2,…xjd)其中，xi1,xi2,…xid和xj1,xj2,…xjd分别是样本xi和xj对应d个描述属性A1,A2,…Ad的具体取值。样本xi和xj之间的相似度通常用它们之间的距离d(xi,xj)来表示，距离越小，样本xi和xj越相似，差异度越小；距离越大，样本xi和xj越不相似，差异度越大。
欧式距离公式如下：
〔2〕选择评价聚类性能的准如此函数
k-means聚类算法使用误差平方和准如此函数来评价聚类性能。给定数据集X，其中只包含描述属性，不包含类别属性。假设X包含k个聚类子集X1,X2,…XK；各个聚类子集中的样本数量分别为n
1，n2,…,nk;各个聚类子集的均值代表点〔也称聚类中心〕分别为m1，m2,…,mk。
如此误差平方和准如此函数公式为：
〔3〕相似度的计算根据一个簇中对象的平均值来进展。
将所有对象随机分配到k个非空的簇中。
计算每个簇的平均值，并用该平均值代表相应的簇。
根据每个对象与各个簇中心的距离，分配给最近的簇。
然后转2〕，重新计算每个簇的平均值。这个过程不断重复直到满足某个准如此函数才停止。
三．算法描述
为中心向量c1, c2, …, ck初始化k个种子
分组:
将样本分配给距离其最近的中心向量
由样本构造不相交〔 non-overlapping 〕的聚类
确定中心:
用各个聚类的中心向量作为新的中心
重复分组和确定中心的步骤，直至算法收敛
四．算法流程
输入：簇的数目k和包含n个对象的数据库。
输出：k个簇，使平方误差准如此最小。
算法步骤：
，这样就有K 个初始聚类中心。

。
，得到K个聚类
O
X
Y
1
0
2
2
0
0
3

0
4
5
0
5
5
2
五．算法举例
数据对象集合S见表1，作为一个聚类分析的二维样本，要求的簇的数量k=2。
(1)选择 ， 为初始的簇中心，即