论文一种相似重复记录检测算法的改进和应用是关于算法方面的论文题目、论文提纲、算法论文开题报告、文献综述、参考文献的相关大学硕士和本科毕业论文。
摘 要：介绍数据清洗与相似重复记录检测算法的相关概念以及相似重复记录的清洗原理.对基本近邻排序算法SNM进行了深入分析和研究,指出其中的不足,在此基础上给出改进策略并加以应用.实践证明：该改进算法在关键性能上有明显改善.
关键词：大数据；数据清洗；相似重复记录
中图分类号：TP311
文献标志码：A
文章编号：2095-5383（2017）02-0017-04
Abstract： In the age of big data,the research of data cleaning algorithm is very important.This paper briefly introduces the concept of data cleaning and detection algorithm for similar duplicate records,then introduces the principle of cleaning the similar duplicate records.The SortedNeighborhood Method（SNM） is analyzed and studied and its shortcomings are pointed out,based on this improved strategy and application,the practice proves that the improved algorithm,the key performance is significantly improved.
Keyword： big data；data cleaning；similar duplicate record
信息化社会每天都产生大量的数据,这些海量数据通常包含一些重要信息,这些信息往往是信息决策支持系统的决策依据.但庞大的数据集中除了含有重要信息的数据之外,也夹杂着一些无用的、错误的、不一致的、不完整的、重复的数据,即“脏数据”.脏数据的存在不可避免,它不仅可能导致信息失真,还极有可能给依此而建立的决策支持系统以及应用商务智能带来隐患[1].因此,在数据进入实用系统前进行数据清洗（data cleaning）是非常重要的.数据清洗是将数据库中的脏数据通过一定的技术和手段转变成合乎系统要求的数据处理过程.本文在分析邻近排序算法（SortedNeighborhood Method,SNM）原理的基础上,针对SNM算法的不足,提出了排序关键字预处理和伸缩窗口等改进措施,以提高数据的聚类速度和比较速度.
1相似重复记录清洗
数据清洗通常是从数据是否完整准确、有无冗余以及时空有效性等方面来进行.从数据清洗的内容来看,主要包括错误数据、不完整数据以及相似重复记录3种清洗对象[2].由于相似重复记录几乎会出现在所有未经清洗的稍大规模的数据集中,因此,针对相似重复记录的清洗尤为重要.
一个客观实体在同一个数据库中以多条完全相同或高度相似的记录形式存在,则這些记录之间彼此互称为相似重复记录.简单地说,在同一个数据库系统中,如果出现两条或两条以上的记录,它们之间出现足够多的相同或相似的属性值,即可认定其为相似重复记录,如表1所示.
最简单的相似重复记录检测方法是用一条记录与数据集中的每条记录进行匹配比较.若数据库中的记录总数为n,则需要进行n（n-1）/2次比较,其时间复杂度为O（n2）,对于海量数据来说,显然是不可取的方法.
为提高检测效率,目前通常使用“排序-合并法”,它先以数据表的某个特征属性或组合属性对数据表进行排序处理,尽可能地使相似重复记录聚集在一起,再将记录与一个较小范围内的记录逐一比较,如发现相似重复记录,则根据预定义的相关规则,对它们进行合并.其清洗过程如图1所示.
由图1可知,排序-合并法一般包括3个阶段：
1）作为数据预处理的方式之一,数据排序依据排序关键字对数据库中的记录进行排序处理.这一环节的主要目的是把可能的相似重复记录尽可能地排在一起.排序的结果显然依赖于排序关键字,采用不同的排序关键字,可能得到差异很大的排序结果.因此,如何选择和处理排序关键字,在数据排序这一环节中尤为重要.
2）第2阶段是对相似重复记录的检测.由于进行相似重复记录检测是在一个经过排序处理后所得到的子集范围内实现,其算法的时间复杂度为O（nlogn）,检测效率明显提升.目前已有的相似重复记录检测方法大多依此思想为基础[3].
3）数据合并是对数据集进行增删补改的清洗阶段.经过检测被认定为相似重复记录的两条记录需要进行数据合并.如果两条相似重复记录是完全重复记录,只需删除两者之一即可；如果仅是相似重复记录,则需将两条记录合并为一条新记录,新记录中保留被合并的两条记录中的关键属性（排序关键字）和相同属性,对于差异化的属性则根据具体实用系统的要求而制定的合并规则进行合并.
2邻近排序算法
目前基于“排序-合并”思想的相似重复记录检测方法有很多,如邻近排序算法（SortedNeighborhood Method,SNM）、多趟近邻排序算法和优先权队列算法等.
多趟近邻排序算法一般能够得到较全的相似重复记录的集合,降低漏配的可能性,但该算法需多次独立地执行SNM算法,且每趟执行之前需重新创建不同的排序关键字,时间性能不佳.
优先权队列算法借用UnionFind数据结构,将记录根据相似性程度的不同,分别放在不同的优先权队列.这种算法能够减少记录的比较次数,但如采用单趟优先权队列算法,很有可能造成相似重复记录的漏配,实际应用中多采用多趟优先队列算法,但这又导致消耗较多的时间.
总结:这篇算法论文范文为免费优秀学术论文范文,可用于相关写作参考。
参考文献：
1、 一种无线传感器网络路由协议LEACH改进算法 摘 要：针对低功耗自适应集簇分层型协议LEACH（low energy adaptive clustering hierarchy）的节点生命周。
2、 基于聚类SIFT人脸检测算法 摘要：为解决在人脸识别领域的特征提取问题，提出一种尺度不变特征转换的SIFT算法与聚类分析相结合的算法，在对人脸特征分类时，通过选取最优化的距离。
3、 2种免疫检验方法检测乙型肝炎病毒感染血清学标志物临床 [摘要] 目的 分析并比较两种不同免疫方法检测乙型肝炎病毒感染血清学标志物的临床效果。 方法 方便选取在2016年3月—2017年5月期间在该院。
4、 孕妇4199例4种传染病感染指标检测结果分析 中图分类号：R714 251 文献标识码：B乙肝病毒（HBV）、丙肝病毒（HCV）、艾滋病病毒（HIV）、梅毒感染的孕妇可在妊娠及围产期通过垂。
5、 基于LEACH的轻量级HELLOflood攻击检测算法 摘要：针对无线传感网络低功耗分簇型路由算法LEACH易遭受HELLO flood等安全攻击的问题，提出一种轻量级的基于接收信号强度值的HELLO。
6、 一种适用于机组组合优化的改进整数编码粒子群算法 摘 要： 针对机组组合这一高维、非线性混合整数规划问题，提出一种结合修补策略的整数编码粒子群（ICPSO） 算法。用正负整数分别表示机组开停机的。