《数据仓库与数据挖掘》课件-第7章：数据挖掘方法 - 聚类

大数据分析实务

第7章数据挖掘方法7.3聚类分析

聚类分析聚类分析聚类分析聚类分析聚类分析如何度量事物相似性如何把不同事物分组组内和组间如何处理7.3.1聚类定义聚类就是按照事物的某些属性，把事物聚集成类，使类间的相似性尽可能小，类内相似性尽可能大。7.3.1聚类定义7.3.1聚类定义一个能产生高质量聚类的算法必须满足下面两个条件:类内数据或对象的相似性最强类间数据或对象的相似性最弱7.3.2聚类分析中的数据许多基于内存的聚类算法选择两种有代表性的数据结构：数据矩阵和相异度矩阵7.3.2聚类分析中的数据d(i,j)表示对象i和对象j之间的差异（或不相似程度）；通常d(i,j)为一个非负数；当对象i和对象j非常相似或彼此“接近”时，该数值接近0；该数值越大，就表示对象i和对象j越不相似。由于有d(i,j)=d(j,i)且d(i,i)=07.3.2聚类分析中的数据欧氏距离7.3.3层次方法层次的聚类方法可以分为凝聚的（agglomerative）和分裂的（divisive）层次聚类。一旦一个合并或分裂被执行，就不能修正，因此一个纯粹的层次聚类方法的聚类质量受到了一定的限制。7.3.3层次方法

凝聚的层次聚类：首先将每个对象作为一族，然后合并这些原子簇为越来越大的簇，直到所有的对象都在一个簇中，或者某个终结条件被满足。一般来说为最小距离法，即找出哪两个事物距离最短。绝大多数层次聚类方法属于这一类，它们只是在簇间相似度的定义上会有所不同。7.3.3层次方法

分裂的层次聚类：首先将所有对象作为一族，然后逐步分裂这个族中的点，直到所有的对象被分开到满足某个终结条件。一般来说为最大距离法，即找出哪两个事物距离最长。例为了研究辽宁等5省1991年城镇居民生活消费情况的分布规律，根据调查资料做类型分类，用最短距离做类间分类。数据如下：x1x2x3x4x5x6x7x8辽宁17.9039.778.4912.9419.2711.052.0413.29浙江27.6850.3711.3513.3019.2514.592.7514.87河南39.4227.938.208.1416.179.421.559.76甘肃49.1627.989.019.3215.999.101.8211.35青海510.0628.6410.5210.0516.188.391.9610.81将每一个省区视为一个样本，先计算5个省区之间的欧式距离，用D0表示距离矩阵（对称阵，故给出下三角阵）因此将3.4合并为一类，为类6，替代了3、4两类类6与剩余的1、2、5之间的距离分别为：

d(3,4)1=min(d31,d41)=min(13.80,13.12)=13.12d(3,4)2=min(d32,d42)=min(24.63,24.06)=24.06d(3,4)5=min(d35,d45)=min(3.51,2.21)=2.21得到新矩阵合并类6和类5，得到新类7类7与剩余的1、2之间的距离分别为：

d(5,6)1=min(d51,d61)=min(12.80,13.12)=12.80d(5,6)2=min(d52,d62)=min(23.54,24.06)=23.54

得到新矩阵合并类1和类2，得到新类8此时，我们有两个不同的类：类7和类8。它们的最近距离d(7,8)

=min(d71,d72)=min(12.80,23.54)=12.80得到矩阵最后合并为一个大类。这就是按最短距离定义类间距离的系统聚类方法。最长距离法类似！7.3.4划分方法：K-meansn个对象或元组的数据库，一个划分方法构建数据的k个划分，每个划分表示一个聚簇，并且k≤n。也就是说，它将数据划分为k个组，同时满足如下的要求：（a）每个组至少包含一个对象；（b）每个对象必须属于且只属于一个组。7.3.4划分方法：K-meansK-means算法基本步骤:（1）从n个数据对象任意选择k个对象作为初始聚类中心；（2）根据每个聚类对象的均值（中心对象），计算每个对象与这些中心对象的距离；并根据最小距离重新对相应对象进行划分；（3）重新计算每个（有变化）聚类的均值（中心对象）；（4）计算标准测度函数，当满足一定条件，如函数收敛时，则算法终止；如果条件不满足则回到步骤（2）。7.3.4划分方法：K-means7.3.4划分方法：K-means7.3.4划分方法：K-means7.3.4划分方法：K-means收敛聚类实例：中国男足在亚洲什么水平？亚洲15只球队在2005-2010年间大型杯赛的战绩，其中包括两次世界杯和一次亚洲杯。对数据做预处理：对于世界杯，进入决赛圈则取其最终排名，没有进入决赛圈的，打入预选赛十强赛赋予40，预选赛小组未出线的赋予50。对于亚洲杯，前四名取其排名，八强赋予5，十六强赋予9，预选赛没出现的予177.3.4划分方法：K-means下面先对数据进行[0,1]规格化，下面是规格化后的数据：

接着用k-means算法进行聚类。设k=3，即将这15支球队分成三个集团。现抽取日本、巴林和泰国的值作为三个簇的种子，即初始化三个簇的中心为A：{0.3,

0,

0.19}，B：{0.7,

0.76,

0.5}和C：{1,

1,

0.5}。下面，计算所有球队分别对三个中心点的相异度，这里以欧氏距离度量。下面是用程序求取的结果：

从做到右依次表示各支球队到当前中心点的欧氏距离，将每支球队分到最近的簇，可对各支球队做如下聚类：中国C，日本A，韩国A，伊朗A，沙特A，伊拉克C，卡塔尔C，阿联酋C，乌兹别克斯坦B，泰国C，越南C，阿曼C，巴林B，朝鲜B印尼C。日本巴林泰国

聚类习题（划分方法）Oxy102