五 模式识别-聚类

模式识别的理论与方法

——聚类分析

信息工程学院

田玉刚主要内容

数据预处理距离与相似系数算法分析实例分析

聚类分析又称群分析，它是研究（样本/样品/模式）分类问题的一种多元统计方法，所谓类，通俗地说，就是指相似元素的集合。严格的数学定义是较麻烦的，在不同问题中类的定义是不同的。聚类分析起源于分类学，在考古的分类学中，人们主要依靠经验和专业知识来实现分类。随着生产技术和科学的发展，人类的认识不断加深，分类越来越细，要求也越来越高，有时光凭经验和专业知识是不能进行确切分类的，往往需要定性和定量分析结合起来去分类，于是数学工具逐渐被引进分类学中，形成了数值分类学。后来随着多元分析的引进，聚类分析又逐渐从数值分类学中分离出来而形成一个相对独立的分支。在社会经济领域中存在着大量分类问题，比如对我国大陆31个省市自治区独立核算工业企业经济效益进行分析，一般不是逐个省市自治区去分析，而较好地做法是选取能反映企业经济效益的代表性指标，如百元固定资产实现利税、资金利税率、产值利税率、百元销售收入实现利润、全员劳动生产率等等，根据这些指标对31个省市自治区进行分类，然后根据分类结果对企业经济效益进行综合评价，就易于得出科学的分析。又比如若对某些大城市的物价指数进行考察等等。总之，需要分类的问题很多，因此聚类分析这个有用的数学工具越来越受到人们的重视，它在许多领域中都得到了广泛的应用。

值得提出的是将聚类分析和其它方法联合起来使用，如判别分析、主成分分析、回归分析等往往效果更好;并且没有哪一种聚类方法具有绝对优势，如果有优势，也只是相对于具体的数据特征而言。聚类分析内容非常丰富，有简单聚类法、层次聚类法、动态聚类法、模糊聚类法、图论聚类法、聚类预报法等。这里主要介绍常用的聚类算法：简单聚类法、层次聚类法、动态聚类法、模糊聚类法。数据预处理

一般地，设某一分类问题共有n个样本，m个特性指标，则原始数据矩阵为由于m个特性指标的量纲和数量级都不同，所以直接利用原始数据式（1）进行聚类，就可能会突出那些数量级特别大的特性指标对聚类的作用，而降低甚至排斥某些数量级较小的特性指标对聚类的作用，从而导致一个指标只要一改变度量单位就会完全改变聚类结果。为了克服这一缺点，必须先对原始数据矩阵进行无量纲化处理，使每一指标统一在某一共同的数据特性范围内。这个处理过程称为数据标准化。目前较常用的数据标准化方法一般有6种。（1）数据预处理1、标准差标准化标准差标准化是先将原始数据按列取平均，并计算各列的标准差。然后按下式计算标准化数据矩阵的元素数据预处理2、极大值标准化极大值标准化是将原始数据矩阵中的元素分别除以所在列的最大值，其商即为标准化数据矩阵的元素

数据预处理3、极差标准化极差标准化是将原始数据矩阵中的元素减去该列的极小值后除以该列最大值与最小值之差，其商即为标准化数据矩阵的元素

数据预处理4、均值标准化均值标准化是将原始数据矩阵中的元素除以所在列的平均值，其商即为标准化数据矩阵的元素数据预处理5、中心标准化中心标准化是将原始数据矩阵中的元素减去该列的的平均值，其商即为标准化数据矩阵的元素

6、对数标准化对数标准化是将原始数据矩阵中的元素取常用对数后作为标准化数据矩阵的元素

数据预处理

由上述标准化方法可知，中心标准化法（方法5）和对数标准化法（方法6）达不到无量纲目的。一个好的变换方法，应在实现无量纲的同时，保持原有各指标的分辨率，即变异性的大小。现将方法1（标准差）、方法2（极大值）

、方法3（极差）和方法4（均值）变换后数据的特征列于表1。表1由表1知，方法1变换后，个指标的均值和标准差完全相同，分辨率已被完全同化；方法3一般也缩小了各指标之间的变异程度差异的作用，分辨率已被部分完全同化；方法2和方法4没有改变原始数据的变异程度，但方法2易受个别极端值的影响。综上，采用方法4也即均值标准化进行原始数据标准化效果较好。数据预处理距离与相似系数为了将样本进行分类，就需要研究样本之间关系。目前用得最多的方法有两个：一种方法是将一个样本看作m维空间的一个点，并在空间定义距离，距离越近的点归为一类，距离较远的点归为不同的类。另一种方法是用相似系数，性质越接近的样本，它们的相似系数的绝对值越接近1；而彼此无关的样本，它们的相似系数的绝对值越接近于零。比较相似的样本归为一类，不怎么相似的样本归为不同的类。但相似系数和距离有各种各样的定义，而这些定义与变量的类型关系极大，因此先介绍变量的类型。距离与相似系数由于实际问题中，遇到的指标有的是定量的（如长度、重量等），有的是定性的（如性别、职业等），因此将变量（指标）的类型按以下三种尺度划分：间隔尺度：变量是用连续的量来表示的，如长度、重量、压力、速度等等。在间隔尺度中，如果存在绝对零点，又称比例尺度，这里并不严格区分比例尺度和间隔尺度。有序尺度：变量度量时没有明确数量表示，而是划分一些等级，等级之间有次序关系，如某产品分上、中、下三等，此三等有次序关系，但没有数量表示。名义尺度：变量度量时没有数量表示，也没有次序关系，如某物体有红、黄、白三种颜色，又如医学化验中的阴性与阳性，市场供求中的“产”和“销”等。不同类型的变量，在定义距离和相似系数时，其方法有很大差异，使用时必须注意。研究比较多的是间隔尺度，因此这里主要给出间隔尺度的距离和相似系数的定义。距离与相似系数

设有n个样本，每个样本有m项指标（变量），经标准化处理的数据矩阵为其中为第i个样本的第j个指标的观测数据。第i个样本Xi为矩阵X的第i行所描述，所以任何两个样本XK与

XL之间的相似性，可以通过矩阵X中的第K行与第L行的相似程度来刻划；任何两个变量与之间的相似性，可以通过第K列与第L列的相似程度来刻划。距离与相似系数1、对样本分类常用的距离和相似系数定义距离与相似系数

明氏距离特别是其中的欧氏距离是人们较为熟悉的也是使用最多的距离。但明氏距离存在不足之处，主要表现在两个方面：第一，它与各指标的量纲有关；第二，它没有考虑指标之间的相关性，欧氏距离也不例外。除此之外，从统计的角度上看，使用欧氏距离要求一个向量的n个分量是不相关的且具有相同的方差，或者说各坐标对欧氏距离的贡献是同等的且变差大小也是相同的，这时使用欧氏距离才合适，效果也较好，否则就有可能不能如实反映情况，甚至导致错误结论。因此一个合理的做法，就是对坐标加权，这就产生了“统计距离”。

距离与相似系数所加的权是，即用样本方差除相应坐标。当取时，就是点P到原点O的距离。若时，就是欧氏距离。

比如设，，且Q的坐标是固定的，点P的坐标相互独立地变化。用s11,s12,…,smm表示m个变量的n次观测的样本方差，则可以义P到Q的统计距离为：距离与相似系数距离与相似系数

以上三种距离的定义是适用于间隔尺度变量的，如果变量是有序尺度或名义尺度时，也有一些定义距离的方法。距离与相似系数（2）相似系数研究样本之间的关系，除了用距离表示外，还有相似系数，顾名思义，相似系数是描写样本相似程度的一个量，常用的相似系数有：i）夹角余弦这是受相似形的启发而来的，下图曲线AB和CD尽管长度不一，但形状相似。当长度不是主要矛盾时，要定义一种相似系数，使AB和CD呈现出比较密切的关系，则夹角余弦就适合这个要求。它的定义是：距离与相似系数距离与相似系数距离与相似系数2、对指标分类常用的距离和相似系数定义距离与相似系数距离与相似系数算法分析-简单聚类一、根据相似性阈值和最小距离原则的简单聚类方法1、条件及约定设待分类的模式为，选定类内距离阈值T。2、算法思想计算模式特征矢量到聚类中心的距离并和阈值比较而决定归属该类或作为新的一类中心。3、算法原理步骤⑴取任意的一个模式特征矢量作为第一个聚类中心。例如，令第一类⑵计算下一个模式特征矢量到的距离。若，则建立新的一类，其中心

算法分析-简单聚类算法分析-层次聚类二、层次聚类效果较好、是常用方法之一1、条件及约定设待分类的模式特征矢量为，表示第k次合并时的第i类。2、基本思想首先将N个模式视作各自成为一类，然后计算类与类之间的距离，选择距离最小的一对合并成一个新类，计算在新产生的类别分划下各类之间的距离，再将距离最近的两类合并，直至所有模式聚成两类为止。

算法分析-层次聚类算法分析-层次聚类停止条件

以类间距离门限作为停止条件，即取距离门限，当中最小阵元小于时，聚类过程停止；

以预定的类别数目作为停止条件，当类别合并过程中，类数等于预定值时，聚类过程停止。类间距离的定义与递推在该算法中所采用的类间距离定义不同，聚类过程及结果是不一样的。上述算法在归并的每次迭代过程中，距离矩阵的最小元素值不断地改变，如果有单调不减关系则称类间距离对并类具有单调性。最近距离法、最远距离法、平均法及离差平方和法等定义的类间距离都具有这个性质，而重心法没有这个性质。算法分析-层次聚类算法特点聚类过程中类心不断地调整，但某一模式一旦分划到某一类中就不再改变。从粗到细的层次聚类这类技术的另一个算法和上述算法过程相反，依据类的离差平方和递推公式按1类至N类进行层次分解，这里不作介绍了。聚类过程可以表示成一个树图。算法分析-动态聚类

三、ISODATA(迭代自组织数据分析)算法特点：具有启发性推理、分析监督、控制聚类结构及人机交互。

1、条件及约定设待分类的模式特征矢量为，算法运行前需设定7个初始参数。

2、算法思想在每轮迭代过程中，样本重新调整类别之后计算类内及类间有关参数，并和设定的门限比较，确定是两类合并为一类还是一类分裂为两类，不断地“自组织”，以达到在各参数满足设计要求条件下，使各模式到其类心的距离平方和最小。算法分析-动态聚类算法分析-动态聚类算法分析-动态聚类算法分析-动态聚类算法分析-动态聚类算法分析-动态聚类算法分析-动态聚类算法分析-动态聚类算法分析-模糊聚类四、模糊ISODATA算法是较常用的模糊聚类方法算法分析-模糊聚类算法分析-模糊聚类算法分析-模糊聚类分类标准的确定

为了能判断分类数的恰当与否和分类的结果是好还是不好，在此定义类间分辨率。对某一个聚类中心，它与其它聚类中心的距离的最小值是；在属于该聚类中心的所有原始数据中，每个原始数据与该聚类中心都有一个距离，这个距离中最大的距离记为，这个距离的平均值记为。则类间分辨率的好坏由如下两个公式的值来判断：算法分析-模糊聚类如果数据分布的较为合理，则每个聚类中心周围都汇聚集着一定数量的原始数据，且应该小于,即应该大于1；同时也要比小，越大，则说明那些属于某一类的数据点越接近聚类中心。当分类数从小变大时，也会从小变大，直到达到一个极大值，也就是此时的分类效果最好。然后由于受分类数C的