动态聚类法

模式识别——动态聚类法K-均值算法&ISODATA算法专业：班级：学号：姓名：一、实验目的1．理解聚类的过程2．理解并掌握K-均值算法的过程3．理解并掌握ISODATA算法（迭代自组织数据分析算法）的过程二、实验原理2.1K-均值算法第一步：选择K个初始聚类中心，𝑍1(1),𝑍2(1),…,𝑍𝑘(1)第二步：逐个将待分模式样本{X}按最小距离准则分配给某个聚类中心𝑍𝑗，j=1,2…,k若𝐷𝑗(𝑘)=min{‖𝑋−𝑍𝑖(𝑘)‖}𝑖=1,2…𝑘则X∈𝑆𝑗(𝑘)其中，k表示迭代次序，𝑆𝑗表示第j个聚类，𝑍𝑖是聚类中心。第三步：分配完成后，计算各个聚类的新中心𝑍𝑗(𝑘+1)=1𝑁𝑗×∑𝑋𝑋∈𝑆𝑗(𝑘)其中，𝑁𝑗是第j类中所含样本数第四步：如果𝑍𝑗(𝑘+1)≠𝑍𝑗(𝑘)则回到第二步，将模式样本重新聚类，重复迭代计算。如果𝑍𝑗(𝑘+1)=𝑍𝑗(𝑘)，则算法收敛，结束。2.2ISODATA算法ISODATA算法加入一些试探步骤，构成人机交互结构，可以利用中间结果所获得的经验进行调整第一步：将N个样本模式{X}读入，预选𝑁𝑐个初始聚类中心{𝑍1,𝑍2,…,𝑍𝑐}，个数可以不等于预期的中心个数预定初值：K：预期的聚类中心数目𝜃𝑁：每一类中最少的样本数目𝜃𝑐：两聚类中心之间的最小距离，小于此两聚类合并𝜃𝑠：一个聚类域中样本距离分布标准差L：在一次迭代运算中可以合并的聚类中心的个数I：迭代运算的次数第二步：将各模式样本按最小距离准则分给各聚类𝐷𝑗=min{‖𝑋−𝑍𝑖(𝑘)‖}则X∈𝑆𝑗(𝑘)第三步：如果𝑆𝑗中的样本数𝑁𝑗𝜃𝑁，取消该子集，𝑁𝑐=𝑁𝑐−1第四步：修正各聚类中心：𝑍𝑗(𝑘+1)=1𝑁𝑗×∑𝑋𝑋∈𝑆𝑗(𝑘)𝑗=1,2…𝑁𝑐第五步：计算𝑆𝑗中样本到聚类中心的平均距离𝐷𝑗̅=1𝑁𝑗×∑‖𝑋−𝑍𝑗‖𝑋∈𝑆𝑗(𝑘)第六步：计算全部模式样本与相应聚类中心的总平均距离(𝑁𝑗为每一类中样本数)𝐷̅=1𝑁×∑𝑁𝑗𝑁𝑐𝑗=1×𝐷𝑗̅第七步：判断分裂，合并及迭代运算1.如果迭代次数已达I次（最后一次），置𝜃𝑐=0（无需新中心），跳到第十四步，结束2.如果𝑁𝑐≤𝐾2，即聚类中心的数目等于或不到规定的一半，进入第八步，分裂。3.如果迭代运行次数是偶数或𝑁𝑐≥2𝐾，跳到第十一步，合并。如果不符合上面两个条件，则进入第八步。第八步：分裂处理计算每个聚类𝑆𝑗中各样本到聚类中心的标准差矢量𝜎𝑗=[𝜎1𝑗,𝜎2𝑗…𝜎𝑛𝑗]𝑇𝜎𝑖𝑗=√1𝑁𝑗×∑(𝑋𝑖𝑘−𝑍𝑖𝑗)2𝑋∈𝑆𝑗(𝑘)其中i表示n维中的第i个分量，i=1,2,…n，j表示第j类，j=1,2,…𝑁𝑐第九步：对各个标准差{𝜎𝑗}求其最大分量max{𝜎𝑖𝑗}=𝜎𝑗𝑚𝑎𝑥第十步：在最大分量集{𝜎𝑗𝑚𝑎𝑥}中，若有𝜎𝑗𝑚𝑎𝑥𝜃𝑠，同时满足：（1）𝐷𝑗̅𝐷𝑗和𝑁𝑗2(𝜃𝑁+1)（2）𝑁𝑐≤𝐾2做分裂处理，将𝑍𝑗分裂成两个新中心，𝑍𝑗+和𝑍𝑗−，同时𝑁𝑐=𝑁𝑐+1𝑍𝑗+=[𝑍1𝑗,𝑍2𝑗,…(𝑍𝑖𝑗+𝑘𝜎𝑗𝑚𝑎𝑥)…𝑍𝑛𝑗]𝑇𝑍𝑗−=[𝑍1𝑗,𝑍2𝑗,…(𝑍𝑖𝑗−𝑘𝜎𝑗𝑚𝑎𝑥)…𝑍𝑛𝑗]𝑇其中0k≤1，即将±𝑘𝜎𝑗𝑚𝑎𝑥置于𝑍𝑗的最大分量之上，完成分裂之后，返回第二步，否则继续。合并：第十一步：计算全部类中心间的距离𝐷𝑖𝑗=‖𝑍𝑖−𝑍𝑗‖第十二步：比较𝐷𝑖𝑗和给定的最小距离𝜃𝑐，将𝐷𝑖𝑗𝜃𝑐的值排序{𝐷𝑖1𝑗1,𝐷𝑖2𝑗2,…𝐷𝑖𝐿𝑗𝐿}，𝐷𝑖1𝑗1𝐷𝑖2𝑗2⋯𝐷𝑖𝐿𝑗𝐿第十三步：将距离为𝐷𝑖𝑙𝑗𝑙的两个中心𝑍𝑖𝑙，𝑍𝑗𝑙合并𝑍𝑙∗=1𝑁𝑖𝑙+𝑁𝑗𝑙[𝑁𝑖𝑙𝑍𝑖𝑙+𝑁𝑗𝑙𝑍𝑗𝑙]l=1,2,…L虽然l=1,2,…L，但实验中，我们每次只合并一个最小的第十四步：若迭代已达最后一次，迭代结束否则到第一步，可改变参数，若无需改变参数则跳到第二步，继续迭代。三、实验过程与分析3.1K-均值算法实验中，对iris数据进行聚类，由于已知iris数据为三类，即setosa，versicolour和virginica。因此为了后面判断聚类是否正确，对三类数据分别设置了标志位，第一类数据setosa第五列置1，第二类versicolour第五列置0，第三类数据virginica第五列置-1。聚类结果如表1所示：表中每个数字表示实验所得的聚类中包含真正属于这一类的数据个数。例如第一行数据表示实验所得的第一聚类有50个数，这50个数中有50个是属于setosa，0个属于versicolour，0个属于virginica。即可以看出对第一类数据完全聚类正确。表1K-均值算法实验结果setosaversicolourvirginica第一类5000第二类04814第三类0236实验结果分析：第一类数据完全聚类正确，第二类和第三类数据聚类时会发生错误。说明二三类数据较为相似，难以进行完全正确的聚类实验结果与初始聚类中心的选取有一定的关系，如果选取不当将陷入死循环。例如当初始的聚类中心全部同一类中的数据时，无法得到聚类结果3.2ISODATA算法首先，实验中初值的预定：预期的聚类中心数目：K=3预设聚类中心数目：Nc=4每一类中最少的样本数目：𝜃𝑁=30两聚类中心之间的最小距离，小于此两聚类合并：𝜃𝑐=0.8一个聚类域中样本距离分布标准差：𝜃𝑠=0.3在一次迭代运算中可以合并的聚类中心的个数：L=1迭代运算的次数：I=50分裂参数：r=0.2实验结果如表2所示：表2ISODATA算法实验结果setosaversicolourvirginica第一类5000第二类04714第三类0336实验结果分析：当预定参数如上面所示时，实验结果表明，第一类数据可以准确的聚类，但是二三类数据会有一定的错误。3.2.1改变预设聚类中心数目Nc对实验结果的影响实验中，预设一个初始的聚类中心数目Nc，这个数值会随着迭代的进行而改变，现在研究其他初始条件不变，仅改变Nc时对聚类结果的影响。实验结果如下：（1）Nc=2表3Nc=2时ISODATA算法实验结果setosaversicolourvirginica第一类0236第二类04814第三类5000（2）Nc=3表4Nc=3时ISODATA算法实验结果setosaversicolourvirginica第一类0336第二类5000第三类04714（3）Nc=4表5Nc=4时ISODATA算法实验结果setosaversicolourvirginica第一类5000第二类04714第三类0336（4）Nc=5表6Nc=5时ISODATA算法实验结果setosaversicolourvirginica第一类0236第二类5000第三类04814实验结果分析：从实验结果可以看出，当其余的初始条件不变时，改变初始的聚类中心数目Nc不会对实验结果产生影响。这是因为实验时会根据迭代的具体情况进行分裂合并等操作改变聚类中心的数目，所以初始的聚类中心数目对实验结果不会产生影响3.2.2改变每一类中最少的样本数目𝜽𝑵对实验结果的影响实验中，需要预设每一类中最少的样本数目𝜃𝑁，现在研究其他初始条件不变，仅改变𝜃𝑁时对聚类结果的影响（1）𝜃𝑁=20表7𝜃𝑁=20时ISODATA算法实验结果setosaversicolourvirginica第一类0236第二类2600第三类2400第四类04814（2）𝜃𝑁=30表8𝜃𝑁=30时ISODATA算法实验结果setosaversicolourvirginica第一类0236第二类04814第三类5000（3）𝜃𝑁=50表9𝜃𝑁=50时ISODATA算法实验结果setosaversicolourvirginica第一类04750第二类5030（4）𝜃𝑁=60表10𝜃𝑁=60时ISODATA算法实验结果setosaversicolourvirginica第一类37513第二类134537实验结果分析：从实验中可以看出，当增大每一类中的最少样本数目𝜃𝑁时，聚类结果的类别数减少。这是显然的，因为当某类中的样本数目少于预设的最少样本数目时，则取消该子集当𝜃𝑁偏小时，例如𝜃𝑁=20，虽然可以进行分类，但是会将原本均属于setosa的数据分到两个聚类中当𝜃𝑁偏大时，例如𝜃𝑁=50，可以看出由于setosa数据与其他两类数据差别较大，所以还是能够进行较好的分类。但是我们已知待分类的三类数据中每一类有50个，所以若𝜃𝑁=50，由于𝜃𝑁过大还是导致setosa数据的聚类结果中有错误𝜃𝑁=60时，可以看出结果完全错误，这也是可以想见的，每一类数据只有50个而将聚类时每一类的最少样本数目设为60，结果肯定是错误的3.2.1改变两聚类中心之间的最小距离𝜽𝒄对实验结果的影响实验时，在进行聚类合并时，有一个最小距离𝜃𝑐，当两聚类中心之间的距离小于此距离时则将两聚类合并。现在研究其他初始条件不变，仅改变𝜃𝑐对于聚类结果的影响。（1）𝜃𝑐=0.2表11𝜃𝑐=0.2时ISODATA算法实验结果setosaversicolourvirginica第一类2600第二类2400第三类0026第四类2323第五类271（2）𝜃𝑐=0.4表12𝜃𝑐=0.4时ISODATA算法实验结果setosaversicolourvirginica第一类2600第二类2400第三类04814第四类0236（3）𝜃𝑐=0.6表13𝜃𝑐=0.6时ISODATA算法实验结果setosaversicolourvirginica第一类2100第二类2900第三类04814第四类0236（4）𝜃𝑐=0.8表14𝜃𝑐=0.8时ISODATA算法实验结果setosaversicolourvirginica第一类5000第二类04814第三类0236实验结果分析：从𝜃𝑐的增大过程可以看出，当增大聚类中心之间的距离时，聚类数目减少。这是由于只有当两聚类中心之间的距离大于𝜃𝑐时才会被分裂，但是当𝜃𝑐增大时，中心距离较小的类别将会被合并，使得聚类数目减少从四种情况可以看出，第一类数据很容易与其余两类进行分类，即使当因聚类中心间距离较小而将第一类数据分为两类时也不会有错误（2）（3）（4）对比可以看出，增大聚类中心之间的距离时，可以使聚类数目减少，同属于setosa得两类可以合并；但同时可以看出，versicolour和virginica的分类已经不会变化，仍有错误。从以上分析可以看出，改变𝜃𝑐的大小会影响最后的聚类个数，但是对于分类效果的改善没有很明显的作用3.2.2改变一个类别中样本距离分布标准差𝜽𝒔对聚类结果的影响实验时，在进行聚类分裂时，有一个指标为样本距离分布标准差𝜃𝑠。现在研究其他初始条件不变，仅改变𝜃𝑠对于聚类结果的影响。（1）𝜃𝑠=0.1表15𝜃𝑠=0.1时ISODATA算法实验结果setosaversicolourvirginica第一类2100第二类2900第三类04814第四类0236（2）𝜃𝑠=0.3表16𝜃𝑠=0.3时ISODATA算法实验结果setosaversicolourvirginica第一类2600第二类2400第三类04814第四类0236（3）𝜃𝑠=0.5表17𝜃𝑠=0.5时ISODATA算法实验结果s