0 引言

对几个著名的公司数据进行研究, 其中有25%的重要数据是存在缺陷的^[1], 由它带来的经济损失也是惊人的, 据统计, “脏数据”导致美国商业每年约损失6 000亿美元^[2]。在大数据时代, 数据预处理已经成为一个重要的研究课题, 吸引了越来越多学术界和工业界研究人员的注意, 根据调查显示, 数据质量工具的市场正以每年17%的速度增长, 远远高出IT行业中其他分支平均7%的增长速度^[3]。

典型的数据预处理过程如图 1所示, 左边的方框表示原始数据集, 其中包括结构化数据、半结构化数据和非结构化数据。中间的方框表示数据预处理的两个主要任务即数据转换和数据清洗。数据转换 (Data Transformation) 是指从原始数据中提取数据, 并将其转换成适合进一步分析的数据格式的过程。数据清洗 (Data Cleaning、Data Cleansing或者Data Scrubbing) 主要用来检测数据中存在的异常数据 (例如错误、缺失、不一致等)^[4]并去除或修正它们, 最终目的就是提高数据的质量^[5-6]。

在过去的十几年中, 数据清洗领域得以飞速发展, 衍生出了许多数据清洗方法和系统, 基于规则的数据清洗方法因为其自身的简单易实现并且清洗效果显著等特点使其在数据清洗领域一直扮演着一个重要的角色^[7-8]。文献[9]对数据质量问题作了详细的分类和分析, 并以判定树的形式给出了检测方法, 从而有力地支持了基于规则的数据清洗技术的现实可行性。本文对现有的一些基于规则的数据清洗方法, 例如NADEEF (A Commodity Data Cleaning System)、AzszpClean (A Rule-based Solution to Data Cleaning) 等进行了研究并概括如表 1。

目前大多数的数据清洗工具或框架都是针对某些特定领域, 如果用户需引入新的规则或是复用其他领域的一些规则 (例如检查身份证号的规则在很多领域是通用的) 则十分困难, 而且扩展现有解决方案或部署这些方案到自己系统中也十分艰巨^{[13, 19-21]}; 目前还有一些清洗工具的脏数据检测和修复借助硬编码来实现^[5], 这会导致系统的可扩展性和灵活性较差, 当清洗规则发生变化时清洗部分的代码需要重新实现, 并且硬编码方法对数据清洗的描述性较弱，在实现复杂逻辑方面的数据清洗时会比较困难, 而且用户的理解度和接受度较低; 另外, 有一些清洗工具是借助人工判断来完成脏数据检测和修复^[22], 该类方法在数据量较小时具有高准确性的优势, 但在数据量庞大且多源异构的情况下劣势会愈发明显。

1 DRDCM方法

基于以上问题, 本文提出了一种基于动态可配置规则的数据清洗方法 (Dynamic Rule-based Data Cleaning Method, DRDCM), 这是一种跨领域的、可重用的、可配置的将脏数据检查与脏数据修复以及数据转换三者融为一体的新方法。该方法支持多种规则类型以及规则间的复杂逻辑运算; 支持三种脏数据修复行为:保留 (RETAIN)、丢弃 (DISCARD) 和回填 (REFILL); 支持用户在运行时增加、删除或修改规则等。

1.1 DRDCM相关定义

图 2为DRDCM的数据清洗过程。

首先, 用户对原始数据分析提取规则, 在DRDCM支持三种类型规则, 分别是:DROOLS (JBoss Rules) 规则、REGEX (Regular Expression) 规则和FUN (Function) 规则。在规则配置阶段实现规则与属性、表以及领域的绑定。其中规则执行包括两部分即数据检测以及根据检测结果进行数据修复。DRDCM中涉及到的相关定义如下:

定义1    数据清洗 (Data Cleaning)。数据清洗是把原始输入数据通过一系列的数据检测和数据修复后转换为干净数据的过程, 可以形式化表示为:

Data Cleaning:${\text{R}} \underrightarrow {{\text{(0}}...{\text{n)CleanRule}}} {\text{D}}$

其中：R代表原始数据; D代表干净数据。

定义2    数据检测 (Data Check)。用来检测数据是否符合既定知识的过程, 可用谓词函数表示为CHECKCOND:D →{T, F}:

CHECKCOND (d)=T表示待检测数据项d是符合清洗规则的数据, 即为“干净数据”, 直接存入干净数据库;

CHECKCOND (d)=F表示待检测数据项d是不符合清洗规则的数据, 即为“脏数据”, 需要进一步作数据修复 (见定义3);

定义3    数据修复 (Data Revise)。根据数据检测的结果, 如果为F则需要对原数据进行修改, DRDCM支持三种修改行为:保留 (RETAIN)、丢弃 (DISCARD) 和回填 (REFILL)。

定义4    DROOLS规则。抽取的规则可以通过Drools语法^[23]清晰表达的, 均定义为DROOLS规则类型, 形如“rule 〈name〉 attributes; when 〈LHS〉; then 〈RHS〉; end”。

定义5    REGEX规则。抽取的规则可以通过Java正则表达式^[24]清晰表达的, 均定义为REGEX规则类型, 例如“18位身份证号且支持以X结尾”, 可以定义为正则表达式“(^[1-9]([0-9]{16}|[0-9]{13})[xX0-9] ＄)”。

定义6    FUN规则。抽取的规则通过DROOLS规则和REGEX规则均无法表达的, 可以定义为FUN规则, 例如一些时间函数、转换函数和数学函数等。

定义7    清洗规则 (Clean Rule)。本文提出的清洗规则可用四元组表示为:

CleanRule :: =〈Number, Rule Type, Data Check,

    Data Revise〉

其中：Number是由规则组号和规则号组成；Rule Type见定义4~6；Data Check见定义2；Data Revise见定义3。

1.2 DRDCM方法的组成

DRDCM方法主要包括如下几个组成部分:

规则模板    即规则实体定义, 方便用户阅读、定义以及修改规则。

规则库    集中保存跨领域的所有规则, 以规则组号和规则号组合为唯一标识, 以便进行规则的管理与重用。

规则配置与存储    处理在实际清洗过程中规则实体与属性、表、领域等的匹配关系, 支持复杂逻辑描述表达式如:((规则1‖规则2) & & !规则3), 支持二元组〈属性名, 规则表达式〉、三元组〈表名, 属性名, 规则表达式〉和四元组〈领域名, 表名, 属性名, 规则表达式〉等。

规则引擎    是规则的运行环境, 用来编译和执行规则。

数据清洗反馈类    负责将清洗结果和存在问题反馈给用户。

1.3 DRDCM方法的特点

相较于其他基于规则的数据清洗方法, DRDCM方法具备以下几个特点:

1) DRDCM采用低耦合的设计模式, 因此将业务规则与业务系统分离。

2) DRDCM采用规则的动态编译方法, 不仅具备坚实的编译理论基础, 而且可以方便地在线修改和增删规则, 方便应对特殊状况, 比如用户一开始没有考虑到引入规则或是规则引入有误或引入规则不足以表达实际需求等情况。

3) DRDCM方法中规则的定义遵循最小化原则 (即规则不可再被拆分为其他子规则), 给数据清洗的复杂逻辑描述以及多领域规则重用打下基础。

4) DRDCM方法中将数据转换与规则配置相结合, 使单源数据或多源数据在集成的同时, 完成数据清洗和修复, 避免数据多次导入导出。

5) DRDCM支持三种规则类型, 避免单一规则类型的局限性, 能够较全面地描述真实数据集中可以提取的规则。

6) DRDCM实现一种新的规则引擎, 可以支持复杂的逻辑表达式和不同层次的规则配置, 如属性、表和领域。

1.4 DRDCM方法的工作模式

DRDCM方法的工作模式如下:首先, 对原始数据集进行分析并提取有效规则, 通过规则定义界面将这些规则录入并存储进规则库中, 其中规则的定义必须符合规则模板。接下来是数据转换, 周傲英教授在文献[25]中阐述了数据转换的重要性, 对多源异构数据进行分析, 从非结构化、半结构化的源数据中抽取结构化信息来定义XML模型从而完成数据转换。在DRDCM方法中, 是在数据转换的过程中完成规则配置, 规则配置形如:<exp><![CDATA[{"constraint":"1_4 or 1_5 or 1_6", "ruleAction":"DISCARD"}]]></exp>, 其中1_4、1_5和1_6均标识规则库中的唯一一条规则。最后是规则的执行, DRDCM提供的规则执行核心模块根据规则配置将所需规则从规则库中取出放入规则队列, 规则引擎会解析对应的规则, 根据规则类型编译和执行对应规则, 规则的执行包括数据检测和根据检测结果执行数据修复两部分。

1.5 算法设计

DRDCM支持三种不同类型的数据清洗规则, 如何把这些规则行之有效地部署到实际应用中是其中一个关键。因此需要设计出一套切实有效的算法来自动地进行数据清洗。

算法1    数据清洗算法。

Input: DRL:待清洗记录集；

    AttributeInfoBeanMap:存储记录集中属性的元数据。        //类型为Map<AttributeName, AttributeInfoBean>

Output: CleanRL:干净的记录集。

1) CleanRL ←{};         //存储干净的记录集, 初始化为空

2) ruleExp="";         //初始化规则表达式

3) ruleQuene←new LinkedList<>();         //初始化规则队列为空, 用于存储规则实体

4) checkValueMap← new Map<String, Boolean>();         //用于存储规则的检查结果, key值为规则编号

5) For each record in DRL Do

6)     cleanRecord←record;         //用于存储修复后的干净记录

7)     For each attribute∈ record Do

8)         If (AttributeInfoBeanMap.get (attribute)! =null)

9)             ruleExp ←读取对应AttributeInfoBean中的规则表达式;         //形如"1_4 or 1_5 or 1_6"

10)             ruleQuene← ruleExp中所有规则号对应的规则实体ruleEntity;

11)             For each ruleEntity in ruleQuene Do

12)                 ruleType ← ruleEntity.getRuleType;

13)                 If (ruleType= ="DROOLS")

14)                     checkValue← Call DroolsSemErr;

15)                 Else if (ruleType= ="REGEX")

16)                     checkValue←Call RegextSemErr;

17)                 Else If (ruleType= ="FUN")

18)                     checkValue ←Call FunSemErr;

19)                 checkValueMap.put (ruleNumber, checkValue);

20)         expCheckValue←runLogicalExp (ruleExp, checkValueMap)

21)         if (expCheckValue= = false)

22)             cleanRecord←call数据修复算法更新cleanRecord;

23)         If (cleanRecord= =null)

24)             break;         //退出循环

25)     End For each attribute;

26)     If (cleanRecord! =null)

27)         CleanRL.add (cleanRecord);

28) End For each record;

29) return CleanRL;

在算法2中, RetainNumMap为Map<String, Integer>类型, 用于存储属性名以及该属性中不符合规则并且没有合适修复策略的属性值个数。

算法2    数据修复算法。

Input: Record:待修复的记录;

    AtrributeName:待修复的属性名;

    Action:修复动作;

    RetainNumMap:         //Map<String, Integer>

Output: ModifiedRecord:被修复后的记录。

1) modifiedRecord ← Record;

2) if (Action= =DISCARD)

3)     modifiedRecord=null;

4) If (Action= =RETAIN)

5)    更新RetainNumMap;

6) If (Action= =REFILL)

7)     //根据属性所属类型选择回填值;

8)     If (AtrributeName是枚举型属性)

9)         ModifiedRecord←ModifiedRecord.setAttribute (AtrributeName, MaxFreqValue);         // MaxFreqValue为该属性中出现频率最高的属性值

10) If (AtrributeName是数值型属性)

11)         Mo difiedRecord←ModifiedRecord.setAttribute (AtrributeName, MeanValue);         // MeanValue为该属性值的样本均值

12)     If (AtrributeName是日期型属性)

13)        转换日期型格式, 如果为空值参考字符串型处理方法;

14)     If (AtrributeName是字符串型属性)

15)        寻找重复记录或最邻近记录对应的属性值作为填充值;

16) return ModifiedRecord;

2 DRDCM参考实现系统 2.1 DRDCM系统架构

DRDCM系统的总体架构如图 3所示, 主要有数据导入模块, 它给结构化、非结构化数据以及半结构化数据的导入提供了一个统一的接口, 这样就可以实现综合的管理, 提高整体的使用效率, 减少今后维护的成本; 数据转换与规则配置模块, 该模块的主要任务是将结构化、非结构化以及半结构化数据转换为方便后期进行数据分析的统一格式, 并通过该模块将规则与属性、表以及领域进行匹配; 规则收集模块 (包括规则模板、规则定义界面和规则库等), 该模块主要功能是从原始数据中抽取规则并进行定义和存储规则; 规则执行核心模块 (包括规则引擎、规则编译、数据检测和数据修复等), 主要功能是执行数据清洗规则以及对原始数据进行修正以获取干净数据; 数据输出模块 (包括清洗反馈和干净数据存储)。

2.2 清洗规则

清洗规则可以表示为:

RULE (n, t, c, o, v)

n:规则的名称 (字母、数字和下划线组成);

t:规则的类型 (t∈{DROOLS, FUN, REGEX});

c:清洗检测 (c∈RegexSemErr, DroolsSemErr, FunSemErr);

o:规则的操作符 (o∈{ BELONGTO, NOTBELONGTO, CONTAINS, NOTCONTAINS, MATCHS, NOTMATCHS, GREATER, LESS, EQUAL, NOTEQUAL, INNER, OUTSIDE, SATISFY, NOT SATISFY});

v:标准值或标准值域。

BELONGTO与NOTBELONGTO描述个体与集合的关系, 例如: 1∈{1, 2, 3}、4∉{1, 2, 3};CONTAINS与NOTCONTAINS描述集合与集合的关系, 例如:{1}⊂{1, 5, 6}、{1}⊄{4, 5, 6};GREATER、GREATEREQ、LESS、LESSEQ、EQUAL、NOTEQUAL、INNER、OUTSIDE分别表示大于、大于等于、小于、小于等于、等于、不等于、在区间内和在区间外, 其中INNER、OUTSIDE可以通过GREATER (GREATEREQ) 与LESS (LESSEQ) 的“∧”运算实现。

规则操作符的定义：

BELONGTO ⇔∈

NOTBELONGTO ⇔∉

CONTAINS ⇔⊆

NOTCONTAINS ⇔⊄

GREATER ⇔>

GREATEREQ ⇔≥

LESS ⇔ <

LESSEQ ⇔≤

EQUAL ⇔=

NOTEQUAL ⇔≠

2.3 规则引擎

DRDCM参考实现系统的规则引擎分三个步骤:

步骤1    解析规则配置文件, 其中配置文件涉及到的数据转换元表和规则表达式元表, 如表 2所示。

步骤2    在将原数据进行数据转换时读取元数据模型中的规则表达式Exp, 并根据规则类型调用对应的规则执行文件, 本文有三种规则类型, 对应的规则执行文件提供的接口分别为:

    RegextSemErr (Object d1, ExpEntity e1)

    DroolsSemErr (Object d1, ExpEntity e1)

    FunSemErr (Object d1, ExpEntity e1)

其中:d1为待清洗数据；e1表示规则实体。这三个接口用来完成每条规则的数据检测。

步骤3    计算规则表达式的值, 如果为F则调用数据修复模块进行数据修复, 最终存入干净数据库。

2.4 规则配置

规则是从一些领域知识或是复杂商业逻辑中提取出来的, 不同领域的原始数据集中会存在一些共有的信息, 例如对人的信息采集, 包括人的性别、身份证号码、族别、出生日期、年龄等信息, 而从这些基本信息中可以抽取到的规则有:性别只有男/女, 身份证号码18位支持X字母结尾, 民族只能是56个民族中的其中一个 (中国公民), 出生日期的日期格式, 等等。在DRDCM系统中, 规则从领域知识中提取但又不依赖于领域, 规则库中的规则可以跨领域进行重用。

DRDCM系统根据规则的关联号把规则分为若干个分组, 并以〈规则组号-规则号〉为索引来匹配和执行规则, 大大降低了时间复杂度。基于这个原则进行规则配置, 当用户修改规则时, 规则引擎无需作任何改动; 当用户增加或删除规则时, 仅需要改动规则配置模块, 规则引擎和其他模块无需作任何改动, 从而极大提高了系统的重用性、扩展性和灵活性。

规则配置中涉及到规则表达式用二元组表示为:

RL=〈RN, LC〉

RN是规则组号-规则号, 用来唯一标识一个规则。LC是逻辑连接词, 用“not”代表“¬(否定)”、用“and”代表“∧(合取)”、用“or”代表“∨(析取)”、用“ifThen”代表“→(蕴涵)”、用“EQ”代表“↔(等价)”。

规则配置支持如下几种格式:

1) Expc:: =〈A, RL〉, 用来表达单个属性下的规则约束;

2) Expc:: =〈T, A, RL, LC〉, 用来表达以表为单位的规则约束;

3) Expc:: =〈D, T, A, RL, LC〉, 用来表示不同领域下的规则约束。

其中：A代表属性名；T代表表名；LC是逻辑连接词；D代表领域名。

在XML规则配置文件中, Expc:: =〈A, RL〉格式如下所示:

< a ttribute OriginalName="idCode" NodeName="Y"

    AttributeName=" idNum" …>

    <exp>

    <![C DATA[{"constraint":"1_4 or 1_5 or 1_6",

        "ruleAction":"DISCARD"}]]>

    </exp>

< /attribute>

3 实际应用

面向公安、国安等地区大数据分析的需求, 结合工信部物联网发展专项的“新疆电梯安全动态监管物联网系统研发与应用”的数据, 以及国家发改委物联网重大专项的“基于物联网技术的车载气瓶电子监管系统及产业化”的数据。采用DRDCM系统对这些原始数据进行清洗, 从而保障数据检索、数据分析以及分析结果展示的准确性。

在实验部分通过以下三个方面来展示该系统的性能:1) 给出该系统的输入输出数据; 2) 给出该系统数据清洗的准确性; 3) 给出该系统数据清洗的效率。

3.1 数据采集

该数据集共计10.7 GB, 时间跨度为2016年1月到2016年5月。数据采集方式有三种：第一种是通过具备NFC功能的智能手机或其他智能手持设备获取；第二种是通过人工录入；第三种是和其他系统对接来导入数据。

“新疆电梯安全动态监管物联网系统研发与应用”和“基于物联网技术的车载气瓶电子监管系统及产业化”两个项目中都引入了近距离无线通信技术 (Near Field Communication, NFC), 它是工作在13.56 MHz频率, 有效距离在20 cm内。事实上, 操作距离以及嵌入手机或其他手持设备的NFC设备自身的灵敏度都会影响到从电子标签中读取数据。第二种采集方法中, 排除纸质材料本身的完整性, 在人工录入时难免会存在错录或少录的情况。在第三种采集方法中, 数据来自不同系统, 因此数据具有异构、多源、分布式、时间跨度大等特点, 这些数据中不可避免地会存在着一些粗糙的、不合时宜的数据。

3.2 评价标准

为了验证本文方法在丢弃记录与回填记录的有效性, 本文引入准确率Accuracy来评定, 其定义如下:

$ Accuracy = \frac{{TP + TN}}{{TP + TN + FP + FN}} \times 100{\rm{\% }} $

(1)

其中:TP是真正例的个数, 即不符合清洗规则且被正确地执行了丢弃或回填动作的属性值个数; TN是真负例的个数, 即属性值本身为干净数据且没有被执行任何修复动作的属性值个数；FP是假正例的个数；FN为假负例的个数。TP+TN+FP+FN为样本总数。总而言之, 准确率就是被正确处理的样本数除以所有的样本数, 通常来说, 准确率越高, 则处理效果越好。

3.3 实验结果以及分析

实验1    限于篇幅和所属项目数据本身的保密性, 本文仅给出其中一个数据表的部分信息 (如表 3中的输入数据所示) 作数据清洗描述, 该测试数据来源是经数据转换后的结构化数据。

表 1中:“idType”属性中值1代表“idNum”中存储的是“身份证”, 值2表示的是“组织机构”, 其中组织机构是由8位数字组成, 值3表示的是“护照”。另外因为涉及隐私问题, 表 3中所列数据中的身份证号码、护照号和姓名都经过了替换处理, 并且某些数字用“*”号代替。其中idNum的规则配置见2.4节中的示例 ({"constraint":"1_4 or 1_5 or 1_6", "ruleAction":"DISCARD"})。

因篇幅原因, 只列举在规则配置文件中的两条规则作为示例。

<!--rule: 1_4 Id card number 18 digits or 17 digits plus X-->

    <rule number="1_4" enabled="true">

    <ruleName>ID_CARD_NUM</ruleName>

    <ruleNumber>1_4</ruleNumber>

    <ruleType>REGEX</ruleType>

    <ruleCheck></ruleCheck>

    <ruleValueOperator>SATISFY</ruleValueOperator>

    <ruleValue>

    (^[1-9]([0-9]{16}|[0-9]{13})[xX0-9] ＄)

    </ruleValue>

    </rule>

< !--rule: 3_1 replace the gender value-->

    <rule number="3_1" enabled="true">

    <ruleName>REPLACE_GENDER</ruleName>

    <ruleNumber>3_1</ruleNumber>

    <ruleType>FUN</ruleType>

    <ruleCheck></ruleCheck>

    <ruleValueOperator>BELONGTO</ruleValueOperator>

    <ruleValue>M:男, F:女</ruleValue>

    </rule>

规则1_4是正则表达式类型规则, 用于检测身份证号码的合法性。规则3_1是函数类型规则, 它的作用是将gender属性中的“F”值替换为“女”、“M”替换为“男”。在规则配置时, 因为idNum是该表的主键, 如果idNum不符合清洗规则表达式，则表示该条记录为无效记录予以丢弃。

经DRDCM系统进行清洗后, 表 3中输入数据部分的第一条记录中ethnic属性值被回填为“汉”另外, 第2条和第4条因idNum不符合清洗规则表达式所以予以丢弃, 具体清洗结果如表 3中输出数据部分所示。

如果使用硬编码方法实现就需要冗长的if…else语句实现, 硬编码方式不仅容易引入错误, 而且修改起来相当困难, 对不同的应用难以复用。而DRDCM方法仅需几条规则即可, 在代码实现部分无需任何改动, 极大地方便和简化了数据清洗和修复的流程。

实验2    每次随机抽取记录, 重复20次, 统计出有多少条记录被抛弃、多少属性值被回填以及它们的准确率。在本次实验中, 用到的规则数量分别是5、10和20。数据清洗的统计结果如表 4所示, 实验结果表明丢弃记录的准确率是可以接受的, 但是回填记录的准确率有待提高, 这在本项目目前正在开发的数据清洗和数据融合系统中会进一步完善。

实验3    对DRDCM的清洗效率进行了实验, 并与硬编码 (Hard Coding, HardCode) 方法作了对比。在图 4中, 横坐标表示实验中所使用的规则条数, 纵坐标表示在对应的规则条数上执行10条、100条、1 000条和10 000条记录所消耗的时间。从图 4可知, 随着规则数量的增加, 性能缓慢下降, 说明DRDCM系统的性能和规则条数的相关度不是很大。

在图 5中给出了DRDCM与HardCode性能的比较。由图 5可知, 在规则数为5时DRDCM系统在性能上要略差于HardCode方法; 但随着规则数增长, 当规则数为20时和40时, DRDCM系统和HardCode的性能差距越来越小。另外, 规则数量的增加, 对HardCode和DRDCM系统的影响基本趋于一致。虽然较之HardCode, 在性能上DRDCM系统的优势并不明显, 但是DRDCM可以使用形式化语言描述规则的复杂逻辑运算, 且易于用户理解和接受; DRDCM把业务规则和业务系统进行分离, 也更方便用户的扩展与修改, 以及一些突发情况的处理; 另外, DRDCM方法支持规则的跨领域重用、配置等。

4 结语

本文通过对现有数据清洗方法特别是基于规则的数据清洗方法进行详细研究后, 提出了一种新的基于动态可配置规则的数据清洗方法DRDCM, 将规则配置、数据转换、数据检测以及数据修复融为一体; 支持跨领域多源数据的规则重用; DRDCM方法支持三种类型的规则并提供对应接口实现, 可以避免单一规则对源数据特征描述时的局限性。另外, 本文对DRDCM方法提出一种参考实现系统, 它支持规则的动态编译, 利用该系统用户可以方便地对规则进行阅读、抽取、新增、修改和删除等操作, 并且支持规则的复杂逻辑描述等, 综合上述改进使该系统具备灵活性和扩展性。该系统已部署在工信部物联网发展专项的“新疆电梯安全动态监管物联网系统研发与应用”和国家发改委物联网重大专项的“基于物联网技术的车载气瓶电子监管系统及产业化”项目中, 在这些项目中的实际运行情况以及获取到的真实数据集进一步验证了该方法在现实场景下的可行性。