梁秉毅 蔡延光 蔡顥 戚遠(yuǎn)航 黃何列 Ole Hejlesen

?

基于優(yōu)化決策樹(shù)和EM的缺失數(shù)據(jù)填充算法*

梁秉毅1蔡延光2蔡顥2戚遠(yuǎn)航2黃何列2Ole Hejlesen3

（1.廣州市第三公共汽車(chē)公司 2.廣東工業(yè)大學(xué)自動(dòng)化學(xué)院 3.奧爾堡大學(xué)健康科學(xué)與工程系）

針對(duì)大數(shù)據(jù)管理與應(yīng)用中數(shù)據(jù)缺失的問(wèn)題，提出一種基于優(yōu)化決策樹(shù)和EM的缺失數(shù)據(jù)填充算法對(duì)多屬性缺失數(shù)值型數(shù)據(jù)進(jìn)行填充。為解決決策樹(shù)過(guò)分?jǐn)M合問(wèn)題，該算法采用基于精英策略的自適應(yīng)遺傳算法優(yōu)化后的決策樹(shù)對(duì)數(shù)據(jù)進(jìn)行分類(lèi)，再結(jié)合EM算法實(shí)現(xiàn)數(shù)值型數(shù)據(jù)的填充。仿真結(jié)果表明：對(duì)比優(yōu)化前的決策樹(shù)算法，優(yōu)化后的決策樹(shù)分類(lèi)精度更高，平均填充耗時(shí)更少。

數(shù)據(jù)填充；決策樹(shù)；EM算法；遺傳算法

0　引言

數(shù)據(jù)缺失是數(shù)據(jù)管理中經(jīng)常面臨的問(wèn)題，含有缺失數(shù)據(jù)的多變量數(shù)據(jù)無(wú)法在絕大多數(shù)的統(tǒng)計(jì)模型中直接分析。當(dāng)數(shù)據(jù)庫(kù)中出現(xiàn)缺失數(shù)據(jù)時(shí)，一般采用數(shù)據(jù)刪除或數(shù)據(jù)填充的方法。如果缺失數(shù)據(jù)較少，可直接刪除有缺失的記錄，但缺失數(shù)據(jù)較多時(shí)，刪除大量數(shù)據(jù)會(huì)給研究結(jié)果帶來(lái)一定的誤差。因此，數(shù)據(jù)填充是當(dāng)前解決數(shù)據(jù)缺失的主要方法。

近年來(lái)，許多學(xué)者在數(shù)據(jù)填充領(lǐng)域進(jìn)行了深入的研究。李宏等提出一種基于貝葉斯網(wǎng)絡(luò)和期望最大值法的缺失數(shù)據(jù)填充算法[1]；武森等提出不完備數(shù)據(jù)聚類(lèi)的缺失數(shù)據(jù)填補(bǔ)方法，并以不完備數(shù)據(jù)聚類(lèi)的結(jié)果為基礎(chǔ)進(jìn)行缺失數(shù)據(jù)的填補(bǔ)[2]；張嬋提出一種基于支持向量機(jī)和回歸填充法的缺失數(shù)據(jù)填充算法[3]；袁景凌等提出一種基于完備相容類(lèi)的不完備大數(shù)據(jù)填補(bǔ)算法、一種基于離散弱相關(guān)的決策森林并行分類(lèi)算法和一種增量更新決策森林的算法[4]；李忠波等提出一種新的樸素貝葉斯分類(lèi)器進(jìn)行數(shù)據(jù)填充[5]；Amiri M采用模糊粗糙集進(jìn)行數(shù)據(jù)填充[6]；Turrado C C提出一種混合算法解決數(shù)據(jù)填充問(wèn)題，并把該算法應(yīng)用在相關(guān)的電力數(shù)據(jù)中[7]。但這些數(shù)據(jù)填充算法普遍存在分類(lèi)精度低、填充耗時(shí)長(zhǎng)等問(wèn)題。

因此，本文提出了一種基于優(yōu)化決策樹(shù)和EM的缺失數(shù)據(jù)填充算法，以基于精英策略的自適應(yīng)遺傳算法優(yōu)化后的決策樹(shù)和EM算法相結(jié)合的方式，解決多屬性數(shù)值型數(shù)據(jù)缺失的問(wèn)題，提高數(shù)據(jù)填充精度和降低數(shù)據(jù)填充耗時(shí)。

1　優(yōu)化決策樹(shù)

1.1　決策樹(shù)

決策樹(shù)算法是一種典型的分類(lèi)算法，構(gòu)建決策樹(shù)的思想與貪婪算法類(lèi)似，采用自頂向下遞歸的方式[8]。先對(duì)原始數(shù)據(jù)進(jìn)行處理，得出觀察樣本；再?gòu)挠?xùn)練集和它們相關(guān)聯(lián)的類(lèi)標(biāo)號(hào)生成可讀的規(guī)則和決策樹(shù)。隨著樹(shù)的構(gòu)建，訓(xùn)練集遞歸地劃分成較小的子集。決策樹(shù)構(gòu)建分為5個(gè)步驟。

步驟1：采集組數(shù)據(jù)，作為建立決策樹(shù)分類(lèi)器的訓(xùn)練數(shù)據(jù)集。

步驟2：所有記錄看作一個(gè)結(jié)點(diǎn)，代表訓(xùn)練樣本的單個(gè)結(jié)點(diǎn)開(kāi)始。

步驟3：遍歷每個(gè)變量的每一種分割方式，找到最好的分割點(diǎn)。如果樣本都在同一個(gè)類(lèi)，則該結(jié)點(diǎn)成為樹(shù)葉，并用該類(lèi)標(biāo)記；否則算法選擇最有分類(lèi)能力的屬性作為決策樹(shù)的當(dāng)前結(jié)點(diǎn)。在每次需要分裂時(shí)，計(jì)算訓(xùn)練元組每個(gè)屬性的增益率gain，然后選擇增益率最大的屬性進(jìn)行分裂。

訓(xùn)練元組按屬性進(jìn)行劃分信息增益gain()具體描述為

其中，為訓(xùn)練元組的信息量；D為第個(gè)類(lèi)別分類(lèi)的信息量；p為第個(gè)類(lèi)別在分類(lèi)元組D中出現(xiàn)的概率；p為第個(gè)類(lèi)別在訓(xùn)練元組中出現(xiàn)的概率。

步驟4：分割成2個(gè)結(jié)點(diǎn)1和2。

步驟5：如果滿(mǎn)足停止條件（剩余訓(xùn)練數(shù)據(jù)不可以用來(lái)進(jìn)一步劃分屬性），決策樹(shù)停止分類(lèi)；否則轉(zhuǎn)步驟3。

1.2　決策樹(shù)的剪枝優(yōu)化

在決策樹(shù)構(gòu)建時(shí)，決策樹(shù)反映的是訓(xùn)練數(shù)據(jù)中的分類(lèi)，而訓(xùn)練數(shù)據(jù)與真實(shí)情況是有一定差距的，不一定能真實(shí)反映數(shù)據(jù)的分類(lèi)，可能出現(xiàn)過(guò)度擬合的問(wèn)題。過(guò)度擬合會(huì)導(dǎo)致決策樹(shù)分類(lèi)精度不高，決策時(shí)間變長(zhǎng)等情況。因此，本文對(duì)由訓(xùn)練數(shù)據(jù)生成的決策樹(shù)進(jìn)行剪枝，剪掉不可靠的分支之后，決策樹(shù)變得更小、更簡(jiǎn)單，不僅可以提高分類(lèi)精度，還可以縮短分類(lèi)決策時(shí)間。本文采用后剪枝的方式對(duì)決策樹(shù)進(jìn)行修剪。

后剪枝的基本思想是建立測(cè)試數(shù)據(jù)集，對(duì)決策樹(shù)采取統(tǒng)計(jì)度量的方式把最不可靠的分支剪掉，通過(guò)刪除決策樹(shù)的分支，用樹(shù)葉代替修剪后的子樹(shù)，類(lèi)標(biāo)號(hào)為子樹(shù)中最頻繁的類(lèi)標(biāo)記[8]。一般情況下，測(cè)試集的異常值影響決策樹(shù)評(píng)估的結(jié)果，需要先對(duì)異常數(shù)據(jù)進(jìn)行隔離，保留測(cè)試集有用的部分。決策樹(shù)后剪枝方法的基本步驟如下：

步驟1：設(shè)訓(xùn)練集生成的決策樹(shù)表示為，建立測(cè)試集以評(píng)估決策樹(shù)的分類(lèi)效果，建立評(píng)價(jià)分類(lèi)效果的標(biāo)準(zhǔn)；

步驟2：用測(cè)試集中的觀察集對(duì)決策樹(shù)進(jìn)行測(cè)試，評(píng)估決策樹(shù)的性能，得出分類(lèi)情況，并以此評(píng)估原決策樹(shù)的錯(cuò)誤率；

步驟3：將影響決策樹(shù)質(zhì)量的分支予以修剪，并用子葉代替。

1.3 決策樹(shù)的染色體編碼

遺傳算法是一種基于生物進(jìn)化的參數(shù)優(yōu)化算法，基本思想是先對(duì)優(yōu)化對(duì)象進(jìn)行二進(jìn)制編碼，然后經(jīng)過(guò)一系列的選擇、交叉和變異操作，在滿(mǎn)足適應(yīng)度函數(shù)的條件或達(dá)到最大迭代次數(shù)后，獲得近似的最優(yōu)解[9]。從結(jié)構(gòu)上看，決策樹(shù)包含若干結(jié)點(diǎn)，結(jié)點(diǎn)與結(jié)點(diǎn)之間由樹(shù)枝連接，可以利用決策樹(shù)這種獨(dú)特的結(jié)構(gòu)進(jìn)行二進(jìn)制編碼。結(jié)合遺傳算法的特點(diǎn)，對(duì)決策樹(shù)進(jìn)行剪枝優(yōu)化操作，以降低決策樹(shù)的規(guī)模。

決策樹(shù)包含若干個(gè)結(jié)點(diǎn)，樣例決策樹(shù)示意圖如圖1所示。所有結(jié)點(diǎn)按照自頂向下、先左后右的方式進(jìn)行編號(hào)，編號(hào)為A，B，C，D，…，如此類(lèi)推；然后對(duì)結(jié)點(diǎn)賦予二進(jìn)制數(shù)值，數(shù)值1表示結(jié)點(diǎn)存在，數(shù)值0表示結(jié)點(diǎn)不存在；最后二進(jìn)制編碼按結(jié)點(diǎn)編號(hào)排列。圖1中5號(hào)分支將被裁剪，即E結(jié)點(diǎn)和F結(jié)點(diǎn)之間的分支消失，在二進(jìn)制編碼中表示F結(jié)點(diǎn)不存在。

圖1　樣例決策樹(shù)示意圖

樣例決策樹(shù)共有6條分支，初始樣例決策樹(shù)的染色體二進(jìn)制編碼可以表示為1111111。5號(hào)分支被裁剪后，樣例決策樹(shù)的染色體二進(jìn)制編碼將變?yōu)?111101。樣例決策樹(shù)修剪前和修剪后的染色體數(shù)值變化如表1所示。

表1　樣例決策樹(shù)修剪前后的染色體數(shù)值變化表

1.4 適應(yīng)度函數(shù)

為在優(yōu)化后的決策樹(shù)集合里挑選出最優(yōu)決策樹(shù)作為缺失數(shù)據(jù)的分類(lèi)器，需要建立衡量決策樹(shù)性能的標(biāo)準(zhǔn)?？紤]到建立決策樹(shù)的目的是對(duì)缺失數(shù)據(jù)進(jìn)行屬性分類(lèi)，本文采用決策樹(shù)的分類(lèi)精度作為衡量決策樹(shù)性能的指標(biāo)。

1.5　交叉運(yùn)算和變異運(yùn)算

為使遺傳個(gè)體得到更好的優(yōu)化，提高個(gè)體的適應(yīng)度，可以用交叉和變異的方式進(jìn)行染色體編碼的改造。本文主要采用交叉和變異2種遺傳運(yùn)算產(chǎn)生后繼染色體。

1）交叉運(yùn)算

交叉運(yùn)算后的染色體具體描述為

2）變異運(yùn)算

變異運(yùn)算是對(duì)染色體中任意的一位編碼進(jìn)行取反，實(shí)現(xiàn)染色體的變異。

1.6　自適應(yīng)策略

交叉和變異操作的概率會(huì)影響遺傳算法執(zhí)行的過(guò)程，交叉率P和變異率P過(guò)小或過(guò)大都會(huì)影響收斂速度。遺傳參數(shù)自適應(yīng)策略的基本思想是：對(duì)于適應(yīng)度低于平均水平的種群，加強(qiáng)交叉和變異操作，加快適應(yīng)度低的種群完成進(jìn)化速度；對(duì)于適應(yīng)度高的種群，適當(dāng)減少交叉和變異操作，以保留較優(yōu)的種群。通過(guò)式(5)自動(dòng)改變遺傳算法的交叉率P，通過(guò)式(6)實(shí)現(xiàn)自動(dòng)改變遺傳算法的變異率P。

1.7　遺傳算法的精英策略

種群的交叉、變異操作具有不確定性，經(jīng)過(guò)交叉和變異的子代種群的優(yōu)劣是未知的，如果父代種群中的優(yōu)良個(gè)體也執(zhí)行交叉操作，最優(yōu)個(gè)體可能會(huì)被替換，因此出現(xiàn)了精英策略[9-11]。精英策略的基本思想是每次迭代的過(guò)程中，從父種群中挑選最優(yōu)個(gè)體添加到子代種群或替換掉子代種群的最差個(gè)體，因?yàn)榻徊孀儺惖慕Y(jié)果是未知的，而父種群中的最優(yōu)個(gè)體是確定的，這樣能保證子代種群的高適應(yīng)度，避免進(jìn)化過(guò)程中最優(yōu)解變異丟失。

1.8　優(yōu)化決策樹(shù)的算法步驟

優(yōu)化決策樹(shù)的算法步驟如下：

步驟1：采集組數(shù)據(jù)，作為對(duì)決策樹(shù)分類(lèi)器進(jìn)行剪枝操作的測(cè)試數(shù)據(jù)集；

步驟2：設(shè)定控制參數(shù)、定義適應(yīng)度函數(shù)等；

步驟2-1：設(shè)定控制參數(shù)，群體規(guī)模、最大迭代次數(shù)max；

步驟2-2：變量聲明，當(dāng)前迭代次數(shù)、交叉概率P、變異概率P；

步驟2-3：染色體編碼；

步驟2-4：計(jì)算交叉概率P、變異概率P，計(jì)算方法如式(5)和式(6)；

步驟2-5：定義適應(yīng)度函數(shù)(H)，其中H為生成個(gè)決策樹(shù)的編號(hào)（=1，2，…，），適應(yīng)度函數(shù)計(jì)算如式(2)；

步驟3：初始化，令=0且隨機(jī)生成個(gè)決策樹(shù)H；

步驟4：形成種群，對(duì)每一個(gè)決策樹(shù)H，計(jì)算適應(yīng)度(H)；

步驟5：選擇適應(yīng)度最高的染色體加入新種群P；

步驟6：其余的染色體進(jìn)行交叉和變異操作；

步驟7：生成種群′，計(jì)算所有新決策樹(shù)的適應(yīng)度(H)；

步驟8：′淘汰最小適應(yīng)度的決策樹(shù)，加入來(lái)自步驟5的決策樹(shù)，形成新種群P；

步驟9：令種群P=P；

步驟10：當(dāng)=max，轉(zhuǎn)步驟11；否則轉(zhuǎn)步驟4；

步驟11：適應(yīng)度最高的決策樹(shù)為最優(yōu)的決策樹(shù)。

2　EM算法

本文采用數(shù)據(jù)樣本總體平均值填充缺失數(shù)據(jù)。缺失數(shù)值型數(shù)據(jù)所在集合的數(shù)據(jù)作為填充數(shù)據(jù)的參考樣本。數(shù)據(jù)按照時(shí)間順序排列，數(shù)據(jù)表示為{1，2，…，X}，是按時(shí)間排列的序號(hào)且為正整數(shù)。數(shù)據(jù)總體分為觀察數(shù)據(jù)和缺失數(shù)據(jù)，觀察數(shù)據(jù)是實(shí)際存在的數(shù)值，觀察數(shù)據(jù)集合為obs= {1，2，…，X}，缺失數(shù)據(jù)集合為miss= {X1，X2，…，X}，是按時(shí)間排列的序號(hào)且為正整數(shù)，。

EM算法[12]步驟如下：

步驟1：變量聲明，當(dāng)前迭代次數(shù)（為正整數(shù)）、收斂參數(shù)（為正數(shù)）、迭代次時(shí)評(píng)價(jià)參量(k)，最大期望值(fillobs，(k))、預(yù)測(cè)值fill；

步驟3：執(zhí)行最大期望步（E步），計(jì)算方法如式(7)所示；

其中，(fillobs，(k))為迭代第次時(shí)填充數(shù)據(jù)期望值；(k)、(k?1)分別為迭代第次、第?1次的評(píng)價(jià)參量；

步驟4：執(zhí)行最大化步（M步），計(jì)算方式如式(8)所示；

其中，(k)、(k?1)分別為迭代第次、第?1次的評(píng)價(jià)參量；X為觀察數(shù)據(jù)，obs= {1，2，…，X}；

步驟5：判斷是否滿(mǎn)足收斂條件，若是轉(zhuǎn)步驟6；否則=+1，轉(zhuǎn)步驟3，計(jì)算方式如式(9)所示；

其中為收斂參數(shù)；

步驟6：輸出預(yù)測(cè)值fill，并使用該值作為對(duì)本數(shù)據(jù)集所有缺失數(shù)據(jù)的填充值，計(jì)算方式如式(10)所示。

3　基于優(yōu)化決策樹(shù)和EM的缺失數(shù)據(jù)填充算法

基于優(yōu)化決策樹(shù)和EM的缺失數(shù)據(jù)填充算法步驟：

步驟1：采用最優(yōu)的決策樹(shù)對(duì)缺失數(shù)據(jù)進(jìn)行分類(lèi)，得到若干分類(lèi)集合；

步驟2：EM算法初始化，以缺失數(shù)值型數(shù)據(jù)所在集合的數(shù)據(jù)作為填充數(shù)據(jù)的參考樣本；

步驟3：執(zhí)行EM算法，完成數(shù)據(jù)填充。

4　實(shí)驗(yàn)與分析

4.1　實(shí)驗(yàn)環(huán)境與參數(shù)設(shè)置

本次實(shí)驗(yàn)的CPU為Intel Core i3 3.40 GHz，內(nèi)存為4 GB，操作系統(tǒng)為Window7 32位，開(kāi)發(fā)環(huán)境為MATLAB R2013a。相關(guān)算法的參數(shù)設(shè)置如表2所示。

表2　算法的參數(shù)設(shè)置

4.2　實(shí)驗(yàn)結(jié)果與分析

4.2.1優(yōu)化決策樹(shù)的分類(lèi)精度測(cè)試

為驗(yàn)證算法準(zhǔn)確性，本文采用車(chē)載健康監(jiān)測(cè)設(shè)備的30000條數(shù)據(jù)作為原始數(shù)據(jù)，包括心率、血壓和體溫等數(shù)值型數(shù)據(jù)，且所有數(shù)據(jù)都是同一人在同一環(huán)境下連續(xù)獲取。原始數(shù)據(jù)生成的決策樹(shù)分類(lèi)精度為82.8%。在測(cè)試樣本數(shù)分別為400，600，800，1000，1200時(shí)，采用相同的測(cè)試樣本，分別用遺傳算法和改進(jìn)遺傳算法對(duì)決策樹(shù)進(jìn)行優(yōu)化操作。每個(gè)算法運(yùn)行5次，選取分類(lèi)精度最好的決策樹(shù)進(jìn)行對(duì)比。實(shí)驗(yàn)結(jié)果如表3、圖2所示。

表3　原始決策樹(shù)、遺傳算法的優(yōu)化決策樹(shù)和改進(jìn)遺傳算法的優(yōu)化決策樹(shù)的分類(lèi)精度測(cè)試結(jié)果

圖2　2種優(yōu)化決策樹(shù)算法的分類(lèi)精度對(duì)比圖

由表3、圖2可知，由于剪去了不可靠的分支，優(yōu)化后的決策樹(shù)分類(lèi)精度明顯提高。從測(cè)試樣本方面看，參與決策樹(shù)剪枝的測(cè)試樣本越大，決策樹(shù)的分類(lèi)精度越高，剪枝效果越好。從分類(lèi)精度方面看，改進(jìn)遺傳算法的優(yōu)化決策樹(shù)分類(lèi)效果優(yōu)于遺傳算法的優(yōu)化決策樹(shù)。這是因?yàn)楦倪M(jìn)遺傳算法在運(yùn)行過(guò)程中對(duì)較優(yōu)個(gè)體進(jìn)行保留操作或者減少交叉變異操作，提高了決策樹(shù)的適應(yīng)度。

4.2.2填充算法的耗時(shí)對(duì)比

從原始數(shù)據(jù)集中隨機(jī)抽取5組樣本數(shù)據(jù)個(gè)數(shù)為3000的樣本作為數(shù)據(jù)測(cè)試集。每組測(cè)試集隨機(jī)刪除若干個(gè)數(shù)據(jù)，生成4個(gè)不同的數(shù)據(jù)測(cè)試集，缺失數(shù)據(jù)個(gè)數(shù)分別為200，400，600，800。對(duì)每個(gè)數(shù)據(jù)集分別用基于原始決策樹(shù)和EM的缺失數(shù)據(jù)填充算法、基于優(yōu)化決策樹(shù)和EM的缺失數(shù)據(jù)填充算法填充缺失數(shù)據(jù)。5組實(shí)驗(yàn)數(shù)據(jù)完成后，得出每個(gè)數(shù)據(jù)測(cè)試集的缺失數(shù)據(jù)填充時(shí)間，按缺失數(shù)據(jù)個(gè)數(shù)求出平均值。實(shí)驗(yàn)結(jié)果如表4、圖3所示。

表4　基于原始決策樹(shù)和EM的缺失數(shù)據(jù)填充算法、基于優(yōu) 化決策樹(shù)和EM的缺失數(shù)據(jù)填充算法的耗時(shí)對(duì)比

由表4、圖3可知，缺失數(shù)據(jù)填充的平均耗時(shí)與缺失數(shù)據(jù)個(gè)數(shù)增加基本呈正相關(guān)的關(guān)系，缺失數(shù)據(jù)個(gè)數(shù)越多，填充數(shù)據(jù)平均耗時(shí)越長(zhǎng)。通過(guò)對(duì)比優(yōu)化前后的決策樹(shù)對(duì)填充缺失數(shù)據(jù)過(guò)程平均耗時(shí)可知，優(yōu)化后缺失數(shù)據(jù)填充算法的平均耗時(shí)減少了。這是因?yàn)闆Q策樹(shù)分支數(shù)減少，縮短了決策樹(shù)分類(lèi)器對(duì)缺失數(shù)據(jù)分類(lèi)的時(shí)間。

圖3　2種缺失數(shù)據(jù)填充算法平均耗時(shí)對(duì)比圖

5　結(jié)論

本文提出了一種基于優(yōu)化決策樹(shù)和EM的缺失數(shù)據(jù)填充算法。該算法主要基于精英策略的自適應(yīng)遺傳算法對(duì)決策樹(shù)進(jìn)行優(yōu)化，克服了決策樹(shù)的過(guò)分?jǐn)M合問(wèn)題，然后結(jié)合優(yōu)化后的決策樹(shù)和EM算法，實(shí)現(xiàn)多屬性數(shù)值型數(shù)據(jù)的分類(lèi)和填充。本文采用車(chē)載健康監(jiān)測(cè)設(shè)備采集的數(shù)據(jù)作為原始數(shù)據(jù)進(jìn)行仿真，結(jié)果表明，相對(duì)于優(yōu)化前的決策樹(shù)算法，優(yōu)化后的決策樹(shù)分類(lèi)精度更高，所提出算法的平均填充耗時(shí)更少。該算法具有較高的實(shí)用價(jià)值，可以有效解決多屬性數(shù)值型數(shù)據(jù)缺失問(wèn)題。

[1] 李宏,阿瑪尼,李平,等.基于EM和貝葉斯網(wǎng)絡(luò)的丟失數(shù)據(jù)填充算法[J].計(jì)算機(jī)工程與應(yīng)用,2010,46(5):123-125.

[2] 武森,馮小東,單志廣.基于不完備數(shù)據(jù)聚類(lèi)的缺失數(shù)據(jù)填補(bǔ)方法[J].計(jì)算機(jī)學(xué)報(bào),2012,35(8):1726-1738.

[3] 張嬋.一種基于支持向量機(jī)的缺失值填補(bǔ)算法[J].計(jì)算機(jī)應(yīng)用與軟件,2013,30(5):226-228.

[4] 袁景凌,鐘珞,楊光,等.綠色數(shù)據(jù)中心不完備能耗大數(shù)據(jù)填補(bǔ)及分類(lèi)算法研究[J].計(jì)算機(jī)學(xué)報(bào),2015,38(12):2499-2516.

[5] 李忠波,楊建華,劉文琦.基于數(shù)據(jù)填補(bǔ)和連續(xù)屬性的樸素貝葉斯算法[J].計(jì)算機(jī)工程與應(yīng)用,2016,52(1):133-140.

[6] Amiri M, Jensen R. Missing data imputation using fuzzy-rough methods[J]. Neurocomputing, 2016, 205:152-164.

[7] Turrado C C, Sánchez L F, Calvorollé J L, et al. A hybrid algorithm for missing data imputation and its application to electrical data loggers[J]. Sensors, 2016, 16(9):1467.

[8] Dong Y J, Liu T Z. Parameter optimization based on genetic algorithm in the research of equivalent pruning effect on fuzzy decision tree[J]. Advanced Materials Research, 2013, 756-759: 3809-3813.

[9] 劉全,王曉燕,傅啟明,等.雙精英協(xié)同進(jìn)化遺傳算法[J].軟件學(xué)報(bào),2012,23(4):765-775.

[10] Leno I J, Sankar S S, Ponnambalam S G. MIP model and elitist strategy hybrid GA–SA algorithm for layout design[J]. Journal of Intelligent Manufacturing, 2015:1-19.

[11] Tretyakova A, Seredynski F. A novel genetic algorithm with asexual reproduction for the maximum lifetime coverage problem in wireless sensor networks[C]. The Third International Conference on Advanced Communications and Computation, 2013: 87-93.

[12] Lin T H. A comparison of multiple imputation with EM algorithm and MCMC method for quality of life missing data[J]. Quality & Quantity, 2010, 44(2):277-287.

Missing Data Imputation Algorithm Based on Optimal Decision Tree and EM

Liang Bingyi1Cai Yanguang2Cai Hao2Qi Yuanhang2Huang Helie2Ole Hejlesen3

(1. Guangzhou No.3 Bus Company 2. School of Automation, Guangdong University of Technology 3. Department of Health Science & Technology, Aalborg University)

Focusing on the problem of missing data in large data management and application, a missing data imputation algorithm based on an optimal Decision Tree and EM is proposed to fill the tmultiple attributed missing numeric data. In order to solve excessive fitting problem of Decision Tree, the proposed algorithm adopts an optimal Decision Tree which is optimized by an adaptive genetic algorithm based on elitist strategy to classify the data, and combines with the EM to fill the numeric data. The simulation results show that: comparing with Decision Tree algorithm without optimization, the classification accuracy of the optimal Decision Tree is better and the proposed algorithm need less time to fill data.

Data Imputation; Decision Tree; Expectation Maximization Algorithm; Genetic Algorithm

梁秉毅，男，1991年生，碩士，研究方向：計(jì)算機(jī)技術(shù)與應(yīng)用。E-mail: byleuang@foxmail.com

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

國(guó)家自然科學(xué)基金（61074147）；廣東省自然科學(xué)基金（S2011010005059）；廣東省教育部產(chǎn)學(xué)研結(jié)合項(xiàng)目（2012B091000171，2011B090400460）；廣東省科技計(jì)劃項(xiàng)目（2012B050600028，2014B010118004，2016A050502060）；廣州市花都區(qū)科技計(jì)劃項(xiàng)目（HD14ZD001）；廣州市科技計(jì)劃項(xiàng)目（201605121347368）。