BigData 复习笔记 02：TFIDF, LCS 与中文分词

发表于 2019-07-24 更新于 2021-06-18 分类于 Tech 阅读次数：

本文字数： 17k 阅读时长 ≈ 16 分钟

TF-IDF, LCS, HMM

Chapter02. 中文分词

NLP 文本相似度

文本相似度

语义相似（从人的角度理解语句含义）

字面相似（中文分词）

余弦相似度 / 向量空间模型

相似度度量

计算个体间相似程度

余弦相似度

一个向量空间中两个向量夹角的余弦值作为衡量两个个体之间差异的大小
余弦值接近 1，夹角趋于 0，表明两个向量越相似

案例：
- 步骤 0
  - 句子 A: 这只皮鞋号码大了，那只号码合适
  - 句子 B: 这只皮鞋号码不小，那只更合适
- 步骤 1: 分词
  - 句子 A: 这只 / 皮鞋 / 号码 / 大了，那只 / 号码 / 合适
  - 句子 B: 这只 / 皮鞋 / 号码 / 不 / 小，那只 / 更 / 合适
- 步骤 2: 列出所有词
  - 这只，皮鞋，号码，大了，那只，合适，不，小，更
- 步骤 3: 计算词频
  - 句子 A: 这只 1, 皮鞋 1, 号码 2, 大了 1, 那只 1, 合适 1, 不 0, 小 0, 更 0
  - 句子 B: 这只 1, 皮鞋 1, 号码 1, 大了 0, 那只 1, 合适 1, 不 1, 小 1, 更 1
- 步骤 4: 词频向量化
  - 句子 A: (1, 1, 2, 1, 1, 1, 0, 0, 0)
  - 句子 B: (1, 1, 1, 0, 1, 1, 1, 1, 1)
- 步骤 5: 套公式计算

文本相似度计算的处理流程

【依据】词袋模型 B.O.W
找出两篇文章的关键词
每篇文章各取出若干个关键词，合并成一个集合，计算每篇文章对于这个集合中的词的词频
生成两篇文章各自的词频向量
计算两个向量的余弦相似度，值越大越相似

TD-IDF

词频 TF

假设：如果一个词很重要，应该会在文章中多次出现

词频：一个词在文章中出现的次数
- 停用词：类似 “的”, “地”, “得” 对结果毫无帮助，必须过滤掉

反文档频率 IDF

假设：如果某个词比较少见，但是它在这篇文章中多次出现，那么它很可能反应了这篇文章的特性，正是我们所需要的关键词

在词频的基础上，赋予每一个词的权重，进一步体现该词的重要性
- 最少见的词（“的”、“是”、“在”）给予最小的权重
- 较常见的词（“国内”、“中国”、“报道”）给予较小的权重
- 较少见的词（“养殖”、“维基”、” 涨停 “）
将 TF 和 IDF 进行相乘，就得到了一个词的 TF-IDF 值，某个词对文章重要性越高，该值越大，于是排在前面的几个词，就是这篇文章的关键词。

计算步骤

【前提】准备语料库
计算 TF：某个词在文章中出现的次数
- 词频标准化（任选一种）
  - TF = 某个词在文章中出现的次数 / 文章的总次数
  - TF = 某个词在文章中出现的次数 / 该文章出现次数最多的词的出现次数
计算 IDF
- 标准化
  - IDF = log (语料库的文档总数 / ( 包含该词的文档数 + 1) )
计算 TF-IDF
- TF-IDF = 词频（TF）* 反文档频率（IDF）
- TF-IDF 与一个词在文档中的出现次数成正比，与包含该词的文档数成反比

【Demo】判断相似文章

步骤 1: 使用 TF-IDF 算法，找出两篇文章的关键词
步骤 2: 每篇文章各取出若干个关键词，合并成一个集合，计算每篇文章对于这个集合中的词的词频（为了避免文章长度的差异，可以使用相对词频）
步骤 3: 生成两篇文章各自的词频向量
步骤 4: 计算两个向量的余弦相似度，值越大越相似

【Demo】自动摘要

文章的信息都包含在句子中，有些句子包含的信息多，有些句子包含的信息少。“自动摘要” 就是要找出那些包含信息最多的句子。

句子的信息量用 “关键词” 来衡量。如果包含的关键词越多，就说明这个句子越重要。

只要关键词之间的距离小于 “门槛值”，它们就被认为处于同一个簇之中，如果两个关键词之间有超过 “门槛值” 个数以上的其他词，就可以把这两个关键词分在两个簇。

下一步，对于每个簇，都计算它的重要性分值。

簇的重要性 = （包含的关键词数量）^2 / 簇的长度

简化：不再区分 “簇”，只考虑句子包含的关键词

确定关键词集合
- 取有限的次数（如 Top-10）
- 如：按 TF-IDF 分数 > 0.7 截断
找出包含关键词的句子
把句子做排序，对每个句子划分等级
- 包含关键词越多越重要
- 关键词分越高越重要
把等级高的句子取出来，形成摘要

优点
- 简单快速，结果比较符合实际情况
缺点
- 单纯以 “词频” 做衡量标准，不够全面，有时重要的词可能出现的次数并不多
- 该算法无法体现词的位置信息，出现位置靠前的词与出现位置靠后的词，都被视为重要性相同，这是不正确的
  - 解决方法：对全文的第一段和每一段的第一句话给予较大权重。

【案例代码】TF-IDF

Map

map_tf.py

import sys

cnt = 0

for line in sys.stdin:
    ss = line.strip().split('\t')
    if len(ss) != 2:
        continue
    file_name, file_content = ss
    word_list = file_content.strip().split(' ')
    for word in word_list:
        cnt += 1

    file_count = file_name + ':' + str(cnt)

    for word in word_list:
        print('%s\t%s\t%s' % (file_count, word, 1))
    cnt = 0

Reduce

red_tf.py

import sys
import math

current_file = None
current_word = None
current_count = 0
sum = 0

for line in sys.stdin:
    ss = line.strip().split('\t')
    if len(ss) != 3:
        continue
    file_count, word, val = ss
    file_name, count = file_count.strip().split(':')
    if current_word is None:
        current_word = word
    if current_word != word:
        tf = math.log(float(sum) / float(current_count))
        print('%s\t%s\t%s' % (current_file, current_word, tf))
        current_word = word
        sum = 0
    sum += int(val)
    current_file = file_name
    current_count = count

tf = math.log(float(sum) / float(current_count))
print('%s\t%s\t%s' % (current_file, current_word, tf))

IDF

Map

map_idf.py

import sys


for line in sys.stdin:
    ss = line.strip().split('\t')
    if len(ss) != 2:
        continue
    file_name, file_content = ss
    word_list = file_content.strip().split(' ')

    word_set = set(word_list)

    for word in word_set:
        print('\t'.join([word, '1']))

Reduce

red_idf.py

import sys
import math

current_word = None
sum = 0

docs_cnt = 508

for line in sys.stdin:
    ss = line.strip().split('\t')
    if len(ss) != 2:
        continue
    word, val = ss
    if current_word is None:
        current_word = word
    if current_word != word:
        idf = math.log(float(docs_cnt) / (float(sum) + 1.0))
        print('\t'.join([current_word, str(idf)]))
        current_word = word
        sum = 0

    sum += int(val)

idf = math.log(float(docs_cnt) / (float(sum) + 1.0))
print('\t'.join([current_word, str(idf)]))

TF-IDF

Map

map.py

#!/usr/bin/python

import sys


def read_local_file_func(file):
    word_map = {}
    file_in = open(file, 'r')
    for line in file_in:
        ss = line.strip().split('\t')
        if len(ss) != 2:
            continue
        word, idf = ss
        word_map[word] = idf
    return word_map


def mapper_func(white_list_fd):
    word_map = read_local_file_func(white_list_fd)

    for line in sys.stdin:
        ss = line.strip().split('\t')
        if len(ss) != 3:
            continue
        file, word, tf = ss
        if word != "" and (word in word_map.keys()):
            idf = word_map[word]
            tfidf = float(float(tf) + float(idf))
            print("%s\t%s\t%s" % (file, tfidf, word))


if __name__ == "__main__":
    module = sys.modules[__name__]
    func = getattr(module, sys.argv[1])
    args = None
    if len(sys.argv) > 1:
        args = sys.argv[2:]
    func(*args)

Reduce

red.py

import sys

current_file = None
result = ''

for line in sys.stdin:
    ss = line.strip().split('\t')
    if len(ss) != 3:
        continue
    file, tfidf, word = ss
    if current_file is None:
        current_file = file
        result = current_file + '\t'
    if current_file != file:
        print(result[:-1])
        current_file = file
        result = current_file + '\t'

    result += word + ':' + tfidf + ' '
print(result[:-1])

【Hadoop Streaming 脚本】

#!/usr/bin/env bash

HADOOP_CMD="/usr/local/src/hadoop-2.8.5/bin/hadoop"
STREAM_JAR_PATH="/usr/local/src/hadoop-2.8.5/share/hadoop/tools/lib/hadoop-streaming-2.8.5.jar"

INPUT_FILE_PATH="/chapter02/01_tfidf/tfidf_input.data"
OUTPUT_PATH_TF="/chapter02/01_tfidf/output/python3/tf"
OUTPUT_PATH_IDF="/chapter02/01_tfidf/output/python3/idf"
OUTPUT_PATH_TFIDF="/chapter02/01_tfidf/output/python3/tfidf"
LOCAL_FILE_PATH="/mnt/hgfs/Code/chapter02/01_tfidf/tfidf_input.data"
UPLOAD_PATH="/chapter02/01_tfidf"


${HADOOP_CMD} fs -rm -r -skipTrash ${INPUT_FILE_PATH}
${HADOOP_CMD} fs -rm -r -skipTrash ${OUTPUT_PATH_TF}
${HADOOP_CMD} fs -rm -r -skipTrash ${OUTPUT_PATH_IDF}
${HADOOP_CMD} fs -rm -r -skipTrash ${OUTPUT_PATH_TFIDF}
${HADOOP_CMD} fs -mkdir -p ${UPLOAD_PATH}
${HADOOP_CMD} fs -put ${LOCAL_FILE_PATH} ${UPLOAD_PATH}

# Step 1. tf
${HADOOP_CMD} jar ${STREAM_JAR_PATH} \
    -D stream.num.map.output.key.fields=2 \
    -D num.key.fields.for.partition=1 \
    -files map_tf.py,red_tf.py \
    -input ${INPUT_FILE_PATH} \
    -output ${OUTPUT_PATH_TF} \
    -mapper "python map_tf.py" \
    -reducer "python red_tf.py" \
    -partitioner org.apache.hadoop.mapred.lib.KeyFieldBasedPartitioner \

# Step 2. idf
${HADOOP_CMD} jar ${STREAM_JAR_PATH} \
    -files map_idf.py,red_idf.py \
    -input ${INPUT_FILE_PATH} \
    -output ${OUTPUT_PATH_IDF} \
    -mapper "python map_idf.py" \
    -reducer "python red_idf.py" \

# Step 3. tf-idf
${HADOOP_CMD} jar ${STREAM_JAR_PATH} \
    -D stream.num.map.output.key.fields=2 \
    -D num.key.fields.for.partition=1 \
    -files map.py,red.py,"hdfs://master:9000/chapter02/01_tfidf/output/python3/idf/part-00000#WH"  \
    -input ${OUTPUT_PATH_TF} \
    -output ${OUTPUT_PATH_TFIDF} \
    -mapper "python map.py mapper_func WH" \
    -reducer "python red.py" \
    -partitioner org.apache.hadoop.mapred.lib.KeyFieldBasedPartitioner \

LCS

LCS：最长公共子序列 (Longest Common Subsequence)

注意区别最长公共子串 (Longest Common Substring)
- 最长公共子串要求连续
用于描述两段文字之间的 “相似度”
- 辨别抄袭，对一段文字进行修改后，计算改动前后文字的最长公共子序列。将除此子序列外的部分提取出来，用该方法判断修改的部分
可用于推荐结果过滤（相似项目）

解法 1：暴力穷举

假设字符串 X, Y 长度分别为 m, n

X 的一个子序列，即下标序列 {1, 2, …, m} 严格递增子序列

X 共有 2^m 个不同子序列
Y 共有 2^n 个不同子序列

时间复杂度: O (2^m * 2^n), 基本不可用

解法 2：动态规划 DP

使用二维数组 C [m, n]
C [i, j] 记录序列 Xi 和 Yj 的最长公共子序列的长度
- 当 i = 0 或 j = 0 时，空序列时 Xi 和 Yj 的最长公共子序列，故 C [i, j] = 0

【案例代码】LCS

Map

map.py

import sys


def cal_lcs(str_1, str_2):
    len_1 = len(str_1.strip())
    len_2 = len(str_2.strip())

    tmp = max(len_1, len_2) + 10

    len_vv = [[0] * tmp] * tmp

    for i in range(1, len_1 + 1):
        for j in range(1, len_2 + 1):
            if str_1[i - 1] == str_2[j - 1]:
                len_vv[i][j] = len_vv[i - 1][j - 1] + 1
            else:
                len_vv[i][j] = max(len_vv[i - 1][j], len_vv[i][j - 1])
    return float(float(len_vv[len_1][len_2] * 2) / float(len_1 + len_2))


for line in sys.stdin:
    ss = line.strip().split('\t')
    if len(ss) != 2:
        continue
    str_1, str_2 = ss

    cos_score = cal_lcs(str_1, str_2)
    print('%s\t%s\t%s' % (str_1, str_2, cos_score))

【Hadoop Streaming 脚本】

#!/usr/bin/env bash

HADOOP_CMD="/usr/local/src/hadoop-2.8.5/bin/hadoop"
STREAM_JAR_PATH="/usr/local/src/hadoop-2.8.5/share/hadoop/tools/lib/hadoop-streaming-2.8.5.jar"

INPUT_FILE_PATH="/chapter02/02_lcs/lcs_input.data"
OUTPUT_PATH="/chapter02/02_lcs/output/python3"
LOCAL_FILE_PATH="/mnt/hgfs/Code/chapter02/02_lcs/lcs_input.data"
UPLOAD_PATH="/chapter02/02_lcs"


${HADOOP_CMD} fs -rm -r -skipTrash ${INPUT_FILE_PATH}
${HADOOP_CMD} fs -rm -r -skipTrash ${OUTPUT_PATH}
${HADOOP_CMD} fs -mkdir -p ${UPLOAD_PATH}
${HADOOP_CMD} fs -put ${LOCAL_FILE_PATH} ${UPLOAD_PATH}

${HADOOP_CMD} jar ${STREAM_JAR_PATH} \
    -D mapreduce.job.reduces=0 \
    -D mapreduce.job.name=lcs_demo \
    -files map.py \
    -input ${INPUT_FILE_PATH} \
    -output ${OUTPUT_PATH} \
    -mapper "python map.py" \

中文分词

中文分词基础

背景

一段文字不仅仅在于字面上是什么，还在于怎么切分和理解

与英文不同，中文词之间没有空格，所以实现中文搜索引擎，比英文多了项分词的任务

分词粒度
- 粗粒度：推荐场景
- 细粒度：搜索场景（召回候选）
切分方法
- 01bit
  - 切开的开始位置对应位是 1，否则对应位是 0
  - “有 / 意见 / 分歧” 的 bit 内容是 11010
- 节点序列
  - 用分词节点序列表示切分方案
  - “有 / 意见 / 分歧” 的分词节点序列是 {0, 1, 3, 5}
- 基于词典匹配
  - 最大长度匹配
    - 前向查找
    - 后向查找（一般效果较好）
数据结构
- 为了提高查找效率，不要逐个匹配词典中的词
- 查找词典所占的时间可能占总的分词时间的 1/3 左右，为了保证切分速度，需要选择一个好的查找词典方法
- Trie 树常用于加速分词查找词典问题

###【Demo】Trie 树

正向
- 北京大学生活动中心
  - Root
    - 北 - 京
    - 北 - 京 - 大 - 学
    - 大 - 学 - 生
    - 学 - 生
    - 生 - 活
    - 活 - 动
    - 中 - 心
- 结果：北京大学 / 生活 / 动 / 中心
反向
- 北京大学生活动中心
  - Root
    - 心 - 中
    - 动 - 活
    - 活 - 生
    - 生 - 学
    - 生 - 学 - 大
    - 学 - 大 - 京 - 北
    - 京 - 北
- 结果：北京 / 大学生 / 活动 / 中心

【Demo】DAG 词图

例：广州本田雅阁汽车

【DAG】：{0: [0, 1, 3], 1: [1], 2: [2, 3, 5], 3: [3], 4: [4, 5], 5: [5], 6: [6, 7], 7: [7]}

概率语言模型

假设需要分出来的词在语料库和词表中都存在，最简单的方法是按词计算概率。

从统计思想的角度看，分词问题的输入是一个字串 C = c1, c2, …, cN，输出是一个词串 S = w1, w2, …, wM，其中 M <= N。对于一个特定的字符串 C，会有多个切分方案 S 对应，分词的任务就是从不同 S 中找出一个切分方案，使得 P (S|C) 值最大。

P (S|C) 就是由字符串 C 产生切分 S 的概率，也就是对输入字符串切分出最有可能的词序列。

基础

朴素贝叶斯：独立性假设

引例

C：南京市长江大桥

切分方案如下：

S1：南京市 / 长江 / 大桥
S2：南京 / 市长 / 江大桥

计算条件概率 P (S1|C) 和 P (S2|C)，然后根据 P (S1|C) 和 P (S2|C) 的值来决定选择 S1 还是 S2。

P (C) 是字串在语料库中出现的概率。

为容易实现，假设每个词之间的概率是上下文无关的

根据朴素贝叶斯公式

所以条件概率为

P (C) 为常数，只是一个用来归一化的固定值
在中文分词中，从词串恢复到汉字串仅有唯一的一种方式，所以 P (C|S) = 1
综上所述，比较 P (S1|C) 和 P (S2|C) 的大小就可以变成比较 P (S1) 和 P (S2) 的大小
- P (S1) = P (南京市，长江，大桥) = P (南京市) * P (长江) * P (大桥)
- P (S2) = P (南京，市长，江大桥) = P (南京) * P (市长) * P (江大桥)
- P (S1) > P (S2)，选择切分方案 S1

P (w) 就是这个词出现在语料库中的概率。因为函数 y = log (x) 单调递增，因为词的概率小于 1，所以取 log 后结果是负数。

取 log 为了防止向下溢出
结果由乘法转为加法，计算机处理起来速度更快

一元模型

对于不同的 S，M 的值都是不一样的，分出的词越多，概率越小（引例）

$在语料库中的出现次数语料库中的总次数$

于是

这个计算公式也叫做基于一元模型的计算公式，它综合考虑了切分出的词数和词频

N 元模型

给定一个词猜测下一个词。当给定 “NBA” 时，下一个词会联想到 “篮球”，但不太可能会联想到 “足球”

前后两词出现的概率是相互独立的的假设在实际中是不成立的。

N 元模型使用 n 个单词组成的序列来衡量切分方案的合理性，即概率的链规则。

P(S) = P(w1, w2, …, wM) = P(w1) * P(w2|w1) * P(w3|w1, w2) * … * P(wM|w1, w2, …, wM-1)

Jieba 分词工具

源码地址：https://github.com/fxsjy/jieba

简介

分词模式

精确模式：将句子最精确的分开，适合文本分析
全模式：句子中所有可以成词的词语都扫描出来，速度快，不能解决歧义
搜索引擎模式：在精确模式的基础上，对长词再次切分，提高召回

实现原理

语料库：词 + 词频 + 词性
基于 Trie 树结构前缀词典，使用前向遍历实现词图扫描，生成句子中汉字所有可能成词情况所构成的有向无环图 DAG
- Python 中实现的 trie 树是基于 dict 类型的数据结构而且 dict 中又嵌套 dict 类型，这样嵌套很深，导致内存耗费严重
- 前缀词典储存词语及其前缀，如 set(['数', '数据', '数据结', '数据结构'])。在句子中按字正向查找词语，在前缀列表中就继续查找，直到不在前缀列表中或超出句子范围。大约比原词库增加 40% 词条。
采用动态规划 DP 查找最大概率路径，找出基于词频的最大切分组合
对于未登录词，基于二元模型，采用基于汉字成词能力的 HMM 模型，使用 Viterbi 算法

具体步骤

给定待分词的句子，使用正则 (re_han) 获取匹配的中文字符 (和英文字符) 切分成的短语列表；
利用 get_DAG (sentence) 函数获得待切分句子的 DAG，首先检测 (check_initialized) 进程是否已经加载词库，若未初始化词库则调用 initialize 函数进行初始化，initialize 中判断有无已经缓存的前缀词典 cache_file 文件，若有相应的 cache 文件则直接使用 marshal.load 方法加载前缀词典，若无则通过 gen_pfdict 对指定的词库 dict.txt 进行计算生成前缀词典，到 jieba 进程的初始化工作完成后就调用 get_DAG 获得句子的 DAG；
根据 cut_block 指定具体的方法 (__cut_all,__cut_DAG,__cut_DAG_NO_HMM) 对每个短语使用 DAG 进行分词，如 cut_block=__cut_DAG 时则使用 DAG (查字典) 和动态规划，得到最大概率路径，对 DAG 中那些没有在字典中查到的字，组合成一个新的片段短语，使用 HMM 模型进行分词，也就是作者说的识别新词，即识别字典外的新词；
使用 python 的 yield 语法生成一个词语生成器，逐词语返回

"""
源码地址：
https://github.com/ustcdane/annotated_jieba/blob/master/jieba/__init__.py
"""

# jieba分词的主函数,返回结果是一个可迭代的 generator
    def cut(self, sentence, cut_all=False, HMM=True):
        '''
        The main function that segments an entire sentence that contains
        Chinese characters into seperated words.
        Parameter:
            - sentence: The str(unicode) to be segmented.
            - cut_all: Model type. True for full pattern, False for accurate pattern.
            - HMM: Whether to use the Hidden Markov Model.
        '''
        sentence = strdecode(sentence) # 解码为unicode
        # 不同模式下的正则
        if cut_all:
            re_han = re_han_cut_all
            re_skip = re_skip_cut_all
        else:
            re_han = re_han_default
            re_skip = re_skip_default

         # 设置不同模式下的cut_block分词方法
        if cut_all:
            cut_block = self.__cut_all
        elif HMM:
            cut_block = self.__cut_DAG
        else:
            cut_block = self.__cut_DAG_NO_HMM
        # 先用正则对句子进行切分
        blocks = re_han.split(sentence)
        for blk in blocks:
            if not blk:
                continue
            if re_han.match(blk): # re_han匹配的串
                for word in cut_block(blk):# 根据不同模式的方法进行分词
                    yield word
            else:# 按照re_skip正则表对blk进行重新切分
                tmp = re_skip.split(blk)# 返回list
                for x in tmp:
                    if re_skip.match(x):
                        yield x
                    elif not cut_all: # 精准模式下逐个字符输出
                        for xx in x:
                            yield xx
                    else: 
                        yield x

前缀词典

对应代码中 Tokenizer.FREQ 字典

def gen_pfdict(self, f_name):
    lfreq = {} # 字典存储  词条:出现次数
    ltotal = 0 # 所有词条的总的出现次数
    with open(f_name, 'rb') as f: # 打开文件 dict.txt 
        for lineno, line in enumerate(f, 1): # 行号,行
            try:
                line = line.strip().decode('utf-8') # 解码为Unicode
                word, freq = line.split(' ')[:2] # 获得词条 及其出现次数
                freq = int(freq)
                lfreq[word] = freq
                ltotal += freq
                for ch in xrange(len(word)):# 处理word的前缀
                    wfrag = word[:ch + 1]
                    if wfrag not in lfreq: # word前缀不在lfreq则其出现频次置0 
                        lfreq[wfrag] = 0
            except ValueError:
                raise ValueError(
                    'invalid dictionary entry in %s at Line %s: %s' % (f_name, lineno, line))
    return lfreq, ltotal

DAG

对一个 sentence DAG 是以 {key:list [i,j…], …} 的字典结构存储，key 是词的在 sentence 中的位置，list 存放的是 sentence 中以位置 key 开始的可能的词语的结束位置.

# DAG中是以{key:list,...}的字典结构存储
# key是字的开始位置
def get_DAG(self, sentence):
    self.check_initialized()
    DAG = {}
    N = len(sentence)
    for k in xrange(N):
        tmplist = []
        i = k
        frag = sentence[k]
        while i < N and frag in self.FREQ:
            if self.FREQ[frag]:
                tmplist.append(i)
            i += 1
            frag = sentence[k:i + 1]
        if not tmplist:
            tmplist.append(k)
        DAG[k] = tmplist
    return DAG

基于词频最大切分组合

有了词库 (dict.txt) 的前缀字典和待分词句子 sentence 的 DAG，使用动态规划方法，从后往前遍历，选择一个频度得分最大的一个切分组合。

#动态规划，计算最大概率的切分组合
   def calc(self, sentence, DAG, route):
       N = len(sentence)
       route[N] = (0, 0)
        # 对概率值取对数之后的结果(可以让概率相乘的计算变成对数相加,防止相乘造成下溢)
       logtotal = log(self.total)
       # 从后往前遍历句子 反向计算最大概率
       for idx in xrange(N - 1, -1, -1):
          # 列表推倒求最大概率对数路径
          # route[idx] = max([ (概率对数，词语末字位置) for x in DAG[idx] ])
          # 以idx:(概率对数最大值，词语末字位置)键值对形式保存在route中
          # route[x+1][0] 表示 词路径[x+1,N-1]的最大概率对数,
          # [x+1][0]即表示取句子x+1位置对应元组(概率对数，词语末字位置)的概率对数
           route[idx] = max((log(self.FREQ.get(sentence[idx:x + 1]) or 1) -
                             logtotal + route[x + 1][0], x) for x in DAG[idx])

例：广州本田雅阁汽车

P (车) = -8.80006921905【语料库 “车” 词频取 log】
P (汽) = -12.897543648【语料库 “汽” 词频取 log】
P (汽车) = -8.78007494718【语料库 “汽车” 词频取 log】
P (汽车) > P (汽) + P (车)，所以 Route 概率使用 P (汽车)
……

Route: {0: (-33.271126717488308, 1),
        1: (-32.231489259807965, 1),
        2: (-23.899234625632083, 5),
        3: (-31.523246813843940, 3),
        4: (-22.214895405024865, 5),
        5: (-19.008467873683230, 5),
        6: (-8.7800749471799175, 7),
        7: (-8.8000692190498415, 7),
        8: (0.0, '')}

隐马尔可夫模型 HMM

马尔可夫链

一个随机过程模型，它表述了一系列可能的事件，在这个系列当中每一个事件的概率仅依赖于前一个事件。

参数
- 状态：由数字表示，假设共有 M 个
- 初始概率：
- 状态转移概率：

例子：天气
- 状态：{晴天，雨天，多云，……}
- 初始概率：P (晴天), P (雨天), ……
- 状态转移概率：P (晴天 | 雨天), P (雨天 | 多云), ……
参数估计
- 最大似然法
  - 初始概率：P (S1 = k) = (k 作为序列开始的次数) / (观测序列总数)
  - 状态转移概率：P (St + 1 = l |St = k) = (l 紧跟 k 出现的次数) / (k 出现的总次数)
小结
- 马尔可夫链是对一个序列数据建模

隐马尔可夫模型

HMM 是一个关于时序的概率模型，它的变量分为两组：

状态变量 (隐变量)：由马尔可夫链随机生成
观测变量：状态序列每个状态对应生成一个观测结果

状态变量和观测变量各自都是一个时间序列，每个状态 / 观测值都和一个时刻相对应

假设 1：假设隐藏的马尔可夫链在任意时刻 tt 的状态只依赖于前一个时刻（t − 1 时）的状态，与其他时刻的状态及观测无关，也与时刻 t 无关。

假设 2：假设任意时刻的观测只依赖于该时刻的马尔可夫链状态，与其他观测及状态无关。

参数
- 状态：由数字表示，假设共有 M 个，状态序列 S
- 观测：由数字表示，假设共有 N 个，观测序列 O
- 状态转移概率： $由表示通常记作矩阵$
- 发射概率： $通常记作矩阵$
- 初始概率： $由表示$

HMM 解决三类问题

概率计算问题（又称评价问题）
- 已知：
  - 模型
  - 观测序列 O
- 求解：
  - 给定观测序列，求它和评估模型之间的匹配度
- 方案：
  - 前向 - 后向算法
预测问题（又称解码问题）
- 已知：
  - 模型
  - 观测序列 O
- 求解：
  - 给定观测序列，求最有可能与之对应的状态序列 S
- 方案：
  - Viterbi 算法
学习问题（又称训练问题）
- 已知：
  - 观测序列 O
  - 或许会给与之对应的状态序列 S
- 求解：
  - 训练模型，使其最大，最好地描述观测数据
- 方案：
  - 有监督 / 无监督

相关文章：52nlp

Jieba HMM

参数
- 初始概率
  - BEMS 位置信息
  - 词性
  - 例: {('B', 'mq'): -6.78695300139688, ……}
- 转移概率
  - 例: {('B', 'ad'): {('E', 'ad'): -0.0007479013978476627}, ……}
- 发射概率
  - 例: {('B', 'df'): {u' 不 ': 0.0}……}
Viterbi 算法实现

#状态转移矩阵，比如B状态前只可能是E或S状态  
PrevStatus = {  
    'B':('E','S'),  
    'M':('M','B'),  
    'S':('S','E'),  
    'E':('B','M')  
}  
def viterbi(obs, states, start_p, trans_p, emit_p):
    V = [{}]  # 状态概率矩阵  
    path = {}
    for y in states:  # 初始化状态概率
        V[0][y] = start_p[y] + emit_p[y].get(obs[0], MIN_FLOAT)
        path[y] = [y] # 记录路径
    for t in xrange(1, len(obs)):
        V.append({})
        newpath = {}
        for y in states:
            em_p = emit_p[y].get(obs[t], MIN_FLOAT)
            # t时刻状态为y的最大概率(从t-1时刻中选择到达时刻t且状态为y的状态y0)
            (prob, state) = max([(V[t - 1][y0] + trans_p[y0].get(y, MIN_FLOAT) + em_p, y0) for y0 in PrevStatus[y]])
            V[t][y] = prob
            newpath[y] = path[state] + [y] # 只保存概率最大的一种路径 
        path = newpath 
    # 求出最后一个字哪一种状态的对应概率最大，最后一个字只可能是两种情况：E(结尾)和S(独立词)  
    (prob, state) = max((V[len(obs) - 1][y], y) for y in 'ES')