基于滑动窗口的数据相似检测方法.pdf

(19)中华人民共和国国家知识产权局*CN103336771A*(12)发明专利申请(10)申请公布号(10)申请公布号CNCN103336771103336771A(43)申请公布日2013.10.02(21)申请号201310114244.8(22)申请日2013.04.02(71)申请人江苏大学地址212013江苏省镇江市京口区学府路301号(72)发明人周莲英周典瑞(74)专利代理机构江苏致邦律师事务所32230代理人樊文红(51)Int.Cl.G06F17/30(2006.01)权权利要求书2页利要求书2页说明书5页说明书5页附图2页附图2页(54)发明名称基于滑动窗口的数据相似检测方法(57)摘要本发明公开了一种基于滑动窗口的数据相似检测方法，包括：S1、采用等级法计算属性的经验向量G；S2、采用数理统计法计算属性的统计向量C；S3、综合经验向量G和统计向量C，计算出最终的权重向量W；S4、计算可变窗口大小的队列的窗口上界；S5、根据属性的个数创建多个线程；S6、在每个线程中，顺序扫描记录集，计算当前记录与可变队列中记录的相似度；S7、合并各线程检测出的重复记录集。本发明采用基于多线程并发的检测算法代替多轮检测，提高了检测效率，节省了检测时间。CN103336771ACN10367ACN103336771A权利要求书1/2页1.一种基于滑动窗口的数据相似检测方法，其特征在于，所述方法包括：S1、采用等级法计算属性的经验向量G；S2、采用数理统计法计算属性的统计向量C；S3、综合经验向量G和统计向量C，计算出最终的权重向量W；S4、计算可变窗口大小的队列的窗口上界；S5、根据属性的个数创建多个线程；S6、在每个线程中，顺序扫描记录集，计算当前记录与可变队列中记录的相似度；S7、合并各线程检测出的重复记录集。2.根据权利要求1所述的方法，其特征在于，所述步骤S1具体为：根据用户经验，采用等级法为每一个属性赋予相应的等级，然后通过均值法计算出代表记录属性特征的等级向量G。3.根据权利要求1所述的方法，其特征在于，所述步骤S2具体为：多次随即抽取指定数目的记录，计算每一属性取值的变化种数，作为客观描述属性对记录的重要性，使用均值法计算出每个属性的取值种类数，生成属性统计向量C。4.根据权利要求1所述的方法，其特征在于，所述经验向量G的计算公式为：其中，Gi表示第i个属性的最终统一等级，m表示用户的个数，s表示第s个操作用户。5.根据权利要求4所述的方法，其特征在于，所述统计向量C的计算公式为：其中，Cij表示第i次第j个属性的取值种类数目，Cj表示第j个属性的最终种类数，m表示选取的次数。6.根据权利要求4所述的方法，其特征在于，所述权重向量W的计算公式为：其中，Wi表示第i个属性的权重向量，Gi表示第i个属性的最终统一等级，Ci表示第i个属性的最终种类数。7.根据权利要求1所述的方法，其特征在于，所述步骤S6中“在每个线程中，顺序扫描记录集”之前还包括：在每个线程中根据属性值对数据集进行排序。8.根据权利要求1所述的方法，其特征在于，所述步骤S6中“计算当前记录与可变队列中记录的相似度”具体为：当前记录与可变队列中的第一个记录进行相似检测；若当前记录与可变队列中的第一个记录相似，把当前记录添加到相思重复记录集中，然后，把当前记录添加到可变队列的第一个记录中，查看可变队列是否已满，如果可变队列已满，先剔除可变队列中最后一条记录，然后再把当前记录添加到可变队列；如果优先队列2CN103336771A权利要求书2/2页不满，则直接添加记录到可变队列中；若当前记录与可变队列中的第一个记录不相似，继续与可变队列的其他记录进行比对。3CN103336771A说明书1/5页基于滑动窗口的数据相似检测方法技术领域[0001]本发明涉及数据清洗技术领域，尤其涉及一种海量数据下基于滑动窗口的数据相似检测方法。背景技术[0002]数据相似检测就是检测数据库中的相似重复记录，以剔除冗余数据。相似重复记录为同一个现实实体在数据集合中不同的表现形式，由于它们在格式、拼写等方面的差异，导致数据库管理系统不能正确识别，进而影响对数据的正确处理。相似重复记录检测的衡量指标包括查全率、查准率及时间效率等，三者之间往往是相互制约的。海量数据下的数据检测在查全率和时间效率上尤为突出。需从多方面对检测算法进行优化算法，以提高检测效果和检测效率。[0003]目前已有的检测算法主要包括字段匹配算法、编辑距离算法、聚类算法以及基于滑动窗口的检测算法。其中尤以基于滑动窗口的算法较为有效。该算法在对记录集进行排序，依据相似记录邻近原理，将检测记录的比较记录数限制在有限的窗口数目内，从而可大大提高检测效率。经典的基于滑动窗口的相似检测的优点是算法简单，有限的比较量。但也存在