第11章-数据挖掘聚类分析.ppt

1、数据挖掘,聚类分析,引言,“物以类聚，人以群分”。对事物进行分类，是人们认识事物的出发点，也是人们认识世界的一种重要方法。因此，分类学已成为人们认识世界的一门基础科学。 在生物、经济、社会、人口等领域的研究中，存在着大量量化分类研究。例如：在生物学中，为了研究生物的演变，生物学家需要根据各种生物不同的特征对生物进行分类。 在经济研究中，为了研究不同地区城镇居民生活中的收入和消费情况，往往需要划分不同的类型去研究。 在地质学中，为了研究矿物勘探，需要根据各种矿石的化学和物理性质和所含化学成分把它们归于不同的矿石类。 在人口学研究中，需要构造人口生育分类模式、人口死亡分类状况，以此来研究人口的生育

2、和死亡规律。,但历史上这些分类方法多半是人们主要依靠经验作定性分类，致使许多分类带有主观性和任意性，不能很好地揭示客观事物内在的本质差别与联系；特别是对于多因素、多指标的分类问题，定性分类的准确性不好把握。 为了克服定性分类存在的不足，人们把数学方法引入分类中，形成了数值分类学。 后来随着多元统计分析的发展，从数值分类学中逐渐分离出了聚类分析方法。 随着计算机技术的不断发展，利用数学方法研究分类不仅非常必要而且完全可能，因此近年来，聚类分析的理论和应用得到了迅速的发展。 聚类分析就是分析如何对样品（或变量-在多元统计中，它就是一个向量）进行量化分类的问题。通常聚类分析分为Q型聚类和R型聚类。Q

3、型聚类是对样品进行分类处理，R型聚类是对变量进行分类处理。,什么是聚类,聚类（clustering）就是将数据分组成多个簇（cluster），使得同一个簇的对象之间具有较高的相似度，不同簇的对象相异 早在孩提时代，人就通过不断改进下意识中的聚类模式来学会如何区分猫和狗、动物和植物,聚类无所不在,聚类无所不在,聚类无所不在,聚类的应用领域,有贡献的领域,什么情况下应该聚类,聚类分析原理,聚类与分类,相似性及其度量,从复杂数据中提取相对简单分组结构的主要工作是找到一个“紧密度”或相似性度量 “当我们看到它的时候，我们即可领会” 基于特征来测量相似性 产生特征 提炼特征 规范化特征 减少特征,测量相

4、似性,在选择相似性度量时掺杂着大量的主观因素：变量的本质（离散的、连续的、二值的）或测量刻度（标称的、顺序的、间隔的、比值的）及主题知识 当所有项被聚类后，通常用距离表明邻近度 变量通常基于相关系数或关联度量而聚合,距离度量的常见计算方法,令O1和O2表示客观世界中的两个对象，O1和O2之间的距离（相异性）是一个实数，用distance(O1,O2)或d(O1，O2) 明考夫斯基距离,（4）幂距离 （5）差异百分率,二元属性对象的相似性,当项不能用有意义的p维测量表示时，项对之间的比较通常根据某些特征的存在和缺失完成，相似的项具有更多的共同项 引入二元变量来描述是否具有某种特征，若具有该特征变

5、量值为1，否则变量值为0 个体对的变量得分计算得分矩阵 1 1的个数为a 1 0的个数为b 0 1的个数为c 0 0的个数为d,相似性系数,简单匹配系数SMC Jaccard系数 Rao系数,实例分析,聚类的基本类型,层次聚类,自底向上（凝聚） 假定所有项属于一个单独簇，然后寻找最佳配对并合并成一个新的簇 自顶向下（分裂） 开始将所有数据看作一个簇，考虑所有可能的方法，将簇一分为二选择最佳划分，并递归第在这两个上继续划分,凝聚层次聚类,依靠共同的距离度量，聚类过程从寻找距离最近的簇开始，并把这两个簇合并为一个簇。 在开始时，让每个对象自成一簇，每个簇都以选定的距离度量定义 合并后，如何确定新簇

6、之间的距离？ 单连接（single linkage） 完全连接（complete linkage）,单连接（最近邻）,两个簇的距离由不同簇的两个最近的对象间的距离决定 簇的距离是属于不同簇的两个样本间的最近距离 d(c1,c2)=mind(o,O),完全连接（最远邻）,两个簇的距离隶属于不同簇的距离最远的两个对象的距离所决定（最远邻的距离）,组平均,两个簇的距离就是隶属不同簇的所有对象的距离的平均 加权平均 组质心 加权组质心 沃德法,单连接,完全连接,层次聚类的优缺点,优点 可以通过观察树状图来确定正确的簇数目 层次的本质很好地反映了人类对某些领域的直觉 树状图的一个潜在应用时可以用来检测离

7、群点 缺点 有时会表现出无意义的或者不合逻辑的模式 无需事先指定簇的数目 层次本质很好地反映了人类对某些领域认识的直觉 可伸缩性不好：时间复杂性至少为O(n2),n是所有对象的数量 和任何启发式搜素算法一样，局部最优是一个问题 对结果的解释具有主观性,算法的步骤,决定k的取值 初始化k个簇中心 通过把对象分配给最近的簇中心来确定N个对象的簇隶属关系 假设上面所得的隶属关系是正确的，重新计算k个簇中心 若在最后一次迭代中N个对象无一再改变隶属关系，则退出，否则再转第3步,K-means算法,基本思想是初始随机给定K个簇中心，按照最邻近原则把待分类样本点分到各个簇。然后按平均法重新计算各个簇的质心

8、，从而确定新的簇心。一直迭代，直到簇心的移动距离小于某个给定的值 K-Means聚类算法主要分为三个步骤：(1)第一步是为待聚类的点寻找聚类中心(2)第二步是计算每个点到聚类中心的距离，将每个点聚类到离该点最近的聚类中去(3)第三步是计算每个聚类中所有点的坐标平均值，并将这个平均值作为新的聚类中心反复执行(2)、(3)，直到聚类中心不再进行大范围移动或者聚类次数达到要求为止,K-均值非常适合用于产生球状簇，是数值的、非监督的、非确定的、迭代的,表示数据点xij到簇中心Cj的距离度量 ，也指示n个数据点及其各自簇中心的 距离,K-中心点,与k-均值相同的过程，只有样本空间中的数据点可以作为中心点

9、 K-重点店是典型的划分算法。对于给定的k，采用该算法的目标是在数据集中寻找k个代表，使得每个对象划归到它最邻近的代表所表示的簇中时，对象和代表的距离最小,算法,1）任意选取k个对象作为初始中心点 2）Repeat 把剩余对象分配到距离它最近的中心点所在的簇 随机选择一个非中心点对象O 计算随机用O交换Oj的总代价S 如S0,则用O交换Oj，形成新的k个中心点的集合 Until 无变化发生 3）结束,工作方式,首先在数据中为每个簇随意选一个对象，从而在n个对象中发现k个簇 这些作为代表的对象称为中心点，其余对象为非中心点 计算所有非中心点到每个中心点的距离，并将所有非中心点划分到距它最近的簇

10、只要聚类结果可以改善，便不断地用非中心点代替中心点 聚类质量通过代价函数来评价，该代价函数反映了对象和它所属簇的代表之间的平均相异性,工作方式,1）任意选择k个代表对象 2）计算每对代表对象Oi和非代表兼Oh的TCih 3）选择满足min(Oi,Oh,TCih)的Oi,Oh对 如果最小的TCih为负，用Oh代替Oi，返回到第2步 4）否则，为每个非代表对象寻找最相似对象,现代聚类方法,五类： 层次方法（BIRCH/CURE/ROCK) 划分方法(K-均值/PAM/CLARA/CLARANS/K-众数） 基于密度方法 基于网格方法 基于模型方法,增量聚类,现在，有些应用涉及到成千上万个高维数据集

11、。由于数据集规模太大，不可能把整个数据集储存在主存储器里。 有三个方法可处理这类数据的聚类分析： 可以把数据集存储在辅助存储器里，对数据的各个子集进行独立地聚类，然后合并生成整个数据集的聚类，称为分治方法。 可以使用增量聚类算法。 可以并行实现聚类算法，并行计算的好处是提高了分治方法的效率。,增量聚类算法的步骤： 把第一个数据项分配到第一个类里。 考虑下一个数据项，把它分配到目前某个类中或一个新类中。它基于一些准则的，例如新数据项到目前类的重心的距离。在这种情况下，每次添加一个新数据项到一个目前的类中时，需要重新计算重心的值。 重复步骤2，直到所有的数据样本都被聚类完毕。,增量算法是非迭代的，

12、需要主存储空间非常小，所需要的时间也很少，即使采用迭代算法，所需的计算时间也不会显著增加。 增量聚类存在的一个明显的缺点：对样本的顺序非常敏感。不同的顺序会产生不同的分区。 例如：仍然采用上例的数据集。假定样本的顺序是x1,x2,x3,x4,x5，则类相似度阈值水平是=3。,第一样本x1为第一个类C1=x1。C1的重心为M1=0,2。 开始分析其他样本。 a)把第二个样本x2和M1比较，距离d为： d(x2,M1)=(02+22)1/2=2.03 因此， x2属于类C1 ，新的重心是： M1=0,1 b)第三个样本x3和重心M1比较： d(x3,M1)=(1.52+12)1/2=1.83 x3

13、 C1 C1 =x1,x2,x3 M1=0.5,0.66,c)第四个样本x4和重心M1比较： d(x4,M1)=(4.52+0.662)1/2=4.553 x4 C2 =x4 M2=5,0 d)第五个样本和这两个类的重心相比较： d(x5,M1)=(4.52+1.442)1/2=4.723 d(x5,M2)=(02+22)1/2=23 x5 C2 C2 =x4,x5 M2=5,1 3. 分析完所有的样本，聚类结果是获得两个类： C1 =x1,x2,x3和C2 =x4,x5 如果观察的样本的顺序不同，聚类结果也不同。,对于大多数分区聚类算法，包括迭代方法，都是通过该类的特征向量CF给出的类的简要

14、表示，每个类的参数由3部分组成，类中点(样本)的个数，类的重心和类的半径。 类的半径定义为类中的点到重心的平均平方距离的平方根(平均类内方差)。 当添加和删除类中的点时，可以通过旧的CF来计算新CF，而不需要用类中所有点去计算新的CF，这一点非常重要。,如果样本是分类的数据，就没有办法计算类的重心来表述类。另一种算法K-最近邻法可用于估计样本和目前类间的距离(或相似度) 。 算法的基本步骤： 计算新的样本到所有已被分类的旧样本之间的距离。 把这些距离按升序排列，选个最近值的样本。 运用投票原理，把新样本添加(分类)给已选的个样本中最大的类。,例如：给出6个6维分类的样本： X1=A,B,A,B,C,B X2=A,A,A,B,A,B X3=B,B,A,B,A,B X4=B,A,B,A,C,A X5=A,C,B,A,B,B X6=A,C,B,A,B,B 它们被聚集成两个类： C1=x1,x2,x3和C2=x4,x5,x6。 新样本Y=A,C,A,B,C,A属于哪一类？,运用-最近邻算法，第一步求出新样本和其他所有已聚类样本间的距离。 采用SMC求出样本间的相似度，代替求样本间的距离。 SMC(Y,X1)=