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

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

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

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