对基于SNM数据清洗算法的优化

张建中¹，方正²，熊拥军¹，袁小一¹

(1. 中南大学 信息科学与工程学院，湖南 长沙，410083；

2. 中南大学 化学化工学院，湖南 长沙，410083)

摘  要：对基本邻近排序算法SNM(basic sorted-neighborhood method)进行分析，指出其不足；提出基于SNM算法的一种优化算法，通过采集中南大学冶金矿物工程机构知识库的2 000多条文献记录作为样本数据进行实验研究，对记录的“脏数据”按照DC标准和相关规范进行清洗与排重。研究结果表明：与SNM算法相比，在同样的运算环境下，优化算法在招回率、误识别率和执行时间上有明显优势。

关键词：数据挖掘；数据清洗；重复记录；SNM算法

中图分类号：TP393          文献标志码：A         文章编号：1672-7207(2010)06-2240-06

Optimization algorithm for cleaning data based on SNM

ZHANG Jian-zhong¹, FANG Zheng², XIONG Yong-jun¹, YUAN Xiao-yi¹

(1. School of Information Science and Engineering, Central South University, Changsha 410083, China;

2. School of Chemistry and Chemical Engineering, Central South University, Changsha 410083, China)

Abstract: The basic sorted-neighborhood method (SNM) was introduced and the analysis was made on its deficiency. An improved algorithm of data cleaning based on SNM was put forward. And the experiments were made on more than    2 000 sample records data from the mineral metallurgy institutional database of Central South University. Key task was cleaning dirty data and removing approximately duplicate records according to dublin core (DC) standard and other criterion. The results show that the improved algorithm is better than SNM in the aspects of recall, precision and run time in the same computer condition.

Key words: data mining; data cleaning; approximately duplicate records; SNM algorithm

在构建机构知识库时，其中一项重要的工作是将收割的临时元数据仓储中的DC(Dublin core)元数据进行规范化^[1]，并将规范后的元数据写入DC元数据中心。由于这些元数据来自不同的加工单位，存在录入错误、语义表示不一致、拼写错误和记录重复等情况，数据质量差异大，尤其是重复记录信息严重，影响查全率和查准率，所以，在元数据导入数据中心前，需要对元数据进行清洗。在处理大的数据集时，匹配重复记录是一项非常耗时的过程。目前，用于相似重复记录识别的算法为基本邻近有序法(SNM)，整个匹配过程相当于对2个记录集做笛卡尔积，算法时间复杂度较大^[2]。在此，本文作者分析SNM算法的缺陷，提出一种基于排序关键字预处理、不同关键字多趟邻近排序、窗口移动速度与大小可伸缩的相似重复记录识别的算法，并通过实例说明优化算法的正确性。

1  元数据清洗

数据清洗就是分析“脏数据”产生的原因和存在形式，利用现有技术手段和方法去清洗，并将它们转化为满足要求的数据，从而提高数据集的质量^[3]。数据清洗(Data cleaning)的目的是检测数据中存在的错误和不一致，剔除或者改正，这样就提高了数据的质量^[4]。数据清洗模型如图1所示，数据由临时数据库装载到中心元数据仓储时，数据清洗过程主要由数据标准化、数据解析、数据增强和重复数据归并4步组成，数据标准化完成数据格式的规范化和数据表达方式的同一化；数据解析主要完成数据字段的拆分和合并；数据增强主要对原始数据进行补充，保证数据的完整性；重复数据归并主要是对相似重复记录的清除与合并。

图1  数据清洗模型

Fig.1  Data cleaning model

1.1  数据清洗工作流程

为实现数据清洗自动执行，关键是清洗规则定义，清洗流程如图2所示。

图2  数据清洗流程

Fig.2  Data cleaning flow chart

在规则中定义了错误类型及其相应的处理策略。例如，在遇到空值时，是应该丢弃这条记录还是将某个特定的值填入，这都是由规则定义文件中的错误类型(error type)及其策略(policy)、处理类(op_class)来决定。当程序遇到与规则描述文件中预定义的错误类型相匹配的错误时，就按照预定义的错误处理策略进行处理，逐条记录处理后，生成目标结构化数据，并将结果追加到中心元数据仓储。这些过程都是由清洗引擎来调度执行。清洗引擎是系统中最重要的部件，整个系统数据清洗质量取决于数据清洗引擎的执行   情况。

1.2  清洗规则定义

清洗规则包含2部分：检查数据完整性的规则和当违反完整性时所采用的处理方法。清洗规则用一种描述方法来描述，同时将这些表述放到清洗规则文件中，以便调度执行或者跟踪和修改。本文作者采用对象的描述方法对清洗规则进行描述。在清洗框架中，对于清洗规则采用批量执行。清洗规则定义文件中规则的描述见文献[5]：

1.3  数据标准化

由于不同的数据源对于同样性质的数据表现的形式不同，不利于信息的检索，数据的标准化主要表现在数据格式的规范化和数据表达方式的统一化。

在数据仓储中，有的元数据日期类型的数据字段表现形式复杂，例如，YYYY—MM—DD，MM/DD/ YYYY以及其他的形式。本模块的作用就在于将同一数据以同种形式表现出来，统一格式为符合ISO 8601 [W3CDTF]规范，并使用YYYY-MM-DD的格式^[6]。

对于“语种”字段，不同系统录入规则也各不相同，如中文，CHN，CN和Chinese等，可统一采用RFC 1766所定义的语种代码规范，此标准定义了1个由2个英文字母组成的语言代码。如中文用CN表示。

1.4  数据解析

数据存在不同的细节级别称为粒度。粒度越高，表示综合程度越高。在中心数据仓储中的查询涉及不同的细节，不同的数据源对信息的描述可能具有不同的粒度，这使得对来自不同数据源的数据很难进行相应的比较。本模块对结构松散的来自不同数据源的原始数据进行分析，使之具有良好的粒度以适合信息的检索需要，有些字段需要拆分，有的则需要合并。

如期刊元数据中的作者字段，有的数据源将所有作者都著录在1个字段中，需要将其拆分为主要责任者(creator)和其他责任者字段(contributor)。

对于主题词，需要将多个合并在同一字段中，并以统一的分隔符分隔。还有如文献引用字段的合并等。

1.5  数据增强

在向中心元数据仓储装载数据的过程中，原始数据可能不完整。因此，有必要对原始数据进行补    充，这是数据增强的任务。数据增强通常包含以下3种方式：

(1) 对数据中不完整的字段补充必要的信息，使之完整。例如：期刊资源中文献标识符URL，有的只定义了参数值，并未给出完整的URL地址，需要补充完整，才可定位到资源对象。

(2) 为空值字段设置合适的值。如期刊数据记录中有的填写了语种值，有的没有填写，对未填写的需要补充。

(3) 以增加字段的方式添加额外的信息。多数据源时，并非所有的数据源都能保证含有所有所需要的字段。在这种情况下，必须为某些缺少的数据源添加字段以保持数据信息的完整性。例如：期刊资源的资源类型、来源、入库时间等字段。

2  重复记录归并

重复记录是指它们在语义上是相同的，也就是说，它们指的是现实世界中同一实体，但它们之间可以有一些不同的其他属性，既占用了空间，也给检索结果造成记录集的冗余。

为了从数据集中检测并归并重复记录，首要的问题就是判断2条记录是否是重复的。最可靠的检测重复记录的办法是比较数据库中每对记录。目前，所采用的算法是基本邻近有序法(Basic sorted- neighborhood method，SNM)，但该算法时间复杂度大，需要进行N(N-1)/2次比较(其中：N是数据库中记录的总数)。排序-合并方法是检测数据库中完全重复记录的标准方法^[6]。它的基本思想是：先对数据集排序，然后，比较相邻记录是否相似。这一方法也为在整个数据库级上检测重复记录提供了思路。目前，已有的检测重复记录的方法也大多以此思想为基础来优   化^[7]。现存的重复记录清除方案主要是基于标准的检测完全相同的2条记录的方法^[8]。Hernandez等^[9]提出在不同的键上多次排序，并分别计算邻近记录的相似度，最后，综合多次计算的结果完成记录匹配过程。李坚等^[10]提出可变移动窗口，对不同属性的重要性设置不同权值，根据总相似度决定相似重复记录。邱越峰等^[11]提出一种基于N-Gram的聚类算法，在检测的同时能自动校正单词的插入、删除错误，提高检测精度，Monge等^[12-13]先将表中所有记录排序，然后，使用包含一定数量群集cluster的优先队列按顺序扫描所有的排序记录并动态地将它们聚类。Kukich等^[14-15]根据用户定义的键值来重排表记录，并采用滑动窗口以成对的方式(pair-wise)比较窗口内的记录。

2.1  基本邻近排序算法

2.1.1  算法描述

步骤1  创建排序关键字。抽取记录属性的一个子集序列或属性值的子串，计算数据集中每一条记录的键值。

步骤2  排序。根据该排序关键字对整个数据集进行排序。尽可能地使潜在的可能的重复记录调整到一个邻近的区域内，从而对于特定的记录可以将进行记录匹配的对象限制在一定的范围之内。

步骤3  合并。在排序后的数据集上滑动一个固定大小的窗口，数据集中每条记录仅与窗口内的记录进行比较。窗口的大小为W条记录，则每条新进入窗口的记录都要与先前进入窗口的W-1条记录进行比较来检测重复记录，最先进入窗口内的记录滑出窗口，最后一条记录的下一条记录移入窗口，再把此W条记录作为下一轮比较对象。图3所示为SNM排序数据集示意图。

图3  SNM排序数据集示意图

Fig.3  Schematic diagram of SNM method

SNM算法采用滑动窗口的方法，每次可以只比较窗口中的W条记录，提高了匹配效率；采用滑动窗口也极大地提高了比较速度，只需要进行W×N次比较，显然，W比N小得多。但是，SNM方法存在以下缺陷^[10]：(1) 对排序关键字的依赖性大；(2) 滑动窗口的大小W的选取较难控制。

2.1.2  基本邻近有序算法的优化思想

针对SNM算法的缺点，对传统SNM方法中的缺陷进行如下改进^[16]：

(1) 排序关键字预处理。针对传统的SNM方法对排序关键字中错误的敏感性，在根据选取的排序关键字对数据集进行排序之前，先对其进行预处理，采用外部源文件更正排序关键字中的错误，统一数据格式。

(2) 选择不同的关键字执行多趟邻近排序。每趟邻近排序，选择不同的关键字。

(3) 窗口移动速度和大小可伸缩。采用伸缩窗口的方法，使得在记录的比较过程中，窗口移动的大小和速度可以在一定的范围内根据相似规模进行调整。

2.1.3  优化算法

算法的参数有2个：窗口最小值W₁，窗口最大值W₂；算法中主要变量有3个：窗口中相似记录数M_{atch_num}，移动速度v和当前窗口大小W_i。

每次窗口的大小W_i为：

       (1)

W_i窗口中，相似记录条数M_{atch_num}可取值为0，1，2，…，W_i-1条。式(1)中，相似记录越多，窗口越大。当相似记录为W_i-1条时，窗口最大为W₂；当没有相似记录时，窗口最小为W₁。每次窗口移动的速度v_i为：

    (2)

窗口移动速度v_i以线性的速度变化。当窗口中相似记录多时，移动速度小，如全部相似时，移动速度为1；当相似记录越少时，移动速度越大，如没有相似记录时，移动速度为v_i。

2.1.4  重复记录清洗算法效率度量标准

衡量重复记录检测算法效率的标准是算法是否能把数据集中存在的所有重复记录都检测出来。常用的标准主要有：召回率(R_ecall)和误识别率(F_alse)^[17]。

(1) 招回率(R_ecall)。定义为被重复记录检测算法正确识别出的重复记录占数据集实际包含的重复记录的百分比。

假设有7条记录{X₁, X₂, X₃, Y₁, Y₂, Y₃, Z₁}，其中{X₁, X₂, X₃}和{Y₁, Y₂, Y₃}分别是记录X和Y的重复记录。通过一个数据清洗的过程识别出{X₁, X₂, Z₁}和{Y₁, Y₂}是重复记录，则其R_ecall=(4/6)×100%=66.67%。

(2) 误识别率(F_alse)。定义为被重复记录检测算法错误地识别为重复记录的数目占被算法识别为重复记录总数的百分比。误识别率越低，表明算法结果的置信度就越高。

在上面的例子中，检测算法错误地把Z₁识别为1条重复记录，则有F_alse=(1/5)×100%=20%。

3  实验方法与结果

实验中所采用的数据集是矿物工程机构库中的50种期刊的2 000多条文献记录，每条记录有23个属性，属性如表1所示，清洗前、清洗后数据质量的记录例子如表2所示。

SNM法和SNM优化算法均采用同一计算环境。各种情况下检测重复记录算法效率的结果如表3所示。从表3可以看出：在排序之前对排序关键字进行预处理，以及利用大小与速度变化窗口的SNM优化算法在效率上要优于传统的SNM算法；由于采用了窗口的大小和移动速度可变的技术，执行时间明显比传统SNM算法少；进行关键字预处理后，招回率明显提高，误识别率得到降低。

表1  期刊元数据信息

Table 1  Metadata information of journal

表2  数据清洗中的部分“脏数据”实例

Table 2  Partly dirty data examples of journal at data cleaning

表3  SNM与优化SNM算法效率的比较

Table 3  Comparison of efficiency of SNM and improved SNM algorithm

4  结果分析与讨论

(1) 数据标准化问题：例如有的发表时间表现为2007.12.10，有的时间表现为2007-1-11和20071015等，故需要统一日期表现格式，必须执行数据的标准化动作。在这里，使用YYYY-MM-DD作为清洗后的日期格式；对语种字段，表现形式有CN、中文和CHN，必须执行标准化操作，统一格式为CN。还有如ISSN号分隔符的不一致、2个汉字的作者字段中有空格、期的字符串位数不同等，这些都需要进行标准化操作。

(2) 数据解析问题：对具有多作者的期刊论文来说，需要将第1作者与其他责任者分解，放在不同的字段中，于是，这就需要数据解析过程。

(3) 数据增强问题：数据中同样存在一些空缺的字段，例如语种、资源类型、来源和入库时间等，可以使用数据增强这个阶段来处理这些问题。

(4) 记录归并问题：在这些记录中，对于“铜蓝的细菌氧化浸出”这篇论文存在2条记录，表现为同一数字对象，故需要执行重复记录归并的步骤来消除重复。

通过调用清洗引擎对多个清洗过程按照工作流程来清洗。与清洗前数据比较，清洗后的数据消除了大部分的错误数据，从而保证了数据库质量。

5  结论

(1) 给出了数据清洗的4个过程和清洗流程：数据标准化、数据解析、数据增强和重复数据归并，并且提出了清洗规则的定义。对数据标准化存在的问题进行分析，采取数据标准化、数据解析和数据增强技术提高了数据质量。

(2) 阐述了SNM算法，指出存在的缺陷：一是窗口的大小选取对结果影响很大；二是对排序关键字的依赖性大，影响了匹配的效率与精度。

(3) 采取排序关键字预处理、选择不同的关键字执行多趟邻近排序以及窗口移动速度和大小可伸缩等方法，提出了SNM优化算法。

(4) 证明了优化的SNM算法优于传统的SNM算法，有效地提高了数据质量。目前，该方法已在实际中得到应用。

参考文献：

[1] 中国高等教育文献保障系统管理中心. 中国高等教育数字图书馆技术标准与规范[M]. 北京: 中国高等教育文献保障系统, 2004: 312-315.

Administrative Center for China Academic Library and Information System. China academic digital library and information system technical standards and specifications[M]. Beijing: China Academic Library and Information System, 2004: 312-315.

[2] 郭芝懋, 周傲英. 数据质量和数据清洗研究综述[J]. 软件学报, 2002, 13(11): 2076-2082.
GUO Zhi-mao, ZHOU Ao-ying. Research on data quality and data cleaning: A survey[J]. Journal of Software, 2002, 13(11): 2076-2082.

[3] 刘波, 杨路明, 雷刚跃, 等. 面向XML 数据库的智能数据清洗策略[J]. 计算机工程, 2008, 34(16): 16-17.

LIU Bo, YANG Lu-ming, LEI Gang-yue, et al. Intelligence data cleaning strategy for XML database[J]. Computer Engineering, 2008, 34(16): 16-17.

[4] Rahm E, Do H H. Data cleaning: Problems and current approaches[J]. IEEE Data Engineering Bulletin, 2000, 23(4): 3-13.

[5] Raman V, Hellerstein J M. Potter’s Wheel: An interactive data cleaning system[C]//Proceedings of the 27th VLDB Conference. San Francisco: Morgan Kaufmann Publishers Inc, 2001: 100-109.

[6] Bitton D, DeWitt D J. Duplicate record elimination in large data files[J]. ACM Transactions on Database Systems, 1983, 8(2): 255-265.

[7] Hernandez M A, Stolfo S J. Real-world data is dirty: data cleansing and the merge/purge problem[J]. Journal of Data Mining and Knowledge Discovery, 1998, 2(1): 9-37.

[8] QIU Yue-feng, TIAN Zong-ping, JI Wen-yun, et al. An efficient approach for detecting approximately duplicate database records[J]. Chinese Journal of Computers, 2001, 24(1): 69-77.

[9] Hernandez M A, Stolfo S J. Real-World data is dirty: Data cleansing and the merge/purge problem[J]. Data Mining and Knowledge Discovery, 1998, 2(1): 9-37.

[10] 李坚, 郑宁. 对基于MPN数据清洗算法的改进[J]. 计算机应用与软件, 2008, 25(2): 245-246.
LI Jian, ZHENG Ning. Improvement on the algorithm of data cleaning based on MPN[J]. Computer Applications and Software, 2008, 25(2): 245-246.

[11] 邱越峰, 田增平, 季文赟, 等. 一种高效的检测相似重复记录的方法[J]. 计算机学报, 2001, 24(1): 69-77.

QIU Yue-feng, TIAN Zeng-ping, JI Wen-yun, et al. An efficient approach for detecting approximately duplicate database records[J]. Chinese Journal of Computers, 2001, 24(1): 69-77.

[12] Monge A E. Matching algorithm within a duplicate detection system[J]. IEEE Data Engineering Bulletin, 2000, 23(4): 14-20.

[13] Monge A E, Elkan C P. An efficient domain-independent algorithm for detecting approximately duplicate database records[C]//Proceeding of the ACM-SIGMOD Workshop on Data Mining and Knowledge Discovery. Tucson: ACM, 1997: 23-29.

[14] Kukich K. Techniques for automatically correcting words in text[J]. ACM Computing Surveys, 1992, 24(4): 377-439

[15] Hernandez M, Stolfo S. The Merge/Purge problem for large databases[C]//Proceeding of ACM SIGMOD International Conference on Management of Data. Boston: ACM, 1995: 127-138.

[16] 张建中. 数字资源整合与个性化服务中关键技术研究[D]. 长沙: 中南大学信息科学与工程学院, 2008: 43-45.

ZHANG Jian-zhong. A study of the key technology for digital library resource integration and personalized services[D]. Changsha: Central South University. School of Information Science and Engineering, 2008: 43-45.

[17] Lee M L, Ling T W, Low W L. IntelliClean: A knowledge-based intelligent data cleaner[C]//Proceedings of the 6th ACM SIGKDD International Conference on Knowledge Discovery and Data Ming. Boston: ACM Press, 2000: 290-294.

(编辑 刘华森)

收稿日期：2009-11-15；修回日期：2010-03-02

基金项目：国家自然科学基金资助项目(50874119)

通信作者：张建中(1955-)，男，河北张家口人，博士，教授，从事数据挖掘、信息管理研究；电话：0731-88836750；E-mail: jzzhang@mail.csu.edu.cn