模式识别第一章Clustering

第一章

聚类分析1.1聚类分析的相关概念1.2模式相似性的测度和聚类准则1.3基于试探的聚类搜索算法1.4分级（系统）聚类法1.5动态聚类法1.6聚类结果的评价（1）相似性和距离聚类：模式之间具有一定的相似性，这既表现在实物的显著特征上，也表现在经过抽象以后特征空间内的特征向量的分布状态上。一个样本的特征向量相当于特征空间中的一点，整个模式样本集合的特征向量可以看成特征空间的一些点，点之间的距离函数可以作为模式相似性的度量，并以此作为模式的分类依据。§1.1距离聚类的概念§1.1距离聚类的概念

定义对一批没有标出类别的模式样本集，按照样本之间的相似程度分类，相似的归为一类，不相似的归为另一类，这种分类称为聚类分析，也称为无监督分类。把整个模式样本集的特征向量看成是分布在特征空间中的一些点，点与点之间的距离即可作为模式相似性的测量依据。

聚类分析是按不同对象之间的差异，根据距离函数的规律（大小）进行模式分类的。§1.1距离聚类的概念

§1.1距离聚类的概念聚类分析的有效性

聚类分析方法是否有效，与模式特征向量的分布形式有很大关系。若向量点的分布是一群一群的，同一群样本密集（距离很近），不同群样本距离很远，则很容易聚类；若样本集的向量分布聚成一团，不同群的样本混在一起，则很难分类；对具体对象做聚类分析的关键是选取合适的特征。特征选取得好，向量分布容易区分，选取得不好，向量分布很难分开。§1.1距离聚类的概念

(2)特征分量个数（特征选择的维数）

如果特征空间的维数较多，也就是表征模式的特征向量的维数较多，也就是特征选取较多，这都会增加以距离作为聚类分类的工作量。因此我们在特征提取的过程中应该根据模式的具体特点，尽量合理的抽取较好反映模式典型的特征。

[降维方法]…….§1.1距离聚类的概念(3)特征的表示数值表示通常特征可用数值来表示，比如即便是性别特征是男和女，但是我们都可以用0和1来进行表示，如身份证号码的最后一个数。但是具体的对象，数字的取值要求不一样，如有的可以是连续的，身高、体重等。有的是分级量化的。如学分2分、3分等，有的是二值化的。如前面说的M、F。§1.1距离聚类的概念量纲选择对同一个分类样本总体来说，他们每个特征都应该采用同一个规则进行标识量化。同时特征反映了模式的某一个物理量，它与一定的单位量纲联系在一起的，量纲不同，会影响到数值的大小，如，说某人身高170cm，也可以说1.7m。在取值的时候要特别注意。

量纲对分类的影响（图例）§1.1距离聚类的概念两类模式分类的实例：一摊黑白围棋子选颜色作为特征进行分类，用“1”代表白，“0”代表黑，则很容易分类；选大小作为特征进行分类，则白子和黑子的特征相同，不能分类（把白子和黑子分开）。§1.2模式相似性的测度和聚类准则

1.2.1相似性的测度已知两个样本

Xi=(Xi1,Xi2,Xi3,…,Xin)T

Xj=(Xj1,Xj2,Xj3,…,Xjn)T（1）欧氏距离:表征了两个模式样本在特征空间中的欧几里得距离，需要特别注意的是Xi和Xj的量纲应该一致，如果用欧式距离作为判断多个样本之间的距离时候，更应该有一致的物理量纲，这样才有可比性。

当m＝2时，明氏距离就是欧氏距离，当m＝1时，就是街坊或绝对（cityblock)距离

（2）一般化的明氏距离切比雪夫距离

m趋向无穷大时明氏距离的极限情况（3）马氏距离它表征了模式向量X与其均值向量m之间的距离平方，C是模式总体的协方差，马氏距离将协方差考虑进来，排除了样本之间的相关性。当协方差为单位矩阵时，马氏距离和欧氏距离相同。马氏距离与欧氏距离相比，就中间多了一项。（4）角度相似性函数

表征了模式向量Xi、Xj之间夹角的余弦，反映了几何上的相似性，当坐标系旋转或者尺度变换（放大or缩小），Cij均保持不变，这有点类似我们中学学的相似三角形的特性。（关于坐标变换，如仿射变换，双线性变换，平方变换、双平方变换等请参见有关文献）x1x2x1x2x3（5）Tanimoto测度

其中x和z的分量用二值来表示，0表示不具有某种特征，1表示具有某种特征。(6)相关系数为xixj（类或者维）的均值1.2.2聚类准则的确定方法（1）

试探方法

依据经验选择测度和阈值来判别分类，并可以选择一定的训练样本来检验测度和阈值的可靠程度。 凭直观感觉，针对实际问题定义一种相似性测度的阈值，然后按最近邻规则指定某些模式样本属于某一个聚类类别。例如对欧氏距离，它反映了样本间的近邻性，但将一个样本分到不同类别中的哪一个时，还必须规定一个距离测度的阈值作为聚类的判别准则（2）聚类准则函数法依据：由于聚类是将样本进行分类以使类别间可分离性为最大，因此聚类准则应是反映类别间相似性或分离性的函数；由于类别是由一个个样本组成的，因此一般来说类别的可分离性和样本的可分离性是直接相关的；可以定义聚类准则函数为模式样本集(x)和模式类别(Sj,j=1,2,…,c)的函数，从而使聚类分析转化为寻找准则函数极值的最优化问题。§1.3基于试探的聚类搜索算法1.3.1按最邻近规则的简单试探法

1.3.2最大最小距离算法NOTE:在以后的算法中用于描述两个样本之间距离，如果没有特殊说明，都是指欧式距离。类与类之间的距离则具体指定。1.3.1按最邻近规则的试探法

1.3.1按最邻近规则的试探法讨论这种方法的优点：计算简单，若模式样本的集合分布的先验知识已知，则可获得较好的聚类结果。在实际中，对于高维模式样本很难获得准确的先验知识，因此只能选用不同的阈值和起始点来试探，因此这种方法缺点：依赖第一个聚类中心的位置，且类中心位置随机待分类模式样本的排列次序距离阈值T的大小样本分布的几何性质1.3.1按最邻近规则的试探法距离阈值T对聚类结果的影响1.3.2最大最小距离算法

基本思想：以试探类间欧氏距离为最大作为预选出聚类中心的条件。算法过程描述：先按照距离最小最大的方法预选出聚类中心，在按照按最邻近规则将模式分类到聚类中心。

以例子来说明具体步骤：

1.3.2最大最小距离算法[算法（实例）]x1x2x3x4x5x6x7x8x9x10x10x20x30x40x50x60x70x80x90x100x1(0,0);x2(3,8);x3(2,2);x4(1,1);x5(5,3);x6(4,8);x7(6,3);x8(5,4);x9(6,4);x10(7,5);算法性能分析：算法复杂度增加，在选聚类中心过程中消耗较大的资源。

这种方法缺点：依赖第一个聚类中心的位置，且类中心位置随机样本分布的几何性质§1.4系统聚类分类法

基本思想 将模式样本按距离准则逐步分类，类别由多到少，直到获得合适的分类要求为止。数据结构：进行聚类合并的一个关键就是每次迭代中形成的聚类之间以及它们和样本之间距离的计算，采用不同的距离函数会得到不同的计算结果。主要的距离计算准则：

最短距离、最长距离、中间距离、重心法、类平均距离等

§1.4系统聚类分类法(续)最短距离

DH、K＝H类中的所有样本与K类中所有样本之间最小的距离。最长距离DH、K＝H类中的所有样本与K类中所有样本之间最大的距离。中间距离

重心法类平均距离递推公式：…………距离不同，则结果可能不同

§1.4系统聚类分类法(续)[举例]设有6个五维模式样本如下，按最小距离准则进行聚类分析：x1:0,3,1,2,0x2:1,3,0,1,0x3:3,3,0,0,1x4:1,1,0,2,0x5:3,2,1,2,1x6:4,1,1,1,0§1.4系统聚类分类法(续)算法过程描述：

Step1:每个样本看成一类：

说明：（1）距离矩阵元的值是类与类之间的距离，距离的定义有多种。（2）距离矩阵，是对称矩阵。对角上线的元值表示同类之间的距离，即为0。000000x1:0,3,1,2,0x2:1,3,0,1,0x3:3,3,0,0,1x4:1,1,0,2,0x5:3,2,1,2,1x6:4,1,1,1,0Step2:合并距离最小的两类，产生新的距离矩阵

说明：距离矩阵中选择距离最小的，如果有相同的可以任选其中一个，要忽略对角线上的元素。00000Step3：继续合并，计算新的距离矩阵

说明：合并类的距离计算

应该符合距离的运算

规则。如，距离反映

的是两类的重心距离，

那么合并后，应该仍然

反映的重心的距离。Step4：继续合并，直到收敛

说明：算法的收敛条件判断准则的确定。

0000000§1.4系统聚类法(续)系统聚类的 树状表示§1.5动态聚类分类法

基本思想首先选择若干个样本点作为聚类中心，再按某种聚类准则（通常采用最小距离准则）使样本点向各中心聚集，从而得到初始聚类；然后判断初始分类是否合理，若不合理，则修改分类；如此反复进行修改聚类的迭代算法，直至合理为止1.5.1C－均值算法1.5.2ISODATA算法（迭代自组织的数据分析方法）1.5.1C－均值算法思想：基于使聚类性能指标最小化，所用的聚类准则函数是聚类集中每一个样本点到该类中心的距离平方之和，并使其最小化。1.5.1C－均值算法目标：将对象分成C个“最好”的非空的子集基本C均值算法（第二版P237，第三版P193）每次调整一个样本就需要重新计算一次类的均值改进：第一步：选C个初始聚类中心，任选C个样本作为初始聚类中心第二步：计算每个类的平均值作为中心点.

第三步：重新将对象划分到离它最近的聚类

第四步：重新计算聚类的中心，重新划分类，直到所有的类中心都不再发生变化.1.5.1C-均值算法[举例]对如图模式 样本用C-均 值算法进行 分类1.5.1C－均值算法说明：（1）C是指需要分成C类，均值是指每类的中心,就是该类所有样本的平均值，不一定就有某个样本在这个位置上。(2)算法的收敛性判别：前后两次迭代的结果，也就是每迭代分类后，分类都是一样的，此时停止。（3）C值和初始聚类中心对分类的结果影响很大。通常需要其它的算法来确定这两个的选取。

1.5.1C-均值算法（4）C的选择： 上面所说的是C已知的情况，如果C未知，则我们把类别数依次增加：C=1，C=2，C=3。。。，分别适用该算法。显然准则函数Je随着类别增加而减小。我们可以选择拐点处的C作为我们的类别数。1.5.1C-均值算法讨论

C-均值算法的结果受如下选择的影响：所选聚类的数目聚类中心的初始分布模式样本的几何性质读入次序在实际应用中，需要试探不同的C值和选择不同的聚类中心的起始值。如果模式样本可以形成若干个相距较远的孤立的区域分布，一般都能得到较好的收敛效果。C-均值算法比较适合于分类数目已知的情况。1.5.2ISODATA算法IterativeSelf-OrganizingDataAnalysisTechniqueAlgorithm 迭代自组织数据分析算法1.5.2ISODATA算法1.考虑了类别的合并与分裂，因而有了自我调整类别数的能力。合并主要发生在某一类内样本个数太少的情况，或两类聚类中心之间距离太小的情况。为此设有最小类内样本数限制，以及类间中心距离参数。若出现两类聚类中心距离小于的情况，可考虑将此两类合并。

分裂则主要发生在某一类别的某分量出现类内方差过大的现象，因而宜分裂成两个类别，以维持合理的类内方差。给出一个对类内分量方差的限制参数，用以决定是否需要将某一类分裂成两类。1.5.2ISODATA算法2.由于算法有自我调整的能力，因而需要设置若干个控制用参数，如聚类数期望值K、每次迭代允许合并的最大聚类对数L、及允许迭代次数I等。1.5.2ISODATA算法算法描述：

Ref第二版P238，第三版P196说明：基本步骤： (i)选择某些初始值—可选不同指标，也可在迭代运算过程中人为修改，以使所有模式样本按指标分配到各个中心中去。 步骤1 ~2（ii）计算各类别和其中样本的距离函数等指标 步骤4~6（iii）判断分裂、合并以及迭代运算等步骤 步骤7(iv)分裂处理 步骤8~10（v）合并处理 步骤11~13(vi)进行迭代运算，重新计算各项指标，判别聚类结果是否符合要求。 步骤14共计6大步。基本步骤都不会变化。对于该算法，不同的文献上对其具体6个步骤的描述略有差异，如，计算各个参数的值，判断分裂和合并的标准依据。1.5.3基于核的动态聚类方法前面的方法使用均值作为类代表点，这种方法适用于各个分量方差接近或者相等的情况为了解决方差相差比较大的情况，可以适用核函数方法：

Kj=K(a,Vj)

相似性度量Δ(y,Kj)当核函数不能确定形式或者不能简单用函数来表示，可