随着大数据时代的到来，每天都产生大量的数据。这些海量数据中通常包含着一些重要信息，而这些信息则往往是一些决策支持系统进行决策的依据。但庞大的数据集中除了含有携带重要信息的数据之外，往往也夹杂着一些无用的、或是错误的、或是不一致的、或是不完整的、或是重复的数据，这些数据的存在严重影响数据库的数据质量，为以此而建立的种种商用决策系统带来隐患，甚至可能因此而给相关企业带来巨大损失。为此，如何把这些所谓的“脏数据”洗出数据库系统，就显得非常重要。本文首先简单介绍了数据清洗与相似重复记录检测算法的相关概念，接着介绍了相似重复记录的清洗原理。对基本近邻排序算法SNM进行了深入分析和研究，指出其中的不足，在此基础上给出改进策略并加以应用，实践证明这些改进算法，在关键性能上有了明显改善。 一种相似重复记录检测算法的改进与应用 李军 随着大数据时代的到来，每天都产生大量的数据。这些海量数据中通常包含着一些重要信息，而这些信息则往往是一些信息决策支持系统进行决策的依据。但庞大的数据集中除了含有携带重要信息的数据之外，往往也夹杂着一些无用的、或是错误的、或是不一致的、或是不完整的、或是重复的数据，这些数据的存在严重影响数据库的数据质量，也为以此而建立的种种商用决策系统带来隐患，甚至可能因此而给相关企业带来巨大损失。这些给数据库系统带来副作用的数据，通常被称之为“脏数据”。对于庞大的数据库系统而言，“脏数据”的存在是无法避免的，比如数据表示方法不同、统计时间不一致、数据来源不同或者是数据录入错误等原因，都可能导致应用系统数据库中存在着“脏数据”。这些脏数据的存在不仅可能导致信息失真，还极有可能为依此而建立的决策支持系统以及应用商务智能带来隐患[1]。因此，数据进入实用系统前进行数据清洗是非常重要的一个环节。 数据清洗（data cleaning）也就是数据清理，其利用有关技术如数理统计、数据挖掘或预定义的清理规则将脏数据转化为满足数据质量要求的数据[2] 。数据清洗从数据的准确性、完整性、一致性、惟一性、适时性、有效性几个方面来处理数据的丢失值、越界值、不一致代码、重复数据等问题。
相似重复记录清洗 数据清洗就是过滤或者修改那些不符合要求的数据，主要体现在相似重复记录清洗、不完整数据清洗和错误数据清洗等方面。其中，相似重复记录清洗是数据清洗工作非常重要的一个环节。 相似重复记录的概念。相似重复记录指同一个现实实体在数据集合中用多条不完全相同的记录来表示,由于它们在格式、拼写上的差异,导致数据库管理系统不能正确识别[3]。简单点说,在同一个数据库系统中，如果出现某些字段的值相同或足够相似的两条记录,即可认定其为相似重复记录。表1给出了一个相似重复记录的实例。 表1 相似重复记录实例 姓名 性别 身份证号 地 址 联系方式 赵明 男 340102198802153316 合肥市长江路138号 15396375548 赵明 男 340102198802153316 合肥市庐阳区长江路杏花小区 05512842365 赵明 男 340102198802153316 安徽合肥长江路138号 32516362@qq.com
相似重复记录的清洗过程。在一个商用的客户信息管理系统中，多次采集同一个客户对象，可能导致在数据库中存在多条相似而不完全相同的记录存在，这些记录绝大多数都是相似重复记录。这些相似重复记录的存在，不仅浪费存储空间和检索时间，甚至可能为依此建立的决策系统带来错误的决策，所以必须对其进行清洗。其清洗过程一般如图一所示。 由图一可见，相似重复记录清洗一般包括以下几个阶段：①数据排序；②对相邻记录进行相似重复记录判断；③数据合并三个步骤。 数据排序是数据预处理的方式之一，其依据排序关键字对数据库中的记录进行排序处理，实现记录的初步聚类。这一环节的主要目的，就是把可能的相似重复记录尽可能地排在一起。排序的结果显然依赖于排序关键字，采用不同的排序关键字，可能得到差异很大的排序结果。因此，如何选择和处理排序关键字，在数据排序这一环节中，显得尤为重要，可以说它是实现相似重复记录清洗的重要基础。 图一 相似重复记录清洗过程 相似重复记录的检测是数据清洗的关键环节。最简单可靠的相似重复记录检测方法即是用一条记录与数据集中的每条记录进行匹配比较。若数据仓库中的记录总数为n，则共需要进行n(n-1)/2次比较，其时间复杂度为O(n2),这对于海量数据来说，显然是不可取的方法。因此，排序-合并方法成为检测数据库中完全重复记录的标准方法[2]，其基本思想是，先以数据表的某个特征属性或组合属性对数据表进行排序聚类处理，尽可能地使相似重复记录聚集在一起，再将记录与邻近范围内的记录进行比较，最后对检测到的相似重复记录进行清洗与合并。由于进行相似重复记录检测是在一个经过聚类处理后得到的子集范围内实现，其算法的时间复杂度为O(nlogn),检测效率有非常明显的提升。目前已有的相似重复记录检测方法大多依此思想为基础[3]。 数据合并是对数据集进行增删补改的清洗阶段。经过检测被认定为相似重复记录的两条记录需要进行数据合并操作。如果两条相似重复记录是完全重复记录，那进行合并时非常简单，只需将两者中删除其一即可；如果仅是相似重复记录，则进行合并时，需将两条记录合并为一条新记录，新记录中保留被合并的两条记录中的关键属性(排序关键字)和相同属性，对于差异化的属性则根据具体实用系统的要求而制定的合并规则进行合并。 基本近邻排序算法 目前基于“排序-合并”思想的相似重复记录检测方法有很多，比较著名的有基本近邻排序算法、多趟近邻排序算法和优先权队列算法。多趟近邻排序算法和优先权队列算法虽然相较于基本近邻排序算法在性能上有了一定的改善，但它们都是在基本近邻排序算法的基础上进行改进而形成的算法，且依然有各自的缺点。 基本近邻排序算法(Basic Sorted-Neighborhood Method,SNM算法)是比较成熟的相似重复记录检测算法，它包括一下三步： 确定排序关键字。抽取记录属性的一个子集序列或属性值的字串作为排序关键字。被抽取作为排序关键字的属性通常是对记录具有较强区分度的属性或属性子串。 排序。依据该排序关键字对数据集进行排序，尽可能使潜在的可能的重复记录聚集在一个邻近的区域内。为了实现这一目的，在确定排序关键字时，需要做更为深入的研究。如何确定排序关键字，对于排序结果的影响起到关键作用。 合并。为数据集设定一个大小固定的可滑动窗口，新进入滑动窗口的记录仅与窗口内的其它记录进行比对，比较的次数由窗口的宽度决定。若窗口的大小为w条记录，则新进入窗口的记录将与先进入窗口的w-1条记录进行比较，以判断记录是否重复。若判断出两条记录是相似重复记录，则对它们进行合并操作。最先进入窗口的记录最先滑出窗口，最后一条记录的下一条记录移入窗口，再把此w条记录作为下一轮比较对象，直到数据集最后。 基本近邻排序算法先通过排序把可能的相似重复记录尽可能的聚集在一起，再引进滑动窗口，每次只比较窗口中的w条记录，通过总共N*w次的比较，实现相似重复记录的检测。通常情况下，w总是远远小于N，所以采用这种方法进行相似重复记录检测，不仅提高了匹配效率，也极大地提高了检测速度。但仔细分析算法，SNM依然存在如下几个方面的不足： 排序关键字的选定对排序结果影响太大。实践表明，排序关键字选取的好坏不仅直接检测效率，对相似性检测的精度也有很大影响，如果选取不当，还有可能漏配一些重复记录。 难以适当控制滑动窗口的大小w。w选择较小时可能漏配掉相似重复记录；w选择较大时，会导致比较次数增多，降低检测效率；对于一个确定的数据集，如果重复记录聚类数值差别较大，则根本无法选择出较为恰当的w。 滑动窗口内两条记录的比较时间长。在滑动窗口内，相比较的两条基本上采用笛卡尔成绩方式进行字段比较，这导致比较时间较长。 基本近邻排序算法的改进思想 针对SNM算法存在的不足，提出以下改进方法： 排序关键字预处理。针对SNM算法对排序关键字具有较强的依赖性，在根据此排序关键字对数据集进行排序之前，先用统一的标准格式对排序关键字中的繁杂表示形式实现规格化处理，形成统一格式的数据；再对排序关键字中的单词进行排序，以字段值中的标点符合或空格作为定界符，将字段单词化，再对这些字段中的单词排序。 采用大小可伸缩窗口。即不固定滑动窗口的大小，而是在一定范围内可根据已排序记录聚类规模的大小来进行自适应式的调整。算法的参数有4个：窗口最小值Wd1,窗口最大值Wd2,窗口中相似记录数Match_num和当前窗口大小Wdi。当前窗口的大小Wdi定义为： 其中，Match_num取值范围为[0,Wdi-1]。由该公式不难看出，当Match_num的取值变大时，也就意味着在该窗口内，聚集的相似重复记录变多了，Wdi的取值跟着变大，即增大滑动窗口，扩大相似重复记录的检索范围，减少相似重复记录遗漏的可能性；当Match_num增大到Wdi-1，即意味着整个滑动窗口的记录均为相似重复记录，此时的Wdi取得最大值Wd2。如果当前窗口中没有相似重复记录，则Match_num取值为0，那么Wdi取得最小值Wd1，即缩小滑动窗口，减小比较范围。通过这种处理，可以使滑动窗口的大小自动跟随滑动窗口内的相似重复记录的数目呈现正相关的变化，既能避免进行过多的无效检索，又能进一步减少相似重复记录因窗口固定大小而被遗漏的可能。 为属性设置权重。为了缩短滑动窗口内的两条记录的比对时间，根据数据表中属性对记录的区分度，为关键属性或其部分属性设置不同的权重Wi，区分度大是属性权重大，区分度小的属性权重小，非关键属性权重为0，所有属性的权重之和为1。为了提高两条记录的比对速度，每条记录中的属性值都根据属性权重由大到小的顺序重新排列，在比对时，只比对权重不为0的属性。假设数据集中设定权值的属性个数为n,判断窗口内记录的属性，给定一个集合Ai{0，1}，如果相比较的两个属性值取值相等，则Ai等于1，否则Ai等于0。在判断记录是否为相似重复记录时，设定一个相似度阈值U,如果 ,即说明两条记录的关键属性完全相似或接近完全相似，即两条记录为相似重复记录。如果这个条件不成立，则足以说明被比较的两条记录是非相似重复记录，则记录中还未来得及比较的剩余属性即刻停止比较，从而大大提高滑动窗口内两条记录的比对效率。
验证结果及衡量标准 衡量相似重复记录检测算法的性能指标通常用召回率和误识别率两个指标来加以描述。 召回率(Recall--R)，也叫查全率，即表示算法检测出来的正确的相似重复记录在数据集中实际存在的相似重复记录的比例[4]。设T表示数据集中的相似重复记录的实际条数，C表示检测算法实际检测出来的相似重复记录条数，则有R=C/T。显然，R的值域为[0,1],求得的R值越大，表明检测算法的查全性能越好。 误识别率(False Percent--FP)也叫失误率，即指相似重复记录检测算法错误地识别为重复记录的数目占被算法识别为重复记录的总数比[5]。设F为算法错误地识别为重复记录的数目，A为被算法识别为重复记录的总数目，则有FP=F/A。显然，误识别率越低，表明算法判别的准确性越高。 显然，通过召回率和误识别率可以简单地比较出相似重复记录检测算法性能的好坏。 实验数据来自于当地一家销售公司的部分客户信息数据集，该部分数据集共有1218条记录，数据表含有姓名、性别、身份证号码、通讯地址、联系电话、单位名称、单位地址、办公电话共8个属性。在实验中设定相似度阈值U=0.85，表2记录了4种不同情况下的检测结果。 表2 改进前后SNM算法性能比较 排序关键字 SNM算法固定窗口 SNM算法伸缩窗口 Wd=8 Wd=12 Wd1=5 Wd2=10 未经预处理 R=87.73% FP=24.2% R=89.08% FP=22.52% R=95.62% FP=20.71% 经过预处理 R=92.41% FP=19.02% R=94.83% FP=15.20% R=97.69% FP=12.15%
实验表明，针对传统SNM算法所存在的不足，在根据排序关键字对数据集中的记录进行排序之前，对排序关键字进行统一数据格式处理、对排序关键字中的单词进行排序、根据属性对记录的区分度不同为部分属性设置权重值，在进行相似重复记录检测时采用可伸缩窗口等措施，能够显著改善SNM算法的性能。 本文在深入分析基本近邻排序算法思想的基础上，指出该算法所存在的明显不足，并针对这些不足，给出了一些改进措施。通过排序关键字的预处理，提高记录聚类的速度；采用伸缩窗口思维可以使滑动窗口的大小，自动跟随滑动窗口内的相似重复记录的数目呈现正相关的变化，既能避免进行过多的无效检索，又能进一步减少相似重复记录因窗口固定大小而被遗漏的可能。为关键属性或其部分属性设置权重值，避免了笛卡尔乘积式的属性比较，只需对关键属性进行比较，省略了非关键属性的比较，明显加快了窗口内两条记录的比较速度。通过这些改进措施，较好地改善了原有SNM算法的性能，且在实际应用中也取得较好效果。但本改进算法也还存在一些不足之处，突出体现在以下两个方面：窗口内两条记录的比对没能找到更加高效的算法，导致整个检测算法的时间性能还有待提高。伸缩窗口的引入，确实提升了SNM算法的性能，但依然存在极少数相似重复记录漏配的现象。 除此之外，还有实验系统的数据集规模偏小，可能掩盖了改进算法的某些缺点等。所有这些，都应引起以后工作的高度重视，同时也是今后努力的方向。 （作者单位：安徽职业技术学院）
|
