【模式识别与智能计算】第9章 聚类分析

本章要点:

• 聚类的设计
• 基于试探的未知类别聚类算法
• 层次聚类算法
• 动态聚类算法
• 模拟退火聚类算法

9.1聚类的设计

聚类分析是指事先不了解-批样品中的每一个样品的类别或者其他的先验知识,而唯一
的分类根据是样品的特征,利用某种相似性度量的方法,把特征相同或相近的归为一类,实现聚类划分。例如，对于- -幅手写数字图像,如图9- 1所示,将相同的手写数字划分为一类,即聚类分析要解决的问题。
本书从第9章到第13章对各种聚类算法进行了理论分析和实例介绍,为了便于读者对后
面章节的阅读,本节将对聚类算法设计中的结构定义以及距离计算方法等常用函数功能进行
介绍,使读者能够更清楚地阅读算法程序。

1.样品结构设计

样品是聚类分析中的最基本单位,例如，手写数字聚类中每一一个 手写数字即为-一个样品，通常一个样品的结构包括样品特征和所属类别两部分。
在本书基于Matlab 的聚类算法设计中,样品结构定义如下。

(1)样品集m _ patterm

样品集为多个样品的集合,一个具有N个样品的样品集m_ pattern, 定义为m_ patterm=
{m_ pattern (1), m_ patten(2),，m _ pattern(N)},其中m _ pattern中每一个元素为一个样品结构。

(2)样品m _ pattern(i)

对于样品集中的样品m _ pattern(i) ,其结构定义为:
Struct m_ pattern(i)
{feature;
category ;
}
其中feature是该样品的特征矩阵,本书中对每个样品划分成7 x7块,共49个特征。category
为样品所属类别。

2.聚类中心结构设计

聚类中心是指当对样品进行聚类划分之后,对每一个划分好的类用一个结构来描述,这个
结构就是聚类中心。聚类中心结构包括聚类中心特征,属于该类的样品数目,类索引值。
类似于样品结构定义, 聚类中心结构定义如下。

(1)聚类中心集m _ center

聚类中心集为多个聚类中心的集合,-一个具有M个类的聚类中心集m_ center,定义为 m
center ={ m_ center (1), m_ center (2),., m_ center (M)} ,其中m _ center 中每-一个元
素为一个聚类中心结构。

(2)聚类中心m _ center(i)

聚类中心m _ center(i) ,其结构定义为
Struct m_ center(i)
feature;
patternNum;
index ;
其中,feature是该聚类中心的特征矩阵,patternNum为属于该类的样品数目,index为类的索
引号。

3.样品(或聚类中心)与样品(或聚类中心)的距离

本书中计算样品(或聚类中心)特征之间距离有四种方法,分别是欧氏距离法、夹角余弦
距离法、二值夹角余弦法和具有二值特征的Tanimoto 测度。计算公式见本书第3章的表3-1。
本书中距离计算的Matlab函数为:GetDistance( ),具体的函数说明及代码如下:

4.计算聚类中心

聚类算法中经常会用到聚类中心的计算,聚类中心的特征值等于该类所有样本特征值的
平均值,在已知- -个聚 类划分的情况下,求解聚类中心的函数为CalCenter( ) ,函数说明如下:

9.2 基于试探的未知类别聚类算法

定义误差平方和为

式中,M是聚类中心的个数,M应该小于样品的总个数。w; 表示第i类,X(,)表示第i类的聚类中心向量。针对所有样品假设某种聚类方案,计算J值,找到J值最小的那一种聚类方案,则认为该种方法为最优聚类。以下讨论的是在聚类数未知情况下,以该准则为聚类方案。

9.2.1最临近规则的试探法

1.理论基础

设有N个样品:X, ,x.,.,Xn,并选取任- -非负的阈值T。为方便起见，我们假设前i(i<
N)个样品已经被分到k(k≤i)个类中。则第i+1个样品应该归入哪一- 个类中呢?假设归入
w。类，要使J最小，则应满足|X,1-x(0)1≤|Xl±X(°》1(1≤b≤h)。若X到w。类的距.
离大于给定的阈值r,即|X… -x(00)1>T,则应为X.,建立一个新的类0…1。在未将所有的
样品分类前,类数是不能确定的。
这种算法与第一个中心的选取、阈值T的大小、样品排列次序以及样品分布的几何特性
有关。这种方法运算简单,若有关于模式几何分布的先验知识做指导给出阈值T及初始点，则能较快地获得合理的聚类结果。
合理地选择聚类中心和阈值,将会得到正确的聚类结果,如图9-2(a)所示,若选择的中心
和阈值不当,得到聚类结果比较粗糙,甚至错误,如图9-2(b)和©所示。

9.2.2最大 最小距离算法

1.理论基础

最大最小距离算法充分利用样品内部特性,计算出所有样品间的最大距离maxdistance作为归类阈值的参考,改善了分类的准确性。若某样品到某–个聚类中心的距离小于maxdistance/3 ,则归人该类，否则建立新的聚类中心。

9.3 层次聚类算法

与未知类别的聚类算法不同,层次聚类分为合并算法和分裂算法。合并算法会在每一一步减小聚类中心数量,聚类产生的结果来自于前-一步的两个聚类的合并;分裂算法与合并算法的.原理相反,在每一步增加聚类中心数量,每一步聚类产生的结果,都是将前一-步的–个聚类中心分裂成两个得到的。合并算法,先将每个样品自成一类,然后根据类间距离的不同,合并距离小于阈值的类。
①设有N个样品,这里取N=4。每个样品自成- -类 ,计算各类间的距离填入表9- 1。

9.4动态聚类算法

动态聚类算法选择若干样品作为聚类中心,再按照某种聚类准则,如最小距离准则,将其
余样品归人最近的中心,得到初始分类。然后判断初始分类是否合理,若不合理则按照特定规则重新修改不合理的分类,如此反复迭代,直到分类合理。

9.4.1 K 均值算法

1.理论基础

K均值算法能够使聚类域中所有样品到聚类中心距离的平方和最小。其原理为:先取h个初始距离中心,计算每个样品到这k个中心的距离,找出最小距离把样品归人最近的聚类中心,如图9-10(a)所示,修改中心点的值为本类所有样品的均值,再计算各个样品到h个中心的距离,重新归类、修改新的中心点,如图9- 10( b)所示。直到新的距离中心等于上- -次的中心点时结束。此算法的结果受到聚类中心的个数以及初始聚类中心的选择影响,也受到样品几何性质及排列次序影响。如果样品的几何特性表明它们能形成几个相距较远的小块孤立区域,则算法多能收敛。

9.4.2迭代自组织的数据分析算法(ISODATA )

1.理论基础

迭代自组织的数据分析算法( Iterative Self- organizing Data Analysis Techniques Algorithm) 也称ISODATA算法。此算法与K均值算法有相似之处,即聚类中心也是通过样品均值的迭代运算来决定的。但ISODATA加入了一些试探性的步骤,能吸取中间结果所得到的经验,在迭代过程中可以将一类一分为二，也可以将两类合并,即“自组织”。这种算法具有启发性。

9.5模拟退火聚类算法

9.5.1模拟退 火的基本概念

模拟退火算法( Simulated annealing, SA)最初由Metropolis 等人于20世纪80年代初提出,其思想源于物理中固体物质退火过程与一般组合优化问题之间的相似性。模拟退火方法是一种通用的优化算法,目前已广泛应用于最优控制、机器学习神经网络等优化问题。

1.物理退火过程

模拟退火算法源于物理中固体物质退火过程,整个过程由以下三部分组成。

(1)升温过程

升温的目的是增强物体中粒子的热运动,使其偏离平衡位置变为无序状态。当温度足够
高时,固体将溶解为液体,从而消除系统原先可能存在的非均匀态,使随后的冷却过程以某一平衡态为起点。升温过程与系统的熵增过程相关,系统能量随温度升高而增大。

(2)等温过程

在物理学中,对于与周围环境交换热量而温度不变的封闭系统,系统状态的自发变化总是
朝向自由能减小的方向进行,当自由能达到最小时,系统达到平衡态。

(3)冷却过程

与升温过程相反,使物体中粒子的热运动减弱并渐趋有序,系统能量随温度降低而下降,
得到低能量的晶体结构。

2.模拟退火算法的基本原理

模拟退火的基本思想是指将固体加温至充分高，再让其徐徐冷却,加温时,固体内部粒子
随温升变为无序状，内能增大,而徐徐冷却时粒子渐趋有序，在每个温度都达到平衡态，最后在常温时达到基态，内能减为最小。
根据Metropolis准则，粒子在温度T时趋于平衡的几率为e - SE/(kT),其中E为温度T时的.内能,△E为其改变量,K为Bolzmann常数。用固体退火模拟组合优化问题,将内能E模拟为.目标函数值f,温度T演化成控制参数t,即得到解组合优化问题的模拟退火算法:由初始解和控制参数初值开始，对当前解重复“产生新解-→计算目标函数差- +判断是否接受-→接受或舍弃”的迭代，并逐步衰减t值，算法终止时的当前解即为所得近似最优解,这是蒙特卡罗迭代求解法的–种启发式随机搜索过程。
如果用粒子的能量定义材料的状态,Metropolis算法用一个简单的数字模型描述了退火过程。假设材料在状态i之下的能量为E(i),那么材料在温度T时从状态i进人到状态j就遵循
如下规律:
如果E(j)≤E(i) ,则接收该状态被转换;
如果E(j)>E(i),则状态转换以如下概率被接收:

式中,K为物理学中的常数;T为材料的温度。

(1)模拟退火算法的组成

模拟退火算法由解空间、目标函数和初始解三部分组成。
①解空间:对所有可能解均为可行解的问题定义为可能解的集合，对存在不可行解的问
题,或限定解空间为所有可行解的集合,或允许包含不可行解但在目标函数中用惩罚函数
(PenaltyFunction)惩罚以致最终完全排除不可行解。
②目标函数:对优化目标的量化描述，是解空间到某个数集的一- 个映射，通常表示为若
干优化目标的一个和式,应正确体现问题的整体优化要求且较易计算，当解空间包含不可行
解时还应包括罚函数项。
③初始解:是算法迭代的起点，试验表明，模拟退火算法是健壮的( Robust)，即最终解
的求得不十分依赖初始解的选取，从而可任意选取一个初始解。

(2)模拟退火算法的基本过程

①初始化，给定初始温度To及初始解w,计算解对应的目标函数值f(w),在本节中w代
表一种聚类划分。
②模型扰动产生新解。‘及对应的目标函数值f(w’)。
③计算函数差值Af=f(w’) -f(w)。
④如果Af≤0,则接受新解作为当前解。
⑤如果Af>0,则以概率p接受新解。

⑥对当前T值降温,对步骤②~⑤迭代N次。
⑦如果满足终止条件,输出当前解为最优解,结束算法，否则降低温度,继续迭代。
模拟退火算法流程如图9-14所示。算法中包含1个内循环和1个外循环，内循环就是
在同一温度下的多次扰动产生不同模型状态,并按照Metropolis准则接受新模型,因此是用模
型扰动次数控制的;外循环包括了温度下降的模拟退火算法的迭代次数的递增和算法停止的
条件,因此基本是用迭代次数控制的。

9.5.2基于模拟退火思想的改进K均值聚类算法

1.K均值算法的局限性

基本的K均值算法目的是找到使目标函数值最小的K个划分,算法思想简单，易实现,而.
且收敛速度较快。如果各个簇之间区别明显,且数据分布稠密,则该算法比较有效,但如果各
个簇的形状和大小差别不大，则可能会出现较大的簇分割现象。此外，在K均值算法聚类时，
最佳聚类结果通常对应于目标函数的极值点,由于目标函数可能存在很多的局部极小值点,这，
就会导致算法在局部极小值点收敛。因此初始聚类中心的随机选取可能会使解陷人局部最优
解,难以获得全局最优解。
该算法主要的局限性主要表现为:
①最终的聚类结果依赖于最初的划分。
②需要事先指定聚类的数目M。
③产生的类大小相关较大,对于“噪声”和孤立点敏感。
④算法经常陷人局部最优。
⑤不适合对非凸面形状的簇或差别很小的簇进行聚类。

2.基于模拟退火思想的改进K均值聚类算法

模拟退火算法是-一种启发式随机搜索算法,具有并行性和渐近收敛性,已在理论上证明它
是一种以概率为l,收敛于全局最优解的全局优化算法,因此用模拟退火算法对K均值聚类算
法进行优化,可以改进K均值聚类算法的局限性,提高算法性能。

基于模拟退火思想的改进K均值聚类算法中,将内能E模拟为目标函数值,将基本K均
值聚类算法的聚类结果作为初始解，初始目标函数值作为初始温度To,对当前解重复“产生新
解→计算目标函数差->接受或舍弃新解”的迭代过程,并逐步降低T值,算法终止时当前解为
近似最优解。这种算法开始时以较快的速度找到相对较优的区域,然后进行更精确的搜索,最
终找到全局最优解。

3.几个重要参数的选择

(1)目标函数

选择当前聚类划分的总类间离散度作为目标函数，如式9-12所示。

式中,X为样本向量;w为聚类划分;X(")为第i个聚类的中心;d(X,X(n)为样品到对应聚类
中心距离;聚类准则函数J。即为各类样本到对应聚类中心距离的总和。

(2)初始温度

-般情况下,为了使最初产生的新解被接受,在算法开始时就应达到准平衡。因此选取基
本K均值聚类算法的聚类结果作为初始解，初始温度T。=J。。

(3)扰动方法

模拟退火算法中的新解的产生是对当前解进行扰动得到的。本算法采用一-种随机扰动方
法,即随机改变一个聚类样品的当前所属类别，从而产生一.种新的聚类划分,从而使算法有可
能跳出局部极小值。

(4)退火方式

本算法采用式(9- 11)描述的退火方式,其中a为退火速度,控制温度下降的快慢,取a =0. 99。

4.算法流程

基于模拟退火思想的改进K均值聚类算法流程如图9- 15所示。