马尔可夫及隐马尔可夫模型在数据挖掘中的应用

马尔可夫及隐马尔可夫模型在数据挖掘中的应用

摘要: 随着用户对于数据挖掘的精确度与准确度要求的日益提高, 马尔可夫模型与隐马尔可夫模型被广泛用于数据挖掘领域。本文 阐述了马尔可夫模型和隐马尔可夫模型数据挖掘领域的应用, 以及隐马尔可夫模型可解决的问题, 以供其他研究者借鉴。

1 引言

当前Internet 与数据库的高速发展, 信息以海量增长, 对于越来越多的数据, 如何寻找有用的信息是人们所关心的问题, 也是数

据挖掘的任务。数据挖掘( Data Mining, DM), 又称数据库中的知识发现(Knowledge Discovery in Database,KDD), 是从90 年代初兴起 的一门数据库技术。数据挖掘就是从大量的、不完全的、有噪声的、模糊的、随机的实际应用数据中, 提取隐含在其中的、人们事先不 知道的、但又是潜在有用的信息和知识的过程。数据挖掘是多学科交叉的产物, 结合了数据库、人工智能、统计学、机器学习、可视化 等技术, 通过发现有用的新规律和新概念, 提高了数据拥有者对大量原始数据的深层次理解、认识和应用, 解决了―数据丰富, 知识 贫乏‖的问题, 具有广泛的应用前景。

数据挖掘能从大量数据中抽取出隐藏在数据之中的有用信息, 从而为决策者进行决策提供重要的依据, 大大提高决策的科学

性和减小决策的盲目性也可以帮助商业管理者更好地理解用户的行为, 制订相应的用户服务政策, 从而增加商业机会。例如电信公 司通过发现用户通话的规律, 制定更合理的优惠政策。随着用户对于挖掘数据的精度与准确度要求的提高, 大量数据挖掘算法涌

现。其中, 数学模型—马尔可夫模型与隐马尔可夫模型应用在许多挖掘领域, 如: 语音识别、自动文本抽取、数据流分类等, 取得了较 好的挖掘效果。

2 马尔可夫模型及隐马尔可夫模型简介

马尔可夫模型(Markov Models, MM) 可来描述为: 如果一个系统有N 个状态, S1,S2, ⋯⋯, Sn , 随着时间的推移, 该系统从某一状 态转移到另一状态, 系统在时间t 的状态记为qt。系统在时间t 处于状态sj( 1≤j≤N) 的概率取决于其在时间1, 2, ⋯⋯, t- 1 的状态, 该概率为: p( qt=sj|qt- 1=si, qt- 2=sk, ⋯⋯)。

若系统在时间t 的状态只与其在时间t- 1 的状态相关, 则该系统构成一个离散的一阶马尔柯夫链( 时间与状态都是离散的) 又 称为齐次马氏链, 即:

p(qt= sj|qt- 1=si, qt- 2=sk, ⋯⋯)=p( qt=sj|qt- 1=si) ( 1)

若( 1) 式是独立于时间t 的随机过程, 即状态于时间无关, 则称为马尔可夫过程。

用Pij(t)表示, 在任一时刻s, qs 从状态i 经过时间t 转移到状态j 的概率。Pij(t)表示其转移概率。则可通过其转移矩阵来求其n 步 转移矩阵, 令p=p(1)=Pij(t) ,则其n 步转移矩阵为p(n)=pn。若初始状态的概率分布P"(0), 则可以求得其n 步的概率分布: P"(n) =P"(0)p(n)。

隐马尔可夫模型(Hidden Markov Models, HMM) 是一个双重随机过程, 具体的状态序列不可知, 只知其状态转移的概率, 即模型 的状态转换过程是不可观察的( 隐蔽的) , 而可观察的事件的随机过程是隐蔽的状态转换过程的随机函数。也就是说: ( 1)HMM的状 态是不确定或不可见的, 只有通过观测序列的随机过程才能表现出来。( 2) 观察到的事件与状态并不是一一对应, 而是通过一组概 率分布相联系。( 3)HMM是一个双重随机过程, 两个组成部分: ①马尔可夫链: 描述状态的转移, 用转移概率描述。②一般随机过程: 描述状态与观察序列间的关系, 用观察值概率描述。隐马尔可夫模型可以用图1 表示, 其参数的含义见图2。假设λ=(π,A,B) , 则可以根据前向算法( The forward procedure) 或后向算法( The backward procedure) 来求P(O|λ)。根据Viterbi 搜

索算法可以解决如何选择一个对应的状态序列s=q1,q2,...qt, 使得s 能够最为合理的解释观察序列O 的问题。

3 马尔可夫模型与隐马尔可夫模型在数据挖掘中的应用

马尔可夫模型是一种预测模型, 广泛的应用于商业预测以及隐含概念漂移的数据流分类中。其在商业预测中为决策者进行决

策提供重要的依据, 提高了决策的科学性, 减少了决策的盲目性; 其用于隐含概念漂移的数据流分类中, 在保证分类准确度的基础 上提高了分类的时间性能。

隐马尔可夫模型是一种应用非常广泛的统计模型,最早是从语音识别问题中发展起来的。七十年代, Fred Jelinek (贾里尼克) 和

卡内基·梅隆大学的Jim and Janet Baker (贝克夫妇) 分别独立地提出用隐含马尔可夫模型来识别语音, 语音识别的错误率相比人工 智能和模式匹配等方法降低了三倍(从30%下降到10%)。八十年代李开复博士坚持采用隐含马尔可夫模型的框架, 成功地开发了世 界上第一个大词汇量连续语音识别系统Sphinx。目前HMM已广泛用于文本信息抽取以及用户兴趣漂移研究中。

3.1 马尔可夫模型在商业预测中的应用

马尔可夫模型多被用于产品的市场占有率预测中[1], 如马尔可夫模型可解决商业群体分析的问题[2], 商业群体中客户可分成VIP 客户、主要客户、普通客户和小客户, 由于不同的客户群体中的客户因为某种原因向其他的客户群体转移, 普通客户可以转移到小

客户, 小客户也可转移成为普通客户, 因而客户群体的分布会发生变化。根据帕累托80/20 法则, 客户群体的变化会直接影响公司的 效益。通过建立相应的马尔可夫模型对客户群体组分类进行预测, 可为企业制定相应的市场策略提供依据。对数据库中数据的分析 可得到各种客户类型初始状态的分布P!(0), 对于一客户群体中的客户向另外一客户群体转移的概率p(n), 可以通过对公司历史交易 数据库进行挖掘得到。这样就可以得到下一个状态的分布P!(1)=P!(0)p(n) 。这样公司就可以根据下一阶段客户群体的可能的分布状态 来调整市场策略。

3.2 马尔可夫模型在隐含概念漂移的数据流分类中的应用

RePro 算法[8]的目标是: (1)利用原始数据组织的历史概念来判别新的概念是否是历史概念的重现。(2)从概念的历史记录中学习 概念转移的规律。(3)实现预测每一个即将来临的概念并用来预测将到来的待分类的样本所属的类。为实现其目标, RePro 算法用马 尔可夫链表示概念的历史进程, 每一个不同的概念就是马尔可夫链的一种状态, 不同概念间的变化可以用概念转移矩阵表示, 每当 出现一个新的概念, 就增加矩阵的行列。假设随着时间的推移, 利用概念等价度量得到一系列历史概念集C_DIS, 利用Proactive 算 法得到互异概念集C_SEQ, 和概念转移矩阵C_TRA。RePro 算法设定一个可能的阈值。一个分类精确度阈值

当一个目标样本窗口I_WIN 到来时, RePro 算法将预测出将用来分类的概念Cnext。Clast 表示C_SEQ 中最近的稳定概念, 依照概念转

移矩阵找出转移概率比thresholdprob 高的并用Cnext(s)表示。如果不止一个Cnext(s)存在, 则对于每一个Cnext(s)计算它在I_WIN 中的分类

精度, 找出分类精度最高的一个。如果不存在Cnext(s), 则计算C_DIS 上的每一个概念在I_WIN 上的分类精度, Cnext 用来表示分类精度

最高的一个。如果Cnext 在I_WIN 上的分类精度比thresholdaccu 低, 则从I_WIN 窗口中学习新的概念并用Cnext 表示。 RePro 算法利用马尔可夫链构造历史概念序列, 并充分利用概念转移矩阵对可能出现的概念进行预测, 提高了分类的时间性能 和分类准确度。

1187

数据库与信息管理本栏目责任编辑：闻翔军

3.3 HMM 在文本信息抽取中的应用

利用HMM 进行信息抽取是一种基于机器学习的信息抽取方法, 它因易于建立、适应性强、抽取精度高的优点而日益受到研究

者的关注。McCallum 提出―收缩(shrinkage)‖技术来改进HMM信息抽取模型概率的估计[6]。钟敏娟等提出了基于多模板隐马尔可夫 模型的文本信息抽取算法[5](MT- HMM)。该算法中HMM被看作成一个五元组{S,T,A,B,Π}。其中S 是状态集, 模型共有N 个状态; V 是 词汇集, 模型共有M个可能的输出单词; A 是N×N 的状态转移矩阵, aij 是从状态si 转换到状态sj 的概率; B 是N×M的释放概率矩 阵, bi(Vk)是在状态bj 时释放单词Vk 的概率; П是初始状态概率集合,πi 是第i 个状态作为初始状态的概率。

采用Maximum Likelihood(ML) 算法, 建立HMM模型, ML 算法主要以统计的方法得出HMM模型参数, 由以下3 个公式分别计

算模型的初始状态概率、转移状态概率和状态释放概率,其中, Init(i)是所有训练序列中, 初始状态为i 的序列个数, Cij 是所有训练序列中, 从状态Si 转换到状态Sj 的次数。

其中, Ej(Vk)是所有训练序列中, 状态Sj 释放单词Vk 的次数。

MT- HMM算法分3 个步骤:

( 1) 基于马尔可夫链模型, 聚类训练数据为几个类;

( 2) 对每一类训练数据, 分别利用公式(1)- (3)训练一个初始概率矩阵П和一个转移概率矩阵A 以及状态释放概率B;

( 3) 使用训练好的模型抽取信息时, 结合每一个初始概率矩阵、每一个转移概率矩阵和统一的释放概率矩阵, 使用Viterbi 算法 来找出最优的标记序列。从这些最优标记序列中选择一个概率最大的序列作为最终标记序列。

该算法对训练数据形式聚类, 分多个形式模板训练隐马尔可夫初始概率及转移概率参数, 同时结合统一训练的释放概率参数

对文本信息进行抽取, 一定情况下提高了信息抽取的精确度和召回率。

3.4 HMM 在处理用户兴趣漂移上的应用

文献[7]中指出, 用户兴趣度的漂移, 可类比概念漂移的模式, 即用概念漂移来模拟兴趣漂移。用户的兴趣是隐含的内容, 用户的

行为( 或通过行为挖掘到的用户的兴趣) 是外在可见目标概念, 当用户的兴趣( 隐含内容) 发生改变后, 用户的行为也会发生改变, 这 是兴趣漂移的过程。可采用一定的漂移算法综合当前用户的兴趣和新发掘的用户的行为(或兴趣), 计算得到用户真正的兴趣变化。 对于一个假设状态集合Q, 具有指定的初始状态qt 和最终状态qf, 那么对于一个状态转移集, 每个元素为(q→q′), 一个离散的输

出符号集: Σ=σ1,σ2...σm。从初始状态开始, 转移到一个新的状态, 观测到一个输出符号, 如此反复, 直到最终状态, 于是就产生一个符 号串: X=x1,x2⋯xm。每一个转移存在着一个转移概率P( q→q′) 在一个状态观测到一个特殊符号的概率为P(σ|q)。那么在一个隐马尔 可夫模型M上一个串X 被观测的概率为在所有可能路径上求概率和。

通过对用户对web 页面的操作( 打印页面, 页面另存, 添加收藏, 点击链接等) , 以及服务器日志记录的挖掘。可以得到所需要的 数据, 然后利用HMM进行求解, 得到用户可能的兴趣漂移。该方法不仅能够准确跟踪用户的兴趣, 还可以预测用户的兴趣, 可以帮 助Web 站点的设计者理解用户的偏好, 以改进站点的设计。

4 结束语

通过对马尔可夫模型及隐马尔可夫模型的分析, 及其应用的研究, 可知马尔可夫模型可以解决分类预测等问题, 而HMM可解

决如下三种问题:

( 1) 给定观察序列O=O1,O2,⋯OT,以及模型λ=(A, B, π) ,如何计算P(O|λ);

( 2) 给定观察序列O=O1,O2,⋯OT 以及模型λ, 如何选择一个对应的状态序列S = q1,q2,⋯qT, 使得S 能够最为合理的解释观察序列O; ( 3) 如何调整模型参数λ=(A, B, π) , 使得P(O|λ)最大。

问题1 可利用前向算法和后向算法解决; 问题2 可用Viterbi 搜索算法解决; 问题3 的解决较为复杂, 可利用前向后向算法

(Baum-Welch or forward- backward procedure)算法解决。

合理的利用马尔可夫或隐马尔可夫模型, 可提高数据挖掘的精确度以及时间性能, 因而其在数据挖掘领域有着广阔的应用前景。 参考文献:

[1] 陈涛.正在走向实用的数据挖掘技术[J].电脑知识与技术,2007,(4):19- 20.

[2] 张捷,琚春华.基于马尔可夫过程模型的商业客户群体分析[J].计算机时代.2006,(1):34- 35.

( 下转第1197 页)

1188

本栏目责任编辑：闻翔军数据库与信息管理

( 上接第1188 页)

[3] 杜雪樵,惠军.随机过程[M].合肥工业大学出版社,2006.30- 70.

[4] 刘次华. 随机过程[M].华中科技大学出版社,2005.42- 83.

[5] 钟敏娟,郝谦,刘云中.基于多模板隐马尔可夫模型的文本信息抽取算法[J].计算机工程,2006,(1):203- 205.

[6] Frietag D,McCallum A.Information extraction with HMMS and shrinkage [C].Procee - dings of the AAAI’99 Workshop on Machine Learning for Information Extraction,1999:31- 36.

[7] 张勉.基于隐马尔可夫模型的用户兴趣漂移模式发现方法[J].北京建筑工程学院学报.2005,(9):50- 52.

[8] Yang Ying, Wu Xindong, Zhu Xingquan.Combining proactive and reactive predictions for data streams [J]. In SIGKDD,

2005,(8):710–

715.

[9] 王实,高文,李锦涛,黄铁军.基于隐马尔可夫模型的兴趣迁移模式发现[J].计算机学报,2001,(2):152- 157.

mr:=:new.mr; jm:=:new.jm;

mr=mr+jm

end if,

end ;

图2 大额资金收受表和举报单

4 结论

在文中, 我们通过几个实例集中讨论了oracle 触发器的在大中型网站设计中的用途, 说明了触发器应用于支持企业级或者商业 级解决方案时,它是一个功能十分强大的工具。除了本文所述触发器在行政纪监系统中的应用之外, 用户还可以通过使用触发器做 到强制数据一致性, 提供审计和日志记录, 防止无效的事务处理, 启用复杂的业务逻辑等。

值得注意的一点是, 过多地使用触发器会降低整个数据库的性能, 特别是触发器写得不好, 更是破坏数据库的运行, 因此适当

的使用触发器显得很重要。

参考文献:

[1] Thomas Kyte Oracle 9i & 10g 编程艺术:深入数据库体系结构[M].北京:人民邮电出版社,2006.

[2] 盖国强.深入浅出Oracle- - DBA 入门、进阶与诊断案例[M].北京:人民邮电出版社,2006.

[3] 袁福庆.Oracle 数据库管理与维护手册[M].北京:人民邮电出版社,2006.

[4] 李华飚等.精通Java 中间件编程[M].北京:中国水利水电出版社,2003.

[5] 孙一林等.Java 数据库编程实例[M].北京:清华大学出版社,2003.

[6] 陈吉平.构建ORACLE 高可用环境:企业级高可用数据库架构、实战与经验总结(ITPUB 版主作品) [M].电子工业出版社,2008.

[7] SAMR.ALAPATI.现代数据库管理( 原书第6 版) [M].北京:人民邮电出版社,2007.

[8] 盖国强,循序渐进ORACLE- - 数据库管理、优化与备份恢复[M].北京:人民邮电出版社,2007.

1197

基于隐马尔可夫模型的多重序列分析

X

罗泽举1 , 朱思铭1 , 何 淼2

(1. 中山大学数学与计算机科学学院, 广东广州510275 ;

2. 中山大学生命科学学院, 广东广州510275)

摘 要: 隐马尔可夫模型是最近几年在许多机器学习领域都得到成功应用的关于序列分析的重要统计模型, 特

别是在蛋白质家族的识别方面。这主要是由于生物数据的急剧增长导致2 个领域(计算科学和生物学) 走向结

合引起的。探讨了多重序列比对和序列谱隐马尔可夫模型, 讨论了隐马尔可夫模型的基本算法以及如何建立

HMMs。根据E 值和训练分数进行蛋白质家族的识别和分类。

关键词: 隐马尔可夫模型; 多重序列比对; 蛋白质家族的分类

中图分类号: O211162 文献标识码: A 文章编号: 052926579 (2005) 0220009205

1 研究背景

隐马尔可夫模型是最近几年在许多机器学习领域都得到成功应用的关于序列分析的重要统计模型, 特别是在蛋白质家族的识别方面。多重序列分析是寻找整个基因家族的共同特征的重要方法, 通过多重序列比对, 发现它们特征序列, 某个家族成员进化可以看成是由特征序列经过若干年代一系列的插入、替代、删除的结果。多重序列分析是一个非常困难的问题, 涉及许多模型的选择, Carillo 和Lipman 引入了基于两两最优化比对分数和的多重序列比对方法, 并得到了广泛应用; 但是这种方法对于计算时间和空间的耗费极大, 被证明是NP 难题[1 ] 。许多研究者利用启发式和近似算法改进了比对分数算法[2 ] , 包括Feng 和Doolittle 的Clustal[3 ] ,Thompson 等[4 ] 著名的多重序列数据库分析的CLUSTALW和新近的基于隐马尔可夫的算法。隐马尔可夫理论最初是由Baum 及他的同事[5 ]于20 世纪60 年代末70 年代初提出, 并最早用于语音识别[6 - 8 ] 。隐马尔可夫模型最早用于计算生物学是于80 年代末90 年代初, 目前已经用于DNA 模型构建, 蛋白质二级结构预测, 基因预测, 横跨膜蛋白识别, 其中最为普遍的应用是Krogh 等[9 ] 基于profile 家族共同特征提取的蛋白质序列分析。隐马尔可夫之所以在生物序列分析中得到普遍应用是因为它正好模拟了生物基因的突变、插入、缺失、匹配过程。 2 多重序列比对

211 多重序列比对的描述

一个多重序列比对可以看成是三元组Ω =(Σ,S ,A) ,其中Σ 是字母表的集合, 若对DNA 或RNA , Σ = {A , T , G, C , —} 或Σ = {A , U ,G,

C ,—} (其中― —‖表示空位或删除态) ; 若是针对蛋白质, Σ 是20 种氨基酸字母和― —‖的集合, 即Σ = { G, A , L , M, F , W, K, S , N ,D , P , V , I , C , Y, H , R , T , Q , E , —} ; S ={ S1 , S2 , ⋯, Sk } 是比对序列的集合, 其中Si ( i= 1 ,2 , ⋯, k) 是以集合的形式代表一条序列, 例如S1 = {A , A , G, G, C , T , T , A} , 代表序列AAGGCTTA , 比对时, 一般取每条序列长度相等,但也可以不等; A = ( aij ) 是一个比对矩阵, 其元素是Σ 中的元素; 如图1 是有3 个序列的比对,图中每条序列的长度相等。S1 : Y E G V A — — TS2 : Y E G — A T — AS3 : F E G — C — V A图1 一个有3 条序列的多重序列比对Fig11 A multiple alignment of three strings由于基于比对和分数的多重序列计算是NP 难题, 用线性罚分的优化比对和分数计算方法, 对k个序列, 每个序列的长度长为n , 则计算时间和空间耗费将分别是O (2k·nk ) 和O ( nk ) , 若k 和n 较X

大, 将超出计算机容量。因此必须改进比对的计算方法。算法的改进要考虑到2 个问题: ①采用什么标准和用什么样的计分函数来计算多重序列比对? ②如何计算其最优化分数? Feng 和Doolittle 的Clustal ,Thompson 等利用启发式和近似算法改进了比对分数算法, 著名多重序列数据库分析工具ClustalW也是这类方法的典型代表; 另一个重要的问题是一个多

重序列比对首先考虑的是一个家族的进化关系, 但上述算法却忽略了这个重要事实, 故若能将进行多重序列比对的各序列具有进化上的

相关关系引入比对分数计算, 是不是可以大大改进计算时间和空间的耗费呢? 隐马尔可夫方法正是利用了这个思想,它利用特征序列(或叫一致序列) 的概念, 将多重序列比对建立在进化关系这一思想下, 使算法得到大大改进, 计算时间和空间都大为减少, 且算法收敛速度快。

212 特征序列

一个多重序列的特征序列是最能描绘这个多重序列的共同本质的序列, 虽然目前还没有关于特征序列的统一定义, 但可以用子序列

(Subsequence)方法, 从多重序列比对中找出每列元素中出现字符最多的元素来定义, 例如图1 的S1 , S2 , S3 的特征序列是YEGAA。定义特征序列的意义至少有3点: ①可以对一个序列进行数据库搜索, 以寻找它的所在家族; ②可以比较不同家族的进化关系; ③它是构建隐马尔可夫模型等的理论基础。

3 隐马尔可夫模型

311 隐马尔可夫模型的生物学背景

现代某类生物的基因组可以认为是某个祖先基因组经过若干代的进化而来的, 和我们研究基因组序列的相似性是为了讨论生物的同源性一样, 生物的特征序列正代表着某个祖先基因, 这个祖先基因经过插入、删除和匹配而不断进化, 最终衍变为一个基因家族, 这个过程正好可以用如下模型来描述。模型用3 个状态来描述, 分别称为删除态、插入态、匹配态, 图中分别用圆形、菱形及正方形表示。基因的进化就可以认为是这3 个状态之间的随机转移的结果。删除态代表基因序列中的空位和缺失, 插入态代表基因的突变, 匹配态代表某个特征序列。为了简化起见, 假设原始祖先序列是CC ,开始以某种转移概率插入了一个碱基A , 再以某随机概率转移到匹配态C , 再随机转移到匹配态C ,

图2 隐马尔可夫的描述圆形为删除态, 菱形为插入态, 正方形为匹配态再进入一个删除态, 最后转入插入态, 插入碱基Y, 从而由特征序列CC 最终形成了序列ACCY。当然这只是进化的一种途径, 由模型还可以形成其它许多序列, 理论上讲, 形成的路径可以有无数多条, 因为有无穷多种插入的可能。

312 隐马尔可夫模型的定义

定义 一个模型λ = ( S ,Σ,A ,B ,π) 称为隐马尔可夫模型, 其中:( 1 ) S = { S1 , S2 , ⋯, SN } 为状态集合,N = | S | 是状态个数;

(2) Σ = { O1 ,O2 , ⋯,OM } 是观察符号或观察向量的集合,M = | Σ| 是观察符号或观察向量的个数;

(3) A = ( aij ) 为状态转移概率矩阵,其元素aij表示从状态Si 转移到状态Sj 的转移概率, 有aij = P( qt+1 = Sj | qt = Si ) ,1 ≤ i , j ≤N (1)满足aij ≥0 , ΣNj = 1aij = 1 ;1 ≤ i , j ≤N (2)

(4) B = ( bj ( k) ) 表示在状态Sj 时产生观察符号vk ∈O 的离散概率值( vk 为离散符号) 或连续概率密度( vk 是连续的观察矢量) 矩阵:bj ( k) = P( vk | qt = Sj ) ,1 ≤j ≤N ,1 ≤ k ≤M (3) 当vk 是连续的观察矢量时, bj ( k) 一般取正态概率密度函数, 即bj ( k) = ΣMm = 1Cjmπ( vk ,μjm ,Ujm ) ,其中Cjm 是混合系数, 满足:Cjm ≥0 , ΣMm = 1Cjm = 1 ,1 ≤j ≤N ,1 ≤ m ≤Mμjm ,Ujm 是方差矩阵π( vk ,μjm ,Ujm ) =12π| Ujm |12