劉明曉，王旭光

（1.西安鐵路職業(yè)技術(shù)學(xué)院，陜西西安710014；2.西安航天自動化股份有限公司，陜西西安710014）

C語言編程實現(xiàn)ISODATA算法

劉明曉1，王旭光2

（1.西安鐵路職業(yè)技術(shù)學(xué)院，陜西西安710014；2.西安航天自動化股份有限公司，陜西西安710014）

ISODATA算法是聚類分析算法中較常使用的算法，是非監(jiān)督狀態(tài)下基于統(tǒng)計模式識別的一種動態(tài)的聚類算法，在模式識別算法中具有較強(qiáng)的實用性。介紹了ISODATA算法的計算過程和具體實現(xiàn)方法，結(jié)合C語言編程工具對具體的樣本進(jìn)行了聚類分析，得到了較為理想的聚類分析結(jié)果，研究了參數(shù)的選取對分類結(jié)果所產(chǎn)生的影響。

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

1 引言

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

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

2 ISODATA基本流程和算法步驟

2.1 ISODATA 基本流程

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

2.2 ISODATA 算法步驟

ISODATA算法步驟如下：

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

圖1 ISODATA算法流程圖

（2）將準(zhǔn)備分類的樣本值讀入。

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

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

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

（6）按照設(shè)定的程序?qū)Σ襟E（2）中輸入的樣本反復(fù)進(jìn)行分類、判別、合并或者分裂操作，如果形成的聚類滿足要求或是進(jìn)行合并和分裂的次數(shù)達(dá)到了規(guī)定的次數(shù)則聚類分類結(jié)束。

3 具體算例與分析

在C語言編程環(huán)境下，利用ISODATA算法將輸入的 10 個樣本組成樣本集｛x0，x1，x2，x3，x4，x5，x6，x7，x8，x9｝，并對其進(jìn)行分類。這 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｝，對其進(jìn)行聚類分析后的樣本分布情況如圖2所示。

圖2 樣本坐標(biāo)圖

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

表1 控制參數(shù)設(shè)定值表

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

表2 輸出的分類結(jié)果表

首先控制 K，θN，θC，L，I參數(shù)的值不變，當(dāng)聚類樣本的標(biāo)準(zhǔn)差閾值分別取 θS＝2.5，1.0，0.5 時，控制參數(shù)如表3所示，輸出的聚類結(jié)果如表4所示。

表3 控制參數(shù)表

表4 輸出的聚類結(jié)果表

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

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

表5 控制參數(shù)表

表6 輸出的分類結(jié)果表

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

但是當(dāng)合并參數(shù)過大時，會導(dǎo)致分類不到位?？刂?K，θN，θS，θC，L 設(shè)定值不變，允許迭代的次數(shù)分別取 I＝20，5，2 時，其控制參數(shù)如表 7 所示，輸出的聚類分析結(jié)果如表8所示。

表7 控制參數(shù)表

由表7、表8得出的結(jié)果可知，迭代次數(shù)設(shè)置過大會導(dǎo)致過度分類；迭代次數(shù)設(shè)置過小，又會導(dǎo)致分類不充分，因此選擇合適的迭代次數(shù)很重要，其對聚類分析結(jié)果影響較大。同時，標(biāo)準(zhǔn)差以及合并參數(shù)改變后，聚類結(jié)果將受到迭代次數(shù)設(shè)定的影響，當(dāng)?shù)M(jìn)行到第10次時，如果保持標(biāo)準(zhǔn)差及合并參數(shù)不變，那么聚類結(jié)果也將保持不變。

表8 輸出的分類結(jié)果表

4 結(jié)束語

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

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

［2］楊淑瑩.圖像模式識別－VC＋＋技術(shù)實現(xiàn)［M］.北京：清華大學(xué)出版社，2005.205－212.

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

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

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

［6］李元萍，李元良.MATLAB編程實現(xiàn)ISODATA算法［J］.礦業(yè)研究與開發(fā)，2005，25（3）：79－80.

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

［8］楊小明，羅 云.ISODATA算法的實現(xiàn)與分析［J］.采礦技術(shù)，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－），女，河南焦作人，助教，碩士，主要研究方向為電力系統(tǒng)及其自動化。

2016－07－11