基于isodata算法的Iris数据分类

一．实验目的通过对Irisdata采用Isodata算法进行聚类，掌握Isodata算法的原理以及具体实施步骤。二．实验原理C均值算法比较简单，但它的自我调整能力也比较差。这主要表现在类别数不能改变，受代表点初始选择的影响也比较大。ISODATA算法的功能与C均值算法相比，在下列几方面有改进。1.考虑了类别的合并与分裂，因而有了自我调整类别数的能力。合并主要发生在某一类内样本个数太少的情况，或两类聚类中心之间距离太小的情况。为此设有最小类内样本数限制N，以及类间中心距离参数C。若出现两类聚类中心距离小于C的情况，可考虑将此两类合并。分裂则主要发生在某一类别的某分量出现类内方差过大的现象，因而宜分裂成两个类别，以维持合理的类内方差。给出一个对类内分量方差的限制参数S，用以决定是否需要将某一类分裂成两类。2.由于算法有自我调整的能力，因而需要设置若干个控制用参数，如聚类数期望值K，每次迭代允许合并的最大聚类对数L、及允许迭代次数I等。下面我们将ISODATA算法的步骤列出：步骤1(确定控制参数及设置代表点)需确定的控制参数为，聚类期望数K，一个聚类中的最少样本数N，标准偏差控制参数，用于控制分裂S，类间距离控制参数，用于控制合并C，每次迭代允许合并的最大聚类对数L，允许迭代的次数I。设初始聚类数为c及聚类中心,1,2...,imic。步骤2(分类)对所有样本，按给定的c个聚类中心，以最小距离进行分类，即若步骤3(撤消类内样本数过小类别)若有任何一个类j，其样本数jNN，则舍去j，令1cc，将j原样本分配至其它类；步骤4(更新均值向量)按现有样本分类结果，调整均值参数步骤5(计算类内平均距离)每类中各样本离开均值的平均距离步骤6(计算整个样本集偏离均值的平均距离)步骤7(入口选择)如这是最后一次迭代(取决于迭代上限I)，则转步骤11，并设置0C，防止合并发生。如果/2cK，则转向步骤8，执行分裂步骤；如果2cK，则转向步骤11，执行合并步骤。步骤8(求各类内各分类标准偏差)对每个聚类j，求其标准偏差式中kiy是j类中第k个样本的第i分量，jim是jm的第i个分量，ij是第j个聚类第i个分量的标准偏差，D是样本特征维数。步骤9(求每类具有最大标准偏差的分量)指每类具有最大标准偏差的分量。步骤10(分裂计算步骤)若任一个max,1,2,...,jjc有maxjs，并且有(a)jDD且2(1)jNN，或有(b)/2cK，则把j分裂成两个聚类，其中心相应为jm与jm，把原来的jm取消，且令1cc，由于jm与jm值设置不当将会导致影响到其它类别，因此jm与jm可按以下步骤计算：给定一k值，01k；其中k值应使j中的样本到jm与jm的距离不同，但又应使j中的样本仍然在分裂后的新样本类中。步骤11(计算类间聚类中心距离)i类与j类的类间距离步骤12(列出类间距离过近者)比较ijD与c并将小于c的ijD按上升次序排列该队列最大个数是控制合并对数的参数L步骤13(执行合并)从类间距离最大的两类开始执行合并过程，此时需将jm与im合并，得且1cc，从第二个22ijD开始，则要检查其涉及类别是否已在前面合并过程中被合并，如两者并未被合并，则执行合并过程。步骤14(结束步骤)如是最后一次迭代则终止，否则可根据需要转步骤1或步骤2，转步骤1是为了更改控制数。迭代计数要加1。以上是整个ISODATA算法的计算步骤。可以看出ISODATA算法与C均值算法一样，都是以与代表点的最小距离作为样本聚类的依据，因此比较适合各类物体在特征空间以超球体分布的方式分布，对于分布形状较复杂的情况需要采用别的度量。ISODATA算法与C均值算法的主要不同在于自我控制与调整的能力不同。它们的另一个不同点是，C均值算法的类均值参数在每个样本归入时随即修改，因而称为逐个样本修正法，而ISODATA算法的均值向量或聚类中心参数是在每一次迭代分类后修正的，因而称为成批样本修正法。三．实验过程及结果分析按照算法过程进行仿真，首先设置算法中所需要的控制参数，控制参数的选取有多种选择组合，这里，我们先设置一组控制参数，对Irisdata进行聚类，说明算法的实施过程以及对得到的结果进行分析。参数设置如下图所示：其中，确定初始聚类中心个数后，在150个原始数据中随机挑选10个作为聚类中心，然后对原始150个数据以该10个聚类中心以最小距离进行聚类。结果如下：结果中的center矩阵为聚类中心矩阵，每一列代表一聚类中心，每一列前4行为聚类中心的4个分量，第5行为隶属于该类的数据个数。将类内个数过少（小于10）的聚类中心删除，并对所有数据依照调整后聚类中心重新进行聚类。完成聚类后，计算每类的均值，作为该类新的聚类中心。上图中的第二个center矩阵即为已经完成均值计算的每类的聚类中心。完成聚类中心初始化后，开始进行迭代，在第一次迭代中(iterative=1)，迭代次数为奇数，但是当前聚类个数72NcK，所以直接进入聚类中心合并过程，结果如下所示：上图中，sortofdis矩阵为两两聚类中心之间的距离矩阵，并按从大到小排列。每一列代表2类之间的距离，第一行为距离，第2，3行为两类的类别。值得注意的是类别号即对应为聚类中心在聚类中心矩阵center中的列数。进入合并步骤不代表一定进行合并处理，当两类的距离小于合并阈值(thmerge=2.5)时，才进行合并处理。且每次迭代，最多进行2次合并(mergenum=2)，且必须是不同的4类。由结果观察到，第3,4类进行合并，第6,7类进行合并。合并后得到新的聚类中心矩阵newcenter，可看到，新的矩阵相对于之前的聚类中心矩阵，少了2列。按照得到的新聚类中心，重新对原始数据进行聚类，得到center矩阵，并检验是否有类内样本个数过少的聚类中心，若没有，对每类数据进行平均，得到更新后的聚类中心矩阵（即上图中最后一center矩阵），第一次迭代完成。在第2次迭代中(iterative=2)，迭代次数为偶数，直接进入合并步骤。由上图可看出，将3，4类进行了合并处理（3,4类仅代表其聚类中心在当前聚类中心矩阵第3，4列，与第一次迭代的3,4类不是一样的）。之后的处理步骤与之前一致，得到平均后的聚类中心矩阵。在第一次迭代中(iterative=3)，迭代次数为奇数，当前聚类个数32NcK，所以进入聚类中心分裂过程，结果如下所示：进入分裂步骤，但是否进行分裂处理还需判断每个聚类中样本到聚类中心的标准差，将每个聚类的标准差向量按列排列，即得到标准差矩阵stdofeach，其中列数代表聚类个数，每行代表聚类中心的一个分量。因为Iris数据为4维数据，则标准差矩阵即为4行。因为3个聚类的标准差向量中的每个分量都小于分裂阈值(thsplit=0.6)，所以不进行分裂处理，进入合并过程。3个聚类中心的两两距离也都大于合并阈值，所以也不进行合并处理。该次迭代后，按相同的方法得到平均后的聚类中心矩阵。在第4次迭代中(iterative=4)，迭代次数为偶数，直接进入合并步骤。可以看到，第4次迭代中没有进行合并处理，只是对数据按照第3次迭代得到的新聚类中心重新进行聚类，并对聚类后的每类样本进行平均，得到新的聚类中心矩阵。值得注意的是，在第4次迭代时，进行平均后的聚类中心与为平均之前完全一致，说明第3次聚类结果与第4次聚类结果是完全一致的。说明算法在第4次迭代时即已收敛，完成了分类。以后迭代次数结果如下：可以看到，第5次结果与第4次也完全一致，且不会再对现有类别进行分裂。之后迭代结果再无变化，就不将其贴出。最后得到的聚类中心如下所示：按照该聚类中心，对数据进行聚类，结果如下：以上是对150个原始数据分类的结果，前4列为每个数据的4个特征，第5列为该数据的序号，第6列为该数据聚类结果。类别数1,2,3对应于聚类中心向量在聚类矩阵中的列数，例如类别为1，则说明该数据隶属于聚类中心矩阵中第1列的聚类中心。可以看到，前50个数据应分为一类，实验结果显示对前50个数据分类完全正确。第51到100号数据应属于一类，但聚类结果显示有2个数据被分为了第3类。第101到150号数据应属于一类，聚类结果显示其中有14个数据被聚到了第2类。这也与之前的实验结果相近，即1到50号数据与其他可完全分开，后两组数据互相之间不可以完全区分。改变初始聚类中心个数，再进行聚类，结果如下：可以看到，第3个分量大于分裂阈值，所以进行分裂处理，分裂处理按照如下公式进行其中k选为0.4。注意，只对第3各分量进行修正。可以看到，在迭代到第8次时，结果已收敛，聚类完成。最终的聚类中心矩阵为：对原始数据的分类结果如下：由聚类结果可得，第一组数据完全分类正确，第二组数据有3个数据分类错误，第三组数据有14个数据分类错误。由以上两组实验结果可得，Isodata算法可以对Iris数据得到较为理想的分类结果，实验结果不依赖于初始聚类中心个数，但与各控制参数关系较大，实验时应反复调整，已得到最佳结果。