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