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