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

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

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

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

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

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

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

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

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

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

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