基于二進制位運算的不完整數據分類與檢測

郭強 魏建宇 馬文彬

陸軍軍事交通學院/基礎部 天津 300161

引言

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

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

缺失值的檢測、分類和估計填充是數據清洗的3個步驟。在對缺失數據進行估計填充之前，首先要完成缺失值的檢測與分類，從而針對不同的缺失值類型選擇恰當的估計填充算法。本文采用一種基于二進制位運算的不完整數據分類與檢測方法，通過對不完整數據分類檢測，提高不完整數據處理的準確性和效率。

1 研究對象及其分類

1.1 研究對象的界定

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

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

不完整記錄是含缺失字段的記錄，分為空記錄和字段缺失的記錄。不完整記錄以及空字段都稱為缺失數據，缺失數據中未填寫的字段值稱為缺失值。

1.2 研究對象的分類

不完整記錄檢測首要應區(qū)分完整記錄和不完整記錄，然后將不完整記錄進一步區(qū)分為不完整合格記錄、不完整修正記錄以及不完整刪除記錄三類。

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

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

2 研究對象表示及其分類檢測方法

2.1 研究對象的二進制位表示

不完整記錄檢測、分類和修正需要對記錄的不完整信息進行描述，本文采用記錄二進制位表示方法對記錄的不完整信息進行描述。

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

2.2 研究對象的二進制位運算分類檢測方法

不完整記錄的二進制位運算分類檢測方法，首先生成各類標準記錄的二進制位表示集，然后將待檢記錄的二進制位表示與各類標準記錄的二進制位表示進行按位異或運算。

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

步驟（2）Bik記為第k類一條不完整記錄樣本二進制位表示，通過Bik和Gk的元素gkl異或運算，檢測Gk中是否已經存在Bik二進制位表示，若存在Bik則出現次數加1，否則將Bik添加到相應Gk類并記出現次數為1，算法描述如下：

?

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

步驟（5）除G4將步驟（4）設為最高優(yōu)先級，步驟（3）設為次優(yōu)先級外，Gk按標準記錄二進制位表示出現次數多少確定優(yōu)先級。

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

圖1 不完整記錄分類檢測流程

3 實例驗證

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

表1 標準記錄二進制位表示集與檢測結果

由上表可知，不完整記錄占總記錄的63.52%，說明由于空字段導致數據表存在不完整記錄是普遍存在的。但只需對占總記錄56.94%的不完整合格記錄的空字段做相應標識，不需要修正，便可正常使用；總記錄中6.02%的不完整修正記錄需要依據缺失字段類型選擇合適的缺失值估計填充算法進行修正；做刪除處理的不完整刪除記錄占總記錄的0.56%。

在5000條樣本記錄分類檢測過程中，未檢出二進制位表示總共出現28個，將他們分別添加到相應類標準記錄二進制位表示集，再從數據表中另連續(xù)選取5000條記錄樣本進行分類檢測，未檢出二進制位表示沒有再出現。

4 結束語

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