聚類學習的理論分析與高效算法研究.pdf

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

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

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

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

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

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

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