Brains


on 朴素贝叶斯分类器的实现, NLP

朴素贝叶斯分类器

因为工程实践里需要实现语义分析的功能,关于如何语义分析,我也是一头雾水。最近花了点时间,依据贝叶斯原理,针对工程实践,写了一个分类器,效果还阔以~~ 哈哈

写在前头

在研一上学期的时候,学院里分配了一个工程实践项目,我所在的4人组选了基于语义的搜索引擎这个课题,项目主页:https://github.com/willstudy/SearchEngine。目前项目进展到语义分析模块了,我就查阅了相关资料,然后根据项目的数据集,定制了一个贝叶斯分类器。

贝叶斯定理

老是说我第一眼看到这个定理的时候,完全没有任何印象。其实这个定理最早出现在本科所学的概率论中的,好惭愧,竟然被我忘光了。。。

贝叶斯定理主要是:当知道A发生的情况下,B发生的概率* P( B | A) 时, 求 B发生的条件下,A发生的概率 P( A | B ) *,其公式为:

来自百度搜索

这个公式在生活很有用,我们在不知不觉中可能就用到了它。比如说,在街上看到一个黑种人,我们很自然的联想到,他可能来自非洲。在得出判断的过程中,我们就用到了贝叶斯分类器的思想。

贝叶斯分类器

在生活,经常会进行各种各样的分类,比如说文档归类、网页分类等,使用的分类方法称之为分类器。大多数分类器都是基于贝叶斯定理展开的,大致过程如下: - 确定需要分出的类别:Y1,Y2,Y3... - 对目标分类对象进行特征(X1,X2,X3...)提取 - 计算这些特征的先验概率,即P(X1|Y1),P(X2|Y1),P(X1|Y2)... - 根据贝叶斯公式,计算待分类的后验概率,即P(Y1|X1,X2,X3..)

贝叶斯计算后验概率的公式如下:

来自博客园截图

这里我会根据工程实践中的数据集,进行一步步的分析。

数据集的描述

我的这个工程实践,是基于语义的搜索引擎,主要做关于美食做法方面的搜索。其所有的数据都是从美食天下网爬到的数据,在此给贵网站带来的不便,致以深深的歉意。其中每条记录主要包含如下字段:

菜的标题 网站的URL 菜的介绍 菜图片的URL 菜的食材 菜的类型 菜的做法步骤 菜的小窍门

大约共3.5W条记录。

分类器的原型

老师说过,软件工程的第一步是需求分析。那我第一步从需求分析写起。项目需要的分类器的需求描述如下:
用户输入一句话,比如:

西红柿炒鸡蛋

分类器能判断用户是想检索菜名类别、食材类别还是工艺类别。因为我选用的分词工具对这句话分割的结果如下:

西红柿 炒 鸡蛋

如果只是简单的字符串匹配,那么它很可能既属于菜名,又可能属于工艺,又可能属于食材。这时候就需要一个分类器,对分词的结果进行分类处理。

所以这个分类器的输入是:分词后的词组,输出是: 类别

分类器的设计

根据上文中提到的贝叶斯分类器的设计步骤,我做了如下工作:

1、类别确定

分类器的类别:菜名食材工艺

2、特征提取

我这里提取的特征,是对分词工具一些简单的修改,然后使用它分词之后的结果作为特征。比如
西红柿炒鸡蛋 的特征为 西红柿 炒 鸡蛋,而 排毒养颜的菜 的 特征为 排毒 养颜 菜

3、计算先验概率

这一步花了我很多时间,首先,我用python把之前爬到的3.5W条记录,再次处理了一下。利用python把每个字段对应的信息提取出来。比如说,我共提取了36924条菜名、食材、工艺,分别单独存放在 title.txt、material.txt、type.txt 中。

然后利用分词工具对上述三个文件 title.txt、material.txt、type.txt 再次处理了一下,把它们分割成词条,分别单独存放在了 splite_title.txt、splite_material.txt、splite_type.txt 中。

然后这一步比较简单,我利用Python统计,上述分割后的文件中词条的词频,然后分别除以每个类别的词条总数。用python处理 split_title.txt 文件描述如下:

#coding=utf-8
from __future__ import division  
import os  
import sys  
import re

reload(sys)  
sys.setdefaultencoding('utf-8')

words = []  
dictory = {}  
word_set = []  
new_dict = {}

file_read = open('split_material.txt', 'r')  
file_write = open('percent_material.txt', 'w+')

for line in file_read.readlines():  
    line = line.strip('\n')
    words.append(line)

word_set = set(words)   # exclude these repeated keyWords  
length = len(words)  
print length

for item in word_set :  
    dictory[item] = words.count(item) / length    
new_dict = sorted( dictory.iteritems(), key = lambda d:d[1], reverse = True ) # sort by value

for key,value in new_dict:  
    file_write.write( key + ":" + str(value) )
    file_write.write( '\n' )

最后会生成 percent_title.txt percent_material.txt percent_type.txt 文件。
最后一步,我这三个概率文件归并在一起,形成最后的先验概率集合。用python描述如下:

#coding=utf-8
from __future__ import division  
import os  
import sys

reload(sys)  
sys.setdefaultencoding('utf-8')

file_title = open('percent_title.txt', 'r')  
file_material = open('percent_material.txt', 'r')  
file_type = open('percent_type.txt', 'r')  
file_gather = open('gather.txt', 'w+')

title_num = 123320  
material_num = 292582  
type_num = 495875

laplace_title = 1 / ( title_num * 2 )  
laplace_material = 1 / ( material_num * 2 )  
laplace_type = 1 / ( type_num * 2 )

dictory_title = {}  
dictory_material = {}  
dictory_type = {}

for line in file_title.readlines():

    line = line.strip('\n')
    result = line.split(':')
    dictory_title[result[0]] = result[1]

file_title.close()

for line in file_material.readlines():

    line = line.strip('\n')
    result = line.split(':')
    dictory_material[result[0]] = result[1]

file_material.close()

for line in file_type.readlines():

    line = line.strip('\n')
    result = line.split(':')
    dictory_type[result[0]] = result[1]

file_type.close()

dictory = {}

for key in dictory_title:

    percent = []

    if dictory.has_key( key ):
        pass
    else :
        percent.append(dictory_title[key])
        percent.append( str(laplace_material) )
        percent.append( str(laplace_type) )

        dictory[key] = percent

for key in dictory_material:

    percent = []

    if dictory.has_key(key):
        percent = dictory[key]
        percent[1] = dictory_material[key]
    else:
        percent.append( str(laplace_title) )
        percent.append(dictory_material[key])
        percent.append( str(laplace_type) )

    dictory[key] = percent

for key in dictory_type:

    percent = []

    if dictory.has_key( key ):
        percent = dictory[key]
        percent[2] = dictory_type[key]
    else:
        percent.append( str(laplace_title) )
        percent.append( str(laplace_material) )
        percent.append(dictory_type[key])

    dictory[key] = percent

for key in dictory:

    file_gather.write(key + ':')

    for item in dictory[key]:

        file_gather.write( item + ' ' )

    file_gather.write('\n')

file_gather.close()  

有一种情况需要特别说明:当一个词条只出现在一个类别,在其他类别没有出现时,它的先验概率计算:

laplace_title = 1 / ( title_num * 2 )  
laplace_material = 1 / ( material_num * 2 )  
laplace_type = 1 / ( type_num * 2 )  

没错,这就是我采用的Laplace平滑方法。

4、计算后验概率

利用贝叶斯公式,分别求出 菜名、食材、工艺的后验概率。这一步我用PHP语言写的,因为我们的分词工具是SCWS的PHP扩展,半推半就的使用PHP写出了这个分类器。其PHP语言描述如下:

<?php  
/*
 *  核心模块:基于贝叶斯公式,定制的一个分类器,经测试准度较高
 */
function gather( $str )  
{
    chdir("./lib/nlp/db");

    $hand_read = fopen( "gather.txt", 'r' );

    if( !$hand_read )
    {
        exit("file gather.txt open failed!");
    }

    $gather_container = array();
    /* 初始化数据集 */
    while( !feof($hand_read) )
    {
        $buffer = fgets( $hand_read, 1024 );
        $buffer = trim( $buffer , "\n" );
        list( $name, $title_proba, $material_proba, $type_proba ) = split( '[ :]',$buffer );

        $temp = array();

        $temp['title'] = $title_proba;
        $temp['material'] = $material_proba;
        $temp['type'] = $type_proba;

        $gather_container[$name] = $temp;
    }
    /* 每个类型的总条数 */
    $title_num = 123320;
    $material_num = 292582;
    $type_num = 495875;

    $total = $title_num + $material_num + $type_num;
    /* 这里的比重暂时没想好,越小,说明权重越大 */
    /*
    $title_percent = $total / $title_num ;
    $material_percent = $total / $material_num ;
    $type_percent = $total / $type_num ;
    */
    $title_percent = 0.3;
    $material_percent = 0.3;
    $type_percent = 0.4;

    $title = $title_percent;
    $material = $material_percent;
    $type = $type_percent;
    $base = 2.7183;

    $num = count( $str );

    for( $i = 0; $i < $num; $i++ )
    {
        $word = $str[$i];

        if( array_key_exists( $word, $gather_container ) )
        {
            $probe_title = $gather_container[$word]['title'];
            $probe_material = $gather_container[$word]['material'];
            $probe_type = $gather_container[$word]['type'];
        }
        else
        {
            $probe_title = 1 / ( $title_num * 2 ) ;
            $probe_material = 1 / ( $material_num * 2 ) ;
            $probe_type = 1 / ( $type_num * 2 ) ;
        }

        $title *= log( $probe_title , $base );
        $material *= log( $probe_material, $base );
        $type *= log( $probe_type, $base );
    }
    /* 值越小,说明越趋近某个分类 */
    $title = abs( $title );
    $material = abs( $material );
    $type = abs( $type );

    $result = array();

    $min_probe = min( $title, $material, $type );
    /* 如果概率相差不大,就可以加入此类型中 */
    if( $title / $min_probe <= 2 )
    {
        $result['title'] = $title;
    }
    if( $material / $min_probe <= 2 )
    {
        $result['material'] = $material;
    }
    if( $type / $min_probe <= 2 )
    {
        $result['type'] = $type;
    }

    fclose( $hand_read );

    return $result;
}
?>

具体做法把先验概率加载进内存,分别查出每个特征的先验概率 probe_title probe_material probe_type,然后根据每个类别的初始比重,进行连乘,分别求出每个类别的概率,描述如下:

if( array_key_exists( $word, $gather_container ) )  
{
  $probe_title = $gather_container[$word]['title'];
  $probe_material = $gather_container[$word]['material'];
  $probe_type = $gather_container[$word]['type'];
}
else  
{
  $probe_title = 1 / ( $title_num * 2 ) ;
  $probe_material = 1 / ( $material_num * 2 ) ;
  $probe_type = 1 / ( $type_num * 2 ) ;
}

$title *= log( $probe_title , $base );
$material *= log( $probe_material, $base );
$type *= log( $probe_type, $base );

这个分类器遇到了一些问题,我会在下部分提出,并写下我的解决方法。

分类器存在的问题及我的解决方案

关于Laplace平滑

若一个特征词只出现在某个分类中,比如说 金玉满堂,它只出现在菜名中,正常的计算结果概率为:

金玉满堂:6.48718780409e-05 0.00 0.00

这样的计算会使一旦出现这个词,其他种类的概率立马变成0了,因为与0相乘,结果为0。这大大的降低了分类器的准确性。

解决措施:将其他类没有出现该词条的概率设为 * 1 / ( 2 * 词条总数 ) ,也称为Laplace平滑。最后 *金玉满堂 的先验概率如下:

金玉满堂:6.48718780409e-05 1.70892262682e-06 1.00831862869e-06

关于乘积指数下溢的情况

因为词条种类共仅92W条,所以有的词条概率很低,那么它们进行贝叶斯公式的相乘时,就会造成丢失精度的情况。这种情况下我效仿了一位博主的做法,先对先验概率进行取自然对数,然后进行相乘。

关于特征值之间的独立性

因为贝叶斯公式要求各个特征之间是相互独立的,也就是说 西红柿 炒 鸡蛋 它们之间是没有关系的。然而实际上是有关系,它们之间的关联度,很大程度上觉得了分类结果。这里我的优化措施是,对最后的分类概率再进行平滑,若之间的概率相差不超过2倍,我就多返回一个分类,这样在丢失精度的情况下,同时保证了语义分析。

写在最后

这个分类器难度在于,对实际问题的抽象。如果知道了哪些是我们需要的特征值,怎么计算先验概率,那么剩下的工作就是数据的处理了。这个贝叶斯分类器效果其实还不错,值越小,说明越接近某个分类。大部分情况下,能得出我想要的分类结果。如下图所示:

分类结果 分类结果 分类结果

为了写这个分类器,连续写了3天代码,脸上长了几个痘痘。。。最后感谢那些提供我资料来源的博主们~~

参考

算法杂货铺——分类算法之朴素贝叶斯分类(Naive Bayesian classification)
朴素贝叶斯分类及其在文本分类、垃圾邮件检测中的应用
Naive Bayes classifier

comments powered by Disqus

纸上得来终觉浅,绝知此事要躬行~