论文网
属性方面有关论文例文,与海量数据的相似重复记录检测算法相关本科毕业论文范文
本论文是一篇属性方面有关本科毕业论文范文,关于海量数据的相似重复记录检测算法相关开题报告范文。免费优秀的关于属性及数理统计及计算机工程方面论文范文资料,适合属性论文写作的大学硕士及本科毕业论文开题报告范文和学术职称论文参考文献下载。
摘 要：针对海量数据下相似重复记录检测算法的低查准率和低效率问题,采用综合加权法和基于字符串长度过滤法对数据集进行相似重复检测.综合加权法通过结合用户经验和数理统计法计算各属性的权重.基于字符串长度过滤法在相似检测过程中利用字符串间的长度差异提前结束编辑距离算法的计算,减少待匹配的记录数.实验结果表明,通过综合加权法计算的权重向量更加全面、准确反映出各属性的重要性,基于字符串的长度过滤法减少了记录间的比对时间,能够有效地解决海量数据的相似重复记录检测问题.
关 键 词：海量数据；相似重复记录；综合加权法；编辑距离
中图分类号：TP311
文献标志码：A
0引言
高质量的数据是保证企业发展的重要前提,因此为了满足业务的需求,需要整合不同的数据源,由于整合的过程会产生一些语法上相同或相似并且代表同一现实实体的相似重复记录,这样会直接影响数据的质量,因此相似重复记录的清除成为提高数据质量的重要步骤.
记录间的相似性检测实质上是表征记录的各属性的相似性检测,由于各个属性对于记录之间的差异性贡献不同,应根据属性的重要程度为各个属性赋予相应的权重,以提高检测的精度.海量数据下的数据检测需要使用大量的时间和资源.
本篇论文出处:http://www.sxsky.net/benkelunwen/060180341.html
为了检测相似重复记录,目前采用的方法主要有：基本的字段匹配算法[1]、递归的字段匹配算法[2]、基于“排序&合并”方法[3]、采用距离函数模型的方法[4]、基于qgram算法[5]、基于聚类的算法[6]和基于人工智能的算法[7]等.传统的方法在进行相似重复记录检测时,需进行大量的磁盘I/O操作,这将导致时间和空间复杂度很高,基于聚类的算法计算量较大,准确率较低；而基于人工智能的算法推理过程复杂.李星毅等[8]为了提高查全率和检测的精度,采取多趟检测的技术和主观的等级赋权法,增加了大量的检测时间.传统方法多采用滑动窗口保存重复记录集,窗口的大小指定不合理,导致有些相似重复记录无法正确检测,降低了查全率.
为了克服以上缺陷,本文对传统的检测方法进行改进,首先采用既考虑主观方面的用户经验又结合客观方面的数理统计方法的综合加权法计算各属性的权重,然后把各属性值作为关键字,利用多线程对数据集并行排序,最后在各线程中采用文献[9]中的优先队列技术依次检测各记录,检测过程中采用基于字符串长度过滤法（加速法）减少不必要记录对之间的比对时间,最终合并检测结果集.
2算法设计
2.1综合加权方法研究与设计
记录之间的相似性检测,实质上是属性的相似性检测.由于各个属性对于记录之间的差异性贡献不同,因此应该根据属性的重要程度,为各个属性赋予相应的权重,提高检测的精度.组合赋权的基本思想为：结合主观的用户经验和客观的数理统计方法,全面考虑属性的重要程度,生成合理的权重向量.
主观方面：李星毅等[8]采用等级法确定等级向量,即首先各用户根据相关经验为各个属性指定一定等级；然后根据均值法计算属性的最终统一等级,生成如表1所示的属性等级表；最后,根据统一等级生成等级向量.
2.2多线程并发应用
海量数据的检测,必须考虑检测时间,如果顺序地对记录集的每一个属性进行排序和相似重复记录检测,势必会浪费大量的时间.本文考虑到共享加载到内存的数据集,采用多线程并发执行相似重复记录检测算法.这样,不仅充分利用计算机资源,同时又能大幅度提高算法的执行效率和相似重复记录的查全率.当所有的数据加载到内存后,如果按照多轮次检测算法,即第一次按照权重最高的属性排序,然后进行检测；如果效果不好,再按照权重次之的属性排序,接着再进行检测；反复进行操作,势必浪费时间.采用多线程的相似检测算法就是按照属性个数开启有限个线程,每个线程中按照属性进行排序,然后执行相同的检测算法,这样既可以减少多轮次检测的时间,又可以保证较高的查全率.
2.4优先队列
传统的记录相似检测采用固定窗口大小的滑动窗口顺序扫描记录集,比较当前记录与滑动窗口中的记录之间的相似性,这样大大减少了记录的比对次数,提高了比对的时间效率.但是由于窗口的大小固定,势必引起漏查或者重复比对的问题.同时,窗口的记录只是单一的一条记录,不能代表某类重复记录的所有特征,同样也会导致漏查现象的存在.针对以上缺陷,采用使用重复记录聚类思想的优先队列代替固定窗口大小的滑动窗口.
使用优先队列对排序后的记录集进行相似记录检测的思想：假如当前记录为Ri,优先队列的第一个聚类项代表为Rj,通过计算两者的相似性判断当前记录是否属于该聚类项,如果不相似,则直接与优先队列中的下一聚类项代表记录Rj+1进行比较,直到优先队列的最后一个聚类项代表；如果一直都不相似,则把记录Ri作为一个新的聚类项代表添加到优先队列的头部；如果此时队列中的记录总数超过优先队列上限,则根据“最久未使用”原则,删除优先队列中末尾聚类项.
如果Ri与Rj相似,说明该记录具有代表性,应该把该记录添加到当前以Rj为代表的聚类项中,并且将Ri作为新聚类项的聚类代表记录,同时把Ri添加到重复记录集中,然后对Ri之后的记录Ri+1继续进行相似检测.每次记录进行比对时,对比较过的聚类项元素进行标记,如果长时间某些聚类项没有被比较过,说明此聚类项在以后被比较的概率也比较小.因此有必要从优先队列中删除此类聚类项,减少优先队列中的记录,从而减少下一次的比对次数,实现了优先队列的自适应性元素删除功能.
通过使用优先队列对记录集进行相似重复检测,大大减少记录的比对次数；同时采用聚类思想,避免了因为单条记录不能代表多条重复记录而漏查的现象.该方式不受数据规模的限制,特别适合海量数据的相似检测.2.5算法流程
首先计算属性的权重,确定每一属性对于记录相似性检测的重要性；然后,多线程并发检测记录集,每个线程针对一个属性对记录集进行排序；最后在每个线程中检测相似重复记录并且合并所有的检测结果.属性相似检测的核心是字符相似度计算,字符相似度的计算通常采用编辑距离算法,由于编辑距离必然大于两字符的长度之差,为了提高检测效率,采用基于字符串长度的过滤策略,即因两字符长度相差较大而相似性较小,省略计算其编辑距离的策略.为了提高检测精度,利用综合加权法计算各属性的权值；并通过多线程并发执行检测算法,有效地提高查全率.
算法描述如下：
步骤1
用户根据属性实际重要程度给各属性指定等级,根据均值法计算各属性的最终统一等级；在各个属性中随机选取一定数目的记录计算其属性取值的种类数,生成属性取值种类数向量,最终把属性等级向量和属性取值种类数向量进行统一化处理,生成属性的权重向量.
步骤2
根据属性的个数创建多个线程.
步骤3
在每个线程中,按照属性值进行排序.采用优先队列顺序扫描记录集,计算当前记录与队列中记录的相似度；然后根据相似阈值判断记录是否相似,并添加到重复记录集中.
步骤4
合并各个线程中的
属性方面有关论文例文,与海量数据的相似重复记录检测算法相关本科毕业论文范文参考文献资料：