[發明專利]一種可變長染色體編碼的混合并行遺傳聚類算法

在審

• 申請號: 201710315280.9
• 申請日: 2017-05-08
• 公開（公告）號: CN107038479A
• 公開（公告）日: 2017-08-11
• 發明（設計）人: 戴文華;焦翠珍;錢濤;趙君喆;聞彬;江偉;厲陽春;范平
• 申請（專利權）人: 湖北科技學院
• 主分類號: G06N3/08
• 分類號: G06N3/08;G06N3/12
• 代理公司: 暫無信息
• 代理人: 暫無信息

技術領域

本發明屬于數據分析與處理技術領域，涉及一種可變長染色體編碼的混合并行遺傳聚類算法。

背景技術

1、K-Means算法

傳統的K-Means算法是一種已知聚類類別數目的無監督學習算法。其基本思想為：在算法中指定類別數為K，對樣本進行聚類。聚類過程以隨機選定的K個聚類中心為基礎，對樣本按距離最小原則進行劃分，并迭代更新聚類中心，以使迭代過程向目標函數值最小的方向靠近，從而達到最優的聚類效果。

在K-Means算法中一般采用公式(1)作為目標函數來顯式地判斷算法的結束與否。

其中DIS(X_i,Z_j)由公式(2)進行計算，K為聚類數，X_i為屬于類C_j的聚類樣本，Z_j為聚類中心。目標函數的意義實際上就是各類樣本到其中心點距離的總和。

傳統K-Means算法的具體步驟如下：

①給定大小為n的數據集X；

②選取K個初始聚類中心Z_j(j＝1,2,…,K)；

③以Z_j為參照點對數據集X按最鄰近法則進行劃分，將各樣 本劃分到不同的簇；

若X_i，Z_j滿足公式(3)，則X_i屬于第j類。

④根據公式(4)調整聚類中心；

其中z_ij表示第i號中心的第j維的值，n_i為類C_i中樣本點個數，X_k為屬于類C_i的樣本點。x_kj為樣本點X_k的第j維的值。

⑤按公式(1)計算目標函數的值J；

⑥如果J的值在多輪迭代中變化不大，則算法結束，否則轉③。

K-Means聚類算法是數據挖掘及知識發現領域中的一種重要方法，它具有算法簡單、局部搜索能力強且收斂速度快的特點。正是這些特點決定了K-Means算法非常適合于高維向量的聚類問題。

然而在使用K-means算法的過程當中，如果聚類數和初始聚類中心的選取不同，都將對聚類結果產生較大影響。

為了解決K-Means算法對初始聚類中心敏感的問題，人們尋求多種方法對K-Means算法進行改進，這些改進主要集中在初始中心的選擇方法以及對聚類結構的合理利用。

在K-Means算法中，初始聚類中心是隨機選擇的，這種選擇方法往往使同一類別中的樣本被強行地作為不同類別的聚類中心，這樣將使得聚類劃分發生偏離。為了合理選擇初始聚類中心，研究人員進行了大量實驗和分析，采用各種方法對聚類中心進行優化選擇。其中最簡單的措施是隨機選取不同的初始值多次執行算法，然后選取最好的結果。也有學者提出將聚類均值點與聚類種子相分離的思想，在進行下一輪聚類種子計算時，采用簇中那 些與上一輪聚類種子相似度較大的數據，計算它們的均值點(幾何中心點)作為下一輪聚類的種子。另有學者提出了一種基于密度和對象方向的KADD改進算法，采取聚類對象分布密度方法確定初始聚類中心，然后根據對象的聚類方向來發現任意形狀的簇。

除此之外，也有學者通過對聚類模型的分析，發現聚類問題普遍具有一種統計特性，稱為聚類特性。利用聚類特性來表示聚類，可以保留更多的聚類信息，對于提高聚類質量有一定作用，而且聚類過程中的參數(如聚類中心、離差平方和以及聚類半徑等)可直接由聚類特性計算得出。多次取樣法就是一種采用聚類特性進行聚類劃分的方法。還有學者提出了一種典型的使用聚類特性的聚類算法CFK-Means算法。

雖然通過實驗可以驗證上述改進的K-Means算法對傳統K-Means算法的性能有了很大的提高，但總體上只是對K-Means算法進行了局部優化，仍然不能加強算法的全局搜索能力。

如果能將K-Means聚類算法和后面所要講到的并行遺傳算法相結合，必將對算法的全局優化能力產生巨大作用，同時能對聚類參數進行優化，使得算法性能大為提高。這些問題都是我們在后面的研究中所要解決的問題。

2、K-Means算法初始聚類中心的選擇

K-Means算法存在的最大問題是初始聚類中心的選擇問題，如果能正確地選取聚類中心，并對初始聚類中心進行優化，算法的精度將會大大提高。

目前初始聚類中心的選擇主要有如下幾種方法：