基于改進的近鄰傳播聚類算法的Gap統計研究

唐 丹,張正軍,王俐莉

(1.南京理工大學 理學院 統計與金融數學系,江蘇 南京 210094;2.海軍指揮學院科研部,江蘇 南京 210016)

基于改進的近鄰傳播聚類算法的Gap統計研究

唐 丹1,張正軍1,王俐莉2

(1.南京理工大學 理學院 統計與金融數學系,江蘇 南京 210094;2.海軍指揮學院科研部,江蘇 南京 210016)

由于K-means算法初始聚類中心的選取具有隨機性，聚類結果可能不穩定，導致Gap統計估計的聚類數也可能不穩定。針對這些不足，提出一種改進的近鄰傳播算法-mAP。該算法考察數據的全局分布特性，不同的點賦予不同的P值。在Gap統計中用mAP算法代替K-means算法,提出基于mAP的Gap統計mAPGap。mAP能在較短的時間內得到較好的聚類效果，而且不需要預先設定初始聚類中心，聚類結果更穩定。實驗結果表明,mAPGap在估計聚類數的穩定性和聚類精度上都優于原Gap。

聚類分析;近鄰傳播聚類;偏向參數;K-means算法;Gap統計

0 引 言

數據集的聚類數估計是數據分析中的一項重要課題。2000年，R.Tibshirani等提出確定最佳聚類數的Gap統計量[1]，采用的聚類算法是K-means算法，該算法需要選取初始聚類中心，通常隨機選取K個樣本點作為初始聚類中心。2013年，劉倩基于Gap統計方法研究了K-means算法，提出了一種基于數據分布規律具有自適應特點的DSA-K-means算法[2]。2013年，陸琴琴針對基于矩Gap統計的圖像分割算法中K-means算法存在的缺陷，提出了MMGSK算法[3]。

2007年，Frey[4]和MezardM[5]提出了屬于劃分聚類方法的近鄰傳播(AffinityPropagation,AP)算法。該算法具有如下優點：能在較短時間內得到較好的聚類效果[6]；算法中類代表點是原始數據中的點，而不是數據的均值點；……