林楓 蔡延光 蔡顥 張麗

學術研究

基于布谷鳥算法優(yōu)化K_means聚類的缺失數(shù)據(jù)填充算法*

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

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

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

缺失數(shù)據(jù)；填充；布谷鳥算法；K_means算法

0　引言

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

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

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

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

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

1　基于布谷鳥算法優(yōu)化的K_means聚類算法

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

設數(shù)據(jù)集為，其中含有個數(shù)據(jù)樣本，每個數(shù)據(jù)樣本的維度為，聚類個數(shù)為，則數(shù)據(jù)樣本記為x= {x1,x2, ...,x}, (= 1, 2, ...,), (= 1, 2, ...,)；數(shù)據(jù)集記為= {1,2, ...,x}；聚類中心記為= {1,2, ...,w}；聚類結果記為= {1,2, ...,W}。基于布谷鳥算法優(yōu)化的K_means聚類算法具體步驟如下：

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

2）從數(shù)據(jù)集內(nèi)隨機選取個數(shù)據(jù)樣本作為初始鳥巢位置；

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

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

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

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

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

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

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

圖1　基于布谷鳥算法優(yōu)化的K_means聚類算法流程圖

2　優(yōu)化后K_means聚類的缺失數(shù)據(jù)填充算法

2.1　缺失值填充策略

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

2.1.1 初始預填充方法

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

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

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

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

2.1.3 遞歸終止條件

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

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

2.2　填充算法流程

優(yōu)化后K_means聚類的缺失數(shù)據(jù)填充算法具體步驟如下：

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

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

優(yōu)化后K_means聚類的缺失數(shù)據(jù)填充算法流程如圖2所示。

圖2　優(yōu)化后K_means聚類的缺失數(shù)據(jù)填充算法

3　實驗與分析

3.1　實驗設計

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

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

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

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

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

錯誤分類度的計算公式為

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

3.2　結果分析

實驗結果如圖3所示。

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

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

綜上所述，本文提出的基于布谷鳥算法優(yōu)化K_means聚類的缺失數(shù)據(jù)填充算法相比于傳統(tǒng)的處理算法具有更好的性能。

4　總結

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

[1] 王妍,王鳳桐,王俊陸,等.基于泛化中心聚類的不完備數(shù)據(jù)集填補方法[J].小型微型計算機系統(tǒng),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] 卜范玉,陳志奎,張清辰.基于聚類和自動編碼機的缺失數(shù)據(jù)填充算法[J].計算機工程與應用,2015,51(18):13-17.

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

[5] 李建更,郭慶雷,賀益恒.時序基因表達缺失值的加權雙向回歸估計算法[J].數(shù)據(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] 史倩玉,梁吉業(yè),趙興旺.一種不完備混合數(shù)據(jù)集成聚類算法[J].計算機研究與發(fā)展,2016,53(09):1979-1989.

[8] 鄭奇斌,刁興春,曹建軍.結合缺失模式的不完整數(shù)據(jù)模糊聚類[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īng)網(wǎng)絡的探索與實現(xiàn)[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] 毛玫靜,鄂旭,譚艷,等.基于屬性相關度的缺失數(shù)據(jù)填補算法研究[J].計算機工程與應用,2016,52(6):74-79.

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

[15] 李武翰,魏東興,王建國,等.基于BP網(wǎng)絡和多抽樣率處理的缺失音頻信號恢復方法[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）；廣東省教育部產(chǎn)學研結合項目（2012B091000171，2011B090400460）；廣東省科技計劃項目（2012B050600028，2014B010118004，2016A050502060），廣州市花都區(qū)科技計劃項目（HD14ZD001），廣州市科技計劃項目（201604016055），廣州市天河區(qū)科技計劃項目（2018CX005）。

TP301 標志碼：A

1674-2605(2020)06-0003-06

10.3969/j.issn.1674-2605.2020.06.003

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

蔡延光，男，1963年生，博士，教授，主要研究方向：網(wǎng)絡控制與優(yōu)化、組合優(yōu)化、智能優(yōu)化、智能交通系統(tǒng)等。

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

張麗，女，1994年生，碩士，主要研究方向：物流運輸調(diào)度、大數(shù)據(jù)質量優(yōu)化控制。