基于isodata算法的Iris數(shù)據(jù)分類(lèi)

1、一 實(shí)驗(yàn)?zāi)康耐ㄟ^(guò)對(duì)iris data采用isodata算法進(jìn)行聚類(lèi)，掌握isodata算法的原理以及具體實(shí)施步驟。二實(shí)驗(yàn)原理c均值算法比較簡(jiǎn)單，但它的自我調(diào)整能力也比較差。這主要表現(xiàn)在類(lèi)別數(shù)不能改變，受代表點(diǎn)初始選擇的影響也比較大。isodata算法的功能與c均值算法相比，在下列幾方面有改進(jìn)。1.考慮了類(lèi)別的合并與分裂，因而有了自我調(diào)整類(lèi)別數(shù)的能力。合并主要發(fā)生在某一類(lèi)內(nèi)樣本個(gè)數(shù)太少的情況，或兩類(lèi)聚類(lèi)中心之間距離太小的情況。為此設(shè)有最小類(lèi)內(nèi)樣本數(shù)限制，以及類(lèi)間中心距離參數(shù)。若出現(xiàn)兩類(lèi)聚類(lèi)中心距離小于的情況，可考慮將此兩類(lèi)合并。分裂則主要發(fā)生在某一類(lèi)別的某分量出現(xiàn)類(lèi)內(nèi)方差過(guò)大的現(xiàn)象，因而宜分裂成

2、兩個(gè)類(lèi)別，以維持合理的類(lèi)內(nèi)方差。給出一個(gè)對(duì)類(lèi)內(nèi)分量方差的限制參數(shù)，用以決定是否需要將某一類(lèi)分裂成兩類(lèi)。2.由于算法有自我調(diào)整的能力，因而需要設(shè)置若干個(gè)控制用參數(shù)，如聚類(lèi)數(shù)期望值，每次迭代允許合并的最大聚類(lèi)對(duì)數(shù)、及允許迭代次數(shù)等。下面我們將isodata算法的步驟列出：步驟1(確定控制參數(shù)及設(shè)置代表點(diǎn))需確定的控制參數(shù)為，聚類(lèi)期望數(shù)，一個(gè)聚類(lèi)中的最少樣本數(shù)，標(biāo)準(zhǔn)偏差控制參數(shù)，用于控制分裂，類(lèi)間距離控制參數(shù)，用于控制合并，每次迭代允許合并的最大聚類(lèi)對(duì)數(shù)，允許迭代的次數(shù)。設(shè)初始聚類(lèi)數(shù)為及聚類(lèi)中心。步驟2(分類(lèi))對(duì)所有樣本，按給定的個(gè)聚類(lèi)中心，以最小距離進(jìn)行分類(lèi)，即若 步驟3(撤消類(lèi)內(nèi)樣本數(shù)過(guò)小類(lèi)別)

3、若有任何一個(gè)類(lèi)，其樣本數(shù)，則舍去，令，將原樣本分配至其它類(lèi)；步驟4(更新均值向量)按現(xiàn)有樣本分類(lèi)結(jié)果，調(diào)整均值參數(shù) 步驟5(計(jì)算類(lèi)內(nèi)平均距離)每類(lèi)中各樣本離開(kāi)均值的平均距離 步驟6(計(jì)算整個(gè)樣本集偏離均值的平均距離) 步驟7(入口選擇)如這是最后一次迭代(取決于迭代上限)，則轉(zhuǎn)步驟11，并設(shè)置，防止合并發(fā)生。如果，則轉(zhuǎn)向步驟8，執(zhí)行分裂步驟；如果，則轉(zhuǎn)向步驟11，執(zhí)行合并步驟。步驟8(求各類(lèi)內(nèi)各分類(lèi)標(biāo)準(zhǔn)偏差)對(duì)每個(gè)聚類(lèi)，求其標(biāo)準(zhǔn)偏差式中是類(lèi)中第個(gè)樣本的第分量，是的第個(gè)分量，是第個(gè)聚類(lèi)第個(gè)分量的標(biāo)準(zhǔn)偏差，d是樣本特征維數(shù)。步驟9(求每類(lèi)具有最大標(biāo)準(zhǔn)偏差的分量) 指每類(lèi)具有最大標(biāo)準(zhǔn)偏差的分量。步驟

4、10(分裂計(jì)算步驟) 若任一個(gè)有，并且有(a) 且，或有(b) ，則把分裂成兩個(gè)聚類(lèi)，其中心相應(yīng)為與，把原來(lái)的取消，且令，由于與值設(shè)置不當(dāng)將會(huì)導(dǎo)致影響到其它類(lèi)別，因此與可按以下步驟計(jì)算： 給定一值，； 其中值應(yīng)使中的樣本到與的距離不同，但又應(yīng)使中的樣本仍然在分裂后的新樣本類(lèi)中。步驟11(計(jì)算類(lèi)間聚類(lèi)中心距離)類(lèi)與類(lèi)的類(lèi)間距離 步驟12(列出類(lèi)間距離過(guò)近者)比較與并將小于的按上升次序排列 該隊(duì)列最大個(gè)數(shù)是控制合并對(duì)數(shù)的參數(shù)步驟13(執(zhí)行合并)從類(lèi)間距離最大的兩類(lèi)開(kāi)始執(zhí)行合并過(guò)程，此時(shí)需將與合并，得 且，從第二個(gè)開(kāi)始，則要檢查其涉及類(lèi)別是否已在前面合并過(guò)程中被合并，如兩者并未被合并，則執(zhí)行合并過(guò)程

5、。步驟14(結(jié)束步驟)如是最后一次迭代則終止，否則可根據(jù)需要轉(zhuǎn)步驟1或步驟2，轉(zhuǎn)步驟1是為了更改控制數(shù)。迭代計(jì)數(shù)要加1。以上是整個(gè)isodata算法的計(jì)算步驟?？梢钥闯鰅sodata算法與c均值算法一樣，都是以與代表點(diǎn)的最小距離作為樣本聚類(lèi)的依據(jù)，因此比較適合各類(lèi)物體在特征空間以超球體分布的方式分布，對(duì)于分布形狀較復(fù)雜的情況需要采用別的度量。isodata算法與c均值算法的主要不同在于自我控制與調(diào)整的能力不同。它們的另一個(gè)不同點(diǎn)是，c均值算法的類(lèi)均值參數(shù)在每個(gè)樣本歸入時(shí)隨即修改，因而稱為逐個(gè)樣本修正法，而isodata算法的均值向量或聚類(lèi)中心參數(shù)是在每一次迭代分類(lèi)后修正的，因而稱為成批樣本修正

6、法。三 實(shí)驗(yàn)過(guò)程及結(jié)果分析按照算法過(guò)程進(jìn)行仿真，首先設(shè)置算法中所需要的控制參數(shù)，控制參數(shù)的選取有多種選擇組合，這里，我們先設(shè)置一組控制參數(shù)，對(duì)iris data進(jìn)行聚類(lèi)，說(shuō)明算法的實(shí)施過(guò)程以及對(duì)得到的結(jié)果進(jìn)行分析。參數(shù)設(shè)置如下圖所示：其中，確定初始聚類(lèi)中心個(gè)數(shù)后，在150個(gè)原始數(shù)據(jù)中隨機(jī)挑選10個(gè)作為聚類(lèi)中心，然后對(duì)原始150個(gè)數(shù)據(jù)以該10個(gè)聚類(lèi)中心以最小距離進(jìn)行聚類(lèi)。結(jié)果如下：結(jié)果中的center矩陣為聚類(lèi)中心矩陣，每一列代表一聚類(lèi)中心，每一列前4行為聚類(lèi)中心的4個(gè)分量，第5行為隸屬于該類(lèi)的數(shù)據(jù)個(gè)數(shù)。將類(lèi)內(nèi)個(gè)數(shù)過(guò)少（小于10）的聚類(lèi)中心刪除，并對(duì)所有數(shù)據(jù)依照調(diào)整后聚類(lèi)中心重新進(jìn)行聚類(lèi)。完成聚

7、類(lèi)后，計(jì)算每類(lèi)的均值，作為該類(lèi)新的聚類(lèi)中心。上圖中的第二個(gè)center矩陣即為已經(jīng)完成均值計(jì)算的每類(lèi)的聚類(lèi)中心。 完成聚類(lèi)中心初始化后，開(kāi)始進(jìn)行迭代，在第一次迭代中(iterative=1)，迭代次數(shù)為奇數(shù)，但是當(dāng)前聚類(lèi)個(gè)數(shù)，所以直接進(jìn)入聚類(lèi)中心合并過(guò)程，結(jié)果如下所示： 上圖中，sortofdis矩陣為兩兩聚類(lèi)中心之間的距離矩陣，并按從大到小排列。每一列代表2類(lèi)之間的距離，第一行為距離，第2，3行為兩類(lèi)的類(lèi)別。值得注意的是類(lèi)別號(hào)即對(duì)應(yīng)為聚類(lèi)中心在聚類(lèi)中心矩陣center中的列數(shù)。進(jìn)入合并步驟不代表一定進(jìn)行合并處理，當(dāng)兩類(lèi)的距離小于合并閾值(thmerge=2.5)時(shí)，才進(jìn)行合并處理。且每次迭代

8、，最多進(jìn)行2次合并(mergenum=2)，且必須是不同的4類(lèi)。由結(jié)果觀察到，第3,4類(lèi)進(jìn)行合并，第6,7類(lèi)進(jìn)行合并。合并后得到新的聚類(lèi)中心矩陣newcenter，可看到，新的矩陣相對(duì)于之前的聚類(lèi)中心矩陣，少了2列。按照得到的新聚類(lèi)中心，重新對(duì)原始數(shù)據(jù)進(jìn)行聚類(lèi)，得到center矩陣，并檢驗(yàn)是否有類(lèi)內(nèi)樣本個(gè)數(shù)過(guò)少的聚類(lèi)中心，若沒(méi)有，對(duì)每類(lèi)數(shù)據(jù)進(jìn)行平均，得到更新后的聚類(lèi)中心矩陣（即上圖中最后一center矩陣），第一次迭代完成。 在第2次迭代中(iterative=2)，迭代次數(shù)為偶數(shù)，直接進(jìn)入合并步驟。由上圖可看出，將3，4類(lèi)進(jìn)行了合并處理（3,4類(lèi)僅代表其聚類(lèi)中心在當(dāng)前聚類(lèi)中心矩陣第3，4列，

9、與第一次迭代的3,4類(lèi)不是一樣的）。之后的處理步驟與之前一致，得到平均后的聚類(lèi)中心矩陣。在第一次迭代中(iterative=3)，迭代次數(shù)為奇數(shù)，當(dāng)前聚類(lèi)個(gè)數(shù)，所以進(jìn)入聚類(lèi)中心分裂過(guò)程，結(jié)果如下所示：進(jìn)入分裂步驟，但是否進(jìn)行分裂處理還需判斷每個(gè)聚類(lèi)中樣本到聚類(lèi)中心的標(biāo)準(zhǔn)差，將每個(gè)聚類(lèi)的標(biāo)準(zhǔn)差向量按列排列，即得到標(biāo)準(zhǔn)差矩陣stdofeach，其中列數(shù)代表聚類(lèi)個(gè)數(shù)，每行代表聚類(lèi)中心的一個(gè)分量。因?yàn)閕ris數(shù)據(jù)為4維數(shù)據(jù)，則標(biāo)準(zhǔn)差矩陣即為4行。因?yàn)?個(gè)聚類(lèi)的標(biāo)準(zhǔn)差向量中的每個(gè)分量都小于分裂閾值(thsplit=0.6)，所以不進(jìn)行分裂處理，進(jìn)入合并過(guò)程。3個(gè)聚類(lèi)中心的兩兩距離也都大于合并閾值，所以也

10、不進(jìn)行合并處理。該次迭代后，按相同的方法得到平均后的聚類(lèi)中心矩陣。在第4次迭代中(iterative=4)，迭代次數(shù)為偶數(shù)，直接進(jìn)入合并步驟?？梢钥吹?，第4次迭代中沒(méi)有進(jìn)行合并處理，只是對(duì)數(shù)據(jù)按照第3次迭代得到的新聚類(lèi)中心重新進(jìn)行聚類(lèi)，并對(duì)聚類(lèi)后的每類(lèi)樣本進(jìn)行平均，得到新的聚類(lèi)中心矩陣。值得注意的是，在第4次迭代時(shí)，進(jìn)行平均后的聚類(lèi)中心與為平均之前完全一致，說(shuō)明第3次聚類(lèi)結(jié)果與第4次聚類(lèi)結(jié)果是完全一致的。說(shuō)明算法在第4次迭代時(shí)即已收斂，完成了分類(lèi)。以后迭代次數(shù)結(jié)果如下：可以看到，第5次結(jié)果與第4次也完全一致，且不會(huì)再對(duì)現(xiàn)有類(lèi)別進(jìn)行分裂。之后迭代結(jié)果再無(wú)變化，就不將其貼出。最后得到的聚類(lèi)中心如下

11、所示：按照該聚類(lèi)中心，對(duì)數(shù)據(jù)進(jìn)行聚類(lèi)，結(jié)果如下：以上是對(duì)150個(gè)原始數(shù)據(jù)分類(lèi)的結(jié)果，前4列為每個(gè)數(shù)據(jù)的4個(gè)特征，第5列為該數(shù)據(jù)的序號(hào)，第6列為該數(shù)據(jù)聚類(lèi)結(jié)果。類(lèi)別數(shù)1,2,3對(duì)應(yīng)于聚類(lèi)中心向量在聚類(lèi)矩陣中的列數(shù)，例如類(lèi)別為1，則說(shuō)明該數(shù)據(jù)隸屬于聚類(lèi)中心矩陣中第1列的聚類(lèi)中心。 可以看到，前50個(gè)數(shù)據(jù)應(yīng)分為一類(lèi)，實(shí)驗(yàn)結(jié)果顯示對(duì)前50個(gè)數(shù)據(jù)分類(lèi)完全正確。第51到100號(hào)數(shù)據(jù)應(yīng)屬于一類(lèi)，但聚類(lèi)結(jié)果顯示有2個(gè)數(shù)據(jù)被分為了第3類(lèi)。第101到150號(hào)數(shù)據(jù)應(yīng)屬于一類(lèi)，聚類(lèi)結(jié)果顯示其中有14個(gè)數(shù)據(jù)被聚到了第2類(lèi)。這也與之前的實(shí)驗(yàn)結(jié)果相近，即1到50號(hào)數(shù)據(jù)與其他可完全分開(kāi)，后兩組數(shù)據(jù)互相之間不可以完全區(qū)分。改變初始聚類(lèi)中心個(gè)數(shù)，再進(jìn)行聚類(lèi)，結(jié)果如下：可以看到，第3個(gè)分量大于分裂閾值，所以進(jìn)行分裂處理，分裂處理按照如下公式進(jìn)行 其中選為0.4。注意，只對(duì)第3各分量進(jìn)行修正。 可以看到，在迭代到第8