原创《一种基于属性权值分组聚类的相似重复记录检测方法》：本文是一篇关于权值论文范文，可作为相关选题参考,和写作参考文献。
摘 要： 为了提高数据集中相似重复记录的检测效率,提出一种基于属性权值的分组聚类算法.该方法在记录集中选取特征属性,通过设定的权值对记录进行聚类,在形成的数据子集中进行字段匹配和记录匹配,来识别相似重复记录,并给出了相关算法.实验表明,该方法能减少字段的匹配次数和记录的匹配范围,节省运行时间,具有较高的查全率和查准率.
关键词： 相似重复记录； 聚类； 特征属性； 字段匹配； 记录匹配
中图分类号： TP 391 文献标志码： A 文章编号： 1671-2153（2015）02-0072-04
0 引 言
消除通过Web上的信息抽取获得的重复记录是目前数据清洗领域研究最多的内容,其关键问题就是判断两个记录是否近似重复.从查全率和查准率的角度来说,检测重复记录最可靠的方法就是逐个比较数据集中的每条记录.目前识别重复记录的经典算法主要是基于排序比较的思想,主要有基本邻近排序算法（Basic Sorted?Neighborhood Method,SNM）[1]、多趟邻近排序算法（Multi?Pass Sorted?Neighborhood,MPN）[2],以及优先队列清洗策略[3].
检测重复记录的核心则是字段的匹配问题,主要算法有：递归字段匹配算法[4]、Smith Waterman（S?W）算法[4]、N?Grams算法[5]以及基于编辑距离的字段匹配算法等.
利用这些传统的算法在海量数据中查找相似重复记录,时间复杂度和空间复杂度均很大,并且某些字段中字符所在位置的敏感性将导致相似的记录未必能相邻排列,往往会降低检测的效果.本文提出一种基于属性权值的记录分组聚类算法来检测相似重复记录,主要包括字段匹配和记录匹配两个方面.
1 算法基本思想
Web上抽取的数据集中记录的各个属性均用来表示该实体的特征,但在描述某个实体时,各个属性的重要程度不同,首先选取特征属性,删除无关属性,并为特征属性划分不同的级别,赋予不同的权重值,根据分层分级的思想,按照属性权重值的大小,对数据集进行初始聚类,使相似记录尽可能排在相邻区域,将大数据集分割成不相交的小数据集；然后对小数据集通过计算字段相似度进行字段匹配；最后进行记录匹配,利用字段加权匹配的方法来检测相似重复记录.
2 属性权重设定
2.1 特征属性
在进行记录匹配时,首先应该选取最能描述记录特征的属性,去除无关属性,从而减少字段匹配的次数和记录匹配的运行时间,提高算法的运行效率,同时有效降低大数量数据相似重复记录检测的复杂性.一般作为特征属性,不能存在值缺失、不唯一、重复太多的情况.例如：开本等,因为很多不同的书籍均采用相同的开本,如16开等,但它们不是重复记录.
2.2 权重值设定
若记录间具有的相同属性越多,且这些相同属性的权值越大,则越相似.假设将关系表中各条记录的特征属性选取出来,形成特征向量C等于（C1,C2,等,Cn）,Ck表示关系表中第k个字段,其中,1≤k≤n；对于任意记录Ri等于{Ri1,Ri2,等,Rin},其中Rik表示记录Ri中第k个字段的值；同时需要设置一个值,用来表示Rik这个字段在这条记录中的重要程度,值越大,说明越重要,将这个值称为属性的权重,则权重向量为
Weight等于{Weight1,Weight2,等,Weightm}.
2.3 初始聚类
初始聚类的目的,就是根据分组的思想,将可能存在的相似重复的记录排在相邻区域,这样可以限制记录匹配范围,既可以减少检测时间,又可以获得较好的查全率和查准率.
聚类的方法：权重值越大的属性越重要,因为它最能体现实体的特征,通常先按权重值最大的属性对记录分组,从而得到若干数据子集,对于子集较大的,可按第二大权重值对应的属性进行二次分组,以此类推,最终得到的分组要求大小适宜.
3 字段匹配
字段匹配是记录匹配的基础,主要用来判断各记录中对应字段的相似度,若对应字段的值在语义上相等,或可以表示同一实体,即为等价.
字段的类型分为数值型和字符型,数值型字段的匹配一般为精确匹配,判断值是否相等即可.而字符型字段的匹配则较为复杂,也是研究的重点.因为Web上抽取到的数据集中字段几乎都为字符型数据,也是最易产生重复数据的根源.
5 实验结果与分析
对于相似重复记录的检测,将基于属性权值的记录分组聚类算法（简称权值分组算法）,与文献[3]提出的优先队列算法进行对比,分别获取抽取数据5000,10000,15000,通过软件和手动方式分别处理成有45,110,165对相似重复记录,用权值分组和优先队列两种方法检测重复记录,从查准率、查全率和运行时间三个方面进行比较,结果如图1～图3所示.
由图1与图2可以看出,优先队列算法的查准率与查全率均低于权值分组,随着数据量的增多,权值分组算法仍然可以保持较高的查全率和查准率,而优先队列算法的查全率和查准率均出现了下降.这主要是因为优先队列算法在排序时由于字符位置的敏感性,导致了相似记录在排序后,不能完全处在相邻区域,而权值分组是给不同字段赋予不同权值,并能进行多趟分组查找,可以提高精度.
由图3可以看出,两种方法在3个不同数据量上进行测试,权值分组算法运行时间分别为8,11,13 s；而优先队列算法运行时间为9,15,26 s,显然比权值分组算法慢得多.这主要是由于权值分组是对记录进行特征属性优选,再根据分组思想将大的数据集分割成小的不相交的数据集,从而减少了字段的匹配次数,与记录匹配的范围,自然节省了运行时间.
6 结束语
相似重复记录的检测是数据清洗工作的核心问题.本文提出了一种基于属性权值的记录分组聚类算法来检测相似重复记录.该方法从记录集中选取特征属性,删除无关属性,按照设定的权值对数据集进行聚类,使相似记录尽可能排在相邻区域,从而可以减少字段的匹配次数和记录的匹配范围,节省运行时间,可以解决大规模数据量中的相似重复记录检测问题,并从查准率、查全率和运行时间三个方面验证了该方法的合理性和有效性.
权值论文参考资料：
结论：一种基于属性权值分组聚类的相似重复记录检测方法为大学硕士与本科权值毕业论文开题报告范文和相关优秀学术职称论文参考文献资料下载，关于免费教你怎么写权值方面论文范文。
