基于MCMC方法的區(qū)間控制偽裝缺失值檢測(cè)算法

史金余 孫禹明 謝 兄 劉衛(wèi)江 滕俊凱

(大連海事大學(xué)大學(xué)信息科學(xué)技術(shù)學(xué)院 遼寧 大連 116026)

0 引 言

在大數(shù)據(jù)應(yīng)用快速發(fā)展的今日，臟數(shù)據(jù)漸漸地成為數(shù)據(jù)分析的一大障礙，不僅會(huì)誤導(dǎo)我們的工作行為，還可能造成巨大的經(jīng)濟(jì)損失。為了減少臟數(shù)據(jù)帶來(lái)的嚴(yán)重影響，數(shù)據(jù)清洗在數(shù)據(jù)處理的過(guò)程中起著越來(lái)越重要的作用。數(shù)據(jù)清洗[1]是一個(gè)檢測(cè)、診斷和編輯臟數(shù)據(jù)的過(guò)程。近幾年研究表明，在進(jìn)行數(shù)據(jù)清洗時(shí)，離群點(diǎn)檢測(cè)技術(shù)成為了一種被廣泛應(yīng)用的數(shù)據(jù)識(shí)別技術(shù)，如工業(yè)損傷檢測(cè)[2]、網(wǎng)絡(luò)入侵檢測(cè)[3]、欺詐檢測(cè)[4]、臨床醫(yī)學(xué)檢測(cè)[5]和地質(zhì)探測(cè)[6]等。

為了提高檢測(cè)效率，現(xiàn)在很多研究都對(duì)離群點(diǎn)進(jìn)行了分類(lèi)[7]，在所有類(lèi)中，對(duì)偽裝缺失值的檢測(cè)成為了一個(gè)難題，尤其是在數(shù)據(jù)范圍內(nèi)隨機(jī)分布并在數(shù)據(jù)集中經(jīng)常使用的有效值(以下簡(jiǎn)稱(chēng)有效值類(lèi)偽裝缺失值)。因此在本文主要講解數(shù)據(jù)集中有效值類(lèi)偽裝缺失值的檢測(cè)方法，目前已有很多學(xué)者采用了不同的方法對(duì)偽裝缺失值檢測(cè)問(wèn)題進(jìn)行了相關(guān)研究。Hua等[8-9]提出了DiMaC算法，該算法提出了一種嵌入式無(wú)偏樣本啟發(fā)式算法來(lái)檢測(cè)偽裝缺失值；Pit-Claudel等[10]提出了dBoost算法，該算法利用元組擴(kuò)展來(lái)檢測(cè)各種數(shù)據(jù)集中的離群點(diǎn)；Qahtan等[11]提出了FAHES算法，該算法主要是將偽裝缺失值分成outlier和inlier兩類(lèi)采用不同的方法進(jìn)行檢測(cè)。三種算法中，dBoost算法并非主要檢測(cè)偽裝缺失值，因檢測(cè)范圍過(guò)大，會(huì)檢測(cè)到非偽裝缺失值，而DiMaC算法解決了此問(wèn)題，但其運(yùn)行時(shí)間較長(zhǎng)。FAHES算法進(jìn)行了分類(lèi)檢測(cè)也縮短了運(yùn)行時(shí)間，但由于分類(lèi)不夠細(xì)致，仍然會(huì)有很多種類(lèi)的錯(cuò)誤出現(xiàn)在分類(lèi)之外。對(duì)上述三種算法的研究發(fā)現(xiàn)，其檢測(cè)效果不好的主要原因在于檢測(cè)范圍問(wèn)題。為了提高檢測(cè)效率，本文提出一種基于MCMC方法的區(qū)間控制偽裝缺失值檢測(cè)算法，來(lái)解決檢測(cè)范圍帶來(lái)的麻煩。

在龐大的數(shù)據(jù)集中，為了在進(jìn)行數(shù)據(jù)分析時(shí)取得良好的結(jié)果，非常有必要進(jìn)行偽裝缺失值檢測(cè)，而本文算法主要采用MCMC算法和基于統(tǒng)計(jì)學(xué)的離群點(diǎn)檢測(cè)算法，如果想有效地使用兩種算法將面臨如下挑戰(zhàn)：

(1) 在檢測(cè)中使用對(duì)基于統(tǒng)計(jì)學(xué)的離群點(diǎn)檢測(cè)算法的改進(jìn)來(lái)確定控制區(qū)間進(jìn)行檢測(cè)，但數(shù)據(jù)集中存在異常點(diǎn)，這必然會(huì)導(dǎo)致數(shù)據(jù)集的相關(guān)參數(shù)的變化，直接使用這些參數(shù)必然會(huì)產(chǎn)生一些誤差，因此需要解決如何減少參數(shù)引起的誤差問(wèn)題。

(2) 從檢測(cè)范圍的角度來(lái)提高檢測(cè)效率，主要通過(guò)縮小檢測(cè)范圍來(lái)提高檢測(cè)效率，因此需要解決如何聚焦檢測(cè)范圍的問(wèn)題。

本文主要貢獻(xiàn)是提出一種新的檢測(cè)算法，將MCMC方法和基于統(tǒng)計(jì)學(xué)的離群點(diǎn)檢測(cè)算法進(jìn)行相應(yīng)的改進(jìn)后結(jié)合起來(lái)檢測(cè)，具體如下：

(1) 使用恰當(dāng)?shù)腗CMC方法對(duì)參數(shù)進(jìn)行采樣，以解決由參數(shù)引起的錯(cuò)誤問(wèn)題。在使用MCMC方法時(shí)，選擇了隨機(jī)游走的M-H算法，并對(duì)其進(jìn)行了相應(yīng)的改進(jìn)，使用格里汶科定理和Jeffreys先驗(yàn)方法來(lái)克服求解分布函數(shù)和先驗(yàn)分布函數(shù)的困難。

(2) 使用基于統(tǒng)計(jì)學(xué)的離群點(diǎn)檢測(cè)算法來(lái)解決檢測(cè)范圍的問(wèn)題。在使用基于統(tǒng)計(jì)學(xué)的離群點(diǎn)檢測(cè)算法時(shí)，通過(guò)對(duì)控制區(qū)間進(jìn)行相應(yīng)的改進(jìn)，以此克服區(qū)間過(guò)大等困難。

1 相關(guān)工作

1.1 偽裝缺失值

目前，隨著離群點(diǎn)檢測(cè)技術(shù)的廣泛應(yīng)用，許多研究都是先對(duì)離群點(diǎn)進(jìn)行分類(lèi)后再進(jìn)行檢測(cè)[11-13]，大大提高了檢測(cè)效率。Pearson[14]提出的一個(gè)新出現(xiàn)的數(shù)據(jù)質(zhì)量問(wèn)題——偽裝缺失值，它是一種特殊的缺失數(shù)據(jù)，指的是數(shù)據(jù)條目中不完全缺失但不能反映的值。文獻(xiàn)[14]對(duì)偽裝缺失值的分類(lèi)具體如下：

(1) 超出范圍的數(shù)據(jù)值，例如在只接受負(fù)值的正值的屬性中隱藏缺失的值。

(2) 異常值，例如用非常大的值或非常小的值來(lái)偽裝缺失的值。

(3) 在使用的鍵盤(pán)上具有重復(fù)字符或彼此相鄰的字符，例如用5555555555代替一個(gè)電話(huà)號(hào)碼。

(4) 不協(xié)調(diào)數(shù)據(jù)類(lèi)型的值，例如用數(shù)值偽裝缺失的字符串，反之亦然。

(5) 在數(shù)據(jù)范圍內(nèi)隨機(jī)分布并在數(shù)據(jù)集中經(jīng)常使用的有效值。

在上述每一種情況下，偽裝缺失數(shù)據(jù)都可以被視為outlier(案例(1)-案例(4))或inlier(案例(5))。本文主要講解上述偽裝缺失值的第五種情況的檢測(cè)方法。

1.2 MCMC方法

MCMC方法[15]主要包括Metropolis-Hastings算法(M-H算法)和Gibbs算法。其中M-H算法[16-19]是MCMC方法的核心，主要用于數(shù)據(jù)采樣。算法主要由以下三部分組成：

(1) 從建議分布生成建議(或候選)樣本。

(2) 基于建議分布和聯(lián)合密度，通過(guò)接受函數(shù)計(jì)算接受概率。

(3) 以概率接受建議(候選)樣本，或拒絕該樣本。

建議分布主要分為對(duì)稱(chēng)分布和非對(duì)稱(chēng)分布兩種，如果滿(mǎn)足式(1)，則建議分布為對(duì)稱(chēng)分布，否則為非對(duì)稱(chēng)分布。

q(xi|xi-1)=q(xi-1|xi)

(1)

對(duì)稱(chēng)分布包括高斯分布、以鏈當(dāng)前狀態(tài)為中心的均勻分布等；不對(duì)稱(chēng)分布包括F分布等。

根據(jù)M-H算法的特征，給出了任一分布作為建議分布的似然函數(shù)(密度函數(shù))、先驗(yàn)分布和后驗(yàn)分布。

根據(jù)建議分布，可以得出其先驗(yàn)分布、似然函數(shù)分別為：

fp(xi)=prior(xi)

(2)

fl(xi)=likehood(xi,μ)

(3)

最后，根據(jù)先驗(yàn)分布與似然函數(shù)的乘積確定后驗(yàn)分布：

f(xi)=fp(xi)×fl(xi)=prior(xi)×likehood(xi,μ)

(4)

根據(jù)后驗(yàn)分布函數(shù)，可以得到接受函數(shù)為：

α(xi|xi-1)=min{1,q(xi-1|xi)π(xi)/

q(xi|xi-1)π(xi-1)}

(5)

根據(jù)式(5)，決定接受還是拒絕該樣本。

1.3 基于統(tǒng)計(jì)學(xué)的離群點(diǎn)檢測(cè)算法

離群點(diǎn)檢測(cè)的統(tǒng)計(jì)學(xué)方法[20]的一般思想是：學(xué)習(xí)一個(gè)擬合給定數(shù)據(jù)集的生成模型，然后識(shí)別該模型低概率區(qū)域中的對(duì)象，把它們作為離群點(diǎn)。離群點(diǎn)檢測(cè)的統(tǒng)計(jì)學(xué)方法可以劃分成參數(shù)方法和非參數(shù)方法兩個(gè)主要類(lèi)型，根據(jù)數(shù)據(jù)集以及實(shí)驗(yàn)需求進(jìn)行分析，最終選擇基于正態(tài)分布的一元離群點(diǎn)檢測(cè)方法。

該方法主要分為兩個(gè)步驟：

(1) 利用最大似然函數(shù):

(6)

(7)

(8)

(2) 遍歷樣本集合，檢測(cè)樣本是否落在以下區(qū)間內(nèi):

(9)

該區(qū)間包含了大量的數(shù)據(jù)，所以如果樣本在區(qū)間內(nèi)，則為正常點(diǎn)，否則為離群點(diǎn)。

2 基于MCMC方法的區(qū)間控制偽裝缺失值檢測(cè)算法

由于數(shù)據(jù)集有很多臟數(shù)據(jù)，導(dǎo)致數(shù)據(jù)集的參數(shù)會(huì)發(fā)生變化，如果直接利用參數(shù)對(duì)數(shù)據(jù)集進(jìn)行分析，誤差就會(huì)很大。因此，本文將MCMC方法和基于統(tǒng)計(jì)學(xué)的離群點(diǎn)檢測(cè)算法結(jié)合，提出基于MCMC方法的區(qū)間控制偽裝缺失值檢測(cè)算法。本文的主要工作如下：首先采用M-H算法對(duì)參數(shù)進(jìn)行采樣，然后根據(jù)采樣出來(lái)的參數(shù)通過(guò)基于正態(tài)分布的一元離群點(diǎn)檢測(cè)算法選取控制區(qū)間對(duì)數(shù)據(jù)樣本進(jìn)行遍歷。算法的主要步驟如圖1所示。

圖1 本文方法的主要步驟

2.1 高頻率偽裝缺失值

為了使檢測(cè)效果得到較好的改善，對(duì)1.1節(jié)中的偽裝缺失值進(jìn)行了進(jìn)一步分類(lèi)處理。以data.gov.uk數(shù)據(jù)集中Accident表中的部分?jǐn)?shù)據(jù)為例來(lái)說(shuō)明1.1節(jié)中偽裝缺失值的第五種類(lèi)型，如表1所示。

表1 data.gov.uk數(shù)據(jù)集中Accident表

可以看出，在Date列和Time列中，它們的值全部為01/01/2015和00:00，數(shù)據(jù)類(lèi)型完全符合數(shù)據(jù)屬性，完全發(fā)現(xiàn)不了是錯(cuò)誤值。但當(dāng)與真實(shí)數(shù)據(jù)進(jìn)行對(duì)比時(shí)，會(huì)發(fā)現(xiàn)數(shù)據(jù)值是錯(cuò)誤的，這種就是在數(shù)據(jù)范圍內(nèi)隨機(jī)分布并在數(shù)據(jù)集中經(jīng)常使用的有效值(第五類(lèi))。此種偽裝缺失值給檢測(cè)工作帶來(lái)了巨大困難，它以一定的概率出現(xiàn)在正確值中，不容易被檢測(cè)到。因此本文主要對(duì)該種偽裝缺失值進(jìn)行講解，并重新命名為高頻率偽裝缺失值。

2.2 參數(shù)采樣的方法(MCMC方法的改進(jìn))

當(dāng)使用MCMC方法時(shí)，選擇的是M-H算法。M-H算法主要分為獨(dú)立抽樣的M-H算法、單變量的M-H算法和隨機(jī)游走的M-H算法，其中隨機(jī)游走的M-H算法[19]是MCMC方法中應(yīng)用最廣泛的一種算法，通用性比較強(qiáng)，任何一種對(duì)稱(chēng)分布都可以作為該算法的建議分布，由此產(chǎn)生的馬爾可夫鏈通常是遍歷的，所以本文選用的是隨機(jī)游走的M-H算法。

在使用隨機(jī)游走M(jìn)-H算法時(shí)，最困難的問(wèn)題是求數(shù)據(jù)集的概率密度函數(shù)和后驗(yàn)分布函數(shù)。為了解決這兩個(gè)問(wèn)題，本文的方法如下：

(1) 利用經(jīng)驗(yàn)分布函數(shù)和格里汶科定理確定分布函數(shù)，進(jìn)而得到概率密度函數(shù)。

(2) 統(tǒng)一利用Jeffreys先驗(yàn)確定方法確定先驗(yàn)分布函數(shù)，得到后驗(yàn)分布函數(shù)和接受函數(shù)。

接下來(lái)，以高斯分布為例來(lái)講述求解改進(jìn)的M-H算法執(zhí)行的主要過(guò)程，即參數(shù)采樣的主要過(guò)程。

Step1經(jīng)驗(yàn)分布函數(shù)。

定理1(格里汶科定理[21]) 設(shè)x1,x2,…,xn是取自樣本總體分布函數(shù)為F(x)的樣本，F(xiàn)n(x)是其經(jīng)驗(yàn)分布函數(shù)，當(dāng)時(shí)n→∞，有：

(10)

定理1表明，當(dāng)n相當(dāng)大時(shí)，經(jīng)驗(yàn)分布函數(shù)Fn(x)是總體分布函數(shù)F(x)的一個(gè)良好的近似。

在求概率密度函數(shù)時(shí)，首先求出了經(jīng)驗(yàn)分布函數(shù)，由于數(shù)據(jù)量比較大，根據(jù)格里汶科定理，由經(jīng)驗(yàn)分布函數(shù)近似得到了分布函數(shù)，進(jìn)而通過(guò)分布函數(shù)得到了數(shù)據(jù)集的概率密度函數(shù)。

Step2建議分布。

在使用M-H算法時(shí)，首先需要確定建議分布類(lèi)型，然后根據(jù)建議分布的不同類(lèi)型，進(jìn)行求解。

假設(shè)樣本服從高斯分布：

xi～N(μ,σ2)

(11)

進(jìn)而可以得出其密度函數(shù)：

(12)

然后，根據(jù)密度函數(shù)可以得到似然函數(shù)：

(13)

Step3先驗(yàn)分布函數(shù)。

先驗(yàn)分布函數(shù)的求解采用的是Jeffreys先驗(yàn)確定方法[22]。首先，對(duì)樣本的似然函數(shù)取對(duì)數(shù)：

(14)

l(μ;σ2)=lnL(μ,σ2)=-n/2ln(2π)-

(15)

然后，求Fisher信息矩陣：

(16)

采用E(·)矩母函數(shù)方法[23]進(jìn)行求解式(17)。

(17)

解得：

(18)

所以：

detI(μ;σ)=2n2σ-4

(19)

最后，根據(jù)先驗(yàn)分布函數(shù)的求解公式：

π(θ)=[detI(θ)]1/2

(20)

解得樣本的先驗(yàn)分布函數(shù)為：

(21)

Step4后驗(yàn)分布函數(shù)。

根據(jù)似然函數(shù)和先驗(yàn)分布函數(shù)的乘積，得出后驗(yàn)分布函數(shù)：

(22)

Step5接受函數(shù)。

為了簡(jiǎn)化計(jì)算，方便對(duì)接受函數(shù)進(jìn)行化簡(jiǎn)，在此考慮建議分布是否為對(duì)稱(chēng)分布，主要采用偏度來(lái)進(jìn)行判斷，具體如下。

偏度[23]是樣本數(shù)據(jù)分布偏斜方向和程度度量，是樣本數(shù)據(jù)分布非對(duì)稱(chēng)程度的數(shù)字特征，計(jì)算公式為：

sk=E[(x-μ)3]/σ3

(23)

(1) 當(dāng)sk=0，樣本數(shù)據(jù)為對(duì)稱(chēng)分布。

(2) 當(dāng)sk≠0，樣本數(shù)據(jù)為非對(duì)稱(chēng)分布，如果sk>0,樣本數(shù)據(jù)為右偏，sk<0樣本數(shù)據(jù)為左偏。

如果建議分布是對(duì)稱(chēng)分布，根據(jù)式(1)，可以將接受函數(shù)簡(jiǎn)化為：

α(xi|xi-1)=min{1,π(xi)/π(xi-1)}

(24)

最后，根據(jù)接受函數(shù)，來(lái)決定接受還是拒絕樣本。

2.3 控制區(qū)間的確定方法(基于統(tǒng)計(jì)學(xué)的離群點(diǎn)檢測(cè)算法的改進(jìn))

本文主要檢測(cè)高頻率偽裝缺失值，因此本文根據(jù)M-H算法傳過(guò)來(lái)的參數(shù)，對(duì)基于統(tǒng)計(jì)學(xué)的離群點(diǎn)檢測(cè)算法進(jìn)行反向應(yīng)用，并對(duì)控制區(qū)間進(jìn)行改進(jìn)，將一個(gè)大區(qū)間分成幾個(gè)小區(qū)間的并集來(lái)控制數(shù)據(jù)遍歷，進(jìn)而提高檢測(cè)效率。

具體方法如下：

Step6控制區(qū)間。

根據(jù)M-H算法所采樣到的參數(shù)，確定兩個(gè)區(qū)間：式(9)和式(25)。

(25)

第一個(gè)區(qū)間為根據(jù)基于統(tǒng)計(jì)學(xué)的離群點(diǎn)檢測(cè)算法確定的區(qū)間，第二個(gè)區(qū)間為置信區(qū)間[21]，置信度越大，置信區(qū)間越寬，通過(guò)調(diào)整置信度，控制區(qū)間，詳細(xì)說(shuō)明如下：

當(dāng)樣本x分布未知，但樣本數(shù)據(jù)較大時(shí)，根據(jù)中心極限定理，它可以近似為：

(26)

當(dāng)σ2已知時(shí)，則μ的置信度為1-α的置信區(qū)間為：

(27)

當(dāng)確定了兩個(gè)區(qū)間時(shí)，通過(guò)分析這兩個(gè)區(qū)間，發(fā)現(xiàn)區(qū)間如式(9)包含的數(shù)據(jù)樣本多于區(qū)間如式(28)的。

(28)

因此，將區(qū)間拆分成多個(gè)小區(qū)間并集，表示為：

(29)

確定小區(qū)間后，判定是否處于這些區(qū)間內(nèi)：

(30)

如果一個(gè)數(shù)據(jù)樣本處于上述區(qū)間(式(30))中，則為高頻率偽裝缺失值，否則為正確值。

通過(guò)對(duì)各種分布的分析，對(duì)高斯分布的計(jì)算一目了然。這里以高斯分布為例進(jìn)行說(shuō)明。

當(dāng)樣本分布為高斯分布時(shí)，區(qū)間式(9)將包含99.7%的正確數(shù)據(jù)，區(qū)間式(28)將包含95%的正確數(shù)據(jù)，因此區(qū)間式(9)比區(qū)間式(28)包含更多的數(shù)據(jù)。為了提高算法的精確度，根據(jù)數(shù)據(jù)樣本分布不同，通過(guò)設(shè)置不同的置信度來(lái)控制控制區(qū)間，其中不規(guī)格分布置信度設(shè)置為75%，規(guī)格分布置信度設(shè)置為85%(包括正態(tài)分布、卡方分布、t分布等)。

2.4 算法描述

首先通過(guò)改進(jìn)的M-H算法對(duì)參數(shù)進(jìn)行采樣；然后根據(jù)改進(jìn)的M-H算法傳過(guò)來(lái)的參數(shù)，通過(guò)改進(jìn)的基于統(tǒng)計(jì)學(xué)的離群點(diǎn)檢測(cè)方法確定控制區(qū)間式(31)。最后，在控制區(qū)間式(31)內(nèi)，對(duì)數(shù)據(jù)對(duì)象進(jìn)行遍歷。本文主要檢測(cè)高頻率偽裝缺失值，如果數(shù)據(jù)對(duì)象在控制區(qū)間內(nèi)，則判定為高頻率偽裝缺失值；否則，判定為正常值。算法執(zhí)行過(guò)程如算法1所示。

算法1本文算法

輸入：數(shù)據(jù)集X中的數(shù)據(jù)對(duì)象x。

輸出：數(shù)據(jù)集X中偽裝缺失值集合G。

1.forxinXdo

2.根據(jù)Jeffreys先驗(yàn)確定方法計(jì)算數(shù)據(jù)對(duì)象x的先驗(yàn)分布函數(shù)；

3.根據(jù)式(22)計(jì)算數(shù)據(jù)對(duì)象x的后驗(yàn)分布函數(shù)；

4.根據(jù)式(5)計(jì)算數(shù)據(jù)對(duì)象x的接受函數(shù)；

5.根據(jù)式(31)計(jì)算數(shù)據(jù)對(duì)象x的控制區(qū)間；

6.ifx∈區(qū)間式(31)

7.將數(shù)據(jù)對(duì)象x添加到偽裝缺失值集合G中；

8.end if

9.end for

10.輸出高頻率偽裝缺失值集合G

3 實(shí)驗(yàn)驗(yàn)證

3.1 相關(guān)定義

為了能夠明顯地看出實(shí)驗(yàn)效果，定義了三個(gè)評(píng)價(jià)指標(biāo)，即查準(zhǔn)率(precision)、查全率(recall)和F1-Measure。設(shè)輸入的樣本總數(shù)量為m，輸出的高頻率偽裝缺失值的數(shù)量為n，檢測(cè)到的高頻率偽裝缺失值的數(shù)量為o。具體計(jì)算公式如下：

(1) 查準(zhǔn)率(precision)，記為P：

P=o/n

(31)

(2) 查全率(recall)，記為R：

R=o/m

(32)

(3) F1-Measure，記為F1：

F1=(2PR)/(P+R)

(33)

相對(duì)而言，如果算法的查準(zhǔn)率、查全率和F1-Measure都比較高，則證明該算法優(yōu)于其他算法，具有良好的可用性。

3.2 數(shù)據(jù)集選擇

為了驗(yàn)證算法的檢測(cè)效果，并考慮到數(shù)據(jù)分析在各個(gè)領(lǐng)域的責(zé)任的重要性，本文選擇Mass.gov數(shù)據(jù)存儲(chǔ)庫(kù)中3張表、UCI-ML數(shù)據(jù)存儲(chǔ)庫(kù)中4張表和Data.gov.uk數(shù)據(jù)存儲(chǔ)庫(kù)中6張表，共13個(gè)數(shù)據(jù)集進(jìn)行比較實(shí)驗(yàn)，主要涉及醫(yī)療、交通和教育等領(lǐng)域。在進(jìn)行實(shí)驗(yàn)前手工注釋了每個(gè)數(shù)據(jù)集中的高頻率偽裝缺失值。

3.3 實(shí)驗(yàn)對(duì)比

實(shí)驗(yàn)從四個(gè)方面測(cè)試了本文算法：Ex-1：算法的效率(查準(zhǔn)率、查全率和F1-Measure)；Ex-2：與dBoost算法的比較；Ex-3：與DiMaC算法的比較；Ex-4：與FAHES算法的比較(Random DMVs)；Ex-5：與k均值聚類(lèi)算法的比較(KMOR算法)。

(1) Ex-1：算法的效率(查準(zhǔn)率、查全率和F1-Measure)。為了驗(yàn)證本文算法的效率，在Mass.gov、UCI-ML和Data.gov.uk三個(gè)數(shù)據(jù)存儲(chǔ)庫(kù)中所選擇的數(shù)據(jù)集上進(jìn)行了相應(yīng)的實(shí)驗(yàn)。為了方便進(jìn)行實(shí)驗(yàn)，首先通過(guò)數(shù)據(jù)樣本映射的方式對(duì)數(shù)據(jù)集進(jìn)行分析，通過(guò)分析得到data.gov.uk數(shù)據(jù)存儲(chǔ)庫(kù)上所選擇的數(shù)據(jù)集呈正態(tài)分布，Mass.gov和UCL-ML數(shù)據(jù)存儲(chǔ)庫(kù)上所選擇的數(shù)據(jù)呈不規(guī)則的分布。通過(guò)對(duì)數(shù)據(jù)集的分析，可以知道在data.gov.uk數(shù)據(jù)存儲(chǔ)庫(kù)上所選擇的數(shù)據(jù)集進(jìn)行實(shí)驗(yàn)會(huì)比較容易些，可以直接得到數(shù)據(jù)樣本的概率密度函數(shù)，根據(jù)概率密度函數(shù)求出似然函數(shù)，再根據(jù)似然函數(shù)求出先驗(yàn)分布函數(shù)，在進(jìn)行求解先驗(yàn)分布函數(shù)時(shí)，由于數(shù)據(jù)樣本所屬分布不同，求解先驗(yàn)分布函數(shù)不夠準(zhǔn)確，導(dǎo)致實(shí)驗(yàn)效果不好，而本文所采用Jeffreys先驗(yàn)確定方法，它在不同分布中無(wú)信息即可確定先驗(yàn)分布函數(shù)，提高了檢測(cè)效率和算法執(zhí)行所用的時(shí)間。根據(jù)似然函數(shù)和先驗(yàn)分布函數(shù)計(jì)算出后驗(yàn)分布函數(shù)和接受函數(shù)，并通過(guò)接受函數(shù)得到所需要的樣本均值和樣本方差，并將置信度設(shè)置為85%，最后通過(guò)區(qū)間式(9)和區(qū)間式(28)確定區(qū)間并在區(qū)間內(nèi)對(duì)數(shù)據(jù)樣本進(jìn)行遍歷。而Mass.gov和UCL-ML數(shù)據(jù)存儲(chǔ)庫(kù)上所選擇的數(shù)據(jù)集呈不規(guī)則分布，無(wú)法直接計(jì)算出概率密度函數(shù)，導(dǎo)致無(wú)法進(jìn)行實(shí)驗(yàn)，而經(jīng)驗(yàn)分布函數(shù)和定理確定其分布函數(shù)，進(jìn)而可以得到概率密度函數(shù)，然后一步步求出似然函數(shù)、先驗(yàn)分布函數(shù)、后驗(yàn)分布函數(shù)、接受函數(shù)，并通過(guò)接受函數(shù)得到所需要的樣本均值和樣本方差，由于是不規(guī)則分布，因此將置信度設(shè)置為75%，最后結(jié)合區(qū)間式(9)和區(qū)間式(28)所確定遍歷區(qū)間對(duì)數(shù)據(jù)樣本進(jìn)行遍歷。

因?yàn)楸疚乃惴ㄋ鶛z測(cè)的目標(biāo)是高頻率偽裝缺失值，它通常偽裝成正確的值并以較高的頻率(出現(xiàn)頻率低于正常值的概率)出現(xiàn)在數(shù)據(jù)集中，用以往的離群點(diǎn)檢測(cè)算法或偽裝缺失值檢測(cè)算法進(jìn)行檢測(cè)結(jié)果不盡人意，因?yàn)樗鼈兯軝z測(cè)到的僅僅是離群點(diǎn)或低頻率偽裝缺失值，而高頻率偽裝缺失值常常被誤認(rèn)為正常值檢測(cè)不到。而本文算法通過(guò)區(qū)間式(9)和區(qū)間式(28)確定了區(qū)間式(31)，即控制區(qū)間，縮小了檢測(cè)范圍。讓數(shù)據(jù)樣本在控制區(qū)間內(nèi)進(jìn)行遍歷，如果數(shù)據(jù)樣本在控制區(qū)間內(nèi)，則可以找出高頻率偽裝缺失值。

遍歷數(shù)據(jù)樣本結(jié)束后，根據(jù)式(27)和式(28)，求出本文算法在Mass.gov、Data.gov.uk和UCI-ML三個(gè)數(shù)據(jù)存儲(chǔ)庫(kù)中13個(gè)數(shù)據(jù)集的平均查全率和平均查準(zhǔn)率，如表2所示。

表2 三個(gè)數(shù)據(jù)存儲(chǔ)庫(kù)上的查準(zhǔn)率、查全率和F1-Measure

(2) Ex-2：與dBoost算法的比較。dBoost算法并非為離群點(diǎn)檢測(cè)而設(shè)計(jì)，進(jìn)行檢測(cè)時(shí)檢測(cè)到非偽裝缺失值，導(dǎo)致檢測(cè)效果較差，而本文算法通過(guò)對(duì)控制區(qū)間的改進(jìn)，縮小了檢測(cè)范圍，為檢測(cè)偽裝缺失值所設(shè)計(jì)，通過(guò)表3中的對(duì)比可以看出，本文算法的查全率提高了很多。

表3 與dBoost算法的對(duì)比

(3) Ex-3：與DiMaC算法的比較。DiMaC算法主要檢測(cè)偽裝缺失值，但是它沒(méi)有對(duì)偽裝缺失值進(jìn)行分類(lèi)，導(dǎo)致其檢測(cè)范圍太大，檢測(cè)效率差，而本文算法對(duì)偽裝缺失值進(jìn)行了分類(lèi)并且取得較好的檢測(cè)效果。檢測(cè)效果對(duì)比如表4所示。

表4 與DiMaC算法的對(duì)比

(4) Ex-4：與FAHES算法的比較(Random DMVs)。因?yàn)镕AHES算法是對(duì)偽裝缺失值分類(lèi)后進(jìn)行檢測(cè)，所以它要優(yōu)于前兩種算法，但是由于分類(lèi)不夠細(xì)致，仍然會(huì)有很多的錯(cuò)誤值出現(xiàn)在分類(lèi)之外，導(dǎo)致檢測(cè)效果略差，而本文算法的檢測(cè)目標(biāo)明確，主要檢測(cè)高頻率偽裝缺失值，檢測(cè)效果有很大的改善，如表5所示。

表5 與FAHES算法的對(duì)比

(5) Ex-5：與k均值聚類(lèi)算法的比較(KMOR算法)。為了驗(yàn)證本文算法的權(quán)威性，選擇了Gan等[26]優(yōu)化的KMOR算法。由于本文主要檢測(cè)高頻率偽裝缺失值，KMOR算法可能將所有偽裝缺失值視為一個(gè)較大的簇，并將它們視為正常值，導(dǎo)致檢測(cè)效果差。比較結(jié)果如表6所示，通過(guò)對(duì)查準(zhǔn)率、查全率和F1-Measure的比較，本文算法的檢測(cè)效果明顯優(yōu)于KMOR算法。

表6 與KMOR算法的對(duì)比

根據(jù)表3-表6中在Mass.gov、Data.gov.uk和UCI-ML三個(gè)數(shù)據(jù)存儲(chǔ)庫(kù)中查全率、查準(zhǔn)率和F1-Measure的對(duì)比，繪制了對(duì)比圖，如圖2-圖4所示?？梢钥闯?，本文算法優(yōu)于其他四種算法。

圖2 五種算法的查準(zhǔn)率對(duì)比

圖3 五種算法的查全率對(duì)比

圖4 五種算法的F1-Measure對(duì)比

4 結(jié) 語(yǔ)

本文主要是解決檢測(cè)高頻率偽裝缺失值的問(wèn)題，為此本文提出基于MCMC方法的區(qū)間控制偽裝缺失值檢測(cè)算法，將改進(jìn)的MCMC方法和改進(jìn)的基于統(tǒng)計(jì)學(xué)的離群點(diǎn)檢測(cè)算法結(jié)合在一起進(jìn)行檢測(cè)。首先采用改進(jìn)的MCMC方法對(duì)樣本進(jìn)行參數(shù)采樣，然后根據(jù)采樣所得的參數(shù)采用改進(jìn)的基于統(tǒng)計(jì)學(xué)的離群點(diǎn)檢測(cè)算法確定控制區(qū)間，最后在確定的控制區(qū)間里對(duì)數(shù)據(jù)樣本進(jìn)行遍歷。此外，利用Mass.gov、UCL-ML和Data.gov.uk三個(gè)數(shù)據(jù)存儲(chǔ)庫(kù)中的數(shù)據(jù)集進(jìn)行對(duì)比實(shí)驗(yàn)，驗(yàn)證算法的權(quán)威性，通過(guò)實(shí)驗(yàn)結(jié)果可以看出，本文算法的查準(zhǔn)率、查全率和F1-Measure有了明顯改善。下一步，本文的工作將主要側(cè)重于解決如何檢測(cè)低概率的有效值類(lèi)偽裝缺失值，進(jìn)一步提高算法的檢測(cè)效果。