一种有效检测汉语相似重复记录的方法文学论文
摘要：从排序属性的选择、匹配方法、相似度计算、检测和处理相似重复记录以及实验结果几个方面，阐述了一种有效检测汉语相似重复记录的方法。
关键词：相似重复记录;匹配;排序属性
Web系统、数据挖掘系统、决策支持系统都离不开高质量的数据。由于系统所需数据常常来自不同数据源中的Web文件、各种格式文档文件和数据库文件，而集成这些文件中的数据极易产生包括相似重复记录在内的各种质量问题。重复记录是指描述同一个对象的记录，而相似记录是指不完全相同但相似度超过了给定阈值的记录。产生相似重复记录出现的原因很多，包括输入错误、缩写、计量单位不同、字符串分割错误、模式转换错误等。相似重复记录的存在不仅浪费系统的存储资源，而且还会造成系统得到有偏差的、甚至是错误的结果。因此，检测和消除相似重复记录是保证系统性能的一项重要工作。检测重复记录的方法很多：在记录层次，有机器学习方法、领域知识方法和基于距离的方法;在属性层次，则有基于字符相似度、基于标记相似度、基于语音相似度和基于数值相似度等方法[1]。在大型数据库中检测相似重复记录，排序—比较—处理是一个有效的方法[2]。
排序的目的是将相似或重复记录尽可能聚集在一起，以便缩小记录之间的比较范围，缩短检测时间，而用于排序的属性一般是关键属性或权重值大的属性[3-4]。比较是检测数据库中相似重复记录的过程，它需要逐个比较记录的各个属性，最后根据各个属性总的匹配程度判断两个记录是否是重复记录或相似记录。处理是对检查出的重复记录或相似记录进行处理，对重复记录一般删除，对相似记录则可以选择保留、合并或删除。在排序—比较—处理方法中，核心工作是字符串之间的匹配，无论是英文还是中文字符串，基于距离的匹配是常用方法[5-6]。
本文提出了一种新的排序—比较—处理方法，实验结果表明，该方法的查准率和运行时间均优于目前已有的方法。
1排序属性的选择
检测数据库中的相似重复记录时，如果不限制比较范围，每条记录从自己的下一条记录开始进行比较直到最后一条记录为止。如果数据库有N条记录，总共需要比较(N-1)!次。如果先排序再比较，则由于具有相同或相似属性值的记录聚集在相近位置，每个记录只需要比较临近的少量记录，这样可以大大降低每条记录的比较次数。设属性Ai值的种类分别有δi种，则用Ai排序后，记录比较的范围是N/δi+ε(ε<
2匹配方法
在排序属性的选择、记录排序和检测记录是否是相似重复记录过程中，都需要进行汉字匹配。汉字字符串匹配、比较时要考虑以下3种情况：一是省略，如“东华大学”和“上海东华大学”相比，省略了“上海”2个字;二是缩写，如“中科大”是“中国科技大学”的缩写;三是输入错误，输入同音、近音字或字形相似的字。
对于前两种情况，通过查找子串算法解决;对于第三种情况，则通过查找相似汉字表解决。相似汉字表选用GB 2312—80中的常用字，按读音对它们进行编码，每个汉字有唯一的区位码。而当满足下面条件之一时，两个汉字被认为是相似的：(1)区码相同，位码差值的绝对值小于8;
(2)区码不同，但属紧邻的区，且位码差值的绝对值小于8。
字符串S和T的匹配方法如下，Ω存放S和T中相同字符个数：步骤1：计算字符串长度|S|和|T|。
步骤2：如果|S|≥|T|，则指针i指向T的第1个字符，指针j指向S的第1个字符;否则相反。
步骤3：保存j的值到变量head作为下次比较开始位置。如果i和j所指字符相同，Ω加1，i和j的值加1，使其指向下一个待比较字符。如果i的值大于Min(|S|，|T)|，匹配束;如果不相同，则查询同音字表;如果在表中的相似度等于0，则j的值增1，否则λ加1，i和j的值加1，使其指向下一个待比较字符。
步骤4：如果j的值等于Max(|S|，|T|)，则将head中的值赋给j作为下次匹配起始位置，返回步骤3。
3相似度计算
对有n个属性的记录M和N，它们的相似度用公式(1)计算：Sim(M，N)=α1ma(tMi，N)i+α2ma(tMj，N)j+nk=1，k≠i，jΣ1-α1-α2n-2ma(tMk，Nk)(1)(α1>0，α2>0，α1+α2<1)式(1)中，ma(tMi，N)i是记录M和N属性Ai的匹配值，α1,α2分别是Ai，Aj匹配结果的权重，越重要的属性权重值越大。
属性值匹配用公式(2)计算：
ma(tMi，N)i=Min(|Mi|，|Ni)|k=1ΣΩk(|Mi|，|Ni)|/2(2)式(2)中，|Mi|和|Ni|分别表示记录M和N的.第i个属性的字符个数，ΣΩ表示相同字符数。
4检测和处理相似重复记录
检测相似重复记录的步骤如下：(1)数据库中记录数是N，则从中抽样εN的记录。N越大，ε就越小，反之越大，原则是抽样记录要能够比较真实地反映整体数据库记录的情况。
(2)统计记录中前5个属性值的种类数，选择种类数最多的属性作为第1次排序的属性。如果Ai是第1排序属性，则统计属性Ai+A(jAj是其他4个属性)值的种类数，选择种类数最多的属性Aj作为第2排序属性;当属性值的匹配值大于0.8时认为相等。
(3)先用Ai然后用Aj对数据库排序。
(4)初始化时i指向第1个记录。
(5)指针j指向下1个记录。
(6)计算第i个和第j个记录中属性的ma(t)，如果值小于0.80，则将j+1的值赋给i，转到步骤(5);如果大于0.80，则计算属性Aj的ma(t);如果均值大于0.90，则继续比较后续的属性，最后计算Sim()，其中Ai和Aj的权重分别是0.3和0.2。如果Sim小于0.90，则将j+1的值赋给i，转到步骤(5);如果Sim大于0.90，则认定它们是相似或重复记录;如果Sim在0.90和0.95之间，则它们之间认定为相似记录，将其复制到文件表中由人工判断;如果大于0.95，则它们是重复记录，转向(5)。
5实验结果
实验环境是Pentium Dual-Core CPU，3.20 GHz，2.00 GB联想电脑。实验数据来源于学校图书馆搜集的汉语文献，其中包含大约8%的相似或重复记录。同时，实验比较了文献[6]中的方法一和本文提出的方法二得到的查准率和运行时间，如图1和图2所示。从中可以看出，本文提出的方法是有所改进的。6结语在当今信息社会，信息的来源和种类越来越多，而将信息集成到一起不可避免地会产生相似重复记录。而如何消除相似重复记录，是人们必须面对的问题，因此也是一个值得研究的问题。
【一种有效检测汉语相似重复记录的方法文学论文】相关文章：