C語言編程實現ISODATA算法

劉明曉，王旭光

（1.西安鐵路職業技術學院，陜西西安710014；2.西安航天自動化股份有限公司，陜西西安710014）

C語言編程實現ISODATA算法

劉明曉1，王旭光2

（1.西安鐵路職業技術學院，陜西西安710014；2.西安航天自動化股份有限公司，陜西西安710014）

ISODATA算法是聚類分析算法中較常使用的算法，是非監督狀態下基于統計模式識別的一種動態的聚類算法，在模式識別算法中具有較強的實用性。介紹了ISODATA算法的計算過程和具體實現方法，結合C語言編程工具對具體的樣本進行了聚類分析，得到了較為理想的聚類分析結果，研究了參數的選取對分類結果所產生的影響。

ISODATA算法；聚類；C語言編程；模式識別

1 引言

ISODATA算法又稱為動態聚類算法或迭代自組織數據分析算法，是一種對樣本進行聚類劃分的算法［1］。ISODATA算法是以均值迭代來確定聚類中心，其與K均值算法的不同是加入了人機對話環節，這使得參數可以隨時進行調整，該算法同時還引入了分裂與合并的功能［2］。分裂是指當某樣本的標準差大于設定的閾值或該樣本的數目超過某一特定的閾值時將該樣本分為兩個樣本，或在該樣本數目少于某一閾值時對樣本進行分裂；合并是指當某兩個樣本的樣本中心間距小于某一閾值時將兩個樣本合并為一個樣本，同時當某一樣本的樣本數目少于設定的閾值時即將該樣本取消，歸入其他樣本中去［3、4］。因此，ISODATA 算法較其他算法相比更加靈活，實用性更強。

ISODATA算法是一種無監督的分類方法，首先選擇若干個樣本點作為聚類中心，再按照最小距離的原則使其余樣本向各個聚類中心聚集，這樣便得到了初始的分類樣本，然后再判斷形成的初始聚類結果是否滿足要求，若不滿足則可將各個聚類進行合并或分裂處理進而形成新的聚類中心，再次判斷新形成的聚類結果是否滿足要求。如此經過多次迭代直到新形成的聚類滿足要求即可停止聚類劃分。

2 ISODATA基本流程和算法步驟

2.1 ISODATA 基本流程

ISODATA 基本流程［5、6］圖如圖 1 所示。

2.2 ISODATA 算法步驟

ISODATA算法步驟如下：

（1）設置聚類分析控制參數。主要包括：所要求的聚類中心數K；一個待分類的樣本應包括的樣本數目θN；一個類別樣本標準差閾值θS；各聚類中心之間的閾值θC；任何一次迭代過程中允許合并或分裂的樣本對數L；允許迭代的最多對數I。

圖1 ISODATA算法流程圖

（2）將準備分類的樣本值讀入。

（3）以距離聚類中心距離最近為原則對讀入的樣本值進行初始化聚類［7］。

（4）聚類分裂［8］。分裂是指在同一聚類中如果樣本數目太過密集或聚類中樣本的數目太稀疏，那么在該空間中還存在其他聚類中心，這時就需要對該聚類進行分裂。分裂是通過對各樣本分布的標準差的上限值進行設定，如果樣本距離聚類中心的距離大于標準差的上限值則被劃分到另一聚類中，否則該樣本仍保留在該聚類中，然后再次轉到步驟（2）。

（5）聚類合并［8］。合并是指兩聚類的聚類中心相聚較近，該兩聚類的樣本沒有進行分裂的必要性，則可將這兩聚類進行合并。具體方法是設置聚類中心之間的距離下限值，如果兩聚類中心的距離小于該下限值或是某一聚類中樣本的數目過少不足以成為一類時，那么將該聚類中的樣本合并到其他聚類中去。然后再次轉到步驟（2）。

（6）按照設定的程序對步驟（2）中輸入的樣本反復進行分類、判別、合并或者分裂操作，如果形成的聚類滿足要求或是進行合并和分裂的次數達到了規定的次數則聚類分類結束。

3 具體算例與分析

在C語言編程環境下，利用ISODATA算法將輸入的 10 個樣本組成樣本集｛x0，x1，x2，x3，x4，x5，x6，x7，x8，x9｝，并對其進行分類。這 10 個樣本值分別如 下：x0｛0，0，0，0｝，x1｛3，0，8，0｝，x2｛2，0，2，0｝，x3｛1，0，1，0｝，x4｛5，0，3，0｝，x5｛4，0，8，0｝，x6｛6，0，3，0｝，x7｛5，0，4，0｝，x8｛6，0，4，0｝，x9｛7，0，5，0｝，對其進行聚類分析后的樣本分布情況如圖2所示。

圖2 樣本坐標圖

從圖2中可以直觀地看出，樣本集分為3類是合理的，其中｛x0，x2，x3｝為第 1 聚類，｛x4，x6，x7，x8，x9｝為第2 聚類，｛x1，x5｝為第3 聚類。分別取 K＝2、3、4，運用ISODATA算法進行迭代計算，并將K取不同值時的控制參數和分類結果分別以表格的形式列出來。各個控制參數的設定值如表1所示，經過ISODATA算法進行分類之后輸出的分類結果如表2所示。

表1 控制參數設定值表

通過分析表2的聚類分析結果，可以看出，將聚類數目K設定為3時，經過ISODATA算法進行合并與分裂之后所輸出的聚類結果與預期的結果是一致的，從而驗證了ISODATA算法的正確性。另外，由于在ISODATA算法中加入了人機對話環節，故可通過參數調整來改變聚類的結果。從表2也可以看出，當聚類中樣本的標準差閾值θS、聚類中心之間距離的閾值θC和允許迭代的最多次數I選取不同的值時，也會對聚類結果產生不同的影響。通過參數控制來研究參數選取對分類結果產生的影響，下面就聚類數K＝3時，通過改變其他參數的設定，來驗證這三個參數是如何影響聚類結果的。

表2 輸出的分類結果表

首先控制 K，θN，θC，L，I參數的值不變，當聚類樣本的標準差閾值分別取 θS＝2.5，1.0，0.5 時，控制參數如表3所示，輸出的聚類結果如表4所示。

表3 控制參數表

表4 輸出的聚類結果表

從表3、表4中可以看出，標準差參數θS設定值越大，分裂的可能性就越小，分類數目也越少，因此，要想得到理想的聚類結果還要通過試驗選擇合適的標準差閾值。

控制 K，θN，θS，L，I的設定值不變，分別取 θC＝5，2，1時，其控制參數如表5所示，輸出的聚類結果如表6所示。

表5 控制參數表

表6 輸出的分類結果表

從表5、表6得出的分類結果可以看出，合并參數越小，ISODATA算法迭代過程中合并的可能性也越小，因此，這在較大程度上保留了上一迭代過程的分類結果。

但是當合并參數過大時，會導致分類不到位。控制 K，θN，θS，θC，L 設定值不變，允許迭代的次數分別取 I＝20，5，2 時，其控制參數如表 7 所示，輸出的聚類分析結果如表8所示。

表7 控制參數表

由表7、表8得出的結果可知，迭代次數設置過大會導致過度分類；迭代次數設置過小，又會導致分類不充分，因此選擇合適的迭代次數很重要，其對聚類分析結果影響較大。同時，標準差以及合并參數改變后，聚類結果將受到迭代次數設定的影響，當迭代進行到第10次時，如果保持標準差及合并參數不變，那么聚類結果也將保持不變。

表8 輸出的分類結果表

4 結束語

本文介紹了基于C語言編程的ISODATA算法原理及具體操作步驟，并結合具體算例進行了聚類分析，得到了較為理想的聚類分析結果，同時，通過改變可影響聚類分析結果的各參數的設定值來研究了各參數對聚類結果的影響程度。ISODATA算法與其他算法的不同是在進行聚類分析之前需要人為設置一些參數，充分體現了人機交互的特點。人機交互過程是將很多人為經驗應用到聚類分析之中，這在很大程度上減少了聚類的盲目性，有利于樣本朝著較好的聚類方向發展。

［1］胡飛翔.基于云計算的聚類算法的MapReduce化研究［D］.沈陽：東北大學，2012.

［2］楊淑瑩.圖像模式識別－VC＋＋技術實現［M］.北京：清華大學出版社，2005.205－212.

［3］王 萍.基于核心集粗化的多層次聚類算法［D］.南京：航空航天大學，2014.

［4］李宗杰.基于聚類分析的風電場輸出功率模型的研究［D］.北京：華北電力大學，2012.

［5］舒 寧.模式識別的理論與方法［M］.武昌：武漢大學出版社，2004.69－73.

［6］李元萍，李元良.MATLAB編程實現ISODATA算法［J］.礦業研究與開發，2005，25（3）：79－80.

［7］曾江源.ISODATA算法的原理與實現［J］.科技廣場，2009.

［8］楊小明，羅 云.ISODATA算法的實現與分析［J］.采礦技術，2006，6（2）：67－68.

Realization of ISODATA algorithm by C language programming

LIU Ming－xiao1，WANG Xu－guang2
（1.Xi’an Railway Vocational and Technical College，Xi’an 710014，China；2.Xi’an Aerospace Automation Co.，Ltd.，Xi’an 710014，China）

The ISODATA algorithm is a commonly used algorithm in clustering analysis，which is a dynamic clustering algorithm under unsupervised state based on statistical pattern recognition，and has strong practicability in pattern recognition algorithm.Firstly，the ISODATA algorithm and the implementation methods are introduced，and then the specific samples are clustered and analyzed combined with the C language programming tools，and thus the ideal clusteringresultsareobtained.Theinfluenceoftheparameterselectionontheclassificationresultsisalsoanalyzed.

ISODATA algorithm；clustering；C language programming；pattern recognition

TP311

A

1005—7277（2016）05—0047—04

劉明曉（1987－），女，河南焦作人，助教，碩士，主要研究方向為電力系統及其自動化。

2016－07－11