Web信息整合中的数据去重方法.doc

Web信息整合中的数据去重方法.doc1Web信息整合中的数据去重方法摘要:针对现有数据去重方法中存在的时间效率和检测精度低的问题,结合Web信息整合的特点,提出一种逐级聚类的数据去重方法(SCDE)。首先通过关键属性分割和Canopy聚类将数据划分成小记录集,然后精确检测相似重复记录,并提出基于动态权重的模糊实体匹配策略,采用动态权重赋值,降低属性缺失对记录相似度计算带来的影响,并对名称的特殊性进行处理,提高匹配准确率。实验结果显示:该方法在时间效率和检测精度上均优于传统算法,%。该方法已应用于林业黄页系统中,取得了较好的应用效果。关键词:Web信息整合;相似重复记录;动态权重;模糊实体匹配中图分类号::A0引言在对海量、异构、多源的Web信息进行整合过程中,存在大量相似重复记录[1-2]。由于“Garbagein,garbageout”,需要对这些记录进行清洗,即数据去重。数据去重过程中需要解决两个关键问题[3]:一是缩小搜索空间,二是相似记录的匹配。解决第一个问题的传统方法大都基于排序合并的基本思想,例如滑动窗口[4]和优先队列[5]等,但由于字符位置敏感性不能保证相似的记录排在邻近的位置,导致其不能取得很好的效2果。一些研究人员针对上述问题,提出将聚类技术用于重复记录检测。例如文献[6]改进了基于密度的聚类(DensityBasedSpatialClusteringofApplicationswithNoise,DBSCAN)算法,文献[7]将记录映射成Qgram空间中的点后采用层次聚类实现检测。聚类方法在准确率和召回率等衡量指标上均有一定提高,但在Web信息整合中,数据量十分庞大,时间效率仍是实际应用中的瓶颈问题。针对第二个问题,常用的相似记录匹配算法有基本字符串匹配算法、编辑距离算法、Qgram算法、SmithWaterman算法以及基于它们的一些改进算法。这些算法较为成熟,在不同领域证明了其适用性,但在Web信息整合环境下的准确率并不高。Web信息整合中的数据去重相对于一般数据去重而言有其特点,由于记录通常来自不同的数据源,而不同数据源对记录存储的目的有不同的侧重,这样致使某些记录的某些属性可能会缺失,进而导致相似记录的匹配出现较大偏差。针对相似重复记录清洗中的两个关键问题结合Web信息整合的特点,本文提出一种逐级聚类的数据去重(StepwiseClusteringDataElimination,SCDE)算法,并在精确去重阶段,提出基于动态权重的模糊实体匹配策略。1逐级聚类的数据去重方法本文提出的逐级聚类数据去重算法,首先由专家利用领域知识人工选定关键属性,依据其对记录集进行互无交叉的分割;然后借用Canopy聚类思想,使用一种开销小的算法对记录粗聚类;最后并行地在子记录集中通过两两比较精确去重相似记录,大大缩小搜索空间,降低计算量,提高3了时间效率。此外,在子记录集中精确检测相似记录时,提出基于动态权重的模糊实体匹配策略,采用动态权重赋值的方法,降低了属性空值对相似记录匹配造成的影响,并对名称的特殊性进行处理,提高匹配准确率。,一条记录往往由若干属性值组成,属性描述了实体记录的特征,但在众多属性描述记录特征时的重要性是不同的,至少有一个关键属性对相似记录匹配起决定性作用(当该属性值相