K均值聚类算法-C均值算法ppt课件.ppt

算法简介算法描述
为中心向量c1,c2,…,ck初始化k个种子
分组:
将样本分配给距离其最近的中心向量
由这些样本构造不相交（non-overlapping）的聚类
确定中心:
用各个聚类的中心向量作为新的中心
重复分组和确定中心的步骤，直至算法收敛算法k-means算法
输入：簇的数目k和包含n个对象的数据库。
输出：k个簇，使平方误差准则最小。
算法步骤：
1.为每个聚类确定一个初始聚类中心，这样就有K个初始聚类中心。
2.将样本集中的样本按照最小距离原则分配到最邻近聚类
3.使用每个聚类中的样本均值作为新的聚类中心。
4.重复步骤2.3直到聚类中心不再变化。
5.结束，得到K个聚类
将样本分配给距离它们最近的中心向量，并使目标函数值减小
K-means聚类算法划分聚类方法对数据集进行聚类时包括如下
三个要点：
（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；各个聚类子集中的样本数量分别为n1，n2,…,nk;各个聚类子集的均值代表点（也称聚类中心）分别为m1，m2,…,mk。则误差平方和准则函数公式为：

（3）相似度的计算根据一个簇中对象的平均值来进行。
（1）将所有对象随机分配到k个非空的簇中。
（2）计算每个簇的平均值，并用该平均值代表相应的簇。
（3）根据每个对象与各个簇中心的距离，分配给最近的簇。
（4）然后转（2），重新计算每个簇的平均值。这个过程不断重复直到满足某个准则函数才停止。O对于：

因为所以将分配给
对于：

因为所以将分配给
更新，得到新簇和
计算平方误差准则，单个方差为
k-means算法的性能分析k-Prototype算法：可以对离散与数值属性两种混合的数据进行聚类，在k-prototype中定义了一个对数值与离散属性都计算的相异性度量标准。

K-Prototype算法是结合K-Means与K-modes算法，针对混合属性的，解决2个核心问题如下：
1.度量具有混合属性的方法是，数值属性采用K-means方法得到P1，分类属性采用K-modes方法P2，那么D=P1+a*P2，a是权重，如果觉得分类属性重要，则增加a，否则减少a，a=0时即只有数值属性
2.更新一个簇的中心的方法，方法是结合K-Means与K-modes的更新方法。k-中心点算法：k-means算法对于孤立点是敏感的。为了解决这个问题，不采用簇中的平均值作为参照点，可以选用簇中位置最中心的对象，即中心点作为参照点。这样划分方法仍然是基于最小化所有对象与其参照点之间的相异度之和的原则来执行的。K-means算法在图像分割上的简单应用在图像分割上的简单应用在图像分割上的简单应用1920