第3卷第3期 智能系统学报 Vol 3 Na 3 2008年6月 CAA I Transactions on Intelligent System s Jun 2008 融合粒子群算法改进L数据智能清洗策略 刘波，杨路明'，邓云龙2 (1.中南大学信息学院，湖南长沙410083,2中南大学湘雅附三医院，湖南长沙410013) 摘要：针对ML数据质量问题，以ML键为基础、借助多模板隐马尔可夫模型信息抽取策略与粒子群算法构建新 的ML数据清洗方法：为了提高ML相似性数据并行检测效率，尝试利用波函数对粒子群算法进行相应优化.对比 其他ML数据清洗算法，一系列仿真实验表明改进的ML数据清洗方法不仅自适应学习功能强、人工参与程度低、 计算量小，而且时间性能有94%左右提升. 关键词：ML键：粒子群算法，数据清洗；隐马尔可夫模型 中图分类号：TP31113文献标识码：A文章编号：1673-4785(2008)03-0226-08 An intelligence data clean ing stra tegy for XML da tabase using PSO L U Bo,YANG Lum ing,DENG Yun-long (1.College of Inomation Science and Engineering.Central-south University,Changsha 410083,China;2 The 3rd Xiangya Hoi tal,Central-south University,Changsha 410013,China) Abstract:To mprove XML data quality,this paper proposes a new XML data cleaning method based on XML- keys,the infomation draw-out strategy of multiple templates,the hidden Markov model (HMM),and particle sam opti ization (PSO).To mprove parallel efficiency when detecting sm ilar XML records,a wave function is empbyed to mprove the PSO algorithm.A series of smulations indicated that,compared with other XML data cleaning algorithms,the mproved XML data cleaning algorithm has a more powerful adaptive leaming capability, requires less human interaction,and reduces computational tme by about 94%. Keywords:XML key,particle swam optm ization;data cleaning hidden Markov model 目前Web上已经积累了大量的ML数据，这检测方法和陈伟提出的ML相似重复数据的清 些参差不齐的数据形成了许多“脏数据”，它们会阻 理方法51等；3)数据清洗框架，如陆凤霞提出的开 碍商业应用，因此需要对它们进行挖掘、清洗，这是 放式数据清理框架6]，王桐提出的基于改进粒子群 提高数据质量的关键.由于国外信息化程度较高，对 优化的结构聚类方法II,R ichi Nayak根据语义和上 数据清洗的需求较为迫切，因此当前的研究大多集 下文相似性对ML文档进行分级、智能聚类等操 中在国外11：随着国内信息化的快速发展，对数据 作1,4)数据分析工具，如RieraLedesa与Salazar 清洗的研究也逐步展开，并取得了骄人的成果36) Gonzalez针对数据数清洗时局部错误数据提出的分 当前数据清洗的研究主要集中如下：1)特殊域清 枝切割算法1和启发式求解算法1等；5)EL工 洗，主要解决某类特定应用域的数据清洗，这是目前 具，如Lee根据数据挖掘过程的学习环境提出的诊 研究得较多的领域，也是应用最成功的一类，2)与 断、预测与合成模型山等.但这些研究或多或少存 特定应用领域无关的数据清洗，主要集中在清洗重 在不完备的地方，主要表现如下：1)数据清洗的研 复的记录，如郑仕辉提出的基于MML相似重复记录 究主要集中在字符型数据上，识别其他字段之间的 关系异常还不成熟、实用，还需探索更灵活的清洗手 收稿日期：2007-06-25 基金项目：湖南信息职业学院科技创新资助项目(108652006011)：湖 段和更实用的清洗算法；2)尽管检测重复记录受到 南省教育厅科研基金资助项目(05c671). 很大的关注，采取了许多措施，但遭遇海量数据时， 通讯作者：刘波.Email:ltho99@yahoo com cn 耗时太多，检测效率与检测精度并不令人满意，3) 1994-2008 China Academic Journal Electronic Publishing House.All rights reserved.http://www.cnki.net第 3卷第 3期 智 能 系 统 学 报 Vol. 3 №. 3 2008年 6月 CAA I Transactions on Intelligent System s Jun. 2008 融合粒子群算法改进 XML数据智能清洗策略 刘 波 1 ,杨路明 1 ,邓云龙 2 (1. 中南大学 信息学院 ,湖南 长沙 410083; 2. 中南大学 湘雅附三医院 ,湖南 长沙 410013) 摘 要 :针对 XML数据质量问题 ,以 XML键为基础、借助多模板隐马尔可夫模型信息抽取策略与粒子群算法构建新 的 XML数据清洗方法 ;为了提高 XML相似性数据并行检测效率 ,尝试利用波函数对粒子群算法进行相应优化. 对比 其他 XML数据清洗算法 ,一系列仿真实验表明改进的 XML数据清洗方法不仅自适应学习功能强、人工参与程度低、 计算量小 ,而且时间性能有 94%左右提升. 关键词 : XML键 ;粒子群算法 ;数据清洗 ;隐马尔可夫模型 中图分类号 : TP311. 13 文献标识码 : A 文章编号 : 167324785 (2008) 0320226208 An intelligence data clean ing strategy for XML database using PSO L IU Bo 1 , YANG Lu2m ing 1 , DENG Yun2long 2 (1. College of Information Science and Engineering, Central2south University, Changsha 410083, China ; 2. The 3 rd Xiangya Hosp i2 tal, Central2south University, Changsha 410013, China) Abstract: To imp rove XML data quality, this paper p roposes a new XML data cleaning method based on XML2 keys, the information draw2out strategy of multip le temp lates, the hidden Markov model ( HMM ) , and particle swarm op tim ization (PSO). To imp rove parallel efficiency when detecting sim ilar XML records, a wave function is emp loyed to imp rove the PSO algorithm. A series of simulations indicated that, compared with other XML data cleaning algorithm s, the imp roved XML data cleaning algorithm has a more powerful adap tive learning capability, requires less human interaction, and reduces computational time by about 94%. Keywords:XML key; particle swarm op tim ization; data cleaning; hidden Markov model 收稿日期 : 2007206225. 基金项目 :湖南信息职业学院科技创新资助项目 ( 108652006011) ;湖 南省教育厅科研基金资助项目 (05c671). 通讯作者 :刘 波. E2mail: ltbo99@yahoo. com. cn. 目前 W eb上已经积累了大量的 XML数据 ,这 些参差不齐的数据形成了许多“脏数据 ”,它们会阻 碍商业应用 ,因此需要对它们进行挖掘、清洗 ,这是 提高数据质量的关键. 由于国外信息化程度较高 ,对 数据清洗的需求较为迫切 ,因此当前的研究大多集 中在国外 [ 122 ] ;随着国内信息化的快速发展 ,对数据 清洗的研究也逐步展开 ,并取得了骄人的成果 [ 326 ] . 当前数据清洗的研究主要集中如下 : 1 )特殊域清 洗 ,主要解决某类特定应用域的数据清洗 ,这是目前 研究得较多的领域 ,也是应用最成功的一类 ; 2)与 特定应用领域无关的数据清洗 ,主要集中在清洗重 复的记录 ,如郑仕辉提出的基于 XML相似重复记录 检测方法 [ 4 ]和陈伟提出的 XML相似重复数据的清 理方法 [ 5 ]等 ; 3)数据清洗框架 ,如陆凤霞提出的开 放式数据清理框架 [ 6 ] ,王桐提出的基于改进粒子群 优化的结构聚类方法 [ 7 ] , Richi Nayak根据语义和上 下文相似性对 XML 文档进行分级、智能聚类等操 作 [ 8 ] ; 4)数据分析工具 ,如 Riera2Ledesma与 Salazar2 González针对数据数清洗时局部错误数据提出的分 枝切割算法 [ 9 ]和启发式求解算法 [ 10 ]等 ; 5) ETL 工 具 ,如 Lee根据数据挖掘过程的学习环境提出的诊 断、预测与合成模型 [ 11 ]等. 但这些研究或多或少存 在不完备的地方 ,主要表现如下 : 1)数据清洗的研 究主要集中在字符型数据上 ,识别其他字段之间的 关系异常还不成熟、实用 ,还需探索更灵活的清洗手 段和更实用的清洗算法 ; 2)尽管检测重复记录受到 很大的关注 ,采取了许多措施 ,但遭遇海量数据时 , 耗时太多 ,检测效率与检测精度并不令人满意 ; 3)