聚类分析算法

1、第二章聚类分析聚类的算法聚1类的技术方案简单聚类根据相似性阈值和最小距离原则聚类WQ,u,uu,；(,e,是,中的样本个数，是给定的阀值。e,类心一旦确定将不会改变。谱系或层次聚类按最小距离原则不断进行两类合并类心不断地修正，但模式类别一旦指定后就不再改变。依据准则函数动态聚类影响聚类结果的主要因数：类心、类别个数、模式输入顺序。所谓动态聚类，是指上述因数在聚类过程中是可变的。规定一些分类的目标参数，定义一个能刻划聚类过程或结果优劣的准则函数，聚类过程就是使准则函数取极值的优化过程。这类方法有一均值法、法、近邻函数法以及运用图论理论的最小张树法。简2单聚类方法根据相似性阈值和最小距离原则的简单

2、聚类方法条件及约定设待分类的模式为区冠巫,选定类内距离门限f。算法思想计算模式特征矢量到聚类中心的距离并和门限F比较而决定归属该类或作为新的一类中心。通常选择欧氏距离。算法原理步骤取任意的一个模式特征矢量作为第一个聚类中心。例如，令第一类朗的中心岔二石。（2）计算下一个模式特征矢量鬲到筍的距离血1。若比，则建立新的一类2，其中心苍=為；若込1兰T，则為已1。假设已有聚类中心耳知恙，计算尚未确定类别的模式特征矢量爲到各聚类中心幻（厂12我）的距离珀，如果轴（丿=12我），则爲作为新的一类孤+i的中心，茲；否则，如果则指判爲。检查是否所有的模式都分划完类别，如都分划完了则结束；否则返到。性能计算简

3、单。聚类结果很大程度上依赖于距离门限F的选取、待分类特征矢量参与分类的次序和聚类中心的选取。当有特征矢量分布的先验知识来指导门限F及初始中心云的选取时，可以获得较合理结果。改进通常采用试探法，选用不同的门限及模式输入次序来试分类，并对聚类结果进行检验即用聚类准则函数。例如，计算每一聚类中心与该类中最远样本点的距离，或计算类内及类间方差，用这些结果指导F及筍的重选。最后对各种方案的划分结果进行比较，选取最好的一种聚类结果。图(2-4距-离1阈)值及初始类心对聚类的影响最大最小距离算法条件及约定设待分类的模式特征矢量集为区耳瓦，选定比例系数B。基本思想在模式特征矢量集中以最大距离原则选取新的聚类中

4、心，以最小距离原则进行模式归类。这种方法通常也使用欧氏距离。3.算法原理步骤3.算法原理步骤选任一模式特征矢量作为第一个聚类中心爲。例如，爲二瓦。从待分类矢量集中选距离爲最远的特征矢量作为第二个聚类中心爲。例如图中如图中-2)最大，取爲二焉。计算未被作为聚类中心的各模式特征矢量朝与云、苍之间的距离并求出它们之中的最小值，即dv=为表述简洁，虽然某些模式已选做聚类中心，但上面仍将所有模式下角标全部列写出来，因这并不影响算法的正确性。若町=maxmin(dn,di2)创屋-刼|则相应的特征矢量耳作为第三个聚类中心，召二石。此例中务二爲。然后转至;否则，转至最后一步。设存在此个聚类中心，计算未被作为

5、聚类中心的各特征矢量到各聚类中心的距离箱并算出跆X4圖-距11跆X4圖-距11盘远选为Z287图最-大2最）小距离算法举例如果必临一羽，则心并转至；否则，转至最后一步。当判断出不再有新的聚类中心之后，将模式特征矢量兀兀，曲；按最小距离原则分到各类中去，即计算（=12；心12,当妒啰囲，则判羌书。在此例中，石届届已1，云=兀；国心亡2,z2X6；兀5，為，io已39;z3X7，O这种算法的聚类结果与参数B以及第一个聚类中心的选取有关。如果没有先验知识指导8和云的选取，可适当调整&和云，比较多次试探分类结果，选取最合理的一种聚类。Xi：（OnO）期彩）纽：（询皿,3）圖：（4腐:6,3）躊:5,4

6、）砂尬4）血亿5）.谱.谱3系聚类法法)系统聚类法、层次聚类效果较好、是常用方法之一。条件及约定设待分类的模式特征矢量为国冠，胡，严表示第次合并时的第I类。基本思想首先将“个模式视作各自成为一类，然后计算类与类之间的距离，选择距离最小的一对合并成一个新类，计算在新产生的类别分划下各类之间的距离，再将距离最近的两类合并，直至所有模式聚成两类为止。算法步骤初始分类。令0,每个模式自成一类，即潭f计算各类间的距离，生成一个对称的距离矩阵沙742,m为类的个数。找出前一步求得的矩阵岀)中的最小元素，设它是叫和於间的距离,将即和两类合并成一类，r-d.t+l).-ffUl)将即和两类合并成一类，于是产生

7、新的聚类检查类的个数。如果类数擁大于2令花十，转至；否则，停止。如果某一循环中具有最小类间距离不止一个类对，则对应这些最小距离的类可以同时合并。上述算法步骤给出了从类至2类的完整聚类过程，停止条件以类间距离门限丁作为停止条件，即取距离门限，当口中最小阵元大于丁时，聚类过程停止；以预定的类别数目作为停止条件，当类别合并过程中，类数等于预定值时，聚类过程停止。类间距离的定义与递推在该算法中可以采用上节已详细介绍过的不同的类间距离定义方式，并使用类间距离递推公式。所采用的类间距离定义不同，聚类过程及结果是不一样的。上述算法在归并的每次迭代过程中，距离矩阵的最小元素值不断地改变，如果有单调不减关系则称

8、类间距离对并类具有单调性。最近距离法、最远距离法、平均法及离差平方和法等定义的类间距离都具有这个性质，而重心法没有这个性质。算法特点聚类过程中类心不断地调整，但某一模式一旦分划到某一类中就不再改变。从粗到细的层次聚类这类技术的另一个算法和上述算法过程相反，依据类的离差平方和递推公式按1类至类进行谱系分解，这里不作介绍了。聚类过程可以表示成一个树图。例：给出6个样本特征矢量如下，按最小距离原则进行聚类。瓦=（1丄020）礼=（H212iy焉=（4,1,1丄0）解：将每一样本看成自成一类局色=為七6叽伉色性和计算距离矩阵表4曲中最小阵元为低它是甲与身之间的距离，将它们合并为一类,得一新的分类为甲斗

9、型烤卜隐鬲驾制理=當甲斗型烤卜隐鬲驾制理=當计算合并后的距离矩阵门表卑制）題=當。-在2这）里使用了距离递推公式，如瑙=rnrn型与第）距离，酸）与逡1距离=rnrn/15,-76）=肝邛中距离最小者为折，它是谓）与帶间的距离，合并第）和电），得新的分类同样计算门表，进一步聚类得同样计算门表，进一步聚类得呼）=申）,曙）常）=今常）二皆即即计算门表，计算门表，由表可知，空、霍）和霍可以一起合并成一类。表4-表-表-表表4-表-表-表-3动4态聚类法最大距离和层次聚类算法的一个共同特点是某个模式一旦划分到某一类之后，在后继的算法过程中就不改变了，而简单聚类算法中类心一旦选定后在后继算法过程中也不

10、再改变了，这类方法效果一般不会太理想。和上述各算法相对应有一种动态聚类法。其要点为：确定模式和聚类的距离测度。当采用欧氏距离时，是计算此模式和该类中心的欧氏距离；为能反映出类的模式分布结构，应采用马氏距离，设该类的均矢为口，协方差阵为贝醮式和该类的距离平方为与该类均矢口的马氏距离应2=亍一口）逞（壬一辽）确定评估聚类质量的准则函数。确定模式分划及聚类合并或分裂的规贝。动态聚类算法的基本步骤：建立初始聚类中心，进行初始聚类；计算模式和类的距离，调整模式的类别；计算各聚类的参数，删除、合并或分裂一些聚类；从初始聚类开始，运用迭代算法动态地改变模式的类别和聚类的中心使准贝函数取得极值或设定的参数达到

11、设计要求时停止。动态聚类原理框图如下：图匚一均值法（条件及约定设待分类的模式特征矢量集为区冠為，类的数目。是取定的。基本思想取定个类别和选取。个初始聚类中心，按最小距离原则将各模式分配到。类中的某一类，不断地计算类心和调整各模式的类别使每个模式特征矢量到其所属类别的距离平方之和最小,算法步骤任选。个模式特征矢量作为初始聚类中心:带左沽刖。将待分类的模式特征矢量集国中的模式逐个按最小距离原则分划给。类中的某一类，即则判召十。式中硝表示吾和时的中心跻的距离，上角标表示迭代次数。于是产生新的聚类呼in。计算重新分类后的各类心式中挖畀）为呼类中所含模式的个数。因为这一步采取平均的方法计算调整后类的中心

12、，且定为。类，故称一均值法。如果工勺，则转至；如果勺则结束。如果工勺，则转至；如果勺则结束。分析我们以欧氏距离为例，简单地分析该算法的可收敛性。在上述算法中，虽然没有直接运用准则函数进行分类，但在中根据式进行模式分划可使严）趋于变小。设某样本石从聚类叫移至聚类孤中，叫移出石后的集合记为為，喩移入石后的集合记为娥。设叫和叫所含样本数分别为和叫，聚类叫、爲、叫和娥的均矢分别凤和,显然有凤和,显然有而这两个新的聚类的类内欧氏距离平方几和人与原来的两个聚类的类内欧氏距离平方心和人的关系是石7十2严距忍比距劭更近时，使得由式-及可知，将瓦分划给喩类可使J变小。这说明在分类问题中不断地计算新分划的各类的类

13、心，并按最小距离原则归类可使值减至极小值。在上述算法中，也可以利用式（2-4进-行1模3式）类别的重新分划性能算法简单，收敛（已于年和年分别给出了严格证明）。如模式分布呈现类内团聚状，该算法是能达到很好聚类结果的，故应用较多。能使各模式到其所判属类别中心距离平方之和为最小的最佳聚类。以确定的类数C、模式输入次序及选定的初始聚类中心为前提，受此限制结果只是局部最优。改进二的调整作一条一曲线，其曲率变化的最大点对应的类数是比较接近最优的类数。在类别数未知的情况下，可使类数c由较小值逐步增加，对于每个选定的c分别使用该算法。显然准则函数是随。的增加而单调减少。在。增加过程中，总会出现使本来较密集的类

14、再拆开的情况，此时虽减小，但减小速度将变缓。如果作一条。一曲线，其曲率变化的最大点对应的类数是比较接近最优的类数。然而在许多情况下，曲线并无明显的这样的点。另一种方法是利用问题的先验知识分析选取合理的聚类数。初始聚类中心选取初始聚类中心可按以下几种方法之一选取：凭经验选择初始类心。将模式随机地分成类，计算每类中心，以其作为初始类心。（最大密度）,求以每个特征点为球心、某一正数为半径的球形域中特征点个数，这个数称为该点的密度。选取密度最大的特征点作为第一个初始类心卸），然后在与計）大于某个距离川的那些特征点中选取具有“最大”密度的特征点作为第二个初始类心硏，如此进行，选取个初始聚类中心。用相距最

15、远的。个特征点作为初始类心。具体地讲，是按前述的最大最小距离算法求取个初始聚类中心。当N较大时，先随机地从个模式中取出一部分模式用谱系聚类法聚成c类，以每类的重心作为初始类心。设已标准化的待分类模式集为国怎為，希望将它们分为。类。令模式吨）=迟恥令模式吨）=迟恥.（:-1，定义且令MA=maxs(z)MA=maxs(z)计算显然-C,若务最接近整数，则把石分划至吗中。对所有样本都实行上述处理，就可实现初始分类，从而产生初始聚类中心。用类核代替类心前面的算法存在一个不足，即是只用一个聚类中心点作为一类的代表，但是一个点往往不能充分地反映该类的模式分布结构，从而损失很多有用的信息。当类的分布是球状

16、或近似球状时，算法尚能有较好的效果，但对于如图（2-4所-示的那种各分量方差不等的正态分布而两类的主轴和类心又是那样的情况，分类效果就不好了，/点应属于朗类，但由于它距禺类的均矢更近，按前述的算法则被指判到朗类。如果已知各类模式分布的某些知识，则可以利用它们指导聚类。为此，我们定义一个类核函数岛二禺元？1表示类吗的模式分布情况，其中厂关于类叫的一个参数集，是挖维空间中的特征矢量，岛可以是一个函数、一个点集或其他适当的模型。为了刻划待识模式和吗类的接近程度还应规定一个模式特征矢量到核岛的距离把区。实际上，马氏距离就是核函数距离的一种简化。当已知某类的分布近似为正态分布时，可以用以这类样本统计估计

17、值为参数的正态分布函数作为核函数，即其中式中勺为进行参数估计的该类样本数。则模式亍与该类的距离为这实际上是第四章将要讨论的最小误判概率准则下先验概率相同时的判决函数。当已知各类样本分别在相应的主轴附近分布时，可以定义主轴核函数：Kxy；=Ux式中，mx耳）是由和叫类的统计协方差阵爲的狰禺）个最大特征值所对应的已规格化的特征矢量作成的矩阵，即6是协方差阵乌给出的部分主轴系统，斑，叫）给出了样本分布的主轴方向散布的情况由特征值反映出来）区为碍轴上的单位矢量。设耳是类样本的均值矢量，求一点和一个轴码的距离可见图-模式和吗类间的距离平方可以用和该类的主轴间的欧氏距离平方来度量。dl（%=贋-耳）-Up

18、f/.x-耳）肪-禺）-UJJ伝-禺）各分量方差不等的正态分布）沿主轴分布）各分量方差不等的正态分布）沿主轴分布类-的4模）式分布情况的示例求-和5主）轴距离示意图例：模式分布如图所-例：模式分布如图所-示6，试用。一均值法进行聚类，取。器丄石=器丄石=（o,oyz=x2=(y牡=聲屁站=2.中=鬲忑，屁JN2=，计算新的聚类中心m5.33,m5.33,因孝工踏（Tt），故转至。由新的聚类中心，得何护卜何即|心1,2,说故得计算聚类中心.2驴JO（4）因聲f七），故转至。求得的分类结果与前一次的结果相同，呼二呼各聚类中心必然也与前一次的相同，不再出现新的类别划分，故分类过程结束。因*X1Q*X

19、各聚类中心必然也与前一次的相同，不再出现新的类别划分，故分类过程结束。因*X1Q*X20-X16-X17-K18K）腐:1）跨（叮）观：1,1）於W）毗1,3）迢W）蹲3）逊：（6上）边。：（7）xn：（8/）牝：（阿沁门J）Xi+：（S?7）纽5：（g/oxis：（9?8）纽9：（讪盜加：9,9）改进的0均值法文献【0基于核函数的概念提出了一种改进的一均值法，其分类性能要好于通常计算模式到类的距离时采用这个模式到类心的欧氏距离或马氏距离的均值法。由于C均值法我们已作详细介绍，这种改进的C均值法只简单表述如下:对给定的待分类模式集兀為心进行初始分划产生。类；计算各聚类吗所含模式数、均值矢量和协

20、方差阵弓；将各模式召按最小距离原则分划到某一聚类中。这里采用最小误判概率准则下正态分布情况的判决规则，计算模式到叫的距离d（x,j）=In%+d（元d（元J=inin）如果则判如果没有模式改变其类别，则停止算法；否则转至。（三）迭代自组织数据分析算法特点：具有启发性推理、分析监督、控制聚类结构及人机交互。条件及约定设待分类的模式特征矢量为氏庞為，算法运行前需设定个初始参数。算法思想在每轮迭代过程中，样本重新调整类别之后计算类内及类间有关参数，并和设定的门限比较，确定是两类合并为一类还是一类分裂为两类，不断地“自组织”以达到在各参数满足设计要求条件下，使各模式到其类心的距离平方和最小。算法原理步

21、骤预置设定聚类分析控制参数：C预期的类数，肚初始聚类中心个数可以不等于。）圧每一类中允许的最少模式数目若少于此数就不能单独成为一类）Q类内各分量分布的距离标准差上界大于此数就分裂）氐两类中心间的最小距离下界若小于此数，这两类应合并）在每次迭代中可以合并的类的最多对数，允许的最多迭代次数。将待分类的模式特征矢量国耳臥读入。选定初始聚类中心，可从待分类的模式特征矢量集刃中任选矶个模式特征矢量作为初始聚类中心相按最小距离原则将模式集忆中每个模式分到某一类中，即式中山表示珀和类叫的中心之间的距离。依据氏判断合并。如果类旳中样本数35，则取消该类的中心石，产琢T，转至或计算产琢T，转至或计算6尸怜-引心

22、12氏），将叫并入距离最近的那一类中；这时“尸肚T，转至。计算分类后的参数:计算分类后的参数:各类中心、类内平均距离及总体平均距离。计算各类的中心（尸12（尸12氏）计算各类中模式到类心的平均距离计算各个模式到其类内中心的总体平均距离依据叽判断停止、分裂或合并。若迭代次数心已达，则置屜转到；否则转下。若恥气则转到将一些类分裂；否则转下。若NK则跳过分裂处理转至否则转下。二：F讥-Zc若2，当迭代次数“是奇数时转至分裂处理）迭代次数是偶数时转至合并处理。计算各类类内距离的标准差矢量，巩）其各分量12枫）式中，疋为分量编号，为类的编号,式中，疋为分量编号，为类的编号,挖为矢量维数，叱是吗的第疋个分

23、量，是冠的第氐个分量。对每一聚类，求出类内距离标准差矢量円中的最大分量円咖在幻吨中，对任一勺逐，若有逐色，同时又满足下面两个条件之一：则将该类叫分裂为两个聚类，且令尸M+1。这两个新类的中心石和石是这样构成的：右和亏只是在勺中相应于逊的分量分别加上和减去肚，而其它分量不变，其中W抵的选取应使右和仍在吗的类域空间中且其它类出“力的模式到石和幻距离较远，而原叫类中的模式和它们距离较小。分裂后，3裂后，3，转至；否则，转下。计算各对聚类中心间的距离（心12枫-1;E+1,，甌）依据判断合并。将坷与比较，并将小于氐的那些必按递增次序排列，取前个，入D。从最小的必开始，将相应的两类合并。若原来的两个类心为和勺，则合并后的聚类中心为（心12（心12）“尸N厂（已并掉的类数）。在一次迭代中，某一类最多只能被合并一次。（11）如果迭代次数妇已达次或过程收敛，则结束。否则，片二片+1，若需要调整参数，则转至；若不改变参数，则转至。我们将该算法的合并和分裂的条件归纳如下：合并的条件：类内样本数空氏）类的数目王比）两类间中心距离弐“）分裂的条件：类的数目类的某分量标准差）类的数目类的某分量标准差）J）A（-2（eB+i）vw|）这里，v表示“或”的关系；八表示“与”的关系。如果类的数目甌有，当。是奇数时分裂，当$是偶数时合并。由上述合并与分裂的判断条