聚類學(xué)習(xí)的理論分析與高效算法研究.pdf

1、聚類學(xué)習(xí)是機器學(xué)習(xí)的一個重要研究內(nèi)容，被廣泛應(yīng)用于金融欺詐、醫(yī)療診斷、圖像處理、信息檢索和生物信息學(xué)等領(lǐng)域.目前，不同類型的聚類模型和算法已被廣泛地提出和發(fā)展.然而，隨著信息技術(shù)和采樣技術(shù)不斷地發(fā)展，需要處理的數(shù)據(jù)不斷呈現(xiàn)出屬性類型的多樣性、高維性、規(guī)模的海量性、分布的不均勻性、時空特征的動態(tài)性等復(fù)雜結(jié)構(gòu).由于聚類分析是數(shù)據(jù)驅(qū)動的，不同的數(shù)據(jù)特征往往導(dǎo)致不同的聚類模型及算法，沒有適合于所有特征的聚類學(xué)習(xí)方法.因此，當復(fù)雜數(shù)據(jù)成為現(xiàn)代社會

2、中數(shù)據(jù)資源的主體時，如何從它們中發(fā)現(xiàn)隱藏的類結(jié)構(gòu)已成為聚類學(xué)習(xí)的一個重要研究內(nèi)容，并引起了廣泛地關(guān)注.
　　本文將以復(fù)雜數(shù)據(jù)為研究對象，構(gòu)建符合其相應(yīng)特征的聚類模型，并對相關(guān)理論與高效算法進行了深入的研究.本文的主要研究成果有:
　　(1)提出了一種面向高維分類數(shù)據(jù)的屬性雙加權(quán)優(yōu)化聚類算法.在該算法中，一種新的屬性加權(quán)模式被提出，并將其應(yīng)用于聚類過程中形成新的聚類優(yōu)化問題.嚴格地獲得了該算法的劃分矩陣、類中心集和屬性權(quán)值在迭

3、代過程中的更新規(guī)則，從而保證了算法能夠在有限次迭代中獲得局部最優(yōu)解.證明了該算法的收斂性.實驗結(jié)果表明新提出的算法既繼承了Chan等人提出的屬性加權(quán)算法的簡單性，又有效地克服了它們在面對高維分類數(shù)據(jù)時的加權(quán)失效問題.
　　(2)提出了一種針對快速全局K-Means聚類算法(FGKM)的加速機制.在該機制中，利用數(shù)據(jù)點的局部幾何信息在保證FGKM聚類結(jié)果的同時減少其大量不必要的距離計算，從而使得FGKM聚類算法能夠有效地處理大規(guī)模數(shù)

4、據(jù).分析了基于提出的加速機制的FGKM算法的空間和時間復(fù)雜度.實驗結(jié)果表明加速后的FGKM算法相比原始的FGKM和其它改進的FGKM算法需要更少的聚類時間和距離計算次數(shù).值得注意的是，新算法的有效性隨著數(shù)據(jù)的維數(shù)和聚類數(shù)目的增加而變得更加明顯.
　　(3)揭示了非平衡數(shù)據(jù)對模糊K-Means聚類算法的表現(xiàn)影響以及聚類結(jié)果的“均勻效應(yīng)”產(chǎn)生的原因.理論分析表明了模糊K-Means聚類算法相比K-Means聚類算法在聚類非平衡數(shù)據(jù)時更

5、傾向于產(chǎn)生“均勻效應(yīng)”，并且隨著模糊因子α值的增加而變得嚴重.為了避免聚類結(jié)果受到“均勻效應(yīng)”的影響，提出了一種基于多類中心的模糊K-Means聚類算法.在該算法中，首先應(yīng)用了全局模糊K-Means聚類算法產(chǎn)生可信賴的類中心.進一步，基于模糊因子α和所產(chǎn)生的類中心之間的最大最小距離，提供了一種確定聚類數(shù)目的方法.最后，將提出的一個分離測度應(yīng)用于組織多類中心去代表每個類.實驗結(jié)果表明該多類中心聚類算法能夠有效地聚類非平衡數(shù)據(jù).
　　

6、(4)提出了一種新的面向動態(tài)分類數(shù)據(jù)流的聚類框架.在該框架中，首先提出了一種新的融合類內(nèi)和類間信息的類特征描述方式以及基于它的數(shù)據(jù)類別標記方法.該方法弱化了滑動窗口中的類尺度對標記結(jié)果的影響.接著，定義了一個有效性函數(shù)，并將其應(yīng)用于去評測新窗口中對象標記結(jié)果的有效性.基于該函數(shù)，概念漂移檢測問題被轉(zhuǎn)化為一個凸規(guī)劃問題.利用該問題的最優(yōu)解來幫助人們?nèi)グl(fā)現(xiàn)漂移的概念，從而使得檢測結(jié)果能夠獨立于數(shù)據(jù)類別標記結(jié)果.實驗結(jié)果表明新的聚類框架相比其

7、它框架不僅能夠有效地標記新窗口的對象而且能準確地發(fā)現(xiàn)漂移的概念.
　　(5)提出了一個泛化的聚類有效性函數(shù)，并在此基礎(chǔ)上，分析了K-Modes目標函數(shù)、分類效用函數(shù)和信息熵函數(shù)之間的關(guān)系.分析結(jié)果表明分類效用函數(shù)在評測聚類結(jié)果的有效性上等效于信息熵函數(shù)，且優(yōu)于K-Modes目標函數(shù).由于泛化的有效性函數(shù)僅僅基于類內(nèi)信息，因此，進一步回答了僅用類內(nèi)信息也能夠有效地評測聚類結(jié)果的問題.最后分析了聚類有效性函數(shù)的歸一化在評測同一算法在不