3/3基于isodata算法的Iris數(shù)據(jù)分類一．實驗目的

通過對Irisdata采用Isodata算法進行聚類，掌握Isodata算法的原理以及具體實施步驟。

二．實驗原理

C均值算法比較簡單，但它的自我調(diào)整能力也比較差。這主要表現(xiàn)在類別數(shù)不能改變，受代表點初始選擇的影響也比較大。ISODATA算法的功能與C均值算法相比，在下列幾方面有改進。

1.考慮了類別的合并與分裂，因而有了自我調(diào)整類別數(shù)的能力。合并主要發(fā)生在某一類內(nèi)樣本個數(shù)太少的情況，或兩類聚類中心之間距離太小的情況。為此設有最小類內(nèi)樣本數(shù)限制Nθ，以及類間中心距離參數(shù)Cθ。若出現(xiàn)兩類聚類中心距離小于Cθ的情況，可考慮將此兩類合并。

分裂則主要發(fā)生在某一類別的某分量出現(xiàn)類內(nèi)方差過大的現(xiàn)象，因而宜分裂成兩個類別，以維持合理的類內(nèi)方差。給出一個對類內(nèi)分量方差的限制參數(shù)Sθ，用以決定是否需要將某一類分裂成兩類。

2.由于算法有自我調(diào)整的能力，因而需要設置若干個控制用參數(shù)，如聚類數(shù)期望值K，每次迭代允許合并的最大聚類對數(shù)L、及允許迭代次數(shù)I等。

下面我們將ISODATA算法的步驟列出：步驟1(確定控制參數(shù)及設置代表點)

需確定的控制參數(shù)為，聚類期望數(shù)K，一個聚類中的最少樣本數(shù)Nθ，標準偏差控制參數(shù)，用于控制分裂Sθ，類間距離控制參數(shù)，用于控制合并Cθ，每次迭代允許合并的最大聚類對數(shù)L，允許迭代的次數(shù)I。設初始聚類數(shù)為c及聚類中心,1,2...,imic=。

步驟2(分類)

對所有樣本，按給定的c個聚類中心，以最小距離進行分類，即若

步驟3(撤消類內(nèi)樣本數(shù)過小類別)

若有任何一個類jΓ，其樣本數(shù)jNNθ，并且有(a)jDD>且2(1)jNNθ>+，或

有(b)/2cK≤，則把jΓ分裂成兩個聚類，其中心相應為jm+與jm-

，把原來的jm取消，

且令1cc=+，由于jm+與jm-值設置不當將會導致影響到其它類別，因此jm+與jm-

可按以下步驟計算：

給定一k值，01k，所以直接進入聚類中心合并過程，結果如下所示：

上圖中，sortofdis矩陣為兩兩聚類中心之間的距離矩陣，并按從大到小排列。每一列代表2類之間的距離，第一行為距離，第2，3行為兩類的類別。值得注意的是類別號即對應為聚類中心在聚類中心矩陣center中的列數(shù)。進入合并步驟不代表一定進行合并處理，當兩類的距離小于合并閾值(thmerge=2.5)時，才進行合并處理。且每次迭代，最多進行2次合并(mergenum=2)，且必須是不同的4類。由結果觀察到，第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列，與第一次迭代的3,4類不是一樣的）。之后的處理步驟與之前一致，得到平均后的聚類中心矩陣。

在第一次迭代中(iterative=3)，迭代次數(shù)為奇數(shù)，當前聚類個數(shù)32NcK=<，所以進入聚類中心分裂過程，結果如下所示：

進入分裂步驟，但是否進行分裂處理還需判斷每個聚類中樣本到聚類中心的標準差，

將每個聚類的標準差向量按列排列，即得到標準差矩陣stdofeach，其中列數(shù)代表聚類個數(shù)，每行代表聚類中心的一個分量。因為Iris數(shù)據(jù)為4維數(shù)據(jù)，則標準差矩陣即為4行。因為3個聚類的標準差向量中的每個分量都小于分裂閾值(thsplit=0.6)，所以不進行分裂處理，進入合并過程。3個聚類中心的兩兩距離也都大于合并閾值，所以也不進行合并處理。該次迭代后，按相同的方法得到平均后的聚類中心矩陣。

在第4次迭代中(iterative=4)，迭代次數(shù)為偶數(shù)，直接進入合并步驟。

可以看到，第4次迭代中沒有進行合并處理，只是對數(shù)據(jù)按照第3次迭代得到的新聚類中心重新進行聚類，并對聚類后的每類樣本進行平均，得到新的聚類中心矩陣。值得注意的是，在第4次迭代時，進行平均后的聚類中心與為平均之前完全一致，說明第3次聚類結果與第4次聚類結果是完全一致的。說明算法在第4次迭代時即已收斂，完成了分類。以后迭代次數(shù)結果如下：

可以看到，第5次結果與第4次也完全一致，且不會再對現(xiàn)有類別進行分裂。之后迭代結果再無變化，就不將其貼出。

最后得到的聚類中心如下所示：

按照該聚類中心，對數(shù)據(jù)進行聚類，結果如下：

以上是對150個原始數(shù)據(jù)分類的結果，前4列為每個數(shù)據(jù)的4個特征，第5列為該數(shù)據(jù)的序號，第6列為該數(shù)據(jù)聚類結果。類別數(shù)1,2,3對應于聚類中心向量在聚類矩陣中的列數(shù)，例如類別為1，則說明該數(shù)據(jù)隸屬于聚類中心矩陣中第1列的聚類中心。

可以看到，前50個數(shù)據(jù)應分為一類，實驗結果顯示對前50個數(shù)據(jù)分類完全正確。第51到100號數(shù)據(jù)應屬于一類，但聚類結果顯示有2個數(shù)據(jù)被分為了第3類。第101到150號數(shù)據(jù)應屬于一類，聚類結果顯示其中有14個數(shù)據(jù)被聚到了第2類。這也與之前的實驗結果相近，即1到50號數(shù)據(jù)與其他可完全分開，后兩組數(shù)據(jù)互相之間不可以完全區(qū)分。

改變初始聚類中心個數(shù)，再進行聚類，結果如下：

可以看到，第3個分量大于分裂閾值，所以進行分裂處理，分裂處理按照如下公式進行

其中k選為0.4。注意，只對第3各分量進行修正。

可以看到，在迭代到第8次時，結果已收斂，聚類完成。最終的聚類中心矩陣為：

對原始數(shù)據(jù)的分類結果如下：