基于多模型融合的不完整數(shù)據(jù)分?jǐn)?shù)插補(bǔ)算法

邵良杉，趙松澤

（1.遼寧工程技術(shù)大學(xué) 軟件學(xué)院，遼寧 葫蘆島 125105；2.遼寧工程技術(shù)大學(xué) 系統(tǒng)工程研究所，遼寧 葫蘆島 125105）

0 概述

在大數(shù)據(jù)時(shí)代，帶有空缺值的不完整數(shù)據(jù)需要處理。因?yàn)榇蟛糠謹(jǐn)?shù)據(jù)挖掘算法無法處理不完整數(shù)據(jù)［1-3］，所以從不完整數(shù)據(jù)中進(jìn)行學(xué)習(xí)是主要處理方式。刪除和插補(bǔ)是目前常用的2 種方法。刪除會(huì)導(dǎo)致數(shù)據(jù)的可用數(shù)量減少，并且增加模型的過擬合風(fēng)險(xiǎn)，無法保證模型的可靠性［4］，通常只在大數(shù)據(jù)情況下采用該方式處理不完整數(shù)據(jù)［5］。插補(bǔ)廣泛應(yīng)用在多個(gè)領(lǐng)域中，如醫(yī)學(xué)［6-9］、統(tǒng)計(jì)學(xué)［10］等。研究人員可以快速使用多種開源的插補(bǔ)算法［11-12］處理不完整數(shù)據(jù)?，F(xiàn)有插補(bǔ)算法分為單值插補(bǔ)和多值插補(bǔ)。單值插補(bǔ)為1 個(gè)空缺樣本生成1 個(gè)插補(bǔ)值；多值插補(bǔ)為1 個(gè)空缺樣本生成多個(gè)插補(bǔ)值。近年來，國(guó)內(nèi)外對(duì)數(shù)據(jù)插補(bǔ)算法進(jìn)行研究，取得一定的研究成果。

單值插補(bǔ)根據(jù)插補(bǔ)次數(shù)可以分為單次插補(bǔ)和多次迭代插補(bǔ)。單次插補(bǔ)有K 近鄰插補(bǔ)算法［13］、EM 算法［14］以及基于聚類的插補(bǔ)算法［15］。多項(xiàng)研究結(jié)果表明，K 近鄰插補(bǔ)算法不對(duì)數(shù)據(jù)進(jìn)行假設(shè)［16］，且優(yōu)于其他單次插補(bǔ)算法［16-17］。因此，研究人員改進(jìn)K 近鄰算法，通過為每個(gè)樣本確定合適的K值來提升插補(bǔ)效果［18-20］，該方法可以解決多視圖聚類問題中樣本缺失的問題［21］。文獻(xiàn)［22］提出一種可以更快速確定樣本K值的K*樹。多次迭代插補(bǔ)算法的代表是基于隨機(jī)森林的插補(bǔ)算法［23］。研究指出，合理確定插補(bǔ)順序可以有效提高多次迭代插補(bǔ)算法的效果［4］。多次迭代插補(bǔ)算法只適用于分類任務(wù)，并且需要將所有連續(xù)屬性離散化，但是離散化操作可能造成信息丟失，增加模型過擬合風(fēng)險(xiǎn)［24-26］。此外，文獻(xiàn)［17，27］提出K 近鄰算法與隨機(jī)森林算法在多個(gè)數(shù)據(jù)集上的插補(bǔ)效果較優(yōu)。文獻(xiàn)［28］將插補(bǔ)視為優(yōu)化問題，利用遺傳算法進(jìn)行插補(bǔ)。文獻(xiàn)［29］基于領(lǐng)域知識(shí)將藥物治療的最差結(jié)果作為插補(bǔ)值。文獻(xiàn)［30］提出非定量字符串?dāng)?shù)據(jù)的插補(bǔ)。文獻(xiàn)［31-33］提出面向特定任務(wù)，根據(jù)數(shù)據(jù)特點(diǎn)制定專用插補(bǔ)算法。文獻(xiàn)［34］提出適用于圖像數(shù)據(jù)缺失的插補(bǔ)算法。文獻(xiàn)［35］使用神經(jīng)網(wǎng)絡(luò)對(duì)缺失數(shù)據(jù)進(jìn)行插補(bǔ)。

多值插補(bǔ)算法主要有多重插補(bǔ)（Multiple Imputation，MI）和分?jǐn)?shù)插補(bǔ)（Fractional Imputation，F(xiàn)I）算法［12，36］，MI 需要保證缺失隨機(jī)發(fā)生且數(shù)據(jù)服從正態(tài)分布［36-38］，而且只能尋找MI倍數(shù)的最優(yōu)解［39］，導(dǎo)致MI的計(jì)算成本增大。對(duì)于數(shù)據(jù)挖掘任務(wù)，MI 10～50 倍［39-40］的數(shù)據(jù)倍增導(dǎo)致后續(xù)建立機(jī)器學(xué)習(xí)模型的時(shí)間也同樣倍增。分?jǐn)?shù)插補(bǔ)算法假設(shè)缺失數(shù)據(jù)與完整數(shù)據(jù)是同分布的，進(jìn)而根據(jù)完整數(shù)據(jù)的概率分布為不完整數(shù)據(jù)生成多個(gè)插補(bǔ)結(jié)果，并將每個(gè)結(jié)果所對(duì)應(yīng)的概率轉(zhuǎn)化為樣本分?jǐn)?shù)。以統(tǒng)計(jì)均值或方差等為目的的FI 使得每個(gè)空缺值樣本的多個(gè)結(jié)果分?jǐn)?shù)和為1［41］，以保證插補(bǔ)后仍可獲取可靠的統(tǒng)計(jì)量。

現(xiàn)有插補(bǔ)算法存在一定局限性，目前插補(bǔ)算法等效看待所有樣本，導(dǎo)致在建立模型時(shí)可靠的完整樣本和插補(bǔ)后樣本對(duì)于偏差的不可靠樣本具有相同權(quán)重，降低模型性能?，F(xiàn)有插補(bǔ)算法無法有效處理高缺失率樣本（缺失率大于50%），高缺失率樣本的插補(bǔ)結(jié)果會(huì)注入大量噪聲數(shù)據(jù)，而刪除又會(huì)降低可用數(shù)據(jù)量，造成過擬合風(fēng)險(xiǎn)。除此之外，所有多值插補(bǔ)算法都有1 個(gè)隱藏假設(shè)，即缺失數(shù)據(jù)與完整數(shù)據(jù)同分布，但是在現(xiàn)實(shí)中通常無法保證該假設(shè)成立，從而限制了多值插補(bǔ)算法的使用范圍。

噪聲標(biāo)簽學(xué)習(xí)通過生成新標(biāo)簽替換噪聲標(biāo)簽，提高學(xué)習(xí)效率［42］。現(xiàn)有的噪聲標(biāo)簽學(xué)習(xí)技術(shù)集中于損失修正，而損失修正的1 個(gè)重要步驟是識(shí)別噪聲［43-44］。研究指出通過β混合分布擬合樣本交叉熵的分布，估算樣本為噪聲的概率［43］可以有效提高噪聲標(biāo)簽學(xué)習(xí)的效果。在計(jì)算樣本的噪聲概率后，通過更新?lián)p失函數(shù)或樣本重加權(quán)的方式降低噪聲對(duì)模型的影響［44］。

本文提出一種基于多模型融合的不完整數(shù)據(jù)分?jǐn)?shù)插補(bǔ)算法FIB。通過樣本分?jǐn)?shù)區(qū)分不同的樣本，使可靠的插補(bǔ)結(jié)果分?jǐn)?shù)更高，不可靠的插補(bǔ)結(jié)果分?jǐn)?shù)更低，進(jìn)而增強(qiáng)后續(xù)建立機(jī)器學(xué)習(xí)模型的性能。通過引入修正模型，使用高缺失率樣本生成偽標(biāo)簽數(shù)據(jù)［45］，以充分利用高缺失率樣本。在此基礎(chǔ)上，基于多模型融合生成多值插補(bǔ)的結(jié)果，不對(duì)缺失數(shù)據(jù)進(jìn)行任何假設(shè)，增加插補(bǔ)算法的適用范圍。

1 基于多模型融合的分?jǐn)?shù)插補(bǔ)算法

1.1 FIB 整體流程

FIB 使用多個(gè)插補(bǔ)算法作為插補(bǔ)子單元，首先在每個(gè)插補(bǔ)子單元中計(jì)算樣本分?jǐn)?shù)，然后使用高缺失率樣本生成偽標(biāo)簽數(shù)據(jù)，將偽標(biāo)簽數(shù)據(jù)擴(kuò)充至初始插補(bǔ)結(jié)果中，最后融合多個(gè)插補(bǔ)子單元的插補(bǔ)結(jié)果。FIB 算法流程如圖1 所示。

圖1 FIB 算法流程Fig.1 Procedure of FIB algorithm

在現(xiàn)有不完整數(shù)據(jù)學(xué)習(xí)算法對(duì)空缺值的處理過程中，可靠的原始完整樣本及不可靠的插補(bǔ)樣本享有相同的權(quán)重，增大了不可靠樣本對(duì)模型性能的影響。因此，通過評(píng)分計(jì)算初始插補(bǔ)結(jié)果中每個(gè)樣本的分?jǐn)?shù)，以降低不可靠樣本的負(fù)面影響。當(dāng)評(píng)分模型完成時(shí)高缺失率樣本的得分趨近于0，對(duì)于模型的影響較小，在數(shù)據(jù)集中含有大量高缺失率樣本的情況下，模型會(huì)過度擬合少部分的完整數(shù)據(jù)。為了充分利用高缺失率樣本，通過生成偽標(biāo)簽數(shù)據(jù)，并重新計(jì)算偽標(biāo)簽數(shù)據(jù)的得分，轉(zhuǎn)化后的分?jǐn)?shù)不再趨近于0，從而更大程度地利用高缺失率數(shù)據(jù)，降低模型過度擬合完整數(shù)據(jù)的風(fēng)險(xiǎn)。將偽標(biāo)簽數(shù)據(jù)擴(kuò)充至插補(bǔ)結(jié)果中，形成1 個(gè)待合并的單元插補(bǔ)結(jié)果。使用多個(gè)插補(bǔ)算法獲得多個(gè)插補(bǔ)結(jié)果，并將這些結(jié)果相融合，得到最終插補(bǔ)結(jié)果。

FIB 不限制插補(bǔ)單元數(shù)量，也不基于任何一種具體算法，當(dāng)采用多個(gè)插補(bǔ)單元時(shí)，通過并行計(jì)算可以加快插補(bǔ)速度。圖1 中所涉及到的算法和模型可替換為任意一種機(jī)器學(xué)習(xí)模型。

1.2 評(píng)分原理及有效性證明

本文定義樣本分?jǐn)?shù)Sn，如式（1）所示：

其中：xn為該樣本的特征；yn為標(biāo)簽；函數(shù)M(?)為從未發(fā)生缺失的原始數(shù)據(jù)集中學(xué)習(xí)的規(guī)律；Sn為第n個(gè)插補(bǔ)樣本與原始數(shù)據(jù)集完整數(shù)據(jù)相同的概率。當(dāng)Sn=1時(shí)，An插補(bǔ)成功，此時(shí)An為正確插補(bǔ)樣本；當(dāng)Sn=0時(shí)，An插補(bǔ)失敗，此時(shí)An為錯(cuò)誤插補(bǔ)樣本。

1.2.1 區(qū)分正誤插補(bǔ)樣本的指標(biāo)

為了估計(jì)Sn的值，本文找到可以有效區(qū)分正誤插補(bǔ)樣本的指標(biāo)。在噪聲標(biāo)簽學(xué)習(xí)中利用神經(jīng)網(wǎng)絡(luò)計(jì)算樣本的交叉熵，交叉熵服從β混合分布［雙峰分布（正確樣本集中分布在左，而噪聲樣本集中分布在右）］，根據(jù)樣本的交叉熵?fù)p失值計(jì)算樣本為噪聲的概率［37］。

噪聲標(biāo)簽本質(zhì)上是空值插補(bǔ)的一種特殊情況，即原始數(shù)據(jù)僅有標(biāo)簽發(fā)生缺失。Dn與交叉熵區(qū)分正誤插補(bǔ)樣本的效果對(duì)比如圖2 所示。為驗(yàn)證噪聲標(biāo)簽學(xué)習(xí)技術(shù)是否可應(yīng)用于空值插補(bǔ)任務(wù)，本文使用交叉熵區(qū)分正確插補(bǔ)樣本與錯(cuò)誤插補(bǔ)樣本的核密度估計(jì)（Kernel Density Estimation，KDE）圖，結(jié)果如圖2（a）所示。從圖2（a）可以看出，正誤插補(bǔ)樣本的交叉熵分布區(qū)域高度重合，說明根據(jù)交叉熵?fù)p失無法判斷插補(bǔ)是否成功。

圖2 Dn與交叉熵區(qū)分正誤插補(bǔ)樣本的效果對(duì)比Fig.2 Comparison of the effect of Dn and cross entropy in distinguishing correct and false imputation samples

在噪聲標(biāo)簽學(xué)習(xí)中有效的交叉熵?fù)p失在空值插補(bǔ)中失效，其原因?yàn)樵肼晿?biāo)簽學(xué)習(xí)具有2 個(gè)空值插補(bǔ)不具有的特點(diǎn)：1）噪聲標(biāo)簽的特征值都是正確的；2）標(biāo)簽與正確值的差異顯著。這2 個(gè)特點(diǎn)是造成噪聲標(biāo)簽損失值普遍高于正確插補(bǔ)樣本的主要原因。插補(bǔ)算法根據(jù)其他屬性預(yù)測(cè)標(biāo)簽值，或根據(jù)標(biāo)簽預(yù)測(cè)缺失屬性的值，該過程會(huì)降低不完整樣本的交叉熵，最終導(dǎo)致插補(bǔ)正確和插補(bǔ)錯(cuò)誤的樣本在交叉熵上的分布一致。

因此，F(xiàn)IB 重新定義一種新的指標(biāo)Dn：

其中：Mi為缺失特征；BBREi為特征的置換重要性，設(shè)BRE 標(biāo)簽為1。

Dn結(jié)合了缺失率及缺失屬性的重要度。從式（2）可以看出，隨著樣本缺失率的增加，插補(bǔ)成功的概率降低。在相同樣本缺失率下，缺失的特征重要性越高，則插補(bǔ)成功率越低。

從圖2（b）可以看出，Dn可以有效區(qū)分正誤插補(bǔ)樣本，正確插補(bǔ)樣本集中分布于左側(cè)，而錯(cuò)誤插補(bǔ)樣本集中分布于右側(cè)。

1.2.2 評(píng)分函數(shù)

已知D可以有效區(qū)分正誤插補(bǔ)樣本，本文構(gòu)造評(píng)分函數(shù)F(Dn)=Sn。由于Sn代表樣本插補(bǔ)正確的概率，因此0 ≤F(?) ≤1。此外，因?yàn)镈n=0 對(duì)應(yīng)完整樣本，所以F(0)=1。Sn與Dn的關(guān)系如下：

FIB 構(gòu)造3 種滿足上述條件的函數(shù)，如式（4）～式（6）所示：

其中：k0=sum(B)；k1由S3(1/k0)=θ解出，θ為超參數(shù)，表示當(dāng)采用隨機(jī)插補(bǔ)算法的成功概率為0 時(shí)，采用基于評(píng)分函數(shù)的插補(bǔ)算法插補(bǔ)成功的概率默認(rèn)為θ。

為驗(yàn)證不同函數(shù)的差異性，首先構(gòu)造F1(x)，F(xiàn)1(x)在不使用任何插補(bǔ)算法的前提下對(duì)空值隨機(jī)插補(bǔ)時(shí)對(duì)應(yīng)的評(píng)分函數(shù)。當(dāng)使用插補(bǔ)算法時(shí)，插補(bǔ)成功的概率不低于F1(x)。本文進(jìn)一步構(gòu)造函數(shù)F2(x)和F3(x)，F(xiàn)2(x)可以保證Sn與Dn的分布特點(diǎn)相同，而基于Sigmoid 函數(shù)構(gòu)造的F3(x)使S向0 與1 聚集，改變?cè)蠨的分布形式，將樣本分為正確插補(bǔ)樣本和錯(cuò)誤插補(bǔ)樣本。

基于S1、S2、S3函數(shù)計(jì)算得到的評(píng)分分?jǐn)?shù)如圖3所示，其中，S1、S2隨著Dn的增加呈線性變化。

圖3 基于Dn的函數(shù)曲線圖Fig.3 Function graph based on Dn

1.3 偽標(biāo)簽數(shù)據(jù)的生成

在數(shù)據(jù)缺失較多的數(shù)據(jù)集中，單獨(dú)使用樣本分?jǐn)?shù)使得不完整樣本的分?jǐn)?shù)趨近于0，而少數(shù)完整樣本分?jǐn)?shù)為1。因此，將分?jǐn)?shù)作為樣本權(quán)重訓(xùn)練機(jī)器學(xué)習(xí)模型，導(dǎo)致模型過擬合少量完整樣本，而利用修正模型生成的偽標(biāo)簽數(shù)據(jù)能夠有效降低模型過擬合的風(fēng)險(xiǎn)。

生成偽標(biāo)簽數(shù)據(jù)的具體步驟如下：1）根據(jù)任務(wù)類型（分類任務(wù)或回歸任務(wù)）選擇合適的算法；2）將計(jì)算得到的樣本分?jǐn)?shù)作為樣本權(quán)重，使用初始插補(bǔ)結(jié)果訓(xùn)練修正模型；3）使用訓(xùn)練好的模型預(yù)測(cè)得分小于α（超參數(shù)）的插補(bǔ)樣本，將非標(biāo)簽特征與預(yù)測(cè)結(jié)果合并得到偽標(biāo)簽數(shù)據(jù)；4）更新偽標(biāo)簽數(shù)據(jù)的樣本分?jǐn)?shù)；5）將偽標(biāo)簽數(shù)據(jù)擴(kuò)充至初始插補(bǔ)結(jié)果，形成單元插補(bǔ)結(jié)果。

偽標(biāo)簽樣本分?jǐn)?shù)的計(jì)算方法如下：

其中：對(duì)于分類任務(wù)，K為修正模型預(yù)測(cè)An所有類別概率中的最大值；對(duì)于回歸任務(wù)，K取值為1。

修正模型的性能直接影響偽標(biāo)簽數(shù)據(jù)的質(zhì)量，在算力充足的情況下使用模型選擇方法確保修正模型的有效性。普通模型的選擇方法首先將數(shù)據(jù)集分為訓(xùn)練集與測(cè)試集，然后通過訓(xùn)練集訓(xùn)練模型，最后選擇在測(cè)試集中表現(xiàn)最佳的模型，如利用交叉熵衡量分類模型性能，利用均方誤差衡量回歸模型性能。修正模型的選擇方法在于樣本分?jǐn)?shù)，首先在訓(xùn)練模型時(shí)，與訓(xùn)練集對(duì)應(yīng)的樣本分?jǐn)?shù)將作為樣本權(quán)重參與訓(xùn)練過程，然后在測(cè)試集上評(píng)估模型時(shí)，利用測(cè)試集對(duì)應(yīng)的樣本分?jǐn)?shù)改變樣本的損失函數(shù)。在分類任務(wù)中，傳統(tǒng)的模型選擇方法計(jì)算測(cè)試集中所有樣本交叉熵的平均值，并利用該值判斷模型性能，然而在選擇修正模型時(shí)，測(cè)試集中每個(gè)樣本的交叉熵將乘以該樣本對(duì)應(yīng)的樣本分?jǐn)?shù)，以減弱低分?jǐn)?shù)的不可靠樣本對(duì)模型評(píng)估造成的影響。

1.4 多模型插補(bǔ)結(jié)果的融合

1.4.1 多模型的融合

常見的多模型融合方式有Voting、Averaging、Bagging、Boosting、Stacking、Blending 以及模型混合，其中，Stacking 與Blending 針對(duì)有監(jiān)督學(xué)習(xí)任務(wù)，不適用于空值插補(bǔ)任務(wù)。

多個(gè)插補(bǔ)模型通過Voting 或Averaging 進(jìn)行融合后，插補(bǔ)效果介于最優(yōu)和最差之間，Bagging 會(huì)降低可用數(shù)據(jù)量，導(dǎo)致在小規(guī)模數(shù)據(jù)集中降低插補(bǔ)性能。

Boosting 使用多個(gè)基礎(chǔ)模型進(jìn)行預(yù)測(cè)，并將其結(jié)果作為輸入來訓(xùn)練最終模型。然而，在空值插補(bǔ)任務(wù)中，不同模型的表現(xiàn)可能會(huì)受到限制。如果基礎(chǔ)模型無法準(zhǔn)確地插補(bǔ)缺失值，那么多模型融合也不能有效地提高插補(bǔ)效果。

由于多模型融合等價(jià)于修改最后1 個(gè)模型空缺值的初始值，因此也不適用于空缺值插補(bǔ)任務(wù)。FIB使用全部數(shù)據(jù)訓(xùn)練插補(bǔ)模型，當(dāng)空缺概率較低時(shí)，改變少量空缺值的初始值不會(huì)影響最終插補(bǔ)效果，當(dāng)空缺率較高時(shí)，插補(bǔ)的成功率較低，產(chǎn)生較多的錯(cuò)誤數(shù)據(jù)。多次插補(bǔ)使得這種錯(cuò)誤更嚴(yán)重，反而會(huì)降低插補(bǔ)效果。

傳統(tǒng)的多模型融合方法不適用于空值插補(bǔ)任務(wù)，F(xiàn)IB 將多個(gè)插補(bǔ)模型的插補(bǔ)結(jié)果進(jìn)行合并，以顯著提高插補(bǔ)性能。

1.4.2 多模型融合的優(yōu)缺點(diǎn)

本節(jié)將以balance-scale 數(shù)據(jù)集為例，說明多模型融合具有的優(yōu)勢(shì)。表1 所示為該數(shù)據(jù)集中的部分?jǐn)?shù)據(jù)，灰色區(qū)域代表缺失的數(shù)據(jù)。其中，Class、L-Weight、L-Distance、R-Weight 和R-Distance 為數(shù)據(jù) 集中的特征。

表1 balance-scale 數(shù)據(jù)集的部分?jǐn)?shù)據(jù) Table 1 Partial data of balance-scale dataset

本文直接使用均值插補(bǔ)算法，根據(jù)R-Distance的平均值將空缺值插補(bǔ)為3，使用sklearn 庫中實(shí)現(xiàn)的CART 決策樹插補(bǔ)算法時(shí)（不限制決策樹的復(fù)雜度），根據(jù)第2、4、5 行數(shù)據(jù)將空缺值插補(bǔ)為2。使用基于決策樹的多重插補(bǔ)算法生成3 個(gè)插補(bǔ)數(shù)據(jù)，分別將空缺值插補(bǔ)為2、4、5。雖然在大多數(shù)情況下使用更復(fù)雜的決策樹插補(bǔ)算法優(yōu)于均值插補(bǔ)算法，但是在這個(gè)特定的缺失下，均值插補(bǔ)算法能夠獲得正確的結(jié)果，說明不同插補(bǔ)算法分別擅長(zhǎng)處理不同的空缺值，多模型融合可以獲得更多的正確插補(bǔ)樣本。

現(xiàn)有多值插補(bǔ)算法的不足之處是假設(shè)缺失數(shù)據(jù)與完整數(shù)據(jù)同分布。在空缺值插補(bǔ)問題中，這種假設(shè)不成立，導(dǎo)致多值插補(bǔ)算法花費(fèi)更高的計(jì)算成本，卻沒有取得更優(yōu)的插補(bǔ)效果，說明多模型融合不對(duì)缺失數(shù)據(jù)的分布進(jìn)行任何假設(shè)。

多模型融合在增加更多正確插補(bǔ)樣本的同時(shí)，也會(huì)增加錯(cuò)誤插補(bǔ)樣本。假設(shè)在2 個(gè)模型的插補(bǔ)結(jié)果中，正確插補(bǔ)樣本的比例分別為rate1與rate2，將其融合后，正確插補(bǔ)樣本的比例為兩者均值。因此，2 個(gè)模型融合后的插補(bǔ)效果應(yīng)該介于2 種模型插補(bǔ)效果之間。

1.4.3 樣本評(píng)分技術(shù)與多模型的結(jié)合

當(dāng)樣本評(píng)分技術(shù)與多模型融合同時(shí)使用時(shí)，通過賦予正確插補(bǔ)樣本高評(píng)分、錯(cuò)誤插補(bǔ)樣本低評(píng)分的方式，強(qiáng)化多模型融合后產(chǎn)生更多正確插補(bǔ)樣本的優(yōu)點(diǎn)，弱化產(chǎn)生更多錯(cuò)誤插補(bǔ)樣本的缺點(diǎn)。當(dāng)樣本評(píng)分完全準(zhǔn)確，即所有正確插補(bǔ)樣本的評(píng)分都為1，錯(cuò)誤插補(bǔ)樣本的評(píng)分都為0 時(shí)，多模型融合后的插補(bǔ)效果優(yōu)于其中任何1 個(gè)插補(bǔ)模型。

插補(bǔ)完全正確的樣本評(píng)分難以獲得，除第1.2.2節(jié)中所提的評(píng)分方式以外，將完整樣本的分?jǐn)?shù)設(shè)置為1，將不完整樣本的分?jǐn)?shù)設(shè)置為1/N，其中N為模型個(gè)數(shù)，可以有效地與多模型融合進(jìn)行結(jié)合。

1.4.4 備選的插補(bǔ)模型

為了使多模型融合后增加更多的正確插補(bǔ)樣本，插補(bǔ)算法應(yīng)該保證選用的模型具有充分的差異性，為保證模型之間的差異性，應(yīng)選擇不同種類的插補(bǔ)模型進(jìn)行融合，此外還應(yīng)考慮所選模型的插補(bǔ)效果、計(jì)算成本以及模型本身的獲取難度。

基于這些因素，F(xiàn)IB 選取的候選插補(bǔ)模型主要有決策樹、K 近鄰、貝葉斯嶺回歸、隨機(jī)森林以及均值插補(bǔ)。

1.5 FIB 的偽代碼及時(shí)間復(fù)雜度

本節(jié)首先給出FIB 的偽代碼，然后在簡(jiǎn)要說明的同時(shí)計(jì)算FIB 的時(shí)間復(fù)雜度。

算法1FIB 算法

設(shè)DATA 的數(shù)據(jù)規(guī)模為n×d，算法1 第1～3 行獲取初始插補(bǔ)結(jié)果。如果使用單值單次插補(bǔ)算法，只需要建立1 個(gè)模型，以K 近鄰算法插補(bǔ)為例，時(shí)間復(fù)雜度T1=O(k×n×d)；如果使用單值多次迭代插補(bǔ)，則需要構(gòu)建d個(gè)插補(bǔ)模型，以CART 決策樹為例，時(shí)間復(fù)雜度T2=O(n×d2×lbn)。

第4～14 行計(jì)算樣本分?jǐn)?shù)，時(shí)間復(fù)雜度取決于插補(bǔ)模型，當(dāng)使用K 近鄰插補(bǔ)時(shí)，T3=O(n×d2)，使用CART 決策樹插補(bǔ)決策樹模型時(shí)，T3=O(n×d×lbn)。

第15～18 行生成偽標(biāo)簽數(shù)據(jù)，以使用CART 決策樹作為修正模型，T4=O(n×d×lbn)。第19～20 行合并插補(bǔ)結(jié)果并返回，T5=O(n×d)。

因此，采用CART 決策樹與K 近鄰插補(bǔ)融合的FIB 插補(bǔ)數(shù)據(jù)的時(shí)間成本T=T1+T2+T3+T4+T5=T2，說明FIB 的時(shí)間復(fù)雜度與單獨(dú)使用CART 決策樹插補(bǔ)的時(shí)間復(fù)雜度相同。

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

2.1 實(shí)驗(yàn)設(shè)置

2.1.1 實(shí)驗(yàn)概述

本文將進(jìn)行5 組實(shí)驗(yàn)，第1 組實(shí)驗(yàn)驗(yàn)證FIB 及各個(gè)部分的有效性，第2 組實(shí)驗(yàn)驗(yàn)證不同評(píng)分函數(shù)的差異，第3 組實(shí)驗(yàn)驗(yàn)證插補(bǔ)模型個(gè)數(shù)對(duì)插補(bǔ)效果的影響，第4 組實(shí)驗(yàn)驗(yàn)證超參數(shù)對(duì)插補(bǔ)效果的影響，第5 組實(shí)驗(yàn)將FIB 與數(shù)據(jù)驅(qū)動(dòng)增量插補(bǔ)模型（DIM）進(jìn)行對(duì)比，并討論FIB 的時(shí)間成本。

本文實(shí)驗(yàn)基于sklearn，由于sklearn 中的插補(bǔ)器只針對(duì)數(shù)值型數(shù)據(jù)且部分只適用于連續(xù)類型的數(shù)據(jù)集，因此將原始數(shù)據(jù)中的非數(shù)值型特征進(jìn)行編碼，對(duì)于離散屬性，在插補(bǔ)后將生成的連續(xù)值還原為最接近的離散值。

2.1.2 對(duì)比算法

對(duì)比算法包括決策樹插補(bǔ)、K 近鄰插補(bǔ)、FIB 以及FIB 的5 個(gè)變式。所有樣本通過函數(shù)F2進(jìn)行計(jì)算，超參數(shù)α設(shè)置為1。

對(duì)比算法主要有：1）KI 直接使用K 近鄰插補(bǔ)；2）KS 是帶有樣本分?jǐn)?shù)的K 近鄰插補(bǔ)；3）KE 在使用K 近鄰插補(bǔ)后，以K 近鄰算法作為修正模型生成偽標(biāo)簽數(shù)據(jù)的插補(bǔ)；4）DI 直接使用決策樹插補(bǔ)；5）DS是帶有樣本分?jǐn)?shù)的決策樹插補(bǔ)；6）DE 在使用決策樹插補(bǔ)后，以決策樹算法作為修正模型來生成偽標(biāo)簽數(shù)據(jù)；7）Blend 是合并KI 與DI 的結(jié)果，完整樣本權(quán)重為1，不完整樣本權(quán)重為0.5。

2.1.3 評(píng)估指標(biāo)

本文使用插補(bǔ)結(jié)果訓(xùn)練模型，通過獲得的模型預(yù)測(cè)原始數(shù)據(jù)，所得得分用于評(píng)估插補(bǔ)性能。對(duì)于分類任務(wù)，將平均準(zhǔn)確率（A）作為評(píng)價(jià)指標(biāo)，對(duì)于回歸任務(wù)，采取R2 得分作為評(píng)價(jià)指標(biāo)。A的計(jì)算如下：

其中：RRCi、PPCi分別代表第i個(gè)樣本標(biāo)簽的真實(shí)值與預(yù)測(cè)值；當(dāng)RRCi=PPCi時(shí)指示函數(shù)l(RRCi,PPCi)取1，反之取0。R2 得分（R2）計(jì)算如下：

2.2 結(jié)果分析

2.2.1 FIB 及各個(gè)部分的有效性分析

本文選擇6 個(gè)UCI 分類任務(wù)數(shù)據(jù)集和UCI 回歸任務(wù)數(shù)據(jù)集，為確保實(shí)驗(yàn)數(shù)據(jù)的全面性，數(shù)據(jù)集包括離散、連續(xù)及混合型，同時(shí)包括低維數(shù)據(jù)及高維數(shù)據(jù)。

原始數(shù)據(jù)集無缺失樣本或僅含有少量缺失樣本，首先將源數(shù)據(jù)中的少量缺失樣本刪除，然后分別以數(shù)據(jù)缺失率10%、30%、50%生成測(cè)試數(shù)據(jù)。數(shù)據(jù)缺失概率10%表示數(shù)據(jù)缺失率而非樣本缺失率，在1 個(gè)N×M大小的數(shù)據(jù)集中有0.1×N×M個(gè)數(shù)據(jù)缺失。

表2 和表3 分別為不同算法在UCI 分類任務(wù)和UCI 回歸任務(wù)數(shù)據(jù)集上的插補(bǔ)性能對(duì)比，加粗表示最優(yōu)數(shù)據(jù)。從表2 和表3 可以看出，F(xiàn)IB 具有最優(yōu)的評(píng)價(jià)指 標(biāo)，相 比KI 和DI算法，F(xiàn)IB 在UCI 分類任 務(wù)和回歸任務(wù)數(shù)據(jù)集上的評(píng)價(jià)指標(biāo)平均相對(duì)提升7.40%和18.73%。在UCI 分類任務(wù)數(shù)據(jù)集中的數(shù)據(jù)缺失率下，DI 的平均分類準(zhǔn)確率優(yōu)于KI，但是在UCI回歸任務(wù)數(shù)據(jù)集中數(shù)據(jù)缺失率50%下，除Auto MPG和Seoul Bike 之外，KI 的R2 得分優(yōu)于DI，說 明KI 的插補(bǔ)效果低于DI?；跇颖驹u(píng)分方法的KS 與DS插補(bǔ)算法可以同時(shí)提升K 近鄰和決策樹算法的插補(bǔ)性能。隨著數(shù)據(jù)缺失率的增加，基于評(píng)分分?jǐn)?shù)能有效提高插補(bǔ)效果，在高數(shù)據(jù)缺失率下評(píng)分更準(zhǔn)確，這是因?yàn)樵诟邤?shù)據(jù)缺失率下，樣本得分的差距增加，可以更有效地通過樣本分?jǐn)?shù)改變模型的結(jié)構(gòu)。

表2 不同算法在UCI 分類任務(wù)數(shù)據(jù)集上的分類準(zhǔn)確率 Table 2 Classification accuracy among different algorithms on UCI classification task datasets %

表3 不同算法在UCI 回歸任務(wù)數(shù)據(jù)集上的R2 得分Table 3 R2 scores among different algorithms on UCI regression task datasets

此外，使用修正模型生成的偽標(biāo)簽數(shù)據(jù)對(duì)于空缺值插補(bǔ)任務(wù)也是有效的，相比DI，DE 在UCI 分類任務(wù)數(shù)據(jù)集中平均提升3.31%，在UCI 回歸任務(wù)數(shù)據(jù)集中平均相對(duì)提升8.46%，而使用K 近鄰作為修正模型的KE 與DI 相比沒有顯著提升，說明標(biāo)簽數(shù)據(jù)質(zhì)量直接影響修正模型的性能。將多模型結(jié)果直接合并對(duì)空缺值插補(bǔ)任務(wù)具有有效性，在分類任務(wù)數(shù)據(jù)集中Blend 相較于DI、KI 的最優(yōu)效果相比，平均相對(duì)提升4.2%，在回歸任務(wù)數(shù)據(jù)集中平均相對(duì)提升11.37%。此外，在數(shù)據(jù)缺失率10%時(shí)，Blend 與DI、KI的差距最大。這是因?yàn)閟klearn 插補(bǔ)數(shù)據(jù)時(shí)會(huì)先使用均值插補(bǔ)作為初始插補(bǔ)器，在數(shù)據(jù)缺失率50%的情況下，大部分的缺失數(shù)據(jù)會(huì)被插補(bǔ)為均值，產(chǎn)生大量的重復(fù)樣本，改變了樣本的分布規(guī)律，導(dǎo)致插補(bǔ)算法更傾向于將缺失值插補(bǔ)為均值。

2.2.2 不同評(píng)分函數(shù)差異的驗(yàn)證

為驗(yàn)證F3（x）是否優(yōu) 于F2（x），本節(jié)使 用與第2.2.1 節(jié)相同的數(shù)據(jù)缺失率，將FIB 的評(píng)分函數(shù)由F2（x）更換為F3（x）重新進(jìn)行實(shí)驗(yàn)，評(píng)估更換評(píng)分函數(shù)后插補(bǔ)性能，結(jié)果如表4 所示。從表4 可以看出，F(xiàn)3（x）的插補(bǔ)效果總體低于F2（x），而且F3（x）的公式更復(fù)雜，計(jì)算成本更高。

表4 將評(píng)分函數(shù)F2（x）修改為F3（x）的評(píng)價(jià)指標(biāo)增幅Table 4 Increase of evaluation index of modifying scoring function F2（x）to F3（x）%

F2(x)通過線性變化在保持D分布規(guī)律的前提下將D的區(qū)間轉(zhuǎn)化為［0，1］，其原因在于大多現(xiàn)有機(jī)器學(xué)習(xí)模型只支持該區(qū)間內(nèi)的樣本權(quán)重。雖然F3(x)有效將樣本分成正確插補(bǔ)樣本和錯(cuò)誤插補(bǔ)樣本2 類，但是計(jì)算出的準(zhǔn)確率低于F2(x)。

2.2.3 插補(bǔ)模型個(gè)數(shù)對(duì)插補(bǔ)效果的影響

在第2.2.1 節(jié)中使用的FIB 只采取了K 近鄰和決策樹相融合的模型，現(xiàn)擴(kuò)大備選插補(bǔ)模型個(gè)數(shù)，額外增加均值插補(bǔ)、貝葉斯嶺回歸及隨機(jī)森林插補(bǔ)模型，共5 種備選插補(bǔ)模型。

從第2.2.1 節(jié)中選取的12 個(gè)UCI 數(shù)據(jù)集中隨機(jī)選取6 個(gè)數(shù)據(jù)集，以相同的方式生成缺失數(shù)據(jù)。對(duì)于每個(gè)缺失數(shù)據(jù)，采用5 個(gè)模型的所有組合方式進(jìn)行插補(bǔ)，并進(jìn)行31 次實(shí)驗(yàn)。經(jīng)過多模型融合后，完整樣本的分?jǐn)?shù)為1，不完整樣本生成的插補(bǔ)樣本分?jǐn)?shù)為模型個(gè)數(shù)的倒數(shù)。

以插補(bǔ)模型的個(gè)數(shù)分組，求解該分組插補(bǔ)性能的平均值，探究模型個(gè)數(shù)與插補(bǔ)性能之間的關(guān)系。模型個(gè)數(shù)與插補(bǔ)得分的關(guān)系如圖4 所示。

圖4 模型個(gè)數(shù)與插補(bǔ)得分的關(guān)系Fig.4 Relationship between the number of models and imputation scores

從圖4 可以看出，無論是分類任務(wù)還是回歸任務(wù)，合并模型個(gè)數(shù)越多，插補(bǔ)效果越好。2 條曲線在N=2 處都存在明顯的拐點(diǎn)，說明融合2 個(gè)模型能有效提高空缺值插補(bǔ)算法的效果。此外，2 條曲線均表現(xiàn)出相同趨勢(shì)：隨著模型個(gè)數(shù)增加，新增1 個(gè)模型所產(chǎn)生插補(bǔ)性能的提升幅度越來越小，在分類任務(wù)曲線中表現(xiàn)尤為明顯。

因?yàn)槎嗄Ｐ途哂懈叩挠?jì)算成本，所以只有在算力充足、數(shù)據(jù)集屬于中小規(guī)?；蛘咴谝恍?duì)插補(bǔ)性能要求極為嚴(yán)格的情況下，盡可能多地選擇模型進(jìn)行融合，在其他情況下只取2 個(gè)模型融合是最優(yōu)的選擇。

2.2.4 超參數(shù)α的驗(yàn)證

超參數(shù)α是數(shù)據(jù)需要重新賦予偽標(biāo)簽的閾值。當(dāng)α取1 時(shí)，所有樣本都被修正模型重新賦予偽標(biāo)簽；當(dāng)α取0 時(shí)，修正模型不生成偽標(biāo)簽數(shù)據(jù)。在第2.2.1 節(jié)的實(shí)驗(yàn)中，α設(shè)置為1。本實(shí)驗(yàn)將驗(yàn)證不同α值對(duì)插補(bǔ)性能的影響。

在數(shù)據(jù)缺失率低的情況下，超參數(shù)α的改變對(duì)插補(bǔ)效果的影響較小。以10%數(shù)據(jù)缺失率的隨機(jī)缺失為例，此時(shí)僅有少部分的分?jǐn)?shù)低于0.5，將α從0.1提升至0.5 時(shí)，偽標(biāo)簽數(shù)據(jù)的規(guī)模變化幅度較低，因此對(duì)插補(bǔ)性能的影響較小。

為進(jìn)一步研究α對(duì)插補(bǔ)性能的影響，本文對(duì)50%數(shù)據(jù)缺失率的分類數(shù)據(jù)進(jìn)行實(shí)驗(yàn)，結(jié)果如圖5所示。

圖5 超參數(shù)α 對(duì)數(shù)據(jù)集插補(bǔ)性能的影響Fig.5 Influence of hyperparametric α on imputation performance of datasets

從圖5 可以看出，超參數(shù)α對(duì)于不同數(shù)據(jù)集的影響效果不同，在Class 數(shù)據(jù)集中，當(dāng)α=0.8 時(shí)插補(bǔ)性能最佳且與其他模型有顯著差異；在Abalone 數(shù)據(jù)集中，插補(bǔ)效果受α影響不明顯，當(dāng)α=0.2 時(shí)的插補(bǔ)效果優(yōu)于α=0，當(dāng)α≥0.2 時(shí)改變?chǔ)林挡逖a(bǔ)性能的變化不大。從具體每個(gè)數(shù)據(jù)集的角度分析，當(dāng)α取0.2 時(shí)，所有數(shù)據(jù)集都可以獲得次優(yōu)的插補(bǔ)效果，且均比α取0 的效果更佳。

因此，α的改變不會(huì)使數(shù)據(jù)集插補(bǔ)性能發(fā)生顯著變化，此外，基于實(shí)驗(yàn)結(jié)果將α設(shè)為0.2 更合理。因此，利用修正模型為不可靠樣本生成偽標(biāo)簽數(shù)據(jù)可以有效提高插補(bǔ)性能。

2.2.5 FIB 與DIM 的對(duì)比實(shí)驗(yàn)

DIM［1］利用數(shù)據(jù)集中所有可用信息，經(jīng)濟(jì)、有效、有序、迭代地對(duì)缺失值進(jìn)行插補(bǔ)。

本節(jié)將與DIM 的實(shí)驗(yàn)結(jié)果進(jìn)行對(duì)比，為保證對(duì)比實(shí)驗(yàn)的合理性，在相同的實(shí)驗(yàn)條件下進(jìn)行對(duì)比。

DIM 只適用于離散屬性的分類數(shù)據(jù)集，因此對(duì)數(shù)據(jù)集進(jìn)行離散化操作。DIM 采用C4.5 算法作為插補(bǔ)模型及衡量性能的模型。DIM 的缺失率指樣本缺失率，即缺失率為10%時(shí)期望有10%的樣本發(fā)生缺失。

在采用相同的實(shí)驗(yàn)條件后，本文基于C4.5 及K近鄰插補(bǔ)算法、α=0.2 的FIB 插補(bǔ)器，F(xiàn)IB 與DIM 的對(duì)比效果如表5 所示。

表5 FIB、DIM 的準(zhǔn)確率對(duì)比 Table 5 Accuracy comparison of FIB and DIM %

從表5 可以看出，F(xiàn)IB 的插補(bǔ)性能比DIM 平均相對(duì)提升8.39%。在Wine 數(shù)據(jù)集中，F(xiàn)IB 準(zhǔn)確率的相對(duì)提升最高，達(dá)到16.52%，遠(yuǎn)超出DIM 的插補(bǔ)效果；在balance-scale 數(shù)據(jù)集中，F(xiàn)IB 準(zhǔn)確率的相對(duì)提升最低，為-0.21%，代表FIB 的插補(bǔ)性能略低于DIM。

從時(shí)間成本角度考慮，DIM 的時(shí)間復(fù)雜度與C4.5 決策樹相同，在1.5 節(jié)得知FIB 的時(shí)間復(fù)雜度也與C4.5 決策樹相同，因此，DIM 與FIB 的時(shí)間復(fù)雜度相同，但在具體的執(zhí)行時(shí)間上，F(xiàn)IB 由于額外采用了K 近鄰插補(bǔ)算法，因此與DIM 相比插補(bǔ)速度較慢。

3 結(jié)束語

本文提出基于多模型融合的不完整數(shù)據(jù)分?jǐn)?shù)插補(bǔ)算法FIB。將噪聲標(biāo)簽學(xué)習(xí)引入到空缺值插補(bǔ)任務(wù)中，設(shè)計(jì)新的樣本分?jǐn)?shù)評(píng)估方法，以降低不可靠樣本對(duì)模型的影響。利用偽標(biāo)簽技術(shù)彌補(bǔ)現(xiàn)有算法無法處理高缺失率樣本的局限。實(shí)驗(yàn)結(jié)果表明，該算法與DIM 算法相比平均準(zhǔn)確率相對(duì)提升8.39%，F(xiàn)IB通過多模型融合的方式生成插補(bǔ)結(jié)果，不需要對(duì)缺失數(shù)據(jù)做出任何假設(shè)，適用范圍更廣。后續(xù)將尋找更高效的多模型集成方式，利用諸多最新機(jī)器學(xué)習(xí)及深度學(xué)習(xí)模型生成FIB 插補(bǔ)算法，如CatBoost、LightGBM 及XGBoost。此外，通過合理融合這些更先進(jìn)的算法提高插補(bǔ)性能也是本文研究的重點(diǎn)方向。