基于布谷鳥算法優化K_means聚類的缺失數據填充算法*

林楓 蔡延光 蔡顥 張麗

學術研究

基于布谷鳥算法優化K_means聚類的缺失數據填充算法*

林楓1蔡延光1蔡顥2張麗1

（1.廣東工業大學自動化學院，廣東 廣州 510006 2.奧爾堡大學健康科學與工程系，丹麥 奧爾堡 9920）

針對K_means聚類算法對初始參數較敏感且相對容易出現局部最優解的問題，提出基于布谷鳥算法優化的K_means聚類算法，并將優化后的K_means聚類算法與條件均值填充算法相結合，遞歸地填充缺失數據。實驗結果表明：與傳統算法相比，基于布谷鳥算法優化K_means聚類的缺失數據填充算法具有更好的效果。

缺失數據；填充；布谷鳥算法；K_means算法

0　引言

數據集在收集與整理過程中，因各種不可控因素導致數據部分屬性值缺失，從而對數據質量造成較嚴重影響且降低數據挖掘效果[1-2]。因此，為提高數據集的分析效果，對其中缺失數據進行填充是至關重要的。常用的缺失數據填充方法有回歸插補法、聚類插補法、人工神經網絡插補法等。

回歸分析是一種基于變量間關系的預測性分析方法，廣泛應用于各個領域[2]。回歸插補法的基本思想是通過數據中的缺失屬性與其余屬性的關系建立回歸模型，再利用回歸模型預測缺失屬性的值并進行填充。卜范玉等利用CFS聚類算法對不完整數據集進行聚類，對降噪自動編碼模型進行改進，并根據聚類結果，利用改進的自動編碼模型對缺失數據進行填充[3]。戴明鋒等利用logistic回歸算法對數據中的缺失屬性值進行填充并取得較好成效[4]。李建更等為解決基因譜的數據缺失問題，提出基于雙向核加權回歸估計算法，取得較好缺失值填充效果[5]。

在數據挖掘領域，聚類算法是對數據進行分類統計分析的一種經典算法。它通過度量數據間的相似性對數據進行分類劃分，使相同類的數據聚集成一類[6]。聚類算法廣泛應用于缺失值填充問題，并取得較好效果。史倩玉等為解決不完全數據集的缺失值填充問題，提出一種新的集成聚類算法，該算法規避了傳統單一填充算法造成的不良影響并取得較好填充效果[7]。針對傳統聚類算法無法準確度量缺失數據間相似性的問題，鄭奇斌等將PatDist-PCM與PatClu-PCM相結合，提出一種改進的模糊聚類算法，有效提高了不完全數據集聚類的準確度[8]。

人工神經網絡是基于對人腦神經元網絡進行抽象處理而建立的一種計算模型[9-12]。神經網絡在處理隨機數據或復雜數據時具有明顯優勢，廣泛應用于復雜數據集的缺失值填充。毛玫靜等針對不完備信息系統的缺失數據填補精度不高的問題，以水產養殖預警信息系統為背景，提出一種基于屬性相關度的缺失數據填補算法，該方法在填補準確度和時間性能上有明顯提高[13]。姚休義等采用非線性神經網絡對缺失數據進行重構并取得較好效果[14]。李武翰等為恢復缺失的音頻數據，提出一種基于神經網絡的缺失值預測算法，該算法不僅具有較高的處理效率還具有較高的處理精度[15]。

以上3種數據預處理方法在處理數據缺失問題上都是行之有效的。與其他預處理方法相比，聚類插補法具有實現簡單、處理效率高、準確度高的特點。為此，本文采用聚類算法對數據集中的缺失數據進行填充處理。

1　基于布谷鳥算法優化的K_means聚類算法

K_means聚類算法具有實現簡單、運行效率高、聚類效果精確等特點。但聚類效果對初始聚類中心的選擇相對比較敏感，如果選擇不恰當容易出現局部最優問題。布谷鳥算法能夠較好地平衡局部搜索與全局搜索的能力且不易出現局部最優特性。針對K_means聚類算法的缺點，本文將布谷鳥算法與K_means聚類算法融合，可有效避免出現局部最優的問題且提高尋優能力。

設數據集為，其中含有個數據樣本，每個數據樣本的維度為，聚類個數為，則數據樣本記為x= {x1,x2, ...,x}, (= 1, 2, ...,), (= 1, 2, ...,)；數據集記為= {1,2, ...,x}；聚類中心記為= {1,2, ...,w}；聚類結果記為= {1,2, ...,W}?；诓脊萨B算法優化的K_means聚類算法具體步驟如下：

1）初始化參數，聚類個數為，最大迭代次數為，布谷鳥的巢寄行為被寄主發現的概率為且∈[0,1]，n,w適應度函數()為

2）從數據集內隨機選取個數據樣本作為初始鳥巢位置；

3）根據當前鳥巢位置，按照距離最小準則將數據集劃分為個類，劃分完成后重新計算每個鳥巢位置的適應度函數()的值；

4）根據式(2)對鳥巢位置進行更新操作，計算更新后的鳥巢位置的適應度函數()的值并與上代鳥巢位置對比，取較優鳥巢；

式中，表示步長控制量，且一般= 1；?代表點乘運算；()表示隨機搜索路徑，且()服從Levy分布；為萊維飛行得出的隨機步長；

5）生成一個隨機數，若>，未對值進行設置則隨機地對鳥巢位置進行改變；若≤，則跳轉至步驟7）；

6）對更新后的鳥巢位置重新進行聚類劃分操作，根據式(3)重新計算聚類中心，計算每個鳥巢位置的適應度函數()的值并與當前鳥巢位置比較，取較優鳥巢；

7）若達到最大迭代次數或適應度函數收斂，則輸出最終結果；否則跳轉至步驟4）。

基于布谷鳥算法優化的K_means聚類算法流程如圖1所示。

圖1　基于布谷鳥算法優化的K_means聚類算法流程圖

2　優化后K_means聚類的缺失數據填充算法

2.1　缺失值填充策略

基于聚類的傳統填充算法是通過在聚類結果的同類簇數據中求取最近鄰點來插補缺失數據，但當數據的缺失屬性過多時，聚類算法就無法度量缺失樣本之間的相似性。因此，本文將優化后的K_means聚類算法與條件均值填充算法相結合，采用遞歸填充的策略，提出基于優化后K_means聚類的遞歸填充算法。該算法主要思想是：首先，利用總體的分組屬性均值對不完全數據集中的缺失數據進行預填充形成初始完全數據集；然后，對初始完全數據集進行聚類，利用聚類結果中的屬性均值更新缺失樣本中的屬性值，多次進行直至滿足終止條件。

2.1.1 初始預填充方法

在對不完全數據集進行聚類前，需對不完全數據集中的缺失數據進行預填充，形成初始完全數據集。總體均值填充算法使用總體中完全樣本的屬性均值對缺失數據進行填充，但該方法降低了樣本的變異程度和各屬性之間的關聯程度，導致原始樣本分布被嚴重扭曲。為此，本文采用條件均值填充算法對不完全數據集的缺失屬性值進行預填充。首先，將不完全數據集隨機地分成若干組；然后，計算各組中完全數據的屬性均值；最后，利用組內完全樣本的屬性均值填充缺失數據的屬性值。相比于總體均值填充算法，條件均值填充算法可提高對總體樣本變異程度的預估，改善各屬性之間的關聯程度。

設不完全數據集，其中包含了個數據樣本，每個樣本由個條件屬性組成，每個樣本記為D= {x1,x2, ...,x}。將不完全數據集隨機地分為組，則組內樣本缺失值的填充公式為

2.1.2 基于聚類的遞歸填充方法

采用優化后的K_means聚類算法對初始完全數據集進行聚類，得到聚類中心= {1,2, ...,w}和聚類結果= {1,2, ...,W}，利用聚類結果中的屬性均值更新缺失樣本中的屬性值。

2.1.3 遞歸終止條件

利用聚類結果中的屬性均值更新缺失樣本中的屬性值，靈活地運用了聚類算法自動求取近鄰的功能。通過多次迭代，對缺失數據的屬性值進行多次填充，可獲得更好的填充效果。本文采用前后兩次填充值的差值Δ作為遞歸終止條件，Δ的計算公式為

當Δ小于設定的閾值或算法達到最大迭代次數時，遞歸終止，輸出填充后的完全數據集。

2.2　填充算法流程

優化后K_means聚類的缺失數據填充算法具體步驟如下：

1）初始化參數，聚類個數為，輸入不完全數據集；

5）計算Δ值，若小于閾值或者算法達到最大迭代次數，則填充結束并輸出最終結果；否則跳轉至步驟3）。

優化后K_means聚類的缺失數據填充算法流程如圖2所示。

圖2　優化后K_means聚類的缺失數據填充算法

3　實驗與分析

3.1　實驗設計

為有效評估算法對缺失值的填充效果，本文在實驗過程中取出數據集中的完全數據，并采用人工方式隨機抹去其中真實的屬性值，按5種不同的缺失比率（5%，10%，20%，30%，40%）分別產生10個缺失比率相等但缺失屬性不同的數據集。為驗證本文提出的基于布谷鳥算法優化K_means聚類的缺失數據填充算法（CKMI）的有效性，將該算法與KNN填充算法、EN填充算法、基于K-means聚類的缺失數據填充算法（KMI）進行實驗比較，交叉驗證10次并取其平均值作為最終的實驗結果。

由于數據集中同時含有連續型屬性與離散型屬性，為正確地評估算法對缺失屬性的填充效果，本文對連續型屬性與離散型屬性的填充效果分別采用基于距離的平方根誤差與錯誤分類度進行評估，并以與的和作為總誤差進行分析。

基于距離的均方根誤差的計算公式為

式中，n表示含連續型缺失屬性值的數據樣本數量；xguess表示缺失屬性的填充值；xtrue表示屬性的真實值。

值越小，表明填充誤差越小，連續型缺失值的填充效果越好。

錯誤分類度的計算公式為

值越小，表明填充誤差越小，離散型缺失值的填充效果越好。

3.2　結果分析

實驗結果如圖3所示。

圖3　4種算法對缺失屬性值的填充結果

由圖3可知：4種算法的誤差均值隨缺失比率的上升而逐漸增大，但CKMI算法一直保持著較低的誤差水平，說明CKMI算法相比于其他算法具有更好的處理效果；當缺失比率上升到一定程度時KMI算法的誤差突然增大，說明傳統K_means聚類算法無法準確地度量缺失比率較高數據間的相似性，從側面證明本文所提出的基于布谷鳥算法優化K_means聚類算法的有效性。

綜上所述，本文提出的基于布谷鳥算法優化K_means聚類的缺失數據填充算法相比于傳統的處理算法具有更好的性能。

4　總結

本文采用K_means聚類算法對數據集中的缺失數據進行填充。針對K_means聚類算法對初始參數較敏感且相對容易出現局部最優解的問題，采用布谷鳥算法對K_means聚類算法進行優化，提出基于布谷鳥算法優化的K_means聚類算法。為解決聚類算法無法度量缺失數據間的相似性，提高缺失數據的填充效果，本文提出基于布谷鳥算法優化K_means聚類的缺失數據填充算法，運用條件均值填充算法與優化后的K_means聚類算法相結合，遞歸地填充缺失數據。實驗結果表明：基于布谷鳥算法優化K_means聚類算法的聚類效果有所提升，且與傳統缺失數據填充算法相比，基于布谷鳥算法優化的K_means聚類的缺失數據填充算法具有更好的效果。

[1] 王妍,王鳳桐,王俊陸,等.基于泛化中心聚類的不完備數據集填補方法[J].小型微型計算機系統,2017,38(09): 2017-2021.

[2] AYDOGMUS Ozgur. Phase transitions in a Logistic metapopulation model with nonlocal interactions[J]. Bulletin of Mathematical Biology, 2018, 80(1): 228-253.

[3] 卜范玉,陳志奎,張清辰.基于聚類和自動編碼機的缺失數據填充算法[J].計算機工程與應用,2015,51(18):13-17.

[4] 戴明鋒,金勇進,查奇芬,等.二分類Logistic回歸插補法及其應用[J].數學的實踐與認識,2013,43(21):162-167.

[5] 李建更,郭慶雷,賀益恒.時序基因表達缺失值的加權雙向回歸估計算法[J].數據采集與處理,2013,28(02):136-140.

[6] JIA Cangzhi, ZUO Yun, ZOU Quan. O-GlcNAcPRED-II: an integrated classification algorithm for identifying O-GlcNAcylation sites based on fuzzy undersampling and a K-means PCA oversampling technique[J]. Bioinformatics, 2018, 34(12): 2029-2036.

[7] 史倩玉,梁吉業,趙興旺.一種不完備混合數據集成聚類算法[J].計算機研究與發展,2016,53(09):1979-1989.

[8] 鄭奇斌,刁興春,曹建軍.結合缺失模式的不完整數據模糊聚類[J].計算機科學,2017,44(12):58-63.

[9] PRIYANKA Singh, Pragya Dwivedi. Integration of new evolutionary approach with artificial neural network for solving short term load forecast problem[J]. Applied Energy, 2018, 217:537-549.

[10] QIAN Jianping, ZHAO Jianping, LIU Yi, et al. Simulation and prediction of monthly accumulated runoff, based on several neural network models under poor data availability[J]. Sciences in Cold and Arid Regions, 2018, 10(6): 468-481.

[11] 王玉哲,許志恒,何虎.仿生物型人工神經網絡的探索與實現[J].計算機工程與設計,2018, 39(4):1161-1166.

[12] MOCANU D C, MOCANU E, STONE P, et al. Scalable training of artificial neural networks with adaptive sparse connectivity inspired by network science[J]. Nature Communications, 2018, 9 (1): 2383.

[13] 毛玫靜,鄂旭,譚艷,等.基于屬性相關度的缺失數據填補算法研究[J].計算機工程與應用,2016,52(6):74-79.

[14] 姚休義,滕云田,楊冬梅,等.基于神經網絡的地磁觀測數據重構研究[J].地球物理學報,2018,61(06):2358-2368.

[15] 李武翰,魏東興,王建國,等.基于BP網絡和多抽樣率處理的缺失音頻信號恢復方法[J].大連理工大學學報,2004(5): 729-732.

Optimized of K_means Clustering Based on Cuckoo Algorithm for Missing Data Filling Algorithm

Lin Feng1Cai Yanguang1Cai Hao2Zhang Li1

(1. School of Automation, Guangdong University of Technology, Guangzhou, Guangdong 510006, China 2. Department of Health Science and Technology, Aalborg University, Aalborg 9220, Denmark)

Aiming at the problem that K_means clustering algorithm is sensitive to initial parameters and relatively easy to appear local optimal solution, a K_means clustering algorithm based on cuckoo algorithm is proposed, and the optimized K_means clustering algorithm is combined with conditional mean filling algorithm. Recursively fill in missing data. The experimental results show that the missing data filling algorithm based on K_means clustering optimized by cuckoo algorithm has better effect than the traditional algorithm.

missing data; data filling; Cuckoo algorithm; K_means algorithm

國家自然科學基金（61074147）；廣東省自然科學基金（S2011010005059）；廣東省教育部產學研結合項目（2012B091000171，2011B090400460）；廣東省科技計劃項目（2012B050600028，2014B010118004，2016A050502060），廣州市花都區科技計劃項目（HD14ZD001），廣州市科技計劃項目（201604016055），廣州市天河區科技計劃項目（2018CX005）。

TP301 標志碼：A

1674-2605(2020)06-0003-06

10.3969/j.issn.1674-2605.2020.06.003

林楓，男，1993年生，碩士，主要研究方向：嵌入式系統及其應用。

蔡延光，男，1963年生，博士，教授，主要研究方向：網絡控制與優化、組合優化、智能優化、智能交通系統等。

蔡顥（通信作者），男，1987年生，博士，主要研究方向：大數據分析、智能信息處理。E-mail: howardbrutii@foxmail.com

張麗，女，1994年生，碩士，主要研究方向：物流運輸調度、大數據質量優化控制。