最新K-MEANS(K均值聚类算法-C均值算法)教学讲义PPT课件.ppt

《最新K-MEANS(K均值聚类算法-C均值算法)教学讲义PPT课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、K-MEANS(K均值聚类算法-C均值算法)主讲内容算法性能分析算法改进算法简介算法应用算法要点算法描述算法实例ISODATA算法gapstatistics算法简介k-means算法，也被称为k-平均或k-均值，是一种得到最广泛使用的聚类算法。它是将各个聚类子集内的所有数据样本的均值作为该聚类的代表点，算法的主要思想是通过迭代过程把数据集划分为不同的类别，使得评价聚类性能的准则函数达到最优，从而使生成的每个聚类内紧凑，类间独立。这一算法不适合处理离散型属性，但是对于连续型具有较好的聚类效果。K-means聚类算法划分聚类

2、方法对数据集进行聚类时包括如下三个要点：（1）选定某种距离作为数据样本间的相似性度量上面讲到，k-means聚类算法不适合处理离散型属性，对连续型属性比较适合。因此在计算数据样本之间的距离时，可以根据实际需要选择欧式距离、曼哈顿距离或者明考斯距离中的一种来作为算法的相似性度量，其中最常用的是欧式距离。下面我给大家具体介绍一下欧式距离。假设给定的数据集，X中的样本用d个描述属性A1,A2…Ad来表示，并且d个描述属性都是连续型属性。数据样本xi=(xi1,xi2,…xid),xj=(xj1,xj2,…xjd)其中，xi1,

3、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;各个

4、聚类子集的均值代表点（也称聚类中心）分别为m1，m2,…,mk。则误差平方和准则函数公式为：（3）相似度的计算根据一个簇中对象的平均值来进行。（1）将所有对象随机分配到k个非空的簇中。（2）计算每个簇的平均值，并用该平均值代表相应的簇。（3）根据每个对象与各个簇中心的距离，分配给最近的簇。（4）然后转（2），重新计算每个簇的平均值。这个过程不断重复直到满足某个准则函数才停止。Oxy10220031.50450552数据对象集合S见表1，作为一个聚类分析的二维样本，要求的簇的数量k=2。(1)选择，为初始的簇中心，即，。(

5、2)对剩余的每个对象，根据其与各个簇中心的距离，将它赋给最近的簇。对：显然，故将分配给例子对于：因为所以将分配给对于：因为所以将分配给更新，得到新簇和计算平方误差准则，单个方差为Oxy10220031.50450552，。总体平均方差是：（3）计算新的簇的中心。重复（2）和（3），得到O1分配给C1；O2分配给C2，O3分配给C2，O4分配给C2，O5分配给C1。更新，得到新簇和。中心为，。单个方差分别为总体平均误差是：由上可以看出，第一次迭代后，总体平均误差值52.25~25.65，显著减小。由于在两次迭代中，簇中心不

6、变，所以停止迭代过程，算法停止。Oxy10220031.50450552k-means算法的性能分析主要优点：是解决聚类问题的一种经典算法，简单、快速。对处理大数据集，该算法是相对可伸缩和高效率的。因为它的复杂度是0(nkt),其中,n是所有对象的数目,k是簇的数目,t是迭代的次数。通常k<

7、果。K-Means算法对于不同的初始值，可能会导致不同结果。解决方法：1.多设置一些不同的初值，对比最后的运算结果）一直到结果趋于稳定结束，比较耗时和浪费资源2.很多时候，事先并不知道给定的数据集应该分成多少个类别才最合适。这也是K-means算法的一个不足。有的算法是通过类的自动合并和分裂，得到较为合理的类型数目K，例如ISODATA算法。3.所谓的gapstatistics（Gap统计模型）它对于“躁声”和孤立点数据是敏感的，少量的该类数据能够对平均值产生极大的影响。ISODATA算法与K-均值算法的比较K-均值算法

8、通常适合于分类数目已知的聚类，而ISODATA算法则更加灵活；从算法角度看，ISODATA算法与K-均值算法相似，聚类中心都是通过样本均值的迭代运算来决定的；ISODATA算法加入了一些试探步骤，并且可以结合成人机交互的结构，使其能利用中间结果所取得的经验更好地进行分类。主要是在选代过程中可将一类一分为二，亦可能二类