[發明專利]基于自適應小生境的遺傳聚類方法

在審

• 申請號: 201310580924.9
• 申請日: 2013-11-18
• 公開（公告）號: CN103617206A
• 公開（公告）日: 2014-03-05
• 發明（設計）人: 盛偉國;白麗葉;盛蒙蒙;單鵬霄;陳勝勇
• 申請（專利權）人: 浙江工業大學
• 主分類號: G06F17/30
• 分類號: G06F17/30
• 代理公司: 杭州天正專利事務所有限公司 33201
• 代理人: 王兵;黃美娟

技術領域

本發明涉及智能算法和數據聚類領域，具體涉及一種基于自適應小生境的遺傳聚類方法，通過嵌入限制錦標賽選擇（RTS）小生境方法自動設置其參數值。

背景技術

數據聚類是機器學習中最難、最具挑戰性的問題之一。它的目標是將一個數據對象劃分為多個簇，使得同一個簇內的對象彼此相似，來自不同簇的對象彼此不相似。數據聚類是無監督學習的一種基本工具，已被廣泛應用于許多科學與工程領域，例如大數據分析和計算機視覺等。一般來講，當需要把大量信息分類成便于管理的有意義的簇的時候，聚類方法極其重要。

數據聚類算法主要包括分層聚類和分割聚類。分層聚類方法生成簇的層次結構，每個簇嵌套在一個更高層次的簇內。這種方法不存在局部最優以及對初始化敏感等問題。然而，分層聚類在聚類過程中僅利用局部信息，忽略簇的大小和全局形狀。此外，該方法是一種靜態聚類方法，數據對象在聚類的早期階段被分配到一個給定的簇后，在下一個階段不能再被分配到其它的簇中。相對于分層聚類，分割聚類則是一種動態的方法，并且考慮簇的大小和全局形狀。本發明專利設計的方法針對數據進行分割聚類。

對于一個較大的數據集，確定其最優分割結果被認為是非常困難的問題。為了解決這一難題，現有的方法往往采用隨機優化技術，其中最突出的技術是遺傳算法。遺傳算法（GA）作為一種搜索和優化技術，目前已被廣泛應用于生物信息學、計算機科學、工程學等領域。在數據聚類中，對于一些搜索空間較小的聚類問題，傳統的GA通常有能力確定最優聚類方案。然而，對于復雜的聚類問題，往往涉及大量的局部最優解，傳統GA則無法找出最優聚類結果。這主要是由于傳統的GA在進化過程中不能保持解決方案多樣性，從而導致整個種群過早收斂到局部最優解。

小生境方法的出現和發展能夠緩解這一問題。在搜索過程中，應用小生境方法可以保持種群的多樣性，從而防止陷入較差的局部最優解。然而，這些小生境方法的運行效果通常取決于其特定參數的設置。通常這些參數在被設定為某個值后，在整個遺傳算法的運行過程中保持不變。由于遺傳算法的運行是動態的過程，在整個運行過程中保持小生境方法參數值不變將在很大程度上限制其運行效果。

本發明提出了一種基于自適應RTS小生境的遺傳聚類方法，該方法自動調節RTS小生境方法的參數，在種群中形成并維持高適應度的散布小生境，從而有效地探索聚類問題的復雜決策空間。

發明內容

本發明要解決現有遺傳聚類算法的缺點和不足，提出一種基于自適應小生境的遺傳聚類方法。該方法設計和采用自適應RTS小生境方法在種群中形成和維持高適宜度的散布小生境，從而有效地探索聚類問題的復雜決策空間。

本發明解決其技術問題所采用的方案是：

一種基于自適應小生境的遺傳聚類方法，包括如下步驟：

1.產生一個具有P個解的初始種群；

2.計算初始種群中每一個解的適宜度值；

DB=1KΣi=1Kmaxj,j≠i{Si+Sjdij}]]>

其中，K為簇數目，d_ij為簇C_i與C_j之間的距離，S_i為簇C_i的散布度，