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

算法简介?k-means算法,也被称为k-平均或k-均值,是一种得到最广泛使用的聚类算法。它是将各个聚类子集内的所有数据样本的均值作为该聚类的代表点,算法的主要思想是通过迭代过程把数据集划分为不同的类别,使得评价聚类性能的准则函数达到最优,从而使生成的每个聚类内紧凑,类间独立。这一算法不适合处理离散型属性,但是对于连续型具有较好的聚类效果。1?,c2,…,:?将样本分配给距离其最近的中心向量?由这些样本构造不相交(non-overlapping):?,直至算法收敛2算法k-means算法输入:簇的数目k和包含n个对象的数据库。输出:k个簇,使平方误差准则最小。算法步骤:,这样就有K个初始聚类中心。。。,得到K个聚类32020/3/31将样本分配给距离它们最近的中心向量,并使目标函数值减小21},...,2,1{||||minjniikjpx???????iCxiixCx1更新簇平均值21??????kiCxiixxE计算准则函数E4K-means聚类算法5划分聚类方法对数据集进行聚类时包括如下三个要点:?(1)选定某种距离作为数据样本间的相似性度量上面讲到,k-means聚类算法不适合处理离散型属性,对连续型属性比较适合。因此在计算数据样本之间的距离时,可以根据实际需要选择欧式距离、曼哈顿距离或者明考斯距离中的一种来作为算法的相似性度量,其中最常用的是欧式距离。下面我给大家具体介绍一下欧式距离。6假设给定的数据集,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越不相似,差异度越大。欧式距离公式如下:????????dkjkikjixxxxd12,??totalmxXm,...,2,1|??7?(2)选择评价聚类性能的准则函数k-means聚类算法使用误差平方和准则函数来评价聚类性能。给定数据集X,其中只包含描述属性,不包含类别属性。假设X包含k个聚类子集X1,X2,…XK;各个聚类子集中的样本数量分别为n1,n2,…,nk;各个聚类子集的均值代表点(也称聚类中心)分别为m1,m2,…,mk。则误差平方和准则函数公式为:21??????kiXpiimpE8?(3)相似度的计算根据一个簇中对象的平均值来进行。?(1)将所有对象随机分配到k个非空的簇中。?(2)计算每个簇的平均值,并用该平均值代表相应的簇。?(3)根据每个对象与各个簇中心的距离,分配给最近的簇。?(4)然后转(2),重新计算每个簇的平均值。这个过程不断重复直到满足某个准则函数才停止。,作为一个聚类分析的二维样本,要求的簇的数量k=2。(1)选择,为初始的簇中心,即,。(2)对剩余的每个对象,根据其与各个簇中心的距离,将它赋给最近的簇。对:显然,故将分配给??2,01O??0,02O??2,011??OM??0,022??OM??????,2231?????OMd??????,2232?????OMd????3132,,OMdOMd?3O3O2C例子10