第二章聚类分析.

第二章聚类分析(ClusteringAnalysis)2.1聚类分析的概念2.2模式相似性测度2.3类的定义与类间距离2.4聚类的算法2.1聚类分析的概念一、聚类分析的基本思想★相似的归为一类。★模式相似性的度量和聚类算法。★无监督分类（Unsupervised）。二、特征量的类型★物理量----(重量、长度、速度)★次序量----(等级、技能、学识)★名义量----(性别、状态、种类)第二章聚类分析三、方法的有效性取决于分类算法和特征点分布情况的匹配。2.1聚类分析的概念2w2W1w1W2x1xb分类无效时的情况1.特征选取不当使分类无效。第二章聚类分析三、方法的有效性取决于分类算法和特征点分布情况的匹配。2.1聚类分析的概念分类无效时的情况2.特征选取不足可能使不同类别的模式判为一类。2w2W1w1W2x1x3w3W第二章聚类分析三、方法的有效性取决于分类算法和特征点分布情况的匹配。2.1聚类分析的概念分类无效时的情况3.特征选取过多可能无益反而有害,增加分析负担并使分析效果变差。2w2W1w1W2x1xb第二章聚类分析三、方法的有效性取决于分类算法和特征点分布情况的匹配。2.1聚类分析的概念分类无效时的情况4.量纲选取不当。第二章聚类分析三、方法的有效性取决于分类算法和特征点分布情况的匹配。2.1聚类分析的概念分类无效时的情况4.量纲选取不当。第二章聚类分析三、方法的有效性取决于分类算法和特征点分布情况的匹配。2.1聚类分析的概念分类无效时的情况4.量纲选取不当。第二章聚类分析下列是一些动物的名称：羊（sheep）狗（dog）蓝鲨（blueshark）蜥蜴（lizard）毒蛇（viper）猫（cat）麻雀（sparrow）海鸥（seagull）金鱼（goldfish）绯鲵鲣（red-mullet）蛙（frog）要对这些动物进行分类，则不同的特征有不同的分法：特征选取不同对聚类结果的影响第二章聚类分析特征选取不同对聚类结果的影响羊,狗,猫蓝鲨蜥蜴,毒蛇,麻雀,海鸥,金鱼,绯鲵鲣,青蛙(a)按繁衍后代的方式分哺乳动物非哺乳动物第二章聚类分析金鱼绯鲵鲣蓝鲨羊,狗,猫蜥蜴,毒蛇麻雀,海鸥青蛙(b)按肺是否存在分无肺有肺特征选取不同对聚类结果的影响第二章聚类分析青蛙羊,狗,猫蜥蜴,毒蛇麻雀,海鸥金鱼绯鲵鲣蓝鲨(c)按生活环境分陆地水里两栖特征选取不同对聚类结果的影响第二章聚类分析蓝鲨金鱼绯鲵鲣蜥蜴,毒蛇麻雀,海鸥青蛙羊,狗,猫(d)按繁衍后代方式和肺是否存在分非哺乳且有肺哺乳且无肺哺乳且有肺非哺乳且无肺特征选取不同对聚类结果的影响第二章聚类分析距离测度不同,聚类结果也不同数据的粗聚类是两类,细聚类为4类第二章聚类分析综上可见:选择什么特征？选择多少个特征？选择什么样的量纲？选择什么样的距离测度？这些对分类结果都会产生极大影响。第二章聚类分析聚类应用的四个基本方向一、减少数据许多时候，当数据量N很大时，会使数据处理变得很费力。因此可使用聚类分析的方法将数据分成几组可判断的聚类m（mN）来处理，每一个类可当作独立实体来对待。从这个角度看，数据被压缩了。第二章聚类分析二、假说生成在这种情况下，为了推导出数据性质的一些假说，对数据集进行聚类分析。因此，这里使用聚类作为建立假说的方法，然后用其他数据集验证这些假说。聚类应用的四个基本方向第二章聚类分析聚类应用的四个基本方向三、假说检验用聚类分析来验证指定假说的有效性。例如：考虑这样的假说“大公司在海外投资”。要验证这个假说是否正确，就要对大公司和有代表性的公司按规模、海外活跃度、成功完成项目的能力等进行聚类分析。从而来支持这个假说。第二章聚类分析四、基于分组的预测对现有数据进行聚类分析，形成模式的特征，并用特征表示聚类，接下来，对于一个未知模式，就可以用前面的聚类来确定是哪一类？聚类应用的四个基本方向例如：考虑被同种疾病感染的病人数据集。先按聚类分析进行分类，然后对新的病人确定他适合的聚类，从而判断他病情。第二章聚类分析2.2模式相似性测度用于描述各模式之间特征的相似程度●距离测度●相似测度●匹配测度第二章聚类分析2.2模式相似性测度一、距离测度(差值测度)测度基础：两个矢量矢端的距离测度数值：两矢量各相应分量之差的函数。时，等号成立；0),(yxd⑴，当且仅当xy),(),(xydyxd⑵),(),(),(yzdzxdyxd⑶第二章聚类分析2.2模式相似性测度常用的距离测度有：1.欧氏(Euclidean)距离第二章聚类分析2.2模式相似性测度4.明氏(Minkowski)距离(2-2-4)2.绝对值距离(街坊距离或Manhattan距离)(2-2-2)3.切氏(Chebyshev)距离(2-2-3)第二章聚类分析2.2模式相似性测度第二章聚类分析随机矢量的自协方差矩阵表征各分量围绕其均值的散布情况及各分量间的相关关系，其定义为：X'E[()()]XXXX2()()'()d()nijnnXxxpxx2.2模式相似性测度5.马氏(Mahalanobis)距离注意！马氏距离对一切非奇异线性变换都是不变的，这说明它不受特征量纲选择的影响，并且是平移不变的。上面的V的含义是这个矢量集的协方差阵的统计量，故马氏距离加入了对特征的相关性的考虑。第二章聚类分析行列式02.2模式相似性测度第二章聚类分析Cholesky分解2.2模式相似性测度二、相似测度测度基础：以两矢量的方向是否相近作为考虑的基础,矢量长度并不不重要。设1.角度相似系数(夹角余弦)(2-2-11)注意：坐标系的旋转和尺度的缩放是不变的,但对一般的线形变换和坐标系的平移不具有不变性。2.2模式相似性测度二、相似测度2.相关系数它实际上是数据中心化后的矢量夹角余弦。(2-2-12)21)())(()()()(),(yyyyxxxxyyxxyxr2.2模式相似性测度二、相似测度3.指数相似系数(2-2-13)niiiiyxnyxe122)(43exp1),(式中为相应分量的协方差，为矢量维数。它不受量纲变化的影响。2in2·3类的定义与类间距离2.3.1类的定义定义之1设集合S中任意元素xi与yj间的距离dij有dijh其中h为给定的阀值，称S对于阀值h组成一类。类的定义有很多种，类的划分具有人为规定性，这反映在定义的选取及参数的选择上。一个分类结果的优劣最后只能根据实际来评价。书中的其它定义方法请大家自行参考学习讨论（续）距离阈值T对聚类结果的影响2·3类的定义与类间距离2.3.2类间距离测度方法⑴最近距离法⑵最远距离法⑶中间距离法⑷重心距离法⑸平均距离法⑹离差平方和法2·3类的定义与类间距离2.3.2类间距离测度方法⑴最近距离法⑵最远距离法⑶中间距离法⑷重心距离法⑸平均距离法⑹离差平方和法式中表示和之间的距离。ijjikldD,minijdkixwljxw2·3类的定义与类间距离2.3.2类间距离测度方法⑴最近距离法⑵最远距离法⑶中间距离法⑷重心距离法⑸平均距离法⑹离差平方和法式中表示和之间的距离。ijdkixwljxwijjikldD,max2·3类的定义与类间距离2.3.2类间距离测度方法⑴最近距离法⑵最远距离法⑶中间距离法⑷重心距离法⑸平均距离法⑹离差平方和法pwqwkwpqkpqDkqDklDkpDlwpqkqkpklDDDD2222412121qplwwwpwqwkwpqkpqDkqDklDkpDpqkqkpklDDDD2222412121qplwwwpwqwkwpqkpqDkqDklDkpDpqkqkpklDDDD2222412121qplwww2·3类的定义与类间距离2.3.2类间距离测度方法⑴最近距离法⑵最远距离法⑶中间距离法⑷重心距离法⑸平均距离法⑹离差平方和法22222)(pqqpqpkqqpqkpqppklDnnnnDnnnDnnnDnp,nq分别为类wp和wq的样本个数22222)(pqqpqpkqqpqkpqppklDnnnnDnnnDnnnD2·3类的定义与类间距离2.3.2类间距离测度方法⑴最近距离法⑵最远距离法⑶中间距离法⑷重心距离法⑸平均距离法⑹离差平方和法wwqjpixxijqppqdnnD2212·3类的定义与类间距离2.3.2类间距离测度方法⑴最近距离法⑵最远距离法⑶中间距离法⑷重心距离法⑸平均距离法⑹离差平方和法wtixtititxxxxs)()(qplwwwqplpqsssD2)()(2qpqpqpqppqxxxxnnnnDtxpxqx分别为对应类的重心类内离差平方和2222pqlkkkqlkqkkplkpkklDnnnDnnnnDnnnnD递推公式为:2·3类的定义与类间距离2.3.3聚类的准则函数判别分类结果好坏的一般标准：类内距离小，类间距离大。某些算法需要一个能对分类过程或分类结果的优劣进行评估的准则函数。如果聚类准则函数选择得好，聚类质量就会高。聚类准则往往是和类的定义有关的，是类的定义的某种体现。2.3.3聚类的准则函数一、类内距离准则设有待分类的模式集在某种相似性测度基础上被划分为类，类内距离准则函数定义为:(表示类的模式均值矢量。)Nxxx,,,21cjjinicjx,,2,1;,,2,1)(；WJcjnijjiWjmxJ112)((2-3-20)2·3类的定义与类间距离jmjw2·3类的定义与类间距离2·3类的定义与类间距离2·4聚类的算法2.4.1聚类的技术方案聚类分析有很多具体的算法,有的比较简单,有的相对复杂和完善,但归纳起来就是三大类:1、按最小距离原则简单聚类方法2、按最小距离原则进行两类合并的方法3、依据准则函数动态聚类方法2·4聚类的算法(1)简单聚类方法针对具体问题确定相似性阈值，将模式到各聚类中心间的距离与阈值比较，当大于阈值时该模式就作为另一类的类心，小于阈值时按最小距离原则将其分划到某一类中。这类算法运行中模式的类别及类的中心一旦确定将不会改变。2·4聚类的算法首先视各模式自成一类,然后将距离最小的两类合并成一类,不断地重复这个过程，直到成为两类为止。(2)按最小距离原则进行两类合并的方法这类算法运行中，类心不断地修正，但模式类别一旦指定后就不再改变，就是模式一旦划为一类后就不再被分划开，这类算法也称为谱系聚类法。2·4聚类的算法(3)依据准则函数动态聚类法设定一些分类的控制参数，定义一个能表征聚类结果优劣的准则函数，聚类过程就是使准则函数取极值的优化过程。算法运行中，类心不断地修正，各模式的类别的指定也不断地更改。这类方法有—C均值法、ISODATA法等。2·4聚类的算法--简单聚类方法2·4聚类的算法--简单聚类方法2·4聚类的算法--简单聚类方法X轴Y轴Z1T=212345910768112·4聚类的算法--简单聚类方法简单聚类图例X轴Y轴Z1T=2X轴Y轴Z1T=2例2.4.1：初始条件不同的简单聚类结果初始中心不同X轴Y轴Z1T=4门限不同X轴Y轴Z1T=2样本顺序不同12345123451234512345109810988768761167116791011910112·4聚类的算法--简单聚类方法这类算法的突出优点是算法简单。但聚类过程中，类的中心一旦确定将不会改变，模式一旦指定类后也不再改变。算法特点:该算法结果很大程度上依赖于距离门限T的选取及模式参与分类的次序。2·4聚类的算法—最大最小距离法⒊算法原理步骤11xz⑴选任一模式特征矢量作为第一个聚类中心1z例如，。1z作为第二个聚类中心2z。⑵从待分类矢量集中选距离最远的特征矢量2·4聚类的算法—最大最小距离法⑶计算未被作为聚类中心的各模式特征矢量ix与1z、2z之间的距离，并求出它