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

写在前头

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

贝叶斯定理

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

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

来自百度搜索

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

贝叶斯分类器

在生活,经常会进行各种各样的分类,比如说文档归类、网页分类等,使用的分类方法称之为分类器。大多数分类器都是基于贝叶斯定理展开的,大致过程如下:

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

来自博客园截图

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

数据集的描述

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

菜的标题 网站的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


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