马平全， 宋 凯， 纪建伟

(1. 沈阳农业大学 信息与电气工程学院， 沈阳 110866； 2. 沈阳理工大学 自动化与电气工程学院， 沈阳 110159)

基于N-Gram算法的数据清洗技术*

马平全1，2， 宋 凯1，2， 纪建伟1

(1. 沈阳农业大学 信息与电气工程学院， 沈阳 110866； 2. 沈阳理工大学 自动化与电气工程学院， 沈阳 110159)

针对数据库中存在的大量相似重复数据，对相似重复记录的属性结构以及产生原因进行了分析，采用N-Gram算法对数据记录进行计算，得到代表每条记录属性的键值，即N-Gram值.依据该键值将数据库中的数据记录进行排序处理，建立有序的数据库，并对其中的数据记录进行相似度计算.运用排列合并的清洗思想对识别出来的相似重复数据记录进行清洗，实验结果表明，N-Gram算法有效提高了相似重复数据记录的查全率和查准率.

相似度； 相似重复记录； 属性； 排序； 合并； 数据清洗； 查全率； 查准率

在第二次世界大战期间，信息传递给战争双方带来了极大的便利，在战争进行过程中，人们渐渐地发现信息的重要性，各方都在不断地更新自己的信息处理机制，加速信息的获取.这种形式促进了电子计算机的产生，并在战争中起到了举足轻重的作用.战争结束以后，电子计算机作为一种新的技术被保留下来，并且不断地被开发，渐渐走进了人们的生活，人类逐渐进入了信息化时代，信息技术成为每一位新时代人所必备的技术.

但随着信息技术的不断发展，数据量不断增加，大量的错误数据充斥其中，相似数据、重复数据和字段缺失数据等，这些垃圾数据的出现给人们带来了很大的不便，甚至会给一些企业机关单位带来严重的后果[1-3].因此，针对这些数据进行数据清洗变得迫在眉睫.

1 相似重复数据产生的原因

相似重复记录是指在合并数据集的过程中，同一目标实体往往有着多条记录，这些记录之间虽然在形式上有所不同，但其所描述的目标却是相同的一个.通常造成这种结果的原因是由于数据录入时错误的拼写、对名词的缩写以及不同的存储类型，导致同一记录实体有着多种不同表现形式，但这些记录往往本意上都是表现同一条数据记录[4-5].由于这种特殊原因，造成了其数据特征并不明显，这对相似重复记录的识别以及对其进行数据清洗造成了很大的困难.因此，清除数据库中的相似重复记录是提高数据库使用率、降低消耗、提高数据质量的一个重要途径[6-7].

本文将相似重复记录大致分为以下两大类：

1) 完全重复记录.这类记录在数据库中无论是字符还是数值，在属性和表现形式上都是完全相同的.

2) 相似重复记录.这类记录是指在数据库中部分属性字段相同或者相似，但却是同一记录实体的不同表现形式[8-9].

2 数据清洗

数据清洗是指通过某种方式来清除数据集中“脏数据”的技术，经常作为提高数据使用率的一种途径.到目前为止，数据清洗仍是一个模糊的概念，研究人员对数据清洗没有给出一个标准定义，对数据清洗技术的理解仍是从字面意思上解释的，比较通用的说法是数据清洗就是把数据库中“脏”的数据记录清洗掉，保留下“干净”的数据记录[10-11].

数据清洗的步骤与一般数据处理过程类似，主要内容包括如下几个方面.

1) 数据分析.数据分析基本上是所有数据处理过程的首要步骤，通过详细分析源数据库，检测源数据库中的错误数据和不一致数据的情况，从而来判定数据质量上的问题.然而，如何准确了解数据集中的质量问题是个难点，而这个问题仅依靠既有的元数据并不能达到预期目的.这便需要对具体的数据实例进行数据分析，从中提取出能够代表整条记录的元数据，这些元数据能够自动改变数据之间的属性，本文称之为依附性，然后重点对这些实例的属性进行分析，才能发现其中的数据质量问题[12].

数据派生和数据挖掘都能够较好地完成数据分析的任务，但两者主要应用在不同的数据库中.首先两者最大的不同是作用范围，数据派生主要是作用在单独的属性上，通过对单独的属性实例进行分析，从而得到大量的属性信息，包括数据类型、数据单位、属性冲突的次数和缺失信息的频率等.而数据挖掘恰好与其相反，其主要应用在大型数据中心，通过对大型数据中心的海量信息进行分析，挖掘出属性之间依赖关系和约束关系，这些关系往往是后期对多数据源中相似重复记录进行数据清洗的一个重要依据，根据这些关系能够较为完善地解决存在的问题[13-14].

2) 确定数据转换规则和工作流.通过数据分析可得到一些信息，包括数据源的个数、错误数据的多少以及“脏数据”的主要类型等，通过这些信息建立合适的清洗步骤、转换算法、查询语句以及检测算法等，从而确定主句转换规则和工作流.

3) 数据验证.在确定数据转换规则和工作流之后，需要对其进行验证，避免出现效率低下等问题.从数据源中抽出一部分数据当作样本数据，然后利用上一步确定的数据转换规则和工作流对抽出来的样本进行验证，并对验证结果进行分析，对工作流和转换规则进行相应的调整和改进[15-16].数据验证这一过程往往需要进行多次，以达到尽可能高的效率以及高精度地进行数据清洗.

4) 数据清洗.在数据验证过程中，对选择的清洗策略进行了验证，确定其可行性，并利用该策略进行数据清洗操作，数据清洗的流程如图1所示.

图1 数据清洗流程Fig.1 Flow chart of data cleaning

3 N-Gram算法

N-Gram算法是一种大词汇连续语音识别中常用的语言模型，它遵循的思想是每一条数据的出现都有一定的概率，通过假设数据中所有词的出现都会影响其之后的词，但对已出现的词并没有任何影响.通过这种思想可以认为整条记录的出现都有一定的概率，与记录中的每一个词均有关系.因此，本文根据每个词出现的概率，给每条记录计算出一个键值，即N-Gram值，该值在一定程度上代表了该条记录的属性，属性越相近，相似程度越高，该值在数值上就越接近.根据这种特性对数据源中所有的数据进行排序能够将相似重复数据放到一起.

当某条记录中第N个词的出现概率并不是随机出现时，而是与这条记录的前N-1个词息息相关，并且仅与这N-1个词有关，与第N个词后面的词都没有关系，每个词出现的概率相乘，便得到整条数据记录出现的概率，而每个词出现的概率都可以直接从所有数据记录的语料库和重复矩阵中计算得到，这便是N-Gram算法模型.

统计语言模型的数学模型表达式为

(1)

(2)

式(2)即为“马尔可夫假设”.二元的Bigram认为，每条语句中的所有词仅和其前面最相近的那个词有关，与其他任何词都无关，则其概率表达式为

P(S)=P(w1w2…wn)=

(3)

三元的Trigram假设下一个词的出现仅依赖于其前面的两个词，则其概率表达式为

(4)

算法过程描述如下.

1) 数据预处理.在进行数据清洗之前，首先对待清洗的数据进行数据预处理，将其中无法识别的字符串或者带有标识性含义的标点进行处理，例如银行系统中常用的“￥”和“＄”符号，以及处于对数据保密的原因所进行的加密处理符号“*”，这些字符串在后期进行数据清洗的时候，由于其具有相似性，会对清洗结果的准确性产生很大的影响.

例如，待清洗的数据库中有如下5条数据：

①Johnny·Depp，California，PrincetonUniversity，Computer

②Tom·Hanks，Districtofcolumbia，HarvardUniversity，philosophy

③Tom·Hanks，Districtcolumbia，HarvardUniversity，philosophy

④Adam·Sandler，Alabamas，UniversityofCaliforniaBerkeley，PhysicalScience

⑤Leonardo·Dicaprio，Connecticut，UniversityofSou-thernCalifornia，Biology

对它们进行预处理之后的结果如下：

① s1=johnnydeppcaliforniaprincetonuniversityco-mputer

② s2=tomhanksdistrictofcolumbiaharvardunivers-ityphilosophy

③ s3=tomhanksdistrictcolumbiaharvarduniversit-yphilosophy

④ s4=adamsandleralabamasuniversityofcaliforni-aberkeleyphysicalscience

⑤ s5=leonardodicaprioconnecticutuniversityofs-outherncaliforniabiology

2) 建立语料库.扫描整个待清洗数据库，根据N-Gram算法精度建立语料库.当N值为2时，语料库中每一个元素字符串的长度则为1，建立上述5条待清洗记录的语料库，如表1所示.

3) 分 割数据记录，计算重复矩阵.按照N-Gram算法将这5条字符串分割成元字符串，例如，当N值为2时，这5条字符串经过N-Gram算法分割后得到的字符串数组如下：

S1={“jo”，“oh”，“hn”，“nn”，…，“ut”，“te”，“er”}

S2={“to”，“om”，“mh”，“ha”，…，“op”，“ph”，“hy”}

S3={“to”，“om”，“mh”，“ha”，…，“op”，“ph”，“hy”}

S4={“ad”，“da”，“am”，“ms”，…，“en”，“nc”，“ce”}

表1 待清洗记录语料库
Tab.1 Corpus of records to be cleaned

名称数量a24b5c16d9名称数量e17f6g1h11名称数量i31j1k3l13名称数量m7n20o24p10名称数量q0r21s16t16名称数量u10v7w0x0名称数量y11z0

S5={“le”，“eo”，“on”，“na”，…，“lo”，“og”，“gy”}

对这些字符串数组建立重复矩阵M.在重复矩阵中，M(a，b)代表“ab”在整个数据库中的数量，则有

4) 计算N-Gram值.根据式(4)及语料库和重复矩阵，对这5条待清洗数据记录进行计算，得到它们的N-Gram值，即

(p(jo)/p(o))(p(oh)/p(h))(p(hn)/p(n))…(p(er)/p(r))=

4.9×10-37

(5)

P(S2)=7.411×10-36

(6)

P(S3)=4.447×10-35

(7)

P(S4)=1.9e×10-51

(8)

P(S5)=3.7×10-50

(9)

5) 对数据进行清洗.根据步骤4)所得到的N-Gram值对待清洗数据记录进行排序，对所得到的排序结果采用基本的字段匹配算法计算数据记录之间的相似度，当相似度低于规定的阈值时，则判定两者为相似重复记录.

4 实验结果及分析

本文根据上述算法设计了一个基于N-Gram算法的相似重复记录数据清洗流程，通过查全率、查准率和运行速度3个因素对数据清洗过程和基于S-W算法的数据清洗技术进行对比.

查全率是评判数据清洗技术好坏的一个重要指标，查全率越高，代表所检查出来的相似重复记录越多，在一定程度上能够代表数据清洗技术的性能.图2为查全率曲线图.从图2中可以看出，在查全率方面，本文提出的算法较S-W算法有较大的优势，且随着数据量的不断增加，两种算法的查全率都在不断递增.

图2 查全率Fig.2 Recall ratio

查准率是评判数据清洗技术好坏的重要指标，是指所检测出来的相似重复记录中确实为相似重复记录的比例，能够真实地反映出一个算法的好坏.图3为查准率曲线图.从图3中可以看出，本文提出的算法较S-W算法有较大优势，虽然随着数据量的不断增加，该优势有所减缓，但结合查全率的优势可以看出本文算法的优点.

图3 查准率Fig.3 Precision ratio

随着信息的不断发展，数据记录的不断增多，运行时间也作为评判一个算法好坏的标准，本文对两种算法的运行时间进行了对比，结果如图4所示.从图4中可以看出，数量级较低时，S-W算法较本文算法具有较大优势，随着数量级的不断增多，S-W算法的运行时间增长迅速，超过本文算法所提出的数据清洗算法运行时间.

图4 运行时间对比Fig.4 Runtime comparison

5 结 论

通过对相似重复数据记录的结构及产生原因进行分析，提出了一种基于N-Gram算法的相似重复记录的数据清洗技术.该方法通过计算数据记录之间的N-Gram值，将待清洗记录进行排序，并对排序后的结果进行相似度检测，从而提高了相似重复记录的查全率和查准率，且随着数量级的不断增加，本文算法的运行时间优于其他算法.

[1]杨东华，李宁宁，王宏志，等.基于任务合并的并行大数据清洗过程优化 [J].计算机学报，2016，39(1)：97-108.

(YANG Dong-hua，LI Ning-ning，WANG Hong-zhi，et al.The optimization of the big data cleaning based on task merging [J].Chinese Journal of Computers，2016，39(1)：97-108.)

[2]罗景峰，刘艳秋，许开立.基于均匀设计与灰局势决策的智能算法参数设定 [J].沈阳工业大学学报，2010，32(1)：84-89.

(LUO Jing-feng，LIU Yan-qiu，XU Kai-li.Parameter establishment of intelligent algorithm based on uniform design and grey situation decision [J].Journal of Shenyang University of Technology，2010，32(1)：84-89.)

[3]陈明.大数据分析 [J].计算机教育，2014(5)：122-126.

(CHEN Ming.Big data analysis [J].Computer Education，2014(5)：122-126.)

[4]吴斐，唐雁，补嘉.基于N-Gram的VB源代码抄袭检测算法 [J].重庆理工大学学报(自然科学)，2012，26(2)：86-91.

(WU Fei，TANG Yan，BU Jia.A VB source code plagiarism detection method based onN-Gram [J].Journal of Chongqing University of Technology (Natural Science)，2012，26(2)：86-91.)

[5]邵林，黄芝平，唐贵林，等.并行缓存结构在高速海量数据记录系统中的应用 [J].计算机测量与控制，2008，16(4)：527-529.

(SHAO Lin，HUANG Zhi-ping，TANG Gui-lin，et al.Application of parallel cache structure in high-speed mass data recording system [J].Computer Measurement and Control，2008，16(4)：527-529.)

[6]周典瑞，周莲英.海量数据的相似重复记录检测算法 [J].计算机应用，2013，33(8)：2208-2211.

(ZHOU Dian-rui，ZHOU Lian-ying.Algorithm for detecting approximate duplicate records in massive data [J].Journal of Computer Applications，2013，33(8)：2208-2211.)

[7]付印金，肖侬，刘芳.重复数据删除关键技术研究进展 [J].计算机研究与发展，2012，49(1)：12-20.

(FU Yin-jin，XIAO Nong，LIU Fang.Research and development on key techniques of data deduplication [J].Journal of Computer Research and Development，2012，49(1)：12-20.)

[8]Lillibridge M，Eshghi K，Bhagwat D.Improving restore speed for backup systems that use inline chunk-based deduplication [C]//Proceedings of the 11th USENIX Conference on File and Storage Technologies.New York，USA，2013：183-197.

[9]朱灿，曹健.实体解析技术综述与展望 [J].计算机科学，2015，42(3)：8-12.

(ZHU Can，CAO Jian.Summary and prospect on entity resolution [J].Computer Science，2015，42(3)：8-12.)

[10]王琛.Web数据清洗及其系统框架研究 [J].计算机时代，2014(12)：42-44.

(WANG Chen.Research on Webdata cleaning and its system framework [J].Computer Era，2014(12)：42-44.)

[11]Geerts F，Mecca G，Papotti P，et al.The LLUNATIC data-cleaning framework [J].VLDB Endowment，2013，6(9)：625-636.

[12]Tan Y J，Jiang H，Sha H M，et al.SAFE：a source deduplication framework for efficient cloud backup ser-vices [J].Journal of Signal Processing Systems，2013，72(3)：209-228.

[13]殷秀叶.大数据环境下的相似重复记录检测方法 [J].武汉工程大学学报，2014，36(3)：66-69.

(YIN Xiu-ye.Method for detecting approximately duplicate database records in big data environment [J].Journal of Wuhan Institute of Technology，2014，36(3)：66-69.)

[14]Nguyen T T，Hui S C，Chang K.A lattice-based approach for mathematical search using formal concept analysis [J].Expert Systems with Applications，2012，39(5)：5820-5828.

[15]党小超，高琪，郝占军.基于小波变换的分布式WSN数据融合模型研究 [J].计算机工程与应用，2014，50(22)：97-101.

(DANG Xiao-chao，GAO Qi，HAO Zhan-jun.Research on model of distributed date aggregation in WSN based on wavelet transform [J].Computer Engineering and Applications，2014，50(22)：97-101.)

[16]谭霜，何力，陈志坤，等.云存储中一致基于格的数据完整性验证方法 [J].计算机研究与发展，2015，52(8)：1862-1872.

(TAN Shuang，HE Li，CHEN Zhi-kun，et al.A method of provable data integrity based on lattice in cloud storage [J].Journal of Computer Research and Deve-lopment，2015，52(8)：1862-1872.)

(责任编辑：钟 媛 英文审校：尹淑英)

Data cleaning technology based onN-Gram algorithm

MA Ping-quan1,2, SONG Kai1,2, JI Jian-wei1

(1. College of Information and Electrical Engineering, Shenyang Agricultural University, Shenyang 110866, China; 2. School of Automation and Electrical Engineering, Shenyang Ligong University, Shenyang 110159, China)

Aiming at the plentiful approximately duplicate data in the database, the attribute structure of approximately duplicate records and the causing reason were analyzed. The data records were calculated with theN-Gram algorithm to get the key values, namelyN-Gram values, which represented the attribute of every record. According to the key values, the data records in the database were ordered so as to form a well-organized database. In addition, the similarity of data records in the database was calculated. The identified approximately duplicate records were cleaned by applying the arranged combination cleaning idea. The experimental results show that theN-Gram algorithm effectively increases the recall ratio and precision ratio of approximately duplicate data records.

similarity; approximately duplicate record; attribute; ordering; combination; data cleaning; recall ratio; precision ratio

2016-06-28.

辽宁省教育厅科学研究项目(LG201610).

马平全(1975-)，男，辽宁丹东人，讲师，博士生，主要从事信号检测与处理等方面的研究.

17∶40在中国知网优先数字出版.

http：∥www.cnki.net/kcms/detail/21.1189.T.20161222.1740.040.html

10.7688/j.issn.1000-1646.2017.01.13

TP 311.11

A

1000-1646(2017)01-0067-06