基于隐马尔可夫模型的入侵检测方法

基于隐马尔可夫模型的入侵检测方法

赵婧，魏彬，罗鹏

摘要:针对当前网络安全事件频发以及异常检测方法大多集中在对系统调用数据的建模研究上等问题，提出一种基于隐马尔可夫模型的入侵检测方法。该算法基于系统调用和函数返回地址链的联合信息来建立主机进程的隐马尔可夫模型。此外，针对常用训练方法存在的不足，设计了一种快速算法用以训练模型的各个参数。实验结果表明:基于系统调用和函数返回地址链的联合信息的引入能够有效区分进程的正常行为和异常行为，大幅度降低训练时间，取得了良好的运算效果。

关键词:入侵检测;隐马尔可夫模型;系统调用序列

入侵检测作为一种网络安全防卫技术，可以有效地发现来自外部或内部的非法入侵，因此针对入侵检测算法的研究具有重要的理论和很强的实际应用价值。

基于动态调用序列对系统的入侵行为进行发掘是入侵检测领域主要的检测方法之一。自Forrest在1996年首次提出使用系统调用进行异常检测的思路和方法以来，有很多基于此的改进算法被提出。

文献提出一种基于频率特征向量的系统调用入侵检测方法，将正常系统调用序列抽取出的子序列的频率特征转换为频率特征向量。文献提出基于枚举序列、隐马尔科夫2种方法建立系统行为的层次化模型。然而，这类方法在误报率以及漏报率方面仍与实际需求有着一定的差距。

此外，由于隐马尔可夫模型(hiddenmarkovmodel，HMM)是一种描述离散时间内观察数据非常强大的统计工具，因此在基于主机的入侵检测研究中，HMM方法是目前重要的研究方向之一。

美国新墨西哥大学的Warrender等首次于1999年在IEEESymposiumonSecurityandPrivacy 会议上提出将HMM应用于基于系统调用的入侵检测中。2002年，Qiao等提出使用HMM对系统调用序列进行建模，利用TIDE方法划分状态序列的短序列，建立正常数据的状态短序列库来进行检测。2003年，Cho等提出用HMM对关键的系统调用序列进行建模。文献设计了一种双层HMM模型进行入侵检测，而其中所用到的训练方法存在局部最优以及时间效率较低等问题限制了其在实际中的应用。文献依据在网络数据包中发现的频繁情节，设计了基于HMM的误用检测模型。文献设计了一种基于节点生长马氏距离K均值和HMM的网络入侵检测方法。近些年，针对此方面的研究热度依然不减。然而，从目前的研究情况看，虽然基于隐马尔可夫模型的入侵检测技术能取得较好的检测效果，但是也存在着如下几个问题:

1)基于HMM的入侵检测技术主要集中在对主机的命令序列或者系统调用序列进行建模，单一的数据源提供的信息较少，因此检测效果仍然不够理想。

2)在线学习问题，隐马尔可夫模型的建立需要消耗大量的时间和空间对参数进行调整学习，这导致了HMM难以得到有效的利用。综上所述，为克服现有模型算法所存在的问题，提出一种新的基于系统调用和进程堆栈信息的HMM入侵检测方法，该方法的主要思想是将系统调用和函数返回地址信息作为检测数据源，并利用HMM来构建主机特权进程的正常行为模型。其次，针对经典模型训练法存在局部最优且算法的复杂度较高等问题，设计一个更为简单的训练算法来计算HMM的参数，进而提升算法效率。最后，设计了附加观察值和附加状态等参数，用以消除非完备的数据以及零概率对模型的影响。

1、隐马尔可夫模型

马尔可夫模型中的每个状态都与一个具体的观察事件相互对应，但实际问题可能会比Markov链模型所描述的情况更复杂，人们所能观察到的事件一般情况下并不是与状态完全

一致对应的，而是通过概率相联系，这样的模型称为HMM。

HMM是由马尔可夫过程扩充改变而形成的一种随机模型算法，它的基本理论是由数学家Baum在20世纪60年代后期建立起来的。该方法最早在20世纪70年代应用于语音处理领域，而在20世纪80年代逐渐广泛应用于文本处理等各个领域中。

20世纪90年代初以来，HMM及其各种推广形式开始被用于图像信号处理以及视频信号处理等领域。

HMM的状态不能够直接观察到，而是可以通过观测向量序列得到，每个观测向量都是由概率密度分布表现为不同的状态，因此其是具有一定状态数的隐马尔科夫链和显示随机函数集。而其在应用过程中需要解决3个基本问题:对于给定的一个观察序列O={O1，O2，…，OT}和一个HMM参数λ=(π，A，B)，有:

1)评估问题，

2)解码问题，

3)训练问题。

2、基于HMM入侵检测方法

2．1模型的参数定义

系统调用和函数返回地址反映了程序执行时系统内核层的服务行为。系统调用信息是进程对资源的请求，它从一定程度上反映了进程行为的变化过程。而层层嵌套的函数返回地址则反映了系统调用对内核资源请求的过程。把函数返回地址的序列称为函数调用链，它代表了一个系统调用产生时完整的函数调用的路径。假设函数f()是函数main()的一个子函数且被main()调用，且函数f()直接调用某个系统调用，则该调用对应的一条函数链为A={a1，a2}，其中，a1为函数main()的返回地址，a2为函数f()的返回地址。系统调用与函数调用链的联合信息能够比仅仅使用系统调用信息更加有效、精确地描述进程的行为，因此，采用系统调用和函数调用链来构建正常进程的隐马尔可夫模型。

HMM是一种双重随机过程，能够有效地刻画离散事件之间的转移特性。传统的基于HMM的入侵检测方法中，系统调用是HMM的观察符号，HMM的观察序列是程序运行时的系统调用序列，而隐状态是不可见的。隐状态在模型中没有具体的意义，一般选择不同类型系统调用的个数作为HMM中隐状态的个数。

在提出的HMM方法中，系统调用作为HMM的隐状态，而系统调用产生时对应的函数调用链作为HMM的观察值。那么，隐马尔可夫模型的参数可以定义如下:

1)N，模型的隐状态个数。定义隐状态集合为S={S1，S2，…，SN}，qt为t时刻HMM 所处的状态。对于某个特权进程，模型的隐状态集合即为进程所有可能出现的不同类型的系统调用组成的集合，该集合中系统调用的个数即为隐状态的个数。

2)M，模型的观察值个数。定义观察值集合为V={v1，v2，…，vM}，Ot为t时刻HMM输出的观察值。对于某个特权进程，模型的观察值集合即为进程所有可能出现的不同的函数调用链组成的集合，该集合中函数链的个数即为观察值个数。

3)状态转移概率矩阵A={aij}，其中，aij=P(qt+1=Sj|qt=Si)，1i，j N，表示当前状态(系统调用)为Sj且下一个状态(系统调用)为Si的概率值。该状态转移矩阵描述了系统调用之间的一步转移概率。

4)输出概率矩阵B={bj(k)}，其中，bj(k)=P(Ot=vk|qt=Sj)，1j N，1 k M，表示当前状态(系调用)为Sj时，对应的观察值(函数调用链)为vk的概率值。如果概率值为0，则表示进程执行时，进程不可能通过执行函数路径vk得到当前系统调用Sj。

5)初始概率矩阵π={πi}，其中，πi=P(q1=Si)，1i N，表示在初始时刻处于状态(系统调用)Si的概率值。

根据上面的参数定义，可以得到关于进程系统调用和堆栈信息的隐马尔可夫模型λ=(π，

A，B)。

2．2模型的训练

隐马尔可夫模型的训练算法是基于HMM的入侵检测应用的关键问题。经典的训练方法Baum-Welch算法是一种迭代算法，它利用前向后向概率来解决参数估计问题。但是BW算法是一种局部最优算法而且算法的复杂度较高，需要消耗大量的时间进行训练，这些缺点影响了HMM的检测效果和实用性。在提出的方法中，系统调用是作为模型的状态出现的，它对于整个模型是可见的。因此，可以利用一个更为简单的训练算法来计算HMM的参数。

给定某个特权进程的一条系统调用序列和相应的函数调用链序列对HMM进行训练。假设进程的函数调用链序列为O={O1，O2，…，OT}，系统调用序列为Q={q1，q2，…qT}，其中，Ot为进程执行系统调用qt时对应执行的函数调用链。HMM模型λ=(π，A，B)的各参数可由如下公式计算得到:aij=NijNi*(1)πi=NiNto(2)bj(k)=MjkMj*(3)其中:Nij为训练进程中当前时刻t的状态qt为Si，下一时刻t+1的状态qt+1为Sj的个数;Ni*为训练进程中当前时刻的t状态qt为Si，下一时刻t+1的状态qt+1为S={S1，S2，…，SN}中任一系统调用的个数;Ni 为训练进程中当前时刻t的状态qt为系统调用Si的个数;Nto为训练进程中系统调用的总个数;Mjk为训练进程中当前时刻t的状态qt为系统调用Sj时，观察符号Ot为函数调用链Vk 的个数;Mj*为训练进程中当前时刻t的状态qt为系统调用Sj时，观察符号Ot为V={v1，v2，…，vM}中任一函数调用链的个数。

由于完备的训练数据是很难获得的，因此在实际检测中有可能出现之前在训练数据集中未曾学习到的系统调用或者函数调用链;另外当服务进程遭受入侵时，也会产生一系列未曾在训练数据中出现过的系统调用或函数调用链。考虑到以上因素，引入一个附加观察值vM+1和附加状态SN+1来表示这些没有出现过的观察值和状态。在隐马尔可夫模型中，参数定义如下:πSN+1=10－6，aSN+1Sj=aSiSN+1=10－6，bj(VM+1)=10－6，i N，1 j M。为了避免检测时出现概率值为零的情况，在状态转移矩阵A和初始概率分布π中为零者，也赋予一个固定的小概率值10－6。

2．3异常检测

基于正常程序行为的HMM训练完成以后，在实验中，以每个进程作为研究对象，检测某个进程是否正常。因此，给定一组包含系统调用和函数调用链的数据，首先按照进程号对它们进行分组，然后将每个进程产生的系统调用和函数调用链作为一组进行检测。在实际的异常检测中，长度为L的滑动窗用以对上述数据进行分割，其中步距为1。

利用正常数据训练得到的HMM参数模型λ=(π，A，B)，对于给定的一条函数调用链序列X={Ot－L+1，…，Ot}(该函数链对应的系统调用序列为Y={qt－L+1，…，qt})，可以按如下公式计算它出现的概率:P(X|λ)=πqt－L+1bqt－L+1(Ot－L+1)Πt－1i=t－L+1aqiqi+1bqi+1(Oi+1)(4)

此外，文中将异常度δ定义为如下的形式:δ=NNCNTS(5)其中:NNC为不匹配短序列数，定义为输出概率小于初始设定阈值数目;NTS为测试进程中的总的短序列数。在实验中将求得的异常度与实验中不断调整得到的阈值δh进行比较，如果异常度大于该阈值，就认为产生此测试序列的进程可能为异常;否则认为是正常。

3、实验结果与分析

3．1实验数据

实验数据由在ＲedhatLinux7．2上跟踪Ftp和SambaHttpd特权进程所获得，并将其分为训练以及测试2个部分。其中，训练数据是部分正常数据，而测试数据则由其余正常数据以及异常数据构成。正常数据由模拟用户各种正常行为获得，而异常数据则是对进程进行模拟攻击得到。

3．2实验结果

每一个正常数据轨迹都是正常状态下，一个特权从开始产生到最后结束的系统调用和函数调用链序列。每一个异常数据轨迹都是特权进程从开始被攻击到最后进程结束的系统调用和函数调用链序列。

能够有效区分进程的正常状态和异常状态是评价一个入侵检测方法好坏的重要标准。进程的正常序列和进程的异常序列之间的异常度差异越大，则越容易发现针对系统的入侵行为。可见正常进程和异常进程的平均异常度差异非常明显，因此可以作为正常与异常的区分。

误报率和漏报率是评价入侵检测方法有效性的一个重要标准。实验中将Warrender提出的经典HMM入侵检测方法和提出的HMM入侵检测方法进行比较。2种方法都采用异常度作为判定进程是否异常的指标，同时滑动窗口的长度均选择为L=6。实验采用的数据为Ftp 和Samba这2种特权进程的正常序列和异常序列。由于Warrender的方法是基于系统调用来对进程的隐马尔可夫模型建模的，因此该方法只使用实验数据中各进程的系统调用序列进行训练和测试。

为了评估提出的入侵检测方法的实时性，在实验中，对2种方法的训练时间进行了比较。实验所用计算机配置为CPUPengtiumIV2．6GHz，512MBDDＲ内存。

3．3实验结果的分析与讨论

从上述结果可以看出:

1)所提出的基于系统调用和进程堆栈信息的HMM入侵检测方法是有效的。无论是Ftp 数据还是Samba数据，异常序列的异常度比正常序列的异常度明显要高得多。因此，使用所提出的方法能够很容易地将程序的正常行为和异常行为区分出来，从而给检测系统提供一个较大的阈值范围选择。

2)提出的方法与Warrender的方法都能够检测出所有的异常进程，2个方法对于测试数据的漏报率相同，在误报率方面提出的方法要比Warrender方法略好。可见，提出的方法可以保持在一个较低误报率的情况下，有效且准确地检测出针对系统的攻击行为。

3)提出的方法对正常行为模型的训练的时间消耗要远远少于Warrender方法。例如，训练近83万条系统调用需耗时约36min左右，而经典的HMM方法则需要耗时约22h。

4、总结

首先介绍了隐马尔可夫模型的基本概念，隐马尔可夫模型的3个基本问题及相关算法。然后根据隐马尔可夫模型的结构特点，提出一种利用系统调用和函数调用链2方面信息来联合构建特权进程的正常行为模型的方法，将系统调用作为隐马尔可夫模型的隐状态，函数调用链作为隐马尔可夫模型的观察符号，利用一种更为简单的训练算法来得到模型的各个参数。检测时，根据一段函数调用链的序列连续出现的概率和异常度来检测整条序列是否异常。实验结果表明:提出的方法能够有效区分进程的正常行为和异常行为;与经典HMM方法相比，该方法的训练时间消耗要小得多，因此具有更好的实时性以及实用性，即可作为一种实时有效的在线入侵检测方法。

参考文献:

［1］王建，冯伟森．基于KAD网络内容监督的关键技术研究［J］．四川大学学报:工程科学版，

［2］张莉萍，雷大江，曾宪华．基于频率特征向量的系统调用入侵检测方法［J］．计算机科学，

［3］郜燕，刘文芬．基于隐Markov过程的网络信任评估模型［J］．四川大学学报:工程科学版，

［4］周星，彭勤科，王静波．基于两层隐马尔可夫模型的入侵检测方法［J］．计算机应用研究，

［5］李丛．基于HMM的网络入侵检测研究［J］．计算机与数字工程，

［6］储泽楠，李世扬．基于节点生长马氏距离K均值和HMM的网络入侵检测方法设计［J］．计算机测量与控制

隐马尔可夫模型及其应用

小论文写作: 隐马尔可夫模型及其应用 学院：数学与统计学院专业：信息与计算科学学生：卢富毓学号：20101910072 内容摘要：隐马尔可夫模型是序列数据处理和统计学习的重要概率模型，已经成功被应用到多工程任务中。本小论文首先从隐马尔可夫模型基本理论和模型的表达式出发，进一步阐述了隐马尔可夫模型的应用。 HMM 隐马尔可夫模型（Hidden Markov Model，HMM）作为一种统计分析模型，创立于20世纪70年代。80 年代得到了传播和发展，成为信号处理的一个重要方向，现已成功地用于语音识别，行为识别，文字识别以及故障诊断等领域。 隐马尔可夫模型状态变迁图（例子如下） x—隐含状态 y—可观察的输出 a—转换概率（transition probabilities） b—输出概率（output probabilities） 隐马尔可夫模型它用来描述一个含有隐含未知参数的马尔可夫过程。其难点是从可观察的参数中确定该过程的隐含参数。然后利用这些参数来作进一步的分析，例如模式识别。 在正常的马尔可夫模型中，状态对于观察者来说是直接可见的。这样状态的转换概率便是全部的参数。而在隐马尔可夫模型中,状态并不是直接可见的，但受状态影响的某些变量则是可见的。每一个状态在可能输出的符号上都有一概率分布。因此输出符号的序列能够透露出状态序列的一些信息。 HMM的基本理论 隐马尔可夫模型是马尔可夫链的一种，它的状态不能直接观察到，但能通过观测向量序列观察到，每个观测向量都是通过某些概率密度分布表现为各种状态，每一个观测向量是由一个具有相应概率密度分布的状态序列产生。所以，隐马尔可夫模型是一个双重随机过程----具有一定状态数的隐马尔可夫链和显示随机函数集。自20世纪80年代以来，HMM被应用于语音识别，取得重大成功。到了

基于神经网络隐马尔可夫模型的混合

基于神经网络/隐马尔可夫模型的混合 语音识别方法的研究现状 摘要：作为大词汇量连续语音识别系统的主流技术，隐马尔可夫模型（HMM ）方法已经取得了相当的成功。但是，由于HMM 在理论上的一些缺陷，使得目前的连续语音识别系统只能在非常有限的范围内得到应用。也就是说，从根本意义上说，语音识别是一个尚未解决的问题，仍旧是一个科学上的问题，离工程化还有相当的距离。所以，不断地探索新模型与新方法对彻底解决这一问题至关重要。另一方面，近几年的研究表明，神经网络（ANN ）具有极强的对复杂模式的分类能力。在连续语音识别的研究中，理应考虑结合两者之长来提高识别系统的性能，尤其是声学层面上的识别率。本文旨在介绍国外这方面的前沿成果，并结合我们自己在这方面的工作，对其发展方向提出一些看法。 关键词：神经网络，隐马尔可夫模型，混合方法。 一. 概况 近年来，自动语音识别的研究已经取得了非常大的进步，许多科研单位和大公司的语音识别系统在实验室中都表现出了较高的识别率。但是，这些识别系统在实际场合的应用效果是不能令人满意的，或者说，目前的识别系统只能在非常有限的范围内得到应用。 为了根本解决语音识别问题，我们还必须不断地探索新模型与新方法。首先，我们回顾一下当前语音识别中最为成功的方法。 语音的产生可以看作是由信息源通过一个有噪信道，把语言序列W 转换为一个信号序列S 的过程[1]，如图1所示。因此，语音识别就是一个最大后验概率（MAP ）的解码问题。 有 噪 信 道 通 道 解 码 图1 根据贝叶斯公式，该解码问题被表示为： arg max (/)arg max (/)()() W W P W A P A W P W P A ∈∈=ΓΓ 其中A 是声学特征向量，P(A/W)是声学模型，P(W)是语言模型，可以认为P(A)与P(W)无关 [2][3]，则（1）式等同于： argmax (/)argmax (/)() W W P W A P A W P W ∈∈=ΓΓ

隐马尔可夫模型

隐马尔可夫模型 维基百科，自由的百科全书 跳转到：导航, 搜索 隐马尔可夫模型状态变迁图（例子） x—隐含状态 y—可观察的输出 a—转换概率（transition probabilities） b—输出概率（output probabilities） 隐马尔可夫模型（Hidden Markov Model，HMM）是统计模型，它用来描述一个含有隐含未知参数的马尔可夫过程。其难点是从可观察的参数中确定该过程的隐含参数。然后利用这些参数来作进一步的分析，例如模式识别。 在正常的马尔可夫模型中，状态对于观察者来说是直接可见的。这样状态的转换概率便是全部的参数。而在隐马尔可夫模型中,状态并不

是直接可见的，但受状态影响的某些变量则是可见的。每一个状态在可能输出的符号上都有一概率分布。因此输出符号的序列能够透露出状态序列的一些信息。 目录 [隐藏] ? 1 马尔可夫模型的演化 ? 2 使用隐马尔可夫模型 o 2.1 具体实例 o 2.2 隐马尔可夫模型的应用 ? 3 历史 ? 4 参见 ? 5 注解 ? 6 参考书目 ?7 外部连接 [编辑]马尔可夫模型的演化 上边的图示强调了HMM的状态变迁。有时，明确的表示出模型的演化也是有用的,我们用x（t1）与x（t2）来表达不同时刻t1和t2的状态。 在这个图中,每一个时间块（x(t), y(t)）都可以向前或向后延伸。通常，时间的起点被设置为t=0 或t=1.

另外,最近的一些方法使用Junction tree算法来解决这三个问题。[编辑]具体实例 假设你有一个住得很远的朋友,他每天跟你打电话告诉你他那天作了什么.你的朋友仅仅对三种活动感兴趣:公园散步,购物以及清理房间.他选择做什么事情只凭天气.你对于他所住的地方的天气情况并不了解,但是你知道总的趋势.在他告诉你每天所做的事情基础上,你想要猜测他所在地的天气情况. 你认为天气的运行就像一个马尔可夫链.其有两个状态 "雨"和"晴",但是你无法直接观察它们,也就是说,它们对于你是隐藏的.每天,你的朋友有一定的概率进行下列活动:"散步", "购物", 或 "清理".

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

马尔可夫及隐马尔可夫模型在数据挖掘中的应用 侯传宇１，２ （１．合肥工业大学计算机与信息学院，安徽合肥２３０００９；２．宿州学院数学系，安徽宿州２３４０００） 摘要：随着用户对于数据挖掘的精确度与准确度要求的日益提高，马尔可夫模型与隐马尔可夫模型被广泛用于数据挖掘领域。本文阐述了马尔可夫模型和隐马尔可夫模型数据挖掘领域的应用，以及隐马尔可夫模型可解决的问题，以供其他研究者借鉴。 关键词：马尔可夫模型；隐马尔可夫模型；数据挖掘 中图分类号：ＴＰ３１１文献标识码：Ａ文章编号：１００９－３０４４（２００８）０７－１１１８６－０３ ＴｈｅＡｐｐｌｉｃａｔｉｏｎｏｆＭａｒｋｏｖＭｏｄｅｌｓａｎｄＨｉｄｄｅｎＭａｒｋｏｖＭｏｄｅｌｓｉｎＤａｔａＭｉｎｉｎｇ ＨＯＵＣｈｕａｎ－ｙｕ１，２ （１．ＳｃｈｏｏｌｏｆＣｏｍｐｕｔｅｒａｎｄＩｎｆｏｒｍａｔｉｏｎ，ＨｅｆｅｉＵｎｉｖｅｒｓｉｔｙｏｆＴｅｃｈｎｏｌｏｇｙ，Ｈｅｆｅｉ２３０００９，Ｃｈｉｎａ；２．ＤｅｐａｒｔｍｅｎｔｏｆＭａｔｈｅｍａｔｉｃｓ，ＳｕｚｈｏｕＣｏｌ－ｌｅｇｅ，Ｓｕｚｈｏｕ２３４０００，Ｃｈｉｎａ） Ａｂｓｔｒａｃｔ：Ｗｉｔｈｔｈｅｃｕｓｔｏｍｅｒ＇ｓｒｅｑｕｉｒｅｍｅｎｔｒａｉｓｉｎｇｄａｙｂｙｄａｙｉｎａｃｃｕｒａｃｙａｎｄａｃｃｕｒａｔｅ，ＭａｒｋｏｖＭｏｄｅｌｓａｎｄＨｉｄｄｅｎＭａｒｋｏｖＭｏｄｅｌｓｗｅｒｅｅｘｔｅｎｓｉｖｅｌｙｕｓｅｄｉｎＤａｔａＭｉｎｉｎｇ．ＴｈｉｓｐａｐｅｒｉｎｔｒｏｄｕｃｅｄｔｈｅａｐｐｌｉｃａｔｉｏｎｏｆＭａｒｋｏｖＭｏｄｅｌｓａｎｄＨｉｄｄｅｎＭａｒｋｏｖＭｏｄｅｌｓｉｎＤａｔａＭｉｎｉｎｇ，ａｎｄｓｏｍｅｐｒｏｂｌｅｍｓｔｈａｔｃｏｕｌｄｂｅｓｏｌｖｅｄｂｙＨｉｄｄｅｎＭａｒｋｏｖＭｏｄｅｌｓ，ｗｈｉｃｈｃｏｕｌｄｐｒｏｖｉｄｅｈｅｌｐｔｏｒｅｓｅａｒｃｈｅｒｓｉｎｔｈｉｓｄｏｍａｉｎ． Ｋｅｙｗｏｒｄｓ：ＭａｒｋｏｖＭｏｄｅｌｓ；ＨｉｄｄｅｎＭａｒｋｏｖＭｏｄｅｌｓ；ＤａｔａＭｉｎｉｎｇ １引言 当前Ｉｎｔｅｒｎｅｔ与数据库的高速发展，信息以海量增长，对于越来越多的数据，如何寻找有用的信息是人们所关心的问题，也是数据挖掘的任务。数据挖掘（ＤａｔａＭｉｎｉｎｇ，ＤＭ），又称数据库中的知识发现（ＫｎｏｗｌｅｄｇｅＤｉｓｃｏｖｅｒｙｉｎＤａｔａｂａｓｅ，ＫＤＤ），是从９０年代初兴起的一门数据库技术。数据挖掘就是从大量的、不完全的、有噪声的、模糊的、随机的实际应用数据中，提取隐含在其中的、人们事先不知道的、但又是潜在有用的信息和知识的过程。数据挖掘是多学科交叉的产物，结合了数据库、人工智能、统计学、机器学习、可视化等技术，通过发现有用的新规律和新概念，提高了数据拥有者对大量原始数据的深层次理解、认识和应用，解决了“数据丰富，知识贫乏”的问题，具有广泛的应用前景。 数据挖掘能从大量数据中抽取出隐藏在数据之中的有用信息，从而为决策者进行决策提供重要的依据，大大提高决策的科学性和减小决策的盲目性也可以帮助商业管理者更好地理解用户的行为，制订相应的用户服务政策，从而增加商业机会。例如电信公司通过发现用户通话的规律，制定更合理的优惠政策。随着用户对于挖掘数据的精度与准确度要求的提高，大量数据挖掘算法涌现。其中，数学模型—马尔可夫模型与隐马尔可夫模型应用在许多挖掘领域，如：语音识别、自动文本抽取、数据流分类等，取得了较好的挖掘效果。 ２马尔可夫模型及隐马尔可夫模型简介 马尔可夫模型（ＭａｒｋｏｖＭｏｄｅｌｓ，ＭＭ）可来描述为：如果一个系统有Ｎ个状态，Ｓ１，Ｓ２，……，Ｓｎ，随着时间的推移，该系统从某一状态转移到另一状态，系统在时间ｔ的状态记为ｑｔ。系统在时间ｔ处于状态ｓｊ（１≤ｊ≤Ｎ）的概率取决于其在时间１，２，……，ｔ－１的状态，该概率为：ｐ（ｑｔ＝ｓｊ｜ｑｔ－１＝ｓｉ，ｑｔ－２＝ｓｋ，……）。 若系统在时间ｔ的状态只与其在时间ｔ－１的状态相关，则该系统构成一个离散的一阶马尔柯夫链（时间与状态都是离散的）又称为齐次马氏链，即： ｐ（ｑｔ＝ｓｊ｜ｑｔ－１＝ｓｉ，ｑｔ－２＝ｓｋ，……）＝ｐ（ｑｔ＝ｓｊ｜ｑｔ－１＝ｓｉ）（１）若（１）式是独立于时间ｔ的随机过程，即状态于时间无关，则称为马尔可夫过程。 用Ｐｉｊ（ｔ）表示，在任一时刻ｓ，ｑｓ从状态ｉ经过时间ｔ转移到状态ｊ的概率。Ｐｉｊ（ｔ）表示其转移概率。则可通过其转移矩阵来求其ｎ步转移矩阵，令ｐ＝ｐ（１）＝Ｐｉｊ（ｔ），则其ｎ步转移矩阵为ｐ（ｎ）＝ｐｎ。若初始状态的概率分布Ｐ"（０），则可以求得其ｎ步的概率分布：Ｐ"（ｎ）＝Ｐ"（０）ｐ（ｎ）。 收稿日期：２００８－０１－１５ 作者简介：侯传宇（１９８０－），男，安徽利辛人，助教，合肥工业大学在职研究生，研究方向：人工智能与数据挖掘。

连续隐马尔科夫链模型简介

4.1 连续隐马尔科夫链模型（CHMM） 在交通规划和决策的角度估计特定出行者的确切的出行目的没有必要，推测出行者在一定条件下会有某种目的的概率就能够满足要求。因此本文提出一种基于无监督机器学习的连续隐马尔科夫链模型（CHMM）来识别公共自行车出行链借还车出行目的，根据个人属性、出行时间和站点土地利用属性数据，得到每次借还车活动属于某种出行目的的概率，进一步识别公共自行车出行链最可能的出行目的活动链。 4.1.1连续隐马尔科夫链模型概述 隐马尔可夫链模型（Hidden Markov Model，HMM）是一种统计模型，它被用来描述一个含有隐含未知状态的马尔可夫链。隐马尔可夫链模型是马尔可夫链的一种，其隐藏状态不能被直接观察到，但能通过观测向量序列推断出来，每个观测向量都是通过状态成员的概率密度分布表现，每一个观测向量是由一个具有相应概率密度分布的状态序列产生。 本文将隐马尔科夫链和混合高斯融合在一起，形成一个连续的隐马尔科夫链模型（CHMM），并应用该模型来识别公共自行车出行链借还车活动目的。连续隐马尔科夫链模型采用无监督的机器学习技术，用于训练的数据无需是标记的数据，该模型既不需要标记训练数据，也没有后续的样本测试，如提示-回忆调查。相反，该模型仅利用智能卡和总的土地利用数据。后者为隐藏活动提供额外的解释变量。出行链内各活动的时间和空间信息是从IC卡数据获得，相关土地利用数据是根据南京土地利用规划图和百度地图POI数据获得。 在本文的研究中，一个马尔可夫链可以解释为出行者在两个连续活动状态之间的状态转换，确定一个状态只取决于它之前的状态，一个状态对应一个出行者未知的借还车活动[48-50]。本研究坚持传统的马尔可夫过程的假设，将它包含进无监督的机器学习模型。“隐藏马尔可夫”源于一个事实，即一系列出行链的活动是不可观察的。 对于CHMM，高斯混合模型负责的是马尔可夫链的输入端，每一个活动模式下的隐藏状态都有属于一个特征空间的集群输出概率，每个集群是观察不到的，隐藏状态集群的数量必须事先给出。一些研究者称这些集群为二级隐状态[51]。

Matlab2011b的HMM(隐马尔可夫模型)相关函数介绍

Matlab 2011b Statistics Toolbox HMM 作者：yuheng666 Email:wuyuheng666@https://www.wendangku.net/doc/9210145839.html, 关键字：HMM，隐马尔科夫模型，Matlab，Statistics Toolbox 声明：本文主要介绍Matlab2011b中Statistics Toolbox工具箱里与隐马尔科夫模型相关的函数及其用法（请勿与其它HMM工具箱混淆）。本文的主要内容来自Matlab 2011b的帮助文档，为作者自学笔记。水平有限，笔记粗糙，本着“交流探讨，知识分享”的宗旨，希望对HMM感兴趣的同学有些许帮助，欢迎指教，共同进步。 有关马尔科夫模型的基本知识，请参考其他资料。如： https://www.wendangku.net/doc/9210145839.html,/~lliao/cis841s06/hmmtutorialpart1.pdf https://www.wendangku.net/doc/9210145839.html,/~lliao/cis841s06/hmmtutorialpart2.pdf https://www.wendangku.net/doc/9210145839.html,/section/cs229-hmm.pdf http://jedlik.phy.bme.hu/~gerjanos/HMM/node2.html https://www.wendangku.net/doc/9210145839.html,/dugad/hmm_tut.html ....... 变量说明： 设有M个状态，N个符号Markov模型。 TRANS：对应状态转移矩阵，大小为M*M，表示各状态相互转换的概率，TRANS(i,j)表示从状态i转换到状态j的概率。 EMIS：对应符号生成矩阵，又叫混淆矩阵，观察符号概率分布。EMIS(i,j)代表在状态i时，产生符号j的概率。 函数介绍： hmmgenerate — Generates a sequence of states and emissions from a Markov model 从一个马尔科夫模型产生状态序列和输出序列，该序列具有模型所表达的随机性特征。 A random sequence seq of emission symbols A random sequence states of states 用法：

隐马尔可夫模型(HMM)简介

隐马尔可夫模型(HMM)简介 （一） 阿黄是大家敬爱的警官，他性格开朗，身体强壮，是大家心目中健康的典范。 但是，近一个月来阿黄的身体状况出现异常：情绪失控的状况时有发生。有时候忍不住放声大笑，有时候有时候愁眉不展，有时候老泪纵横，有时候勃然大怒…… 如此变化无常的情绪失控是由什么引起的呢？据警队同事勇男描述，由于复习考试寝室不熄灯与多媒体作业的困扰，阿黄近日出现了失眠等症状；与此同时，阿黄近日登陆一个叫做“xiaonei 网”的网站十分频繁。经医生进一步诊断，由于其他人也遇到同样的考试压力、作息不规律的情况而并未出现情绪失控；并且，其它登陆XIAONEI网的众多同学表现正常，因此可基本排除它们是情绪失控的原因。黄SIR的病情一度陷入僵局…… 最近，阿黄的病情有了新的眉目：据一位对手相学与占卜术十分精通的小巫婆透露，阿黄曾经私下请她对自己的病情进行诊断。经过观察与分析终于有了重大发现：原来阿黄的病情正在被潜伏在他体内的三种侍神控制！他们是：修罗王、阿修罗、罗刹神。 据悉，这三种侍神是情绪积聚激化而形成的自然神灵，他们相克相生，是游离于个体意识之外的精神产物，可以对人的情绪起到支配作用。每一天，都会有一位侍神主宰阿黄的情绪。并且，不同的侍神会导致不同的情绪突然表现。然而，当前的科技水平无法帮助我们诊断，当前哪位侍神是主宰侍神；更糟的是，不同的侍神(3个)与不同的情绪（4种）并不存在显而易见的一一对应关系。 所以，乍看上去，阿黄的病情再次陷入僵局…… 我们怎样才能把握阿黄情绪变化的规律？ 我们怎样才能通过阿黄的情绪变化，推测他体内侍神的变化规律？ 关键词：两类状态： 情绪状态（观察状态）：放声大笑，愁眉不展，老泪纵横，勃然大怒 侍神状态（隐状态）：修罗王，阿修罗，罗刹神 （二） 阿黄的病情引来了很多好心人的关心。这与阿黄真诚善良的品格不无关系。 关于侍神的特点，占卜师和很多好心人找来了许多珍贵资料。其中很多人经过一段时间的观察与记录后，在貌似毫无规律的数据背后，发现了侍神与情绪之间的内在规律！！他们在多次观测后，

隐马尔可夫模型及其最新应用与发展

2010 年 第19卷 第 7 期 计 算 机 系 统 应 用 Special Issue 专论·综述 255 隐马尔可夫模型及其最新应用与发展① 朱 明 郭春生 (杭州电子科技大学 通信工程学院 浙江 杭州 310018) 摘 要： 隐马尔可夫模型是序列数据处理和统计学习的一种重要概率模型，已被成功应用于许多工程任务中。 首先介绍了隐马尔可夫模型的基本原理，接着综述了其在人的行为分析、网络安全和信息抽取中的最新应用。最后对最近提出来的无限状态隐马尔可夫模型的原理及最新发展进行了总结。 关键词： 隐马尔可夫模型;行为分析;网络安全;信息抽取;无限状态隐马尔可夫模型 Hidden Markov Model and Its latest Application and Progress ZHU Ming, GUO Chun-Sheng (College of Communication Engineering, Hangzhou Dianzi University, Hangzhou 310018, China) Abstract: Hidden Markov Model (HMM) is an important probabilistic model of sequential data processing and statistical study. It has already been successfully applied in many projects in practice. Firstly, this paper introduces the basic principles of the Hidden Markov Model, and then gives a review to its latest application in the human activity analysis, network security and information extraction. Finally it summarizes the theory and latest progress of the recently proposed infinite Hidden Markov Model (iHMM). Keywords: HMM ；activity analysis ；network security ；information extraction ；iHMM 1 引言 隐马尔可夫模型(Hidden Markov Model, HMM)作为一种统计分析模型，创立于20世纪70年代，80年代得到了传播和发展并成功应用于声学信号的建模中，到目前为止，它仍然被认为是实现快速精确语音识别系统最成功的方法。作为信号处理的一个重要方向，HMM 广泛应用于图像处理，模式识别，语音人工合成和生物信号处理等领域的研究中，并取得了诸多重要的成果[1]。近年来，很多研究者把HMM 应用于计算机视觉、金融市场的波动性分析和经济预算等新兴领域中，因此，结合实际应用，进一步研究各种新型HMM 及其性质，具有重要的意义。文章首先介绍了HMM 的基本理论，接着对其在人的行为分析、网络安全和信息抽取中的最新应用进行了综述。针对经典HMM 应用中存在的两大问题，近年来提出了无限状态隐马尔可夫模型(infinite Hidden Markov Model ，iHMM)，文章的最后对其基本理论及最新发展进行了总结。 ① 收稿时间:2009-10-25;收到修改稿时间:2009-12-06 2 HMM 的基本原理及结构 2.1 HMM 的基本原理 HMM 由两个随机过程组成，其中一个是状态转移序列，它是一个单纯的马尔可夫过程；另一个是与状态对应的观测序列，如图1为一状态数为3的HMM 示意图，其中为状态序列，它们之间的转移是一个马尔可夫过程，为各状态下对应的观测值。在实际问题中，我们只能看到观测值，而不能直接看到状态，只能是通过观测序列去推断状态的存在及转移特征，即模型的状态掩盖在观测序列之中，因而称之为“隐”Markov 模型。 图1 状态数为3的HMM 示意图 设模型的状态数目为，可观测到的符号数目为，