劉明曉，王旭光

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

C語(yǔ)言編程實(shí)現(xiàn)ISODATA算法

劉明曉1，王旭光2

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

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

ISODATA算法；聚類；C語(yǔ)言編程；模式識(shí)別

1 引言

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

ISODATA算法是一種無監(jiān)督的分類方法，首先選擇若干個(gè)樣本點(diǎn)作為聚類中心，再按照最小距離的原則使其余樣本向各個(gè)聚類中心聚集，這樣便得到了初始的分類樣本，然后再判斷形成的初始聚類結(jié)果是否滿足要求，若不滿足則可將各個(gè)聚類進(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；一個(gè)待分類的樣本應(yīng)包括的樣本數(shù)目θN；一個(gè)類別樣本標(biāo)準(zhǔn)差閾值θS；各聚類中心之間的閾值θC；任何一次迭代過程中允許合并或分裂的樣本對(duì)數(shù)L；允許迭代的最多對(duì)數(shù)I。

圖1 ISODATA算法流程圖

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

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

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

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

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

3 具體算例與分析

在C語(yǔ)言編程環(huán)境下，利用ISODATA算法將輸入的 10 個(gè)樣本組成樣本集｛x0，x1，x2，x3，x4，x5，x6，x7，x8，x9｝，并對(duì)其進(jìn)行分類。這 10 個(gè)樣本值分別如 下：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｝，對(duì)其進(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)行迭代計(jì)算，并將K取不同值時(shí)的控制參數(shù)和分類結(jié)果分別以表格的形式列出來。各個(gè)控制參數(shù)的設(shè)定值如表1所示，經(jīng)過ISODATA算法進(jìn)行分類之后輸出的分類結(jié)果如表2所示。

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

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

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

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

表3 控制參數(shù)表

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

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

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

表5 控制參數(shù)表

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

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

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

表7 控制參數(shù)表

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

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

4 結(jié)束語(yǔ)

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

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

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

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

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

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

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

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

［8］楊小明，羅 云.ISODATA算法的實(shí)現(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－），女，河南焦作人，助教，碩士，主要研究方向?yàn)殡娏ο到y(tǒng)及其自動(dòng)化。

2016－07－11