数学建模论文聚类分析

《数学建模论文聚类分析》由会员分享，可在线阅读，更多相关《数学建模论文聚类分析（6页珍藏版）》请在装配图网上搜索。

1、1 聚类分析将认识对象进行分类是人类认识世界的一种重要方法，比如有关世界的时间进程的究，就形成了历史学，也有关世界空间地域的研究，则形成了地理学。又如在生物学中，为了研究生物的演变，需要对生物进行分类，生物学家根据各种生物的特征，将它们归属于同的界、门、纲、目、科、属、种之中。事实上，分门别类地对事物进行研究，要远比在一个混杂多变的集合中更清晰、明了和细致，这是因为同一类事物会具有更多的近似特性。在企业的经营管理中，为了确定其目标市场，首先要进行市场细分。因为无论一个企业多么庞大和成功，它也无法满足整个市场的各种需求。而市场细分，可以帮助企业找到适合自己特色，并使企业具有竞争力的分市场，将其作

2、为自己的重点开发目标。通常，人们可以凭经验和专业知识来实现分类。而聚类分析（cluster analyses）作为一种定量方法，将从数据分析的角度，给出一个更准确、细致的分类工具。1.1 相似性度量1.1.1 样本的相似性度量要用数量化的方法对事物进行分类，就必须用数量化的方法描述事物之间的相似程度。一个事物常常需要用多个变量来刻画。如果对于一群有待分类的样本点需用p 个变量描述，则每个样本点可以看成是Rp空间中的一个点。因此，很自然地想到可以用距离来度量样本点间的相似程度。 记是样本点集，距离d(,)是 R+的一个函数，满足条件：1）d(x, y) 0，x, y；2）d(x, y) = 0当

3、且仅当x = y；3）d(x, y) = d( y, x)，x, y；4）d(x, y) d(x, z) + d(x, y)，x, y, z。这一距离的定义是我们所熟知的，它满足正定性，对称性和三角不等式。在聚类分析中，对于定量变量，最常用的是Minkowski 距离 当q = 1,2或q +时，则分别得到 1） 绝对值距离 (1)2） 欧氏距离 (2)3） Chebyshev 距离 (3)在 Minkowski 距离中，最常用的是欧氏距离，它的主要优点是当坐标轴进行正交旋转时，欧氏距离是保持不变的。因此，如果对原坐标系进行平移和旋转变换，则变换后样本点间的距离和变换前完全相同。值得注意的是在

4、采用 Minkowski 距离时，一定要采用相同量纲的变量。如果变量的量纲不同，测量值变异范围相差悬殊时，建议首先进行数据的标准化处理，然后再计算距离。在采用Minkowski 距离时， 还应尽可能地避免变量的多重相关性（multicollinearity）。多重相关性所造成的信息重叠，会片面强调某些变量的重要性。由于Minkowski 距离的这些缺点，一种改进的距离就是马氏距离，定义如下4） 马氏（Mahalanobis）距离 (4) 其中x, y为来自p 维总体Z 的样本观测值，为Z 的协方差矩阵，实际中往往是不知道的，常常需要用样本协方差来估计。马氏距离对一切线性变换是不变的，故不受量纲

5、的影响。此外，还可采用样本相关系数、夹角余弦和其它关联性度量作为相似性度量。近年来随着数据挖掘研究的深入，这方面的新方法层出不穷。1.1.2 类与类间的相似性度量如果有两个样本类 1 G 和2 G ，我们可以用下面的一系列方法度量它们间的距离：1） 最短距离法（nearest neighbor or single linkage method） (5) 它的直观意义为两个类中最近两点间的距离。2） 最长距离法（farthest neighbor or complete linkage method） (6) 它的直观意义为两个类中最远两点间的距离。3） 重心法（centroid method）

6、 (7) 其中x, y 分别为1 2 G ,G 的重心。4） 类平均法（group average method） (8) 它等于中两两样本点距离的平均，式中 分别为中的样本点个数。5）离差平方和法（sum of squares method）若记 其中 则定义 (9) 事实上，若 内部点与点距离很小，则它们能很好地各自聚为一类，并且这两类又能够充分分离（即 很大），这时必然有 很大。因此，按定义可以认为，两类 之间的距离很大。离差平方和法最初是由Ward 在1936 年提出，后经 Orloci 等人1976 年发展起来的，故又称为Ward 方法。1.2 系统聚类法1.2.1 系统聚类法的功能

7、与特点系统聚类法是聚类分析方法中最常用的一种方法。它的优点在于可以指出由粗到细的多种分类情况，典型的系统聚类结果可由一个聚类图展示出来。例如，在平面上有7 个点1 2 7 w ,w ,􀀢,w （如图1（a），可以用聚类图（如图1（b）来表示聚类结果。 图1 聚类方法示意图 记 聚类结果如下：当距离值为5 时，分为一类 距离值为分为两类： 距离值为分为三类： ; 距离值为分为六类： 距离小于分为七类，每一个点自成一类。 怎样才能生成这样的聚类图呢？步骤如下：设1)计算n个样本点两两之间的距离,记为矩阵； 2）首先构造n 个类，每一个类中只包含一个样本点，每一类的平台高度均为零；

8、3）合并距离最近的两类为新类，并且以这两类间的距离值作为聚类图中的平台高度；4）计算新类与当前各类的距离，若类的个数已经等于1，转入步骤5），否则，回到步骤3）；5）画聚类图；6）决定类的个数和类。显而易见，这种系统归类过程与计算类和类之间的距离有关，采用不同的距离定义，有可能得出不同的聚类结果。 1.2.2 最短距离法与最长距离法如果使用最短距离法来测量类与类之间的距离，即称其为系统聚类法中的最短距离法（又称最近邻法），最先由Florek 等人1951 年和Sneath1957 年引入。下面举例说明最短距离法的计算步骤。 例1 设有5个销售员，他们的销售业绩由二维变量() 描述,见表1。 表

9、1 销售员业绩表销售员（销售量）百件（回收款项）万元1011 324325 记销售员w (i =1,2,3,4,5) i 的销售业绩为（）。如果使用绝对值距离来测量点与点之间的距离，使用最短距离法来测量类与类之间的距离，即，由距离公式d(,)，可以算出距离矩阵。 第一步，所有的元素自成一类。每一个类的平台高度为零，即。显然，这时。 第二步，取新类的平台高度为 1，把合成一个新类，此时的分类情况是 第三步，取新类的平台高度为 2，把合成一个新类，此时的分类情况是 第四步，取新类的平台高度为 3，把合成一个新类，此时的分类情况是 第五步，取新类的平台高度为4，把 和合成一个新类,此时的分类情况是 图2 最短距离法 这样， 9 h 已把所有的样本点聚为一类，因此，可以转到画聚类图步骤。画出聚类图（如图2（a）。这是一颗二叉树，如图2（b）。有了聚类图，就可以按要求进行分类。可以看出，在这五个推销员中的工作成绩最佳，的工作成绩最好，而的工作成绩较差。完全类似于以上步骤，但以最长距离法来计算类间距离，就称为系统聚类法中的最长距离法。