K-MEANS(K均值聚类算法,C均值算法).pptx

2.13.2 The k-Means Algorithm (K-均值聚类算法）;主讲内容;算法简介;算法描述 为中心向量c1, c2, …, ck初始化k个种子 分组: 将样本分配给距离其最近的中心向量 由这些样本构造不相交（ non-overlapping ）的聚类 确定中心: 用各个聚类的中心向量作为新的中心 重复分组和确定中心的步骤，直至算法收敛;算法 k-means算法 输入：簇的数目k和包含n个对象的数据库。 输出：k个簇，使平方误差准则最小。 算法步骤： 1.为每个聚类确定一个初始聚类中心，这样就有K 个初始聚类中心。 2.将样本集中的样本按照最小距离原则分配到最邻近聚类 3.使用每个聚类中的样本均值作为新的聚类中心。 4.重复步骤2.3直到聚类中心不再变化。 5.结束，得到K个聚类 ;2011-4-14;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-Means算法对于不同的初始值，可能会导致不同结果。解决方法： 1.多设置一些不同的初值，对比最后的运算结果）一直到结果趋于稳定结束，比较耗时和浪费资源 2.很多时候，事先并不知道给定的数据集应该分成多少个类别才最合适。这也是 K-means 算法的一个不足。有的算法是通过类的自动合并和分裂，得到较为合理的类型数目 K，例如 ISODATA 算法。 3. 所谓的gapstatistics（ Gap统计模型） ;ISODATA算法;与K-means相比在下列几方面有改进： 1.考虑了类别的合并与分裂，因而有了自我调整类别数的能力。合并主要发生在某一类内样本个数太少的情况，或两类聚类中心之间距离太小的情况。为此设有最小类内样本数限制 ，以及类间中心距离参数 。若出现两类聚类中心距离小于 的情况，可考虑将此两类合并。　　分裂则主要发生在某一类别的某分量出现类内方差过大的现象，因而宜分裂成两个类别，以维持合理的类内方差。给出一个对类内分量方差的限制参数 ，用以决定是否需要将某一类分裂成两类。　　2.由于算法有自我调整的能力，因而需要设置若干个控制用参数，如聚类数期望值K、每次迭代允许合并的最大聚类对数L、及允许迭代次数I等。;基本步骤和思路 （1） 选择某些初始值。可选不同的参数指标，也可在迭代过程中人为修改，以将N个模式样本按指标分配到各个聚类中心