大數(shù)據(jù)挖掘中的K?means無監(jiān)督聚類算法的改進

吳海麗

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

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

中圖分類號： 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? 引? 言

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

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

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

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

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

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

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

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

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

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

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

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

2? 算法的改進

2.1? 改進思路

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

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

2.2? 算法的具體操作

2.2.1? 種群初始化

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

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

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

3） 實現(xiàn)種群[P]與[OP]的合并，規(guī)模設置為2[NP]。根據(jù)適應度函數(shù)大小實現(xiàn)排列，從中選擇[NP]規(guī)模的優(yōu)化個體構成算法初始種群。

2.2.2? 函數(shù)適應度設計

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

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

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

2.2.3? 算子選擇

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

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

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

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

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

2.2.5? 算法流程

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

輸出：最優(yōu)聚類中心與數(shù)量[9?11]。

算法描述如下：

1） 進化參數(shù)的設置。

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

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

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

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

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

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

8） 實現(xiàn)最優(yōu)聚類中心的輸出，并且實現(xiàn)聚類操作。

9） 聚類結果的輸出。

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

3? 算法仿真

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

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

4? 結? 語

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

參考文獻

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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