劉鋼　李宗辰

摘要：該文在通過對傳統(tǒng)K-means算法的深入研究后發(fā)現(xiàn)，數(shù)據(jù)集中存在著孤立點和算法的初始聚類中心選取是否合理都將會嚴(yán)重影響算法最終的聚類結(jié)果的質(zhì)量。于是，該文針對K-means算法以上兩點問題做出了優(yōu)化，給出了一種基于統(tǒng)計距離和極大極小值原則的改進K-means算法（KSDM）。KSDM算法首先采用一種基于統(tǒng)計距離的孤立點檢測算法對數(shù)據(jù)集中的數(shù)據(jù)進行檢測，然后再通過基于極大極小值原則的初始聚類中心選取算法來選取初次劃分的聚類中心對數(shù)據(jù)做聚類處理。經(jīng)過大量實驗分析、研究、驗證，KSDM算法在孤立點檢測方面效果明顯，同時在選取初始聚類中心的方面較元算法相比更加的合理。

關(guān)鍵詞：聚類；k-means算法；初始聚類中心；孤立點排除

1概述

隨著互聯(lián)網(wǎng)時代的飛速發(fā)展，數(shù)據(jù)的數(shù)量呈指數(shù)的爆增，在這些數(shù)據(jù)中存在著很多有價值的信息在等待著我們?nèi)グl(fā)掘，于是，數(shù)據(jù)挖掘技術(shù)成為了互聯(lián)網(wǎng)時代信息領(lǐng)域的重點研究方向之一。數(shù)據(jù)挖掘技術(shù)“大家庭”的重要組成成員——聚類分析也是當(dāng)前互聯(lián)網(wǎng)時代的研究熱點。聚類分析是將一個整體的數(shù)據(jù)集分解成若干個小的子集，而所得到的這些個子集的內(nèi)部的數(shù)據(jù)對象的相似程度相對較高，而不同子集之間的數(shù)據(jù)對象的它們的差異性相對較大，相似程度也相對較低。其中，基于劃分方法的K-means算法是在聚類領(lǐng)域中經(jīng)典的算法之一，因為該算法操作簡捷、運行時間較短以及收斂速度相對較快等多方面的優(yōu)勢，被大量學(xué)者應(yīng)用、優(yōu)化以及改進。但是，即使是經(jīng)典的K-means算法中也存在著一些需要優(yōu)化的不足之處；首先，需要進行聚類處理的數(shù)據(jù)集中存在著一些孤立點，孤立點就是那些在數(shù)據(jù)集中與其他數(shù)據(jù)對象相異度最高、相似度最低并且邊緣化的數(shù)據(jù)點，所以會因為孤立點的存在，導(dǎo)致在算法的運行過程以及最后的聚類結(jié)果的質(zhì)量都造成影響。其次，傳統(tǒng)的K-means算法的初次劃分的聚類中心是由算法隨機選擇出來的，由于隨機選擇的合理性不穩(wěn)定，所以很容易使算法陷入局部最優(yōu)；所以，初次劃分的聚類中心選擇是否合理也將決定著最后的聚類結(jié)果的質(zhì)量的好壞。另外，在隨著對傳統(tǒng)的K-means算法的深入研究發(fā)現(xiàn)，K-means算法在整個聚類的過程中，要對上一次聚類得到的簇求得均值，然后再以求得的均值為聚類中心重新聚類，需要連續(xù)不斷地重復(fù)這一過程直到準(zhǔn)則函數(shù)收斂給出聚類結(jié)果；因此，當(dāng)初始聚類中心選取的不合理時，會使算法增加的迭代次數(shù)，延長算法的運行時間。

目前，很多研究者對K-means算法進行了改進。文獻(xiàn)中的作者提出了一種基于最大最小距離法的初始聚類中心選取方法，該算法夠能計算出k值并且能夠在數(shù)據(jù)集中找到k個相對比較合理的初次劃分的聚類中心，但是該算法容易將數(shù)據(jù)集內(nèi)的邊緣數(shù)據(jù)對象選定成為初次劃分的聚類中心，并且需要較大時間消耗。段桂芹采用了一種基于均值與最大距離的乘積的方法選取初始聚類中心，該算法首先選擇與距離數(shù)據(jù)集均值最遠(yuǎn)的那個數(shù)據(jù)對象作為聚類中心，并納入聚類中心的集合，然后依次將與數(shù)據(jù)集均值和當(dāng)前聚類中心的乘積最大的數(shù)據(jù)對象納入聚類中心的集合，從而提高了準(zhǔn)確率。

針對上文所闡述的諸多K-means算法的缺陷，本文給出了基于K-means算法的改進算法KSDM。在KSMD算法中給出了一種基于統(tǒng)計距離的孤立點檢測算法和一種基于極大極小值原則的初始聚類中心選取算法。實驗結(jié)果表明，KSDM算法不僅能夠有效的檢測和排除孤立點，還能夠選取到較為合理的初始聚類中心，從而使算法的迭代次數(shù)減少，得到較佳的聚類結(jié)果。

2基于K-means算法改進

經(jīng)過對傳統(tǒng)的K-means算法深入研究發(fā)現(xiàn)，該算法的初次劃分的聚類中心是由算法隨機選定出來的，由于數(shù)據(jù)集中存在著一些與其他數(shù)據(jù)對象相似度很低。相異度很高，并且嚴(yán)重偏離數(shù)據(jù)集中心區(qū)域的一些數(shù)據(jù)對象，這里稱之為孤立點；這些孤立點的存在會使得K-means算法在選擇初次劃分的聚類中心時不穩(wěn)定、不合理，從而會使得聚類過程中迭代次數(shù)曾多、運行時間延長、聚類結(jié)果質(zhì)量下降等影響；所以在算法運行之前，將數(shù)據(jù)集中的孤立點檢測出來并刪除以及如何選取出更為合理的初始聚類中心是很有必要的。

于是，針對上述的2個問題作者給出了基于K-means算法的改進KSDM算法，KSDM算法很好地優(yōu)化了K-means算法的缺陷。

2.1算法1：基于統(tǒng)計距離的孤立點排除算法

所謂孤立點，是因為數(shù)據(jù)集中存在著一些與其他數(shù)據(jù)對象相似度很低、相異度很高，并且嚴(yán)重偏離數(shù)據(jù)集中心區(qū)域的一些數(shù)據(jù)對象，所以這種數(shù)據(jù)對象不屬于任何一類的孤立數(shù)據(jù)對象，也稱謂孤立點。由于K-means算法是隨機選擇初次劃分的聚類中心時的，所以有這些孤立點的存在會使得算法在選取初次劃分的聚類中心時存在著不穩(wěn)定性、不合理性，因此，算法最終的聚類效果會因為孤立點的存在而延長運行時間、增加迭代次數(shù)以及聚類結(jié)果質(zhì)量較低等隱患。所以，在運行聚類算法之前，將數(shù)據(jù)集中所存在的孤立點檢測出來并刪除是必要的。