聚类分析算法

1、第二章 聚类分析1.1.1 4聚类的算法1.1.2 聚类的技术方案简单聚类根据相似性阈值和最小距离原则聚类VXi Q= Xi, X2, , , Xn = 020 2, USc；if D( Xi, mj) < T, mj=(1/n j)工Xi，XiC , n是 幼中的样本个数，T是给 定的阀值。Then Xi 切i类心一旦确定将不会改变。谱系或层次聚类按最小距离原则不断进行两类合并类心不断地修正，但模式类别一旦指定后就不再改变。依据准则函数动态聚类影响聚类结果的主要因数：类心、类别个数、模式输入顺序0所谓动态聚类、是指上述因数在聚类过程中是可变的。规定一些分类的目标参数，定义一个能刻划聚类

2、过程或结果优劣的准则函数，聚类过程就是使准则函数取极值的优化过程。这类方法有C 一均值法、ISODAT做、近邻函数法以及运用图论理论的最小张树法。1.1.3 简单聚类方法根据相似性阈值和最小距离原则的简单聚类方法1 .条件及约定设待分类的模式为 瓦设为),选定类内距离门限To2 .算法思想计算模式特征矢量到聚类中心的距离并和门限7比较而决定归属该类或作为新的一类中心。通常选择欧氏距离。3 .算法原理步骤取任意的一个模式特征矢量作为第一个聚类中心。例如，令第一类师的中心后二耳。 计算下一个模式特征矢量 吊到用的距离距。若41 >7 ,则建立新的一类 小?,其中心后二右；若册£了，

3、则后£ M 。假设已有聚类中心WZ，Z,计算尚未确定类别的模式特征矢量用到各 聚类中心药。=12的距离4,如果4"0=12A),则不作为新的一 类处+1的中心，山二礼否则，如果(2-4-1)4/ 二 min|dJ则指判月E&。检查是否所有的模式都分划算类别，如都分划完了则结束；否则 返到。4性能计算简单。聚类结果很大程度上依赖于距离门限T的选取、待分类特征矢量参与分类的次序和聚类中心的选取。当有特征矢量分布的先验知识来指导门限 T及初始中心用的选取时，可以获得较合理结果。5.改进通常采用试探法，选用不同的门限及模式输入次序来试分类，并对聚类结果 进行检验，即用聚类准

4、则函数Ji。例如，计算每一聚类中心与该类中最远样本点 的距离，或计算类内及类间方差，用这些结果指导 T及&的重选。最后对各种方 案的划分结果进行比较，选取最好的一种聚类结果。图（2-4-1）距离阈值及初始类心对聚类的影响最大最小距离算法1 .条件及约定设待分类的模式特征矢量集为 阮后，禹）,选定比例系数6。2 .基本思想在模式特征矢量集中以最大距离原则选取新的聚类中心，以最小距离原则进行模式归类。这种方法通常也使用欧氏距离。3 .算法原理步骤 选任一模式特征矢量作为第一个聚类中心&。例如，4 二*。 从待分类矢量集中选距离7最远的特征矢量作为第二个聚类中心 为。例 如图（2-4

5、-2） 中 飞一甬 最大，取4 = %。 计算未被作为聚类中心的各模式特征矢量 可与圆、为之间的距离并求 出它们之中的最小值，即4二根力| CM2）1.一（2-4-2）为表述简洁，虽然某些模式已选做聚类中心，但上面仍将所有模式下角标全 部列写出来，因这并不影响算法的正确性。(4)若(2-4-3)4 = mja mm(心儿)> 6日一切则相应的特征矢量将作为第三个聚类中心，君二%。此例中,广*然后转至;否则，转至最后一步。 设存在E个聚类中心，计算未被作为聚类中心的各特征矢量到各聚类中 心的距离并算出(2-4-4)如果4 隼厂即|,则£1 二后并转至；否则，转至最后一步 当判断出

6、不再有新的聚类中心之后，将模式特征矢量伍兀J,岳）按最小距离原则分到各类中去，即计算4吨-以 0 = 12;i = L2j,M （ 2-4-5） 当册=啰区则判工网。在此例中，伍尻，止他H二礼伍周）E铀%二%;伉鬲禹居岛）E% , 4= &这种算法的聚类结果与参数0以及第一个聚类中心的选取有关。如果没有先 验知识指导0和Z的选取，可适当调整0和芯，比较多次试探分类结果，选取最合理的一种聚类理（LD 43） 4）K式53 旃0司 为 0,3） 题:（5用 43用 的口：。,5）X1图（2-4-2）最大最小距离算法举例2.4.3 谱系聚类法（Hierarchical Clustering

7、Method）（系统聚类法、层次聚类法）效果较好、是常用方法之一。1 .条件及约定设待分类的模式特征矢量为 同帚，禹）,表示第k次合并时的第j类。2 .基本思想首先将打个模式视作各自成为一类，然后计算类与类之间的距离，选择距离最小的一对合并成一个新类，计算在新产生的类别分划下各类之间的距离，再将距离最近的两类合并，直至所有模式聚成两类为止。3 .算法步骤 初始分类。令上二。,每个模式自成一类，即 0二 仁12©。 计算各类间的距离 为,生成一个对称的距离矩阵 "“二（乌）.萧，m为类 的个数。找出前一步求得的矩阵。中的最小元素，设它是和q勘间的距离， 将中和4"两

8、类合并成一类，于是产生新的聚类 G*”。；叫，令港二胡-1。 检查类的个数。如果类数 例大于2,令上二上+1,转至；否则，停止。如果某一循环中具有最小类间距离不止一个类对，则对应这些最小距离的类可以同时合并。上述算法步骤给出了从 N类至2类的完整聚类过程，停止条件以类间距离门限T作为停止条件，即取距离门限7,当。阳中最小阵元大于T时，聚类过程停止；以预定的类别数目作为停止条件，当类别合并过程中，类数等于预定值 时，聚类过程停止。类间距离的定义与递推在该算法中可以采用上节已详细介绍过的不同的类间距离定义方式，并使用 类间距离递推公式。所采用的类间距离定义不同、聚类过程及结果是不一样的。上述算法在

9、归并的每次迭代过程中，距离矩阵的最小元素值不断地改变，如果有 单调不减关系则称类间距离对并类具有单调性。最近距离法、最远距离法、平均 法及离差平方和法等定义的类间距离都具有这个性质，而重心法没有这个性质。算法特点聚类过程中类心不断地调整，但某一模式一旦分划到某一类中就不再改变。从粗到细的层次聚类这类技术的另一个算法和上述算法过程相反，依据类的离差平方和递推公式按1类至M类进行谱系分解，这里不作介绍了。聚类过程可以表示成一个树图。例：给出6个样本特征矢量如下，按最小距离原则进行聚类-L2W 焉君= （33（W- - （UQ20y 弓=（32L2U 钎,LLO）'解：将每一样本看成自成一类

10、暧=同5叽国0叫J乜幻计算距离矩阵”（表2-4-1）。加）中最小阵元为在它是G”与理）之间的距离，将它们合并为一类, 得一新的分类为齿二贺）在这里使用了距离递推公式，如中二中明伍闾计算合并后的距离矩阵 ""（表2-4-2） 见）=训 Gf，与苗"距离，潸，与G"距离=nun fjlS,Vs） = M"”中距离最小者为它是呼与呼间的距离，合并和,得新的分类甲二 G3G? 二 Gp中二G甲=（的或）同样计算小事（表2-4-3），进一步聚类得 宙，“ 编二甲 砂甲即I" ",：' .'.J', ；'

11、.-公计算“九表2-4-4）。 由表可知，G,、«的和己才可以一起合并成一类。表（2-4-1）。表（2-4-2） 加铲噌G）贽誓0噌行0国叼V15乖0乖V5V130赠Vii78木后0噌V21V147§而740甲曹管0祈口750次小0JTT0表(2-4-3)""表(2-4-4)d <!endif>碟仃产呼邛0鹫1在0后而0呼布次行0甲型*0*J60留百乐02.4.4 动态聚类法(Dynamic clustering algorithm)最大距离和层次聚类算法的一个共同特点是某个模式一旦划分到某一类之 后，在后继的算法过程中就不改变了，而简单聚类

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

13、 则函数取得极值或设定的参数达到设计要求时停止。动态聚类原理框图如下： C 均值法(C means)图(2-4-3)1 .条件及约定设待分类的模式特征矢量集为 阮，如禹),类的数目r是取定的。2 .基本思想取定c个类别和选取C个初始聚类中心,按最小距离原则将各模式分配到 C 类中的某一类，不断地计算类心和调整各模式的类别使每个模式特征矢量到其所 属类别的距离平方之和最小3 .算法步骤 任选C个模式特征矢量作为初始聚类中心： 犁，碟，那)。 将待分类的模式特征矢量集(后中的模式逐个按最小距离原则分划给 c 类中的某一类，即如果端=吁咖(12,附(2-4-6)则判为e砂川。式中与表示看和肉的中心M

14、J的距离，上角标表示迭代次数。于是产生新的 聚类 *0=12、。计算重新分类后的各类心#叫 _ I V T勺 JiT乙西 ,1 口 勺g产G = 1,2产(2-4-7)M命I', 人 人式中芍为勺类中所含模式的个数。因为这一步采取平均的方法计算调整后类的中心，且定为。类，故称e均值法。如果 广空7 7),则转至；如果孝“二茶，则结束。4 .分析在上述算法中，虽然没有我们以欧氏距离为例，简单地分析该算法的可收敛性直接运用准则函数(2-4-8)进行分类，但在中根据式(2-4-6)进行模式分划可使J趋于变小。设某样本大从聚类号移至聚类皿中，W了移出%后的集合记为防，皿移入月后的集合记为设叫和

15、所含样本数分别为勺和服，聚类小、可、Q和诵的均矢分别为网、网、脸和物t,显然有2rl 1 _一m.二丽什(祗-亢)3 ' «.-r J 1J(2-4-9)(2-4-10)而这两个新的聚类的类内欧氏距离(平方)和人与原来的两个聚类的类内欧氏距离(平方)0和0的关系是小一作司(2-4-11)h小含斤闻f(2-4-12)当天距帆t比距叼更近时，使得X分划给Q类可使J变小。这说(2-4-13)由式(2-4-11)、(2-4-12)及(2-4-13)可知，将 餐 明在分类问题中不断地计算新分划的各类的类心，并按最小距离原则归类可使J 值减至极小值。在上述算法中，也可以利用式(2-4-1

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

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

18、用相距最远的e个特征点作为初始类心。具体地讲，是按前述的最大 最小距离算法求取e个初始聚类中心。当M较大时，先随机地从 户个模式中取出一部分模式用谱系聚类法聚成r类，以每类的重心作为初始类心。设已标准化的待分类模式集为礼设,扁）,希望将它们分为c类令模式且令月二仇”石”，仆）,定义能冽二X %MA = maxMf = min 故洲（i）(2-4-14)(2-4-15)(2-4-16)计算_ g-啪)-1(2-4-17)% MA-MI(l=U?-rAT)显然IS* Wc,若因最接近整数J ,则把总分划至印中。对所有样本都实 行上述处理，就可实现初始分类，从而产生初始聚类中心。用类核代替类心前面的

19、算法存在一个不足，即是只用一个聚类中心点作为一类的代表，但是一个点往往不能充分地反映该类的模式分布结构，从而损失很多有用的信息。当类的分布是球状或近似球状时，算法尚能有较好的效果，但对于如图（2-4-4）所示的那种各分量方差不等的正态分布而两类的主轴和类心又是那样的情况，分类效果就不好了，工点应属于5类，但由于它距 研类的均矢更近，按前述的算法 则被指判到场类。如果已知各类模式分布的某些知识，则可以利用它们指导聚 类。为此，我们定义一个类核函数 0二口叫表示类町的模式分布情况，其 中关于类旧的一个参数集，？是在维空间中的特征矢量，Kj可以是一个函数、 一个点集或其他适当的模型。为了刻划待识模式

20、X和为类的接近程度还应规定一个模式特征矢量充到核Kj的距离/"，”）。实际上，马氏距离就是核函数距 离的一种简化。当已知某类的分布近似为正态分布时，可以用以这类样本统计估计值为参数 的正态分布函数作为核函数，即0（叫"一八叫也）町（彳也）(2-4-18)（2兀）噌4L *其中A J1 1 1口广一2、, 勺2#_AA4二一；x（切任-必） 与T刖, W. -式中J为进行参数估计的该类样本数。则模式 X与该类的距离为丹'£）=什也俎0-修+;呵%乙乙（2-4-19）这实际上是第四章将要讨论的最小误判概率准则下先验概率相同时的判决函数当已知各类样本分别在相应的

21、主轴附近分布时，可以定义主轴核函数：乎（2-4-20）式中，4二M町，%）是由和叩类的统计协方差阵的叫伽,小）个最大特T T八征信所对应的已规格化的特征矢量作成的矩阵，即 4是协方差阵Z给出的部分主轴系统，4G = 12附J给出了样本分布的主轴方向（散布的情况由特征值反A映出来）。4为"i轴上的单位矢量。设口J是勺类样本的均值矢量，求一点充和一fl，- -一肌，、一一一、 E 1 一 个轴叫的距离可见图（2-4-5）。模式I和J类间的距离平方可以用工和该类的主 轴间的欧氏距离平方来度量。*AA I I AA姆号）二归-邛笈-削人-印”-3（2-4-21）（a）各分量方差不等的正态分布

22、（b）沿主轴分布图（2-4-4） 类的模式分布情况的示例图（2-4-5） 求和主轴距离示意图例：模式分布如图（2-4-6）所示，试用C 一均值法进行聚类，取C=2选二二一.一 二-因,故&ed"匠判咽一喇I,故吊叫斤一小W1,故以砂，二亿总M二2 ；婢二伉芯,，%）,也=18计算新的聚类中心机支胡=加+标& 5,'567;533, = Z为=16 + %+猊）=%岛18因二 w那。= 1,2）,故转至。由新的聚类中心，得卜-刑砧-冽/=12,-,8卜-术H钎斓|1=9,1。,加故得#=伉扁,必二8计算聚类中心琛二勺,25、767：J西图（2-K6）二一均11尊

23、法例题的模式集<!endif>因靖丰泮U = L2）,故转至。”求得的分类结果与前一次的结果相同，婷二*0 = 12）"各聚类中心必然也与前一次的相同，引二方）（JT，2）T3）因4=4（尸L2）,不再出现新的类别划分，故分类过程结束过如知如) 次(I)知 X3：(0,l) Xb：(7,7)对 1) &C.7)*(L3) &R局前(3,3)曲式g 勘:(6,6)即 沟qOj6) &O0F)改进的c一均值法文献【10】基于核函数的概念提出了一种改进的 e一均值法，其分类性能要 好于通常计算模式到类的距离时采用这个模式到类心的欧氏距离或马氏距离的 C一

24、均值法。由于r均值法我们已作详细介绍，这种改进的c均值法只简单表述如下：对给定的待分类模式集 氏见，,亏）进行初始分划产生C类;计算各聚类日所含模式数勺、均值矢量口和协方差阵;将各模式工按最小距离原则分划到某一聚类中。这里采用最小误判概 率准则下正态分布情况的判决规则，计算模式 ？到叩的距离f 1 %二14卜（亍-即早亍项）-2%(2-4-22)如果心曲"呼W眄）j则判加也 如果没有模式改变其类别，则停止算法；否则转至。（三）ISODATA您代自组织数据分析）算法（Iterative Self-Organizing Data Analysis Techniques Algorithm

25、）特点：具有启发性推理、分析监督、控制聚类结构及人机交互。1 .条件及约定设待分类的模式特征矢量为 阮，焉，嘉），算法运行前需设定7个初始参数。2 .算法思想在每轮迭代过程中，样本重新调整类别之后计算类内及类间有关参数，并和 设定的门限比较，确定是两类合并为一类还是一类分裂为两类， 不断地“自组织”， 以达到在各参数满足设计要求条件下，使各模式到其类心的距离平方和最小。3 .算法原理步骤预置设定聚类分析控制参数：:=预期的类数，N产初始聚类中心个数（可以不等于C）,金二每一类中允许的最少模式数目（若少于此数就不能单独成为一类）， &二类内各分量分布的距离标准差上界（大于此数就分裂），伪

26、二两类中心间的最小距离下界（若小于此数，这两类应合并），:=在每次迭代中可以合并的类的最多对数，=允许的最多迭代次数。 将待分类的模式特征矢量月兀，司）读入。 选定初始聚类中心，可从待分类的模式特征矢量集 后）中任选“个 模式特征矢量作为初始聚类中心 勺。=12也）o按最小距离原则将模式集可中每个模式分到某一类中，即如果,'-二, ：（ 2-4-23）则判式中心表示和类可的中心%之间的距离。 依据斗判断合并。如果类 四,中样本数勺Y4 ,则取消该类的中心 句, 从二M一1,转至（或计算加书一题1（二12闻,力），将小并入距 离最近的那一类中；这时 N1广心T,转至。 计算分类后的参数：

27、各类中心、类内平均距离及总体平均距离。计算各类的中心-I XT1 一.二1（ 2-4-24）计算各类中模式到类心的平均距离(片12M(2-4-25) 计算各个模式到其类内中心的总体平均距离_1_(2-4-26)d=力4aN j-i依据乙、从判断停止、分裂或合并。 若迭代次数人已达/ ,则置6。二°，转到；否则转下NW 若2则转到（将一些类分裂）；否则转下。 若此之2c ,（则跳过分裂处理）转至，否则转下。:t a, tf z若2,当迭代次数h是奇数时转至（分裂处理）；迭代次数"是偶数时转至（合并处理）。计算各类类内距离的标准差矢量(2-4-27)其各分量(上二124 ；J

28、= 12也)(2-4-28)式中，长为分量编号，J为类的编号, 是马的第E个分量。R为矢量维数，在是岳的第上个分量，。 对每一聚类，求出类内距离标准差矢量可中的最大分量勺啾叫=m普尔0 = 1,2/ ,闻)(2-4-29)在上加k）中，对任一 4血x,若有血J：,同时又满足下面两个条件之一":4和叼 2（& + 1） 一则将该类号分裂为两个聚类，且令也=刈+1。这两个新类的中心W和%是这 样构成的：5和4只是在句中相应于4闻的分量分别加上和减去 何则，而其 它分量不变，其中04EM1, k的选取应使4,和4仍在叫'的类域空间中且其它 类喊h J）的模式到W和司距离较远

29、，而原 门类中的模式和它们距离较小。分 裂后，,，=4+1,转至；否则，转下。 计算各对聚类中心间的距离，一 ,：.,-1 . ； ： +（ 2430） 依据牝判断合并。将%与与比较，并将小于 仇的那些为按递增次序 排列，取前个，D疝4%。从最小的为开始，将相应的两类合并。若原来的两个类心为 t和各，则合并后的聚类中心为- 1 - - 为二金马+”吊/”（E2T）（2-4-31）M=&一（已并掉的类数）。在一次迭代中，某一类最多只能被合并一次。（id如果迭代次数4已达/次或过程收敛，则结束。否则，。=4+1,若需 要调整参数，则转至；若不改变参数，则转至。我们将该算法的合并和分裂的条件

30、归纳如下：合并的条件：（类内样本数&）U（类的数目之）八（两类间中心距离 岛）。分裂的条件：（类的数目- 2 ）八（类的某分量标准差 > 殳）八鸣+i）v（mW）士 C这里，u表示“或”的关系； 八表示“与”的关系。如果类的数目儿有c一 < M m2。7y2,当，是奇数时分裂，当今是偶数时合并。由上述合并与分裂的判断条件可以看出算法初设的7个参数存在一定的相互制约。例：用ISODATAJ法聚类图（2-4-7）中的数据 解：在本例中N二8, m=2。设定参数和初始值c = 2=1= 1 仇=4£=1 1 = 4 或=1 4 = （W = 1在无先验知识的情况下，可任意选取这些参数和初始值，然后在逐次迭代中加以 调整。 因只有一个聚类中心，故例=与4，工J ,«i=8因勺& ,无合并。 计算聚类中心、类内平均距离和总的平均距离。3.38、;275,计算聚类中心11 X-1 -4五=一为二% #i«>L 计算类内平均距离H纱-讣226D计算总的平均距离d-dY- 2.26cNk 因不是最后一步迭代，且 2 ,转至(6)求的标准差矢量算得&二1的C13Gh=L99口且"2'将%分裂成两类，取上=05，0-5。脸用L0,则<3.38 +