1、1二、基于距离阈值的聚类算法二、基于距离阈值的聚类算法1）问题：问题：有N个待分类的模式 ，要求按距离阈值T分类到以 为聚类中心的模式类中。NXXX,21,21ZZ2）算法描述算法描述 任取样本Xi 作为第一个聚类中心的初始值，如令Z1=X1。计算样本X2 到Z1 的欧氏距离 ，若 ，定义一新的聚类中心Z2=X2；否则 X2 以Z1为中心的聚类。1221ZX DTD21(T_threshold)1 近邻聚类法近邻聚类法2依此类推，直到将所有的N个样本都进行分类。假设已有聚类中心Z1、Z2，计算 和 ，1331ZX D2332ZX D若 且 ，则建立第三个聚类中心Z3=X3；TD 31TD32否
2、则X3离Z1和Z2中最近者（最近邻的聚类中心）。3）算法特点算法特点B）优点：计算简单。（一种虽粗糙但快速的方法）A）局限性：很大程度上依赖于第一个聚类中心的位置选择、待 分类模式样本的排列次序、距离阈值T的大小以及样本分布 的几何性质等。3 用先验知识指导阈值T 和起始点Z1的选择，可获得合理的聚类结果。否则只能选择不同的初值重复试探，并对聚类结果进行验算，根据一定的评价标准，得出合理的聚类结果。对结果验算，类内各样对结果验算，类内各样本点间距离方差之和太大本点间距离方差之和太大减小减小T，修改中心，修改中心Z。2T1T1T4）算法讨论）算法讨论图5 选取不同阈值和聚类中心时得到的不同聚类结
3、果42 最大最小距离算法（小中取大距离算法最大最小距离算法（小中取大距离算法）1）问题问题已知N个待分类的模式 ，分类到聚类中心 对应的类别中。NXXX,21,21ZZ2）算法描述算法描述 选任意一模式样本做为第一聚类中心Z1。选择离Z1距离最远的样本作为第二聚类中心Z2。逐个计算各模式样本与已确定的所有聚类中心之间的距离，并选出其中的最小距离。例当聚类中心数k=2时，计算11ZX iiD22ZX iiDmin(Di1,Di2)，i=1，N（N个最小距离）5 将样本 按最近距离划分到相应聚类中心对应的类别中。Nii,2,1,X 重复步骤，直到没有新的聚类中心出现为止。在所有最小距离中选出最大距
4、离，如该最大值达到 的一定分数比值一定分数比值(阈值阈值T)以上以上，则相应的样本点取为新的聚类中心，返回；否则，寻找聚类中心的工作结束。21ZZ 10,.,2,1),maxmin(2121ZZNiDDii若（：用试探法取为一固定分数，如1/2。）则Z3存在。为使聚类中心更有代表性，可取各类的样本均值作为聚类中心。例k=2时思路总结：思路总结：先找中心后分类；关键：怎样开新类，聚类中心如何定。先找中心后分类；关键：怎样开新类，聚类中心如何定。6例3 对图示模式样本用最大最小距离算法进行聚类分析。选选Z1=X1距距Z1最远，选为最远，选为Z2。计算。计算T。对应最小距离对应最小距离中的最大值，中
5、的最大值，且且T，选作，选作Z3。结果：Z1=X1；Z2=X6；Z3=X7。用全体模式对三个聚类中心计算最小距离中的最大值，无T 情况，停止寻找中心。聚类80212121ZZT10个最小距离中，X7对应的距离T,73XZ7三三 层次聚类法层次聚类法（Hierarchical Clustering Method）（系统聚类法、分级聚类法）（系统聚类法、分级聚类法）思路：每个样本先自成一类，然后按距离准则逐步合并，减少类数。1 算法描述算法描述 N个初始模式样本自成一类，即建立N 类：计算各类之间（即各样本间）的距离，得一NN维距离矩阵D(0)。“0”表示初始状态。)0(,),0(),0(21NG
6、GG(G_Group)8假设已求得距离矩阵D(n)（n为逐次聚类合并的次数），找出D(n)中的最小元素，将其对应的两类合并为一类。由此建立新的分类：),1(),1(21nGnG计算合并后新类别之间的距离，得D(n+1)。跳至第2步，重复计算及合并。结束条件：结束条件：取距离阈值T，当D(n)的最小分量超过给定值 T 时，算法停 止。所得即为聚类结果。或不设阈值T，一直到将全部样本聚成一类为止，输出聚类的分 级树。92 问题讨论：类间距离计算准则问题讨论：类间距离计算准则KHDDKHKHHKXXXX,minHK最短距离法最短距离法 如H、K是两个聚类，则两类间的最短距离定义为：H类中的某个样本X
7、H和K类中的某个样本XK之间 的欧氏距离。KHDXX,DHK：H类中所有样本与K类中所有样本之间的最小距离。10IHDDIHIHHIXXXX,minJHDDJHJHHJXXXX,min如果K类由I和J两类合并而成，则HJHIHKDDD,min得到递推公式：HKIJHIDHJD最长距离法最长距离法 KHDDKHKHHKXXXX,max若K类由I、J两类合并而成，则IHDDIHIHHIXXXX,maxJHDDJHJHHJXXXX,maxHJHIHKDDD,max有：11中间距离法中间距离法 介于最长与最短的距离之间。如果K类由I类和J类合并而成，则H和K类之间的距离为重心法重心法 将每类中包含的样
8、本数考虑进去。若I类中有nI个样本，J类中有nJ个样本，则类与类之间的距离递推式为 222412121JIJHIHKHDDDD2222)(JIJIJIJHJIJIHJIIKHDnnnnDnnnDnnnD12 定义类间距离的方法不同，分类结果会不太一致。实际问定义类间距离的方法不同，分类结果会不太一致。实际问题中常用几种不同的方法，比较分类结果，从而选择一个比较题中常用几种不同的方法，比较分类结果，从而选择一个比较切合实际的分类。切合实际的分类。22JHJIJIHJIIKHDnnnDnnnD类平均距离法类平均距离法KjHijiKHKHdnnD212jid：H类任一样本Xi和K类任一样本Xj之间的
9、欧氏距离平方。若K类由I类和J类合并产生，则递推式为13T10,2,1,3,0XT20,1,0,3,1XT31,0,0,3,3XT40,2,0,1,1XT51,2,1,2,3XT60,1,1,1,4X例：给出6个五维模式样本如下，按最短距离准则进行系统聚类分类。计算各类间欧氏距离：解：（1）将每一样本看作单独一类，得：11)0(XG22)0(XG33)0(XG44)0(XG55)0(XG66)0(XG301101)0(212122515224142231322212221112112xxxxxxxxxxDXX1512103)0(212213D)0(34D)0(35D)0(36D，；)0(14D
10、)0(15D)0(16D)0(23D)0(24D)0(25D)0(26D；14)0(1G)0(2G)0(3G)0(4G)0(5G)0(6G)0(1G)0(2G3)0(3G156)0(4G6513)0(5G11867)0(6G21148114D(0)000000（2）将最小距离 对应的类 和 合并为1类，得 新的分类。3)0(1G)0(2G)0()1(44GG)0()1(55GG)0(),0()1(2112GGG)0()1(33GG)0()1(66GG计算聚类后的距离矩阵D(1)：由D(0)递推出D(1)。得距离矩阵D(0)：15)0(1G)0(2G)0(3G)0(4G)0(5G)0(6G)0(
11、1G)0(2G3)0(3G156)0(4G6513)0(5G11867)0(6G21148114D(0)000000)1(12G)1(3G)1(4G)1(5G)1(6G)1(12G)1(3G6)1(4G513)1(5G867)1(6G148114 D(1)0 0 0 0 0（3）将D(1)中最小值 对应的类合为一类，得D(2)。4)2(12G)2(3G)2(4G)2(56G)2(12G)2(3G6)2(4G513)2(56G867 D(2)0 0 0 016（4）将D(2)中最小值 对应的类合为一类，得D(3)。5)2(12G)2(3G)2(4G)2(56G)2(12G)2(3G6)2(4G5
12、13)2(56G867 D(2)0 0 0 0)3(124G)3(3G)3(56G)3(124G)3(3G6)3(56G76 D(3)0 0 0若给定的阈值为 ，D(3)中的最小元素 ，聚类结束。5T4211,XXXG 32XG 653,XXG 若无阈值，继续分下去，最终全部样本归为一类。可给出聚类过程的树状表示图。13T61765431X2X4X3X5X6X 层次聚类法的树状表示 类间距离类间距离阈值增大，阈值增大，分类变粗。分类变粗。18五、五、动态聚类法动态聚类法两种常用算法：*K-均值算法*迭代自组织的数据分析算法(ISODATA,iterative self-organizing d
13、ata analysis techniques algorithm)判断判断合理性合理性选初始选初始 中心中心聚类聚类合理合理不合理不合理输出输出修改修改图9 动态聚类法的基本思路19K-均值算法的聚类准则：聚类中心Zj的选择应使准则函数J极小，即使Jj的值极小。1 K-均值算法均值算法 基于使聚类准则函数最小化，准则函数：聚类集中每一样本点到该类中心的距离平方和。对于第j个聚类集，准则函数定义为Sj：第j个聚类集（域），聚类中心为Zj；Nj：第j个聚类集Sj中所包含的样本个数。对所有K个模式类有jiKjjNijiSJXZX112,|jijNijijSJXZX,|12201）算法描述算法描述括
14、号内序号：迭代运算的次序号。（1）任选K个初始聚类中心：Z1(1)，Z2(1)，ZK(1)算法主要流程：1.随机地选择k个对象，每个对象初始地代表了一个簇的中心；2.对剩余的每个对象，根据其与各簇中心的距离，将它赋给最近的簇；3.重新计算每个簇的平均值，更新为新的簇中心；4.不断重复2、3，直到准则函数收敛。21（2）按最小距离原则将其余样本分配到K个聚类中心中的某一 个，即：若)()(,2,1,)(minkDkKikjjiZXZX，则)(kSXj注意：注意：k迭代运算次序号；K聚类中心的个数。Nj：第j类的样本数。KjNkkjSXjj,2,11)1(XZKjkj,2,1)1(Z（3）计算各个
15、聚类中心的新向量值：（4）如果 ，则回到（2），将模式 样本逐个重新分类，重复迭代计算。这里：分别计算K个聚类中的样本均值向量，故称K-均值算法。Kjkkjj,2,1)()1(ZZKjkkjj,2,1)()1(ZZ，算法收敛，计算完毕。如果22聚类过程中，聚类中心位置或个数发生变化。“动态”聚类法2）算法讨论算法讨论 结果受到所选聚类中心的个数和其初始位置，以及模式样本的几何性质及读入次序等的影响。实际应用中需要试探不同的K值和选择不同的聚类中心起始值。23例：已知20个模式样本如下，试用K-均值算法分类。T10,0XT20,1XT31,0X T41,1XT51,2XT62,1XT72,2XT
16、82,3XT96,6XT106,7XT116,8XT127,6XT137,7XT147,8XT157,9XT168,7XT178,8XT188,9XT199,8XT209,9XT110,0)1(XZT220,1)1(XZ解：取K=2，并选：计算距离，聚类：10010|)1(|0|)1(|22212111ZXZXDD)1(1121SDDX1X：0|)1(|1|)1(|222121ZXZXDD)1(2212SDDX2X：2420110|)1(|10100|)1(|2223222131ZXZXDD)1(1321SDDX3X：10111|)1(|20101|)1(|2224222141ZXZXDD)1
17、(2412SDDX4X：2,)1(1311NSXX18,.,)1(2205422NSXXXX，可得到：计算新的聚类中心：5.00100021)(211)2(311111XXXZSXN 33.567.5)(1811)2(20421222XXXXZSXN)1()2(jjZZ2,1j 判断：，故返回第步。25 从新的聚类中心得：|)2(|)2(|212111ZXZXDD)2(11SX1X：|)2(|)2(|22021201ZXZXDD)2(220S X20X：8,)2(18211NSXXX12,.,)2(2201092NSXXX有：计算聚类中心：13.125.1)(811)3(8212111XXXX
18、ZSXN 33.767.7)(1211)3(201092222XXXXZSXN26)2()3(jjZZ2,1j 返回第步，以Z1(3)，Z2(3)为中心进行聚类。以新的聚类中心分类，求得的分类结果与前一次迭代结果相 同：)2()3(11SS)2()3(22SS 计算新聚类中心向量值，聚类中心与前一次结果相同，即：2,1,3)4(jjjZZ)3()4(jjZZ33.767.7,13.125.121ZZ，故算法收敛，得聚类中心为结果图示：27图10 K-均值算法聚类结果X1X4X3X5X8X9X7X10X2X6x1x213579135790X11X12X13X14X15X16X17X18X19X2
19、013.125.11Z33.767.72Z28 上述K-均值算法，其类型数目假定已知为K个。当K未知时，可以令K逐渐增加，此时J j 会单调减少。最初减小速度快，但当K 增加到一定数值时，减小速度会减慢，直到K=总样本数N 时，Jj=0。JjK关系曲线如下图：3）聚类准则函数）聚类准则函数Jj与与K的关系曲线的关系曲线JjA135724608109K 曲线的拐点 A 对应着接近最优的K值（J 值减小量、计算量以及分类效果的权衡）。并非所有的情况都容易找到关系曲线的拐点。迭代自组织的数据分析算法可以确定模式类的个数K。292 迭代自组织的数据分析算法迭代自组织的数据分析算法(iterative
20、self-organizing data analysis techniques algorithm,ISODATA)算法特点 加入了试探性步骤，组成人机交互的结构；可以通过类的自动合并与分裂得到较合理的类别数。相似：聚类中心的位置均通过样本均值的迭代运算决定。相异：K-均值算法的聚类中心个数不变；ISODATA的聚类中心个数变化。与K-均值算法比较：1）算法简介）算法简介30基本思路：（1）选择初始值包括若干聚类中心及一些指标。可在迭代运 算过程中人为修改，据此将N个模式样本分配到各个聚类中 心去。（3）聚类后的处理：计算各类中的距离函数等指标，按照给定的 要求，将前次获得的聚类集进行分裂或
21、合并处理，以获得新 的聚类中心，即调整聚类中心的个数。（4）判断结果是否符合要求：符合，结束；否则，回到（2）。（2）按最近邻规则进行分类。31算法共分十四步：第一 六步：预选参数，进行初始分类。为合并和分裂准备必要的数据。第七步：决定下一步是进行合并还是进行分裂。第八 十步：分裂算法。第十一 十三步：合并算法。第十四步：决定算法是否结束。2）算法描述）算法描述设有N个模式样本X1，X2，XN。预选参数，进行初始分类。第一步：预选NC个聚类中心 ，NC也是聚类过程 中实际的聚类中心个数。预选指标：,21CNZZZ32K：希望的聚类中心的数目。N：每个聚类中应具有的最少样本数。若样本少于N，则该
22、 类不能作为一个独立的聚类，应删去。S：一个聚类域中样本距离分布的标准差阈值。标准差向量的 每一分量反映样本在特征空间的相应维上，与聚类中心的 位置偏差（分散程度）。要求每一聚类内，其所有分量中 的最大分量应小于S，否则该类将被分裂为两类。C：两聚类中心之间的最小距离。若两类中心之间距离小于 C，则合并为一类。L：在一次迭代中允许合并的聚类中心的最大对数。I：允许迭代的次数。33第二步：把N个样本按最近邻规则分配到NC个聚类中。CijNi,2,1,minZXZX若 jSX则 第三步：若Sj中的样本数NjN，则取消该类，并且NC减去1。jSjjNXXZ1CNj,2,1第四步：修正各聚类中心值。第
23、五步：计算Sj类的类内平均距离 。jDjSjjjNDXZX1CNj,2,1第六步：计算总体平均距离 ，即全部样本到各自聚类中心距 离的平均距离。D CNjjjCNjjSjDNNND1111XZXN：每类应具有的 最少样本数。343)如果迭代的次数是偶数，或NC2K，即聚类中心数目大于或 等于希望数的两倍，则跳到第十一步(合并)。否则进入第八步 (分裂)。第七步：判决是进行分裂还是进行合并，决定迭代步骤等。判断分裂还是合并。1)如迭代已达I次(最后一次)，置C=0，跳到第十一步(合并)。2)若NCK/2，即聚类中心小于或等于希望数的一半，进入 第八步(分裂)。C：两聚类中心之间的最小距离。NC：
24、预选的聚类中心数。I：允许迭代的次数。K：希望的聚类中心的数目。35分裂处理。第八步：计算每个聚类中样本距离的标准差向量。对第Sj类有T2,1,jnjjj方差jSXjijijjizxN21分量：CNj,2,1是聚类数；ni,2,1是维数（特征个数）。第九步：求每个标准差向量的最大分量。j的最大分量记为 jmax，j=1,2,NC。36第十步：在最大分量集 中，如有 ，,2,1,maxCjNjSjmax1)和 ，即类内平均距离大于总体平均距离，并且Sj类中样本数很大。DDj)1(2NjN说明Sj类样本在对应方向上的标准差大于允许的值。此时，又满足以下两个条件之一：2)，即聚类数小于或等于希望数目
25、的一半。2KNC则将Zj分裂成两个新的聚类中心 和 ，并且NC加1。其中jZjZN：每个聚类中应具有的最少样本数。S：聚类域中样本距离分布的标准差阈值。maxmaxjjjkZ对应的分量maxmaxjjjkZ对应的分量10k：分裂系数若完成了分裂运算，迭代次数加1，跳回第二步；否则，继续。按邻近规则聚类37合并处理。jiijDZZ 1,2,1CNiCNij,1第十一步：计算所有聚类中心之间的距离。Si类和Sj类中心间 的距离为第十二步：比较所有Dij与C的值，将小于C的Dij按升序排列 LjLijijiDDD,2211第十三步：如果将距离为 的两类合并，得到新的聚类中心 为lljiDC：两聚类中
26、心之间的最小距离。ljljlililjlilNNNNZZZ1Ll,2,1每合并一对，NC减1。38判断结束。第十四步：若是最后一次运算(迭代次数为I)，算法结束。否则，有两种情况：1)需要由操作者修改输入参数时(试探性步骤)，跳到第一步；2)输入参数不需改变时，跳到第二步。按邻近规则聚类此时，选择两者之一，迭代次数加1，然后继续进行运算。39例：已知8个模式样本如下，试用ISODATA算法对这些样本分类。T10,0X T21,1XT53,5XT64,4XT32,2XT43,4XT74,5XT85,6XT110,0 XZ解：第一步，第一步，选NC=1，各参数预选为：4,0,4,1,2ILKCN第
27、二步，第二步，只有一个聚类中心Z1，故8,18211NXXXS第三步，第三步，因NN1，故无聚类可删除第四步，第四步，修改聚类中心T1175.238.311，SNZXX40T56.1,99.1 1第五步，第五步，计算26.21111SNDX1ZX第六步，第六步，计算D，因只有一类，故26.21 DD第七步，第七步，因不是最后一次迭代，且2/KNC故进入第八步进行分裂运算。第八步，第八步，求S1的标准差向量1，得第九步，第九步，99.1max141Smax1第十步，第十步，因且2/KNC故可将Z1分裂为两个新的聚类中心。选k=0.5，TTTT75.2,38.275.2,5.038.375.2,3
28、8.475.2,5.038.3max11max11ZZ1,121加令CNZZZZ1即迭代次数加1，跳回到第二步，进行第二次迭代运算，本次运算从第二步开始42第二步，第二步，按最近邻规则对所有样本聚类，得到两个聚类分别为3,5,222121876541NSNSXXXXXXXX第三步，第三步，因NNN21,，故无聚类可删除。第四步，第四步，修改聚类中心T12T1100.106.1,80.380.42211，SNSNZZXXXX43第五步，第五步，计算,94.0,8.0221121211SNSNDDXX1ZXZX第六步，第六步，计算D95.02181jjjDND第七步，第七步，因这是偶数次迭代，符合
29、第七步的第（3）条，故进入第十一步。第十一步，第十一步，计算聚类之间的距离，得72.41221ZZD44第十二步，第十二步，比较C12C12,DD得与第十三步，第十三步，根据第十二步的结果，聚类中心不能发生合并。第十四步，第十四步，因为不是最后一次迭代，所以要判断是否需要修改给定的参数。第二步到第六步，第二步到第六步，与前一次迭代计算的结果相同。random迭代次数加1，回到第二步。不必修改参数。45第七步，第七步，没有一种情况被满足，继续执行第八步。第八步，第八步，计算S1和S2的标准差向量21和3,5,222121876541NSNSXXXXXXXXTT82.0,82.0,75.0,75.
30、021第九步，第九步，82.0,75.0max2max1第十步，第十步，分裂条件不满足，故继续执行第十一步。46第十一步，第十一步，计算聚类之间的距离，结果与前次迭代结果相同72.41221ZZD第十二、十三步，第十二、十三步，与前一次迭代计算的结果相同。第十四步，第十四步，因为不是最后一次迭代，且不需要修改参数。故返回到第二步，迭代次数加1。第二步到第六步，第二步到第六步，与前一次迭代计算的结果相同。第七步，第七步，由于是最后一次迭代，故置0C跳到第十一步。47第十一步，第十一步，计算聚类之间的距离，结果与前次迭代结果相同72.41221ZZD第十二步，第十二步，与前次迭代结果相同第十三步，第十三步，没有合并发生。第十四步，第十四步，因为是最后一次迭代，故算法结束。聚类结果如图12。48图12 ISODATA算法聚类结果X1X4X3X5X8X7X2X6x1x213579135790谢谢！
