K均值算法初始聚類中心選取相關(guān)問題研究.pdf

1、聚類分析是數(shù)據(jù)挖掘的功能之一,是在訓(xùn)練數(shù)據(jù)不提供類標(biāo)號的情況下按照最大化類內(nèi)對象間的相似性、最小化不同類對象之間的相似性的原則聚類和分組數(shù)據(jù)。目前,存在著大量的聚類算法,K均值算法是應(yīng)用廣泛的聚類算法之一。
　　 K均值算法的優(yōu)點是:算法思想簡單:時間復(fù)雜度接近線性:對大規(guī)模數(shù)據(jù)的挖掘具有可伸縮性,但是該算法存在如下缺點:對聚類初始值的依賴:聚類個數(shù)K需要預(yù)先給定:準(zhǔn)則函數(shù)易陷入局部極小:對離群點敏感等等。
　　 本文重

2、點針對K均值算法對初始聚類中心的依賴性,提出了基于密度選取K個初始聚類中心的算法。其主要思想是:在一個數(shù)據(jù)集合里,高密度區(qū)域的數(shù)據(jù)對象被低密度區(qū)域的對象所分割,處于低密度區(qū)域的數(shù)據(jù)對象通常被認(rèn)為是噪聲點。首先根據(jù)兩個參數(shù)(鄰域半徑e、高密度點在鄰域半徑內(nèi)至少包含數(shù)據(jù)對象的數(shù)目MinPts),劃分高低密度點,然后取高密度點集合G中相距最遠(yuǎn)的K個點作為初始聚類中心。通過在不同數(shù)據(jù)集(來自UCI數(shù)據(jù)庫)上對兩個算法的多次對比實驗,驗證了基于密

3、度選取K個初始聚類中心的K均值算法比傳統(tǒng)的K均值算法聚類結(jié)果準(zhǔn)確率更高,更穩(wěn)定。
　　 研究進(jìn)一步給出了基于距離矩陣D確定ε和MinPts參數(shù)值的方法。主要思想是:通過距離矩陣計算每個對象距離的中間值(median),然后取這些中間值的平均值作為ε的值。計算每個對象鄰域半徑ε內(nèi)對象的個數(shù),將這些個數(shù)相加,再除以2*n,獲得參數(shù)MinPts的值,其中n是數(shù)據(jù)集對象的個數(shù)。通過檢驗聚類結(jié)果是否理想或者以文獻(xiàn)已給定的經(jīng)驗值作正確性判斷