第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)
第3期 刘波，等：融合粒子群算法改进ML数据智能清洗策略 ·227· 大多数数据清洗工具都是针对特定的领域，其应用 ①P',P"和K构成Pahs(T)的一个划分； 受到一定的限制.虽然特定领域的数据清洗仍是应 ②VP,p∈p',K→P 用的重点，但较通用的清洗解决方案会受到越来越 ③pP}∈P”了{p,pm},使得{p, 多的关注：4)国产的数据清洗工具还很少，其主要 …pm}UK→P 是研究重复记录的清洗问题，目前还很少研究关于 3)K的任何真子集都不满足1)和2). 不完整数据、错误数据的清洗问题，5)日前数据清 根据上述的定义及约束条件，给出一个求解 洗的研究主要集中在结构化数据上，而ML的通用 FD集∑的候选键算法： 性、自描述性等特征使它在互联网上得到了广泛的 输入：一个FDw集∑，路径集Pahs(T); 应用，其相应的Web数据越来越多，而对它的数据 管理研究却滞后. 输出：∑的一个候选健K; 针对以上分析，本文将以ML键为基础讨论构 Finding a Candidate Key for XML(∑， 建ML数据清洗的过程 Paths(T)). 1基本定义与MML键的获取 1)初始化：{LP左部路径集；RP一右部路径 集；DP←双部路径集，；EP←外部路径集： 定义1脏数据3指不符合数据仓库或上层 2)P"-EP; 应用逻辑规格的数据，清洗过程中识别脏数据后，将 3)ifDP=Φhen{K←LP;etum(K);} 会丢弃或转换，用DirtyData表示； else{K-LPU{所有右部路径的左部路 定义2清洗检查指检测出干净数据或脏数据 径}，P'RP 的过程，用条件函数cond:Daa→boo lean表示：cond (data)=tnue表示数据项data验证为脏数据(daa∈ ∑·∑·所有右部路径出现过的Dm的 DirtyData);cond(data)=false表示数据项data验证 约束}； 为千净数据(daa∈CleanData); whie∑≠Φdo 定义3数据清洗[3指从各种原始数据中抽 {f6 r each(侮个FDoM:1,Pm→B1, 取出干净数据的过程，可以形式化表示为Daa Bmin∑中) Clean:RawData-CleanData; K-K U{pa..Px; 定义4ML文档树指一棵ML文档树被定 义为T=W,chl,lab,val,V,),其中V为ML文档 ∑+∑-{A1,Bm→1，B 树T中的节点集合，V为根结点，chl表子节点的集 for each(Ba,;Bm的FDM:中inRP) 合，val表从集合V到EUSUA(E为元素名称集 {K←KU种的左部路径}； 合，S:指代#PCDA TA,A:属性名称集合)的映射函 ∑∑ 数 or each（VBH1,'Bm的FDom:Φ'imLP) 针对ML树T及其对应的架构，一个L关 {∑∑-φ：} 键字就是一个对(Hh,h,,A}),其中H是一 }} 个路径表达式Pahs(T),fn,B,,A}是一个简 }} 单路径表达式的集合，其约束关系如下：取出任意2 4)retum(K). 个节点（m,n)∈[[H]1,对应2个节点集合对 例下面选用英文的ACMSICMOD2007的ML数 (m[[B11,h[p,1),这2个集合分别是从m、 据集进行举例分析2]，QMS1GMOD数据集是由53 沿着路径p,所到达的节点的集合. 卷ML格式的ACMSICMOD论文组成的，其文档结 定义5ML候选键约束指给定DDD= 构如图1(a)所示」 (E,A,P,R,,任意的ML文档树TFD, 为了减少单个键值的操作冲突，一般选择相应 Pahs(T)为文档树T上的路径集合，是MML函数 一组ML键构成相应集合，如图1(a)对应键组合 依赖(ML functinal dependency,FD)集，K是 {signodrecord→issues→issue→olum e,signodrecord FD集∑的候选键，当且仅当 →issues→issue*num ber,.sigmodrecord→issues◆is 1)K是Pahs(T)中元素构成的集合； sue→articles→article→title,signodrecord→issues- 2)存在路径P',P使得 issue→articles→article→au tho rs→au thor} 1994-2008 China Academic Journal Electronic Publishing House.All rights reserved.http://www.cnki.net
大多数数据清洗工具都是针对特定的领域 ,其应用 受到一定的限制. 虽然特定领域的数据清洗仍是应 用的重点 ,但较通用的清洗解决方案会受到越来越 多的关注 ; 4)国产的数据清洗工具还很少 ,其主要 是研究重复记录的清洗问题 ,目前还很少研究关于 不完整数据、错误数据的清洗问题 ; 5)目前数据清 洗的研究主要集中在结构化数据上 ,而 XML的通用 性、自描述性等特征使它在互联网上得到了广泛的 应用 ,其相应的 Web数据越来越多 ,而对它的数据 管理研究却滞后. 针对以上分析 ,本文将以 XML键为基础讨论构 建 XML数据清洗的过程. 1 基本定义与 XML键的获取 定义 1 脏数据 [ 324 ]指不符合数据仓库或上层 应用逻辑规格的数据 ,清洗过程中识别脏数据后 ,将 会丢弃或转换 ,用 D irtyData表示 ; 定义 2 清洗检查指检测出干净数据或脏数据 的过程 ,用条件函数 cond: Data→boolean表示 : cond ( data) = true表示数据项 data验证为脏数据 ( data∈ D irtyData) ; cond ( data) = false表示数据项 data验证 为干净数据 ( data∈CleanData) ; 定义 3 数据清洗 [ 324 ]指从各种原始数据中抽 取出干净数据的过程 ,可以形式化表示为 Data2 Clean: RawData→CleanData; 定义 4 XML文档树指一棵 XML文档树被定 义为 T = (V , chl, lab, val, Vr ) ,其中 V为 XML文档 树 T中的节点集合 , V r为根结点 , chl表子节点的集 合 , val表从集合 V 到 E ∪ S ∪ A ( E为元素名称集 合 , S :指代 #PCDATA, A :属性名称集合 )的映射函 数. 针对 XML树 T及其对应的架构 ,一个 XML关 键字就是一个对 (H, { p1 , p2 , …, pn } ) ,其中 H是一 个路径表达式 Paths ( T) , { p1 , p2 , …, pn } 是一个简 单路径表达式的集合 ,其约束关系如下 :取出任意 2 个节点 ( n1 , n2 ) ∈ [ [H ] ], 对应 2个节点集合对 ( n1 [ [ pi ] ], n2 [ [ pi ] ]) ,这 2个集合分别是从 n1、n2 沿着路径 pi 所到达的节点的集合. 定义 5 XML 候选键约束指给定 DTD D = ( E, A, P, R, r) , 任 意 的 XML 文 档 树 T 5 D , Paths( T)为文档树 T上的路径集合 , 是 XML 函数 依赖 ( XML functional dependency, FD ) 集 , K 是 FDXML集 ∑的候选键 ,当且仅当 1) K是 Paths( T )中元素构成的集合 ; 2)存在路径 P′, P″使得 ① P′, P″和 K构成 Paths( T )的一个划分 ; ② Π P′i , P′i ∈ P′, K → P′i; ③ Π P′j , P′j ∈P″, ϖ { p′x1 , …, p′xn },使得 { p′x1 , …, p′xn } ∪ K → P′j; 3) K的任何真子集都不满足 1)和 2). 根据上述的定义及约束条件 ,给出一个求解 FDXML集 ∑的候选键算法 : 输入 :一个 FDXML集 ∑,路径集 Paths( T ) ; 输出 : ∑的一个候选健 K ; Finding a Candidate Key for XML ( ∑, Paths( T) ). 1)初始化 : { L P ←左部路径集; R P ←右部路径 集; D P ←双部路径集; EP ←外部路径集 }; 2 ) P″← EP ; 3) ifD P =Φ then { K ←L P ; return ( K ) ; } else { K ← L P ∪{所有右部路径的左部路 径 }; P′← R P; ∑← ∑ - {所有右部路径出现过的 FDXML的 约束 }; while ∑≠Φ do { for each (每个 FDXML : px1 , …, pxn → py1 , …, pym in ∑中 ) { K ← K ∪ { px1 , …, pxn } ; ∑← ∑- { px1 , …, pxn → py1 , …, pym }; for each ( py1 , …, pym 的 FDXML : φ in R P ) { K ← K ∪ {φ的左部路径 }; ∑← ∑- φ; for each ( Π py1 , …, pym 的 FDXML : φ′in L P ) { ∑← ∑- φ′; } } } } } 4) return ( K ). 例 下面选用英文的 ACMSIGMOD2007的 XML 数 据集进行举例分析 [ 12 ] , CMSIGMOD数据集是由 53 卷 XML格式的 ACMSIGMOD论文组成的 ,其文档结 构如图 1 ( a)所示. 为了减少单个键值的操作冲突 ,一般选择相应 一组 XML键构成相应集合 ,如图 1 ( a)对应键组合 { sigmodrecord→issues→issue→volume, sigmodrecord →issues→issue→number, sigmodrecord→issues→ is2 sue→articles→article→title, sigmodrecord→issues→ issue→articles→article→authors→author}. 第 3期 刘 波 ,等 :融合粒子群算法改进 XML数据智能清洗策略 · 722 ·
·228- 智能系统学报 第3卷 root sigmodrecord 需要解决MM中的学习与解码问题，因此整个操 作划分为三大步骤：1)以ML键组合训练数据为 issues -element 几个类：2)训练MM参数，3)使用学习到的HMM (issue 参数进行ML数据抽取 volume rumberCarticles 1)基于马尔可夫链模型，以ML键组合训练 数据为几个类 value 15 2 Carticle 若第k个已标记的训练ML文档序列用以下 titleauthors 的转移概率矩阵Ak表示：Ak=(,其中 distributed( author PA刘= S十0一，a=B 1) DB system n Xn carey lu (Su+ 式中：S是训练ML文档序列中从标记状态转移 (a)sigmodrecord文档树 到标记状态的次数，通常取B=n,n是模型状态 (root -proceedingspage 数 volume (dateyear confyear ①ocation nit-,1≤ij≤N. (2) numbe (month articles (conference element ∑nit(D article 式中：hit(表所有训练序列中，初始状态为的序 title∠ tofulltext to addition- Cinitpage 列个数 almaterial Cauthor endpage Format addotionak 0 CL,1≤ij≤N. 二N 3) value- +108119 material iadex ienis 式中：C,是所有训练序列中从状态S,转换到状态S (b)ProceedingsPage文档树 的次数 图1 ACMSIMOD数据集合中的两个MML文档的 b(V)= DOM树 E,1≤j≤N,1≤k≤M4 Fig 1 The DOM tree of to XML documents extracted ∑E, fiom ACMS IMOD dataset 式中：E,W)是所有训练序列中状态S,释放单词Vx 的次数 2多模板隐马尔科夫模型与ⅪML文 若第k个训练序列用矩阵A:表示，第个训练 序列用矩阵A,表示，那么这2个训练ML文档序 档向量化 列之间的距离可用以下公式来计算： 虽然ML键组合有利简化ML数据的提取， ∑∑nbg+∑∑Albg P行子 但ML数据本身的多样性与数据清洗需要知识库 D(Ak.A1) 2×n 作为蓝本，对于动态的ML数据难以建立一个固定 (5) 的知识库样本，因此利用ML键组合构建隐马尔可 那么对任意2个马尔可夫链，当它们具有相同的 夫模型(HMM)的多模板功能灵活地实现ML数据 动态特征时，它们之间的距离为零.当它们之间的动态 的抽取就是一个较好地选择 特征差异越大，距离值就越大.这样，就能够得到任意2 一个隐马尔可夫模型是一个五元组：Qx, 个训练ML文档序列之间的距离，基于这种距离，通 P。,A,B,),其中：Px=(,h,,}表状态的 过调节距离的门槛值，可以控制得到的分类个数 有限集合：0。=(5，，表观察值的有限集 2)对每一类训练数据，依次利用式2)~(4)训 合；A=fag,a=p(X+1=qK,=q)表转移概率： 练初始概率矩阵π转移概率矩阵A以及状态释放 B={bk},be=p(O,=X,=,表输出概率；T= 概率B. π，/，π，=p(X,=g,表初始状态分布，那么入=A, 3)使用训练好的模型抽取ML数据时，结合 B,π是给定HMM的参数，则应用HMM主要解决 每一个初始概率矩阵π、转移概率矩阵A和统一的 如下问题：评估、解码与学习问题，而ML数据抽取 释放概率矩阵B,使用马尔可夫模型的韦特比算法 1994-2008 China Academic Journal Electronic Publishing House.All rights reserved.http://www.cnki.net
图 1 ACMSIGMOD数据集合中的两个 XML文档的 DOM树 Fig. 1 The DOM tree of two XML documents extracted from ACMSIGMOD dataset 2 多模板隐马尔科夫模型与 XML文 档向量化 虽然 XML键组合有利简化 XML数据的提取 , 但 XML数据本身的多样性与数据清洗需要知识库 作为蓝本 ,对于动态的 XML数据难以建立一个固定 的知识库样本 ,因此利用 XML键组合构建隐马尔可 夫模型 (HMM)的多模板功能灵活地实现 XML数据 的抽取就是一个较好地选择. 一个隐马尔可夫模型 [ 13214 ]是一个五元组 : (ΩX , ΩO , A, B,π) ,其中 :ΩX = { q1 , q2 , . . . , qN }表状态的 有限集合;ΩO = { v1 , v2 , . . . , vM }表观察值的有限集 合; A = { aij}, aij = p (Xt + 1 = qj |Xt = qi )表转移概率; B = { bik }, bik = p (Ot = vk | Xt = qi )表输出概率;π = {πi },πi = p (Xi = qi )表初始状态分布 ,那么 λ = {A, B,π}是给定 HMM 的参数 ,则应用 HMM 主要解决 如下问题 :评估、解码与学习问题 ,而 XML数据抽取 需要解决 HMM 中的学习与解码问题 ,因此整个操 作划分为三大步骤 : 1)以 XML 键组合训练数据为 几个类 ; 2)训练 HMM 参数 ; 3)使用学习到的 HMM 参数进行 XML数据抽取. 1)基于马尔可夫链模型 ,以 XML 键组合训练 数据为几个类. 若第 k个已标记的训练 XML文档序列用以下 的转移概率矩阵 Ak 表示 : Ak = ( pk ij ) ,其中 pk ij = Sk ij +αk ij ∑ n j =1 (Sk ij +αk ij ) , αk ij = β n ×n . (1) 式中 : Sk ij是训练 XML文档序列中从标记状态 i转移 到标记状态 j的次数 ,通常取 β = n, n是模型状态 数. πi = Init( i) ∑ N j=1 Init( j) , 1 ≤ i, j ≤N. (2) 式中 : Init( i)表所有训练序列中 ,初始状态为 i的序 列个数. αij = Cij ∑ N k =1 Cik , 1 ≤ i, j ≤N . (3) 式中 : Cij是所有训练序列中从状态 Si 转换到状态 Sj 的次数. bj (Vk ) = Ej (Vk ) ∑ M k =1 Ej ( vk ) , 1 ≤ j ≤N, 1 ≤ k ≤M. (4) 式中 : Ej (Vk )是所有训练序列中状态 Sj释放单词 Vk 的次数. 若第 k个训练序列用矩阵 Ak 表示 ,第 l个训练 序列用矩阵 Al 表示 ,那么这 2个训练 XML文档序 列之间的距离可用以下公式来计算 : D (Ak , Al ) = ∑ n i =1 ∑ n j=1 pk ij log pk ij plij + ∑ n i =1 ∑ n j =1 plij log plij pk ij 2 ×n . (5) 那么对任意 2个马尔可夫链,当它们具有相同的 动态特征时,它们之间的距离为零. 当它们之间的动态 特征差异越大,距离值就越大.这样,就能够得到任意 2 个训练 XML文档序列之间的距离,基于这种距离,通 过调节距离的门槛值,可以控制得到的分类个数. 2)对每一类训练数据 ,依次利用式 (2) ～( 4)训 练初始概率矩阵 π、转移概率矩阵 A 以及状态释放 概率 B. 3)使用训练好的模型抽取 XML 数据时 ,结合 每一个初始概率矩阵 π、转移概率矩阵 A 和统一的 释放概率矩阵 B,使用马尔可夫模型的韦特比算法 · 822 · 智 能 系 统 学 报 第 3卷
第3期 刘波，等：融合粒子群算法改进ML数据智能清洗策略 ·229· 找出最优的标记序列，并从这些最优标记序列中选 (,,,+k.1)将ML数据库中的每一个 择一个概率最大的序列作为最终标记序列.即对于 ML文档D映射为一个k维的距离向量Vo,Vo的 每一种分类模板使用韦特比算法一次，这样每一个 第维坐标可以通过计算D和，之间的语义距离得 模板都会产生一个标记序列，从所有这些模板产生 到，V。[t=ed(D,r,这样通过参照集RS,每个 的最优标记序列中选出概率最大的序列作为最终输 ML文档D可被映射为n个k维距离向量V。,再 出结果 将这n个距离向量V。的平均值作为每个ML文档 虽然这样抽取ML数据比较灵活，但有一种情形 D在k维坐标平面上的投影V[万，，，这样就 必须考虑，就是缩写词的处理，它是ML数据清理中 可以降低ML维度，有利ML操作」 不可回避的问题，如中南大学信息科学与工程学院，可 向量化的主要目的是将一个较长的记录进行分 以叫中大信息学院，中大信息院等，都是同一个单位， 解，根据属性大小分成更小的信息片断，对来自2个 在此参考文献15提出的动态缩写发现算法进行处 或多个L数据库的数据可以将所有可能匹配的 理，毕竞在专业领域内，缩写的形式和内容存在一定的 记录排在一起，组成一个序列，然后应用以下步骤匹 规律，模式比较固定，因此应用启发式规则或知识库 配相应记录： 来选择真正的缩写形式是可行的. 1)产生键值：在记录序列里，取每个记录的相 利用多模板的隐马尔可夫模型构建ML数据 关字段或字段的一部分按求解ML候选键算法生 的清洗知识库后，就可以对海量ⅫML数据进行相应 成每个记录的键. 清洗了，为了降低清洗的难度，在此首先需要把 2)排序：在记录序列里应用第一步产生的键值 ML文档树进行向量化. 对记录进行排序. 定义6ML文档向量化指从ML数据库中 3比较、合并与剔除：在排好序的记录里，利用 按照ML键组合抽取组且每组包含属性长度k多模板的隐马尔可夫模型提取的知识库在记录序列 个ML文档而构成一个参照集RS,S={(片，， 里按选定方向移动，在某个距离范围内选择相似点， 八，(E1,尸，(aDk,t”,其中 除去相同元素、修补欠缺元素、更正错误元素等，达 (,,,+.1的选取尽可能的按照差异最大 到清除目的 化的原则，这个差异由ML文档间距来评定.通过 因此本文研究的数据清洗过程用图2表示. 多模板院 XMI 马尔可夫模型 知识库 XML XML源数据 键组合 清洗 清洗 1操作 干净数据 检查 XML向量化 数据泸洗 图2ML数据清洗过程 Fig 2 The data cleaning's process of XML 这样设计的主要优点是： 一种智能优化算法，最初由Kennedy和Eberhart于 1)无需对ML数据源数据进行假设，可以直 1995年提出并成功地应用于函数优化，后来进行了 接对ML文档进行数据处理； 大量地拓展.它是对鸟群觅食过程和聚集的模拟，是 2加强了ML数据清洗的功能，由于ML键 一种全局优化算法，现在有许多改进版本，其优化表 的参与，数据抽取与量化有了方向，数据清洗可以更 达式如下： 加灵活和贴近原始数据 =0X+gX万X(p-X)+ 为了更快捷地利用抽取的知识库对量化的 2X X(paX), 6) ML数据进行相似性比较，特引入并优化粒子群算 =X+a 法参与ML数据清洗过程， Xex run 3粒子群算法与ML数据清洗算法 (8) 粒子群算法61是近年来被广泛关注和研究的 式中：r为区间0,1]上的随机数，o为惯性权重，o 1994-2008 China Academic Journal Electronic Publishing House.All rights reserved.http://www.cnki.net
找出最优的标记序列 ,并从这些最优标记序列中选 择一个概率最大的序列作为最终标记序列. 即对于 每一种分类模板使用韦特比算法一次 ,这样每一个 模板都会产生一个标记序列 ,从所有这些模板产生 的最优标记序列中选出概率最大的序列作为最终输 出结果. 虽然这样抽取 XML数据比较灵活,但有一种情形 必须考虑,就是缩写词的处理,它是 XML数据清理中 不可回避的问题,如中南大学信息科学与工程学院,可 以叫中大信息学院,中大信息院等,都是同一个单位, 在此参考文献 [15 ]提出的动态缩写发现算法进行处 理,毕竟在专业领域内, 缩写的形式和内容存在一定的 规律, 模式比较固定, 因此应用启发式规则或知识库 来选择真正的缩写形式是可行的. 利用多模板的隐马尔可夫模型构建 XML数据 的清洗知识库后 ,就可以对海量 XML数据进行相应 清洗了 , 为了降低清洗的难度 , 在此首先需要把 XML文档树进行向量化. 定义 6 XML文档向量化指从 XML数据库中 按照 XML键组合抽取 n组且每组包含属性长度 k 个 XML文档而构成一个参照集 RS, RS = { ( r1 , …, rk ) 1 , ( rk + 1 , …, r2k ) 2 , …, ( r( n - 1) k , …, rnk ) n }, 其中 ( ri , …, rt , …, ri + k - 1 )的选取尽可能的按照差异最大 化的原则 ,这个差异由 XML文档间距来评定. 通过 ( ri , …, rt , …, ri + k - 1 )将 XML 数据库中的每一个 XML文档 D映射为一个 k维的距离向量 VD , VD 的 第 t维坐标可以通过计算 D和 rt 之间的语义距离得 到 , VD [ t] = ed (D, r ) , 这样通过参照集 RS, 每个 XML文档 D 可被映射为 n个 k维距离向量 VD ,再 将这 n个距离向量 VD 的平均值作为每个 XML文档 D在 k维坐标平面上的投影 VD [ r1 , …, rk ],这样就 可以降低 XML维度 ,有利 XML操作. 向量化的主要目的是将一个较长的记录进行分 解 ,根据属性大小分成更小的信息片断 ,对来自 2个 或多个 XML数据库的数据可以将所有可能匹配的 记录排在一起 ,组成一个序列 ,然后应用以下步骤匹 配相应记录 : 1)产生键值 :在记录序列里 ,取每个记录的相 关字段或字段的一部分按求解 XML候选键算法生 成每个记录的键. 2)排序 :在记录序列里应用第一步产生的键值 对记录进行排序. 3)比较、合并与剔除 :在排好序的记录里 ,利用 多模板的隐马尔可夫模型提取的知识库在记录序列 里按选定方向移动 ,在某个距离范围内选择相似点 , 除去相同元素、修补欠缺元素、更正错误元素等 ,达 到清除目的. 因此本文研究的数据清洗过程用图 2表示. 图 2 XML数据清洗过程 Fig. 2 The data cleaning’s p rocess of XML 这样设计的主要优点是 : 1)无需对 XML 数据源数据进行假设 ,可以直 接对 XML文档进行数据处理; 2)加强了 XML数据清洗的功能 ,由于 XML键 的参与 ,数据抽取与量化有了方向 ,数据清洗可以更 加灵活和贴近原始数据. 为了更快捷地利用抽取的知识库对量化的 XML数据进行相似性比较 ,特引入并优化粒子群算 法参与 XML数据清洗过程. 3 粒子群算法与 XML数据清洗算法 粒子群算法 [ 16 ]是近年来被广泛关注和研究的 一种智能优化算法 ,最初由 Kennedy和 Eberhart于 1995年提出并成功地应用于函数优化 ,后来进行了 大量地拓展. 它是对鸟群觅食过程和聚集的模拟 ,是 一种全局优化算法 ,现在有许多改进版本 ,其优化表 达式如下 : V t+1 i =ω ×V t i + c1 ×r1 ×( pbd i - X t i ) + c2 ×r2 ×( pgd - X t i ) , (6) X t+1 i = X t i +αV t+1 i , (7) ω =ωmax - (ωmax - ωm in ) ×exp 1 - sqrt runmax run . (8) 式中 : r为区间 [ 0, 1 ]上的随机数 ,ω为惯性权重 ,ω 第 3期 刘 波 ,等 :融合粒子群算法改进 XML数据智能清洗策略 · 922 ·
·230· 智能系统学报 第3卷 ∈02,12)，其中om为最大惯性权重值，omn为 最小惯性权重值，nun为当前迭代次数，nuna为算法 迭代总次数，ā为控制速度的约束因子，G是认知系 数，6是社会系数，G+9=4,在此对0、a、G、9统 称为权重因子 那么若抽取的MML文档知识库规模为k利用 P9O算法进行相似性测量过程如图3所示. 、初始化设置 图4粒子相似性检测划分过程 Fig 4 The sm ilarity checking and pltting process 初始化种群 of particle 评价粒子的适应度 dex =1- min小al.1创) 选择PBi与GB d(a.b)+max(a l.b)-min(l al,Ib) 粒子状态更新 min(l al.I1) (9) 满足设定条件 N 计算距离，a、b,表示2个标识对应的字符，d(a,b) Y 表示对应字符间的距离，若a,=b,则d(a,b,)=1, (输出最优结果 否则d(a,b,)=0max(|al,1b1)-mim(1al,|b1) 图3P9O操作过程 表示多余的字符相应的距离 Fig 3 The operating process of PSO 字符串匹配问题字符串属于长信息字段，可再 分解，然后根据标识的重要性分配权值，利用 在此过程中，利用定义6将向量化的ML知识 ⊥a∩bL (10) 库投影为二维坐标平面上的样本点，同时将二维平 des =1-min(l al.Ibl) 面进行等间距网格划分，并将待检测己向量化的 来计算标识距离，字段距离为标识距离的加权和，其 ML数据粒子随机分散于一个平面上，即随机赋 中a、b都是标识，|a∩b标识a、b中相同的字符数： 给每个粒子一对(x,y以坐标，同时以本粒子初始对 |a表示a的长度，Ib表示b的长度. 应坐标为中心，为观察半径，利用式(9)或(10)计 由于粒子群算法的时间复杂度为O(cXn, 算此模式在观察半径范围内的粒子相似度，同时依 对海量ML文档进行检测，其代价较高，因此需要 次检测该网格周围的邻域网格是不是大于最少样本 根据其量化过程对粒子群操作进行优化，并建立波 函数的粒子群(WP9O)并行处理机制 点数，若大于就将网格的坐标加入到邻域连接缓冲 在量子时域空间的框架下，粒子的状态由一个 列表的尾部，否则就将网格内的所有样本点丢弃，这 波函数中(x,来描述，在三维空间中粒子的波函数 样依次计算已形成的每一个文档类的检测中心 描述为 在运用P9O检测相似重复记录之前，需要先对 I中|2 dxdydx=Odxdyd:: (11) 数据进行一些处理，主要处理操作包括 式中：「中2波函数的概率密度，并且满足 1)字段分裂.依据ML键组合的结构，利用多 模板的隐马尔可夫模型抽取各个部分； 了i电Pddd=了eddd:=l,那么粒子群算 2验证和改正.根据知识库及相关领域知识验 法可优化成如下形式： 证提取值的正确性，若发现错误，则加以改正； P (a pa +h pes)/(a+b). (12) 3)数据标准化.将同一类型的数据用统一的格 L=(1/g).abs(xa p). 13) 式来表示，比如日期、电话号码、性别等 xa=p出(ln(I/u. (14) 4)在计算过程中，可分别针对数字字符与字符 式中：P是第个粒子在解空间的第d维所找到的 串分别套用不同的公式计算相应的距离值，图4表 最优解，x是第个粒子在解空间第d维的当前值， 示其检测过程示意图」 P是所有粒子在解空间中第d维找到的最优解，a 数字匹配问题：可采用将全部的数字字符一一 6都是O,1)之间的随机数，而参数g的选取将直 比较的方法来得到标识距离，用公式 接影响到算法的性能，由文献16哈出的参数控制 1994-2008 China Academic Journal Electronic Publishing House.All rights reserved.http://www.cnki.net
∈[0. 2, 1. 2 ],其中 ωmax为最大惯性权重值 , ωm in为 最小惯性权重值 , run为当前迭代次数 , runmax为算法 迭代总次数 ,α为控制速度的约束因子 , c1 是认知系 数 , c2 是社会系数 , c1 + c2 = 4,在此对 ω、α、c1、c2 统 称为权重因子. 那么若抽取的 XML文档知识库规模为 k,利用 PSO算法进行相似性测量过程如图 3所示. 图 3 PSO操作过程 Fig. 3 The operating p rocess of PSO 在此过程中 ,利用定义 6将向量化的 XML知识 库投影为二维坐标平面上的样本点 ,同时将二维平 面进行等间距网格划分 , 并将待检测已向量化的 XML数据粒子随机分散于一个平面上 , 即随机赋 给每个粒子一对 ( x, y)坐标 ,同时以本粒子初始对 应坐标为中心 , r为观察半径 ,利用式 ( 9)或 ( 10)计 算此模式在观察半径范围内的粒子相似度 ,同时依 次检测该网格周围的邻域网格是不是大于最少样本 点数 ,若大于就将网格的坐标加入到邻域连接缓冲 列表的尾部 ,否则就将网格内的所有样本点丢弃 ,这 样依次计算已形成的每一个文档类的检测中心. 在运用 PSO检测相似重复记录之前 ,需要先对 数据进行一些处理 ,主要处理操作包括 : 1)字段分裂. 依据 XML键组合的结构 ,利用多 模板的隐马尔可夫模型抽取各个部分; 2)验证和改正. 根据知识库及相关领域知识验 证提取值的正确性 ,若发现错误 ,则加以改正; 3)数据标准化. 将同一类型的数据用统一的格 式来表示 ,比如日期、电话号码、性别等. 4)在计算过程中 ,可分别针对数字字符与字符 串分别套用不同的公式计算相应的距离值 ,图 4表 示其检测过程示意图. 数字匹配问题 :可采用将全部的数字字符一一 比较的方法来得到标识距离 ,用公式 图 4 粒子相似性检测划分过程 Fig. 4 The sim ilarity checking and p lotting p rocess of particle dex = 1 - ∑ m in (| a| , | b| ) i =1 d ( ai , bi ) +max( | a | , | b | ) - m in ( | a | , | b | ) m in ( | a | , | b | ) (9) 计算距离 , ai、bi 表示 2个标识对应的字符 , d ( ai , bi ) 表示对应字符间的距离 ,若 ai = bi ,则 d ( ai , bi ) = 1, 否则 d ( ai , bi ) = 0; max ( | a | , | b | ) - m in ( | a | , | b | ) 表示多余的字符相应的距离. 字符串匹配问题 :字符串属于长信息字段 ,可再 分解 ,然后根据标识的重要性分配权值 ,利用 des = 1 - | a ∩ b | m in ( | a | , | b | ) (10) 来计算标识距离 ,字段距离为标识距离的加权和 ,其 中 a、b都是标识 , | a∩b |标识 a、b中相同的字符数 : | a |表示 a的长度 , | b |表示 b的长度. 由于粒子群算法的时间复杂度为 O ( nc ×n 3 ) , 对海量 XML文档进行检测 ,其代价较高 ,因此需要 根据其量化过程对粒子群操作进行优化 ,并建立波 函数的粒子群 (WPSO)并行处理机制. 在量子时域空间的框架下 ,粒子的状态由一个 波函数 ψ( x, t)来描述 ,在三维空间中粒子的波函数 描述为 | ψ | 2 dxdydx = Q dxdydz. (11) 式中 : | ψ | 2 波 函 数 的 概 率 密 度 , 并 且 满 足 ∫ +∞ - ∞ | ψ | 2 dxdydz = ∫ +∞ - ∞ Q dxdydz = 1,那么粒子群算 法可优化成如下形式 : P = ( a. pid + b. pgd ) / ( a + b) , (12) L = (1 / g). abs( xid - p) , (13) xid = p ±L. ( ln (1 / u) ). (14) 式中 : pid是第 i个粒子在解空间的第 d维所找到的 最优解 , xid是第 i个粒子在解空间第 d维的当前值 , pgd是所有粒子在解空间中第 d维找到的最优解 , a、 b、u都是 (0, 1)之间的随机数 ,而参数 g的选取将直 接影响到算法的性能 ,由文献 [ 16 ]给出的参数控制 · 032 · 智 能 系 统 学 报 第 3卷
第3期 刘波，等：融合粒子群算法改进ML数据智能清洗策略 ·231 与选取的方法，只要g满足条件：g>n2就能保证 以选择该粒子位置的更新： 算法的收敛。 3)如果个体粒子的位置超出了预设的范围，采 因此ML数据清洗的主要算法如下： 取让该粒子向相反方向飞行的策略.为了尽可能的 输入：一个FD集∑，路径集Pahs(T): 减少计算量和更好的引导粒子向最优解靠拢以增强 粒子的收敛性，规定只要当前代粒子的适应值优于 输出：一个干净的Dm集∑' 上一代，就不再更新粒子的速度与位置X Data Cleaning or XML(∑，Paths()7), 这样减少计算工作量 l)Finding a Candidate Key for XML(∑，Pahs 本算法虽然由4个部分组成，但时间性能主要 由WP9O决定，相对PSO,虽然循环代码没有多少变 (T),获取ML键组合∑g 化，但由于采用不同的更新与投影方法，其迭代次数 2)Picking up a Knowledge Lib or XML. 却大大减少 ∑gx,获取动态知识库∑曲 4实验仿真 3)利用XML知识库∑aw利用WPSO算法 41数据集与实验设计 匹配向量化的ML数据集， 实验使用CM173 GHCPU,1GB内存，80GB ①在给定的范围内初始化种群粒子的位置X SATA5400转硬盘的笔记本，在Wn2000专业p4版 和速度o; 操作系统上利用仿真软件Mathlab2007a和C妍发 ②利用式(9)或10)计算每个粒子的适应度 工具进行仿真测试. ,并将粒子群的当前位置设为4，将适应度最优位 分别选用英文的AQMS1GMOD2中2006、2005 置的粒子设为乃 2002、1999年4个年度ML数据集进行实验分析，每 ③根据步骤32的结果利用式2~14计算PL、x4: 个ACMSICMOD数据集都由数千篇不同ML格式的 ④用个体粒子的速度产生选择该粒子更新位置 ACMSICMOD论文组成的，其文档结构类似图1格 方程的数据： 式，实验选用1165个文档由表1所示. rand q =1/(1+(ax-Vid)/(vd -n)). 这4个数据集都有分类信息，在ACMS IMOD (15) 文档中，每个文档通常属于多个分类，而属于同一个 ⑤油步骤32产生的数据选择更新粒子位置的方程： 分类的L文档具有较强的相似性，因此在实验中 if rand_qQ 5xa =p +L X(In(1/u)). 采取随机选取3次训练样本，测试结果取平均，并分 else x =p-L X(In(1/u)). 别采用基于规则、聚类与本算法进行ML数据清洗 ⑥根据步骤②中x的大小判断是否更新粒子 实验评价 的速度： 98 120 ifxx 97 100 96 if xid Xmax id =Xmax,Va =-Vaf, 95 80 型 94 else if xid Xmin xd =Xmin,V =Vd 93 60 在更新粒子速度时，即使粒子的速度超出了预设的 92 0 范围，无需采取=ax、=这种策略，这样就 91 90 20 避免了分母中(x-u和(u·。)这2项为零， 96 2×10 00.51.01.X10 而式(15)分母取绝对值，保证其结果处于0和1之 记录大小/个 记录大小/个 间，也保证算法能有效运行 (a)记录大小与相对精度比 (6)记录大小与时代价 4)for each(pin∑){/收集数据成∑} 图5提取不同规模的ML数据及花费时间图 本算法中的波函数粒子群算法WPSO)相对一 Fig 5 The precision and tme of different bulk of XML data 般粒子群算法(PSO主要改进方面是： 42实验结果分析 1)它适合ML多维数据的平面处理，而向量 421多模板的隐马尔可夫模型对ML数据的抽 的投影有利降低PSO的维度灾和简化计算规模， 2)利用个体粒子的速度产生一个介于0,1)之 取能力 间的数来代替原算法中的由计算机随机产生的数 本实验利用ML键组合作为模板，利用隐马尔 1994-2008 China Academic Journal Electronic Publishing House.All rights reserved.http://www.cnki.net
与选取的方法 ,只要 g满足条件 : g > ln 2就能保证 算法的收敛. 因此 XML数据清洗的主要算法如下 : 输入 :一个 FDXML集 ∑,路径集 Paths( T) ; 输出 : 一个干净的 FDXML集 ∑′; Data Cleaning for XML ( ∑, Paths( T) ). 1) Finding a Candidate Key for XML ( ∑, Paths ( T) ) ,获取 XML键组合 ∑keyset . 2) Picking up a Knowledge Lib for XML ( ∑, ∑keyset ) ,获取动态知识库 ∑XML lib . 3)利用 XML知识库 ∑XML lib利用 W PSO算法 匹配向量化的 XML数据集. ①在给定的范围内初始化种群粒子的位置 X0 和速度 V0 ; ②利用式 ( 9)或 ( 10)计算每个粒子的适应度 fi ,并将粒子群的当前位置设为 pid ,将适应度最优位 置的粒子设为 pgd ; ③根据步骤 3. 2的结果利用式 (2)～(14)计算 P、L、xid; ④用个体粒子的速度产生选择该粒子更新位置 方程的数据 : rand_q = 1 / (1 +| ( vmax - vid ) / ( vid - vm in ) | ). (15) ⑤由步骤 3. 2产生的数据选择更新粒子位置的方程: if rand_q > 0. 5xid = p +L ×( ln (1 / u) ) , else xid = p - L ×( ln (1 / u) ). ⑥根据步骤 ②中 xid的大小判断是否更新粒子 的速度 : if x t i > x t- 1 i , if xid > Xmax { xid = Xmax , vid = - vid }, else if xid < Xm in { xid = Xm in , vid = - vid }. 在更新粒子速度时 ,即使粒子的速度超出了预设的 范围 ,无需采取 vid = vmax、vid = vm in这种策略 ,这样就 避免了分母中 ( vmax - vid )和 ( vid - vm in )这 2项为零 , 而式 (15)分母取绝对值 ,保证其结果处于 0和 1之 间 ,也保证算法能有效运行. 4) for each ( pi in ∑) { / /收集数据成 ∑′}. 本算法中的波函数粒子群算法 (W PSO )相对一 般粒子群算法 (PSO)主要改进方面是 : 1)它适合 XML 多维数据的平面处理 ,而向量 的投影有利降低 PSO的维度灾和简化计算规模; 2)利用个体粒子的速度产生一个介于 ( 0, 1)之 间的数来代替原算法中的由计算机随机产生的数 , 以选择该粒子位置的更新; 3)如果个体粒子的位置超出了预设的范围 ,采 取让该粒子向相反方向飞行的策略. 为了尽可能的 减少计算量和更好的引导粒子向最优解靠拢以增强 粒子的收敛性 ,规定只要当前代粒子的适应值优于 上一代 ,就不再更新粒子的速度 V t + 1 i 与位置 X t + 1 i , 这样减少计算工作量. 本算法虽然由 4个部分组成 ,但时间性能主要 由 W PSO决定 ,相对 PSO,虽然循环代码没有多少变 化 ,但由于采用不同的更新与投影方法 ,其迭代次数 却大大减少. 4 实验仿真 4. 1 数据集与实验设计 实验使用 C2M1. 73 GHzCPU, 1 GB内存 , 80 GB SATA5400转硬盘的笔记本 ,在 W in2000专业 sp4版 操作系统上利用仿真软件 Mathlab2007a和 C#开发 工具进行仿真测试. 分别选用英文的 ACMSIGMOD [ 12 ]中 2006、2005、 2002、1999年 4个年度 XML数据集进行实验分析 ,每 个 ACMSIGMOD数据集都由数千篇不同 XML格式的 ACMSIGMOD论文组成的 ,其文档结构类似图 1格 式 ,实验选用 1 165个文档由表 1所示. 这 4个数据集都有分类信息 ,在 ACMSIGMOD 文档中 ,每个文档通常属于多个分类 ,而属于同一个 分类的 XML文档具有较强的相似性 ,因此在实验中 采取随机选取 3次训练样本 ,测试结果取平均 ,并分 别采用基于规则、聚类与本算法进行 XML数据清洗 实验评价. 图 5 提取不同规模的 XML数据及花费时间图 Fig. 5 The p recision and time of different bulk of XML data 4. 2 实验结果分析 4. 2. 1 多模板的隐马尔可夫模型对 XML数据的抽 取能力 本实验利用 XML键组合作为模板 ,利用隐马尔 第 3期 刘 波 ,等 :融合粒子群算法改进 XML数据智能清洗策略 · 132 ·
·232· 智能系统学报 第3卷 可夫模型提取ML数据，根据ML数据规模统计 为了检测各算法对ML数据的检测能力，以表 准确提取的数据及花费时间。 1提取的数据为基础投影到二维平面上，针对不同 422WPSO与PSO对ML数据的检测能力 数据规模进行测试，实验结果如表3所示。 表1实验中使用的数据子集 Table I Data subsets used n the experient 2006(ACM·1) 2005(ACM.2) 2002(ACM-3) 1999(ACM-4) ML键个数 IndexTem sPage 0 0 0 920 13 Ord inary IssuePage 45 45 30 51 9 ProceedingsPage 6 16 17 14 SigmodRecord 1 6 表2提取不同规模的ML数据及花费时间 Table 2 Picking up different bulk of XML da ta and correspond ing time 记录大小 文档数 有数记录数 花费时间/s 52 2 51 1.1958 143 7 137 57953 297 279 195516 578 22 527 490597 1572 36 1409 1214384 表3ML数据相似性实验 Table 3 The result of XML data si ilar ity test 记录大小 最终距离(pso/wpso) 迭代次数(pso/wps) 花费时间(pso/wpso)/s 52 932479/948851 5029/2803 932479/27.2749 143 3629409/3633528 3729/1356 380556/15.3254 297 6554254/655.8966 3564/976 509508/15.3275 578 10821/10800 1447/289 507136/300117 1573 3180.9/31803 2293/521 1520110/523560 从实验结果可知由于WPSO主要针对ML多 1001 维数据进行投影操作，对比一般优化的P9O算法， 90 80 南…粒子清洗 在最终距离相近情况下，其迭代次数与时间花费却 200 600 1000 1400 至少降低一倍以上，而且随着数据量的加大，效果越 记录/个 98 明显 96 规则清 423不同清洗策略对比实验 一粒字清洗 200 600 1000 1400 为了更好的对比ML数据清洗算法，本文特与 记求/个 500 文献[1516提出的规则清洗与聚类清洗算法在相 规则清洗 同条件下进行对比实验，为了达到更好的清洗效果， ……子清洗 针对不同数据规模加入不同噪音的测试数据，对应 200 600 1000 1400 记录/个 秩序是规则清洗、聚类清洗与粒子清洗，实验结果如 图6ML相似重复数据清洗对比图 表4、图6所示.其对应的平均准确率是94%，905%、 Fig 6 The result of XML si ilarity data cleaning 表4ML相似重复数据清洗实验结果 Table 4 The result of XML sin iar ity da ta clean ng 记录规模 重复记录 检测结果 正确检测 准确率/% 查全率/% 时间/s 52 20 20119/20 19/18/19 100/95/100 95/95/95 37.2/3871/29.5 297 130 127/123/129 123/121/124 98/95199 97198/96 1955/2073/914 578 359 350/346/352 335/336/345 97/96198 96/97198 2528/2473/1715 1573 539 434/410/481 423/401/472 81/76/89 97198/98 4382/4337/259.6 1994-2008 China Academic Journal Electronic Publishing House.All rights reserved. http://www.cnki.net
可夫模型提取 XML数据 ,根据 XML数据规模统计 准确提取的数据及花费时间. 4. 2. 2W PSO与 PSO对 XML数据的检测能力 为了检测各算法对 XML数据的检测能力 ,以表 1提取的数据为基础投影到二维平面上 ,针对不同 数据规模进行测试 ,实验结果如表 3所示. 表 1 实验中使用的数据子集 Table 1 Da ta subsets used in the exper im en t 2006 (ACM - 1) 2005 (ACM - 2) 2002 (ACM - 3) 1999 (ACM - 4) XML键个数 IndexTermsPage 0 0 0 920 13 O rdinaryIssuePage 45 45 30 51 9 ProceedingsPage 16 16 17 17 14 SigmodRecord 3 3 1 1 6 表 2 提取不同规模的 XML数据及花费时间 Table 2 Pick ing up d ifferen t bulk of XML da ta and correspond ing tim e 记录大小 文档数 有数记录数 花费时间 /s 52 2 51 1. 195 8 143 7 137 5. 795 3 297 13 279 19. 551 6 578 22 527 49. 059 7 1 572 36 1 409 121. 438 4 表 3 XML数据相似性实验 Table 3 The result of XML da ta sim ilar ity test 记录大小 最终距离 (p so /wp so) 迭代次数 (p so /wp so) 花费时间 (p so /wp so) /s 52 93. 247 9 /94. 885 1 5 029 /2 803 93. 247 9 /27. 274 9 143 362. 940 9 /363. 352 8 3 729 /1 356 38. 055 6 /15. 325 4 297 655. 425 4 /655. 896 6 3 564 /976 50. 950 8 /15. 327 5 578 1 082. 1 /1 080. 0 1 447 /289 50. 713 6 /30. 011 7 1 573 3 180. 9 /3 180. 3 2 293 /521 152. 011 0 /52. 356 0 从实验结果可知由于 W PSO主要针对 XML多 维数据进行投影操作 ,对比一般优化的 PSO 算法 , 在最终距离相近情况下 ,其迭代次数与时间花费却 至少降低一倍以上 ,而且随着数据量的加大 ,效果越 明显. 4. 2. 3 不同清洗策略对比实验 为了更好的对比 XML数据清洗算法 ,本文特与 文献 [ 15216 ]提出的规则清洗与聚类清洗算法在相 同条件下进行对比实验 ,为了达到更好的清洗效果 , 针对不同数据规模加入不同噪音的测试数据 ,对应 秩序是规则清洗、聚类清洗与粒子清洗 ,实验结果如 表 4、图 6所示. 其对应的平均准确率是 94% , 90. 5%、 图 6 XML相似重复数据清洗对比图 Fig. 6 The result of XML similarity data cleaning 表 4 XML相似重复数据清洗实验结果 Table 4 The result of XML sim ilar ity da ta clean ing 记录规模 重复记录 检测结果 正确检测 准确率 /% 查全率 /% 时间 /s 52 20 20 /19 /20 19 /18 /19 100 /95 /100 95 /95 /95 37. 2 /38. 7 /29. 5 297 130 127 /123 /129 123 /121 /124 98 /95 /99 97 /98 /96 195. 5 /207. 3 /91. 4 578 359 350 /346 /352 335 /336 /345 97 /96 /98 96 /97 /98 252. 8 /247. 3 /171. 5 1 573 539 434 /410 /481 423 /401 /472 81 /76 /89 97 /98 /98 438. 2 /433. 7 /259. 6 · 232 · 智 能 系 统 学 报 第 3卷
第3期 刘波，等：融合粒子群算法改进ML数据智能清洗策略 ·233· 965%,平均查全率是9625%、97%、9675%，平均 mantic and hierarchical siilarity measures[J ]Knowledge- 节省时间率是326%、245%、9429%，由此可知本 Based System s.2007,20(6):336-349 文算法的主要优势，随着记录规模的扩大，其时间性 [9]R IERA L J,SALAZAR G J.A branch-and-cut algorithm for the continuous error bcalization problem in data cleaning 能上表现更明显」 [J ]Computers Operatons Research,2007,34 (9): 5结束语 2790-2804 [10]R IERA L J,SALAZAR G J.A heuristic approach for the 本文基于ML键提出ML数据清理新方法， continuous error localization problem in data cleaning[J]. 利用多模板的隐马尔可夫模型抽取ML数据构成 Computers Operations Research,2007,34 (8):2370- 2383 动态知识库，结合波函数优化粒子群算法，简化 [11 ]LEE C S Diagnostic,predictive and compositional model- ML数据相似性判断过程，特别是对ML数据进 ing with data m ining in integrated leaming envirorments 行向量化，有效地避开了粒子群算法的维度灾问题， [J ]Computers Education,2007,49(3):562-580. 有利数据并行比较，简化计算量，在并行处理与时间 [12 Sigmod Signod Record EB /OL ][2007-05-29]ht //www.sigmod org/record/xmI/index xml 性能上有较大的改善，也为ML数据清理的研究提 [13]GEMELLO R,MANA F,SCANZD S,et al Linear hid- 供一些借鉴 den trans-omations for adaptation of hybrid ANN /HMM models[J].Speech Communication,2007,49 (10):827- 参考文献： 835. [1 ]R IERA L J,SALAZAR G J.A branch-and-cut algorithm or [14]CHAR IIOS T,WAAL P R,GAAGL C Convergence in the continuous error bcalization problem in data cleaning Markovian models with mplications or efficiency of infer [J ]Computers Operations Research,2007,34 (9): ence[J]Intematonal Joumal of Approxmate Reasoning. 2790-2804 2007,46(2):300-319 [2]ZHAO Q K,CHEN L,BHOWM CCK S S,etal XML struc- [15叶舟，王东.基于规则引擎的数据清洗[J计算机 tural delta m ining issues and challenges [J ]Data 工程，2006,32(23)：52-55 Knowledge Engineering,2006,59(3):652-680 YE Zhou,WANG Dong Rules engine based data cleans- [3郭志懋，周傲英.数据质量和数据清洗研究综述[J小软 ing[J]Computer Engineering,2006,32(23):52-55. 件学报，2002,13(11)：20762083 [16冯玉才，桂浩，李华，等.数据分析和清理中相关算 GO Zhmao,ZHOU Aoying Research on data quality and 法研究[J].小型微型计算机系统，2005,26(6)：1018- data cleaning a survey J Joumal of Sofware,2002,13 1022 (11):2076-2083. FENG Yucai,G IHao,LIHua,et al Research on relat- 「4掷仕辉，周傲英，张龙.ML文档的相似测度和结构索 ed algoritms in data analysing and cleaning[J ]Joumal of 引研究[J]计算机学报，2003,26(9)：1116-1123 Chinese Computer Systems,2005,26(6):1018-1022 ZHENG Shihui,ZHOU Aoying,ZHANG Long Sim ilarity 作者简介： measure and structural index of XML documents [J].Jour 刘波，男，1969年生，博士研究 nal of Computer,,2003,26(9):1116-1123. 生，主要研究方向为软件工程与数据库 [5陈伟，丁秋林.一种ML相似重复数据的清理方法研 技术 究[J]北京航空航天大学学报，2004,30(9)：835-838 CHEN Wei,DNGQ iulin Study on an XML app roxmately dup licated data cleaning method[J].Joumal of Beijing Uni- versity ofAeronautics and A stronautics.2004.30(9):835- 838 杨路明，男，1947年生，教授，博士 [6陆凤霞，王静秋，王宁生.一种开放式数据清理框架[J] 生导师，主要研究方向为信息系统与数 南京航空航天大学学报，2006,38(4)：459-463 据库技术，发表学术论文40余篇。 LU Fengxia,WANG Jingqiu,WANG Ningsheng Open da- ta cleaning frame [J ]Joumal of Nanjing University of Aeronautics and A stronautics,2006,38(4):459-463. [7正桐，刘大昕.一种基于改进粒子群优化的ML结构 聚类方法[J]小型微型计算机系统，2007,28(5)：871- 邓云龙，男，1962年生，教授，博士 生导师，博士，主要研究方向为软件心 875 WANG Tong,L U Daxin XML structural clustering based 理学.获得科研教学成果多项发表学 on the mproved particle sam optm ization [J]Joumal of 术论文50余篇 Chinese Computer System s,2007,28(5):871-875. [8 ]NA YAK R,RYAD IW.XML schema clustering with se- 1994-2008 China Academic Journal Electronic Publishing House.All rights reserved.http://www.cnki.net
96. 5% ,平均查全率是 96. 25%、97%、96. 75% ,平均 节省时间率是 3. 26%、2. 45%、94. 29% ,由此可知本 文算法的主要优势 ,随着记录规模的扩大 ,其时间性 能上表现更明显. 5 结束语 本文基于 XML键提出 XML数据清理新方法 , 利用多模板的隐马尔可夫模型抽取 XML数据构成 动态知识库 ,结合波函数优化粒子群算法 ,简化 XML数据相似性判断过程 ,特别是对 XML 数据进 行向量化 ,有效地避开了粒子群算法的维度灾问题 , 有利数据并行比较 ,简化计算量 ,在并行处理与时间 性能上有较大的改善 ,也为 XML数据清理的研究提 供一些借鉴. 参考文献 : [ 1 ]R IERA L J, SALAZAR G J. A branch2and2cut algorithm for the continuous error localization p roblem in data cleaning [J ]. Computers & Operations Research, 2007, 34 ( 9 ) : 279022804. [ 2 ] ZHAO Q K, CHEN L, BHOWM ICK S S, et al. XML struc2 tural delta mining: issues and challenges [ J ]. Data & Knowledge Engineering, 2006, 59 (3) : 6522680. [ 3 ]郭志懋 ,周傲英. 数据质量和数据清洗研究综述 [J ]. 软 件学报 , 2002, 13 (11) : 207622083. GUO Zhimao, ZHOU Aoying. Research on data quality and data cleaning: a survey [ J ]. Journal of Software, 2002, 13 (11) : 207622083. [ 4 ]郑仕辉 ,周傲英 ,张 龙. XML文档的相似测度和结构索 引研究 [J ]. 计算机学报 , 2003, 26 (9) : 111621123. ZHENG Shihui, ZHOU Aoying, ZHANG Long. Sim ilarity measure and structural index of XML documents [J ]. Jour2 nal of Computer, 2003, 26 (9) : 111621123. [ 5 ]陈 伟 ,丁秋林. 一种 XML相似重复数据的清理方法研 究 [J ]. 北京航空航天大学学报 , 2004, 30 (9) : 8352838. CHEN W ei, D ING Q iulin. Study on an XML app roximately dup licated data cleaning method[J ]. Journal of Beijing Uni2 versity ofAeronautics and A stronautics, 2004, 30 (9) : 8352 838. [ 6 ]陆凤霞 ,王静秋 ,王宁生. 一种开放式数据清理框架 [J ]. 南京航空航天大学学报 , 2006, 38 (4) : 4592463. LU Fengxia, WANG Jingqiu, WANG N ingsheng. Open da2 ta cleaning frame [ J ]. Journal of Nanjing University of Aeronautics and A stronautics, 2006, 38 (4) : 4592463. [ 7 ]王 桐 ,刘大昕. 一种基于改进粒子群优化的 XML结构 聚类方法 [J ]. 小型微型计算机系统 , 2007, 28 ( 5) : 8712 875. WANG Tong, L IU Daxin. XML structural clustering based on the imp roved particle swarm op tim ization [J ]. Journal of Chinese Computer Systems, 2007, 28 (5) : 8712875. [ 8 ]NAYAK R, IRYAD IW. XML schema clustering with se2 mantic and hierarchical similarity measures[J ]. Knowledge2 Based System s, 2007, 20 (6) : 3362349. [ 9 ]R IERA L J, SALAZAR G J. A branch2and2cut algorithm for the continuous error localization p roblem in data cleaning [J ]. Computers & Operations Research, 2007, 34 ( 9 ) : 279022804. [ 10 ]R IERA L J, SALAZAR G J. A heuristic app roach for the continuous error localization p roblem in data cleaning[J ]. Computers & Operations Research, 2007, 34 ( 8 ) : 23702 2383. [ 11 ]LEE C S. D iagnostic, p redictive and compositionalmodel2 ing with data mining in integrated learning environments [J ]. Computers & Education, 2007, 49 (3) : 5622580. [ 12 ] Sigmod. Sigmod Record [ EB /OL ]. [ 2007205229 ]. ht2 tp: / /www. sigmod. org/ record /xm l/ index. xml. [ 13 ] GEMELLO R, MANA F, SCANZIO S, et al. L inear hid2 den trans2 formations for adap tation of hybrid ANN /HMM models[J ]. Speech Communication, 2007, 49 (10) : 8272 835. [ 14 ]CHAR ITOS T, WAAL P R, GAAG L C. Convergence in Markovian models with imp lications for efficiency of infer2 ence[J ]. International Journal of App roximate Reasoning, 2007, 46 (2) : 3002319. [ 15 ]叶 舟 ,王 东. 基于规则引擎的数据清洗 [J ]. 计算机 工程 , 2006, 32 (23) : 52255. YE Zhou, WANG Dong. Rules engine based data cleans2 ing[J ]. Computer Engineering, 2006, 32 (23) : 52255. [ 16 ]冯玉才 ,桂 浩 ,李 华 ,等. 数据分析和清理中相关算 法研究 [J ]. 小型微型计算机系统 , 2005, 26 ( 6) : 10182 1022. FENG Yucai, GU IHao, L IHua, et al. Research on relat2 ed algorithm s in data analysing and cleaning[J ]. Journal of Chinese Computer Systems, 2005, 26 (6) : 101821022. 作者简介 : 刘 波 ,男 , 1969年生 ,博士研究 生 ,主要研究方向为软件工程与数据库 技术. 杨路明 ,男 , 1947年生 ,教授 ,博士 生导师 ,主要研究方向为信息系统与数 据库技术 ,发表学术论文 40余篇. 332 · 邓云龙 ,男 , 1962年生 ,教授 ,博士 生导师 ,博士 ,主要研究方向为软件心 理学. 获得科研教学成果多项.发表学 术论文 50余篇. 第 3期 刘 波 ,等 :融合粒子群算法改进 XML数据智能清洗策略 ·
