软件学报  2019, Vol. 30 Issue (9): 2830-2856   PDF    
数据治理技术
吴信东1,2,3,4 , 董丙冰2,3,4 , 堵新政1 , 杨威1     
1. 明略科技集团, 北京 100084;
2. 合肥工业大学 大知识科学研究院, 安徽 合肥 230009;
3. 大数据知识工程教育部重点实验室(合肥工业大学), 安徽 合肥 230009;
4. 合肥工业大学 计算机与信息学院, 安徽 合肥 230601
摘要: 随着信息技术的普及,人类产生的数据量正在以指数级的速度增长,如此海量的数据就要求利用新的方法来管理.数据治理是将一个机构(企业或政府部门)的数据作为战略资产来管理,需要从数据收集到处理应用的一套管理机制,以期提高数据质量,实现广泛的数据共享,最终实现数据价值最大化.目前,各行各业对大数据的研究比较火热,但对于大数据治理的研究还处于起步阶段,一个组织的正确决策离不开良好的数据治理.首先介绍数据治理和大数据治理的概念、发展以及应用的必要性;其次,对已有的数据治理技术——数据规范、数据清洗、数据交换和数据集成进行具体的分析,并介绍了数据治理成熟度和数据治理框架设计;在此基础上,提出了大数据HAO治理模型.该模型以支持人类智能(HI)、人工智能(AI)和组织智能(OI)的三者协同为目标,再以公安的数据治理为例介绍HAO治理的应用;最后是对数据治理的总结和展望.
关键词: 数据治理    数据规范    数据清洗    数据交换    数据集成    
Data Governance Technology
WU Xin-Dong1,2,3,4 , DONG Bing-Bing2,3,4 , DU Xin-Zheng1 , YANG Wei1     
1. Mininglamp Technology, Beijing 100084, China;
2. Research Institute of Big Knowledge, Hefei University of Technology, Hefei 230009, China;
3. Key Laboratory of Knowledge Engineering with Big Data(Hefei University of Technology), Hefei 230009, China;
4. School of Computer Science and Information Engineering, Hefei University of Technology, Hefei 230601, China
Abstract: Along with the pervasiveness of information technology, the amount of data generated by human beings is growing at an exponential rate. Such massive data requires management with new methodologies. Data governance is the management of data for an organization (enterprise or government) as a strategic asset, from the collection of data to a set of management mechanisms for processing and applications, aiming to improve data quality, achieve a wide range of data sharing, and ultimately maximize the data value. Research and development on big data is nowadays popular in various domains, but big data governance is still in its infancy, and the decision-making of an organization cannot be separated from excellent data governance. This paper first introduces the concepts, developments, and necessity of data governance and big data governance, then analyzes existing data governance technologies-data specification, data cleaning, data exchange, and data integration, and also discusses the maturity measurement and framework design of data governance. Based on these introductions, analyses and reviews, the paper puts forward a "HAO governance" model for big data governance, which aims to facilitate HAO Intelligence with human intelligence (HI), artificial intelligence (AI), and organizational intelligence (OI), and then instantiates the "HAO governance" model with public security data governance as an example. Finally, the paper summarizes data governance with its challenges and opportunities.
Key words: data governance    data specification    data cleaning    data exchange    data integration    

随着信息技术的迅速发展, 数据规模逐渐扩大.与此同时, 劣质数据也随之而来, 极大地降低了数据挖掘的质量, 对信息社会造成了严重的困扰[1].劣质数据大量存在于很多领域和机构, 国外权威机构的统计表明:美国的企业信息系统中, 1%~30%的数据具有各种错误和误差[2]; 13.6%~81%的关键数据不完整或陈旧情况存在于美国的医疗信息系统中[3].根据Gartner的调查结果:在全球财富1 000强的企业中, 超过25%的企业信息系统中存在错误数据[4].

大多数组织不考虑数据质量对大数据平台建设、分析应用等方面的重要影响而盲目投入, 缺乏对大数据资源的整体规划和综合治理, 最终导致一些项目实施的终止和失败.项目的失败和数据量的激增, 使得数据治理的重要性逐步得到工业界和学术界的共识.随着国家政策支持以及产业实际需求的增长, 如何通过数据治理提升组织数据管理能力、消除数据孤岛、挖掘数据潜在的价值, 将成为重点发展领域.

数据治理的重要前提是建设统一共享的数据平台, 信息系统的建设发展到一定阶段, 数据资源将成为战略资产, 而有效的数据治理才是数据资产形成的必要条件.同时, 在数据共享的时代, 享受大数据带来便利的同时, 也带来如个人隐私泄露的问题[5].个人隐私信息泄露事件频繁发生, 使得人们更加注重保护个人的隐私信息, 通常采取一些措施, 如在进行网站注册时故意填写虚假信息, 这将会严重的影响数据的质量和完整性, 低质量的数据将导致低质量的挖掘结果.数据治理不仅要规范数据, 实现数据的价值和管控风险, 还要做到隐私保护.

本文首先对数据治理做全面的分析, 然后介绍我们自己设计的大数据治理模型.本文第1节介绍数据治理的定义和发展趋势.第2节介绍数据规范技术的内涵以及应用方法.第3节介绍数据清洗的背景以及清洗的基本方法.第4节对数据交换的基本概念及其实现模式进行阐述.第5节介绍数据集成技术的基本概念和数据集成的方法, 并说明这些方法的应用场景.第6节从数据治理的成熟度模型开始, 引出数据治理框架.第7节对我们提出的HAO治理模型进行详细说明.第8节以公安数据治理为例, 具体介绍治理模型的具体应用.最后是对数据治理技术的总结与展望.

1 数据治理的研究现状 1.1 数据治理的定义

至今为止, 数据治理还没有统一标准的定义.IBM对于数据治理的定义是, 数据治理是一种质量控制规程, 用于在管理、使用、改进和保护组织信息的过程中添加新的严谨性和纪律性[6].DGI则认为, 数据治理是指在企业数据管理中分配决策权和相关职责[6].

数据治理的目标, 总体来说就是提高数据质量, 在降低企业风险的同时, 实现数据资产价值的最大化, 包括:

●  构筑适配灵活、标准化、模块化的多源异构数据资源接入体系;

●  建设规范化、流程化、智能化的数据处理体系;

●  打造数据精细化治理体系、组织的数据资源融合分类体系;

●  构建统一调度、精准服务、安全可用的信息共享服务体系.

其次, 我们还需理解数据治理的职能——数据治理提供了将数据作为资产进行管理所需的指导.最后, 我们要把握数据治理的核心——数据资产管理的决策权分配和指责分工[7].

由此, 数据治理从本质上看就是对一个机构(企业或政府部门)的数据从收集融合到分析管理和利用进行评估、指导和监督(EDM)的过程, 通过提供不断创新的数据服务, 为企业创造价值[6].

数据治理与数据管理是两个十分容易混淆的概念, 治理和管理从本质上看是两个完全不同的活动, 但是存在一定的联系, 下面我们对这两个概念进行详细的解读.

COBIT5(control objectives for information and related technology)对管理的定义:管理是按照治理机构设定的方向开展计划、建设、运营和监控活动来实现企业目标[6].所以, 治理过程是对管理活动的评估、指导和监督, 而管理过程是对治理决策的计划、建设和运营.具体分析:首先, 数据治理与数据管理包含不同的活动即职能, 数据治理包括评估指导和监督, 数据管理包括计划建设和运营; 其次, 数据治理是回答企业决策的相关问题并制定数据规范, 而数据管理是实现数据治理提出的决策并给予反馈; 最后, 数据治理和数据管理的责任主体也是不同的, 前者是董事会, 后者是管理层.

1.2 大数据治理——数据治理新趋势

近年来, 大数据已成为国内外专家学者研究的热点话题, 目前基本上采用IBM的5V模型描述大数据的特征:第1个V(volume)是数据量大, 包括采集、存储和计算的量都非常大; 第2个V(velocity)是数据增长速度快, 处理速度也快, 时效性要求高; 第3个V(variety)是种类和来源多样化, 包括结构化、半结构化和非结构化数据; 第4个V(value)是数据价值密度相对较低, 可以说是浪里淘沙却又弥足珍贵; 第五个V(veracity)是各个数据源的质量良莠不齐, 需要精心甄别[8].随着数据量的激增, 可以用“5V+I/O”——体量、速度、多样性、数据价值和质量以及数据在线来概括其特征.这里的“I/O”是指数据永远在线, 可以随时调用和计算, 这个特征是大数据与传统数据最大的区别.

2014年, 吴信东等人基于大数据具有异构、自治的数据源以及复杂和演变的数据关联等本质特征, 提出了HACE定理[9].该定理从大数据的数据处理、领域应用及数据挖掘这3个层次(如图 1所示)来刻画大数据处理框架[8].

Fig. 1 A big data processing framework[9] 图 1 大数据处理框架[9]

框架的第1层是大数据计算平台, 该层面临的挑战集中在数据存取和算法计算过程上; 第2层是面向大数据应用的语义和领域知识, 该层的挑战主要包括信息共享和数据隐私、领域和应用知识这两个方面; 架构的第3层集中在数据挖掘和机器学习算法设计上:稀疏不确定和不完整的数据挖掘、挖掘复杂动态的数据以及局部学习和模型融合[9].第3层的3类算法对应3个阶段:首先, 通过数据融合技术对稀疏、异构、不确定、不完整和多源数据进行预处理; 其次, 在预处理之后, 挖掘复杂和动态的数据; 最后, 通过局部学习和模型融合获得的全局知识进行测试, 并将相关信息反馈到预处理阶段, 预处理阶段根据反馈调整模型和参数[9].

面对大数据兴起带来的挑战, 为了促进大数据治理的发展和变革, 目前业界比较权威的大数据治理定义是:大数据治理是广义信息治理计划的一部分, 它通过协调多个职能部门的目标, 来制定与大数据优化、隐私与货币化相关的策略[10].此定义指出:大数据的优化、隐私保护以及商业价值是大数据治理的重点关注领域, 大数据治理是数据治理发展的一个新阶段, 与数据治理相比, 各种需求的解决在大数据治理中变得更加重要和富有挑战性[6].

●  海量数据存储:根据本地实际数据量级和存储处理能力, 结合集中式或分布式等数据资源的存储方式进行构建, 为大数据平台提供PB级数据的存储及备份能力支撑.云计算[11, 12]作为一种新型的商业模式, 它所提供的存储服务具有专业、经济和按需分配的特点, 可以满足大数据的存储需求;

●  处理效率:大数据治理提供多样化的海量数据接入及处理能力, 包括对各类批量、实时、准实时及流式的结构化、非结构化数据提供快速的计算能力和搜索能力, 比如数据加载能力≥130MB/s、亿级数据秒级检索、百亿数据实时分析≤10s、千亿数据离线分析≤30m等等.对于大数据的搜索能力方面, 为了保证数据安全, 大数据在云计算平台上的存储方式一般为密文存储, 因此, 研究人员设计了很多保护隐私的密文搜索算法[13-22], 基于存储在云平台上大数据的计算安全问题的解决方法一般采用比较成熟的完全同态加密算法[23-29];

●  数据可靠性:围绕行业数据元相关标准规定, 基于行业元数据体系打造大数据平台采集汇聚、加工整合、共享服务等全过程的、端到端的数据质量稽核管控体系, 确保数据准确可靠;

●  数据安全性:数据价值是大数据平台的核心价值, 所以数据的安全是保证平台运行的基础.数据安全包括数据存储的安全、数据传输过程中的安全, 数据的一致性、数据访问安全等, 如图 2所示.数据安全的总体目标是保证数据的存储、传输、访问、展示和导出安全.数据安全措施主要有数据脱敏控制[30]、数据加密控制、防拷贝管理、防泄漏管理、数据权限管理、数据安全等级管理等.

Fig. 2 Data application security schematic 图 2 数据应用安全示意图

而数据治理技术就是在数据治理的过程中所用到的技术工具, 其中主要包括数据规范、数据清洗、数据交换和数据集成这4种技术, 下面具体介绍这4种技术.

2 数据规范 2.1 数据规范的含义

数据治理的处理对象是海量分布在各个系统中的数据, 这些不同系统的数据往往存在一定的差异:数据代码标准、数据格式、数据标识都不一样, 甚至可能存在错误的数据.这就需要建立一套标准化的体系, 对这些存在差异的数据统一标准, 符合行业的规范, 使得在同样的指标下进行分析, 保证数据分析结果的可靠性.例如, 对于数据库的属性值而言, 可以建立唯一性规则、连续性规则以及空值规则等来对数据进行检验和约束:唯一性规则一般是指为主键或其他属性填写unique约束, 使得给定属性的每个值与该属性的其他值不同; 连续性规则是指属性的最大值和最小值之间没有缺失值并且每个值也是唯一的, 一般用于检验数; 空值规则是指使用其他特殊符号来代替空值, 以及对于这样的值应该如何处理.

数据的规范化能够提高数据的通用性、共享性、可移植性及数据分析的可靠性.所以, 在建立数据规范时要具有通用性, 遵循行业的或者国家的标准.

2.2 数据规范方法

数据治理过程中可使用的数据规范方法有:规则处理引擎、标准代码库映射.

(1) 规则处理引擎

数据治理为每个数据项制定相关联的数据元标准, 并为每个标准数据元定义一定的处理规则, 这些处理逻辑包括数据转换、数据校验、数据拼接赋值等.基于机器学习等技术, 对数据字段进行认知和识别, 通过数据自动对标技术, 解决在数据处理过程中遇到的数据不规范的问题.

●  根据数据项标准定义规则模板, 图 3中“出生日期”的规则如下所示。

Fig. 3 Rule processing schematic 图 3 规则处理示意图

    ➢  值域稽核规则:YYYY:MM:DD或YYYY-MM-DD;

    ➢  取值范围规则:1900 < YYYY < =2018, 1 < =MM < =12, 1 < =DD < =31.

●  将数据项与标准库数据项对应。

借助机器学习推荐来简化人工操作, 根据语义相似度和采样值域测试, 推荐相似度最高的数据项关联数据表字段, 并根据数据特点选择适合的转换规则进行自动标准化测试.根据数据项的规则模板自动生成字段的稽核任务.

规则体系中包含很多数据处理的逻辑:将不同数据来源中各种时间格式的数据项, 转化成统一的时间戳(timestamp)格式; 对数据项做加密或者哈希转换; 对身份证号做校验, 检验是否为合法的18位身份证号, 如果是15位的, 则将其统一转换成18位; 将多个数据项通过指定拼接符号, 连接成一个数据项; 将某个常量或者变量值赋给某个数据项等.

规则库中的规则可以多层级迭代, 形成数据处理的一条规则链.规则链上, 上一条规则的输出作为下一条规则的输入, 通过规则的组合, 能够灵活地支持各种数据处理逻辑.例如:对身份证号先使用全角转半角的规则, 对输出的半角值使用身份证校验转换规则, 统一成18位的身份证号; 再对18位身份证号使用数据脱敏规则, 将身份证号转成脱敏后的字符串.

(2) 标准代码库映射

标准代码库是基于国标或者通用的规范建立的key-value字典库, 字典库遵循国标值域、公安装备资产分类与代码等标准进行构建.当数据项的命名为XXXDM(XXX代码)时, 根据字典库的国标或部标代码, 通过字典规则关联出与代码数据项对应的代码名称数据项XXXDMMC(XXX代码名称).

例如, 我们想要将所有表示性别“男”的字段都转换成“男”这种同一的表示方式, 可以先建立一个数据字典, 其中的键的取值范围是所有不同表示方式的集合, 值为最终我们想要归一化表示的“男”.

{

  “男” = > “男”,

  “男性” = > “男”,

  “male” = > “男”,

  “man” = > “男”,

  “1” = > ”男”

  …

}

使用数据转换规则时查找数据字典, 将所有不同的表示方式统一成一种表示方式.

3 数据清洗 3.1 数据清洗背景

数据质量一般由准确性、完整性、一致性、时效性、可信性以及可解释性等特征来描述, 根据Rahm等人在2000年对数据质量基于单数据源还是多数据源以及问题出在模式层还是实例层的标准进行分类, 将数据质量问题分为单数据源模式层问题、单数据源实例层问题、多数据源模式层问题和多数据源实例层问题这4大类[31].现实生活中的数据极易受到噪声、缺失值和不一致数据的侵扰, 数据集成可能也会产生数据不一致的情况, 数据清洗就是识别并且(可能)修复这些“脏数据”的过程[32].如果一个数据库数据规范工作做得好, 会给数据清洗工作减少许多麻烦.对于数据清洗工作的研究基本上是基于相似重复记录的识别与剔除方法展开的, 并且以召回率和准确率作为算法的评价指标[33, 34].现有的清洗技术大都是孤立使用的, 不同的清洗算法作为黑盒子以顺序执行或以交错方式执行, 而这种方法没有考虑不同清洗类型规则之间的交互简化了问题的复杂性, 但这种简化可能会影响最终修复的质量, 因此需要把数据清洗放在上下文中结合端到端质量执行机制进行整体清洗[35].随着大数据时代的到来, 现在已经有不少有关大数据清洗系统的研究[36, 37], 不仅有对于数据一致性[38-40]以及实体匹配[41]的研究, 也有基于MapReduce的数据清洗系统的优化[42]研究.下面对数据清洗具体应用技术以及相关算法进行分析.

3.2 数据清洗基本方法

从微观层面来看, 数据清洗的对象分为模式层数据清洗和实例层数据清洗[43].数据清洗识别并修复的“脏数据”主要有错误数据、不完整的数据以及相似重复的数据, 根据“脏数据”分类, 数据清洗也可以分为3类:属性错误清洗、不完整数据清洗以及相似重复记录的清洗, 下面分别对每种情况进行具体分析.

3.2.1 属性错误清洗

数据库中很多数据违反最初定义的完整性约束, 存在大量不一致的、有冲突的数据和噪声数据, 我们应该识别出这些错误数据, 然后进行错误清洗.

(1) 属性错误检测

属性错误检测有基于定量的方法和基于定性的方法.

●  定量的误差检测一般在离群点检测的基础上采用统计方法来识别异常行为和误差, 离群点检测是找出与其他观察结果偏离太多的点, Aggarwal将关于离群点检测方法又分为6种类型:极值分析、聚类模型、基于距离的模型、基于密度的模型、概率模型、信息理论模型[44], 并对这几种模型进行了详尽的介绍;

●  定性的误差检测一般依赖于描述性方法指定一个合法的数据实例的模式或约束, 因此确定违反这些模式或者约束的就是错误数据.

图 4描述了定性误差检测技术在3个不同方面的不同分类, 下面我们对图中提出的3个问题进行分析.

Fig. 4 Classification of qualitative error detection techniques[45] 图 4 定性误差检测技术分类[45]

●  首先, 错误类型是指要检测什么.定性误差检测技术可以根据捕捉到的错误类型来进行分类, 目前, 大量的工作都是使用完整性约束来捕获数据库应该遵守的数据质量规则, 虽然重复值也违反了完整性约束, 但是重复值的识别与清洗是数据清洗的一个核心(在后续小节将会单独介绍);

●  其次, 自动化检测.根据人类的参与与否以及参与步骤来对定性误差检测技术进行分类, 大部分的检测过程都是全自动化的, 个别技术涉及到人类参与;

●  最后, 商业智能层是指在哪里检测.错误可以发生在数据治理的任何阶段, 大部分的检测都是针对原始数据库的, 但是有些错误只能在数据治理后获得更多的语义和业务逻辑才能检测出来.

不仅可以使用统计方法来对属性错误进行检测, 使用一些商业工具也可以进行异常检测, 如数据清洗工具以及数据审计工具等.Potter’s Wheel[46]是一种公开的数据清洗工具, 不仅支持异常检测, 还支持后面数据不一致清洗所用到的数据变换功能.

(2) 属性错误清洗

属性错误清洗包括噪声数据以及不一致的数据清洗.

●  噪声数据的清洗也叫光滑噪声技术, 主要方法有分箱以及回归等方法:分箱方法是通过周围邻近的值来光滑有序的数据值但是只是局部光滑, 回归方法是使用回归函数拟合数据来光滑噪声;

●  不一致数据的清洗在某些情况下可以参照其他材料使用人工进行修改, 可以借助知识工程工具来找到违反限制的数据, 例如:如果知道数据的函数依赖关系, 通过函数关系修改属性值.但是大部分的不一致情况都需要进行数据变换, 即定义一系列的变换纠正数据, 也有很多商业工具提供数据变换的功能, 例如数据迁移工具和ETL工具等, 但是这些功能都是有限的.

3.2.2 不完整数据清洗

在实际应用中, 数据缺失是一种不可避免的现象[42].有很多情况下会造成数据值的缺失, 例如填写某些表格时需要填写配偶信息, 那没有结婚的人就无法填写此字段, 或者在业务处理的稍后步骤提供值, 字段也可能缺失.处理缺失值目前有以下几种方法.

●  忽略元组:一般情况下, 当此元组缺少多个属性值时常采用此方法, 否则该方法不是很有效.当忽略了此条元组之后, 元组内剩下的有值的属性也不能被采用, 这些数据可能是有用的;

●  人工填写缺失值:这种方法最大的缺点就是需要大量的时间和人力, 数据清理技术需要做到最少的人工干预, 并且在数据集很大、缺失很多属性值时, 这种方法行不通;

●  全局变量填充缺失值:使用同一个常量来填充属性的缺失值.这种方法虽然使用起来较为简单, 但是有时不可靠.例如, 用统一的常量“NULL”来填写缺失值, 在后续的数据挖掘中, 可能会认为它们形成了一个有趣的概念;

●  中心度量填充缺失值:使用属性的中心度量来填充缺失值.中心度量是指数据分布的“中间”值, 例如均值或者中位数, 数据对称分布使用均值、倾斜分布使用中位数;

●  使用最可能的值填充:相当于数值预测的概念.回归分析是数值预测最常用的统计学方法, 此外也可以使用贝叶斯形式化方法的基于推理的工具或决策树归纳确定缺失值.

鉴于现在很多人为了保护自己的隐私或者为了方便, 随意地选择窗口中给定的值, Hua等人于2007年提出了一种识别伪装缺失数据的启发式方法, 当用户不愿意泄露个人信息时故意错误地选择窗口上的默认值(如生日字段), 这时数据就会被捕获[47].

3.2.3 相似重复记录清洗

●  相似重复记录识别

消除相似重复记录, 首先应该识别出相同或不同数据集中的两个实体是否指向同一实体, 这个过程也叫实体对齐或实体匹配.文本相似度度量是实体对齐的最基础方法, 大致分为4种:基于字符的(例如编辑距离、仿射间隙距离、Smith-Waterman距离、Jaro距离度量、Q-gram距离[48])、基于单词的(例如Jaccard系数)、混合型(例如softTF-IDF)和基于语义的(例如WordNet).随着知识表示学习在各个领域的发展, 一些研究人员提出了基于表示学习的实体匹配算法, 但均是以TransE系列模型为基础构建的.TransE[49]首次提出基于翻译的方法, 将关系解释为实体的低维向量之间的翻译操作, 随之涌现出一些扩展的典型算法, 下面对这些算法进行简单介绍.

a) MTransE算法[50]:基于转移的方法解决多语言知识图谱中的实体对齐.首先, 使用TransE对单个的知识图谱进行表示学习; 接着, 学习不同空间的线性变换来进行实体对齐.转移方法有基于距离的轴校准、翻译向量、线性变换这3种.该知识模型简单复用TransE, 对于提高实体对齐的精度仍存在很大局限;

b) JAPE算法[51]是针对跨语言实体对齐的联合属性保护模型, 利用属性及文字描述信息来增强实体表示学习, 分为结构表示、属性表示.IPTransE算法[52]使用联合表示的迭代对齐, 即使用迭代的方式不断更新实体匹配.该方法分为3部分:知识表示、联合表示、迭代对齐.但这两种算法都是基于先验实体匹配, 将不同知识图谱中的实体和关系嵌入到统一的向量空间, 然后将匹配过程转换成向量表示间距离的过程;

c) SEEA算法[53]分为两部分:属性三元组学习、关系三元组学习.该模型能够自学习, 不需要对齐种子的输入.每次迭代, 根据前面迭代过程所得到的表示模型, 计算实体向量间的余弦相似度.并选取前β对添加到关系三元组中更新本次表示模型, 直到收敛.收敛条件:无法选取前β对实体对.

实体对齐方法不仅应用于数据清洗过程中, 对后续的数据集成以及数据挖掘也起到重要的作用.除此之外, 也有很多重复检测的工具可以使用, 如Febrl系统、TAILOR工具、WHIRL系统、BigMatch等, 但是很多匹配算法只适用于英文不适合中文, 所以中文数据清洗工具的开发还需要进一步的研究.

●  相似重复记录清洗

相似重复记录的清洗一般都采用先排序再合并的思想, 代表算法有优先队列算法、近邻排序算法、多趟近邻排序算法.优先队列算法比较复杂, 先将表中所有记录进行排序后, 排好的记录被优先队列进行顺序扫描并动态地将它们聚类, 减少记录比较的次数, 匹配效率得以提高, 该算法还可以很好地适应数据规模的变化.近邻排序算法是相似重复记录清洗的经典算法, 近邻排序算法是采用滑动窗口机制进行相似重复记录的匹配, 每次只对进入窗口的w条记录进行比较, 只需要比较w×N次, 提高了匹配的效率.但是它有两个很大的缺点:首先是该算法的优劣对排序关键字的依赖性很大, 如果排序关键字选择得不好, 相似的两条记录一直没有出现在滑动窗口上就无法识别相似重复记录, 导致很多条相似重复记录得不到清洗; 其次是滑动窗口的值w也很难把控, w值太大可能会产生没必要的比较次数, w值太小又可能会遗漏重复记录的匹配.多趟近邻排序算法是针对近邻排序算法进行改进的算法, 它是进行多次近邻排序算法每次选取的滑动窗口值可以不同, 且每次匹配的相似记录采用传递闭包, 虽然可以减少很多遗漏记录, 但也会产生误识别的情况.这两个算法的滑动窗口值和属性值的权重都是固定的, 所以也有一些学者提出基于可变的滑动窗口值和不同权重的属性值来进行相似重复记录的清洗.以上算法都有一些缺陷, 如都要进行排序, 多次的外部排序会引起输入/输出代价过大; 其次, 由于字符位置敏感性, 排序时相似重复的记录不一定排在邻近的位置, 对算法的准确性有影响.

4 数据交换 4.1 数据交换的基本概念

数据交换是将符合一个源模式的数据转换为符合目标模式数据的问题, 该目标模式尽可能准确并且以与各种依赖性一致的方式反映源数据[54, 55].

早期数据交换的一个主要方向是在关系模式之间从数据交换的上下文中寻求一阶查询的语义和复杂性. 2008年, Afrati等人开始系统地研究数据交换中聚合查询的语义和复杂性, 给出一些概念并做出了技术贡献[56].在一篇具有里程碑意义的论文中, Fagin等人提出了一种纯粹逻辑的方法来完成这项任务[55].从这时起, 在数据库研究界已经对数据交换进行了深入研究.近年, Xiao等人指出, 跨越不同实体的数据交换是实现智能城市的重要手段, 设计了一种新颖的后端计算架构——数据隐私保护自动化架构(DPA), 促进在线隐私保护处理自动化, 以无中断的方式与公司的主要应用系统无缝集成, 允许适应灵活的模型和交叉的服务质量保证实体数据交换[57].随着云计算和Web服务的快速发展, Wu等人将基于特征的数据交换应用于基于云的设计与制造的协作产品开发上, 并提出了一种面向服务的基于云的设计和制造数据交换架构[58].

完善合理的数据交换服务