. 使用有向无环图表示变量间依赖关系：有向图模型或贝叶斯网（Bayesian network）；

. 使用无向图表示变量间的相关关秀：无向图模型或马尔科夫网（Markov network）；

《机器学习》周志华

. 第一个骰子是我们平常见的骰子（称这个骰子为D6），6个面，每个面（，，，，，）出现的概率是1/

. 第二个骰子是个四面体（称这个骰子为D4），每个面（，，，）出现的概率是1/

. 第三个骰子有八个面（称这个骰子为D8），每个面（，，，，，，，）出现的概率是1/

我们构造的场景就是掷骰子实验。

1.实验假设前提

. 每次从三个骰子里挑一个，挑到每一个骰子的概率未知；

. 每次选的骰子对下一次选择是否有影响也是未知；

. 对每个骰子来说抛到某一个面的概率是相等的（即骰子是没有动过手脚的）

2. 实验结果数据采集

我们不断重复掷骰子，每次得到一个数字，不停的重复该过程，我们会得到一串数字

经过10次实验，我们得到一串数字：1 6 3 5 2 7 3 5 2 4

3. 实验目标

得到观测结果后，我们的目标是进行一些列概率估计：

. 我们得到了这一串数字，每次抛骰子具体是3个中的哪个骰子是未知的，现在需要估计出整个10次实验中最可能的骰子类型是什么（即每次实验对应的骰子）；

. 我们得到了这一串数字，每次抛骰子具体是3个中的哪个骰子是未知的，现在需要估计出现这个观测结果（这一串数字）的概率有多大

这2个问题非常具有代表性，它们实际上代表了HMM问题中的解码和预测两类核心问题。我们来稍微深入一些讨论这个问题。

0x2: 从独立同分布假设开始 - 极简化的HMM假设

写这章的目的是为了能更好的阐述HMM的序列依赖假设，对HMM熟悉的读者可能会挑战说，HMM至少是1阶的，即至少存在“一步依赖”关系。没错！！

笔者在这里作的独立同部分假设，本质上可以理解为是0阶HMM假设，读者朋友在阅读完这章后，可以对比下独立同部分假设和N阶序列依赖假设在对时序数据进行模式提取的时候的不同变现，从而在实际项目中选择是否需要应用HMM去解决你的实际问题。

1. 独立同分布假设

对上面的问题，我们先建立一个基本假设：

. 每次实验选择什么骰子是完全独立随机的（即 /）；

. 每次实验和上一次实验也不存在关系，即实验之间是独立同分布的；

Res：，S = S2

Res：，S = S1

Res：，S = S2

Res：，S = S1

Res：，S = S2

Res：，S = S3

Res：，S = S2

Res：，S = S1

Res：，S = S2

Res：，S = S2

. 从一次实验到下一次选择什么骰子是完全随机的（即 /3 ），也即状态转移概率为 1/3；

. 每次实验之前不再是独立同分布的，每次实验都与之前的N次实验有依赖关联；

六面骰（D6）产生1的输出概率是1/。产生2，，，，6的概率也都是1/；

四面骰（D4）产生1的输出概率是1/。产生2，，4的概率也都是1/；

八面骰（D8）产生1的输出概率是1/。产生2，，，，，，8的概率也都是1/；

. D6的下一个状态是D4，D6，D8的概率都是1/

. D4的下一个状态是D4，D6，D8的概率都是1/

. D8的下一个状态是D4，D6，D8的概率都是1/

. 在HMM中，隐变量是转换概率。知道了转换概率，根据实验观测结果可以最大似然推测出时序

. HMM中，隐变量和观测变量的关系是前者决定后者的关系，即输出概率

http://blog.163.com/zhoulili1987619@126/blog/static/353082012013113191924334/

https://www.zhihu.com/question/20962240

https://www.zhihu.com/question/20962240

http://www.cnblogs.com/skyme/p/4651331.html

http://blog.csdn.net/bi_mang/article/details/52289087

https://yanyiwu.com/work/2014/04/07/hmm-segment-xiangjie.html

https://www.zhihu.com/question/20962240

https://www.zhihu.com/question/52778636

https://www.zhihu.com/question/37391215

https://www.zhihu.com/question/20551866

https://www.zhihu.com/question/28311766

https://www.zhihu.com/question/28311766

https://www.zhihu.com/question/22181185

《统计机器学习》李航

. 开始，从4个盒子里随机选取1个盒子（/4等概率），从这个盒子里随机抽出1个球，记录其颜色后，放回；

. 然后，从当前盒子随机转移到下一个盒子，规则是

　　）如果当前盒子是盒子1，那么下一个盒子一定是2

　　）如果当前盒子是2或3，那么分别以概率0.4和0.6转移到左边或右边的盒子

　　）如果当前盒子是盒子4，那么各以0.5的概率停留在盒子4或者转移到盒子3

. 确定转移的盒子后，再从这个盒子里随机抽出1个球，记录其颜色，放回；

. 如此重复下去，重复进行5次

# -*- coding:utf- -*-

from __future__ import division

import numpy as np

from hmmlearn import hmm

states = ["Rainy", "Sunny"]   ## 隐藏状态类型

n_states = len(states)        ## 隐藏状态数量

observations = ["walk", "shop", "clean"]  ## 可观察的状态类型

n_observations = len(observations)        ## 可观察序列的状态数量

start_probability = np.array([0.6, 0.4])  ## 初始状态概率

## 状态转移概率矩阵

transition_probability = np.array([

  [0.7, 0.3],   # 晴天倾向保持晴天

  [0.4, 0.6]    # 阴天倾向转为晴天

])

## 观测序列概率矩阵

emission_probability = np.array([

  [0.1, 0.4, 0.5],

  [0.6, 0.3, 0.1]

])

# 构建了一个MultinomialHMM模型，这模型包括开始的转移概率，隐状态间的转移矩阵A（transmat），隐状态到观测序列的发射矩阵emissionprob，下面是参数初始化

model = hmm.MultinomialHMM(n_components=n_states)

model.startprob_ = start_probability

model.transmat_ = transition_probability

model.emissionprob_ = emission_probability

# predict a sequence of hidden states based on visible states

bob_says = np.array([[, , , , , ]]).T  ##预测时的可见序列

print bob_says.shape

print bob_says

logprob, alice_hears = model.decode(bob_says, algorithm="viterbi")

print logprob ##该参数反映模型拟合的好坏

## 最后输出decode解码结果

print "Bob says(观测行为序列):", ", ".join(map(lambda x: observations[x[]], bob_says))

print "Alice hears(天气序列)(隐状态序列):", ", ".join(map(lambda x: states[x], alice_hears))

http://www.cs.ubc.ca/~murphyk/Bayes/rabiner.pdf

http://www.cnblogs.com/pinard/p/7001397.html

http://blog.csdn.net/u014365862/article/details/50412978

http://blog.csdn.net/yywan1314520/article/details/50533850

http://hmmlearn.readthedocs.io/en/latest/api.html

http://blog.csdn.net/wowotuo/article/details/40783357

import numpy as np

from hmmlearn.hmm import GaussianHMM

###############################################################################

# Working with multiple sequences

X1 = [[0.5], [1.0], [-1.0], [0.42], [0.24]]

X2 = [[2.4], [4.2], [0.5], [-0.24]]

# concatenate them into a single array and then compute an array of sequence lengths:

X = np.concatenate([X1, X2])

lengths = [len(X1), len(X2)]

###############################################################################

# Run Gaussian HMM

print "fitting to HMM ..."

# Make an HMM instance and execute fit

# There is  type of states

model = GaussianHMM(n_components=, n_iter=).fit(X)

# Train the model parameters and hidden state

model_pre = model.fit(X, lengths)

###############################################################################

print "Compute the observation sequence log probability under the model parameters"

print model_pre.score(X1)

print "Compute the log probability under the model and compute posteriors."

print model_pre.score_samples(X1)

-2.64250783257

import numpy as np

from hmmlearn.hmm import GaussianHMM

###############################################################################

# Working with multiple sequences

X1 = [[0.5], [1.0], [-1.0], [0.42], [0.24]]

X2 = [[2.4], [4.2], [0.5], [-0.24]]

# concatenate them into a single array and then compute an array of sequence lengths:

X = np.concatenate([X1, X2])

lengths = [len(X1), len(X2)]

###############################################################################

# Run Gaussian HMM

print "fitting to HMM ..."

# Make an HMM instance and execute fit

# There is  type of states

model = GaussianHMM(n_components=, n_iter=).fit(X)

# Train the model parameters and hidden state

model_pre = model.fit(X, lengths)

###############################################################################

print "Find most likely state sequence corresponding to X."

print model_pre.decode(X1)

print "pridect the mostly likly hidden state sequence according to the sample"

print model_pre.predict(X1)

print "Compute the posterior probability for each state in the model."

print model_pre.predict_proba(X1)

[[  4.28596850e-013   0.00000000e+000   1.00000000e+000   4.82112557e-178]

 [  1.00000000e+000   1.82778069e-311   3.61988083e-021   0.00000000e+000]

 [  1.00000000e+000   0.00000000e+000   7.31100741e-098   0.00000000e+000]

 [  7.17255159e-002   0.00000000e+000   9.28274484e-001   0.00000000e+000]

 [  9.97881894e-001   0.00000000e+000   2.11810616e-003   0.00000000e+000]]

[    ]

http://hmmlearn.readthedocs.io/en/stable/api.html

http://hmmlearn.readthedocs.io/en/stable/tutorial.html 

# -*- coding: utf- -*-

import urllib

import urlparse

import re

from hmmlearn import hmm

import numpy as np

from sklearn.externals import joblib

MIN_LEN =      # 处理参数值的最小长度

N_Hidden =     # 隐状态个数（从领域经验来看，隐状态数量和观测变量的状态数量基本上应该持平）

T = -  # 最大似然概率阈值

# URL中会出现的特殊字符

SEN = [

    '<',

    '>',

    ',',

    ':',

    '\'',

    '/',

    ';',

    '"',

    '{',

    '}',

    '(',

    ')'

]

# 排除中文干扰 只处理127以内的字符

def isascii(istr):

    if re.match(r'^(http)', istr):

        return False

    for i, c in enumerate(istr):

        if ord(c) >  or ord(c) < :

            return False

        if c in SEN:

            return True

    return True

# 特征离散规范化，减少参数状态空间

def etl(istr):

    vers = []

    for i, c in enumerate(istr):

        c = c.lower()

        if ord(c) >= ord('a') and ord(c) <= ord('z'):   # ascii字母

            vers.append([ord(c)])

        elif ord(c) >= ord('') and  ord(c) <= ord(''):    # 数字

            vers.append([])

        elif c in SEN:

            vers.append([ord(c)])

        else:

            vers.append([])

    return np.array(vers)

def extractvec(filename):

    X = [[]]

    LINES = [['']]

    X_lens = []

    with open(filename) as f:

        for line in f:

            query = urllib.unquote(line.strip('\n'))  # url解码

            if len(line) >= MIN_LEN:

                params = urlparse.parse_qsl(query, True)

                for k, v in params:

                    if isascii(v) and len(v) >= N_Hidden:

                        vers = etl(v)  # 数据处理与特征提取

                        X = np.concatenate([X, vers])  # 每一个参数value作为一个特征向量

                        # # 通过np.concatenate整合成了一个1D长向量，同时需要额外传入len list来标明每个序列的长度边界

                        X_lens.append(len(vers))  # 长度

                        LINES.append(v)

    return X, X_lens, LINES

def train(filename):

    X, X_lens, LINES = extractvec(filename)

    remodel = hmm.GaussianHMM(n_components=N_Hidden, covariance_type="full", n_iter=)

    remodel.fit(X, X_lens)

    joblib.dump(remodel, "../model/xss-train.pkl")

    return remodel

def predict(filename):

    remodel = joblib.load("../model/xss-train.pkl")

    X, X_lens, LINES = extractvec(filename)

    LINES = LINES[:]

    X = X[:, :]

    X_lens = X_lens[:]

    lastindex =

    for i in range(len(X_lens)):

        line = np.array(X[lastindex:lastindex+X_lens[i], :])

        lastindex += X_lens[i]

        pros = remodel.score(line)

        if pros < T:

            print "Find bad sample POR: %d LINE:%s" % (pros, LINES[i])

if __name__ == '__main__':

    # 以白找黑，给HMM输入纯白样本，让其记住正常url参数的模型转化概率

    # remodel = train("../data/web-attack/normal-10000.txt")    # train a GMM model with train sample

    # 输入待检测样本，设定一个阈值(score的分值越小，说明出现的概率越小，也即说明偏离正常样本的程度)

    predict("../data/xss-20.txt")

    # predict the probability of the new sample according to the model(abnormal detection)

# -*- coding:utf- -*-

import sys

import urllib

import urlparse

import re

from hmmlearn import hmm

import numpy as np

from sklearn.externals import joblib

import HTMLParser

import nltk

MIN_LEN =     # 处理参数值的最小长度

N =    # 状态个数

T = -    # 最大似然概率阈值

SEN = ['<', '>', ',', ':', '\'', '/', ';', '"', '{', '}', '(', ')']  #其他字符2

index_wordbag =      # 词袋索引

wordbag = {}    # 词袋

# 数据提取与特征提取，这一步我们不采用单字符的char特征提取，而是根据领域经验对特定的phrase字符组为基础单位，进行特征化，这是一种token切分方案

# </script><script>alert(String.fromCharCode(,,))</script>

# <IMG SRC=x onchange="alert(String.fromCharCode(88,83,83))">

# <;IFRAME SRC=http://ha.ckers.org/scriptlet.html <;

# ';alert(String.fromCharCode(88,83,83))//\';alert(String.fromCharCode(88,83,83))//";alert(String.fromCharCode(88,83,83))

# //\";alert(String.fromCharCode(88,83,83))//--></SCRIPT>">'><SCRIPT>alert(String.fromCharCode(88,83,83))</SCRIPT>

tokens_pattern = r'''(?x)

 "[^"]+"

|http://\S+

|</\w+>

|<\w+>

|<\w+

|\w+=

|>

|\w+\([^<]+\) #函数 比如alert(String.fromCharCode(,,))

|\w+

'''

def split_tokens(line, tokens_pattern):

    tokens = nltk.regexp_tokenize(line, tokens_pattern)

    return tokens

def load_wordbag(filename, max=):

    X = [[]]

    X_lens = []

    tokens_list = []

    global wordbag

    global index_wordbag

    with open(filename) as f:

        for line in f:

            line = line.strip('\n')

            line = urllib.unquote(line)   # url解码

            #h = HTMLParser.HTMLParser()    # 处理html转义字符

            #line = h.unescape(line)

            if len(line) >= MIN_LEN:  # 忽略短url value

                line, number = re.subn(r'\d+', "", line)   # 数字常量替换成8

                line, number = re.subn(r'(http|https)://[a-zA-Z0-9\.@&/#!#\?:=]+', "http://u", line)    # ulr日换成http://u

                line, number = re.subn(r'\/\*.?\*\/', "", line)     # 去除注释

                tokens = split_tokens(line, tokens_pattern)  # token切分

                tokens_list += tokens

    fredist = nltk.FreqDist(tokens_list)  # 单文件词频

    keys = fredist.keys()

    keys = keys[:max]     # 降维，只提取前N个高频使用的单词，其余规范化到0

    for localkey in keys:  # 获取统计后的不重复词集

        if localkey in wordbag.keys():  # 判断该词是否已在词袋中

            continue

        else:

            wordbag[localkey] = index_wordbag

            index_wordbag +=

    print "GET wordbag", wordbag

    print "GET wordbag size(%d)" % index_wordbag

def train(filename):

    X = [[-]]

    X_lens = []

    global wordbag

    global index_wordbag

    with open(filename) as f:

        for line in f:

            line = line.strip('\n')

            line = urllib.unquote(line)   # url解码

            #h = HTMLParser.HTMLParser() # 处理html转义字符

            #line = h.unescape(line)

            if len(line) >= MIN_LEN:

                line, number = re.subn(r'\d+', "", line)   # 数字常量替换成8

                line, number = re.subn(r'(http|https)://[a-zA-Z0-9\.@&/#!#\?:]+', "http://u", line)     # ulr日换成http://u

                line, number = re.subn(r'\/\*.?\*\/', "", line)     # 干掉注释

                words = split_tokens(line, tokens_pattern)

                vers = []

                for word in words:

                    # 根据词汇编码表进行index编码，对不在词汇表中的token词不予编码

                    if word in wordbag.keys():

                        vers.append([wordbag[word]])

                    else:

                        vers.append([-])

            np_vers = np.array(vers)

            X = np.concatenate([X, np_vers])

            X_lens.append(len(np_vers))

    remodel = hmm.GaussianHMM(n_components=N, covariance_type="full", n_iter=)

    remodel.fit(X, X_lens)

    joblib.dump(remodel, "../model/find_black_with_black-xss-train.pkl")

    return remodel

def test(remodel, filename):

    with open(filename) as f:

        for line in f:

            line = line.strip('\n')

            line = urllib.unquote(line)     # url解码

            # 处理html转义字符

            #h = HTMLParser.HTMLParser()

            #line = h.unescape(line)

            if len(line) >= MIN_LEN:

                line, number = re.subn(r'\d+', "", line)      # 数字常量替换成8

                line, number = re.subn(r'(http|https)://[a-zA-Z0-9\.@&/#!#\?:]+', "http://u", line)     # ulr日换成http://u

                line, number = re.subn(r'\/\*.?\*\/', "", line)     # 干掉注释

                words = split_tokens(line)

                vers = []

                for word in words:

                    # test和train保持相同的编码方式

                    if word in wordbag.keys():

                        vers.append([wordbag[word]])

                    else:

                        vers.append([-])

                np_vers = np.array(vers)

                pro = remodel.score(np_vers)

                if pro >= T:

                    print "SCORE:(%d) XSS_URL:(%s) " % (pro, line)

if __name__ == '__main__':

    train_filename = "../data/xss-200000.txt"

    # 基于训练样本集（纯黑，我们这里是以黑找黑），得到词频编码表

    load_wordbag(train_filename, )

    # 基于同样的训练样本集（纯黑，我们这里是以黑找黑），训练HMM模型

    remodel = train(train_filename)

    # 基于训练得到的HMM模型，对未知样本的最大似然概率进行预测（即预测未知样本观测序列出现的可能性，即找类似的黑样本）

    test(remodel, "../data/xss-20.txt")

泛化 -> 分词 -> 词集编码 -> 词集模型处理流程

# -*- coding:utf- -*-

import sys

import urllib

import urlparse

import re

from hmmlearn import hmm

import numpy as np

from sklearn.externals import joblib

import HTMLParser

import nltk

import csv

import matplotlib.pyplot as plt

MIN_LEN =     # 处理域名的最小长度

N =      # 状态个数

T = -   # 最大似然概率阈值

FILE_MODEL = "../model/12-4.m"     # 模型文件名

def load_alexa(filename):

    domain_list = []

    csv_reader = csv.reader(open(filename))

    for row in csv_reader:

        domain = row[]

        if domain >= MIN_LEN:

            domain_list.append(domain)

    return domain_list

def domain2ver(domain):

    ver = []

    for i in range(, len(domain)):

        ver.append([ord(domain[i])])

    return ver

def train_hmm(domain_list):

    X = [[]]

    X_lens = []

    for domain in domain_list:

        ver = domain2ver(domain)    # 逐字符ascii向量化

        np_ver = np.array(ver)

        X = np.concatenate([X, np_ver])

        X_lens.append(len(np_ver))

    remodel = hmm.GaussianHMM(n_components=N, covariance_type="full", n_iter=)

    remodel.fit(X, X_lens)

    joblib.dump(remodel, FILE_MODEL)

    return remodel

def load_dga(filename):

    domain_list = []

    # xsxqeadsbgvpdke.co.uk,Domain used by Cryptolocker - Flashback DGA for  Apr ,--,

    # http://osint.bambenekconsulting.com/manual/cl.txt

    with open(filename) as f:

        for line in f:

            domain = line.split(",")[]

            if domain >= MIN_LEN:

                domain_list.append(domain)

    return domain_list

def test_dga(remodel,filename):

    x = []

    y = []

    dga_cryptolocke_list = load_dga(filename)

    for domain in dga_cryptolocke_list:

        domain_ver = domain2ver(domain)

        np_ver = np.array(domain_ver)

        pro = remodel.score(np_ver)

        x.append(len(domain))

        y.append(pro)

    return x, y

def test_alexa(remodel,filename):

    x=[]

    y=[]

    alexa_list = load_alexa(filename)

    for domain in alexa_list:

        domain_ver = domain2ver(domain)

        np_ver = np.array(domain_ver)

        pro = remodel.score(np_ver)

        x.append(len(domain))

        y.append(pro)

    return x, y

if __name__ == '__main__':

    domain_list = load_alexa("../data/top-1000.csv")

    # remodel = train_hmm(domain_list)    # 以白找黑: 基于alexa域名数据训练hmm模型

    remodel = joblib.load(FILE_MODEL)

    x_3, y_3 = test_dga(remodel, "../data/dga-post-tovar-goz-1000.txt")

    x_2, y_2 = test_dga(remodel,"../data/dga-cryptolocke-1000.txt")

    fig, ax = plt.subplots()

    ax.set_xlabel('Domain Length')      # 横轴是域名长度

    ax.set_ylabel('HMM Score')          # 纵轴是hmm对观测序列计算得到的似然概率

    ax.scatter(x_3, y_3, color='b', label="dga_post-tovar-goz")

    ax.scatter(x_2, y_2, color='g', label="dga_cryptolock")

    ax.legend(loc='right')

    plt.show()