聚類分析中的若干問題研究及應(yīng)用.pdf

1、聚類分析是知識發(fā)現(xiàn)、機(jī)器學(xué)習(xí)和數(shù)據(jù)挖掘等領(lǐng)域的一個(gè)非常重要的基本工具。與傳統(tǒng)的分類方法不同，聚類是在沒有任何先驗(yàn)知識的前提下，僅根據(jù)數(shù)據(jù)間的相似性將沒有標(biāo)號數(shù)據(jù)集劃分成不同的類(或簇)，使得同一個(gè)類中的元素盡可能相似，而不同類中的元素差別盡可能大，因此聚類分析又是一個(gè)非監(jiān)督學(xué)習(xí)過程。 模糊聚類和Gauss混合模型是目前應(yīng)用最為廣泛的兩種聚類分析方法，本文主要針對這兩類方法中存在的一些基本問題，做了以下幾個(gè)方面的研究工作：

2、 在第一章，我們對文獻(xiàn)中存在的主要聚類分析方法做了一個(gè)全面的綜述，主要分析了劃分聚類方法、層次聚類方法、基于密度的聚類方法、基于網(wǎng)格的聚類方法以及基于模型的聚類方法中的多種算法的優(yōu)缺點(diǎn)。 第二章主要就模糊聚類方法中的FCM和PCM及其優(yōu)缺點(diǎn)展開討論。 首先對FCM和PCM做了較為詳盡的綜述報(bào)告，并從理論和數(shù)值試驗(yàn)兩個(gè)角度分析了FCM和PCM算法的不足之處。 然后研究了由J S Zhang等人提出的將FCM和PCM

3、相結(jié)合的模糊聚類算法，數(shù)值試驗(yàn)表明，該算法能有效地發(fā)揮FCM和PCM的優(yōu)點(diǎn)，克服它們各自的缺點(diǎn)，其聚類效果比單一的FCM和PCM都更為理想。在第二章的最后部分，我們以數(shù)值試驗(yàn)說明了模糊球殼聚類算法FCSS不能對加有噪聲的同心球殼狀數(shù)據(jù)進(jìn)行有效聚類，并從理論上分析了產(chǎn)生這一現(xiàn)象的原因，那就是FCSS采用的基于梯度法和交替尋優(yōu)策略容易陷入局部極值點(diǎn)，從而影響聚類效果。 因此，我們提出用遺傳算法搜索FCSS目標(biāo)函數(shù)的最優(yōu)解，并且，為了

4、加速遺傳算法的收斂速度，我們還將原FCSS算法與遺傳算法進(jìn)行巧妙地結(jié)合起來，產(chǎn)生出所謂的基于遺傳算法與FCSS相結(jié)合的模糊球殼聚類算法GA-FCSS。 大量的數(shù)值試驗(yàn)表明，我們提出的GA-FCSS算法是有效的，它能將各種含有噪聲的球殼(包括同心球殼)狀數(shù)據(jù)進(jìn)行很好地分離，得到的球殼中心和半徑與真實(shí)值較為接近，對數(shù)據(jù)點(diǎn)的分類結(jié)果也幾乎完全正確。 第三章就基于統(tǒng)計(jì)模型的聚類算法展開討論，主要選擇了目前較為實(shí)用的Gauss混合

5、模型，它是一種半?yún)?shù)的聚類方法。 首先，我們將Gauss混合模型與聚類問題進(jìn)行了類比。 然后推導(dǎo)了求解Gauss混合模型相關(guān)參數(shù)的極大似然估計(jì)的EM算法，并以數(shù)值試驗(yàn)實(shí)例說明了EM算法對實(shí)心橢球狀數(shù)據(jù)進(jìn)行聚類是有效的。 最后，我們以Gauss混合模型為基礎(chǔ)，研究了聚類的有效性問題，即待聚類的數(shù)據(jù)中有多少個(gè)類別的問題，這在Gauss混合模型中表現(xiàn)為有多少個(gè)正態(tài)分支。我們主要研究了基于極小信息長度準(zhǔn)則的MML-EM算

6、法，該算法可以同時(shí)處理Gauss混合模型的模型選擇(估計(jì)類別數(shù))與參數(shù)估計(jì)兩個(gè)問題。 數(shù)值試驗(yàn)表明，當(dāng)以接近真實(shí)值的整數(shù)初始化聚類的類別數(shù)時(shí)，MML-EM算法能以較高的正確率選擇出最優(yōu)類別數(shù)，但對聚類原型的估計(jì)可能出現(xiàn)較大偏差；當(dāng)以遠(yuǎn)離真實(shí)值的整數(shù)初始化類別數(shù)時(shí)，MML-EM算法選擇最優(yōu)類別數(shù)的正確率迅速降低，并且有過高估計(jì)最優(yōu)類別數(shù)的趨勢。 針對這一情況，我們從理論上重新分析了MML準(zhǔn)則，找出了出現(xiàn)這樣結(jié)果的原因，并提