李潤青+謝明鴻+黃冰晶

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

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

DOIDOI：10.11907/rjdk.172074

中圖分類號：TP312

文獻標識碼：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)域，包括模式識別、機器學(xué)習(xí)、圖像處理、信息檢索等[1]，在數(shù)據(jù)挖掘中起到重要作用。

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

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

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

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

1 相關(guān)研究

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

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

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

2 密度最大中心點ISODATA聚類算法

2.1 設(shè)計思想

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

2.2 D-ISODATA算法

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

3 實驗分析

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

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

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

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

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

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

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

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

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

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

4 結(jié)語

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

參考文獻：

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

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

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

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

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

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

[7] 朱紅燦，陳星星.一種消除變量間相關(guān)性的模型聚類方法[J].統(tǒng)計與決策，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].計算機應(yīng)用研究，2011（11）：4071-4073.

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

[14] 張麗娜，姜新華，那日蘇.基于改進的ISODATA算法的大樣本數(shù)據(jù)聚類方法研究[J].內(nèi)蒙古農(nóng)業(yè)大學(xué)學(xué)報：自然科學(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é)報，2009，26（4）：539-548.

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