基于二進(jìn)制位運(yùn)算的不完整數(shù)據(jù)分類(lèi)與檢測(cè)

郭強(qiáng) 魏建宇 馬文彬

陸軍軍事交通學(xué)院/基礎(chǔ)部 天津 300161

引言

數(shù)據(jù)是否完整，數(shù)據(jù)是否明確，數(shù)據(jù)是否有意義，數(shù)據(jù)是否正確是真實(shí)世界系統(tǒng)狀態(tài)映射到信息系統(tǒng)的四個(gè)問(wèn)題[1]。其中，作為數(shù)據(jù)質(zhì)量重要維度之一的數(shù)據(jù)完整性在大多數(shù)情況下會(huì)直接影響其他3個(gè)維度的狀態(tài)。

周金陵等人指出用含有缺失值的數(shù)據(jù)做信息共享、統(tǒng)計(jì)分析和決策支持可能會(huì)產(chǎn)生嚴(yán)重問(wèn)題[2]。其原因：含缺失值的樣本數(shù)據(jù)只能提供不完整信息，數(shù)據(jù)表現(xiàn)出顯著的不確定性，數(shù)據(jù)蘊(yùn)含的確定性成分難以把握，降低了數(shù)據(jù)的有效性；數(shù)據(jù)分析常采用刪除含缺失值記錄的方法來(lái)處理樣本數(shù)據(jù)，當(dāng)缺失數(shù)據(jù)占比較高時(shí)，會(huì)造成數(shù)據(jù)資源浪費(fèi)，導(dǎo)致數(shù)據(jù)分析任務(wù)不精準(zhǔn)，產(chǎn)生錯(cuò)誤的分析結(jié)果。

缺失值的檢測(cè)、分類(lèi)和估計(jì)填充是數(shù)據(jù)清洗的3個(gè)步驟。在對(duì)缺失數(shù)據(jù)進(jìn)行估計(jì)填充之前，首先要完成缺失值的檢測(cè)與分類(lèi)，從而針對(duì)不同的缺失值類(lèi)型選擇恰當(dāng)?shù)墓烙?jì)填充算法。本文采用一種基于二進(jìn)制位運(yùn)算的不完整數(shù)據(jù)分類(lèi)與檢測(cè)方法，通過(guò)對(duì)不完整數(shù)據(jù)分類(lèi)檢測(cè)，提高不完整數(shù)據(jù)處理的準(zhǔn)確性和效率。

1 研究對(duì)象及其分類(lèi)

1.1 研究對(duì)象的界定

關(guān)系數(shù)據(jù)集不完整分為表缺失、空表和表不完整3種情況，其中表不完整又可分為記錄缺失、空記錄和記錄不完整3種情況。記錄缺失是關(guān)系數(shù)據(jù)表沒(méi)有記錄；空記錄是創(chuàng)建關(guān)系數(shù)據(jù)表時(shí)產(chǎn)生的記錄只含有主鍵等生成字段值，其余字段為空字段；記錄不完整既包括字段值為空值的空字段情況，又包括字段值內(nèi)容不完整的字段不完整情況，如姓名字段只填寫(xiě)姓氏沒(méi)填寫(xiě)名字，本論文只討論空字段情況。

關(guān)系數(shù)據(jù)集由數(shù)據(jù)表組成，每張數(shù)據(jù)表又包含一條或多條記錄，而記錄是由若干字段組成，字段是關(guān)系數(shù)據(jù)表操作的基本單位，也是數(shù)據(jù)對(duì)象完整性描述的基本單位。因此，關(guān)系數(shù)據(jù)集的不完整主要探討的是因字段缺失造成的記錄不完整。

不完整記錄是含缺失字段的記錄，分為空記錄和字段缺失的記錄。不完整記錄以及空字段都稱(chēng)為缺失數(shù)據(jù)，缺失數(shù)據(jù)中未填寫(xiě)的字段值稱(chēng)為缺失值。

1.2 研究對(duì)象的分類(lèi)

不完整記錄檢測(cè)首要應(yīng)區(qū)分完整記錄和不完整記錄，然后將不完整記錄進(jìn)一步區(qū)分為不完整合格記錄、不完整修正記錄以及不完整刪除記錄三類(lèi)。

完整記錄是記錄中沒(méi)有空字段的記錄；不完整合格記錄區(qū)分為兩種情況，第一種情況是記錄準(zhǔn)完整即記錄中雖然存在空字段但對(duì)于對(duì)象描述的完整性沒(méi)有影響，第二種情況是記錄中除不影響當(dāng)前應(yīng)用的關(guān)鍵字段無(wú)空字段外存在缺失值；不完整修正記錄是記錄中某些空字段需進(jìn)行估計(jì)填充后才不影響對(duì)象描述的完整性或不影響當(dāng)前應(yīng)用的不完整記錄；不完整刪除記錄包括空記錄、有價(jià)值字段為空無(wú)實(shí)際意義的無(wú)效記錄以及不可修正字段過(guò)多無(wú)修正價(jià)值的記錄3種情況。

文獻(xiàn)綜述針對(duì)不完整記錄做如下處理：不完整合格記錄的空字段填充N(xiāo)ull值[3]；不完整修正記錄依據(jù)缺失字段類(lèi)型選擇合適的缺失值估計(jì)填充算法進(jìn)行修正[4-7]；不完整刪除記錄采用級(jí)聯(lián)刪除，實(shí)現(xiàn)邏輯刪除本條記錄。為保證數(shù)據(jù)操作的可追溯性和數(shù)據(jù)的可恢復(fù)性，數(shù)據(jù)清洗的所有操作都必須有良好的數(shù)據(jù)溯源和數(shù)據(jù)世系設(shè)計(jì)。

2 研究對(duì)象表示及其分類(lèi)檢測(cè)方法

2.1 研究對(duì)象的二進(jìn)制位表示

不完整記錄檢測(cè)、分類(lèi)和修正需要對(duì)記錄的不完整信息進(jìn)行描述，本文采用記錄二進(jìn)制位表示方法對(duì)記錄的不完整信息進(jìn)行描述。

設(shè)某關(guān)系數(shù)據(jù)表有m個(gè)字段，n條記錄，記錄ri，i=1,2,…,n的字段記為aij，j=1,2,…,m，記錄ri的二進(jìn)制位表示為Bi=bi1bi2…bim。若aij非空時(shí)，bij=1；aij為空時(shí)，bij=0。

2.2 研究對(duì)象的二進(jìn)制位運(yùn)算分類(lèi)檢測(cè)方法

不完整記錄的二進(jìn)制位運(yùn)算分類(lèi)檢測(cè)方法，首先生成各類(lèi)標(biāo)準(zhǔn)記錄的二進(jìn)制位表示集，然后將待檢記錄的二進(jìn)制位表示與各類(lèi)標(biāo)準(zhǔn)記錄的二進(jìn)制位表示進(jìn)行按位異或運(yùn)算。

2.2.1 標(biāo)準(zhǔn)記錄的二進(jìn)制位表示集生成。直接生成法和樣本生成法是生成各類(lèi)標(biāo)準(zhǔn)記錄二進(jìn)制位表示集的兩種方法。直接生成法即根據(jù)關(guān)系數(shù)據(jù)表2m個(gè)或所有可能出現(xiàn)記錄生成各類(lèi)標(biāo)準(zhǔn)記錄的二進(jìn)制位表示。由于數(shù)據(jù)表的不完整記錄的缺失字段具有一定分布規(guī)律，因此直接生成法在分類(lèi)檢測(cè)初期會(huì)產(chǎn)生大量的冗余表示和冗余運(yùn)算。樣本生成法即根據(jù)關(guān)系表的記錄樣本生成各類(lèi)標(biāo)準(zhǔn)記錄二進(jìn)制位表示集，并根據(jù)記錄二進(jìn)制位表示出現(xiàn)次數(shù)的多少確定該位表示在相應(yīng)類(lèi)的檢測(cè)優(yōu)先級(jí)。樣本生成法在分類(lèi)檢測(cè)初期可能會(huì)出現(xiàn)不能識(shí)別記錄二進(jìn)制位表示的情況，對(duì)新出現(xiàn)的記錄二進(jìn)制位表示需添加到相應(yīng)類(lèi)標(biāo)準(zhǔn)記錄二進(jìn)制位表示集，該方法具有實(shí)現(xiàn)簡(jiǎn)單、效率高的特點(diǎn)，本文采用樣本生成法生成各類(lèi)標(biāo)準(zhǔn)記錄的二進(jìn)制位表示集，步驟（1）～（5）如下：

步驟（2）Bik記為第k類(lèi)一條不完整記錄樣本二進(jìn)制位表示，通過(guò)Bik和Gk的元素gkl異或運(yùn)算，檢測(cè)Gk中是否已經(jīng)存在Bik二進(jìn)制位表示，若存在Bik則出現(xiàn)次數(shù)加1，否則將Bik添加到相應(yīng)Gk類(lèi)并記出現(xiàn)次數(shù)為1，算法描述如下：

?

步驟（3）G4中因某幾個(gè)有價(jià)值字段（如第s、t位字段）缺失，影響當(dāng)前應(yīng)用而需刪除該記錄的規(guī)則為Bi＆Bj=0，其中，Bj為除第s、t位為1外其余位均為0的m位二進(jìn)制數(shù)。實(shí)際應(yīng)用中可以有多個(gè)如Bj形式的二進(jìn)制數(shù)。

步驟（5）除G4將步驟（4）設(shè)為最高優(yōu)先級(jí)，步驟（3）設(shè)為次優(yōu)先級(jí)外，Gk按標(biāo)準(zhǔn)記錄二進(jìn)制位表示出現(xiàn)次數(shù)多少確定優(yōu)先級(jí)。

2.2.2 不完整記錄的位運(yùn)算分類(lèi)檢測(cè)。設(shè)待檢記錄ri，首先求取其二進(jìn)制位表示Bi，然后按類(lèi)進(jìn)行決策判定，在每一類(lèi)決策節(jié)點(diǎn)，按照標(biāo)準(zhǔn)記錄二進(jìn)制位表示的優(yōu)先級(jí)順序逐一進(jìn)行異或操作，若運(yùn)算結(jié)果為零，判定該記錄屬于此類(lèi)別，輸出檢測(cè)結(jié)果，算法停止；若未檢出記錄二進(jìn)制位表示，需人工判定記錄類(lèi)別，并將其作為標(biāo)準(zhǔn)記錄二進(jìn)制位表示添加到相應(yīng)類(lèi)的二進(jìn)制位表示集，如圖1所示。

圖1 不完整記錄分類(lèi)檢測(cè)流程

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

實(shí)例驗(yàn)證所采用的數(shù)據(jù)是我國(guó)北方某城市交通監(jiān)控系統(tǒng)的駕駛員數(shù)據(jù)表，該表有16個(gè)字段，首先從數(shù)據(jù)表的記錄樣本中選取不完整合格記錄、不完整修正記錄和不完整刪除記錄各50條按樣本生成法生成標(biāo)準(zhǔn)記錄二進(jìn)制位表示集，并用步驟（3）、步驟（4）對(duì)不完整刪除記錄標(biāo)準(zhǔn)二進(jìn)制位表示集進(jìn)行代替，然后從表任一位置開(kāi)始連續(xù)取5000條樣本按照?qǐng)D1所示的流程進(jìn)行不完整記錄分類(lèi)檢測(cè)。生成的標(biāo)準(zhǔn)記錄二進(jìn)制位表示集、分類(lèi)檢測(cè)過(guò)程中未檢出的二進(jìn)制位表示數(shù)以及檢測(cè)結(jié)果如表1所示。

表1 標(biāo)準(zhǔn)記錄二進(jìn)制位表示集與檢測(cè)結(jié)果

由上表可知，不完整記錄占總記錄的63.52%，說(shuō)明由于空字段導(dǎo)致數(shù)據(jù)表存在不完整記錄是普遍存在的。但只需對(duì)占總記錄56.94%的不完整合格記錄的空字段做相應(yīng)標(biāo)識(shí)，不需要修正，便可正常使用；總記錄中6.02%的不完整修正記錄需要依據(jù)缺失字段類(lèi)型選擇合適的缺失值估計(jì)填充算法進(jìn)行修正；做刪除處理的不完整刪除記錄占總記錄的0.56%。

在5000條樣本記錄分類(lèi)檢測(cè)過(guò)程中，未檢出二進(jìn)制位表示總共出現(xiàn)28個(gè)，將他們分別添加到相應(yīng)類(lèi)標(biāo)準(zhǔn)記錄二進(jìn)制位表示集，再?gòu)臄?shù)據(jù)表中另連續(xù)選取5000條記錄樣本進(jìn)行分類(lèi)檢測(cè)，未檢出二進(jìn)制位表示沒(méi)有再出現(xiàn)。

4 結(jié)束語(yǔ)

基于二進(jìn)制位運(yùn)算的不完整數(shù)據(jù)分類(lèi)檢測(cè)方法，以二進(jìn)制位運(yùn)算為基礎(chǔ)，首先按照不完整記錄層次分類(lèi)方法實(shí)現(xiàn)待檢記錄二進(jìn)制位表示層次分類(lèi)，避免了各類(lèi)之間的相互沖突，同時(shí)不破壞待檢記錄的二進(jìn)制位表示，然后根據(jù)記錄樣本生成標(biāo)準(zhǔn)記錄二進(jìn)制位表示集并依據(jù)記錄二進(jìn)制位表示的檢測(cè)優(yōu)先級(jí)進(jìn)行異或檢測(cè)，減少了表示冗余和運(yùn)算冗余，提高運(yùn)算效率。