[發明專利]一種基于遺傳算法的數據聚類分析方法

在審

• 申請號: 201910242200.0
• 申請日: 2019-03-28
• 公開（公告）號: CN110188785A
• 公開（公告）日: 2019-08-30
• 發明（設計）人: 王利鑫
• 申請（專利權）人: 山東浪潮云信息技術有限公司
• 主分類號: G06K9/62
• 分類號: G06K9/62;G06N3/12
• 代理公司: 濟南信達專利事務所有限公司 37100
• 代理人: 姜明

1.一種基于遺傳算法的數據聚類分析方法，其特征在于，包括以下步驟：

(A)首先從要聚類的樣本集選出初始種群；

(B)對選出的初始種群執行遺傳算法；

(C)對執行完遺傳算法后產生的新種群執行K-means操作；

(D)步驟(A)-步驟(C)反復循環，直到尋找出聚類問題的最優解。

2.根據權利要求1所述的基于遺傳算法的數據聚類分析方法，其特征在于：所述步驟(A)中，初始群體隨機生成，具體步驟如下：

(1)首先從樣本空間中隨機選出k個個體，每個個體表示一個初始聚類中心；

(2)然后根據所采用的編碼方式將這組隨機選出的初始聚類中心編碼成一條染色體；

(3)重復進行m次染色體初始化，直到生成初始種群，所述m為種群大小。

3.根據權利要求2所述的基于遺傳算法的數據聚類分析方法，其特征在于：所述步驟(2)中，染色體編碼采用基于聚類中心的浮點數編碼方法。

4.根據權利要求1所述的基于遺傳算法的數據聚類分析方法，其特征在于：所述步驟(B)中，對選出的初始種群執行遺傳算法，包括以下步驟：

(1)采用錦標賽選擇法進行選擇操作，隨機地從種群中挑選一定數目的個體，然后從中選出適應度最大的個體作為父個體，重復迭代該步驟直到父個體的總數達到種群規模；

(2)采用適合浮點數編碼的算術交叉算子對兩個相互配對的染色體進行交叉操作，形成兩個新的個體；

(3)采用均勻變異算子對交叉操作得到的新個體染色體編碼串進行變異操作，從而形成一個新的個體。

5.根據權利要求4所述的基于遺傳算法的數據聚類分析方法，其特征在于：所述步驟(1)中，適應度是用來評價個體的適應度，區別群體中個體優劣的標準；個體的適應度越高，其存活的概率就越大；由于聚類準則函數J越小說明聚類劃分的質量越好，聚類準則函數J越大說明聚類劃分的質量越差，因此適應度函數表示為：

其中，聚類準則函數J公式為：

其中，k為聚類類別數，S_j為第j個類別的樣本集合，x為樣本對象，z_j為S_j集合的聚類中心。

6.根據權利要求4所述的基于遺傳算法的數據聚類分析方法，其特征在于：所述步驟(2)中，交叉操作是指對兩個相互配對的染色體按某種方式相互交換部分基因，從而形成兩個新的個體；算術交叉是指由兩個個體的線性組合而產生出兩個新的個體；

當在兩個個體x₁和x₂之間進行算術交叉時，交叉操作后產生的新個體為：

其中，α是交叉參數，在均勻算術交叉中α是一個常數。

7.根據權利要求4所述的基于遺傳算法的數據聚類分析方法，其特征在于：所述步驟(3)中，變異是指將個體染色體編碼串中的某些基因座上的基因值用該基因座的其他等位來替換，從而形成一個新的個體；變異的目的是改善遺傳算法的局部搜索能力；維持群體的多樣性，防止早熟收斂；變異操作包括以下步驟：

(S1)依次指定個體編碼串中的每個基因座為變異點，并確定每個基因點的取值范圍[U_min，U_max]；

(S2)對每一個變異點，以變異概率P_m從對應基因的取值范圍內取一個隨機數來代替原有值，其中變異點的新基因值為：

其中，r為(0，1)范圍內符合均勻概率分布的一個隨機數。

8.根據權利要求1所述的基于遺傳算法的數據聚類分析方法，其特征在于：所述步驟(C)中，以變異后產生的新群體的編碼值作為中心，把每個數據對象分配到最近的類，形成新的聚類劃分；然后計算新的聚類中心，取代原來的編碼值；經K-means優化操作后產生新一代種群開始執行下一輪遺傳算法操作。

9.根據權利要求1～8任意一項所述的基于遺傳算法的數據聚類分析方法，其特征在于，具體步驟如下：

(1)設置遺傳參數，包括聚類類別數k，種群規模m，最大迭代次數T，交叉概率P_c和變異概率P_m；

(2)從樣本中隨機選取k個點作為聚類中心并進行染色體編碼，重復m次，產生初始種群；

(3)計算群體中各個體的適應度f；

(4)依次通過選擇操作、交叉操作、變異操作和K-means操作，產生新一代群體；

(5)重復步驟(3)和步驟(4)，直到達到最大迭代次數T；

(6)計算新一代群體的適應度f，以最大適應度的最佳個體為中心進行K-means聚類；

(7)輸出聚類結果。