商务智能理论与应用6-k-means算法ppt课件

1、聚类分析K-means算法李广明2022/7/101.聚类分析概念聚类与分类的不同在于：分类作为一种监视学习方法，要求必需事先明确知道各个类别的信息，并且断言一切待分类项都有一个类别与之对应。但是很多时候上述条件得不到满足，尤其是在处置海量数据的时候，假设经过预处置使得数据满足分类算法的要求，那么代价非常大，这时候可以思索运用聚类算法。聚类属于无监视学习，相比于分类，聚类不依赖预定义的类和类标号的训练实例。 聚类分析指将物理或笼统对象的集合分组成为由类似的对象组成的多个类的分析过程。2022/7/102.聚类算法可以用来完成对l维特征向量的分组。对应于一样地面类型的点，如水，将其聚类在一同构成

2、一组。一旦这样分组以后，分析人员就可以经过每一组中的样本点和地面数据的参考信息相联络来识别地面类型。2022/7/103.聚类分析中的数据类型2022/7/104.相异度计算2022/7/105.区间标度变量2022/7/106.对象间的类似度和相异度对象间的类似度和相异度是基于两个对象间的间隔来计算的。标量也就是无方向意义的数字，也叫标度变量。如今先思索元素的一切特征属性都是标量的情况。例如，计算X=2,1,102和Y=1,3,2的相异度。一种很自然的想法是用两者的欧几里得间隔来作为相异度，欧几里得间隔的定义如下：其意义就是两个元素在欧氏空间中的集合间隔，由于其直观易懂且可解释性强，被广泛用

3、于标识两个标量元素的相异度。将上面两个例如数据代入公式，可得两者的欧氏间隔为： 除欧氏间隔外，常用作度量标量相异度的还有曼哈顿间隔和闵可夫斯基间隔，两者定义如下： 曼哈顿间隔： 闵可夫斯基间隔： 2022/7/107.规格化问题上面这样计算相异度的方式有一点问题，就是取值范围大的属性对间隔的影响高于取值范围小的属性。例如上述例子中第三个属性的取值跨度远大于前两个，这样不利于真实反映真实的相异度，为理处理这个问题，普通要对属性值进展规格化。所谓规格化就是将各个属性值按比例映射到一样的取值区间，这样是为了平衡各个属性对间隔的影响。通常将各个属性均映射到0,1区间，映射公式为： 其中max(ai)和

4、min(ai)表示一切元素项中第i个属性的最大值和最小值。例如，将例如中的元素规格化到0,1区间后，就变成了X=1,0,1，Y=0,1,0，重新计算欧氏间隔约为1.732。 2022/7/108.二元变量2022/7/109.二元变量相异度-实例2022/7/1010.分类与序数变量分类变量是二元变量的推行，类似于程序中的枚举变量，但各个值没有数字或序数意义，如颜色、民族等等，对于分类变量，用“取值不同的同位属性数/单个元素的全部属性数来标识其相异度。 序数变量是具有序数意义的分类变量，通常可以按照一定顺序意义陈列，如冠军、亚军和季军。对于序数变量，普通为每个值分配一个数，叫做这个值的秩，然后

5、以秩替代原值当做标量属性计算相异度。 2022/7/1011.向量对象对于向量，由于它不仅有大小而且有方向，所以闵可夫斯基间隔不是度量其相异度的好方法，一种流行的做法是用两个向量的余弦度量，其度量公式为： 其中|X|表示X的欧几里得范数。要留意，余弦度量度量的不是两者的相异度，而是类似度！ 2022/7/1012.聚类分析方法的分类划分方法层次方法基于密度的方法基于网格的方法基于模型的方法基于约束的方法2022/7/1013.划分方法根本思想：给定n个对象或数据元组的数据库，划分方法构建数据的k个划分，每一个划分表示一个簇，k=n。划分方法创建一个初始划分，然后采用迭代重定位技术，尝试经过对象

6、在组间的挪动来改良划分。典型的划分方法有1k均值算法，其中每个簇都用该簇中对象的均值来表示。2k中心点算法，其中每个簇用接近簇中心的一个对象来表示。它们的异同点有：k-均值算法和k-中心算法都属于聚类分析中的划分方法；k-均值算法是将簇中对象的均值作为簇的中心，可以是一个虚点，计算其他点与各个簇中心间隔，归入间隔最近的簇中；k-中心算法是找簇中最中心的点作为簇中心，是一个实践存在数据点。这只是均值与中心区别，两种算法详细流程还是不同的。 2022/7/1014.K均值算法的由来k平均聚类发明于1956年， 该算法最常见的方式是采用被称为劳埃德算法(Lloyd algorithm)的迭代式改良探

7、求法。劳埃德算法首先把输入点分成k个初始化分组，可以是随机的或者运用一些启发式数据。然后计算每组的中心点，根据中心点的位置把对象分到离它最近的中心，重新确定分组。继续反复不断地计算中心并重新分组，直到收敛，即对象不再改动分组中心点位置不再改动。 2022/7/1015.K均值算法1K均值算法是基于质心的技术，k均值算法以k为输入参数，把n个对象集合分为k个簇，使得簇内的类似度高，簇间的类似度低。簇的类似度是关于簇中对象的均值度量，可以看作簇的质心。K均值算法的处置流程如下，首先，随机的选择k个对象，每个对象代表一个簇的初始均值，对剩余的每个对象，根据其与各个簇均值的间隔。将它指派到最类似的簇。

8、然后计算每个簇的新均值，这个过程不断的反复，直到准那么函数收敛。通常采用平方误差准那么 这里Jcm是数据库中一切对象的平方误差的总和，Xi是空间中的点，表示给定的数据对象，Zj是簇Cj的平均值 Xi和Zj都是多维的。 2022/7/1016.K均值算法2算法：k均值。用于划分的k均值算法，每个簇的中心用簇中对象的均值来表示。输入：k:簇的数目， D:包含n个对象的数目集。输出：k个簇的集合。方法：从D中恣意选择k个对象作为初始簇中心；Repeat根据簇中对象的均值，将每个对象再指派到最类似的簇更新簇均值，即计算每个簇中对象的均值Until不再发生变化2022/7/1017.K均值算法32022

9、/7/1018.K-MEANS例如下面，我们来看看k-means算法一个有趣的运用例如：中国男足近几年究竟在亚洲处于几流程度？以下图是我采集的亚洲15只球队在2005年-2021年间大型杯赛的战绩 其中包括两次世界杯和一次亚洲杯。我提早对数据做了如下预处置：对于世界杯，进入决赛圈那么取其最终排名，没有进入决赛圈的，打入预选赛十强赛赋予40，预选赛小组未出线的赋予50。对于亚洲杯，前四名取其排名，八强赋予5，十六强赋予9，预选赛没出现的赋予17。这样做是为了使得一切数据变为标量，便于后续聚类。2022/7/1019.2022/7/1020.下面先对数据进展0,1规格化，下表是规格化后的数据202

10、2/7/1021. 接着用k-means算法进展聚类。设k=3，即将这15支球队分成三个集团。现抽取日本、巴林和泰国的值作为三个簇的种子，即初始化三个簇的中心为A：0.3, 0, 0.19，B：0.7, 0.76, 0.5和C：1, 1, 0.5。为什么选这三个呢？下面，计算一切球队分别对三个中心点的相异度，这里以欧氏间隔度量。下面是用程序求取的结果：2022/7/1022.从左到右依次表示各支球队到当前中心点的欧氏间隔，将每支球队分到最近的簇，可对各支球队做如下聚类：中国C，日本A，韩国A，伊朗A，沙特A，伊拉克C，卡塔尔C，阿联酋C，乌兹别克斯坦B，泰国C，越南C，阿曼C，巴林B，朝鲜B，

11、印尼C。第一次聚类结果：A：日本，韩国，伊朗，沙特；B：乌兹别克斯坦，巴林，朝鲜；C：中国，伊拉克，卡塔尔，阿联酋，泰国，越南，阿曼，印尼。2022/7/1023.下面根据第一次聚类结果，调整各个簇的中心点。A簇的新中心点为：(0.3+0+0.24+0.3)/4=0.21, (0+0.15+0.76+0.76)/4=0.4175, (0.19+0.13+0.25+0.06)/4=0.1575 = 0.21, 0.4175, 0.1575取簇中一切元素各自维度的算术平均数。用同样的方法计算得到B和C簇的新中心点分别为0.7, 0.7333, 0.4167，1, 0.94, 0.40625。202

12、2/7/1024. 用调整后的中心点再次进展聚类，得到：第二次迭代后的结果为：中国C，日本A，韩国A，伊朗A，沙特A，伊拉克C，卡塔尔C，阿联酋C，乌兹别克斯坦B，泰国C，越南C，阿曼C，巴林B，朝鲜B，印尼C。2022/7/1025.结果无变化，阐明结果已收敛，于是给出最终聚类结果：亚洲一流：日本，韩国，伊朗，沙特亚洲二流：乌兹别克斯坦，巴林，朝鲜亚洲三流：中国，伊拉克，卡塔尔，阿联酋，泰国，越南，阿曼，印尼看来数据通知我们，说国足近几年处在亚洲三流程度真的是没有冤枉他们，至少从国际杯赛战绩是这样的。其实上面的分析数据不仅通知了我们聚类信息，还提供了一些其它有趣的信息，例如从中可以定量分析出

13、各个球队之间的差距，例如，在亚洲一流队伍中，日本与沙特程度最接近，而伊朗那么相距他们较远，这也和近几年伊朗衰败的实践相符。 2022/7/1026.k均值算法的优点假设变量很大，k均值比层次聚类的计算速度更快假设k很小。与层次聚类相比，k均值可以得到更严密的簇，尤其是对于球状簇。对大数据集，是可伸缩和高效率的。算法尝试找出使平方误差函数值最小的k个划分。当结果簇是密集的，而簇与簇之间区别明显的时候，效果较好。2022/7/1027.K均值算法的缺陷没有指明初始化均值的方法。常用的方法是随机的选取k个样本作为均值。产生的结果依赖于均值的初始值，经常发生得到次优划分的情况。处理方法是多次尝试不同的

14、初始值。能够发生间隔簇中心mi最近的样本集为空的情况，因此， mi将得不到更新。这是一个必需处置的问题，但我们忽略该问题。结果依赖于|x- mi|的度量单位。一个常用的处理方法是用规范差规范各个变量，虽然这并非总是可取的。结果还依赖于k值，所以难以比较聚类结果的优劣。不适宜发现非凸面外形的簇，并对噪声和离群点数据是较敏感的，由于少量的这类数据可以对均值产生极大的影响。2022/7/1028.K均值算法的改良改良措施：1样本数据预处置。计算样本对象两两之间的间隔，筛掉与其它一切样本的间隔和最大的m个对象。2初始聚类中心的选择。如不采用簇中的平均值作为参考点，而选用簇中位置最接近中心的对象。这样可

15、以防止孤立点的影响。2022/7/1029.K均值算法的变种首先采用层次凝聚算法决议结果簇的数目，并找到一个初始聚类，然后用迭代重定位来改良该聚类。K众数方法，它扩展了k均值方式来聚类分类数据，用簇的众数来取代簇均值，采用新的相异性度量处置分类对象，采用基于频率的方法更新簇众数。EM期望最大化算法，与k均值算法将每一个对象指派到一个簇相反，在EM算法中，每个对象按照权重指派到每个簇，其中权重表示对象的隶属概率。2022/7/1030.假设数据发掘的义务是将如下的八个点用(x,y)代表位置聚类为三个类。A1(2,10),A2(2,5),A3(8,4),B1(5,8),B2(7,5),B3(6,4

16、),C1(1,2),C2(4,9)2022/7/1031.假设初始我们选择A1,B1,和C1为每个簇的中心，用k-means算法来给出2022/7/1032.A1-A2 ：dist=(2-2)2 +(5-10)2=25;A1-A3:dist=(8-2)2+(4-10)2=72; A1-B2:dist=(7-2)2+(5-10)2 =50; A1-B3:dist=(6-2)2+(4-10) 2=52;A1-C2:dist=(4-2)2+(9-10)2=5; B1-A2:dist=(2-5)2+(5-8)2=18; B1-A3:dist=(8-5)2+(4-8)2=25;B1-B2:dist=(7

17、-5)2+(5-8)2=13 B1-B3:dist=(6-5)2+(4-8)2=172022/7/1033.B1-C2:dist=(4-5)2+(9-8)2=2 C1-A2:dist=(2-1)2+(5-2)2=10 C1-A3:dist=(8-1)2+(4-2)2=53 C1-B2:dist=(7-1)2+(5-2)2=45 C1-B3:dist=(6-1)2+(4-2)2=29 C1-C2:dist=(4-1)2+(9-2)2=582022/7/1034.其他五个结点选择与其最近的质心，三个簇分别为：B1,C2,B3,B2,A3C1,A2A1计算这三个簇的质心：B1,C2,B3,B2,A3的质心为：(8+5+7+6+4/5,(4+8+5+4+9)/5)即6，6；C1,A2的质心为：2+1/2，5+2/2即为1.5,3.5;A1的质心为2，10。2022/7/1035.在第一次循环执行后的三个簇中心分别为6，6，1.5,3.5，2，10重新指派各个对象到离其最近的质心，与上面方面一样，构成的三个簇为A3,B1,B2,B3，C1，A2，A1,C2