一个简单的距离度量，如Euclidean距离，经常被用作反映不同数据间的相异性，一些有关相似性的度量，例如PMC和SMC，能够被用来特征化不同数据的概念相似性，在图像聚类上，子图图像的误差更正能够被用来衡量两个图形的相似性。
将数据对象分到不同的类中是一个很重要的步骤，数据基于不同的方法被分到不同的类中，划分方法和层次方法是聚类分析的两个主要方法，划分方法一般从初始划分和最优化一个聚类标准开始。Crisp Clustering，它的每一个数据都属于单独的类；Fuzzy Clustering，它的每个数据可能在任何一个类中，Crisp Clustering和Fuzzy Clusterin是划分方法的两个主要技术，划分方法聚类是基于某个标准产生一个嵌套的划分系列，它可以度量不同类之间的相似性或一个类的可分离性用来合并和分裂类，其他的聚类方法还包括基于密度的聚类，基于模型的聚类，基于网格的聚类。
评估聚类结果的质量是另一个重要的阶段，聚类是一个无管理的程序，也没有客观的标准来评价聚类结果，它是通过一个类有效索引来评价，一般来说，几何性质，包括类间的分离和类内部的耦合，一般都用来评价聚类结果的质量，类有效索引在决定类的数目时经常扮演了一个重要角色，类有效索引的最佳值被期望从真实的类数目中获取，一个通常的决定类数目的方法是选择一个特定的类有效索引的最佳值，这个索引能否真实的得出类的数目是判断该索引是否有效的标准，很多已经存在的标准对于相互分离的类数据集合都能得出很好的结果，但是对于复杂的数据集，却通常行不通，例如，对于交叠类的集合。
四）聚类分析的计算方法： 1、划分法(partitioning methods)：给定一个有N个元组或者纪录的数据集，分裂法将构造K个分组，每一个分组就代表一个聚类，K 录的个数无关的，它只与把数据空间分为多少个单元有关。代表算法有：STING算法、CLIQUE算法、WAVE-CLUSTER算法； 5、基于模型的方法(model-based methods):基于模型的方法给每一个聚类假定一个模型，然后去寻找能个很好的满足这个模型的数据集。这样一个模型可能是数据点在空间中的密度分布函数或者其它。它的一个潜在的假定就是：目标数据集是由一系列的概率分布所决定的。通常有两种尝试方向：统计的方案和神经网络的方案。 具体的有： 1、K-MEANS算法 k-means 算法接受输入量 k ；然后将n个数据对象划分为 k个聚类以便使得所获得的聚类满足：同一聚类中的对象相似度较高；而不同聚类中的对象相似度较小。聚类相似度是利用各聚类中对象的均值所获得一个“中心对象”（引力中心）来进行计算的。 k-means 算法的工作过程说明如下：首先从n个数据对象任意选择 k 个对象作为初始聚类中心；而对于所剩下其它对象，则根据它们与这些聚类中心的相似度（距离），分别将它们分配给与其最相似的（聚类中心所代表的）聚类；然后再计算每个所获新聚类的聚类中心（该聚类中所有对象的均值）；不断重复这一过程直到标准测度函数开始收敛为止。一般都采用均方差作为标准测度函数. k个聚类具有以下特点：各聚类本身尽可能的紧凑，而各聚类之间尽可能的分开。 2、K-MEDOIDS算法 K-MEANS有其缺点：产生类的大小相差不会很大，对于脏数据很敏感。 改进的算法：k—medoids 方法。这儿选取一个对象叫做mediod来代替上面的中心的作用，这样的一个medoid就标识了这个类。步骤： （1）、任意选取K个对象作为medoids（O1,O2,?Oi?Ok）。 以下是循环的： （2）、将余下的对象分到各个类中去（根据与medoid最相近的原则）； （3）、对于每个类（Oi）中，顺序选取一个Or，计算用Or代替Oi后的消耗—E（Or）。选择E最小的那个Or来代替Oi。这样K个medoids就改变了，下面就再转到2。 （4）、这样循环直到K个medoids固定下来。 这种算法对于脏数据和异常数据不敏感，但计算量显然要比K均值要大，一般只适合小数据量。 3、Clara算法 上面提到K-medoids算法不适合于大数据量的计算。现在介绍Clara算法，这是一种基于采用的方法，它能够处理大量的数据。 Clara算法的思想就是用实际数据的抽样来代替整个数据，然后再在这些抽样的数据上利用K-medoids算法得到最佳的medoids。Clara算法从实际数据中抽取多个采样，在每个采样上都用K-medoids算法得到相应的（O1,O2?Oi?Ok），然后在这当中选取E最小的一个作为最终的结果。 4、Clarans算法 Clara算法的效率取决于采样的大小，一般不太可能得到最佳的结果。 在Clara算法的基础上，又提出了Clarans的算法，与Clara算法不同的是：在Clara算法寻找最佳的medoids的过程中，采样都是不变的。而Clarans 算法在每一次循环的过程中所采用的采样都是不一样的。与上次课所讲的寻找最佳medoids的过程不同的是，必须人为地来限定循环的次数。 模糊聚类分析方法 聚类分析方法形成思路 变量的数据预处理 分类前，对原始数据进行预处理，使其所有变量尺度均匀化。方法有以下几种： 变量的标准化 设有n个样品，m个特征变量，设第i个样品，第j个变量的观测值为xij(i?1,2,?,n;j?1,2,?,m)，由此可构成一个n?m阶矩阵为 ?x11?x21??????xn1x12x22?xn2????x1m??x2m? （1） ???xnm?X?(xij)n?m将式（1）中每个变量xij根据以下公式变换，称为标准化。 对每个变量的标准化计算公式为 ??xijxij?xjSjSj?[1nij(i?1,2,?,n)(j?1,2,?,m)(x?ni?1 （2） 式中，xj?1nijx?ni?1?xj)]21/2 标准化后变量的平均值为0，标准离差为1。 变量的正规化 对每个变量施行以下变换，称为正规化。 ??xijxij?xj(min)xj(max)?xj(min)(i?1,2,?,n)(j?1,2,?,m) （3） ??1。式中，xj(max)和xj(min)分别为第j个变量的最大值和最小值。显然，0?xij 变量的规格化 对每个变量施行以下变换，称为规格化。 ??xijxijxj(max)(i?1,2,?,n)(j?1,2,?,m) （4） ??1。 式中，，xj(max)为第j个变量的最大值。显然，0?xij注：数据的预处理以不丢失原有信息为前提。三种预处理方法的选择应根据现有 数据的特点来考虑。 分类统计量的确定及其聚类方法的选择 分类统计量的确定 一般是把相似程度大的并成一类，把相似程度小的分为不同的类，因此要定量地表示样品间的相似程度。设论域U?{x1,x2,?,xn}，xi?{xi1,xi2,?,xim}(i?1,2,?,n)，即数据矩阵为 A??xij?n?m，如果xi与xj的相似程度为rij?R(xi,xj)(i,j?1,2,?,n)，则称之为相似系 ~数，确定相似系数rij有多种不同的方法。常用的方法如下： (1) 数量积法 对 于 xi?{xi1,xi2,?,xim}?U，令 ?m?M?max??xik?xjk?i?j?k?1?，则取 i?j?1,rij?1?m?，显然rij?[0,1]。若出现有某些rij?0，可令rij?，rij??1x?x,i?j2jk?M?ikk?1?则有rij??[0,1]。也可以用平移-极差变换将其压缩到[0,1]上，即可以得到模糊相 似矩阵R??rij?n?m。 (2) 夹角余弦法（相似系数统计量）: 令 m?xrij?k?1m2ikk?1ikxjkm2jk(i,j?1,2,?,n) ?x??xk?1则R??rij?n?n。 (3) 相关系数法（相关系数统计量）: 令 m??xrij?k?1ik?xi??xjk?xj???xk?1mik?xi????x2k?1m(i,j?1,2,?,n) jk?xj?2其中xi?x，x?mikk?11mj?x，则R??rij?。 ?n?nmjkk?11m注意：xi?{xi1,xi2,?,xim}中的样本xik属于同一个样本空间Xi(k?1,2,?,m)。 (4) 指数相似系数法: 令 2??3(xik?xjk)??rij??exp??? 2mk?1sk???4?1m其中sk?1?x?ni?1nik?xk?2,xk?1nikx?ni?1(k?1,2,?,m)。则R?rij??n?n。 注意：xi?{xi1,xi2,?,xim}中的样本xik属于不同的样本空间Xk，即 xik?Xk(k?1,2,?,m)。 (5) 最大最小值法: 令 ??xrij?k?1mik?xjk?xjk???xk?1mik?(xij?0;i,j?1,2,?,n) 则R??rij?n?n。 (6) 算术平均值法: 令 ??xrij?k?1mik?xjk?1?x?2k?1mik?xjk?(xij?0;i,j?1,2,?,n) 则R??rij?n?n。 (7) 几何平均值法：令 ??xrij?k?1mmik?xjk?(xij?0;i,j?1,2,?,n) ?则R??rij?n?n。 k?1xik?xjk(8) 绝对值倒数法：令 i?j?1,??1rij???m??M??xik?xjk?,i?j???k?1 其中M为使得所有rij?[0,1](i,j?1,2,?,n)的确定常数，则R??rij?n?n。 (9) 绝对值指数法：令 ?mrij?exp???xik?xjk?k?1??(i,j?1,2,?,n) ?则R??rij?n?n。 (10) 海明距离法（距离系数统计量。如果变量的量纲不同，原始数据变异范围相差悬殊时，建议首先进行数据的标准化处理，然后再计算距离）：令 ?rij?1?H?d(xi,xj)?m(i,j?1,2,?,n) ??d(xi,xj)??xik?xjkk?1?其中H为使得所有rij?[0,1](i,j?1,2,?,n)的确定常数。则R?rij??n?n。 (11) 欧氏距离法（最常用）：令 ?rij?1?E?d(xi,xj)?m(i,j?1,2,?,n) ?2?d(xi,xj)???xik?xjk?k?1?其中E为使得所有rij?[0,1](i,j?1,2,?,n)的确定常数。则R?rij??n?n。 (12) 契比雪夫距离法：令 ?rij?1?Q?d(xi,xj)?m??d(xi,xj)??xik?xjkk?1?(i,j?1,2,?,n) 其中Q为使得所有rij?[0,1](i,j?1,2,?,n)的确定常数。则R??rij?n?n。
数学建模方法大全
