【摘要】 聚類屬于無監(jiān)督學(xué)習(xí)，是將數(shù)據(jù)集中的數(shù)據(jù)對(duì)象分成多個(gè)簇或者類，使得在同一個(gè)簇中對(duì)象相似度高，而在不同簇中對(duì)象的相似度低，因此，對(duì)空間數(shù)據(jù)對(duì)象的聚類可通過基于聚類目標(biāo)函數(shù)的優(yōu)化問題來解決。從這一思路出發(fā)，將自適應(yīng)能力及魯棒性較高的計(jì)算智能技術(shù)應(yīng)用于聚類分析，產(chǎn)生了很多基于計(jì)算智能技術(shù)的聚類分析模型�；谟�(jì)算智能的聚類分析成功解決了數(shù)據(jù)的聚類問題，對(duì)處理目標(biāo)的特性有良好的適應(yīng)能力，彌補(bǔ)了傳統(tǒng)聚類方法的不足，取得了良好的效果。計(jì)算智能方法主要包括神經(jīng)網(wǎng)絡(luò)、模糊控制、進(jìn)化計(jì)算、混沌科學(xué)、免疫計(jì)算、DNA計(jì)算及群體智能等。近年來，神經(jīng)網(wǎng)絡(luò)、模糊邏輯和進(jìn)化計(jì)算三個(gè)方向的研究成為熱點(diǎn)。自組織映射（SOM）是最有代表性的神經(jīng)網(wǎng)絡(luò)聚類方法；遺傳算法、進(jìn)化策略、免疫規(guī)劃、克隆學(xué)說、蟻群系統(tǒng)、微粒群優(yōu)化、文化算法等進(jìn)化計(jì)算已成功應(yīng)用到聚類分析中；另外，在傳統(tǒng)聚類分析中引入模糊集概念，產(chǎn)生了模糊聚類算法；根據(jù)計(jì)算智能技術(shù)的優(yōu)缺點(diǎn)，將一些計(jì)算智能方法融合起來應(yīng)用于聚類分析，提高了聚類的能力。論文將神經(jīng)網(wǎng)絡(luò)、遺傳算法等計(jì)算智能技術(shù)用于聚類分析，構(gòu)造聚類分析模型，研究該模型的定義及優(yōu)化方法的特點(diǎn)和不足，改進(jìn)或提出相應(yīng)的解決方法；另外，針對(duì)模型在聚類分析中的應(yīng)用研究并結(jié)合離散Morse的相關(guān)理論和方法，研究離散Morse理論在聚類分析中實(shí)現(xiàn)的關(guān)鍵技術(shù)和方法，并提出基于Morse理論的聚類分析模型以適應(yīng)具體應(yīng)用的要求。通過實(shí)驗(yàn)，驗(yàn)證了模型的有效性和可行性。本文的主要研究?jī)?nèi)容如下：1.針對(duì)傳統(tǒng)SOM網(wǎng)絡(luò)模型用于聚類分析時(shí)競(jìng)爭(zhēng)層神經(jīng)元個(gè)數(shù)須預(yù)先指定的缺點(diǎn)，給出了在訓(xùn)練過程中動(dòng)態(tài)確定網(wǎng)絡(luò)結(jié)構(gòu)和單元數(shù)目的解決方案，提出一種新的動(dòng)態(tài)自組織特征映射模型，并給出模型的訓(xùn)練算法。此算法初始只有一個(gè)根結(jié)點(diǎn)。在網(wǎng)絡(luò)訓(xùn)練過程中不斷產(chǎn)生新結(jié)點(diǎn)。新的結(jié)點(diǎn)可在任意位置根據(jù)需要自動(dòng)生成。當(dāng)訓(xùn)練算法結(jié)束時(shí)，根據(jù)得到的樹形結(jié)構(gòu)確定聚類的數(shù)目。算法中通過擴(kuò)展因子控制網(wǎng)絡(luò)的生長(zhǎng)，實(shí)現(xiàn)了不同層次的聚類。算法采用兩階段的訓(xùn)練思想。當(dāng)算法的生長(zhǎng)階段完成后，利用模糊C-聚類的思想，對(duì)生長(zhǎng)階段產(chǎn)生的粗聚類結(jié)果做細(xì)化處理，從而提高最終聚類結(jié)果的精度和算法的收斂速度。通過UCI數(shù)據(jù)集來驗(yàn)證該模型的有效性和優(yōu)越性，并對(duì)其聚類的有效性進(jìn)行對(duì)比分析。2.介紹了譜聚類技術(shù)及相關(guān)概念，對(duì)譜聚類算法進(jìn)行研究及分析，提出一種自動(dòng)確定聚類數(shù)目的譜聚類算法。為了解決CLARANS算法易收斂于局部最優(yōu)及面對(duì)大數(shù)據(jù)集聚類效率不高的問題，結(jié)合遺傳算法易于找到全局最優(yōu)值的特點(diǎn)，將遺傳算法和CLARANS算法相結(jié)合，提出基于GA的聚類分析模型，并通過選擇合適的適應(yīng)值函數(shù)，達(dá)到聚類的目的。通過實(shí)驗(yàn)證明了新算法的的優(yōu)越性3.介紹了離散Morse理論的基本原理及相關(guān)概念，提出一種構(gòu)建離散Morse函數(shù)求最優(yōu)解的算法，并證明了構(gòu)建的函數(shù)是最優(yōu)的離散Morse函數(shù)，同時(shí)構(gòu)建了一種基于離散Morse理論的優(yōu)化模型，實(shí)驗(yàn)的結(jié)果證明了該模型的有效性。這是一個(gè)全新的嘗試。4.把基于離散Morse理論的優(yōu)化模型應(yīng)用于聚類分析，提出一種基于離散Morse優(yōu)化模型的密度聚類算法。聚類后的結(jié)果運(yùn)用層次聚類的思想進(jìn)行優(yōu)化，可以通過參數(shù)的調(diào)整來控制聚類簇的數(shù)目，達(dá)到聚類效果。實(shí)驗(yàn)證明新算法的可行性及有效性。本文的創(chuàng)新點(diǎn)總結(jié)如下：1.提出一種新的動(dòng)態(tài)SOM模型。該模型采用新的生長(zhǎng)閾值函數(shù)，訓(xùn)練算法采用兩階段思想。實(shí)驗(yàn)在UCI數(shù)據(jù)集上進(jìn)行，通過與SOM模型、FCM算法及TreeGNG對(duì)比驗(yàn)證了該模型的有效性和優(yōu)越性。2.提出一種基于GA的自動(dòng)譜聚類算法GA-ISC。通過改進(jìn)的譜聚類算法ISC-CLARANS達(dá)到自動(dòng)產(chǎn)生聚類結(jié)果的目的。引入GA提高CLARANS算法的執(zhí)行效率。實(shí)驗(yàn)分別在人工數(shù)據(jù)集及UCI數(shù)據(jù)集上進(jìn)行。實(shí)驗(yàn)證明ISC-CLARANS算法正確、有效。通過GA-ISC與ISC-CLARANS算法的聚類結(jié)果比較，驗(yàn)證了GA-ISC算法的高效性。3.提出一種基于離散Morse理論的優(yōu)化模型，該模型通過在單純復(fù)形上構(gòu)造離散Morse函數(shù)來實(shí)現(xiàn)。實(shí)驗(yàn)結(jié)果證明了該模型的正確性及有效性。4.提出一種新的基于離散Morse優(yōu)化的聚類模型。該模型在離散曲面上進(jìn)行。聚類后的結(jié)果運(yùn)用層次聚類的思想進(jìn)行優(yōu)化。實(shí)驗(yàn)在人工數(shù)據(jù)集及UCI數(shù)據(jù)集上進(jìn)行，通過與DBSCAN算法的聚類結(jié)果比較，驗(yàn)證了新模型的高效性及優(yōu)越性。 

第 1 章 緒論

1.1 研究課題的背景和意義
隨著信息時(shí)代的不斷發(fā)展以及網(wǎng)絡(luò)的普及，形式多樣的數(shù)據(jù)急劇膨脹。要想在這浩如煙海的數(shù)據(jù)世界中找到所需的信息，強(qiáng)有力的數(shù)據(jù)分析工具尤為重要。人們非常需要一種強(qiáng)有力的能夠發(fā)現(xiàn)數(shù)據(jù)之間內(nèi)在關(guān)系的、隱含的信息和知識(shí)的工具。為迎合這種需要而產(chǎn)生并迅速發(fā)展起來的數(shù)據(jù)挖掘技術(shù)引起了信息科學(xué)領(lǐng)域的普遍關(guān)注[1]。其中聚類分析作為數(shù)據(jù)挖掘的一種強(qiáng)有力的分析工具，得到了迅猛的發(fā)展和成功的應(yīng)用，已在科學(xué)數(shù)據(jù)探測(cè)、圖像處理、模式識(shí)別、醫(yī)療診斷、計(jì)算生物學(xué)、文檔檢索以及 Web 分析等領(lǐng)域起著非常重要的作用。聚類分析的經(jīng)典方法主要可歸納為[2,3,4]：劃分方法、層次方法、基于密度的方法、基于網(wǎng)格的方法、基于模型的方法以及基于計(jì)算智能的神經(jīng)網(wǎng)絡(luò)法、進(jìn)化計(jì)算法、模糊法等[5,6]，以及目前受到關(guān)注的半監(jiān)督聚類方法[7]。而近來新出現(xiàn)的聚類集成方法已迅速成為聚類分析的新興研究熱點(diǎn)。聚類集成的目的是融合來自多個(gè)聚類算法的結(jié)果以得到更高質(zhì)量和魯棒性的聚類結(jié)果�；趫D論的方法[8]，這是新近發(fā)展較快的方法之一，它是利用圖論和圖形學(xué)的原理實(shí)現(xiàn)聚類的方法。與傳統(tǒng)算法相比，該算法可以處理更為復(fù)雜的簇結(jié)構(gòu)如非凸結(jié)構(gòu)，并能收斂于全局最優(yōu)解。
 

1.1.1 聚類分析介紹及意義

聚類是從數(shù)據(jù)集中發(fā)現(xiàn)一些自然的分組（簇），使得簇內(nèi)的相似度大，簇間的相似度小[17]。聚類技術(shù)已被應(yīng)用于多個(gè)領(lǐng)域如模式識(shí)別、機(jī)器學(xué)習(xí)等。聚類問題可這樣表述：在d維空間dR中，給定n個(gè)樣本點(diǎn)和整數(shù)k的值，找到k個(gè)點(diǎn)的集合，其中k個(gè)點(diǎn)稱為中心，使得n中的每個(gè)數(shù)據(jù)點(diǎn)與其最近的中心的歐氏距離的平方根（SSE）之和最小。1 1( )'( )jnkij j ij jj iSSE x x x x ，其中11jnj ijijx xn    為第j個(gè)簇的中心，ijx是第j個(gè)簇中的第i個(gè)數(shù)據(jù)點(diǎn)，且1,2,...ii  n，j  1,2,...k。目前存在如下幾類聚類算法：（1）劃分方法：給定包含n個(gè)樣本點(diǎn)的數(shù)據(jù)集，劃分方法：數(shù)據(jù)集劃分為k個(gè)不相交的子集，每個(gè)子集均代表一個(gè)簇且k  n。代表算法為 K-Means 算法、K-Medoids 算法和 EM 算法、PAM 算法、CLARANS 算法等。K-Means 算法是基于劃分方法的典型算法。用簇中對(duì)象的平均值來表示該簇；K-Medoids 算法中，每個(gè)簇用接近聚類中心的一個(gè)對(duì)象來表示；EM 算法以另一種形式對(duì) K-Means 算法進(jìn)行了擴(kuò)展。它不把對(duì)象分配給一個(gè)確定的簇，而是根據(jù)對(duì)象與簇之間的隸屬關(guān)系發(fā)生的概率來分配對(duì)象。新的平均值基于加權(quán)的度量值來計(jì)算。PAM 算法是基于 K-Medoids 算法的思想。該算法中對(duì)所有可能的對(duì)象對(duì)進(jìn)行分析，每個(gè)對(duì)中的一個(gè)對(duì)象看作是中心點(diǎn)，而另一個(gè)不是。一個(gè)對(duì)象被能產(chǎn)生最大平方-誤差值減少的對(duì)象替代，在一次迭代中產(chǎn)生的最佳對(duì)象的集合成為下次迭代的中心點(diǎn)。此算法的時(shí)間復(fù)雜度為2O ( k ( n  k) )，當(dāng) n 和 k 較大時(shí)，其計(jì)算代價(jià)非常高。比較適合處理較小規(guī)模的數(shù)據(jù)集。CLARA 算法則可處理較大的數(shù)據(jù)集。該算法選取整個(gè)數(shù)據(jù)集中的小部分樣本，采用 PAM 算法選擇中心點(diǎn)進(jìn)行聚類。該算法的執(zhí)行效率比 PAM 要高，但其聚類的質(zhì)量主要取決于選取的小部分樣本。

第 2 章 基于神經(jīng)網(wǎng)絡(luò)的聚類算法研究

2.1 引言
神經(jīng)網(wǎng)絡(luò)技術(shù)用于聚類分析起源于 Kohonen 在 1981 年提出的自組織特征映射神經(jīng)網(wǎng)絡(luò)（SOM）。SOM 神經(jīng)網(wǎng)絡(luò)是一種無監(jiān)督的聚類方法。該網(wǎng)絡(luò)可分為輸入層和輸出層。輸出層的神經(jīng)元互相連接，，每個(gè)輸出神經(jīng)元連接到所有輸入神經(jīng)元，通過若干個(gè)單元競(jìng)爭(zhēng)當(dāng)前對(duì)象來實(shí)現(xiàn)聚類。雖然 SOM 網(wǎng)絡(luò)能夠模擬人腦的處理過程，輸出保持了輸入對(duì)象的拓?fù)浣Y(jié)構(gòu)，有利于在二維或者三維空間中可視化高維數(shù)據(jù)。但當(dāng) SOM 網(wǎng)絡(luò)應(yīng)用于聚類分析時(shí)，由于該模型本身的缺點(diǎn)及應(yīng)用環(huán)境的變化，在應(yīng)用過程中主要存在以下問題：1）SOM 網(wǎng)絡(luò)結(jié)構(gòu)的難以確定由于傳統(tǒng) SOM 網(wǎng)絡(luò)模型用于聚類分析時(shí)競(jìng)爭(zhēng)層神經(jīng)元個(gè)數(shù)須預(yù)先指定，因此大大限制了網(wǎng)絡(luò)的結(jié)構(gòu)及其收斂速度。當(dāng)在聚類過程中采用該模型時(shí)，由于數(shù)據(jù)間的聚類關(guān)系不確定，若輸出層神經(jīng)元個(gè)數(shù)M過多則會(huì)降低學(xué)習(xí)的速度，增加計(jì)算量。若M的個(gè)數(shù)過少，則可能產(chǎn)生粗的聚類結(jié)果，把兩種或兩種以上模式相近的簇歸為一類，不能得到期望的聚類結(jié)果。因此，多種在訓(xùn)練過程中動(dòng)態(tài)確定網(wǎng)絡(luò)結(jié)構(gòu)和單元數(shù)目的算法應(yīng)運(yùn)而生。

2.2 基于 SOM 網(wǎng)絡(luò)的聚類分析模型
當(dāng)外界輸入不同的樣本到 SOM 網(wǎng)絡(luò)時(shí)，初始，輸入樣本引起輸出興奮細(xì)山東師范大學(xué)博士學(xué)位論文28胞的位置各不相同，但經(jīng)過自組織后形成一些細(xì)胞群，他們分別反映了輸入樣本的特征。這些細(xì)胞群在二維輸出空間是一個(gè)平面區(qū)域，樣本自學(xué)習(xí)后，在輸出神經(jīng)元層中排列成一張二維的映射圖，功能相同的神經(jīng)元靠得比較近，功能不相同的神經(jīng)元分得比較開，這個(gè)映射過程通過無指導(dǎo)的競(jìng)爭(zhēng)學(xué)習(xí)算法來實(shí)現(xiàn)，因此稱為自組織特征映射。SOM 屬于無監(jiān)督學(xué)習(xí)網(wǎng)絡(luò)。當(dāng)輸入矢量X屬于兩個(gè)不同類別時(shí)，則相應(yīng)的輸出y的值應(yīng)能夠反映輸入矢量X的特征。如果矢量X在矢量空間中具有隨機(jī)分布，此分布有一個(gè)變化最大的方向，則特征就是指大體上是該矢量在此方向上的投影。當(dāng)X屬于不同的類時(shí)，相應(yīng)的輸出值y會(huì)有一個(gè)明顯的差異，則聚類的功能就可完成。如果輸入矢量是一個(gè)在空間中具有純均勻分布的隨機(jī)矢量，則算法失效；只有當(dāng)輸入矢量的分布具有某種特征時(shí)，才能通過神經(jīng)元的自組織學(xué)習(xí)來發(fā)現(xiàn)這些特征，并且用輸出函數(shù)y來描述這種特征。

第 3 章 基于遺傳優(yōu)化的譜聚類算法研究
3.1 引言................................................................43
3.2 譜聚類算法的介紹....................................................44
3.3 改進(jìn)的譜聚類算法 ...................................................54
3.4 基于遺傳算法的譜聚類方法.............................................57
3.5 小結(jié).................................................................63

第 4 章 基于 Morse 優(yōu)化模型的聚類算法研究

4.1 引言
Morse 理論作為一個(gè)強(qiáng)有力的工具應(yīng)用于計(jì)算拓?fù)鋵W(xué)、計(jì)算機(jī)圖形學(xué)、幾何建模等領(lǐng)域。該理論最初用于研究光滑流形的結(jié)構(gòu)。近年來，F(xiàn)orman 將理論推廣到離散結(jié)構(gòu)如單純復(fù)形中，取得了更廣范圍的應(yīng)用。在流形上定義一個(gè) Morse 函數(shù)，則可通過產(chǎn)生的臨界單元得出該流形的拓?fù)浣Y(jié)構(gòu)信息。因此，如何在單元復(fù)形上定義最優(yōu)離散 Morse 函數(shù)是一個(gè)關(guān)鍵問題。而最優(yōu)則是指由此產(chǎn)生的臨界單元最少。Forman 證明了這是一個(gè)MAX  SNP問題。Thomas 在 2 維流形上提出一種線性算法使得總能達(dá)到最優(yōu)。受 Forman[88][115]的離散 Morse 理論的啟發(fā)，本文嘗試在 3 維及以上離散空間K 對(duì)任意給定的 f :K   R進(jìn)行優(yōu)化分析構(gòu)造最優(yōu)離散 Morse 函數(shù)，產(chǎn)生盡可能少的臨界單元，從而得到函數(shù)的最優(yōu)值或接近最優(yōu)值。根據(jù)上述思想構(gòu)建了一種基于離散 Morse 理論的優(yōu)化模型，解決了離散 Morse 理論的優(yōu)化問題，并把這一優(yōu)化模型應(yīng)用于聚類分析，提出一種基于離散 Morse 優(yōu)化模型的聚類算法。算法采用基于核密度估計(jì)的層次聚類的思想，根據(jù)離散 Morse 優(yōu)化模型得到密度函數(shù)的極值，同時(shí)根據(jù)構(gòu)造的離散梯度向量場(chǎng)得到以極值點(diǎn)為聚類中心的數(shù)據(jù)集的初始劃分，然后通過臨界單元的抵消算法對(duì)初始聚類進(jìn)行合并產(chǎn)生不同層次的劃分模式。實(shí)驗(yàn)分別在人工數(shù)據(jù)集和 UCI 數(shù)據(jù)庫中的Iris數(shù)據(jù)集和Haberman 's Survival數(shù)據(jù)集上進(jìn)行。理論分析和仿真實(shí)驗(yàn)結(jié)果顯示，該算法能夠發(fā)現(xiàn)任意形狀、大小和密度的聚類，能較好劃分?jǐn)?shù)據(jù)點(diǎn)重疊區(qū)域的聚類形狀，證明了新算法的可行性及有效性。

結(jié)論
基于計(jì)算智能的聚類分析模型對(duì)處理目標(biāo)的特性有良好的適應(yīng)能力，彌補(bǔ)了傳統(tǒng)聚類算法的缺點(diǎn)及不足，取得了良好的效果。本文中有針對(duì)性的選取了計(jì)算智能方法中的人工神經(jīng)網(wǎng)絡(luò)、遺傳算法、離散 Morse 理論應(yīng)用于聚類分析，構(gòu)造聚類分析模型，研究該模型的定義及優(yōu)化方法的特點(diǎn)和不足，改進(jìn)或提出相應(yīng)的解決方法。離散 Morse 理論是一種新的計(jì)算智能技術(shù)，本文在研究其理論的基礎(chǔ)上，成功把該技術(shù)應(yīng)用到聚類分析中。本文針對(duì)模型在聚類分析中的應(yīng)用研究并結(jié)合離散 Morse 的相關(guān)理論和方法，研究離散 Morse 理論在聚類分析中實(shí)現(xiàn)的關(guān)鍵技術(shù)和方法，并提出基于 Morse 理論的密度聚類分析模型以適應(yīng)具體應(yīng)用的要求，同時(shí)對(duì)提出的聚類分析模型進(jìn)行推廣，使其具有更為普遍的適用性。根據(jù)該模型的特點(diǎn)，采用面向?qū)ο蠹夹g(shù)搭建實(shí)驗(yàn)平臺(tái)，以驗(yàn)證所提方法或策略的有效性。
現(xiàn)將論文取得的一些研究成果總結(jié)如下：1. 闡述了傳統(tǒng)的 SOM 網(wǎng)絡(luò)聚類分析模型，給出了 SOM 網(wǎng)絡(luò)聚類模型的特點(diǎn)，研究及分析了 SOM 網(wǎng)絡(luò)用于聚類分析時(shí)競(jìng)爭(zhēng)層神經(jīng)元個(gè)數(shù)需提前給出及網(wǎng)絡(luò)結(jié)構(gòu)的固定化等問題。針對(duì)傳統(tǒng) SOM 網(wǎng)絡(luò)聚類分析模型，介紹了有代表性的動(dòng)態(tài)網(wǎng)絡(luò)聚類分析模型—TreeGNG 動(dòng)態(tài)網(wǎng)絡(luò)聚類分析模型。本論文借鑒了 TreeGNG 網(wǎng)絡(luò)訓(xùn)練算法中樹形結(jié)構(gòu)的構(gòu)造思想，結(jié)合神經(jīng)網(wǎng)絡(luò)中兩步聚類的方法，提出一種新的動(dòng)態(tài)模糊自組織神經(jīng)網(wǎng)絡(luò)聚類模型 DSOM-FCM（dynamic self-organizing map-fuzzy C-means）。DSOM-FCM 是基于初始只有一個(gè)根結(jié)點(diǎn)的樹形結(jié)構(gòu)模型。在網(wǎng)絡(luò)訓(xùn)練過程中不斷產(chǎn)生新結(jié)點(diǎn)。新的結(jié)點(diǎn)可在任意位置根據(jù)需要自動(dòng)生成。當(dāng)訓(xùn)練算法結(jié)束時(shí)，根據(jù)得到的樹形結(jié)構(gòu)確定聚類的數(shù)目。

參考文獻(xiàn)（略）