1、畢業論文設計（論文）題目 魚群算法在聚類分析中的應用 學院名稱 專 業 （班 級） 姓 名 （學 號） 指 導 教 師 2013年6月5日目錄 TOC o 1-3 h z u HYPERLINK l _Toc387332329 摘 要 PAGEREF _Toc387332329 h 3 HYPERLINK l _Toc387332330 Abstract PAGEREF _Toc387332330 h 4 HYPERLINK l _Toc387332331 1緒論 PAGEREF _Toc387332331 h 5 HYPERLINK l _Toc387332332 1.1研究的背景和意義 P

2、AGEREF _Toc387332332 h 5 HYPERLINK l _Toc387332333 1.1.1研究背景 PAGEREF _Toc387332333 h 5 HYPERLINK l _Toc387332334 1.1.2研究目的與意義 PAGEREF _Toc387332334 h 5 HYPERLINK l _Toc387332335 1.2國內外研究現狀 PAGEREF _Toc387332335 h 6 HYPERLINK l _Toc387332336 1.2.1數據挖掘研究現狀 PAGEREF _Toc387332336 h 6 HYPERLINK l _Toc387

3、332337 1.2.2聚類方法研究現狀 PAGEREF _Toc387332337 h 6 HYPERLINK l _Toc387332338 1.3論文各部分的主要內容 PAGEREF _Toc387332338 h 7 HYPERLINK l _Toc387332339 2聚類算法概論 PAGEREF _Toc387332339 h 7 HYPERLINK l _Toc387332340 2.1聚類的定義 PAGEREF _Toc387332340 h 7 HYPERLINK l _Toc387332341 2.2聚類算法的分類與應用 PAGEREF _Toc387332341 h 8

4、HYPERLINK l _Toc387332342 2.3 K-means算法 PAGEREF _Toc387332342 h 9 HYPERLINK l _Toc387332343 3人工魚群算法 PAGEREF _Toc387332343 h 10 HYPERLINK l _Toc387332344 3.1人工魚的相關定義 PAGEREF _Toc387332344 h 10 HYPERLINK l _Toc387332345 3.2人工魚群算法發的運行機制 PAGEREF _Toc387332345 h 11 HYPERLINK l _Toc387332346 3.1.1 行為描述 PA

5、GEREF _Toc387332346 h 11 HYPERLINK l _Toc387332347 3.1.2 行為選擇 PAGEREF _Toc387332347 h 12 HYPERLINK l _Toc387332348 3.3人工魚群算法的研究與發展趨勢 PAGEREF _Toc387332348 h 13 HYPERLINK l _Toc387332349 4人工魚群算法求解聚類問題 PAGEREF _Toc387332349 h 14 HYPERLINK l _Toc387332350 4.1引言 PAGEREF _Toc387332350 h 14 HYPERLINK l _T

6、oc387332351 4.2人工魚群算法與聚類融合 PAGEREF _Toc387332351 h 14 HYPERLINK l _Toc387332352 4.3算例及結果計算分析 PAGEREF _Toc387332352 h 14 HYPERLINK l _Toc387332353 4.3.1實現算法步驟 PAGEREF _Toc387332353 h 14 HYPERLINK l _Toc387332354 4.3.2運算結果 PAGEREF _Toc387332354 h 14 HYPERLINK l _Toc387332355 4.3.3分析 PAGEREF _Toc387332

7、355 h 14 HYPERLINK l _Toc387332356 5總結 PAGEREF _Toc387332356 h 14魚群算法在聚類分析中的應用摘 要：數據挖掘是信息產業界近年來非常熱門的研究方向，聚類分析是數據挖掘中的核心技術。聚類在數據挖掘、統計學、機器學習等很多領域都有廣泛應用，聚類算法大體可劃分為以下幾類：劃分方法、層次方法、基于密度的方法、基于網格的方法和基于模型的方法。人工魚群算法（AFSA）是一種新型的仿生優化算法，采用自下而上的設計方法，對尋優空間的形式和性質有求不高。且算法擁有對初始參數要求低、結構簡單和尋優速度快等優點，使得算法從提出到現在得到了廣泛的好評。 本

8、文將人工魚群算法與聚類的思想相融合，并將算法用于求解聚類問題。并與傳統的K-means算法進行比較，得出算法的優越性。關鍵詞：人工魚群算法；聚類；K-means算法；尋優Abstract1緒論1.1研究的背景和意義1.1.1研究背景隨著信息信息技術的日益發展，大量的數據不斷地從我們的工作和生活中產生，這些數據記錄了我們的日常生活中的點點滴滴，我們將其中對我們有意義、有價值的保存起來，就形成了數據庫里面的一條條記錄。然而，對于這些每天都在積累的大量的數據本身而言是并不能作為信息的，然而這些數據的背后卻隱藏著巨大的信息量，對我們有用的數據才是信息，所以我們得通過各種技術去對大量的數據進行統計、挖掘

9、。面對每日以指數增長的數據量，老舊的數據挖掘技術顯得心有余而力不足，與此同時聚類數據挖掘的興起與仿生群體算法的發展，使得數據挖掘更加的高效。數據挖掘（Data Mining）又被稱為知識發現（Knowledge Discovery，KD），是從大量隨機的數據中“挖掘”隱含在數據集中的潛在信息的過程（王沖）。聚類分析是數據挖掘中的核心技術，聚類分析（Cluster Analysis）又稱群分析，是根據“物以類聚”的道理，對樣品或指標進行分類的一種多元統計分析方法，它們討論的對象是大量的樣品，要求能合理地按各自的特性來進行合理的分類，沒有任何模式可供參考或依循，即是在沒有先驗知識的情況下進行的。聚

10、類算法大體可劃分為以下幾類：劃分方法、層次方法、基于密度的方法、基于網格的方法和基于模型的方法。而屬于劃分聚類的k均值聚類算法算法是根據初始聚類中心來確定一個初始劃分，然后對初始劃分進行優化。他的缺點就是初始聚類中心的選擇對聚類結果的影響很大而且當數據量非常大時，算法的時間開銷非常大。所以，近年來產生了許多仿生類的對原始參數要求較低并且能迅速準確的獲得最優解的算法，如魚群算法、蟻群算法、螢火蟲算法等。人工魚群算法（AFSA）是李曉磊等人模仿魚類行為方式提出的一種基于動物自治體的優化方法，是集群智能思想的一個具體應用。例如：在一片水域中，魚生存數目最多的地方一般就是本水域中富含營養物質最多的地方

11、，因此，本算法就依據這一特點來模仿魚群的聚群行為從而實現聚類的。該算法具有尋優快、對初始值和參數要求不高、結構簡單、能迅速脫離局部最優等優點。1.1.2研究目的與意義本文研究的目的：1）研究人工魚群算法的工作機制；2）研究如何將聚類機制引入人工魚群算法；3）研究如何將魚群算法應用于聚類挖掘并與傳統的聚類挖掘算法進行比較；4）探索驗證該算法在解決優化問題的特性；本文研究的意義：人工魚群算法是一種基于動物行為的只能優化算法，它采用自下而上的設計方法，對尋優空間的形式和性質沒有特殊要求。魚群算法從構造魚類底層的行為開始，通過每條人工魚個體的尋優行為，最終在整個魚群中使得全局最優值凸顯出來，并且算法的

12、實現無需設定大量的參數。算法具有良好的自適應能力、尋優速度快、克服局部極值取得全局最優值的能力強等優點。是一種魯棒性好的并行算法，可以應用于許多優化模型的求解。人工魚群算法的提出與研究，不僅具有理論意義而且有很高的應用價值。1.2國內外研究現狀1.2.1數據挖掘研究現狀數據挖掘與知識發現（Knowledge Discovery in databases，KDD）都是數據庫領域中的重要研究課題。1989年，KDD一詞正式形成。1995年，工程領域的數據挖掘技術與科研領域的知識發現分開。經歷了二十年左右的探索，目前圍繞KDD理論、技術和應用方面的研究都有了一定的成果，跨領域的理論結合和方法整合成為

13、當前研究者們的主要研究方向之一。相比于國外，國內對數據挖掘方面的研究起步較晚，但由于人們的高度重視，現在正處于一個發展快速的階段。目前國內外幾個主要的研究熱點包括：文本數據挖掘、網站數據挖掘和基因或生物信息的數據挖掘。網站數據挖掘與傳統的數據挖掘相差不大，主要的數據格式來源于用戶點擊率。文本挖掘與傳統挖掘有一定的差距，因為分析和抽取有用文本并形成相應知識需要很復雜的問題分析技術，而目前還沒有能夠聚類完善的分析能力的完本挖掘算法?；蚝蜕镄畔⒌臄祿诰驅θ祟愑兄钸h的意義，找到病人基因的變化然后研究相應的制藥技術，是人類一直以來的夢想，這些醫用技術的發現需要達賴能夠的基因數據分析，需要數據挖掘

14、技術的支撐。1.2.2聚類方法研究現狀聚類是數據挖掘的一個重要的研究領域，而聚類的方法也一直受到研究人員的廣泛關注，經歷了長期的發展，形成了各種不同的聚類方法。聚類的算法大體可劃分成以下幾類：劃分方法、層次方法、基于密度的方法、基于網格的方法和基于模型的方法，不同的聚類方法又都有著各自的特性和應用范圍。比如K-means算法，以收斂速度快，執行效率高見長，對球裝簇的中小規模的數據非常適用，缺點是對不規則形狀的數據集難以識別導致適用性大大降低、過度依賴于聚類中心的選擇、初始參數設置復雜等特點。為了彌補在傳統聚類算法存在的不同缺陷，一些研究人員將一些智能算法與聚類算法融合，改造成聚類算法，以此來更

15、好的發揮聚類算法的性能。常用的智能算法有：遺傳算法、粒子群算法、蟻群算法、魚群算法等。遺傳算法(Genetic Algorithm,GA)通過借鑒達爾文進化理論中的選擇機制和競爭淘汰的生物進化過程,模擬自然界遺傳機理的搜索優化算法。免疫算法(Immune Algorithm)從網絡理論和體細胞理論中得到啟發,模擬人類自身的免疫系統,通過生成不同抗體模擬了類似于免疫系統的自我調節功能。由于劃分方法的經典K-均值算法是聚類算法中高效且簡單的算法且容易實現,現在已經被應用到如圖象分割、文檔聚類等方面相當廣泛的領域中。王沖1.3論文各部分的主要內容本文主要研究了人工魚群算法應用于。在基本人工魚群算法的

16、基礎上，添加聚類因素，將人工魚群算法改造成一種聚類算法。本文的組織結構如下：第一章：結合本文的研究內容，介紹了數據挖掘技術、國內外大數據研究近況等，并對本文的研究目的、研究意義和研究的思路進行了簡要說明。第二章：主要介紹了聚類分析的基本概念，及K-means算法的運行機制和研究狀況。第三章：主要介紹了基本人工魚群算法，以及人工魚群算法的研究現狀和發展趨勢。第四章：在深入研究人工魚群算法和聚類問題的基礎上，求解聚類問題的人工魚群算法。第五章：對全文進行總結，得出魚群算法在聚類方面相比于傳統聚類算法的優越性。2聚類算法概論2.1聚類的定義到目前為止，聚類仍舊沒有一個在學術界統一的定義。1974年E

17、veritt定義：一個類簇內的個體是相似的，不同類簇的個體是不相似的；一個類簇是在數據空間中點的聚集，而同一類簇的任意兩個點之間的距離小于他與不同類簇之間兩個點的距離；類簇可以認為是一個多維空間中點密集度相對較高的一個連通區域，他們與其他密度較低的點集區域相分離。聚類與分類是不同的，在聚類中，目標數據集的類簇信息是未知的，從而需要以某種度量標準來將數據集中的樣本劃分到各個類簇。而對于分類來說，分類的目的是要從目的訓練樣本集中提出分類規則，而首先樣本數據的類簇標號需要是已知的，再根據提取出來的規則對其他位置標號的對象進行類標識。所以相比于分類，聚類分析稱為無知道或者無監督學習。王沖所謂聚類分析就

18、是從數據中找到數據之間的相似度，根據相似度將數據劃分到不同的類，使各類之間具有盡可能大的離散度，各類內部具有盡可能小的離散度。它的一般數學描述如下：設X=Xi,|Xi=Xi1,Xi2,Xid,i=1,2,n標識模式樣本集，共有n個樣本。其中，d維向量Xi=Xi1,Xi2,Xid表示一個樣本，樣本集有k個模式分類。聚類問題的實質就是要找一個劃分C=C1,C2,Ck,滿足：X=i=1kCi,CiF,i=1,2,k,CiCj=,i,j=1,2,k;ij;使同一類內部離散度之和達到最小，用（1.1）式表示。F=minj=1kXiCjdXi,mj (1.1)mj=1|Cj|XiCjXi, j=1,2,k

19、 (1.2) 在式（1.1）中，mj為聚類中心，由（1.2）式計算得到，d（Xi,mj）表示第Cj類中模式樣本Xi到該類中心mj的歐式距離。2.2聚類算法的分類與應用聚類算法大體可以劃分為以下幾類：劃分方法、層次方法、基于密度的方法、基于網格的方法和基于模型的方法。（1）劃分方法（partitioning method）給定一個包含n個數據對象或元組的數據庫，一個劃分方法構建數據的c個劃分，每個劃分表示一個簇，且cn。通常會采用一個劃分準則（經常成為相似度函數），例如距離，一邊在同一個簇中的對象是“相似的”，在不同簇中的對象是“相異的”。這些聚類方法對在中小規模的數據庫中發現球狀簇很適用。為了

20、對大規模的數據集進行聚類，以及處理復雜形狀的聚類，基于劃分的方法需要進一步的擴展。（2）層次方法（hiernrchical method）層次方法對給定數據對象集合進行層次的分解。根據層次分解是自底向上還是自頂向下形成，層次聚類的方法可以進一步分為凝聚和分裂的。層次聚類方法的缺陷在于，一旦一個步驟（合并或分裂）完成，他就不能被撤銷，因此而不能更正錯誤的決定。改進層次方法的聚類質量的一個有希望的方向就是將層次聚類和其他聚類技術進行集成，形成多階段聚類。（3）基于密度的方法（density-based method） 提出了基于密度的聚類方法是為了發現任意形狀的聚類結果。其主要思想是：只要臨近區域

21、的密度超過某個閥值。就繼續聚類。這樣的方法可以用來過濾“噪聲”孤立點數據，發現任意形狀的簇。（4）基于網格的方法（grid-based method）基于網格的聚類方法采用一個多分辨率的網格數據結構。把對象空間量化為有限數只的單元，形成了一個網格結構。所有的聚糞操作都在這個網格結構上進行。這種方法的主要優點是它的處理速度很快。其處理時間獨立于數據對象的數目，只與量化空間中每一維的單元數目有關。（5）基于模型的方法（model-based method） 基于模型的方法為每個簇假定了一個模型，尋找數據對給定模型的最佳擬合?；谀Ｐ偷乃惴赡苄酝ㄟ^構建反映數據點空間分布的密度函數來定位聚類。這種聚

22、類方法試圖優化給定的數據和某些數學模型之間的適應性。2.3 K-means算法K-means算法是聚類算法中最典型最常用之一，該算法使用所有數據的加權平均來表示它的每個類別，表示類別的平均值稱為聚類中心。k-means算法對于數值屬性的數據，能充分體現出聚類在幾何學和統計學上的意義，但不能用于類別屬性的數據。在K-means算法中，用數據對象與簇中心的距離來表示相似度，相似度小的就劃分到同一個簇。具體流程：先隨機地選擇k個對象初始代表k個劃分；其次，對其他對象，根據其與各個簇中心的距離，劃分到距離最近的簇，隨后，重新計算每個簇的平均值得到新的簇中心，再重新聚類，不斷重復這個過程直到準則函數收斂

23、。如果所有對象總數用n表示，簇的數目用k表示，迭代次數用t表示，k-means算法的時間復雜度表示為O(nkt)。雖然算法效率比較高；但原始k-means算法也存在一些缺陷：黃志紅.基于層次聚類的k均值算法研究J.電腦開發與應用,2009,22(7):l一5 初始聚類中心的選擇對聚類結果的好壞影響很大；可能陷入局部最優值；沒有可依循的準則來選擇K值；對異常數據較為敏感；處理的數據只能數值屬性的數據；可能使得聚類結果不平衡。 k均值聚類的核心思想用數學方法描述如下：設xj(1，2，n)表示n個向量，Gi(1，2，c)表示c個組，算法就是要將n個向量分到c個分組中，通過計算每組的聚類中心，使得非相

24、似性(或距離)指標的價值函數(或目標函數)達到最小。如果用歐幾里德距離表示組j中向量xk與相應聚類中心ci間的非相似性指標，那么價值函數可定義如式(1.3)。J=i=1cJi=i=1c(k,xkGixkci2) (1.3)式（1.3）中，Ji=k,xkGixkci2表示組i類的價值函數。可以看出，Ji的值依賴于Gi的幾何特性和ci的位置。一般用一個cn的二位隸屬矩陣U來定義劃分過的組。如果第j個數據點xi屬于組i，則U中的元素ui為1；否則，U中的元素uij取0。聚類中心ci一旦確定，可得到式（1.3）最小的uij的式子，如式（1.4）。uij=10 對每個ki，如果xkci2xkck2其他

25、(1.4)若ci是xi的最近聚類中心，則xj屬于組i。因為一個給定數據只能屬于一個組，所以隸屬矩陣U具有式(1.5)、式(1.6)的性質。j=1cuij=1,j=1,2,n (1.5) 且i=1cj=1nuij=n (1.6)對于固定的uij，使式(1.3)最小的最佳聚類中心就是組i中所有向量的均值，如式(1.7)所示。ci=1Gik,xkGixk (其中，|Gi|是Gi的規模) (1.7)n個向量xi(1,2,n)的k均值算法確定聚類中心ci和隸屬矩陣U的步驟如下：第1步：算法初始化聚類中心ci，i=1，2，c。從所有數據點中任取c個點是一種典型的做法。第2步：用式(1.4)確定隸屬矩陣U。

26、第3步：根據式(1.3)計算價值函數。如果它小于某個確定的閥值,或它相對上次價值函數值的改變量小于某個閥值,則算法停止。第4步：根據式(1.5)修正聚類中心。返回第2步。這個算法是循環執行的且不能確保它收斂于全局最優解。k均值算法的性能主要依賴于聚類中心的初始位置。k均值算法在線運行的情況下,利用時間平均導出相應的聚類中心和組。算法使用式(1.8)修正給定的數據點x對應的最近的聚類中心ci。ci=(xci) (1.8)式(1.8)從本質上講已經嵌入了非監督學習神經元網絡的學習法則，一句定義的測量標準，將數據分成幾組，使得同組內數據與其他組數據相比具有較強的相似性，也就是聚類。聚類是數據挖掘中最

27、基礎的操作之一，一些傳統聚類方法已不能滿足處理復雜類型的高維的任意分布形狀的數據集合的聚類。3人工魚群算法在動物的進化過程中，經過漫長的自然界的優勝劣汰，形成了形形色色的覓食和生存方式，這些方式為人類解決問題的思路帶來了不少啟發和鼓舞，動物一般不具有人類所具有的復雜邏輯推理能力和綜合判斷能力的高級智能，它們的目的是在個體的簡單行為或通過群體的簡單行為而達到或突現出來的。動物行為具有以下幾個特點： 1）適應性：動物通過感覺器官來感知外界環境，并應激性的做出各種反應，從而影響環境，表現出與環境交互的能力；2） 自治性： 動物有其特有的某些行為，在不同的時刻和不同的環境中能夠自主的選取某種行為，而不

28、是通過外界的控制或指導； 3）盲目性：不像傳統的基于知識的智能系統，有著明確的目標；單個個體的行為是獨立的，與總目標之間沒有直接的關系； 4）突現性：總目標的完成是在個體行為的運動過程中突現出來的： 5）并行性：各個體的行為是實時的、并行進行的?！纠顣岳凇?.1人工魚的相關定義在一片水域中，與生存數目最多的地方一般就是水域中富含營養物質最多的地方，因此，本算法就依據這一特點來模仿魚群的覓食行為從而實現尋優。魚群的幾種典型的行為：覓食行為、聚群行為和追尾行為，魚群的行為與尋優問題的求解聯系密切，人工魚群算法實施的主要問題就在于如何利用簡單有效的方式來構造并實現這些魚群行為。魚群的覓食行為實質是朝

29、著食物多的方向游動，而在魚群算法中，則是以迭代方式向較優方向前進。用向量X=（x1,x2,xn）表示人工魚個體的狀態，變量xi（i=1,2,n）表示欲尋優的變量；定義Y=f（X）表示人工魚X當前所在位置的食物濃度,即Y為目標函數值；定義dij=XiXj表示人工魚個體之間的距離；人工魚的感知距離用變量Visual表示；人工魚移動的最大步長用Step表示；擁擠度因子用變量d表示。 3.2人工魚群算法發的運行機制3.1.1 行為描述（1）覓食行為設人工魚當前狀態為Xi，在其感知范圍內隨機選擇一個狀態Xj，如果在求極大問題中，YiYj，應極大和極小問題可以互相轉換，所以以下均以求幾大問題討論），則向該

30、方向前進一步；反之，再重新隨機選擇狀態Xj，判斷是否滿足前進條件；反復幾次后，如果仍然不滿足前進條件，則隨機移動一步。偽代碼描述如下：Float Artificial-fish:AF-prey() for(i=0;itry-number;i+) Xj=Xi+Random(Visual); if(YiYj) Xi|next=Xi+Random(Step)XjXiXjXi; else Xi|next=Xi+Random(Step); return AF-foodconsistence(Xi|next); （2）聚群行為設人工魚當前狀態為Xi，探索當前領域內（即dijYi，表明伙伴中心有較多的食物并且不太擁擠，則朝伙伴的中心位置方向前進一步；否則執行覓食行為。偽代碼如下：float Artificial-fish:AF-swarm() nf=0; Xc=0; for(j=0;jfriend-number;j+) if(dijYi) Xi|next=Xi+Random(Step)XcXiXcXi; else AF-prey(); eturn AF-foodconsistence(Xi|next);（3）追尾行為【李曉磊】設人工魚當前狀態為Xi，探索當前領域內（即dijYi，表明Xj的狀態具有較高的食物濃度并且其周圍并不太擁擠，則朝伙伴Xj的方向前進一步；否則執行覓食行為。偽代碼描述