一種改進(jìn)的聚類算法

一種改進(jìn)的聚類算法

隨著數(shù)據(jù)處理研究領(lǐng)域技術(shù)的發(fā)展，分組算法作為本文創(chuàng)業(yè)的主要方法之一越來越受到重視。在眾多的聚類算法中,k均值聚類算法的應(yīng)用領(lǐng)域非常廣泛,包括圖像及語音數(shù)據(jù)壓縮,使用徑向基函數(shù)網(wǎng)絡(luò)進(jìn)行系統(tǒng)建模的數(shù)據(jù)預(yù)處理,以及異構(gòu)神經(jīng)網(wǎng)絡(luò)結(jié)構(gòu)中的任務(wù)分解,因此研究k均值算法的優(yōu)化是很有必要的。原k均值算法對孤立點(diǎn)很敏感,少量的這些孤立點(diǎn)會對聚類結(jié)果產(chǎn)生較大的影響,本文從減小孤立點(diǎn)對聚類結(jié)果的影響這一點(diǎn)出發(fā)對其加以改進(jìn)。1原始k-mean算法1.1聚類算法聚類最常用的基于劃分的聚類算法是k-means算法,該算法不斷計(jì)算每個聚類Si的中心,也就是聚類Si中對象的平均值,作為新的聚類種子。k-means聚類算法的步驟為:1)隨機(jī)選取k個不同的數(shù)據(jù)對象作為k個類的代表;2)將數(shù)據(jù)對象分配給距離最近的某個類代表所屬的類,形成k個類,計(jì)算聚類準(zhǔn)則函數(shù);3)計(jì)算各個類的重心,將這些重心作為各個類的代表,若這些代表與劃分前的代表相同或兩輪聚類準(zhǔn)則函數(shù)的值之差小于一定的數(shù)則終止,否則轉(zhuǎn)2)。1.2k-meas算法原k-means算法僅能處理數(shù)字屬性;需要預(yù)先設(shè)定初始中心,還需要預(yù)先知道類的數(shù)目,只能得到次優(yōu)解。當(dāng)結(jié)果簇密集并且各簇之間的區(qū)別明顯時,采用k-means算法的效果較好。k-means算法對于數(shù)據(jù)集中孤立點(diǎn)很敏感,少量的這類數(shù)據(jù)將對聚類結(jié)果產(chǎn)生較大的影響。為此,提出了一種改進(jìn)的k均值算法,改進(jìn)后的k均值算法能很好地處理數(shù)據(jù)中存在孤立點(diǎn)的問題。2聚類分離的計(jì)算方法用k均值算法進(jìn)行數(shù)據(jù)聚類時,可以看出結(jié)果的穩(wěn)定性還存在很大的問題,有時聚類的效果非常好(當(dāng)數(shù)據(jù)分布呈凸形或球形的時候聚類的效果會非常好),而有時聚類結(jié)果會出現(xiàn)明顯的偏差和錯誤,這種偏差和錯誤產(chǎn)生的原因在于數(shù)據(jù)的分散性。聚類的數(shù)據(jù)不可避免地會出現(xiàn)孤立點(diǎn),即少量數(shù)據(jù)遠(yuǎn)離高密度的數(shù)據(jù)密集區(qū)的情況,但我們在進(jìn)行k均值聚類計(jì)算時,是將聚類均值點(diǎn)(類中所有數(shù)據(jù)的幾何中心點(diǎn))作為新的聚類種子進(jìn)行新一輪聚類計(jì)算,在這種情況下,新的聚類種子可能偏離真正的數(shù)據(jù)密集區(qū),從而導(dǎo)致聚類結(jié)果出現(xiàn)偏差。由此可以看出,k均值算法處理孤立點(diǎn)數(shù)據(jù)時有很大的局限性。采用聚類均值點(diǎn)與聚類種子相分離的思想,在改進(jìn)算法中,對原算法中的步驟3按如下方式計(jì)算,當(dāng)進(jìn)行第k輪聚類種子的計(jì)算時,采用簇中那些與第k-l輪聚類種子相似度較大的數(shù)據(jù),計(jì)算它們的均值點(diǎn)作為第k輪聚類的種子,相當(dāng)于把孤立點(diǎn)排除在外,孤立點(diǎn)不參加聚類中心的計(jì)算,這樣聚類中心就不會因?yàn)楣铝Ⅻc(diǎn)的原因而明顯偏離數(shù)據(jù)集中的地方,而導(dǎo)致了聚類結(jié)果出現(xiàn)不應(yīng)有的問題。這種聚類均值點(diǎn)和聚類種子相分離的思想,最主要的就是做到在計(jì)算新一輪的聚類中心的時候,盡量不把對聚類結(jié)果有影響的孤立點(diǎn)計(jì)算在內(nèi)。因此在計(jì)算聚類中心的時候,要用一定的算法把孤立點(diǎn)排除在用來計(jì)算均值點(diǎn)的那些數(shù)據(jù)之外?？梢杂玫挠?jì)算方法有很多,對聚類過程和結(jié)果的影響是不同的,改進(jìn)算法采用以下兩種計(jì)算方法。第一種計(jì)算步驟如下:1)對于第k-1輪聚類獲得的類,計(jì)算類中數(shù)據(jù)與該類聚類種子相似度最小的相似度simmin和數(shù)據(jù)中與該類聚類種子相似度最大的相似度simmax;2)選擇類中與聚類種子相似度大于(simmax+simmin)/2的數(shù)據(jù)組成每個類的一個子集;3)計(jì)算子集中數(shù)據(jù)的均值點(diǎn),作為第k輪聚類的聚類種子。這樣每一輪參加聚類種子計(jì)算的數(shù)據(jù)都是與前一輪的聚類種子相似度大的數(shù)據(jù),如果存在孤立點(diǎn),就會因?yàn)楣铝Ⅻc(diǎn)不參與聚類種子的計(jì)算而有效地避免其對聚類結(jié)果的影響。采用(simmax+simmin)/2計(jì)算,當(dāng)類中有明顯的孤立點(diǎn)時,即simmax和simmin差別較大時較好,但是如果某個類中的數(shù)據(jù)都比較密集,沒有明顯的孤立點(diǎn)時,即simmax和simmin的差別并不大時,在每一次計(jì)算聚類中心時采用這個式子就會排除很多不是孤立點(diǎn)的數(shù)據(jù),聚類中心在從初始值到最終值的移近過程中就會移近很慢,因此聚類的迭代次數(shù)會增加。為解決此問題,在數(shù)據(jù)本身就較集中時讓更多的數(shù)據(jù)參與到聚類中心的計(jì)算中去,由此采用第二種計(jì)算方法。第二種計(jì)算方法步驟如下:1)對于第k-1輪聚類獲得的類,計(jì)算該類中所有數(shù)據(jù)與該類聚類中心的平均距離S2;2)選擇類中與聚類種子相似度大于2×S2的數(shù)據(jù)組成每個類的一個子集;3)計(jì)算子集中數(shù)據(jù)的均值點(diǎn),作為第k輪聚類的聚類種子。采用這種計(jì)算方法,當(dāng)類中有明顯的孤立點(diǎn)的時候,平均距離S2會比較大,但它與類中相似度最小的相似度值相比還有很大差距,這樣2倍的平均距離就基本能包括大多數(shù)的數(shù)據(jù),從而排除孤立點(diǎn)。而當(dāng)類中數(shù)據(jù)較集中,沒有明顯的孤立點(diǎn)時,平均距離S2和類中相似度最小的相似度值之差會比較小,這樣2倍的平均距離能包括幾乎所有的數(shù)據(jù),就在一定程度上解決了采用第一種計(jì)算方法帶來的由于排除點(diǎn)過多而導(dǎo)致的迭代次數(shù)增加等問題,也能獲得很好的聚類結(jié)果。3tp數(shù)據(jù)的聚類分析實(shí)驗(yàn)采用的數(shù)據(jù)是二維的數(shù)值數(shù)據(jù),總共150個數(shù)據(jù),數(shù)據(jù)分為兩類,第一類沒有明顯的孤立點(diǎn),數(shù)據(jù)較為集中,第二類相對來說較分散,而且有明顯的孤立點(diǎn)。3.1關(guān)于聚類數(shù)據(jù)的聚類聚類進(jìn)行了四次迭代,分類結(jié)果因?yàn)楣铝Ⅻc(diǎn)的影響有明顯的錯誤,本該在第二類中的〈4.5,4.5〉,〈4.0,5.0〉,〈4.3,4.7〉和〈4.4,4.8〉這4個數(shù)據(jù)被分到了第一類中,這是因?yàn)槭艿降诙愔械?個明顯的孤立點(diǎn)的影響,使第二類的中心點(diǎn)最后明顯偏離了數(shù)據(jù)集中的區(qū)域,從而導(dǎo)致了聚類結(jié)果出現(xiàn)明顯的錯誤,出錯的那4個點(diǎn)離第一類的中心較近,而離第二類的中心較遠(yuǎn)了。3.2算法的增加和迭代次數(shù)改進(jìn)后的程序糾正了源程序所犯的錯誤,〈4.5,4.5〉,〈4.0,5.0〉,〈4.3,4.7〉和〈4.4,4.8〉這4個數(shù)據(jù)分到了正確的類中,但是聚類過程的迭代次數(shù)卻達(dá)到了7次,比原算法增加了3次。這是因?yàn)椴捎?simmax+simmin)/2這個式子排除孤立點(diǎn)是比較粗糙的,當(dāng)類中有明顯的孤立點(diǎn)時,如第二類,很好地排除了6個孤立點(diǎn),而其他數(shù)據(jù)都參與到了聚類中心的計(jì)算中,但是當(dāng)類中數(shù)據(jù)較集中,沒有明顯的孤立點(diǎn)時,在計(jì)算聚類中心時,很多數(shù)據(jù)都被排除在外了,這就導(dǎo)致了雖然分類的結(jié)果在第三次迭代后就沒改變,但是聚類中心還在不斷地改變,迭代還要不斷進(jìn)行下去,因此就增加了聚類過程的迭代次數(shù)。不過聚類中心已經(jīng)明顯地移向了數(shù)據(jù)集中的區(qū)域。聚類的質(zhì)量和效率都是很重要的,分析第一種改進(jìn)算法所帶來的問題,進(jìn)一步改進(jìn)算法。3.3聚類中心的計(jì)算方法采用2×S2這個式子,獲得了完全正確的聚類結(jié)果,并且迭代次數(shù)不但沒有增加,而且較原算法還減少了一次。這是因?yàn)楫?dāng)類中有孤立點(diǎn)時,類中數(shù)據(jù)與聚類中心距離的最大值和類中數(shù)據(jù)與聚類中心距離的平均值相差較大,所以用在2倍平均值范圍內(nèi)的數(shù)據(jù)來計(jì)算新一輪的聚類中心時,它能包括大多數(shù)的數(shù)據(jù)并排除掉孤立點(diǎn),讓聚類中心不受孤立點(diǎn)的影響。而當(dāng)類中數(shù)據(jù)較集中,沒有明顯的孤立點(diǎn)時,類中數(shù)據(jù)與聚類中心距離的最大值和類中數(shù)據(jù)與聚類中心距離的平均值相差會較小,所以2倍平均值范圍內(nèi)的數(shù)據(jù)幾乎就包括了該類中所有的數(shù)據(jù)。這樣就比較好地解決了原k均值算法和采用第一種計(jì)算方法進(jìn)行改進(jìn)的k均值算法所產(chǎn)生的問題。實(shí)驗(yàn)結(jié)果表明,改進(jìn)后的k均值算法獲得了好的聚類結(jié)果,