搜索
第2章聚类分析及其应用实例2.1聚类分析简介聚类分析是根据“物以类聚”的道理，对样品或指标进行分类的一种多元统计分析方法，它们讨论的对象是大量的样品，要求能合理地按各自的特性來进行合理的分类，没有任何模式可供参考或依循，即是在没有先验知识的情况下进行的[']。聚类分析方法有很多，按不同的分类方式，有不同的分类。按聚类方法的不同可分为以下几种：(1)系统聚类法：对所在的指标进行分类，每一次将最相似的两个数据合并成一类，合并之后和其他数据的距离会重新计算，这个步骤会不断重复下去直至所有指标合并成一类，并类的过程可用一张谱系聚类图描述.(2)调优法（动态聚类法）：所谓调优法，从表面意思就可以看出是在对n个对象初步分类后，根据分类后的信息损失尽可能小的原则对分类进行择优调整，直到分类合理为止.(3)有序样品聚类法：在很多实际问题中，所谓的样品都是相互独立的个体，因此可以平等的划分。但是有序样品聚类法的存在就是因为在另外一些实际问题中，样品之间是存在着某种联系而在分类中是不允许打乱顺序的。有序样品聚类法开始时将所有样品归为一类，然后根据某种分类准则将其分为二类等等，一直往下分类下去直至满足分类要求。它的思想正好与系统聚类法的相反。(4)模糊聚类法：利用模糊聚集理论来处理分类问题，它对经济领域中具有模糊特征的两态数据或多态数据具有明显的分类效果.(5)图论聚类法：在处理分类问题中独创性的引入了图论中最小支撑树的概念。(6)聚类预报法：顾名思义，就是用聚类分析的方法来在各个领域中进行预报。在多元统计分析中，判别分析、回归分析等方法都可以用来做预报，但是在一些异常数据面前，这些方法做的预报都不是很准确，方法也不好准确的实施，而聚类预报则很好的解决了这一点。可以预见，聚类预报法经过更深入的研究后，一定会得到更加广泛的应用。按聚类对象的不同，聚类分析可分为2型[对样品（CASES)聚类]与型[对变量（VARIABLE)聚类]，两种聚类在方法和步骤上都基本相同.2.2聚类分析方法介绍数学方法在实际应用中是否受欢迎，最主要的一点就是它能不能适用于大型6第2章聚类分析及.11；应用实例计算的问题。图论聚类法、基于等价关系的聚类方法和谱系聚类法在大型问题中难以快速有效处理数据而应用甚少。基于目标函数的聚类方法因其设计简单，在实际生活中被广泛运用，其主要思想是将问题转换为带约束条件的非线性优化，这样就可以运用完备的线性最优化知识解决问题，而且这种方法也易于在计算机上实现。而伴随着计算机技术的突飞猛进，基于目标函数的聚类方法必定会成为研究的热点。2.2.1谱系聚类方法在待分析样本数较小时，通常采用谱系聚类方法（系统聚类法）。谱系聚类法是按距离准则来对样本进行分类的，例如我们要将样本集X中的《个样本划分为C类。那么算法的实现过程如下：首先令这^个样本各自为一个类，此时，总的类数为《;其次，计算这/7个类别之间的相互距离，合并距离最小的两个样本，这样总得分类数就只有个；然后计算新形成的个类别之间的距离，同样合并最小的两个类，使类别减少为n-2个，依此原则，继续合并；最后，当总的类别只剩下C类时，停止计算，分类结束，此时的C类就是聚类的结果。需要注意的是，在此过程中，计算类与类之间的距离的方法有很多种，具体选择什么方法，需要视具体情况而定。计算类间距离的方法，后续也会有比较详细的介绍。根据上述聚类原则，我们很快可以知道，对于样本集里的任意两个样本X々和Xj’它们总是可以聚类到一个类别中去。“上述所介绍的，只是谱系聚类算法中的一种，这种算法一般称为聚集法，它比较适合于类别比较多的时候，当类别较少时，用此种方法就显得计算量非常的大，使得分类效率不高；另一种谱系聚类算法叫做分裂法，它与聚集法初始时将所有样本卑独分成一类刚好相反，它是将所有样本当成一类，然后在将某些样本分离出去，形成其他的类别，这样就节省了相当一部分的计算量。在实际运用中，具体选择哪种方法来聚类就得以具体情况为准。上述算法中的分类仅仅依靠样本间的距离或者类间距离，因而，距离的计算决定了分类结果。距离的计算种类有：闽可夫斯基距离（包括街区距离、欧氏距离和切比雪夫距离等），也可以选择马氏距离、角度相似性函数或者Taniraoto测度。其中马氏距离定义DI=-m)'C~'-m)(2—1)这里X为模式向量，w为均值向量，C为模式总体的协方差矩阵.马氏距离的优点k是排除了模式样本之间的相关性影响.比如，我们取一个模式特征向量，可能有九7第2章聚类分析及用实例如果B类是由E和F两类合并而成的，则有2.最长距离法[9】与上述相似，两个聚类A和B间的最长距离定义为=max{i/Jaee5}(2—5)同样地，如果B类是由E和F两类合并而成的，贝max3.中间距离法[9]如果B类是由E和F两类合并而成的，则A类和B类之间的距离为(2-6)它介于最长距离和最短距离之间.4.重心法上述定义的类间距离没有考虑每一类中包含的样本数目，如果E类中有个样本，F类中有个样本，则E和F两类合并后共有+?,.个样本.用”）fP'//工、代替中_距离、法中的系数，即得：重心、法的类与类之间的距离递推公/l?A-+?/■■；式为D,.?(2-7)Vn,+n,n,+n,(?/:.+?,)—5.类平均距离法[9]如果采用类间所有距离的平均距离，则有Da,B=Yj^Ih(2-8)VoA,heB不难得到类平均距离的递推公式为D,、b=(2-9)V?//+n「n,,.+n,,-由于定义类间距离的方法不同，使分类结果不太一致.实际问题中常用几种不同地方法进行计算，比较其分类结果，选择一个比较切合实际的分类.对于上述五种定义类间距离的方法，可采用统一的递推公式：~^E^AJi+^F^AJ'七PD丨“1:+7\D^J；-（2-10)由此，我们可以得到五种类间距离递推公式中的权系数，如表1所示，其中9第2章聚类分析及ji；应用实例n,^n,+n,,即B类样本数目是E和F类样本的合并。表2-1统一类间距离递推公式中的权系数Table2-1TheWeightCoefficientinTheRecurrenceFormulaofDistanceBetweentheUnifiedClass方法a、:a,,.P7空间性质最短距离法0.50.50-0.5HI缩最长距离法0.50.500.5扩张类间平均距离法nJriB?/.//}00保持重心法《/;/??-n,:/1,,/nl0保持中间距离法0.50.5-0.250^2.2.2基于等价关系的聚类方法由离散数学中关于关系的描述我们知道，定义在集合Z=^[;c,，x,,上的关系如果具有自反性、对称性和传递性则被称为等价关系.设义是一给定集合，尤…，是它的子集，如果满足[9】：X!nXj二(j)，V/,7=1,2,?;，/半jX^yjX^Kj^--KjX^=X则集合尸=,,…，X」被称为集合的一个划分，而，被叫做这个划分的块.若是集合上的等价关系，对于任意一个元素X,可以构造一个X的子集，叫做X,对于的等价类，[x,],,=eX,Kx.RXj\.对于这种集合，它具有下列性质：(1)x,e[x丄；(2)如果Xye[x,\，则必有[xy.=[x,L；(3)若X广[x^L，但?生V.L，则必有k]r。L=.由此可知，集合Z上的等价关系7?所构成的类，两两互不相交，而且覆盖整个集合JT.我们得到如下定理：集合X上的等价关系R所构成的类产生集合X的10个分量是反映同一特征A，而只有一个分量反映另一特征B，欧氏距离计算出來的结果将绝大部分反应特征A，而弱化了特征B，而马氏距离去除了相关性后，据规避了这个缺点。通过式（2.1)我们可以看出，当C为对角阵时，各特征分量相互独立，同时，我们还发现，欧氏距离其实就是协方差矩阵C等于单位矩阵I时的一个特例。可以看出，在这种条件下模式样本集的概率分布不仅各分量之间不相关，而且其密度函数的等高线为圆（或者超球面），即各分量方向上的密度分布是均匀的需要指出的是，计算协方差矩阵是计算马氏距离的关键所在，但是我们只有在模式集给定的情况下，才能计算出协方差矩阵，遗憾的是这个条件很难实现。角度相似性函数定义为‘士^^(2-2)是模式向量;C与X之间的夹角余弦，也就是X的单位向量II与X的单位向量*‘‘/IW‘II之间的点积.夹角余弦的测度反映了几何上相似形的特征，它对于坐标系的/KII旋转及缩放时不变的，但对位移和一般的线性变换则并不具有不变性的性质.Tanimoto测度是将夹角余弦度量进行细小的修改后得到的，主要用于具有{0，1}二值特性的情况[”。其具体定义为共有的特征数目，xlx,=；Cf或；Cj.中占有的特征数目之总数一不过，相似性测度函数的共同点都涉及到把两个相比较的向量X和X的分量kj值组合起来，但怎样组合并无普遍有效的方法，对于具体的模式分类，需视情况作适当的选择[8]。在谱系聚类算法中，每次迭代中形成的聚类之间以及它们与各个样本之间的距离，有多种不同的准则函数[7]。1.最短距离法[9]假设A和B是两个聚类，则两类间的最短距离定义为j|aeA,beb](2—4)式中，（力表示A类中的样本X。和B类中的样本之间的距离.表示A类中所有样本与B类中所有样本之间的最小距离.8第2章聚类分析及其应用实例￡(?-^j)?=I广'n.(2-14)Jpr叫pr又J这里，七=—XX.i，■^J~~X^A.Sk=\S4.指数相似系数5r.=—文e'si(2-15)Sk^\这里，是第A个特征的方差，=-^(?‘k=\’2,…，S(2-16)“M5.最大最小法^min(x?,x^Jr,(2-17)Jmax(x?,x^J/c=l6.算术平均最小法Emm(x?,x^Jr?=^(2—18)Zk=\7.算术平均最小法Emin(x?,x^Jr,丨-(2-19)舍t(?+?）L人--18.几何平均最小法Emin(x,,,x^Jr,=^(2-20)ys^^k=\9.绝对值指数法12笫2苹聚类分析及K:应用实例一个划分，此划分叫做Z关于的商集，记做例如，同余关系i?‘对整数集/产生的商集就是模C的剩余类[9]:///?,={[0],,.,[lL,..,[c-4.}由上述讨论可知，在给定集合Z上定义一个等价关系，就决定集合;r的一种划分.显然，这样的划分是硬分割，我们可以把这一概念推广到模糊关系上来[9]。由于模糊等价关系及是论域与自己笛卡尔乘积jxl上的一个模糊集合，而模糊集合的任何a(0SaS1)截集及?都是XXX上的一个普通集合，即为X上的普通等价关系，也就得到了关于X中对象元素的一种分类.当《由1下降为0时，所得到的分类由粗变细，逐渐归并，从而形成一个动态的聚类谱系图.由此可见，分类对象集Z上的模糊等价关系的建立是这种聚类分析方法中的一个关键性的环节[9]。为了建立分类对象集合X上的模糊等价关系瓦，通常需要首先计算各个分类对象之间的相似性统计量，建立分类对象集合I上的模糊相似关系=k]，?、LIJJfjxn0r,1,i,j=AV表示分类对象\与\的相似程度.常用的计算分类对象的相似性统计量的方法有如下几种[9]。1.夹角余弦法■S广’J=广'.(2-11)Vk=\k=\2.数量积法'1i=jr,j=‘1(2-12)MtlI*]这里，M是一个适当选取的正数，并且满足Mmax|^X丨k(2-13)3.相关系数法11笫2苹聚类分析及;用实例即合成的传递闭包：巧==充。瓦.，R:=R^or；,……这样下去，就必然存在一个自然数I使得巧*=R'。紀?这时，^便是一个模糊等价关系了.在此基础上，我们就可以利用不同水平下的截集得到该水平上的聚类结果，所有不同水平的聚类结果形成聚类的谱系图[9]。2.2.3图论聚类方法图论聚类方法最早是由Zahn提出来的，又称作最大（小）支撑树聚类算法.后来经过人们加以改造从而可以实现模糊聚类分析.图G中一条长度为尺的路径(Path)P是一系列连接的结点，P=〈x,，X2，.,Xa.+,〉，其中对V/e(0,Ar),(x,,x,+|)eE；如果图G中没有一条非零长度的路径P=,且X,=Xh,，