动态聚类

利用聚类分析方法进行图像分类使用较多的是动态聚类法。在系统聚类法中，对于那些先前已被“错误”聚类的样本，将不再提供重新聚类的机会，而动态聚类法却允许样本从一个类移动到另一个类中。此外与建立在距离矩阵基础上的系统聚类法相比，动态聚类具有计算量小，占用计算机内存较少和方法简单的优点。

动态聚类又称为逐步聚类、迭代聚类、快速聚类法。其基本思想是选择一批凝聚点或给出一个初始的聚类，让样本按某种原则向凝聚点凝聚，对凝聚点进行不断地修改或迭代，直至分类比较合理或迭代稳定为止。简单地说，就是初始设定基础上，在分类过程中根据一定原则不断重复计算类别总数、类别中心，使分类结果逐渐趋于合理，直到满足一定条件分类完毕。根据初始条件的设定方式又分为聚合法和分裂法(图1)。

图1 动态聚类算法框图

(1)聚合法

遥感图像分类的对象就是像元，统计分类的指标是像元的灰度差异。如果按8位灰度级计算，最多可将全部像元分为256级，以此作为初始类别数显然不合理。于是在应用聚合法图像分裂时先给出一个粗糙的初始分类，然后使用某种原则进行修改，直到分类比较合理为止。动态聚类开始时多按某些原则设法选择一些初始类中心，而让待分像元依某些判别准则向初始类中聚集，第一次分类之后，调整各类中心，重新进行第二次分类，对第一次分类进行修改。如此反复进行，直到最后满意为止，这就是迭代法的基本思想。

动态聚类方法的过程：

• 选择初始分类数

初始类别数和类中心有多种设定方法，可以根据实际分类对象和对图像的初步目视分诶下确定类别数(可忽略设多些)，也可用下面方法确定：在每个分类波段上选取若干灰度值，比如4个波段参加分类，根据各类图像的直方图作累计分布直方图，取累计分布直方图等于1/3和2/3处的灰度值，可以有16种组合，这16中灰度值组合便构成了四维特征空间中的16个矢量点的坐标位置，就是16个类别的初始类中心点。也可以分析图像后确定大致类别数，初始类中心可以任意选择，并不影响分类结果，但会延长计算时间(图2)。

图2 初始灰度选择

• 计算最小距离

在动态聚类过程中，扫描每一个像元点，计算每一个像元点和初始类中心得特征空间距离。一般图像处理软件都设有距离参数供用户选择。常用的距离有欧式距离，绝对距离等。用户可事先确定使用哪一种距离。计算待分像元点跟所有类中心距离之后，进一步比较这些距离，从中选出距离最小距离，则待分像元点就应归属于这个最小距离代表的那一类。如图3，像元x距w3距离最短，故划归该类。设计程序软件时，往往设有一个拒绝分类的阈值，这个阈值是拒绝类的门限值。待分像元最小距离大于门限值时，就判为拒绝类。设置的门限值应大小合适，如果太大，就等于没有拒绝，即等于按最小拒绝判决分类。相反，如果门限值取得太小，被拒绝的像元点就会过多，所以这个门限值要设置得当。也可以不设门限值。

图3 最小距离判别图

• 修改类中心进行下一次迭代

在全部像元样本按各类中心分类之后，重新计算每一类的新的均值，用这个均值作为下一次分类的中心，这一过程称为迭代过程。再重新执行2、3两个步骤，这样循环迭代继续下去，按照一定的精度要求控制分类进程，分类结果渐渐趋于精确。分类的关键是循环迭代过程的控制，包括类别数目控制、参数选择和分类终止条件。

• 类的合并和分裂

在迭代过程中，类别数可以有变化，有些类可以分开，有些类也可以合并，这正是动态聚类的特点。为此，需要规定分裂合并的条件。

类的合并：如果两个类的中心太近，即均值差很小，这时就要合并。如果某一类的像元数太少，这一类就跟相近的类合并，或者完全去掉不考虑，暂时归为拒绝类，等下一次迭代被重新分类。如果总的类别数太多，即在分裂过程中，超过了事先给定的类数，这时则将最近的两类合并。

类的分裂：如果某一类别像元太多，占拳头像元的百分比太大，就要设法分为两类。首先要计算本类的均值和标准差，然后以均值减去标准差作为一个类的中心，再以均值减去标准差作为另一个类的中心。如果类数太少，少于某一实现给定的阈值，则将离散度最大的一类分裂为两个新类别。因为如果某一个类别在特征空间中的离散度太大，则有可能不是同一类别。这时对它进行分裂是有道理的，具体的分裂方法仍和前面一样。

• 分类过程控制

如果不加限制，在动态聚类过程中，合并分裂，分裂合并就会无限循环下去。可以从以下几个方面来设定分类的终止条件：用控制迭代次数的方法使动态聚类分类停止下来。可以事先确定迭代次数，迭代次数完成分类也就结束了，此种方法的缺点是硬性迭代次数，实际分类效果如何难以预知；通过比较收敛效果的方法来考虑分类过程的结束，在分类过程中每进行一次迭代，都要将本次迭代结果与上一次迭代结果进行比较，如果两次迭代结果差不多，很接近，满足我们的精度要求，就认为迭代结果已经收敛，分类过程可以结束；用分类的类别数是否有变化来控制分类过程的结束，在分类过程中如果分类的类别数一直保持不变，这时分类就已经停止。但此种方法没有考虑到某些类分裂而另一些类合并达到动态平衡保持类数不变的情况。

• 参数的选择

在动态聚类分类过程中，分类效果好坏很大程度决定于参数的选择。参数选择合理，就会有好的分裂结果；反之，参数不合适，各个参数互相制约，不但不会产生好的分类结果，有时还会使分类陷入死循环状态，毫无休止地进行下去。这一方面需要靠专业知识，也要考多积累一些经验。

(2)分裂法

另一种动态聚类是用所谓分裂方法来实现的，分类过程与前述相似。

• 初始类别中心的确定

开始聚类时，如果设置的初始类别数为m，这时就要寻m个类中心。类中心的建立必须先求出整幅图像的均值和标准差，然后按照下面的公式计算出每一个类别中心值。

其中，M是图像均值；

σ是标准差。

一般来说，分m个类别时，则在(M-σ)到(M+σ)之间等分(m-1)份，就可以有m个节点，这m个节点的数值就是m个类别的初始中心。如果开始没有给出类别数m，则可按一分为二的方法建立类中心进行分类。这种方法也要先计算待分类图像的均值和标差，然后以均值加减标准差各为一类的中心进行聚类，以后根据情况逐级分裂下去。

• 分类准则

和前面聚合法一样，也按最小距离原则判归类别。

• 类别分裂

设置某一标准σy作为阈值，计算分类后各类别的均值与标准差，只要有 一个波段的标准差大于指定的σy，则该类就分裂为两类。直到所有类别的标准差都小于指定的σy，分类才会停止。

• 控制分类过程结束

通过分裂进行聚类也需要设定一些条件，以防止分类无休止进行下去，可以预先规定最多分类数，超过阈值就要停止，虽然分裂过程可以由标准差σy阈值、最多类别数控制，但为避免过多循环，有必要指定最多迭代次数，如果超过这一阈值，则分类过程自动终止。

动态聚类的特点在于聚类过程通过不断地迭代来完成，且在迭代中通常允许样本从一个聚合类中转移到另一个聚合类中。ISODATA聚类法认为同类事物在某种属性空间上具有一种密集型的特点，它假定样本集中的全体分为m类，并选定Zk为初始聚类中心，然后根据最小距离原则将每个样本分配到某一类中；之后不断迭代，计算各类的聚类中心，并以新的聚类中心调整聚类情况，并在迭代过程中，根据聚类情况自动地进行类的合并和分裂。

动态聚类包括许多种方法，此处我们讨论一种较常用的方法K-Means聚类法。K-Mezn是由麦克奎因(Macqueen)于1967年提出的。模糊C均值算法是应用最广、最灵活的一种模糊聚类算法，最早是Dunn在1974年提出m=2的情形，是对硬C均值聚类算法的一种改进算法，随后被Bezdek进一步推广到任意m并证明了收敛性。FCM作为传统C均值聚类算法的自然推广，是最受欢迎的模糊聚类算法，已经成功应用于图像分割、公路检测等诸多领域。其主要优点是理论基础好，算法简单、快速、能有效处理大数据。

1.K-Means算法

基本K-Means算法的思想很简单，事先确定常数K，常数K意味着最后只能够的剧烈类别数，首先随机选定初始点为质心，并通过计算每一个样本与质心之间的相似度（这里为欧式距离），将样本点归到最相似的类中，接着重新计算每个类的质心（即为类心），重复这样的过程，不断地“自组织”，直至质心不再改变，最终确定每个样本所属的类别及每个类的质心。由于每次都要计算所有的样本与每一个质心之间的相似度，因此在大规模的数据集上，K-Means算法的收敛速度比较慢。

换一种说法：

1.1K-Means算法流程

K-Means算法是一种基于样本相似性度量的间接聚类反复噶，属于非监督学习方法。此算法以K为参数，把n个对象分为K个簇，以使簇内具有较高的相似度，而且簇间的相似度较低。相似度的计算根据一个簇中对象的平均值（被看作簇的重心）来进行。此算法首先随机选择K个对象。对于其余的每一个对象，根据该对象与各聚类质心之间的距离，把它分配到与最相似的聚类中。然后计算每个聚类的新质心。重复上述过程，直到准则函数收敛。K-Means算法是一种较典型的逐点迭代的动态聚类算法，其要点是以误差平方和为准则函数。逐点修改类中心：一个象元样本按某一准则归属于某一组内后，就要重新计算这个组类的均值，并且以新的均值作为凝聚中心点进行下一次象元聚类；然后逐批修改类中心：在全部象元样本按某一组的类中心分类之后，再计算修改各类的均值，作为下一次分类的凝聚中心点。过程如下：

(1)初始化常数K，随机选取初始点为质心；

(2)重复计算一下过程，直到质心不再改变；

(3)计算样本与每个质心之间的相似度，将样本归类到最相似的类中；

(4)重新计算质心;

(5)输出最终的质心及每个类。

1.2K-Means算法实现

在实际应用中，由于K-Means一般作为数据预处理，或者用于辅助分类贴标签，所以K一般不会设置很大。可以通过枚举，令K从2到一个固定值如10，在每个K值上重复运行数次K-Means(避免局部最优解)，并计算当前K的平均轮廓系数，最后选取轮廓系数最大的值对应的K作为最终的集群数目。

1.3K-Means算法存在的问题

由于K-Means算法简单且易于实现，因此K-Means算法得到了很多的应用，但是从K-Means算法的过程中发现，K-Means算法中的聚类中心的个数K需要事先指定，这一点对于一些未知数据存在很大的局限性。其次，在利用K-Means算法进行聚类之前，需要初始化K个聚类中心，但是聚类中心选择不好，对于K-Means算法由很大的影响。样本的最终聚类在某种程度上依赖于最初的划分，或种子的选择。为了检验聚类的稳定性，可用一个新的初始分类重新检验整个聚类算法。如最终分类与原来不一样，则不必计算；否则，须另行考虑聚类算法。

例如，在python中，某篮球联赛共计257名篮球运动员，表1中展示了他们的赛绩得分(PPG)、场均篮板(RPG)和场均助攻(ARG)的前10条记录，对表1中的球员场均得分、篮板助攻的数据采用K-Means聚类法对球员进行聚类，指定聚类的个数k=2。

表1 球员场均得分篮板助攻数据

import numpy as np
import scipy.cluster.vq as vq
import matplotlib.pylab as plt
ball = np.loadtxt(r'C:\Users\xpp\Desktop\basketball.csv ', delimiter= ',')
# 对数据进行单位化
data1 = vq.whiten(ball)  
kmeans_cent2 = vq.kmeans(data1, 2)
print('聚类中心为：\n', kmeans_cent2[0])
# 画出单位化后和聚类中心的散点图
p = plt.figure(figsize=(9,9))
for i in range(3):
    for j in range(3):
        ax = p.add_subplot(3,3,i*3+1+j)
        plt.scatter(data1[:, j], data1[:, i])
        plt.scatter(kmeans_cent2[0][:, j], 
                    kmeans_cent2[0][:, i], c='r')
plt.savefig('C:/Users/xpp/Desktop/K-Means聚类法聚类结果.png')
plt.show()

为了解决因为初始化的问题带来K-Means算法的问题，因此改进了K-Means算法，即K-Means++算法被提出。K-Means++算法主要是为了能够在聚类中心的选择过程中选择较优的聚类中心。

2.K-Means++算法

在聚类中心的初始化过程中，K-Means++算法的基本原则是使初始的聚类中心之间的相互距离尽可能远，这样可以避免出现K-Means算法问题。

2.1K-Means++算法流程

K-Means++算法是一种基于K-Means改进的算法，主要思想是：初始的聚类中心之间的相互距离尽可能地远。首先根据专家经验选取第一个种子点，然后从距离第一个种子点较远的这些数据中根据权重随机选取一个种子点，重复以上步骤，直到选取的种子点个数满足要求为止。

K-Means++算法的初始化过程为：在数据集中随机选择一个样本点作为第一个初始化的聚类中心，选择出其余的聚类中心；计算样本中的每一个样本点与已知初始化的聚类中心之间的距离，并选择其中最短的距离记为di；以概率选择距离最大的样本作为新的聚类中心，重复上述过程，直到K个聚类中心都被确定；对K个初始化的聚类中心，；利用K-Means算法计算最终的聚类中心。在上述的K-Means++算法中可知K-Means++算法与K-Means算法最本质的区别是在K个聚类中心的初始化过程。

K-Means算法的主要工作体现在种子点的选择上，基本原则是使各个种子点的距离尽可能地大，但是需要排除噪声的影响。以下为基本思路：

(1)从输入的数据点集合(要求有K个聚类)中随机选择一个点作为第一个聚类中心；

(2)对于数据集中的每一个点x，计算它与最近聚类中心(指已选择地剧烈中心)的距离D(x)；

(3)选择一个新的数据点作为新的聚类中心，选择的原则是：D(x)较大的点，被选取作为聚类中心的概率较大；

(4)重复(2)步和(3)步，直到K个聚类中心被选出来；

(5)利用这K个初始的聚类中心来进行标准的K-Means算法。

K-Means++算法是K-Means算法的改进，是解决初始化种子点的问题，其选择初始种子点的基本思想就是初始的聚类中心之间的相互距离尽可能地远。该算法的描述是：从输入的数据点集合中随机选择一个点作为第一个聚类中心；对于数据集中的每一个点x，计算它与最近聚类中心(指已选择的聚类中心)的距离D(x)；选择一个新的数据点作为新的聚类中心，选择的原则是D(x)较大的点，被选取作为聚类中心的概率较大，重复图4中的第2步和第4步，直到K个聚类中心被选出来；利用这K个初始的聚类中心运行标准的K-Means算法。具体的算法流程：

图4 K-Means++算法流程

与K均值聚类算法相比较，它在下列几个方面做了改进：

(1)考虑了类别的合并与分裂，因而有了自我调整类别数的能力。合并主要发生在某一类别数的能力。合并主要发生在某一类内样本个数太少的情况，或两类聚类中心之间距离太小的情况，为此设有最小类内样本数限制，以及类间中心距离参数。若出现两类聚类中心距离较小的情况，可考虑将此两类合并。分类主要发生在某一类别的某分量出现类内方差过大的情况下，因而宜分裂成两个类别，以维持合理的类内方差。需要给出一个对类内分量方差的限制参数，用以决定是否需要将某一类分裂成两类；

(2)易于算法由自我调整的能力，因而需要设置若干个控制参数，如聚类期望值，每次迭代允许合并的最大聚类对数，及允许迭代次数等。

模糊K均值算法虽然相对高效并应用广泛，但是仍有许多问题需要解决：

(1)Bezdek使用模糊划分的概念在FCM算法的目标中引入了新的参数-模糊指标k，该参数严重影响这FCM的性能。因此，如何选择合适的模糊指标k，是有效使用FCM必须面对的问题。于剑等人于2004年提出了基于Hessian矩阵的FCM算法模糊指数分析方法，从理论上提出了FCM算法模糊指数的取值范围；

(2)FCM聚类算法采用欧几里得距离作为相似度量，适用于每类为球形且类内紧密，类间距大的数据，不能处理非常凸形状的数据。因此选用不同的数据度量(相似度度量)可用来发现不同结构的数据集。另外，算法对孤立点是敏感的。针对于此，文献中有很多对FCM算法距离度量函数的讨论。最为经典的对FCM算法距离函数的改进是GK聚类算法，该算法由Gustafson和Kessel于1978年提出；

(3)与硬划分等其他聚类算法类似，FCM算法需要预先划分类的个数C并进行初始化。目前，尚没有很好地确定聚类个数的方法。有些文献通过聚类中心的合并等思想，避免聚类中心初始化。这类算法也得到了比较广泛的应用。FCM算法是寻找气候吸引子和气候突变的有效方法。这种方法根据量化成等级的历史气候资料，统计特定地区在一定长度内各旱涝等级发生的概率，然后根据所定义的时段找到聚类中心，确定吸引子的特点，进而划分气候演化时段。如我国2000年以来旱涝时空演化规律研究中，利用模糊动态聚类算法发现，2000年以来气候系统主要的一次变化发生在1230年前后。1230年以前旱、涝多发，且气候时段持续时间较短，转换较快，因此气候时段较多。1230年以后旱灾多发，涝灾多发，单个气候时段的持续时间加长，气候状态发生转变次数较少，因而气候时段也较少，标志着气候系统在一个长得多的准周期轨道上运行。在进行图片匹配时，根据队列图片与图片库的距离远近进行特征排列，然后对排列的队列进行KNN聚类，从而确定图片最终归属于哪个类，如ABBYY的检索结果(图5)。

图5 ABBYY的检索结果

衡量聚类算法优劣的标准：

(1)处理大的数据集的能力；

(2)处理任意形状，包括有间隙的嵌套的数据的能力；

(3)算法处理的结果与数据输入的顺序是否相关；

(4)处理数据噪声的能力；

(5)是否需要预先直到聚类个数，是否需要用户给出领域知识；

(6)对数据维度是否敏感。

系统聚类法和动态聚类法的优缺点：

系统聚类法

优点：可解释性好，可以优先考虑先取K比较大的K-Means后，合并阶段用系统聚类也能产生更高质量的聚类。

缺点：时间复杂度高。

动态聚类法：优点：适用于大样本的Q型聚类分析。Q型系统聚类法一般是在样品间距离矩阵的基础上进行的，故当样品的个数n很大(如n≥100)时，系统聚类法的计算量是非常大的，将占据大量的计算机内存空间和较多的计算机时间，甚至会因计算机内存或计算机时间的限制而无法进行。因此，当n很大时，我们自然需要一种相比系统聚类法而言计算量少得多，以致计算机运行时只需占用较少的内存空间和较短计算时间的聚类法。动态聚类法正是基于这种考虑而产生的一种方法。由于该方法不必确定距离矩阵，在计算机运行中不必存储基本数据，因此同系统聚类法相比，这种方法更适用于大的数据集，而且n越大，它的优越性就越突出。大型数据一般较集中，异常值影响较弱。算法简单高效，时间复杂度低。

缺点：依赖初始点的选取或依赖于初始划分，容易落入局部最优，对噪声和利群值敏感。