聚类分析算法.doc

《聚类分析算法.doc》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第二章聚类分析2·4聚类的算法2.4.1聚类的技术方案⑴简单聚类根据相似性阈值和最小距离原则聚类"xi∈W={x1,x2,…,xn}=w1Èw2È…Èwc；ifD(xi,mj)≤T,mj=(1/nj)Sxi(j)，xi(j)∈wj，nj是wj中的样本个数，T是给定的阀值。Thenxi∈wi类心一旦确定将不会改变。⑵谱系或层次聚类按最小距离原则不断进行两类合并类心不断地修正，但模式类别一旦指定后就不再改变。⑶依据准则函数动态聚类影响聚类结果的主要因数：类心、类别个数、模式输入顺序。所谓动态聚类，是指上述因数在聚类过程中是可变

2、的。规定一些分类的目标参数，定义一个能刻划聚类过程或结果优劣的准则函数，聚类过程就是使准则函数取极值的优化过程。这类方法有—均值法、ISODATA法、近邻函数法以及运用图论理论的最小张树法。2.4.2简单聚类方法㈠根据相似性阈值和最小距离原则的简单聚类方法⒈条件及约定设待分类的模式为，选定类内距离门限。⒉算法思想计算模式特征矢量到聚类中心的距离并和门限比较而决定归属该类或作为新的一类中心。通常选择欧氏距离。⒊算法原理步骤⑴取任意的一个模式特征矢量作为第一个聚类中心。例如，令第一类的中心。⑵计算下一个模式特征矢量到的距离。若

3、，则建立新的一类，其中心；若，则。⑶假设已有聚类中心，计算尚未确定类别的模式特征矢量到各聚类中心的距离，如果，则作为新的一类的中心，；否则，如果(2-4-1)则指判。检查是否所有的模式都分划完类别，如都分划完了则结束；否则返到⑶。⒋性能l计算简单。l聚类结果很大程度上依赖于距离门限的选取、待分类特征矢量参与分类的次序和聚类中心的选取。当有特征矢量分布的先验知识来指导门限及初始中心的选取时，可以获得较合理结果。⒌改进通常采用试探法，选用不同的门限及模式输入次序来试分类，并对聚类结果进行检验,即用聚类准则函数J1。例如，计算每

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

5、计算未被作为聚类中心的各模式特征矢量与、之间的距离并求出它们之中的最小值，即(2-4-2)为表述简洁，虽然某些模式已选做聚类中心，但上面仍将所有模式下角标全部列写出来，因这并不影响算法的正确性。⑷若(2-4-3)则相应的特征矢量作为第三个聚类中心，。此例中。然后转至⑸；否则，转至最后一步⑹。⑸设存在个聚类中心，计算未被作为聚类中心的各特征矢量到各聚类中心的距离,并算出(2-4-4)如果，则并转至⑸；否则，转至最后一步⑹。⑹当判断出不再有新的聚类中心之后，将模式特征矢量按最小距离原则分到各类中去，即计算(2-4-5)当，则判

6、。在此例中，，；，；，。这种算法的聚类结果与参数以及第一个聚类中心的选取有关。如果没有先验知识指导和的选取，可适当调整和，比较多次试探分类结果，选取最合理的一种聚类。图(2-4-2)最大最小距离算法举例2.4.3谱系聚类法(HierarchicalClusteringMethod)(系统聚类法、层次聚类法）效果较好、是常用方法之一。⒈条件及约定设待分类的模式特征矢量为，表示第k次合并时的第类。⒉基本思想首先将个模式视作各自成为一类，然后计算类与类之间的距离，选择距离最小的一对合并成一个新类，计算在新产生的类别分划下各类之间

7、的距离，再将距离最近的两类合并，直至所有模式聚成两类为止。⒊算法步骤⑴初始分类。令，每个模式自成一类，即。⑵计算各类间的距离，生成一个对称的距离矩阵，为类的个数。⑶找出前一步求得的矩阵中的最小元素，设它是和间的距离，将和两类合并成一类，于是产生新的聚类，令。⑷检查类的个数。如果类数大于2，令，转至⑵；否则，停止。如果某一循环中具有最小类间距离不止一个类对，则对应这些最小距离的类可以同时合并。上述算法步骤给出了从类至类的完整聚类过程，停止条件l以类间距离门限作为停止条件，即取距离门限，当中最小阵元大于时，聚类过程停止；l以预

8、定的类别数目作为停止条件，当类别合并过程中，类数等于预定值时，聚类过程停止。类间距离的定义与递推在该算法中可以采用上节已详细介绍过的不同的类间距离定义方式，并使用类间距离递推公式。所采用的类间距离定义不同，聚类过程及结果是不一样的。上述算法在归并的每次迭代过程中，距离矩阵的最小元素值不断地改变，如果有单