一種基于初始點(diǎn)密度最大的改進(jìn)型ISODATA聚類算法

李潤青+謝明鴻+黃冰晶

摘要：針對ISODATA對初始聚類點(diǎn)選取較為敏感，不能處理噪聲點(diǎn)的缺陷，提出一種基于結(jié)合密度最大的改進(jìn)型ISODATA的劃分聚類方法D-ISODATA。基于高局部密度點(diǎn)距離和局部密度最大原則，優(yōu)化聚類初始點(diǎn)并去除噪聲點(diǎn)。根據(jù)考察對象所處空間區(qū)域的密度分布情況劃分基本簇，結(jié)合ISODATA聚類算法良好的自適應(yīng)性，有效地對數(shù)據(jù)集進(jìn)行分類。實(shí)驗(yàn)表明，這種基于密度聚類的改進(jìn)型ISODATA算法能有效去除噪聲點(diǎn)，改善初始中心點(diǎn)選擇對最后聚類算法的影響，并且具有良好的自適應(yīng)性，對于數(shù)據(jù)集處理的準(zhǔn)確性優(yōu)于傳統(tǒng)K-means算法和ISODATA算法。

關(guān)鍵詞：高局部密度點(diǎn)距離；初始點(diǎn)選擇；噪聲點(diǎn)；ISODATA；D-ISODATA 算法

DOIDOI：10.11907/rjdk.172074

中圖分類號：TP312

文獻(xiàn)標(biāo)識碼：A 文章編號：1672-7800（2017）012-0094-05

Abstract：Aiming at the defect that ISODATA is sensitive to the initial clustering points and can not deal with the noise points， this paper proposes an improved ISODATA clustering method based on the combination of maximum density D-ISODATA. Based on the principle of “high local density point distance” and local density maximum principle， the initial points and the noise points are optimized. Through the investigation of the basic object to divide the cluster density distribution area， combined with the ISODATA clustering algorithm is a good “adaptive”， classify the data set， experiments show that the improved ISODATA algorithm can effectively remove the noise density clustering based on improved effect on the final selection of the initial center point clustering algorithm， and have good adaptability. The accuracy of data processing is better than the traditional partition based clustering algorithms such as K-means algorithm and IOSDATA algorithm and the clustering algorithm based on density division such as DBSCAN algorithm.

Key Words：high local density point distance； optimal initial point selection； noise point； ISODATA； D-ISODATA algorithm

0 引言

聚類是一種流行的數(shù)據(jù)挖掘技術(shù)，聚類算法被廣泛應(yīng)用于諸多領(lǐng)域，包括模式識別、機(jī)器學(xué)習(xí)、圖像處理、信息檢索等[1]，在數(shù)據(jù)挖掘中起到重要作用。

現(xiàn)有聚類算法可以分為劃分法[2]、層次法[3]、密度法[4]、網(wǎng)格法[5]和模型法[6-7]。劃分法首先創(chuàng)建k個(gè)劃分，然后利用循環(huán)定位技術(shù)將對象從一個(gè)劃分移到另一個(gè)更合適的劃分，以此改善劃分質(zhì)量。層次法創(chuàng)建一個(gè)層次以分解給定的數(shù)據(jù)集，該方法可分為自上而下（分解）和自下而上（合并）兩種操作方式。為彌補(bǔ)分解與合并的不足，層次合并經(jīng)常要與其它聚類方法相結(jié)合，如循環(huán)定位。密度法根據(jù)元素密度完成對象聚類。它根據(jù)對象周圍的密度（如DBSCAN）不斷增長聚類。網(wǎng)格法首先將對象空間劃分為有限個(gè)單元以構(gòu)成網(wǎng)格結(jié)構(gòu)，然后利用網(wǎng)格結(jié)構(gòu)完成聚類。模型法則假設(shè)每個(gè)聚類的模型并發(fā)現(xiàn)適合相應(yīng)模型的數(shù)據(jù)。

以上聚類算法具有各自的特點(diǎn)，在不同領(lǐng)域也有著各自的優(yōu)缺點(diǎn)?；趧澐值木垲?，如K-means算法[8]，具有算法簡單、速度快等優(yōu)點(diǎn)，因此在實(shí)踐中使用最為廣泛。但此方法只能對簡單的數(shù)據(jù)進(jìn)行分類，并且存在分類結(jié)果受初始點(diǎn)選擇影響較大的缺點(diǎn)?；诿芏鹊木垲惙椒?，如DBSCAN[9]，由于不需要輸入聚類個(gè)數(shù)，能發(fā)現(xiàn)任意形狀簇，但是對于密度變化不明顯或密度變化過于復(fù)雜的數(shù)據(jù)，卻存在著處理效果不理想的問題，同時(shí)該算法還存在處理結(jié)果對噪聲點(diǎn)比較敏感的缺陷[10]。

相對于K-means算法，基于劃分的ISODATA算法[11]更加靈活，能自動調(diào)整類別中心和類別個(gè)數(shù)。其自組織性也能減小一些初始點(diǎn)選擇所帶來的影響，使得該算法得到了廣泛應(yīng)用。但初始點(diǎn)選擇對ISODATA算法的影響卻始終存在，當(dāng)數(shù)據(jù)中存在較多噪聲點(diǎn)時(shí)，初始點(diǎn)選擇對分類效果的影響會更加明顯。

本文針對上述傳統(tǒng)ISODATA聚類算法的缺點(diǎn)，提出一種改進(jìn)算法（D-ISODATA）。該算法能夠有效處理噪聲點(diǎn)，并且通過高局部密度點(diǎn)距離和局部密度最大原則自動選擇初始點(diǎn)（而非經(jīng)典ISODATA的隨機(jī)選取初始點(diǎn)方法），可以極大改善最終聚類效果。

1 相關(guān)研究

迭代自組織的數(shù)據(jù)分析算法也稱ISODATA聚類算法，此算法與K-means算法有相似之處，即聚類中心由樣本均值的迭代決定。但I(xiàn)SODATA算法加入了一些試探性的步驟，即能吸取中間結(jié)果所得到的經(jīng)驗(yàn)，在迭代過程中可以將類一分為二，也可以將兩類合并，即“自組織”。ISODATA算法通過設(shè)置初始參數(shù)而引入人機(jī)對話環(huán)節(jié)，并使用合并和分裂等機(jī)制，當(dāng)兩類聚類中心小于某個(gè)閾值時(shí)，將它們合并為一類。當(dāng)某類的標(biāo)準(zhǔn)差大于某一閾值或其樣本數(shù)目超過某一閾值時(shí)，將其分裂為兩類。在某類樣本數(shù)目小于某一閾值時(shí)，將其取消。這樣根據(jù)初始類聚中心和設(shè)定的類別數(shù)目等參數(shù)迭代，最終得到一個(gè)比較理想的聚類結(jié)果。ISODATA算法是一種常用的聚類分析方法，也是一種非監(jiān)督學(xué)習(xí)方法。

ISODATA算法基本步驟如下：①選擇某些初始值，可選不同的參數(shù)指標(biāo)，也可在迭代過程中人為修改，以將N個(gè)模式樣本按指標(biāo)分配到各聚類中心；②計(jì)算各類諸樣本的距離指標(biāo)函數(shù)；③按給定要求將前一次獲得的聚類集進(jìn)行分裂與合并處理從而獲得新的聚類中心；④重新進(jìn)行迭代運(yùn)算，計(jì)算各項(xiàng)指標(biāo)判斷聚類結(jié)果是否符合要求。經(jīng)過多次迭代后若聚類結(jié)果收斂則運(yùn)算結(jié)束。

可以發(fā)現(xiàn)，ISODATA聚類算法相比K-means算法在靈活性上提高了很多，其“自組織”性也使得能夠更準(zhǔn)確地找到各類。但同時(shí)，該算法也存在著很大缺陷：ISODATA有很多需要選擇的參數(shù)，其中初始聚類數(shù)目難指定，而數(shù)據(jù)集中初始中心點(diǎn)選取的不同往往導(dǎo)致最后聚類效果的不同。文獻(xiàn)[12]基于密度思想，通過設(shè)定Eps 鄰域及Eps鄰域內(nèi)至少包含的對象數(shù)minpts排除孤立點(diǎn)，并將不重復(fù)的核心點(diǎn)作為初始聚類中心用于改進(jìn)K-means的初始聚類中心，此方法對ISODATA算法同樣有改進(jìn)效果。文獻(xiàn)[13]通過對DBSCAN的初始點(diǎn)進(jìn)行優(yōu)化以改進(jìn)算法。該優(yōu)化算法先確定全局密度最大點(diǎn)，結(jié)合該點(diǎn)和數(shù)據(jù)集自身特征，自適應(yīng)得到DBSCAN算法所聚類出的當(dāng)前簇所需參數(shù)。優(yōu)先對高密度簇聚類，即能對變化密度的數(shù)據(jù)集進(jìn)行聚類。文獻(xiàn)[14]提出黃金分割法度量用ISODATA算法聚類的有效性。該方法可動態(tài)計(jì)算聚類度量參數(shù)，能夠反映聚類數(shù)據(jù)的內(nèi)在結(jié)構(gòu)?？傮w而言，以上算法主要通過優(yōu)化初始點(diǎn)，增加評判標(biāo)準(zhǔn)判斷類內(nèi)、類間參數(shù)改進(jìn)算法，但這些算法依舊存在不足，如不能解決噪聲問題等。

2 密度最大中心點(diǎn)ISODATA聚類算法

2.1 設(shè)計(jì)思想

ISODATA雖然對原有K-means算法有所改進(jìn)，但該聚類算法在合并、分裂過程中沒有考慮到噪聲點(diǎn)（異常點(diǎn)），而噪聲點(diǎn)對數(shù)據(jù)集聚類影響較大。由于ISODATA所選的中心點(diǎn)具有隨機(jī)性，最后的聚類結(jié)果受初始中心點(diǎn)的選取影響很大。ISODATA聚類算法有很好的自適應(yīng)性，本文提出的改進(jìn)算法是通過高局部密度點(diǎn)距離[15]和局部密度最大原則選取初始中心點(diǎn)得到初始聚類簇，再結(jié)合ISODATA的良好自適應(yīng)性完成進(jìn)一步聚類。此方法能解決ISODATA受初始點(diǎn)選取影響，每次選取中心點(diǎn)不同所帶來的隨機(jī)性而造成最終結(jié)果不同的問題。同時(shí)由于引入高局部密度點(diǎn)距離，該算法能夠在劃分初始聚類簇時(shí)去除數(shù)據(jù)集中的異常點(diǎn)（噪聲點(diǎn)）。

2.2 D-ISODATA算法

D-ISODATA（密度最大中心點(diǎn)ISODATA聚類算法）通過引入局部密度和高局部密度點(diǎn)距離這兩個(gè)概念優(yōu)化ISODATA存在的問題。

3 實(shí)驗(yàn)分析

通過實(shí)驗(yàn)對D-ISODATA算法進(jìn)行評估，分別采用人工數(shù)據(jù)集、IRIS數(shù)據(jù)集進(jìn)行測試。通過與ISODATA算法、K-means算法比較，檢測其對初始點(diǎn)選取的優(yōu)化能力和去噪聲能力，提高聚類準(zhǔn)確性。對于兩個(gè)數(shù)據(jù)集都采用歐幾里德距離（Euclidian Distance）。

D-ISODATA算法對于數(shù)據(jù)集的處理是先計(jì)算高局部密度點(diǎn)距離δi及局部密度ρi確定密度最大點(diǎn)，即最優(yōu)初始聚類中心。其中，由于全局密度最大點(diǎn)的高局部密度點(diǎn)距離δi無窮大，因此給定一個(gè)較大值19.9作為其δi，再以該點(diǎn)為中心通過中心點(diǎn)密度曲線的波峰波谷得到數(shù)據(jù)集的初始聚類簇，實(shí)驗(yàn)結(jié)果如圖1、圖2所示。將得到的初始聚類簇通過ISODATA的分裂、合并迭代進(jìn)一步優(yōu)化聚類結(jié)果。

本文實(shí)驗(yàn)環(huán)境為Windows 7操作系統(tǒng)，實(shí)驗(yàn)平臺為Matlab 2014a。

（1）人工數(shù)據(jù)集檢測。分別以均值為0、5、10，方差為1的正態(tài)分布的300個(gè)隨機(jī)點(diǎn)作為待處理數(shù)據(jù)值，并在該數(shù)據(jù)值中加入加性高斯白噪聲如圖3所示，每個(gè)數(shù)據(jù)包含X與Y兩個(gè)坐標(biāo)值。分別采用K-means算法、ISODATA算法及D-ISODATA算法進(jìn)行實(shí)驗(yàn)對比。其中，K-means算法和ISODATA算法的初始類手工設(shè)定為3類。由于K-means算法和ISODATA算法的初始點(diǎn)選取具有隨機(jī)性，取100次實(shí)驗(yàn)求平均值。

D-ISODATA算法由于具有良好的去噪性且對初始聚類中心點(diǎn)有良好判斷，最終對數(shù)據(jù)集的處理效果準(zhǔn)確度及準(zhǔn)確率明顯好于ISODATA聚類算法和K-means聚類算法。實(shí)驗(yàn)結(jié)果如圖4所示。

由實(shí)驗(yàn)結(jié)果可以看出，由于ISODATA算法的初始中心點(diǎn)選擇不當(dāng)加上噪聲點(diǎn)的影響，聚類結(jié)果與預(yù)期偏差較大。而D-ISODATA聚類結(jié)果顯示，噪聲點(diǎn)明顯減少，聚類結(jié)果很好。表1給出了3種實(shí)驗(yàn)方法在發(fā)現(xiàn)簇?cái)?shù)量、準(zhǔn)確率上的對比，其中K-means算法和ISODATA算法以100次實(shí)驗(yàn)結(jié)果平均值作為對比結(jié)果。

由表1可知，在人工數(shù)據(jù)集中，3種方法的實(shí)驗(yàn)準(zhǔn)確率分別為87.22%、89.93%和96.41%，在發(fā)現(xiàn)簇的數(shù)量及準(zhǔn)確率上，D-ISODATA算法實(shí)驗(yàn)效果比ISODATA算法更優(yōu)。

（2）IRIS數(shù)據(jù)集檢測。IRIS數(shù)據(jù)集是由3種不同種類鳶尾花的各50個(gè)樣本組成，每個(gè)樣本共4種屬性，分別代表花萼長度、花萼寬度、花瓣長度和花瓣寬度，共有150個(gè)數(shù)據(jù)。該實(shí)驗(yàn)中，ISODATA算法仍采用100次實(shí)驗(yàn)求平均值，每次選取初始聚類點(diǎn)個(gè)數(shù)為3。實(shí)驗(yàn)結(jié)果如圖5所示。

IRIS數(shù)據(jù)集是4維數(shù)據(jù)，本實(shí)驗(yàn)圖像采用該數(shù)據(jù)集的前3維數(shù)據(jù)進(jìn)行畫圖比較，從圖像中發(fā)現(xiàn)，D-ISODATA相對于ISODATA在實(shí)驗(yàn)準(zhǔn)確率上優(yōu)化效果不明顯。

由表2可知，在IRIS數(shù)據(jù)集中，ISODATA算法比D-ISODATA算法的準(zhǔn)確率略低，在發(fā)現(xiàn)簇的數(shù)量上都很準(zhǔn)確，但由于隨機(jī)取中心點(diǎn)的不穩(wěn)定性，在測試ISODATA算法時(shí)有幾次實(shí)驗(yàn)的結(jié)果與真實(shí)情況嚴(yán)重不符，導(dǎo)致準(zhǔn)確率大為降低。而D-ISODATA算法由于其良好的穩(wěn)定性在相同數(shù)據(jù)集下的多次實(shí)驗(yàn)結(jié)果都相同。

4 結(jié)語

為了解決ISODATA聚類算法不能處理噪聲點(diǎn)，且在初始點(diǎn)的選擇上具有較大隨機(jī)性，并帶來實(shí)驗(yàn)結(jié)果的不確定性和巨大差異性問題，本文提出了基于局部密度最大中心點(diǎn)選取的改進(jìn)型ISODATA聚類算法。由于這種改進(jìn)型算法引用了高局部密度點(diǎn)距離和局部密度原則，在初始點(diǎn)選取和噪聲處理過程中有著非常好的實(shí)驗(yàn)結(jié)果，解決了ISODATA算法由于中心點(diǎn)選取帶來的實(shí)驗(yàn)結(jié)果不穩(wěn)定性問題。相比于ISODATA算法，改進(jìn)型ISODATA聚類算法具有實(shí)驗(yàn)準(zhǔn)確率高、發(fā)現(xiàn)簇的數(shù)量更加準(zhǔn)確等優(yōu)點(diǎn)。但同時(shí)，其在IRIS數(shù)據(jù)集中改進(jìn)算法的準(zhǔn)確率比ISODATA算法的平均準(zhǔn)確率提升不夠明顯，說明在處理高維數(shù)據(jù)時(shí)的實(shí)驗(yàn)效果還有待提高。后續(xù)研究中，需重點(diǎn)解決高維數(shù)據(jù)處理問題，如加入SVM的核函數(shù)，將數(shù)據(jù)投影到高維再進(jìn)行分類等。

參考文獻(xiàn)：

[1] 王光宏，蔣平.數(shù)據(jù)挖掘綜述[J].同濟(jì)大學(xué)學(xué)報(bào)：自然科學(xué)版，2004，32（2）：246-252.

[2] 董琦璠.基于劃分聚類算法的研究及其應(yīng)用[D].哈爾濱：哈爾濱工程大學(xué)，2015.

[3] 陳黎飛，姜青山，王聲瑞.基于層次劃分的最佳聚類數(shù)確定方法[J].軟件學(xué)報(bào)，2008，19（1）：62-72.

[4] 張業(yè)嘉誠.劃分聚類與基于密度聚類算法的改進(jìn)方法研究[D].大連：大連理工大學(xué)，2007.

[5] 趙慧，劉希玉，崔海青.網(wǎng)格聚類算法[J].計(jì)算機(jī)技術(shù)與發(fā)展，2010，20（9）：83-85.

[6] 賀玲，吳玲達(dá)，蔡益朝.數(shù)據(jù)挖掘中的聚類算法綜述[J].計(jì)算機(jī)應(yīng)用研究，2007，24（1）：10-13.

[7] 朱紅燦，陳星星.一種消除變量間相關(guān)性的模型聚類方法[J].統(tǒng)計(jì)與決策，2016（21）：26-28.

[8] MACQUEEN J.Some methods for classification and analysis of multivariateobservations[C].Proc. of Berkeley Symposium on Mathematical Statistics and Probability，1967：281-297.

[9] BI F M，WANG W K，CHEN L.DBSCAN：density-based spatial clustering of applications with noise[J].Journal of Nanjing University，2012，48（4）：491-498.

[10] SARWAR B，KARYPIS G，KONSTAN J，et al.Item-based collaborative filtering recommendation algorithms[C].International Conference on World Wide Web. ACM，2001：285-295.

[11] VELASCO F R D.Thresholding using the ISODATA clustering algorithm[J].IEEE Transactions on Systems Man & Cybernetics，2007，10（11）：771-774.

[12] 張琳，陳燕，汲業(yè)，等.一種基于密度的K-means算法研究[J].計(jì)算機(jī)應(yīng)用研究，2011（11）：4071-4073.

[13] 戴陽陽，李朝鋒，徐華.初始點(diǎn)優(yōu)化與參數(shù)自適應(yīng)的密度聚類算法[J].計(jì)算機(jī)工程，2016，42（1）：203-209.

[14] 張麗娜，姜新華，那日蘇.基于改進(jìn)的ISODATA算法的大樣本數(shù)據(jù)聚類方法研究[J].內(nèi)蒙古農(nóng)業(yè)大學(xué)學(xué)報(bào)：自然科學(xué)版，2013，34（1）：133-137.

[15] RODRIGUZE A，LAIO A.Clustering by fast search and find of density peaks[J].Science，2014，344（6191）：1492-1498.

[16] 王晶，夏魯寧，荊繼武.一種基于密度最大值的聚類算法[J].中國科學(xué)院大學(xué)學(xué)報(bào)，2009，26（4）：539-548.

（責(zé)任編輯：孫 娟）