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