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