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

TF-IDF, LCS, HMM


ole-witt-vp7gEXuon08-unsplash

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: 套公式计算

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

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

TD-IDF

词频TF

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

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

反文档频率IDF

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

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

计算步骤

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

【Demo】判断相似文章

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

【Demo】自动摘要

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

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

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

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

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

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

  1. 确定关键词集合
    • 取有限的次数(如Top-10)
    • 如:按TF-IDF分数 > 0.7截断
  2. 找出包含关键词的句子
  3. 把句子做排序,对每个句子划分等级
    • 包含关键词越多越重要
    • 关键词分越高越重要
  4. 把等级高的句子取出来,形成摘要
  • 优点
    • 简单快速,结果比较符合实际情况
  • 缺点
    • 单纯以“词频”做衡量标准,不够全面,有时重要的词可能出现的次数并不多
    • 该算法无法体现词的位置信息,出现位置靠前的词与出现位置靠后的词,都被视为重要性相同,这是不正确的
      • 解决方法:对全文的第一段和每一段的第一句话给予较大权重。

【案例代码】TF-IDF

  1. TF

    1. Map

      map_tf.py
      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      12
      13
      14
      15
      16
      17
      18
      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
    2. Reduce

      red_tf.py
      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      12
      13
      14
      15
      16
      17
      18
      19
      20
      21
      22
      23
      24
      25
      26
      27
      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))
  2. IDF

    1. Map

      map_idf.py
      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      12
      13
      14
      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']))
    2. Reduce

      red_idf.py
      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      12
      13
      14
      15
      16
      17
      18
      19
      20
      21
      22
      23
      24
      25
      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)]))
  3. TF-IDF

    1. Map

      map.py
      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      12
      13
      14
      15
      16
      17
      18
      19
      20
      21
      22
      23
      24
      25
      26
      27
      28
      29
      30
      31
      32
      33
      34
      35
      36
      37
      38
      #!/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)
    2. Reduce

      red.py
      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      12
      13
      14
      15
      16
      17
      18
      19
      20
      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])
  4. 【Hadoop Streaming脚本】

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    #!/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

  1. Map

    map.py
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    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))
  2. 【Hadoop Streaming脚本】

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    #!/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]}

DAG

概率语言模型

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

从统计思想的角度看,分词问题的输入是一个字串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算法

具体步骤

  1. 给定待分词的句子, 使用正则(re_han)获取匹配的中文字符(和英文字符)切分成的短语列表;
  2. 利用get_DAG(sentence)函数获得待切分句子的DAG,首先检测(check_initialized)进程是否已经加载词库,若未初始化词库则调用initialize函数进行初始化,initialize中判断有无已经缓存的前缀词典cache_file文件,若有相应的cache文件则直接使用 marshal.load 方法加载前缀词典,若无则通过gen_pfdict对指定的词库dict.txt进行计算生成前缀词典,到jieba进程的初始化工作完成后就调用get_DAG获得句子的DAG;
  3. 根据cut_block指定具体的方法(__cut_all,__cut_DAG,__cut_DAG_NO_HMM)对每个短语使用DAG进行分词 ,如cut_block=__cut_DAG时则使用DAG(查字典)和动态规划, 得到最大概率路径, 对DAG中那些没有在字典中查到的字, 组合成一个新的片段短语, 使用HMM模型进行分词, 也就是作者说的识别新词, 即识别字典外的新词;
  4. 使用python的yield 语法生成一个词语生成器, 逐词语返回
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
"""
源码地址:
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

jieba

前缀词典

对应代码中Tokenizer.FREQ字典

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
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开始的可能的词语的结束位置.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
# 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,使用动态规划方法,从后往前遍历,选择一个频度得分最大的一个切分组合。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#动态规划,计算最大概率的切分组合
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(汽车)
  • ……
1
2
3
4
5
6
7
8
9
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, '')}

route

隐马尔可夫模型HMM

马尔可夫链

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

  • 参数
    • 状态:由数字表示,假设共有M个
    • 初始概率:$\pi{k}=P\left(S{1}=k\right) \quad \mathrm{k}=1,2, \ldots, \mathrm{M}$
    • 状态转移概率:$a{k, l}=P\left(S{t+1}=l | S_{t}=k\right) \quad \mathrm{k}, 1=1,2, \ldots, \mathrm{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

    • 状态转移概率:$由a_{k, l}表示, 通常记作矩阵A$

    • 发射概率:$b{k}(u)=\mathrm{P}\left(O{t}=u | S_{t}=k\right) \quad u=1,2, \ldots, N ; k=1,2, \dots, M, 通常记作矩阵B$

    • 初始概率:$由\pi_{k}表示$

HMM

HMM解决三类问题
  • 概率计算问题(又称评价问题)

    • 已知:

      • 模型$\lambda=[A, B, \pi]$
      • 观测序列O
    • 求解:

      • 给定观测序列,求它和评估模型之间的匹配度$P(O | \lambda)$
    • 方案:
      • 前向-后向算法
  • 预测问题(又称解码问题)

    • 已知:
      • 模型$\lambda=[A, B, \pi]$
      • 观测序列O
    • 求解:
      • 给定观测序列,求最有可能与之对应的状态序列S
    • 方案:
      • Viterbi算法
  • 学习问题(又称训练问题)

    • 已知:
      • 观测序列O
      • 或许会给与之对应的状态序列S
    • 求解:
      • 训练模型$\lambda=[A, B, \pi]$,使其$P(O | \lambda)$最大,最好地描述观测数据
    • 方案:
      • 有监督/无监督

相关文章:52nlp

Jieba HMM

  • 参数

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
#状态转移矩阵,比如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')



Alessa0 wechat
(> <)  中国儿童少年基金会  &  Alessa0.cn  谢谢您的帮助!
--------- 本文结束 感谢您的阅读 ---------

本文标题:BigData复习笔记02:TFIDF, LCS与中文分词

文章作者:Alessa0

发布时间:2019年07月24日 - 19:07

最后更新:2019年08月05日 - 15:08

原始链接:https://alessa0.cn/posts/944875b5/

版权声明: CC BY-NC-ND 4.0 转载请保留原文链接及作者。

0%