7-第四章_2 相似性度量聚类准则

第七章聚类分析

第七章聚类分析§7.1聚类分析方法一、基本思想根据一批样品的多个观测指标，具体找出一些能够度量样品或指标间相似

程度的统计量，以这些统计量为划分类型的依据，把一些相似程度较大的样品聚为一类。关系密切的聚为一个小的分类单位，关系疏远的聚为

一个大的分类单位，直到把所有样品或指标都聚类完毕，这样就可以形成一个由小到大的分类系统。聚类分析分类：按聚类变量分为样品

聚类（Q聚类）和指标聚类（R聚类）；按聚类方法分为系统聚类和动态聚类二、相似性测度1、对样品进行聚类时，相似性一般用距离

来衡量：（1）绝对值距离（2）欧氏距离（欧几里得距离）（3）平方欧氏距离（4）切比雪夫距离（5）闵可夫斯

基距离2、对指标进行聚类时，相似性通常根据相关系数或某种关联性来决定（1）夹角余弦（2）皮尔逊相关系数（简单相

关系数）§7.2系统聚类法一、基本思想系统聚类法分类：聚集法和分解法。聚集法：首先将每个个体各自看成一群

，将最相似的两个群合并，重新计算群间距离，再将最相似的两群合并，每步减少一群，直至所有个体聚为一群为止。分解法：首先将所有

个体看成一群，将最不相似的个体分成两群，每步增加一群，直至所有个体各自成为一群。二、群间距离的定义1、最短距离法

将两变量间的距离定义为一个群中所有个体与另一个群中的所有个体距离最小者。设为群中的任

一个体，为群中的任一个体，表示个体与间的距离，表示群与群间的距离，则

最短距离法把两群间距离定义为：设类合并成一个新类记为，则任一类

的距离为最短距离法进行聚类分析的步骤如下：（1）定义样品间距离，计算样品的两两距离，得一距离阵记为,

开始每一个样品即为一类，显然这时（2）找出距离最小元素，设为，则将合并成一个新类，记为

，即（3）按类间距离计算新类与其他类的距离（4）重复（2）（3）步，直到所有元素并成一类。如果

某一步距离最小的元素不止一个，则对应这些最小元素的类可以同时合并。例7.1设有六个样品，每个只测量一个指标，分别是1,

1 5.2 聚类准则函数

在样本相似性度量的基础上，聚类分析还需要一定的准则函数，才能把真正属于同一类的样本聚合成一个类型的子集，而把不同类的样本分离开来。如果聚类准则函数选得好，聚类质量就会高。同时，聚类准则函数还可以用来评价一种聚类结果的质量，如果聚类质量不满足要求，就要重复执行聚类过程，以优化结果。在重复优化中，可以改变相似性度量，也可以选用新的聚类准则。

1．误差平方和准则（最常用的）

假定有混合样本},......,,{21nxxxX，采用某种相似性度量，X被聚合成c个分离开的子集cXXX,.....,,21，每个子集是一个类型，它们分别包含cnnn,......,,21个样本。

为了衡量聚类的质量，采用误差平方和cJ聚类准则函数，定义为：

cjnkjkcjmxJ112||||

式中jm为类型jw中样本的均值：jnjjjjxnm11，cj,....,2,1。

jm是c个集合的中心，可以用来代表c个类型。

cJ是样本和集合中心的函数。在样本集X给定的情况下，cJ的取值取决于c个集合中心。cJ描述n个试验样本聚合成c个类型时，所产生的总误差平方和。cJ越小越好。

最小方差划分：寻找cJ最小的聚类结果，也就是在误差平方和准则下的最优结果。

误差平方和准则适用于各类样本比较密集且样本数目悬殊不大的样本分布。例如：

上图的样本分布，共有3个类型，各个类型的样本数目相差不多（10个左右）。类内较密集，误差平方和很小，类别之间距离远。

注意：如果不同类型的样本数目相差很大，采用误差平方和准则，有可能把样本数目多的类型分开，以便达到总的cJ最小。如下图所示：

下面进一步说明上述问题：

1 例如：有5个样本，如下图所示1x～14wx，25wx。

虚线为正确类型区分域，实线为采用误差平方和最小准则时的类别区分。

虚线划分时：},,,{:432111xxxxXw，Tkkxm)0,0(41411

聚类超详细的性能度量和相似度方法总结

非监督学习与监督学习最重要的区别在于训练数据是否包含标记数据，在机器学习开发的工作中，往往包含了大量的无标记数据和少量的标记数据，非监督方法通过对无标记训练样本的学习来发掘数据的内在规律，为进一步的数据分析提供基础。

聚类算法是非监督学习最常用的一种方法，性能度量是衡量学习模型优劣的指标，也可作为优化学习模型的目标函数。聚类性能度量根据训练数据是否包含标记数据分为两类，一类是将聚类结果与标记数据进行比较，称为“外部指标”；另一类是直接分析聚类结果，称为内部指标。本文对这两类的性能度量以及相似度方法作一个详细总结。

目录

1. 外部指标

2. 内部指标

3. 相似度方法总结

4. 小结

1. 外部指标

在详细介绍外部指标前，先定义两两配对变量a和b：

a：数据集的样本对既属于相同簇C也属于相同簇K的个数

b：数据集的样本对不属于相同簇C也不属于相同簇K的个数

用一个简单例子来说明a，b的含义：

真实簇向量：[ 0, 0, 0, 1, 1, 1 ]

预测簇向量：[ 0, 0, 1, 1, 2, 2 ]

a为属于相同簇向量的样本对个数，用红色框标记：

如上图：a = 2；

b为数据集不属于相同簇C也不属于相同簇K的样本对个数，用绿色框标记： 如上图：b = 1；

知道了a，b的含义，下面开始详细介绍外部指标的性能度量。

1.1 RI（兰德系数）

RI是衡量两个簇类的相似度，假设样本个数是n，定义：

其中是所有可能的样本对个数。

假设：

真实簇向量：[ 0, 0, 0, 1, 1, 1 ]

预测簇向量：[ 0, 0, 1, 1, 2, 2 ]

RI系数的缺点是随着聚类数的增加，随机分配簇类向量的RI也逐渐增加，这是不符合理论的，随机分配簇类标记向量的RI应为0。

1.2 ARI（调整兰德系数）

ARI解决了RI不能很好的描述随机分配簇类标记向量的相似度问题，ARI的定义：

聚类分析

我们所研究的样品（网点）或指标（变量）之间存在程度不同的相似性（亲疏关系——以样品间距离衡量）。于是根据一批样品的多个观测指标，具体找出一些能够度量样品或指标之间相似程度的统计量，以这些统计量为划分类型的依据。把一些相似程度较大的样品（或指标）聚合为一类，把另外一些彼此之间相似程度较大的样品（或指标）又聚合为另一类，直到把所有的样品（或指标）聚合完毕，这就是分类的基本思想。 在聚类分析中，通常我们将根据分类对象的不同分为Q型聚类分析和R型聚类分析两大类。

一：Q型聚类分析（系统聚类）

1：样本的相似性度量

记是样本点集，距离(,)d是R的一个函数，满足条件：

（1） (,)0,,dxyxy；

（2） (,)0dxy当且仅当xy；

（3） (,)(,),,dxydyxxy；

（4） (,)(,)(,),,,dxydxzdzyxyz。

这一距离的定义是我们所熟知的，它满足状态性、对称性和三角不等式。在聚类分析中，对于定量变量，最常用的是闵式距离(Minkowski)距离，即

11(,),0pqqpkkkdxyxyq

当1,2q或q时，则分别得到：

（1） 绝对值距离

11(,)pkkkdxyxy

（2） 欧式(Euclid)距离

12221(,)pkkkdxyxy

（3） 切比雪夫(Chebyshew)距离

1(,)maxkkkpdxyxy

（4） 马氏(Mahalanobis)距离

T1(,)()()dxyxyxy,

其中：,xy为来自p维总体Z的样本观测值；为Z的协方差矩阵，实际中往往是未知的，常常需要用样本协方差来估计。马氏距离对一切线性变换是不变的，故不受量纲的影响。

2：类与类的相似性度量

如果有两个样本类1G和2G，可以用下面的一系列方法度量它们的距离。