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

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

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

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

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

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

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

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