【品质管理资料】基于isodata算法的Iris数据分类精编版

1、品质管理一.实验目的通过对Iris data采用Isodata算法进行聚类，掌握Isodata算法的原理以及具体实施步骤。二实验原理C均值算法比较简单，但它的自我调整能力也比较差。这主要表现在类别数不能改变，受代表点初始选择的影响也比较大。ISODATA算法的功能与C均值算法相比，在下列几方面有改进。1考虑了类别的合并与分裂，因而有了自我调整类别数的能力。合并主要发生在某一类 内样本个数太少的情况，或两类聚类中心之间距离太小的情况。为此设有最小类内样本数限制入，以及类间中心距离参数九。若出现两类聚类中心距离小于尢的情况，可考虑将此两类合并。分裂则主要发生在某一类别的某分量出现类内方差过大的现象

2、，因而宜分裂成两个类 别，以维持合理的类内方差。给出一个对类内分量方差的限制参数出，用以决定是否需要将某一类分裂成两类。2由于算法有自我调整的能力，因而需要设置若干个控制用参数，如聚类数期望值K，每次迭代允许合并的最大聚类对数L、及允许迭代次数I等。下面我们将ISODATA算法的步骤列出：步骤1（确定控制参数及设置代表点 ）需确定的控制参数为，聚类期望数K , 一个聚类中的最少样本数 vN，标准偏差控制参数，用于控制分裂 出，类间距离控制参数，用于控制合并，每次迭代允许合并的最大聚类对数L,允许迭代的次数I。设初始聚类数为 c及聚类中心mi,i =1,2,c。步骤2（分类）对所有样本，按给定的

3、 c个聚类中心，以最小距离进行分类，即若|厂呦|<|厂隧|j工上则代口步骤3（撤消类内样本数过小类别）若有任何一个类-j，其样本数Nj ：入，则舍去-j，令c二c-1，将】j原样本分配 至其它类；步骤4（更新均值向量）按现有样本分类结果，调整均值参数叫=十工尹 J = kN疋步骤5（计算类内平均距离）每类中各样本离开均值的平均距离si订习Vs II a严r,步骤6（计算整个样本集偏离均值的平均距离）品质管理步骤7（入口选择）如这是最后一次迭代（取决于迭代上限I ）,则转步骤11，并设置= °，防止合并发生。如果C乞K / 2，则转向步骤8,执行分裂步骤; 如果c _2K，则转向

4、步骤11,执行合并步骤。步骤8（求各类内各分类标准偏差） 对每个聚类j，求其标准偏差式中yki是j类中第k个样本的第i分量，mji是mj的第i个分量，二0是第j个聚类第i 个分量的标准偏差，D是样本特征维数。步骤9（求每类具有最大标准偏差的分量）巧-QWK * j -tC指每类具有最大标准偏差的分量。步骤10（分裂计算步骤）若任一个-jmax, j =1,2,.,C 有二 jmax *，并且有（a） Dj D 且 Nj2N1），或有（b） c乞K/2，则把-j分裂成两个聚类，其中心相应为mj与 m，把原来的mj取消,且令c = c 1，由于mj与m值设置不当将会导致影响到其它类别，因此mj与m

5、可按以下步骤计算：给定一 k值，0讣：1；G =上中叱其中k值应使-j中的样本到mj与m的距离不同，但又应使-j中的样本仍然在分裂后的新样本类中。步骤11（计算类间聚类中心距离）i类与j类的类间距离q =11 啤朋J II? = l,2r .-,C -1,J = I +lj +步骤12（列出类间距离过近者）比较Dj与入并将小于 化的Dij按上升次序排列% J%,1<L该队列最大个数是控制合并对数的参数L步骤13（执行合并）从类间距离最大的两类开始执行合并过程，此时需将mj与mj合并，得且c二c -1，从第二个Dj2j2开始，则要检查其涉及类别是否已在前面合并过程中被合并，如两者并未被合并

6、，则执行合并过程。步骤14（结束步骤）如是最后一次迭代则终止，否则可根据需要转步骤1或步骤2,转步骤1是为了更改控制数。迭代计数要加 1。以上是整个ISODATA算法的计算步骤。可以看出ISODATA算法与C均值算法一样，都是以与代表点的最小距离作为样本聚类的依据，因此比较适合各类物体在特征空间以超球体分布的方式分布，对于分布形状较复杂的情况需要采用别的度量。ISODATA算法与C均值算法的主要不同在于自我控制与调整的能力不同。它们的另一个不同点是，C均值算法的类均值参数在每个样本归入时随即修改，因而称为逐个样本修正法，而ISODATA算法的均值向量或聚类中心参数是在每一次迭代分类后修正的，因

7、而称为成批样本修正法。三实验过程及结果分析按照算法过程进行仿真，首先设置算法中所需要的控制参数，控制参数的选取有多种选择组合，这里，我们先设置一组控制参数，对Iris data进行聚类，说明算法的实施过程以及对得到的结果进行分析。参数设置如下图所示：初始化控制参数jnin_in_catagory=10; desiredcatagory=3; maxt ire=10;thsplit=O, 6;mergenum=2;thmerge=2* 5;mit ialnujii= 10 ;郴耦 一个聚类中的昴少样本數勰敬希望得到的类别数眦霭紬迭代最大次数%标准偏差控制参数，用于控制分裂%港代时合井过程中最多的

8、合井次数%合并时的类间距离阈值%初始聚类中心数目其中，确定初始聚类中心个数后，在150个原始数据中随机挑选10个作为聚类中心,然后对原始150个数据以该10个聚类中心以最小距离进行聚类。结果如下：Cqu社nil Tindof覘華以下序号歟据作曲初塢聚耍中心choose 二91928363851嗣89117148center 二4,4000氐 70005.2Q005, 00004.90007. QQOOgr 00005-60006.5000S. 50002.900D3. 80003.50003. 20003.60003. 20Q02.70003-00003,00003. 00001.400D1.

9、7000I.50DD1.2000I.4D004.70005.10004.10005.50005. 20000. 20000. 3000i. 20000. 20000.10001.4000R60001.30001.S0002. 00008. 00006. 000018. 000010. 00008.000010. 000022.000031.000024.000013. 0000某些廉类样本SfcilO.需擀其删去，丼更曲分类cerrter 二6.21334. 69506.66006. 04095.5B397.01676. 55383. 09603.D1002.71362.67743. 066?

10、3.13851.EI671.38004.59004.91364.00655. 99175.27690,27670.20001.42001, 6909L.25162, 05572.13S530. 000020 000010.GOOD22,00OQ31.QDDD24.0000iS.flflDO结果中的center矩阵为聚类中心矩阵，每一列代表一聚类中心，每一列前4行为聚类中心的 4个分量，第5行为隶属于该类的数据个数。将类内个数过少(小于10)的聚类中心删除，并对所有数据依照调整后聚类中心重新进行聚类。完成聚类后，计算每类的均值，作为该类新的聚类中心。上图中的第二个center矩阵即为已经完成均值

11、计算的每类的聚类中心。完成聚类中心初始化后，开始进行迭代，在第一次迭代中(iterative=1)，迭代次数为奇数,但是当前聚类个数 Nc =7 2K，所以直接进入聚类中心合并过程，结果如下所示:Cauand Tindoiterative =1进入合笄步陳sortofdis =CoLuiuts I throush 118.771?7.73777.48606.45106,31002, DDQO2+ QQiQOhODOQL DQOO2,000000007.00006.00007.0 DOO3. 0000GdIwitis12 through 212.862?2-78262.46172. ieoeLS

12、3971. 00004,00003.00003-0 D004,00005. OiQOD民 00006.00005a 00005- 0000浪 XA5.98915.02334. 7024.62234. 14943-68832. OQQDL DODO|+QQQQ£ QDOD2, 0QO05+ QQQQ4.00003.00004.00006.00005. 00007-00001.74361.42?L 286?1.024D0. 32094-00003-0 DOO1, 0000S. OOQD3. 00007.000000002. OOQO7.00004. aooo本次迭代进行舍井处巡newce

13、ntar =孔 23442.80634. . 81251.3063氐 B54I3.09196r EM2.09195. 21333. 6500L 506?0. 2F674. 69503.0950L 3SDO0-20005. 58392.67744. Q0651.2516eenter =6.-23442. 30634.8125|+D6340.00006. B54I3.09195. 74062,091932.DOOO5. 21333. 65001.5167G 2F6728. 00004.6950XO95OI.3SOOCL 200022-00005. 58392. 6F?44. 0066L 25162

14、8.0000center =6.25252.85504.8160L62504000006.91253.100D5.84592U31232.DOOO5. 24293. 66T91.6000 a 2B2128.GOOD札 70453.122?1.4136D+20Q022.00005.53212. 63573.96071.228628.0000上图中，sortofdis矩阵为两两聚类中心之间的距离矩阵，并按从大到小排列。每一列代表2类之间的距离，第一行为距离，第2，3行为两类的类别。值得注意的是类别号即对应为聚类中心在聚类中心矩阵cen ter中的列数。进入合并步骤不代表一定进行合并处理，当两类的距

15、离小于合并阈值 (thmerge=2.5)时，才进行合并处理。且每次迭代，最多进行2次合并(mergenum=2)，且必须是不同的 4类。由结果观察到，第 3,4类进行合并，第6,7类进行合 并。合并后得到新的聚类中心矩阵n ewce nter，可看到，新的矩阵相对于之前的聚类中心矩阵，少了 2列。按照得到的新聚类中心，重新对原始数据进行聚类，得到center矩阵，并检验是否有类内样本个数过少的聚类中心，若没有，对每类数据进行平均，得到更新后的聚类中心矩阵(即上图中最后一center矩阵)，第一次迭代完成。在第2次迭代中(iterative=2)，迭代次数为偶数，直接进入合并步骤。由上图可看出

16、，将3,4类进行了合并处理(3,4类仅代表其聚类中心在当前聚类中心矩阵第3, 4列，与第一次迭代的 3,4类不是一样的)。之后的处理步骤与之前一致，得到平均后的 聚类中心矩阵。Nc =3 ： 2K，所以进在第一次迭代中(iterative=3)，迭代次数为奇数，当前聚类个数 入聚类中心分裂过程，结果如下所示：进入分裂步骤，但是否进行分裂处理还需判断每个聚类中样本到聚类中心的标准差,将每个聚类的标准差向量按列排列，即得到标准差矩阵stdofeach,其中列数代表聚类个数，每行代表聚类中心的一个分量。因为Iris数据为4维数据，则标准差矩阵即为4行。因为3个聚类的标准差向量中的每个分量都小于分裂阈

17、值(thsplit=0.6)，所以不进行分裂处理，进入合并过程。3个聚类中心的两两距离也都大于合并阈值，所以也不进行合并处理。该次迭代 后，按相同的方法得到平均后的聚类中心矩阵。在第4次迭代中(iterative=4)，迭代次数为偶数，直接进入合并步骤。CoKiajid Vindnw? 城iterative s4进胆合并歩骤scctotdi?=?.59d84.33643.25I. JOOOL 00002.00003k00002”QQ0Q畀QOQQ可以看到，第4次迭代中没有进行合并处理，只是对数据按照第 3次迭代得到的新聚类中心重新进行聚类，并对聚类后的每类样本进行平均，得到新的聚类中心矩阵。值

18、得注意的是，在第4次迭代时，进行平均后的聚类中心与为平均之前完全一致，说明第3次聚类结果与第4次聚类结果是完全一致的。说明算法在第4次迭代时即已收敛，完成了分类。以后迭代次数结果如下：CaBsaii'dl Yindloviterative =stdafeach 二0,34890.46260,48780. 37530.29390.28620. 1719Q.504.B0.4821Du 10430.29510. 2762可以看到，第5次结果与第4次也完全一致，且不会再对现有类别进行分裂。之后迭代结果再无变化，就不将其贴出。最后得到的聚类中心如下所示：按照该聚类中心，对数据进行聚类，结果如下:

19、Eile £di t於aphicw Dehu 武 Eemktop iindo Klp鼻諂船电 &工呂曲：田m日白口m Array Editoi匚叵|区121693.25.72312131225.6284 9122212377286.721233124632.74.91.B1242125673.3P5.72.112531257.23.21.812631276.2284 81.812721286 134.91.B1282129642.85.62.112931307.235 81.B13031317.42.8'6.11.913131327.93.86.4213231336.

20、42.85.62213331346 3285.11.513421356.12661.41353価阳36J2.313631376.33.4r5.62.41373138643 1551.81383139634 81.813921406 93.1542.114031416.73.15.62.41413142693.15.12.314231435.8275.11.914321446.8325.92.31443145_-_1673.35.72.51453仙6735.22.31463忖6.32551.914721436.535221483149623.45.42.314931505935.11.91502

21、234567ini以上是对150个原始数据分类的结果，前4列为每个数据的4个特征，第5列为该数据的序号，第6列为该数据聚类结果。类别数1,2,3对应于聚类中心向量在聚类矩阵中的列数，例如类别为1,则说明该数据隶属于聚类中心矩阵中第1列的聚类中心。可以看到，前50个数据应分为一类，实验结果显示对前50个数据分类完全正确。第51到100号数据应属于一类，但聚类结果显示有2个数据被分为了第 3类。第101到150号数据应属于一类，聚类结果显示其中有14个数据被聚到了第 2类。这也与之前的实验结果相近，即1到50号数据与其他可完全分开，后两组数据互相之间不可以完全区分。改变初始聚类中心个数，再进行聚类

22、，结果如下:%初始化控制参数min_in_cat agory=l 0;%一个聚类中的最少样本数desiredeatagory=3;%希望得到的类别数jiiaxt ijne=10;%迭代擾大钦數*thBplit=Or 6;%标准偏差控制参数，用千控制芬裂jiLergenujiL=2;RM矗为曲迭代时台并过程中撮多的合并次数thmerge=2T 5*広置电址合并时的类间距离阈値mxt ialnujii=l;初始聚荚中心数目可以看到，第3个分量大于分裂阈值，所以进行分裂处理，分裂处理按照如下公式进行G =如）叱枫；=® +加眄=叫其中k选为0.4。注意，只对第3各分量进行修正。I Conand Tindoviterative 二3进入分裂步骤st dof 已且uh =0. 61950. 33630. 313