聚类分析算法.doc

第二章 聚 类 分 析24 聚类的算法2.4.1 聚类的技术方案1 简单聚类 根据相似性阈值和最小距离原则聚类xiW= x1,x2,xn = w1w2wc；if D(xi,mj)T, mj=(1/nj)Sxi(j)，xi(j) wj，nj是wj中的样本个数，T是给定的阀值。Then xiwi类心一旦确定将不会改变。2 谱系或层次聚类 按最小距离原则不断进行两类合并类心不断地修正，但模式类别一旦指定后就不再改变。3 依据准则函数动态聚类 影响聚类结果的主要因数：类心、类别个数、模式输入顺序。所谓动态聚类，是指上述因数在聚类过程中是可变的。规定一些分类的目标参数，定义一个能刻划聚类过程或结果优劣的准则函数，聚类过程就是使准则函数取极值的优化过程。这类方法有均值法、ISODATA法、近邻函数法以及运用图论理论的最小张树法。 2.4.2 简单聚类方法 根据相似性阈值和最小距离原则的简单聚类方法 条件及约定设待分类的模式为，选定类内距离门限。 算法思想 计算模式特征矢量到聚类中心的距离并和门限比较而决定归属该类或作为新的一类中心。通常选择欧氏距离。 算法原理步骤 取任意的一个模式特征矢量作为第一个聚类中心。例如，令第一类的中心。 计算下一个模式特征矢量到的距离。若，则建立新的一类，其中心；若，则。 假设已有聚类中心，计算尚未确定类别的模式特征矢量到各聚类中心的距离，如果，则作为新的一类的中心，；否则，如果 ( 2-4-1)则指判。检查是否所有的模式都分划完类别，如都分划完了则结束；否则返到。 性能l 计算简单。 l 聚类结果很大程度上依赖于距离门限的选取、待分类特征矢量参与分类的次序和聚类中心的选取。 当有特征矢量分布的先验知识来指导门限及初始中心的选取时，可以获得较合理结果。 改进 通常采用试探法，选用不同的门限及模式输入次序来试分类，并对聚类结果进行检验,即用聚类准则函数J1。例如，计算每一聚类中心与该类中最远样本点的距离，或计算类内及类间方差，用这些结果指导及的重选。最后对各种方案的划分结果进行比较，选取最好的一种聚类结果。 图 (2-4-1) 距离阈值及初始类心对聚类的影响 最大最小距离算法 条件及约定设待分类的模式特征矢量集为，选定比例系数。 基本思想在模式特征矢量集中以最大距离原则选取新的聚类中心，以最小距离原则进行模式归类。这种方法通常也使用欧氏距离。 算法原理步骤 选任一模式特征矢量作为第一个聚类中心。例如，。 从待分类矢量集中选距离最远的特征矢量作为第二个聚类中心。例如图( 2-4-2)中最大，取。 计算未被作为聚类中心的各模式特征矢量与、之间的距离并求出它们之中的最小值，即 ( 2-4-2)为表述简洁，虽然某些模式已选做聚类中心，但上面仍将所有模式下角标全部列写出来，因这并不影响算法的正确性。4 若 ( 2-4-3)则相应的特征矢量作为第三个聚类中心，。此例中。然后转至；否则，转至最后一步。 设存在个聚类中心，计算未被作为聚类中心的各特征矢量到各聚类中心的距离,并算出 ( 2-4-4)如果，则并转至；否则，转至最后一步。 当判断出不再有新的聚类中心之后，将模式特征矢量按最小距离原则分到各类中去，即计算 ( 2-4-5)当，则判。在此例中，；，；，。 这种算法的聚类结果与参数以及第一个聚类中心的选取有关。如果没有先验知识指导和的选取，可适当调整和，比较多次试探分类结果，选取最合理的一种聚类。 图 (2-4-2) 最大最小距离算法举例2.4.3 谱系聚类法(Hierarchical Clustering Method)(系统聚类法、层次聚类法） 效果较好、是常用方法之一。 条件及约定 设待分类的模式特征矢量为，表示第k次合并时的第类。 基本思想 首先将个模式视作各自成为一类，然后计算类与类之间的距离，选择距离最小的一对合并成一个新类，计算在新产生的类别分划下各类之间的距离，再将距离最近的两类合并，直至所有模式聚成两类为止。 算法步骤1 初始分类。令，每个模式自成一类，即。 2 计算各类间的距离，生成一个对称的距离矩阵，为类的个数。 找出前一步求得的矩阵中的最小元素，设它是和间的距离，将和两类合并成一类，于是产生新的聚类，令。 检查类的个数。如果类数大于2，令，转至；否则，停止。 如果某一循环中具有最小类间距离不止一个类对，则对应这些最小距离的类可以同时合并。上述算法步骤给出了从类至类的完整聚类过程， 停止条件l 以类间距离门限作为停止条件，即取距离门限，当中最小阵元大于时，聚类过程停止； l 以预定的类别数目作为停止条件，当类别合并过程中，类数等于预定值时，聚类过程停止。 类间距离的定义与递推在该算法中可以采用上节已详细介绍过的不同的类间距离定义方式，并使用类间距离递推公式。所采用的类间距离定义不同，聚类过程及结果是不一样的。上述算法在归并的每次迭代过程中，距离矩阵的最小元素值不断地改变，如果有单调不减关系则称类间距离对并类具有单调性。最近距离法、最远距离法、平均法及离差平方和法等定义的类间距离都具有这个性质，而重心法没有这个性质。算法特点聚类过程中类心不断地调整，但某一模式一旦分划到某一类中就不再改变。从粗到细的层次聚类这类技术的另一个算法和上述算法过程相反，依据类的离差平方和递推公式按类至类进行谱系分解，这里不作介绍了。聚类过程可以表示成一个树图。 例：给出个样本特征矢量如下，按最小距离原则进行聚类。 解： 将每一样本看成自成一类 计算距离矩阵(表 2-4-1)。 中最小阵元为它是与之间的距离，将它们合并为一类，得一新的分类为 计算合并后的距离矩阵(表 2-4-2)。在这里使用了距离递推公式，如与距离，与距离 中距离最小者为它是与间的距离，合并和，得新的分类 同样计算(表 2-4-3)，进一步聚类得 即 计算(表 2-4-4)。 由表可知，、和可以一起合并成一类。 表(2-4-1)表(2-4-2) 表(2-4-3) 表(2-4-4) 2.4.4 动态聚类法(Dynamic clustering algorithm)最大距离和层次聚类算法的一个共同特点是某个模式一旦划分到某一类之后，在后继的算法过程中就不改变了，而简单聚类算法中类心一旦选定后在后继算法过程中也不再改变了，这类方法效果一般不会太理想。和上述各算法相对应有一种动态聚类法。其要点为：1 确定模式和聚类的距离测度。当采用欧氏距离时，是计算此模式和该类中心的欧氏距离；为能反映出类的模式分布结构，应采用马氏距离，设该类的均矢为，协方差阵为，则模式和该类的距离平方为与该类均矢的马氏距离 2 确定评估聚类质量的准则函数。 3 确定模式分划及聚类合并或分裂的规则。 动态聚类算法的基本步骤：1 建立初始聚类中心，进行初始聚类； 2 计算模式和类的距离，调整模式的类别； 3 计算各聚类的参数，删除、合并或分裂一些聚类； 4 从初始聚类开始，运用迭代算法动态地改变模式的类别和聚类的中心使准则函数取得极值或设定的参数达到设计要求时停止。 动态聚类原理框图如下：图 (2-4-3) 均值法(means) 条件及约定 设待分类的模式特征矢量集为，类的数目是取定的。 基本思想 取定c个类别和选取个初始聚类中心，按最小距离原则将各模式分配到类中的某一类，不断地计算类心和调整各模式的类别使每个模式特征矢量到其所属类别的距离平方之和最小 算法步骤 任选个模式特征矢量作为初始聚类中心：。 将待分类的模式特征矢量集中的模式逐个按最小距离原则分划给类中的某一类，即 如果 ( 2-4-6)则判 。 式中表示和的中心的距离，上角标表示迭代次数。于是产生新的聚类。 计算重新分类后的各类心 ( 2-4-7)式中为类中所含模式的个数。 因为这一步采取平均的方法计算调整后类的中心，且定为类，故称一均值法。 如果()，则转至；如果，则结束。 分析我们以欧氏距离为例，简单地分析该算法的可收敛性。在上述算法中，虽然没有直接运用准则函数 ( 2-4-8)进行分类，但在中根据式(2-4-6)进行模式分划可使趋于变小。设某样本从聚类移至聚类中，移出后的集合记为，移入后的集合记为。设和所含样本数分别为和，聚类、和的均矢分别为、和，显然有 ( 2-4-9) ( 2-4-10)而这两个新的聚类的类内欧氏距离(平方)和与原来的两个聚类的类内欧氏距离(平方)和的关系是 ( 2-4-11) ( 2-4-12)当距比距更近时，使得 ( 2-4-13)由式(2-4-11)、(2-4-12)及(2-4-13)可知，将分划给类可使变小。这说明在分类问题中不断地计算新分划的各类的类心，并按最小距离原则归类可使值减至极小值。在上述算法中，也可以利用式(2-4-13)进行模式类别的重新分划。 性能l 算法简单，收敛（已于1974年和1967年分别给出了严格证明）。如模式分布呈现类内团聚状，该算法是能达到很好聚类结果的，故应用较多。l 能使各模式到其所判属类别中心距离(平方)之和为最小的最佳聚类。以确定的类数、模式输入次序及选定的初始聚类中心为前提，受此限制结果只是局部最优。 改进 的调整 作一条一曲线，其曲率变化的最大点对应的类数是比较接近最优的类数。 在类别数未知的情况下，可使类数由较小值逐步增加，对于每个选定的分别使用该算法。显然准则函数是随的增加而单调减少。在增加过程中，总会出现使本来较密集的类再拆开的情况，此时J虽减小，但减小速度将变缓。如果作一条一曲线，其曲率变化的最大点对应的类数是比较接近最优的类数。然而在许多情况下，曲线并无明显的这样的点。另一种方法是利用问题的先验知识分析选取合理的聚类数。 初始聚类中心选取 初始聚类中心可按以下几种方法之一选取： 凭经验选择初始类心。 将模式随机地分成类，计算每类中心，以其作为初始类心。 （最大密度），求以每个特征点为球心、某一正数为半径的球形域中特征点个数，这个数称为该点的密度。选取密度最大的特征点作为第一个初始类心，然后在与大于某个距离的那些特征点中选取具有“最大”密度的特征点作为第二个初始类心，如此进行，选取个初始聚类中心。 4 用相距最远的个特征点作为初始类心。具体地讲，是按前述的最大最小距离算法求取个初始聚类中心。 5 当较大时，先随机地从个模式中取出一部分模式用谱系聚类法聚成类，以每类的重心作为初始类心。 设已标准化的待分类模式集为，希望将它们分为类。令模式 ，定义 ( 2-4-14)且令 ( 2-4-15) ( 2-4-16)计算 ( 2-4-17)显然，若最接近整数，则把分划至中。对所有样本都实行上述处理，就可实现初始分类，从而产生初始聚类中心。 用类核代替类心前面的算法存在一个不足，即是只用一个聚类中心点作为一类的代表，但是一个点往往不能充分地反映该类的模式分布结构，从而损失很多有用的信息。当类的分布是球状或近似球状时，算法尚能有较好的效果，但对于如图(2-4-4)所示的那种各分量方差不等的正态分布而两类的主轴和类心又是那样的情况，分类效果就不好了，点应属于类，但由于它距类的均矢更近，按前述的算法则被指判到类。如果已知各类模式分布的某些知识，则可以利用它们指导聚类。为此，我们定义一个类核函数表示类的模式分布情况，其中关于类的一个参数集，是维空间中的特征矢量，可以是一个函数、一个点集或其他适当的模型。为了刻划待识模式和类的接近程度还应规定一个模式特征矢量到核的距离。实际上，马氏距离就是核函数距离的一种简化。 当已知某类的分布近似为正态分布时，可以用以这类样本统计估计值为参数的正态分布函数作为核函数，即 ( 2-4-18)其中， 式中为进行参数估计的该类样本数。则模式与该类的距离为 ( 2-4-19)这实际上是第四章将要讨论的最小误判概率准则下先验概率相同时的判决函数。当已知各类样本分别在相应的主轴附近分布时，可以定义主轴核函数： ( 2-4-20)式中，是由和类的统计协方差阵的个最大特征值所对应的已规格化的特征矢量作成的矩阵，即是协方差阵给出的部分主轴系统，给出了样本分布的主轴方向(散布的情况由特征值反映出来)。为轴上的单位矢量。设是类样本的均值矢量，求一点和一个轴的距离可见图( 2-4-5)。模式和类间的距离平方可以用和该类的主轴间的欧氏距离平方来度量。 ( 2-4-21)(a) 各分量方差不等的正态分布(b) 沿主轴分布图 (2-4-4) 类的模式分布情况的示例图 (2-4-5) 求和主轴距离示意图例：模式分布如图(2-4-6)所示，试用一均值法进行聚类，取=2。 选 因，故 ，故 ，故 得，；， 计算新的聚类中心 因，故转至。 由新的聚类中心，得 故得， ， 计算聚类中心 因，故转至。 求得的分类结果与前一次的结果相同，。 各聚类中心必然也与前一次的相同，。 因，不再出现新的类别划分，故分类过程结束。 2 改进的均值法 文献【10】基于核函数的概念提出了一种改进的均值法，其分类性能要好于通常计算模式到类的距离时采用这个模式到类心的欧氏距离或马氏距离的均值法。 由于均值法我们已作详细介绍，这种改进的均值法只简单表述如下： 1 对给定的待分类模式集进行初始分划产生类； 2 计算各聚类所含模式数、均值矢量和协方差阵； 3 将各模式按最小距离原则分划到某一聚类中。这里采用最小误判概率准则下正态分布情况的判决规则，计算模式到的距离 ( 2-4-22)如果 则判 如果没有模式改变其类别，则停止算法；否则转至。（三） ISODATA(迭代自组织数据分析)算法(Iterative Self-Organizing Data Analysis Techniques Algorithm)特点：具有启发性推理、分析监督、控制聚类结构及人机交互。 条件及约定设待分类的模式特征矢量为，算法运行前需设定7个初始参数。 算法思想在每轮迭代过程中，样本重新调整类别之后计算类内及类间有关参数，并和设定的门限比较，确定是两类合并为一类还是一类分裂为两类，不断地“自组织”，以达到在各参数满足设计要求条件下，使各模式到其类心的距离平方和最小。 算法原理步骤 预置 设定聚类分析控制参数： =预期的类数， =初始聚类中心个数(可以不等于)， =每一类中允许的最少模式数目(若少于此数就不能单独成为一类)， =类内各分量分布的距离标准差上界(大于此数就分裂)， =两类中心间的最小距离下界(若小于此数，这两类应合并)， =在每次迭代中可以合并的类的最多对数， =允许的最多迭代次数。 将待分类的模式特征矢量读入。 选定初始聚类中心，可从待分类的模式特征矢量集中任选个模式特征矢量作为初始聚类中心。 按最小距离原则将模式集中每个模式分到某一类中，即 如果 ( 2-4-23) 则判 式中表示和类的中心之间的距离。 依据判断合并。如果类中样本数，则取消该类的中心，转至(或计算，将并入距离最近的那一类中；这时，转至。 计算分类后的参数:各类中心、类内平均距离及总体平均距离。 计算各类的中心 ( 2-4-24) 计算各类中模式到类心的平均距离 ( 2-4-25) 计算各个模式到其类内中心的总体平均距离 ( 2-4-26) 依据、判断停止、分裂或合并。 若迭代次数已达，则置转到；否则转下。 若则转到(将一些类分裂)；否则转下。 若,(则跳过分裂处理)转至,否则转下。 若，当迭代次数是奇数时转至(分裂处理)；迭代次数是偶数时转至(合并处理)。 计算各类类内距离的标准差矢量 ( 2-4-27)其各分量 ( 2-4-28)式中，为分量编号，为类的编号，为矢量维数，是的第个分量，是的第个分量。 对每一聚类，求出类内距离标准差矢量中的最大分量 ( 2-4-29) 在中，对任一，若有，同时又满足下面两个条件之一： 1 和 2 则将该类分裂为两个聚类，且令。这两个新类的中心和是这样构成的：和只是在中相应于的分量分别加上和减去，而其它分量不变，其中，的选取应使和仍在的类域空间中且其它类的模式到和距离较远，而原类中的模式和它们距离较小。分裂后，转至；否则，转下。 计算各对聚类中心间的距离( 2-4-30) 依据判断合并。将与比较，并将小于的那些按递增次序排列，取前个，。从最小的开始，将相应的两类合并。若原来的两个类心为和，则合并后的聚类中心为 ( 2-4-31)（已并掉的类数）。在一次迭代中，某一类最多只能被合并一次。 如果迭代次数已达次