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

聚类分析K-means算法李广明2019/7/301聚类分析概念聚类与分类的不同在于：分类作为一种监督学习方法，要求必须事先明确知道各个类别的信息，并且断言所有待分类项都有一个类别与之对应。但是很多时候上述条件得不到满足，尤其是在处理海量数据的时候，如果通过预处理使得数据满足分类算法的要求，则代价非常大，这时候可以考虑使用聚类算法。聚类属于无监督学习，相比于分类，聚类不依赖预定义的类和类标号的训练实例。聚类分析指将物理或抽象对象的集合分组成为由类似的对象组成的多个类的分析过程。2019/7/302聚类算法可以用来完成对L维特征向量的分组。对应于相同地面类型的点，如水，将其聚类在一起形成一组。一旦这样分组以后，分析人员就可以通过每一组中的样本点和地面数据的参考信息相联系来识别地面类型。2019/7/303聚类分析中的数据类型2019/7/304相异度计算2019/7/305区间标度变量2019/7/306对象间的相似度和相异度对象间的相似度和相异度是基于两个对象间的距离来计算的。标量也就是无方向意义的数字，也叫标度变量。现在先考虑元素的所有特征属性都是标量的情况。例如，计算X={2,1,102}和Y={1,3,2}的相异度。一种很自然的想法是用两者的欧几里得距离来作为相异度，欧几里得距离的定义如下：其意义就是两个元素在欧氏空间中的集合距离，因为其直观易懂且可解释性强，被广泛用于标识两个标量元素的相异度。将上面两个示例数据代入公式，可得两者的欧氏距离为：除欧氏距离外，常用作度量标量相异度的还有曼哈顿距离和闵可夫斯基距离，两者定义如下：曼哈顿距离：闵可夫斯基距离：2019/7/307规格化问题上面这样计算相异度的方式有一点问题，就是取值范围大的属性对距离的影响高于取值范围小的属性。例如上述例子中第三个属性的取值跨度远大于前两个，这样不利于真实反映真实的相异度，为了解决这个问题，一般要对属性值进行规格化。所谓规格化就是将各个属性值按比例映射到相同的取值区间，这样是为了平衡各个属性对距离的影响。通常将各个属性均映射到[0,1]区间，映射公式为：其中max(ai)和min(ai)表示所有元素项中第i个属性的最大值和最小值。例如，将示例中的元素规格化到[0,1]区间后，就变成了X’={1,0,1}，Y’={0,1,0}，重新计算欧氏距离约为1.732。2019/7/308二元变量2019/7/309二元变量相异度-实例2019/7/3010分类与序数变量分类变量是二元变量的推广，类似于程序中的枚举变量，但各个值没有数字或序数意义，如颜色、民族等等，对于分类变量，用“取值不同的同位属性数/单个元素的全部属性数”来标识其相异度。序数变量是具有序数意义的分类变量，通常可以按照一定顺序意义排列，如冠军、亚军和季军。对于序数变量，一般为每个值分配一个数，叫做这个值的秩，然后以秩代替原值当做标量属性计算相异度。2019/7/3011向量对象对于向量，由于它不仅有大小而且有方向，所以闵可夫斯基距离不是度量其相异度的好办法，一种流行的做法是用两个向量的余弦度量，其度量公式为：其中||X||表示X的欧几里得范数。要注意，余弦度量度量的不是两者的相异度，而是相似度！2019/7/3012聚类分析方法的分类划分方法层次方法基于密度的方法基于网格的方法基于模型的方法基于约束的方法2019/7/3013划分方法基本思想：给定n个对象或数据元组的数据库，划分方法构建数据的k个划分，每一个划分表示一个簇，k=n。划分方法创建一个初始划分，然后采用迭代重定位技术，尝试通过对象在组间的移动来改进划分。典型的划分方法有（1）k均值算法，其中每个簇都用该簇中对象的均值来表示。（2）k中心点算法，其中每个簇用接近簇中心的一个对象来表示。它们的异同点有：k-均值算法和k-中心算法都属于聚类分析中的划分方法；k-均值算法是将簇中对象的均值作为簇的中心，可以是一个虚点，计算其他点与各个簇中心距离，归入距离最近的簇中；k-中心算法是找簇中最中心的点作为簇中心，是一个实际存在数据点。这只是均值与中心区别，两种算法具体流程还是不同的。2019/7/3014K均值算法的由来k平均聚类发明于1956年，该算法最常见的形式是采用被称为劳埃德算法(Lloydalgorithm)的迭代式改进探索法。劳埃德算法首先把输入点分成k个初始化分组，可以是随机的或者使用一些启发式数据。然后计算每组的中心点，根据中心点的位置把对象分到离它最近的中心，重新确定分组。继续重复不断地计算中心并重新分组，直到收敛，即对象不再改变分组（中心点位置不再改变）。2019/7/3015K均值算法（1）K均值算法是基于质心的技术，k均值算法以k为输入参数，把n个对象集合分为k个簇，使得簇内的相似度高，簇间的相似度低。簇的相似度是关于簇中对象的均值度量，可以看作簇的质心。K均值算法的处理流程如下，首先，随机的选择k个对象，每个对象代表一个簇的初始均值，对剩余的每个对象，根据其与各个簇均值的距离。将它指派到最相似的簇。然后计算每个簇的新均值，这个过程不断的重复，直到准则函数收敛。通常采用平方误差准则这里Jc（m）是数据库中所有对象的平方误差的总和，Xi是空间中的点，表示给定的数据对象，Zj是簇Cj的平均值（Xi和Zj都是多维的）。2019/7/3016K均值算法（2）算法：k均值。用于划分的k均值算法，每个簇的中心用簇中对象的均值来表示。输入：k:簇的数目，D:包含n个对象的数目集。输出：k个簇的集合。方法：1.从D中任意选择k个对象作为初始簇中心；2.Repeat3.根据簇中对象的均值，将每个对象（再）指派到最相似的簇4.更新簇均值，即计算每个簇中对象的均值5.Until不再发生变化2019/7/3017K均值算法（3）2019/7/3018K-MEANS示例下面，我们来看看k-means算法一个有趣的应用示例：中国男足近几年到底在亚洲处于几流水平？下图是我采集的亚洲15只球队在2005年-2010年间大型杯赛的战绩其中包括两次世界杯和一次亚洲杯。我提前对数据做了如下预处理：对于世界杯，进入决赛圈则取其最终排名，没有进入决赛圈的，打入预选赛十强赛赋予40，预选赛小组未出线的赋予50。对于亚洲杯，前四名取其排名，八强赋予5，十六强赋予9，预选赛没出现的赋予17。这样做是为了使得所有数据变为标量，便于后续聚类。2019/7/30192019/7/3020下面先对数据进行[0,1]规格化，下表是规格化后的数据2019/7/3021接着用k-means算法进行聚类。设k=3，即将这15支球队分成三个集团。现抽取日本、巴林和泰国的值作为三个簇的种子，即初始化三个簇的中心为A：{0.3,0,0.19}，B：{0.7,0.76,0.5}和C：{1,1,0.5}。（为什么选这三个呢？）下面，计算所有球队分别对三个中心点的相异度，这里以欧氏距离度量。下面是用程序求取的结果：2019/7/3022从左到右依次表示各支球队到当前中心点的欧氏距离，将每支球队分到最近的簇，可对各支球队做如下聚类：中国C，日本A，韩国A，伊朗A，沙特A，伊拉克C，卡塔尔C，阿联酋C，乌兹别克斯坦B，泰国C，越南C，阿曼C，巴林B，朝鲜B，印尼C。第一次聚类结果：A：日本，韩国，伊朗，沙特；B：乌兹别克斯坦，巴林，朝鲜；C：中国，伊拉克，卡塔尔，阿联酋，泰国，越南，阿曼，印尼。2019/7/3023下面根据第一次聚类结果，调整各个簇的中心点。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}。2019/7/3024用调整后的中心点再次进行聚类，得到：第二次迭代后的结果为：中国C，日本A，韩国A，伊朗A，沙特A，伊拉克C，卡塔尔C，阿联酋C，乌兹别克斯坦B，泰国C，越南C，阿曼C，巴林B，朝鲜B，印尼C。2019/7/3025结果无变化，说明结果已收敛，于是给出最终聚类结果：亚洲一流：日本，韩国，伊朗，沙特亚洲二流：乌兹别克斯坦，巴林，朝鲜亚洲三流：中国，伊拉克，卡塔尔，阿联酋，泰国，越南，阿曼，印尼看来数据告诉我们，说国足近几年处在亚洲三流水平真的是没有冤枉他们，至少从国际杯赛战绩是这样的。其实上面的分析数据不仅告诉了我们聚类信息，还提供了一些其它有趣的信息，例如从中可以定量分析出各个球队之间的差距，例如，在亚洲一流队伍中，日本与沙特水平最接近，而伊朗则相距他们较远，这也和近几年伊朗没落的实际相符。2019/7/3026K均值算法的优点1.如果变量很大，k均值比层次聚类的计算速度更快（如果k很小）。2.与层次聚类相比，k均值可以得到更紧密的簇，尤其是对于球状簇。3.对大数据集，是可伸缩和高效率的。4.算法尝试找出使平方误差函数值最小的k个划分。当结果簇是密集的，而簇与簇之间区别明显的时候，效果较好。2019/7/3027K均值算法的缺点1.没有指明初始化均值的方法。常用的方法是随机的选取k个样本作为均值。2.产生的结果依赖于均值的初始值，经常发生得到次优划分的情况。解决方法是多次尝试不同的初始值。3.可能发生距离簇中心mi最近的样本集为空的情况，因此，mi将得不到更新。这是一个必须处理的问题，但我们忽略该问题。4.结果依赖于||x-mi||的度量单位。一个常用的解决方法是用标准差规范各个变量，虽然这并非总是可取的。结果还依赖于k值，所以难以比较聚类结果的优劣。5.不适合发现非凸面形状的簇，并对噪声和离群点数据是较敏感的，因为少量的这类数据能够对均值产生极大的影响。2019/7/3028K均值算法的改进改进措施：（1）样本数据预处理。计算样本对象两两之间的距离，筛掉与其它所有样本的距离和最大的m个对象。（2）初始聚类中心的选择。如不采用簇中的平均值作为参考点，而选用簇中位置最靠近中心的对象。这样可以避免孤立点的影响。2019/7/3029K均值算法的变种1.首先采用层次凝聚算法决定结果簇的数目，并找到一个初始聚类，然后用迭代重定位来改进该聚类。2.K众数方法，它扩展了k均值模式来聚类分类数据，用簇的众数来取代簇均值，采用新的相异性度量处理分类对象，采用基于频率的方法更新簇众数。3.EM（期望最大化）算法，与k均值算法将每一个对象指派到一个簇相反，在EM算法中，每个对象按照权重指派到每个簇，其中权重表示对象的隶属概率。2019/7/3030假设数据挖掘的任务是将如下的八个点（用(x,y)代表位置）聚类为三个类。A1(2,10),A2(2,5),A3(8,4),B1(5,8),B2(7,5),B3(6,4),C1(1,2),C2(4,9)2019/7/3031假设初始我们选择A1,B1,和C1为每个簇的中心，用k-means算法来给出2019/7/3032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-5)2+(5-8)2=13B1-B3:dist=(6-5)2+(4-8)2=172019/7/3033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=