,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,第二章 聚类分析,分类与聚类的区别,分类：用已知类别的样本训练集来设计分类器（监督学习）,聚类（集群）：用事先不知类别的样本，而利用样本的先验知识来构造分类器（无监督学习）,2.1,聚类分析的概念,基本思想：,对一批没有标明类别及类数的模式样本集，根据模式间的相似程度，按照物以类聚、人以群分的思想，将相似的模式分为一类，不相似的分为另一类。,特征的类型,1.,低层特征：,无序尺度：有明确的数量和数值。,有序尺度：有先后、好坏的次序关系，如酒,分为上，中，下三个等级。,名义尺度：无数量、无次序关系，如有红，,黄两种颜色,2.,中层特征：经过计算，变换得到的特征,3.,高层特征：在中层特征的基础上有目的的经过运,算形成,例如：椅子的重量,=,体积*比重,体积与长，宽，高有关；比重与材料，纹理，颜色有关。这里低、中、高三层特征都有了。,方法的有效性,特征选取不当,特征过少,特征过多,量纲问题,主要聚类分析技术,谱系法（系统聚类，层次聚类法）,基于目标函数的聚类法（动态聚类）,图论聚类法,模糊聚类分析法,2.2,模式相似度度量,各种距离表示相似性：,绝对值距离,已知两个样本,x,i,=(x,i1,x,i2,x,i3,x,in,),T,x,j,=(x,j1,x,j2,x,j3,x,jn,),T,欧几里德距离,明考夫斯基距离,其中当,q=1,时为绝对值距离，当,q=2,时为欧氏距离,切比雪夫距离,q,趋向无穷大时明氏距离的极限情况,马哈拉诺比斯距离,其中,x,i,，,x,j,为特征向量，为协方差。使用的条件是,样 本符合正态分布,夹角余弦,为,xi xj,的均值 即样本间夹角小的为一类，具有相似性,例：,x1,x2,x3,的夹角如图：,因为,x1,x2,的夹角小，所以,x1,x2,最相似。,x,1,x,1,x,2,x,2,x,3,相关系数,为,x,i,x,j,的均值,注意：在求相关系数之前，要将数据标准化,2.3,类的定义和与类间距离,用距离进行定义类（书）,非监督学习方法分类,1、基于概率密度函数估计的直接方法,(,不实用）,2、基于样本间相似性度量的间接聚类方法,两类间的距离,1、最短距离：两类中相距最近的两样本间的距离。,2、最长距离 ：两类中相距最远的两个样本间的距离。,3、中间距离：最短距离和最长距离都有片面性，因此有时用中间距离。,设,1,类和,23,类间的最短距离为,d,12,，,最长距离为,d,13,，,23,类的长度为,d,23,，,则中间距离为：,上式推广为一般情况：,4、重心距离：均值间的距离,5、类平均距离：两类中各个元素两两之间的距离平方相加后取平均值,6、离差平方和：,设,N,个样品原分,q,类，则定义第,i,类的离差平方和为：,离差平方和增量：设样本已分成,p,q,两类，若把,p,q,合为,r,类，则定义离差平方：,聚类准则,类内距离越小越好,类间距离越大越好,一些准则函数,聚类分析三要素,相似性测度,聚类准则,聚类算法,2.4,聚类的算法,（,1),根据相似性阈值和最小距离原则的简单聚类法,（,2,）按照最小距离原则不断进行两类合并的方法,（,3,）依据准则函数的动态动态聚类算法,系统聚类的算法,谱系聚类的算法,原理、步骤,例：如下图所示,1、设全部样本分为6类，,2、作距离矩阵,D(0),1,2,3,4,5,2,9,3,1,16,4,49,16,64,5,25,4,36,4,6,64,25,81,1,9,3、求最小元素：,4、把,1,3,合并,7,=(1,3),4,6,合并,8,=(4,6),5,、,作距离矩阵,D(1),7,2,8,2,9,8,49,16,5,25,4,4,6、若合并的类数没有达到要求，转3。否则停止。,3、求最小元素：,4,、,8,5,2,合并,9,=（2,5,4,6）,分解聚类,分解聚类：把全部样本作为一类，然后根据相似性、相邻性分解。,目标函数 两类均值方差,N：,总样本数，：,1,类样本数,：,2,类样本数，,分解聚类框图：,初始分类,调整分类方案,最终结果,目标函数,达到最优先？,对分算法：略,例：已知21个样本，每个样本取二个特征，原始资料矩阵如下表：,样本号,1,2,3,4,5,6,7,8,9,10,x,1,0,0,2,2,4,4,5,6,6,7,x,2,6,5,5,3,4,3,1,2,1,0,11,12,13,14,15,16,17,18,19,20,21,-4,-2,-3,-3,-5,1,0,0,-1,-1,-3,3,2,2,0,2,1,-1,-2,-1,-3,-5,目标函数,解：第一次分类时计算所有样本，分别划到,时的,E,值，找出最大的。,1、开始时，,2、分别计算当 划入,时的,E,值,把 划入,时有,然后再把 划入 时对应的,E,值，找出一个最大的,E,值。,把 划为 的,E,值最大。,E(1)=56.6,再继续进行第二，第三次迭代,计算出,E(2),E(3),次数,E,值,1 56.6,2 79.16,3 90.90,4 102.61,5 120.11,6 137.15,7 154.10,8 176.15,9 195.26,10 213.07,11 212.01,第10次迭代 划入 时，,E,最大。于是分成以下两类：,每次分类后要重新计算 的值。可用以下递推公式：,动态聚类,兼顾系统聚类和分解聚类,一、动态聚类的方法概要,先选定某种距离作为样本间的相似性的度量;,确定评价聚类结果的准则函数;,给出某种初始分类，用迭代法找出使准则函数取极值的最好的聚类结果。,选代表点,初始分类,分类合理否,最终分类,修改分类,Y,N,动态聚类框图,二、代表点的选取方法：代表点就是初始分类的聚类中心数,k,凭经验选代表点，根据问题的性质、数据分布，从直观上看来较合理的代表点,k;,将全部样本随机分成,k,类，计算每类重心，把这些重心作为每类的代表点;,按密度大小选代表点：,以每个样本作为球心，以,d,为半径做球形;落在球内的样本数称为该点的密度，并按密度大小排序。首先选密度最大的作为第一个代表点，即第一个聚类中心。再考虑第二大密度点，若第二大密度点距第一代表点的距离大于,d,1,（,人为规定的正数）则把第二大密度点作为第二代表点，否则不能作为代表点，这样按密度大小考察下去，所选代表点间的距离都大于,d,1,。d,1,太小，代表点太多，,d,1,太大，代表点太小，一般选,d,1,2d。,对代表点内的密度一般要求大于,T。T0,为规定的一个正数。,用前,k,个样本点作为代表点。,三、初始分类和调整,选一批代表点后，代表点就是聚类中心，计算其它样本到聚类中心的距离，把所有样本归于最近的聚类中心点，形成初始分类，再重新计算各聚类中心，称为成批处理法。,选一批代表点后,依次计算其它样本的归类，当计算完第一个样本时，把它归于最近的一类，形成新的分类。再计算新的聚类中心，再计算第二个样本到新的聚类中心的距离，对第二个样本归类。即每个样本的归类都改变一次聚类中心。此法称为逐个处理法。,直接用样本进行初始分类，先规定距离,d,把第一个样品作为第一类的聚类中心，考察第二个样本，若第二个样本距第一个聚类中心距离小于,d，,就把第二个样本归于第一类，否则第二个样本就成为第二类的聚类中心，再考虑其它样本，根据样本到聚类中心距离大于还是小于,d，,决定分裂还是合并。,最佳初始分类。,如图所示，随着初始分类,k,的增大，准则函数下降很快，经过拐点,A,后，下降速度减慢。拐点,A,就是最佳初始分类。,四、,C,平均算法,例：已知有20个样本，每个样本有2个特征，数据分布如下图,第一步：令,C=2，,选初始聚类中心为,样本序号,x,1,x,2,x,3,x,4,x,5,x,6,x,7,x,8,x,9,x,10,特征,x,1,0,1,0,1,2,1,2,3,6,7,特征,x,2,0,0,1,1,1,2,2,2,6,6,x,11,x,12,x,13,x,14,x,15,x,16,x,17,x,18,x,19,x,20,8,6,7,8,9,7,8,9,8,9,6,7,7,7,7,8,8,8,9,9,第三步：根据新分成的两类建立新的聚类中心,第四步：,转第二步。,第二步：重新计算 到,z,1,(2),z,2,(2),的距离，把它们归为最近聚类中心，重新分为两类，,第三步，更新聚类中心,第四步，,第二步，,第三步，更新聚类中心,迭代自组织数据分析算法（,ISOData,）,方法步骤,（,1,）任选初始值（中心），,C,个,（,2,）将,N,个样本分到,C,类中,（,3,）计算距离：,（,4,）要求对中心分裂，合并,新的中心,（,5,）判断。,上机作业,已知,50,个样本（随机产生），每个样本2个特征（取值在,0,10,），数据如下：,用,c,平均算法和,ISODATA,算法分类，编程上机，并画出分类图。,样本序号,1 2 3 4 5 6 7 8 9 10,x,1,0 1 2 4 5 5 6 1 1 1,x,2,0 1 1 3 3 4 5 4 5 6,