一种客户关系数据库相似重复记录清洗算法

郭 文 龙

(福建江夏学院 电子信息科学学院，福建 福州 350108)

商业银行利用银行卡为客户办理存贷款手续，航空公司、大型超市、连锁酒店等企业为了营销需要，经常发放各类会员卡，这些卡片信息随同客户资料均保存在企业的客户关系数据库中统一管理．现实生活中，一个人在同一个商业银行办理多张银行卡、在同一个企业办理多张会员卡的情况比比皆是，每张银行卡或会员卡都对应客户关系表中的一条记录，这就造成同一客户的记录在同一个数据库或数据表中出现多条．在所有的客户卡片中，有些卡片可能从办理之后就从未使用过，这些卡片成了名符其实的“废卡”，这就使得各类客户管理系统中存在大量的无用数据，这些无用数据造成系统服务器存储空间极大浪费，此外随着数据记录数的增多还导致查询速度变慢等问题出现．如何定期删除无用的客户记录，如何合并同一客户在数据库中的多条记录，进而提高空间利用率并提高查询速度就成了一个好的系统应解决的问题．

1 概述

一个客户关系数据库中拥有多条这样的记录，它们的多数属性相等、少部分属性相似或足够相似、个别属性不同，则称这样的多条记录为相似重复记录．在银行客户管理系统和各类企业的会员管理系统中，存在许多相似重复记录．这些记录的共性是姓名、性别、身份证号等属性一样，卡号属性不一样，地址属性相似或相等．如果能把这些相似重复记录合并，即在关系表中通过增加列，如增加卡号列，将原来卡号只有一列依实际情况修改为“卡号1、卡号2…卡号N”的N列结构，就可以大大降低记录数，从而提高存储空间利用率，还可以加快查询速度，取得多赢的效果．相似重复记录示例如表1所示，经合并后如表2所示．

表1 相似重复记录示例

表2 记录合并后情况表

由表2可知，张三在原数据表中存在三条记录，合并后只含一条记录，显然提高了空间利用率，且随着数据记录数的减少，数据的查询、插入和删除等操作速度也将大大提高．数据合并前必须将疑似相似重复记录聚集到相邻位置，聚集采用排序的方法实现；聚集之后还得判定相邻记录是否为相似重复记录，如果是再进行合并．

综上，客户关系数据库相似重复记录清洗流程如图1所示．

2 常用相似重复记录检测算法

相似重复记录检测的最简单方法是用一条记录和数据库中其它记录逐一对比，这种方法实现简单，精确度最高，然而时间耗费是极其可怕的，其时间复杂度达到O(n2)，所以在实际应用中是不可取的．

相似重复记录清洗方法最常用的是基于排序-合并的方法，即先利用数据表的某个属性或若干个属性进行排序，再对排好序后的记录在邻近的宽度内比对，然后对检测到的相似重复记录进行清洗与合并．常见的基于排序-合并方法的相似重复记录检测算法有 SNM 算法(Sorted-Neighborhood Method)[1-2]、MPN算法(Multi-Pass Sorted Neighborhood，MPN)[1-2]．SNM 算法的基本思想是设定若干条记录宽度的窗口，在窗口内进行记录的相似重复判定．该算法实现简单，算法的时间复杂度为O(nlogn)，排序是时间开销最大的一环．MPN算法对SNM算法进行了改进，该算法使用不同的关键字进行排序，每次排序后单独在一个较小的窗口内使用SNM算法判重．

图1 相似重复记录清洗流程

3 客户关系数据库相似重复记录清洗算法

经研究大量的企业客户关系数据库，发现客户关系数据表的属性个数均不多，一般为10个左右，且客户信息基本包含了姓名、性别、身份证号、住址等属性．对于住址等属性由于描述方式不一或采用简写等方面的原因，造成同一个人在同一张表中出现了多条住址不一样的记录．然而如果两条或多条记录相似重复，其姓名、性别和身份证号等属性必定相同，所以对于客户关系数据表判重前的排序使用“姓名+性别+身份证号”的多关键字排序方式．经排序，相似和重复记录已位于邻近的区间内．在排序的基础上，对相邻数据记录进行比对，如构成相似重复记录，则进行合并，合并后删除原来的两条记录，将新合并的记录插入数据表，然后用新合并的记录和之后的记录再进行比对，以此类推．

记录的排序、合并和删除实现起来均非常简单，所以清洗中最麻烦的一环便是数据记录的比对即相邻记录相似重复的判定．

此外，客户关系数据库中常出现许多无用的数据，即“废卡”信息，为了减少这些“脏数据”占用系统资源，也为了提高相似重复记录的清洗速度，在相似重复记录清洗前有必要对这些数据先行清洗．由于客户关系数据库都会记录卡片使用情况，如用卡时间等信息，可以根据这些信息对所有的记录进行扫描，导出无用的数据，由人工方式判断是否予以删除．

由上所述，针对客户关系表的数据特点，提出记录清洗算法思路，具体实现步骤如下．

步骤一： “废卡”记录等“脏数据”清洗；

步骤二： 根据某个属性或若干个属性进行排序；

步骤三： 根据关系表的属性重要性，为部分属性设定不同的权重Wi，权重之和为1，假设关系表中设定权值的属性个数为n，判断窗口内记录的属性，给定一个集合Ai{0,1}，如果属性值取值相等，Ai等于1，

否则Ai等于0，求

步骤五：将合并后的记录插入数据表，删除构成相似重复的两条记录；

步骤六：用新合并的记录参与随后的记录判重．

在客户关系表中最重要的属性莫过于身份证号了，所以身份证号的权值设置为最大．假设有数据记录如表1所示，依次为身份证号、姓名和性别三个属性分配权值，权值分别为 0.5、0.3、0.2，设置记录相似度 U =0.7．依据上述算法，表1中前两条记录的清洗过程如下：

1) 根据身份证号进行排序，排序结果同表1；

2) 计算 Ai，A1=1，A2=1，A3=1；

5) 合并两条记录，删除原两条记录，新记录参与之后的相似重复记录清洗．

经两次清洗合并，表1的三条记录清洗为表2的一条记录．合并时需考虑属性取值不同的合并策略，如表1中的三条记录是相似重复记录，而地址和卡号各不相同，必须分别对其进行处理．卡号的合并处理较为简单，只需在关系表中增加新列，在新列中添加相似重复记录中相应的属性值即可．对于地址的处理，目前的技术也较为成熟，如果相似重复记录的地址数据均一样，则直接进行合并，不做任何处理；如果不一样，必须清洗之后再合并，目前常用的地址清洗方法是基于特征字、基于地址词典和基于规则的方法，文献[3-5]对地址的处理方法均达到较好的效果，所以可以将地址导出参照相关文献进行清洗后，再将规范的地址导入关系表．

然而，因人为输入等原因，导致关系表中出现如表3所示的两条记录，两条记录的性别、身份证号和地址均完全相同，第二条记录因输入错误将“张”输入成“章”，显然两条记录互为相似重复记录，这种情况可将记录导出，设置同音字表，通过查询同音字表由机器判断清洗，或由人工判断修正后再进行清洗．

表3 相似重复记录示例表

4 小结

在客户关系数据库中存在大量的客户信息，有些客户的信息是以多条记录的方式存在于同一关系表中，这些记录构成了相似重复记录．通过制定算法对相似重复记录进行清洗并合并，可以提高系统空间的利用率，降低记录数量还可以提高新数据插入、无用数据删除和查询的速度．本文提出利用关系表的若干个属性对关系表的数据记录进行排序，对排序后的相邻记录通过设置属性权值和记录相似度闸值，求相邻记录的相似度，如相邻记录构成相似重复，再对其清洗并合并，取得了较好的效果．然而算法的属性权重和记录相似度闸值是凭经验设置，实际应用中应设置多大较合适，文中未有定论，这将是下一步需进一步研究的地方．

[1] HERNANDEZ M A, STOLFO S J. The Merge/Purge Problem for Large Databases[C]//In: Proceedings of the ACM SIGMOD International Conference on Management of Data, San Jose, California,1995:127-138.

[2] 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(1): 9-37.

[3] 张雪英,闾国年,李伯秋,等.基于规则的中文地址要素解析方法[J].地球信息科学学报,2010,12(1):9-16.

[4] 程昌秀,于滨.一种基于规则的模糊中文地址分词匹配方法[J].地理与地理信息科学,2011,27(3):26-29.

[5] 刘哲,夏秀峰,宋晓燕,等. 一种中文地址类相似重复信息的检测方法[J].小型微型计算机系统,2008,29(4):726-729.