聚类分析算法

本文格式为Word版，下载可任意编辑——聚类分析算法

其次章聚类分析2·4聚类的算法

2.4.1聚类的技术方案

⑴简单聚类

根据相像性阈值和最小距离原则聚类?xi∈?={x1,x2,?,xn}=?1??2????c；

ifD(xi,mj)≤T,mj=(1/nj)?xi(j)，xi(j)∈?j，nj是?j中的样本个数，T是给定的阀值。

Thenxi∈?i

类心一旦确定将不会改变。

⑵谱系或层次聚类

按最小距离原则不断进行两类合并

类心不断地修正，但模式类别一旦指定后就不再改变。

⑶依据准则函数动态聚类

影响聚类结果的主要因数：类心、类别个数、模式输入顺序。所谓动态聚类，是指上述因数在聚类过程中是可变的。

规定一些分类的目标参数，定义一个能刻划聚类过程或结果优劣的准则函数，聚类过程就是使准则函数取极值的优化过程。这类方法有—均值法、ISODATA法、近邻函数法以及运用图论理论的最小张树法。2.4.2简单聚类方法

㈠根据相像性阈值和最小距离原则的简单聚类方法⒈条件及约定设待分类的模式为⒉算法思想

计算模式特征矢量到聚类中心的距离并和门限比较而决定归属该类或作

，选定类内距离门限。

为新的一类中心。寻常选择欧氏距离。

⒊算法原理步骤

⑴取任意的一个模式特征矢量作为第一个聚类中心。例如，令第一类中心

。

到

的距离。

，计算尚未确定类别的模式特征矢量，假使

，则

到各

。若

，则建立新的一类

的

⑵计算下一个模式特征矢量，其中心

；若

，则

⑶假设已有聚类中心聚类中心类

的中心，

的距离

作为新的一

；否则，假使

(2-4-1)

则指判返到⑶。

⒋性能

。检查是否所有的模式都分划完类别，如都分划完了则终止；否则

?计算简单。

?聚类结果很大程度上依靠于距离门限的选取、待分类特征矢量参与分

类的次序和聚类中心的选取。

当有特征矢量分布的先验知识来指导门限及初始中心得较合理结果。

⒌改进

寻常采用试探法，选用不同的门限及模式输入次序来试分类，并对聚类结果进行检验,即用聚类准则函数J1。例如，计算每一聚类中心与该类中最远样本点的距离，或计算类内及类间方差，用这些结果指导及案的划分结果进行比较，选取最好的一种聚类结果。

的重选。最终对各种方

的选取时，可以获

图(2-4-1)距离阈值及初始类心对聚类的影响

㈡最大最小距离算法⒈条件及约定

设待分类的模式特征矢量集为⒉基本思想

在模式特征矢量集中以最大距离原则选取新的聚类中心，以最小距离原则进行模式归类。这种方法寻常也使用欧氏距离。

⒊算法原理步骤

⑴选任一模式特征矢量作为第一个聚类中心⑵从待分类矢量集中选距离如图(2-4-2)中

最大，取

。例如，

。

。例

，选定比例系数。

最远的特征矢量作为其次个聚类中心

。

与

、

⑶计算未被作为聚类中心的各模式特征矢量出它们之中的最小值，即

之间的距离并求

(2-4-2)

为表述简单，虽然某些模式已选做聚类中心，但上面仍将所有模式下角标全部列写出来，因这并不影响算法的正确性。

⑷若

(2-4-3)

则相应的特征矢量作为第三个聚类中心，。此例中。然后转至⑸；

否则，转至最终一步⑹。

⑸设存在个聚类中心，计算未被作为聚类中心的各特征矢量到各聚类中心的距离

,并算出

假使

，则

(2-4-4)

并转至⑸；否则，转至最终一步⑹。

按最

⑹当判断出不再有新的聚类中心之后，将模式特征矢量小距离原则分到各类中去，即计算

当

；

，则判

。在此例中，，

。

，

(2-4-5)；

，

这种算法的聚类结果与参数以及第一个聚类中心的选取有关。假使没有先

的选取，可适当调整和

，比较屡屡试探分类结果，选取最

验知识指导和

合理的一种聚类。

图(2-4-2)最大最小距离算法举例

2.4.3谱系聚类法(HierarchicalClusteringMethod)(系统聚类法、层次聚类法）

效果较好、是常用方法之一。

⒈条件及约定

设待分类的模式特征矢量为

⒉基本思想首先将

个模式视作各自成为一类，然后计算类与类之间的距离，选择距

，

表示第k次合并时的第类。

离最小的一对合并成一个新类，计算在新产生的类别分划下各类之间的距离，再将距离最近的两类合并，直至所有模式聚成两类为止。

⒊算法步骤

⑴初始分类。令⑵计算各类间的距离

，每个模式自成一类，即，生成一个对称的距离矩阵

。，为类

的个数。

⑶找出前一步求得的矩阵将

和

中的最小元素，设它是

和，令

间的距离，

。

两类合并成一类，于是产生新的聚类

大于2，令

⑷检查类的个数。假使类数，转至⑵；否则，中止。

假使某一循环中具有最小类间距离不止一个类对，则对应这些最小距离的类可以同时合并。上述算法步骤给出了从

中止条件

?以类间距离门限作为中止条件，即取距离门限，当

大于时，聚类过程中止；

?以预定的类别数目作为中止条件，当类别合并过程中，类数等于预定值

时，聚类过