《武汉工程大学学报》
2017年04期
403-408
出版日期：
2017-10-14
ISSN:
1674-2869
CN:
42-1779/TQ
基于模糊综合评判和长度过滤的SNM改进算法
当前，全球各行各业均组建了可以管理和推广自身业务的管理信息系统，如何有效管理和利用各类数据资源，是科学研究和决策支持的前提. 随着信息化水平的不断提高，全球的各类数据库中存储的数据都呈现井喷式的增长. 诸如银行、证券公司、通信公司等数据库的存储量均在百万以上，且可以预见随业务扩张的趋势将继续推动数据增长；而政府的人口基础数据库的数据量更是以亿计. 在这些数据量庞大的数据库中存在着诸多重复数据，如何清理相似重复数据便成了亟需解决的问题. 目前常用的相似重复记录清洗算法是基本邻近排序算法（basic sorted-neighborhood method， SNM）［1-3］. 该算法基于排序和合并的思路，通过关键字对数据记录进行排序，再在一定的窗口内比较临近的数据记录是否构成相似重复记录，如果构成重复记录则合并. 由于算法简单且易于实现，所以得到了大量的应用［4］. 相似重复记录的识别通常由两个步骤实现，第一步是逐一对记录属性进行匹配，第二步综合考虑所有属性的相似度并计算两条记录的相似度，最后通过事先设定的阈值判定两条记录是否构成相似重复记录. 而在综合考虑所有属性的相似度并计算两条记录的相似度前必须为记录的所有属性设置权值，逐一利用属性权值乘以属性匹配度，方可客观地判断两条记录是否相似重复，所以属性权值的设置便成了判重的关键. 殷秀叶［5］提出了属性加权和同义属性的概念对相似重复记录进行判定. 文献［6］通过计算记录字段间的相似度，组成特征向量；然后采用改进的量子粒子群优化算法优化反向传播（back propagation，BP）神经网络进行学习，建立最优相似重复记录检测模型. 李鑫等提出了一种分组模糊聚类的特征优选方法，首先进行分组记录的属性处理，然后采用一种相似度比较计算方法进行组内相似重复记录的检测［7］. 周典瑞等采用综合加权法和基于字符串长度过滤法对数据集进行相似重复检测［8］. 然而这些方法的属性权值均是人为主观设置，未能体现不同属性的重要性程度. 针对属性权值确定主观性过强的问题，肖满生等提出基于数据分组和模糊综合评判的相似重复记录识别方法，该方法能较客观反映属性的重要性程度，取得较高的识别精度［9-10］. 文献［11］提出一种基于长度过滤的SNM改进算法，首先在窗口内根据两条记录的长度比例将构成相似重复记录可能性极小的数据排除在外，减少了记录比较的次数，提高了检测效率，为了降低因属性缺失等因素对判重的影响，进一步提出添加属性有效性因子并通过设定可变权值的方法取得了一定的效果. 刘雅思等提出动态容错法，解决了因属性缺失而误判的问题，提高了准确率［12］. 然而文献［11-12］中的权值仍然凭借单用户主观设定. 笔者结合文献［10-12］的思想提出了基于模糊综合评判和长度过滤的相似重复记录检测方法，主要思路为：采用模糊综合评判方法确定属性权值，提高判重精度；在检测相似重复记录前，采用长度过滤并充分考虑属性缺失的影响，排除不可能构成相似重复的记录，减少记录的比较次数，从而提高检测效率；基于SNM算法思想对数据记录集进行检测. 1 相关算法描述 1.1 模糊综合评判法 模糊综合评判法是基于模糊数学的评价法，也就是用模糊数学对现实世界中多种相互制约和关联的事物做出定量的评价［13］. 该方法可以将定性评价转为定量评价，可以较好解决非确定性的难以量化的评价问题［14］. 在相似重复记录的属性权重计算中，可以通过多个用户分别对属性进行等级评价，然后取这些评价的平均值，通过模糊综合评判可以更客观的反映属性的重要性程度. 1.2 SNM算法 该算法由Hernandez M等人提出，其主要思路是先利用关键字或关键字的组合对所有数据进行排序，然后设定一个固定长度的窗口，在窗口内进行相似重复记录检测，随后滑动窗口，重复查重的过程［1-3，15］. SNM算法的主要过程如下： 1）排序. 根据属性的重要性程度，选择重要性程度高的一个关键字或若干个关键字的组合作为排序关键字，对数据记录集进行排序. 经排序后，潜在的相似重复记录将被调整到相邻或邻近的一个范围内. 2）归并. 设置固定长度的窗口，将第一条记录依次和窗口内的其他记录匹配，如果构成相似重复记录则合并处理. 当前窗口处理完毕，将窗口内第一条记录移除，然后将当前窗口内最后一条记录的下一条相邻记录移入窗口，循环执行匹配的过程. 由于该方法限定记录的匹配在窗口内进行，所以极大提高了判重效率. 1.3 长度过滤算法 针对大数据集，相似重复记录所占比例较小，如果在相似重复记录识别前首先将不可能构成相似重复的记录排除在外，显然可以提高检测效率. 长度过滤算法是根据两个字符串的长度比例找出每条记录的可能相似重复数据集范围的方法［11］. 然而，实际数据库中的记录常出现属性缺失或属性采用简写方式输入等情况，如在有些数据库中地址属性不是必填项，可能出现缺失也可能采用简写输入，而地址字符串长度在记录总字符串长度中的占比较高，此时再单纯进行记录长度过滤显然存在偏差. 针对上述问题，结合模糊综合评判计算出的属性权重，本文提出改进的长度过滤方法. 设C表示待检测的数据记录集，n表示数据量，Ri表示第i条记录，Rj表示第j条记录，则C=｛R1，R2，……，Rn｝. 设记录有m个属性，经模糊综合评判后计算出来的第k个属性权值为[Wk]（0≤k≤m）. 设Len（Rik）表示第i条记录的第k个属性值长度，u表示预先设置的长度比例阈值，则当两条记录的长度比例低于u时认为这两条记录不构成相似重复记录，即当[k=1mWk?Len(Rik)/Len(Rjk)]=u） //满足条件则进行判重，否则过滤掉 ｛ 根据属性权重向量进行判重处理； Output（Ri，Rj）； ｝ ｝ ｝ 4 实验部分 4.1 实验环境 实验硬件配置：intel（R）Core（TM）i3-3110M
[email protected]
GHz，内存4.0 GB，硬盘空间500 GB. 软件环境：操作系统WIN7，数据库软件SQL Serve2005，算法在VC++6.0中编译运行. 4.2 评价方案 衡量清洗算法优劣标准的通常做法是计算查重的查全率和查准率，设C表示数据集中实际的重复记录，T表示检测出来的重复记录，F表示检测出来的错误的重复记录，则查全率R和查准率P的定义如下： [R=T-FC]. （1） [P=T-FT] . （2） 除了查全率和查准率外，运行速度也是算法优劣评判的指标之一. 本文算法主要在文献［11］的基础上改进，故其性能通过在相同的数据集上分别对比文献［11］算法的查全率、查准率及运行时间来分析. 4.3 实验过程 实验数据来自某地人口基础数据库，共包含76.3万条记录和31个属性. 实验中分别随机提取2万条、4万条及6万条数据量，基于人工和软件结合方法将数据集依次处理成包含407条、823条及1 478条的相似重复记录集，实验后检测出来的重复记录数及正确的相似重复记录数由人工方式统计. 在实验中共组织100个用户对记录属性进行等级评判，相似度阈值设为0.9，长度阈值设为0.8. 在同样的数据集合上，分别利用文献［11］算法和本文算法进行判重，通过分别计算两种算法的查全率、查准率及运行时间并进行对比. 4.4 实验结果分析 在相同的数据集上分别对文献［11］算法及本文算法进行实验，为了描述方便，将文献［11］算法称为原算法，而将本文算法称为改进算法. 根据以上所述方法，分别统计两种算法的查全率、查准率及运行时间，并整合绘制成图来表示，其结果如图1~图3所示. 从图1和图2中可以看出，改进算法不管是查准率还是查全率均比原算法有所提高. 文献［11］首先根据单用户的主观意识设置属性权值，然后基于SNM算法在窗口内对数据记录进行长度过滤. 而改进算法基于多用户对记录集的属性进行模糊综合评判，进而计算出属性权值，此方法必然能更客观地反映出记录属性的重要程度. 此外，改进算法在长度过滤时再次利用到模糊综合评判法计算出来的属性权值，首先依次计算出两条记录每个属性的长度，然后分别利用两条记录各自的属性长度依次乘以前面计算出来的对应的属性权值，再把计算出来的两个结果进行相除得出一个值，根据其值和事先设定的记录相似度阈值进行比较，如果超过阈值则表示两条记录重复，否则两条记录不构成相似重复.改进算法在长度过滤时充分考虑到属性值缺失的情况，如果记录的某个属性值缺失则该属性长度为0，这更能客观反应两条记录的相似重复情况.综上，改进算法的查全率及查准率必然有所提高. 从图3中可以看出，对于同样的数据量，改进算法在运行时间上均比原算法有所减少. 判重算法中均涉及到排序的操作，而排序操作所耗费的时间一致，两种算法均采用了长度过滤的方法，花费的时间也一致. 但是原算法采用添加属性有效性因子并在算法运行过程中根据实际情况调整属性权值，这必然耗费了时间，所以运行时间更长. 从图3中可知，随着数据量增大，两种算法的时间差越大，这说明改进算法的时间效率更高. 5 结 语 当前，数据呈现井喷式增长，各类数据库中所包含的相似重复记录不断增多，清洗相似重复记录也变得日趋重要. 基于相关文献，本文提出基于模糊综合评判计算属性权值，更客观地反映出属性重要性程度. 在此基础上，充分考虑属性缺失等情况，利用模糊综合评判的属性权值计算记录长度，将不可能构成相似重复的记录过滤掉，进一步减少判重过程中的匹配次数. 实验证明，改进算法一定程度提高了判重的精度和时间效率. 然而，在相似重复记录清洗过程中相似度阈值及长度阈值的设置问题仍是一个值得探讨的问题，两者设置过大或过小都将对查重精度产生影响，这将是今后应继续研究的问题.