【转载】理工渣眼中的HMM及安全应用

本文主要是介绍【转载】理工渣眼中的HMM及安全应用，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

话说，又到了盼星星盼月亮才等来的周末，结果由于强网杯又给糟蹋了。

比赛实在是被虐的受不了了，于是“点子扎手，风紧扯呼”了~

去91RI逛了一圈，发现了一篇讲HMM不错的文章，记录下来学习学习。

原文地址：http://www.91ri.org/12659.html

----------------------------------------------------------------我是华丽丽的分割线---------------------------------------------------------------------

虽然是理工妹子，但仍是数学渣。症状之一就是每次学习算法都能把自己绕成鸡窝头。所以尝试写一篇数学渣眼中的HMM。

我们先看一个让人头疼的HMM定义式（喜欢从公式下手是我多年来应付考试养成的不良习性）

一、HMM五元素

N：隐藏状态数 hidden states

M：观测状态数 observed states

A：状态转移矩阵 transition matrix

B：发射矩阵 emission matrix

pi：初始隐状态向量 initial state vector

好了，接下来我们用数学渣可以理解的语言来解释上面都是些什么鬼

女主：小红(用食物丈量心情喵)

心情状态有三种: 开心、正常、崩溃

吃的食物也有三种：汉堡、西瓜、啤酒

男主：小明(面部表情识别障碍汪)

因此对男主而言，

隐藏状态：女主的心情状态

观测状态：女主吃的食物

隐藏状态数 ：N=3

观测状态数: M=3

初始隐状态向量pi:

对照下表看：女主处于各种心情状态的概率，例如女主51%的概率是正常的，36%的概率是开心的，13%的概率是崩溃的

开心	正常	崩溃
0.36	0.51	0.13

状态转移矩阵A:

上一个隐状态到下一个隐状态的转化概率矩阵

对照下表看：在女主上一个状态是开心的条件下，则此刻状态是开心的概率为36.5%,正常的概率为50%,崩溃的概率为13.5%

	开心	正常	崩溃
开心	0.365	0.500	0.135
正常	0.250	0.125	0.625
崩溃	0.365	0.265	0.370

发射矩阵B：

隐状态对应的观测状态的概率

对照下表看：在女主是开心的状态下，她吃汉堡的概率是10%，西瓜的概率是20%，啤酒的概率是70%

	汉堡	西瓜	啤酒
开心	0.1	0.2	0.7
正常	0.5	0.25	0.25
崩溃	0.8	0.1	0.1

一个HMM模型就由上面描述的隐藏状态数N，观测状态数M，初始隐状态向量pi，状态转移矩阵A，混淆矩阵B五个要素组成。

-----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------

现在男主小明开始做任务了，我们用现成的工具mahout来示例

查了Mahout的中文意思——驭象的人，再看看Mahout的logo，好吧，想和小黄象happy地玩耍，得顺便陪陪这位驭象人耍耍了...

安装指南（仅介绍local版）

wget http://archive.apache.org/dist/mahout/0.9/mahout-distribution-0.9.tar.gzcd mahout-distribution-0.9/vim bin/mahout

修改

MAHOUT_JAVA_HOME=/usr/lib/jvm/java-6-openjdk-amd64 （修改为你自己的java所在地址）MAHOUT_LOCAL=true

任务一：学习（本例中根据女主吃的食物序列，推断一个合适的HMM模型）

输入：观测状态序列——女主吃的食物序列，我们用数字表示对应的食物与心情

0：汉堡

1：西瓜

2：啤酒

0 ：崩溃

1：开心

2: 正常

输出：生成一个合适的HMM模型

算法：BaumWelch

1.输入观测序列

echo "0 1 2 2 2 1 1 0 0 2 1 2 1 1 1 1 2 2 2 0 0 0 0 0 0 2 2 2 0 0 0 0 0 0 1 1 1 1 2 2 2 2 2 0 2 1 2 0 2 1 2 1 1 0 0 0 1 0 1 0 2 1 2 1 2 1 2 1 1 0 0 2 2 0 2 1 1 0" 
>> hmm-input

2.输入观测序列后，开始生成HMM模型

bin/mahout baumwelch -i hmm-input(观测序列文件） -o hmm-model（hmm模型文件） -nh 3（隐状态数） -no 3（观测状态数） -e .0001 -m 10

3.观察结果

Initial probabilities: 初始隐状态向量pi
0 1 2
0.062295949769082204 0.22250521455286396 0.7151988356780538
Transition matrix:状态转移矩阵A:
0 1 2
0 0.3765444789556002 0.5583673988903969 0.06508812215400292
1 0.3759312048603327 0.2560959620304218 0.36797283310924545
2 0.5383787685979908 0.24752553248847228 0.21409569891353694
Emission matrix: 发射矩阵
0 1 2
0 0.4419117509334424 0.3106990713267408 0.2473891777398168
1 0.20948851558479514 0.2830936761513362 0.5074178082638686
2 0.34341499252552676 0.40310175949497634 0.2534832479794969

--------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------

任务二：预测（根据上一个任务生成的HMM模型来预测女主后续会吃的东西）

输入：HMM模型

输出：预测后续的观测状态，或者计算给定规则状态序列的概率(这个我们在下一个场景中描述）

算法： ForwardBackward

bin/mahout hmmpredict -m hmm-model（hmm模型文件） -o hmm-predictions （预测结果文件）-l 10（预测多少个后续观测状态）

我们看结果

more hmm-predictions 
2 2 0 0 1 2 1 2 2 1

预测女主后续会吃的东西依次为：啤酒，啤酒，汉堡，汉堡，西瓜，啤酒，西瓜，啤酒，啤酒、西瓜
--------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------

任务三：编码（根据女主吃的东西，判断女主当前的心情，这个也是男主最关心的任务，女孩的心思你别猜。。。）

输入：HMM模型，观测状态序列

输出：观测状态序列对应的隐藏状态序列

算法： viterbi

输入观测状态序列，本例中女主吃的食物

echo "2 2 0 0 1 2 1 2 2 1" >> hmm-viterbi-input

判断观测状态序列对应的隐状态序列

bin/mahout viterbi -i hmm-viterbi-input -o hmm-viterbi-output -m hmm-model -l

我们看结果

more hmm-viterbi-output 
2 1 2 0 0 1 2 0 1 2

可以看到女主

吃的东西：啤酒，啤酒，汉堡，汉堡，西瓜，啤酒，西瓜，啤酒，啤酒、西瓜

对应的心情：正常，开心，正常，崩溃，崩溃，开心，正常，崩溃，开心，正常
----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------

三、安全上的应用—— jahmm示例

现在我们知道了什么是HMM以及HMM能做什么，最关键的时刻到了，现实场景的应用。我们先提出

需要解决的问题——HTTP异常请求的检测（弥补基于签名检测的不足）

解决方案猜想——HTTP请求内容实际是一系列字符串，而正常字符串出现的概率远大于异常字符串。我们可以靠概率来划分正常请求与异常请求。

有了这个前提，再结合HMM的学习功能与预测功能，学习功能能根据观测序列（HTTP请求内容）生成最适合的HMM模型，而预测功能能在HMM模型下能计算指定观测序列（HTTP请求内容）的概率。我们得出下面这个

解决方案——两个阶段解决问题：

阶段一：训练；使用正常日志生成HMM模型，并设置正常请求的概率范围

阶段二：检测；使用待检测的请求来计算该请求在上一步所生成的HMM模型中的概率，不在正常请求概率范围内的则判定为异常请求。

原理：我们可以根据概率分布来区分正常与异常请求的原理是 正常请求远远多于异常请求；正常请求是相似的，异常请求各异