相似重复记录检测的特征优选策略探究

杨家娥

摘 要：信息时代的来临，对大数据的检测和识别提出更高的要求，如检测精度更高和检测代价低廉。而传统的重复记录检测方法其特征属性繁多，数据源组成更为繁琐，导致检测精度不足和检测代价高昂问题的出现。为此，本文探索分析了相似重复记录检测的特征优选方案，从分组模糊聚类的原理出发，对相似重复几率的组内计算方法进行剖析，探究其在大数据集中检测精度和识别认识方面的优势。

关键词：特征优选；相似重复记录；模糊聚类；相似度；策略

依据相关的研究文献，可以发现传统重复记录检测方法基于排序和组合的思想，对大数据进行识别和检测，如优先队列技术、两字符串距离指标计算技术、数据清洗识别技术、滑动窗口技术等。所有这些重复记录检测技术的原理基本一致，在实际应用中存在检测精度不足且实施检测的成本高昂。如优先队列技术在应用过程中筛选具有代表性的记录能力不足；滑动窗口技术是基于相似重复记录的传递性基础上导致检测精确度不足等等。面对传统相似重复记录检测方法的不足和漏洞，一种的新的基于分组模糊聚类的记录特征属性优选方法表现出其具有非常强的优势和弥补性。此种方法基于模糊聚类压缩记录的基础上，对组内具有代表性的记录进行筛选，利用组内相似度比较的算法对重复记录进行有效的检测和识别。这一理论具有完善的基础理论体系，利用先进的理论分析方法和精确的设计思路，在实践应用中表现出高检测精确度和低检测成本的优势。

1 特征优选的分组聚类的实现过程

1.1 记录分组与组内记录属性处理过程

就目前的相关研究而言，关键字属性排序分组方法已经成为几率分组和聚集的应用最为多的方法，这也是相似重复记录检测的初始步骤。关键字属性排序分组方法对记录的属性值进行分割，形成大小适中的原字串，然后对每一个原子串进行数字化编码，以正序和逆序编码排序为原则，利用关键属性对记录进行排序，然后将具有相同的正序和逆序排列合并为一组。以此减少记录分组过程中的误差或者错误的出现，如在关键属性输入错误的情况下，正序和逆序排列可能存在不一致性，导致记录分组不在同一组别内。

1.2 大数据集组内属性的处理

1.2.1 组内无关属性的处理方法

大数据集组内属性受特征属性的影响，特征属性越典型，分组越精确，越不典型，分组误差越大。因此，对组内每个记录进行处理时，应确保每一个维度上的特征属性值都呈现高斯分布，将记录的特征属性值聚集在均值附近，以此减少偏差。特征属性值越是聚集于均值附近，说明其越典型；反之则代表误差过大，对分组越不利，即属于分组无关的属性。其衡量标准可以用下式验证：

某一维属性值同其均值偏差的表示方式，即其属性方差：

其中 —— 代表第j维属性的均值，P代表记录的属性维数。

1.2.2 组间特征属性处理

所谓的典型特征的选择，也即是对存在于组内的且对分组无关的属性进行删除。这一选择过程也即是组间特征属性的处理过程。在记录检测过程中，对记录集中最优的特征属性进行选取，避免因存在大量的相关属性而影响记录分组的精确度，降低重复记录检测的可分性。为此，组间特征属性的处理可以利用算法进行处理。首先对特征属性的数目进行自动确定，利用组间特征属性之间的距离和相似矢量对其相似性进行处理。其次，借助聚类分析的方法，利用FCM对自动确定的特征属性进行压缩，其中FCM的算法如下：

其中FCM表示模糊C均值聚类算法，c=q。

对具有相似性的特征属性的维度进行压缩，有利于筛选出组内最具有代表性的记录，提高了相似重复记录的识别精度。

2 组内相似重复记录的检测

在组内具有代表性记录获取之后，检测重复记录成为最关键性的工作。基于分组模糊聚类的相似度计算方法，可以对实际的记录组内的每个属性值进行分割，每一个属性值的集合其元素则是由分割而得到的原子串。在进行原子串分割、集合、编码过程中，可充分利用中、西方文字进行混合使用，从而最大程度的降低因记录输入而出现的拼写或者所写错误，避免其对重复记录检测的影响。利用算法对不同记录的相似度进行检测，删除超过阈值的几率，最后检测出记录较为集中的记录。其应用到的算法如下：

其中 中 表示是原子串a与 原子串匹配的分值， 介于0到1之间。 的属性长度为 ，其数量为m。

通过分析，我们了解到基于分组模糊聚类的相似重复记录检测的特征优选方案，相比于传统的排列和合并检测方法具拥有检测精度高、实施检测成本低的特征。新的特征优选方案对组间和组内的特征属性进行分组压缩，降低其属性的维数，一方面利用FCM方法自动确定特征属性的数量，最后将具有代表性的记录与其他记录进行比较，从而大大提高检测的精度。

[参考文献]

[1]宏圆，孙未未，施伯乐.一种使用双阈值的数据仓库环境下重复记录消除算法[J].计算机工程与应用，2005.41（1）：168—171.

[2]李星毅，包从剑，施化吉.数据仓库中的相似重复记录检测方法[J].电子科技大学学报，2007，36（6）：1273-1277.