第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卷