大數據挖掘中的K?means無監督聚類算法的改進

吳海麗

摘? 要： 針對K?means聚類算法簡單，并且收斂速度比較快的問題，提出基于大數據挖掘的K?means無監督聚類算法。此算法設置一定范圍，在迭代次數不斷動態增加中，交叉算法增加，從而使算法在迭代過程中實現全局搜索，再實現局部搜索，有助于平衡算法全局尋優及局部搜索能力，使算法收斂速度加快。對K?means聚類算法和標準差分進化算法進行分析，提出K?means聚類算法的改進，給出算法改進的步驟，利用實驗對算法進行仿真。通過仿真結果表示，此算法聚類效果良好，聚類劃分精度和穩定性高，還具有較高的穩定性。

關鍵詞： 大數據挖掘; 差分進化算法; K?means聚類算法; 全局尋優; 魯棒性; 收斂速度

中圖分類號： TN911.1?34; TP391? ? ? ? ? ? ? ? ? 文獻標識碼： A? ? ? ? ? ? ? ? ? ? 文章編號： 1004?373X（2020）19?0118?04

Abstract： In view that the K?means clustering algorithm is simple and its convergence speed is fast， an unsupervised K?means clustering algorithm based on big data mining is proposed. In the algorithm， a certain range is set， the crossover algorithm increases when the number of iterations increases dynamically， so that the algorithm can achieve global search and then local search in the iterative process. Therefore， it is helpful to balance the global optimization and local search ability of the algorithm， which accelerates the convergence speed of the algorithm. The K?means clustering algorithm and the standard differential evolution algorithm are analyzed. And then， the K?means clustering algorithm is improved and the steps of algorithm improvement are given. Finally， the algorithm is simulated in experiments. The simulation results show that the algorithm has good clustering effect， high clustering partition accuracy and stability.

Keywords： big data mining; differential evolution algorithm; K?means clustering algorithm; global optimization; robustness; convergence rate

0? 引? 言

優化的主要目的就是尋找最優方案，雖然目前常規優化方法中存在部分問題，尤其在面臨多峰、高維、函數結構復雜等問題時，求解精度和算法時間復雜度無法滿足設計需求，所以要更加系統地研究該問題。進化算法編程簡單，利用特殊進化測量能夠使種群質量得到提高，從而得到明確的算法尋優方向[1]。K?means聚類算法屬于常見聚類方法，使用較為廣泛，比如，對不同客戶群體購物習慣進行解析，實現客戶細分;對消費者不同需求特征進行分析，使產品市場按不同消費市場進行細分。因為傳統K?means算法對于聚類中心敏感，無法有效確定[K]值等問題，所以提出了K?means無監督聚類算法。

1? K?means聚類算法和標準差分進化算法

K?means均值聚類思想是以聚合中心距離與數據對象作為基礎，將數據對象劃分成為和距離比較近的集合。[K]屬于K?means算法參數，使[m]個對象集合朝著最近子集進行劃分，對比相同子集中的對象，子集數據對象的不同也存在一定的差別[2]。此算法步驟為：

1） 通過樣本集選擇[k]條數據樣本作為初始[k]個集合中心;

2） 依據最近鄰法則，將數據樣本被劃分到與其相互接近的集合;

3） 計算全新的類簇中心，可利用不同集合樣本數據均值計算得出;

4） 不改變類簇中心，說明算法終止，到最終的結果進行返回;否則，跳至步驟2）進行返回計算。

此聚類算法中的主要問題就是對算法初始類簇中心進行選擇，如果初始劃分與全局最優劃分出現問題，那么就會導致算法逐漸陷入局部最優。

交叉操作、變異操作為標準差分進化算法中的核心，其定義如下。

變異操作：變異操作中全新的個體是通過群體單個或者多個線性進行計算得出，差分進化算法中的變異機制比較多，以下公式中使用大量的變異策略。

交叉操作：利用現代個體[ci]中的分量和目標個體進行轉變，實現測試個體[ti]的生成。二項交叉與指數交叉為主要的交叉方式，在執行二項交叉過程中，是將每條染色體中的分量作為基礎，從而實現0～1之間隨機數量[r]的生成。假如[r]比CR小，目標個體相應分量進行接收;否則，將目前個體分量進行保留[3?4]。

選擇操作：利用貪心實現選擇差分進化（DE）標準，目前[ci]對比測試個體[ti]，利用更好個體實現下一代搜索。

2? 算法的改進

2.1? 改進思路

控制參數對于DE算法的影響比較大，目前學術界對于參數研究并沒有系統性結論，對DE算法在現實中的使用具有一定的影響。國內外相關研究人員提出了多種集成算法模型及框架，此算法具備魯棒性與普適性，并且效果良好。目前，也出現了基于靜態知識的DE集成算法，靜態知識也稱為經驗知識，主要表示知識初級形態。

使用新變異算法的改進：相關研究人員受到PSO優化算法的影響，通過兩個極值更新個體位置與速度的啟發，提出全新變異因子，此因子通過兩個位置信息：局部鄰域良好個體位置信息、全局最優個體位置信息得到。算法為：

2.2? 算法的具體操作

2.2.1? 種群初始化

因為DE算法在進化初期缺少相應的經驗知識，只能夠在可行域內隨機出現初始種群，從而降低了算法進化初期的收斂速度。如果初始種群個體到全局最優距離比較近，能夠有效加快算法收斂速度。所以為了使算法在進化初期的收斂速度得到提高，通過反向學習方法及混沌搜索相互結合的方式實現初始種群的產生，使初始種群質量得到提高。先使用Logistis映射生成混沌序列，使算法初始隨機數質量得到提高[4?5]，具體描述為：

式中：[xi]指混沌序列變量在第[i]次迭代過程中的值;[v]為變量控制常數，在其取值范圍為[3.56，4.0]時，[xi]為混沌變量，這時系統在完全混沌的狀態中，混沌序列不會重復。算法根據反向學習方法，能夠實現所有混沌序列個體的反向個體生成，之后對反向個體及混沌序列種群進行合并，并且實現以上種群全部個體，根據適應度函數值大小進行排列，最后使用其中相應規模比較優的個體構成初始種群。

混沌搜索的反向學習過程為：

3） 實現種群[P]與[OP]的合并，規模設置為2[NP]。根據適應度函數大小實現排列，從中選擇[NP]規模的優化個體構成算法初始種群。

2.2.2? 函數適應度設計

利用適應度函數、遺傳算法能夠評價種群個體適應度，并且區分種群個體的優劣程序。存活概率和個體適應度兩者具有正比的關系，可提高適應度和存活的可能性。K?means聚類算法指的是目標函數[G]尋找過程中的最小劃分[5?7]。

在算法操作過程中，劃分染色體編碼的初始種群，對不同聚類點到聚類中心進行聚類計算，使其成為目標函數[G]。通過目標函數對聚類劃分效果進行判斷，目標函數[G]越小，聚類效果越好。

利用標準DE算法搜索目標函數解空間，以此得到目標函數最小值。那么，本文以目標函數實現適應度函數的創建：

2.2.3? 算子選擇

通過模仿生物界實現遺傳算法，在選擇操作時使生物界優勝劣汰的規則得到滿足。操作選擇將種群個體適應度值作為基礎，利用父代個體對個體進行選擇，遺傳到下一代。算法設計與概率選擇具有密切的關系，個體[xi]的選擇概率為：

2.2.4? 自適應交叉與變異算子

通過選擇變異概率和交叉概率，能夠有效實現遺傳操作，對遺傳算法計算結果造成影響。對于交叉算子來說，隨著交叉概率不斷增加的過程，就會提高個體生成的速度，在交叉概率比較小時，就會降低遺傳搜索的速度;對于變異算子來說，個體在小變異概率中并不新穎，在大變異概率時，會失去遺傳算法的效果，朝著隨機搜索算法轉變。

對于上述變異操作與交叉操作存在的問題，本文利用自適應交叉實現操作。[Pc]與[Pm]能夠以不同情況實現自我調節，公式為：

式中：[fmax]指群體中最大適應度值;[favg]指群體平均適應度值;[f]指交叉的兩個個體中較大的適應度值;[f]指變異個體適應度值;[k1]，[k2]，[k3]，[k4]取（0，1）區間的值。假如沒有定義[k1]，[k2]，[k3]，[k4]的根據，可以初始確定四者的值，利用[Pc]與[Pm]對比相同優化目標下的進化代數，對應進化代數比較少的[Pc]和[Pm]是較優的，那么對應[k1]，[k2]，[k3]，[k4]也比較合理。

2.2.5? 算法流程

輸入：輸入內容主要包括聚類樣本集、種群大小、最大迭代次數、自適應交叉與變異系數。

輸出：最優聚類中心與數量[9?11]。

算法描述如下：

1） 進化參數的設置。

2） 通過染色體的編碼方案生成初始種群。

3） 對個體適應度值進行計算。

4） 對最好個體計算，對最好適應度和平均適應度進行記錄。

5） 進行交叉、變異、選擇等操作。

6） 計算個體適應度，尋找最大適應度的個體，替代上一次最大的適應度個體。

7） 對是否為最大迭代次數進行判斷，假如是，就進行下一步;否則，回到步驟5）。

8） 實現最優聚類中心的輸出，并且實現聚類操作。

9） 聚類結果的輸出。

算法的具體操作流程如圖1所示。

3? 算法仿真

為了對算法的有效性進行驗證，本文使用常用數據集進行實驗。表1給出了數據集名稱、數據對象數量與屬性個數。為了保證對比的有效性，設置改進K?means算法內容為：相關ACDE函數保留原本參數設置，種群大小[NP]設置為100，最大迭代次數[Imax]設置為[11?13]200，閾值參數為3。均值與方差對比結果見表2。

本文使用DB指標作為本文算法中函數的優化選擇，將20次最終DB值均值（mean）與方差（std）作為評價標準，并且通過聚類數均值和方差對算法聚類性能進行評價。通過表2可以看出，本文算法均值與方差比較小，并且接近于數據集實際種類，所以，不管是聚類效果或者穩定性，本文算法更好。另外，本文算法誤分率也比較小，表示本文算法的聚類劃分精度要高[13?15]。

4? 結? 語

在本文研究過程中基于DE算法實現動態交叉算法的設計，有效結合K?means算法和遺傳算法，能夠使收斂速度得到提高。通過實驗結果可知，本文算法聚類效果良好，并且聚類劃分精度較高，還具有較高的穩定性，提高了搜索效果。

參考文獻

[1] 王勇臻，陳燕，張金松.一種改進的求解聚類問題的差分進化算法[J].計算機應用研究，2016，33（9）：2630?2633.

[2] 申彥，朱玉全.CMP上基于數據集劃分的K?means多核優化算法[J].智能系統學報，2015，15（4）：607?614.

[3] 胡先兵，趙國慶.引入時頻聚集交叉項干擾抑制的大數據聚類算法[J].計算機科學，2016，43（4）：197?201.

[4] 王雪梅，李曉峰，高巍巍.一種改進的K?Means聚類算法的研究[J].計算機與數字工程，2013，41（11）：1717?1719.

[5] 胡春華.基于自適應差分進化算法擬合圓的樹干胸徑測量方法[J].農業機械學報，2018，49（9）：183?188.

[6] 劉莉莉，曹寶香.基于差分進化算法的K?Means算法改進[J].計算機技術與發展，2015，21（10）：88?92.

[7] 劉飛，唐雅娟，劉瑤.K?means聚類算法中聚類個數的方法研究[J].電子設計工程，2017，25（15）：9?13.

[8] 李運娣，文政穎，于海鵬.基于k?means算法和相關反饋信息的圖像檢索方法[J].福建電腦，2015（5）：19?20.

[9] 吳雅琴，王曉東.大數據挖掘中的混合差分進化K?Means無監督聚類算法[J].重慶理工大學學報（自然科學），2019，15（5）：107?112.

[10] 王鳳領.一種改進差分進化的自動聚類算法研究[J].數學的實踐與認識，2018，48（21）：187?194.

[11] 王明威，萬幼川，高賢君，等.紋理影像特征選擇及K?means聚類優化方法[J].國防科技大學學報，2017，39（6）：152?159.

[12] 樊一康，劉建偉.支持差分隱私保護及離群點消除的并行K?means算法[J].計算機應用研究，2019，15（6）：1776?1781.

[13] 周艷平，蔡素，李金鵬.一種粒子群和改進自適應差分進化混合算法及在生產調度中的應用[J].計算機測量與控制，2019，27（8）：227?230.

[14] 宋鑫宏，張樂，方光輝.基于Voronoi盲區的差分進化WSN部署算法[J].軟件導刊，2017，16（4）：59?61.

[15] 胡闖，楊庚，白云璐.面向差分隱私保護的聚類算法[J].計算機科學，2019，46（2）：120?126.