基于朴素贝叶斯分类器的文本分类算法（上）
http://www.cnblogs.com/phinecos/archive/2008/10/21/1316044.html
基于朴素贝叶斯分类器的文本分类算法（下）
http://www.cnblogs.com/phinecos/archive/2008/10/21/1316044.html
转载请保留作者信息：
作者：phinecos（洞庭散人）
Blog：http://phinecos.cnblogs.com/
Email：[email protected]
Preface
本文缘起于最近在读的一本书-- Tom M.Mitchell的《机器学习》,书中第6章详细讲解了贝叶斯学习的理论知识，为了将其应用到实际中来，参考了网上许多资料，从而得此文。文章将分为两个部分，第一部分将介绍贝叶斯学习的相关理论(如果你对理论不感兴趣，请直接跳至第二部分<<基于朴素贝叶斯分类器的文本分类算法（下）>>)。第二部分讲如何将贝叶斯分类器应用到中文文本分类，随文附上示例代码。
Introduction
我们在《概率论和数理统计》这门课的第一章都学过贝叶斯公式和全概率公式，先来简单复习下：
条件概率
定义 设A, B是两个事件，且P(A)>0 称P(B∣A)=P(AB)/P(A)为在条件A下发生的条件事件B发生的条件概率。
乘法公式 设P(A)>0 则有P(AB)=P(B∣A)P(A)
全概率公式和贝叶斯公式
定义 设S为试验E的样本空间，B1, B2, …Bn为E的一组事件，若BiBj=Ф, i≠j, i, j=1, 2, …,n; B1∪B2∪…∪Bn=S则称B1, B2, …, Bn为样本空间的一个划分。
定理 设试验E的样本空间为，A为E的事件，B1, B2, …,Bn为的一个划分，且P(Bi)>0 (i=1, 2, …n)，则P(A)=P(A∣B1)P(B1)+P(A∣B2)+ …+P(A∣Bn)P(Bn)称为全概率公式。
定理 设试验俄E的样本空间为S，A为E的事件，B1, B2, …,Bn为的一个划分，则
P(Bi∣A)=P(A∣Bi)P(Bi)/∑P(B｜Aj)P(Aj)=P(B｜Ai)P(Ai)/P(B)
称为贝叶斯公式。说明：i，j均为下标，求和均是1到n
下面我再举个简单的例子来说明下。
示例1
考虑一个医疗诊断问题，有两种可能的假设：（1）病人有癌症。（2）病人无癌症。样本数据来自某化验测试，它也有两种可能的结果：阳性和阴性。假设我们已经有先验知识：在所有人口中只有0.008的人患病。此外，化验测试对有病的患者有98%的可能返回阳性结果，对无病患者有97%的可能返回阴性结果。
上面的数据可以用以下概率式子表示：
P(cancer)=0.008,P(无cancer)=0.992
P(阳性|cancer)=0.98,P(阴性|cancer)=0.02
P(阳性|无cancer)=0.03，P(阴性|无cancer)=0.97
假设现在有一个新病人，化验测试返回阳性，是否将病人断定为有癌症呢？我们可以来计算极大后验假设：
P(阳性|cancer)p(cancer)=0.98*0.008 = 0.0078
P(阳性|无cancer)*p(无cancer)=0.03*0.992 = 0.0298
因此，应该判断为无癌症。
贝叶斯学习理论
贝叶斯是一种基于概率的学习算法，能够用来计算显式的假设概率，它基于假设的先验概率，给定假设下观察到不同数据的概率以及观察到的数据本身（后面我们可以看到，其实就这么三点东西，呵呵）。
我们用P(h)表示没有训练样本数据前假设h拥有的初始概率，也就称为h的先验概率，它反映了我们所拥有的关于h是一个正确假设的机会的背景知识。当然如果没有这个先验知识的话，在实际处理中，我们可以简单地将每一种假设都赋给一个相同的概率。类似，P(D)代表将要观察的训练样本数据D的先验概率（也就是说，在没有确定某一个假设成立时D的概率）。然后是P(D/h)，它表示假设h成立时观察到数据D的概率。在机器学习中，我们感兴趣的是P(h/D),也就是给定了一个训练样本数据D,判断假设h成立的概率，这也称之为后验概率，它反映了在看到训练样本数据D后假设h成立的置信度。（注：后验概率p(h/D)反映了训练数据D的影响，而先验概率p(h)是独立于D的）。
P(h|D) = P(D|h)P(h)/p(D),从贝叶斯公式可以看出，后验概率p(h/D)取决于P(D|h)P(h)这个乘积，呵呵，这就是贝叶斯分类算法的核心思想。我们要做的就是要考虑候选假设集合H，并在其中寻找当给定训练数据D时可能性最大的假设h（h属于H）。
简单点说，就是给定了一个训练样本数据（样本数据已经人工分类好了），我们应该如何从这个样本数据集去学习，从而当我们碰到新的数据时，可以将新数据分类到某一个类别中去。那可以看到，上面的贝叶斯理论和这个任务是吻合的。
朴素贝叶斯分类
也许你觉得这理论还不是很懂，那我再举个简单的例子，让大家对这个算法的原理有个快速的认识。（注：这个示例摘抄自《机器学习》这本书的第三章的表3-2.）
假设给定了如下训练样本数据，我们学习的目标是根据给定的天气状况判断你对PlayTennis这个请求的回答是Yes还是No。
| Day | Outlook | Temperature | Humidity | Wind | PlayTennis |
| D1 | Sunny | Hot | High | Weak | No |
| D2 | Sunny | Hot | High | Strong | No |
| D3 | Overcast | Hot | High | Weak | Yes |
| D4 | Rain | Mild | High | Weak | Yes |
| D5 | Rain | Cool | Normal | Weak | Yes |
| D6 | Rain | Cool | Normal | Strong | No |
| D7 | Overcast | Cool | Normal | Strong | Yes |
| D8 | Sunny | Mild | High | Weak | No |
| D9 | Sunny | Cool | Normal | Weak | Yes |
| D10 | Rain | Mild | Normal | Weak | Yes |
| D11 | Sunny | Mild | Normal | Strong | Yes |
| D12 | Overcast | Mild | High | Strong | Yes |
| D13 | Overcast | Hot | Normal | Weak | Yes |
| D14 | Rain | Mild | High | Strong | No |
可以看到这里样本数据集提供了14个训练样本，我们将使用此表的数据，并结合朴素贝叶斯分类器来分类下面的新实例：
(Outlook = sunny,Temprature = cool,Humidity = high,Wind = strong)
我们的任务就是对此新实例预测目标概念PlayTennis的目标值(yes或no).
由上面的公式可以得到：
可以得到：
P(PlayTennis =yes) = 9/14 = 0.64,P(PlayTennis=no)=5/14 = 0.36
P(Wind=Stong| PlayTennis =yes)=3/9=0.33,p(Wind=Stong| PlayTennis =no)=3/5 = 0.6
其他数据类似可得，代入后得到：
P(yes)P(Sunny|yes)P(Cool|yes)P(high|yes)P(Strong|yes) = 0.0053
P(no)P(Sunny|no)P(Cool|no)P(high|no)P(Strong|no)=0.0206
因此应该分类到no这一类中。
贝叶斯文本分类算法
好了，现在开始进入本文的主旨部分：如何将贝叶斯分类器应用到中文文本的分类上来？
根据联合概率公式（全概率公式）
M——训练文本集合中经过踢出无用词去除文本预处理之后关键字的数量。
作者：洞庭散人
出处：http://phinecos.cnblogs.com/
本博客遵从 Creative Commons Attribution 3.0 License ，若用于非商业目的，您可以自由转载，但请保留原作者信息和文章链接URL。
源代码下载：NaviveBayesClassify.rar
Preface
文本的分类和聚类是一个比较有意思的话题，我以前也写过一篇blog《基于K-Means的文本聚类算法》，加上最近读了几本数据挖掘和机器学习的书籍，因此很想写点东西来记录下学习的所得。
在本文的上半部分《基于朴素贝叶斯分类器的文本分类算法（上）》一文中简单介绍了贝叶斯学习的基本理论，这一篇将展示如何将该理论运用到中文文本分类中来，具体的文本分类原理就不再介绍了，在上半部分有，也可以参见代码的注释。
文本特征向量
文本特征向量可以描述为文本中的字／词构成的属性。例如给出文本：
Good good study,Day day up.
可以获得该文本的特征向量集：{ Good, good, study, Day, day , up.}
朴素贝叶斯模型是文本分类模型中的一种简单但性能优越的的分类模型。为了简化计算过程，假定各待分类文本特征变量是相互独立的，即“朴素贝叶斯模型的假设”。相互独立表明了所有特征变量之间的表述是没有关联的。如上例中，[good]和[study]这两个特征变量就是没有任何关联的。
在上例中，文本是英文，但由于中文本身是没有自然分割符（如空格之类符号），所以要获得中文文本的特征变量向量首先需要对文本进行中文分词
中文分词
这里采用极易中文分词组件，这个中文分词组件可以免费使用，提供Lucene接口，跨平台，性能可靠。
package com.vista;
import java.io.IOException;
import jeasy.analysis.MMAnalyzer;
public class ChineseSpliter
{
public static String split(String text,String splitToken)
{
String result = null ;
MMAnalyzer analyzer = new MMAnalyzer();
try
{
result = analyzer.segment(text, splitToken);
}
catch (IOException e)
{
e.printStackTrace();
}
return result;
}
}
停用词处理
去掉文档中无意思的词语也是必须的一项工作,这里简单的定义了一些常见的停用词，并根据这些常用停用词在分词时进行判断。
package com.vista;
public class StopWordsHandler
{
private static String stopWordsList[] = { " 的 " , " 我们 " , " 要 " , " 自己 " , " 之 " , " 将 " , " “ " , " ” " , " ， " , " （ " , " ） " , " 后 " , " 应 " , " 到 " , " 某 " , " 后 " , " 个 " , " 是 " , " 位 " , " 新 " , " 一 " , " 两 " , " 在 " , " 中 " , " 或 " , " 有 " , " 更 " , " 好 " , "" }; // 常用停用词
public static boolean IsStopWord(String word)
{
for ( int i = 0 ;i < stopWordsList.length; ++ i)
{
if (word.equalsIgnoreCase(stopWordsList[i]))
return true ;
}
return false ;
}
}
训练集管理器
我们的系统首先需要从训练样本集中得到假设的先验概率和给定假设下观察到不同数据的概率。
package com.vista;
import java.io.BufferedReader;
import java.io.File;
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Properties;
import java.util.logging.Level;
import java.util.logging.Logger;
public class TrainingDataManager
{
private String[] traningFileClassifications; // 训练语料分类集合
private File traningTextDir; // 训练语料存放目录
private static String defaultPath = " D:\\TrainningSet " ;
public TrainingDataManager()
{
traningTextDir = new File(defaultPath);
if ( ! traningTextDir.isDirectory())
{
throw new IllegalArgumentException( " 训练语料库搜索失败！ [ " + defaultPath + " ] " );
}
this .traningFileClassifications = traningTextDir.list();
}
public String[] getTraningClassifications()
{
return this .traningFileClassifications;
}
public String[] getFilesPath(String classification)
{
File classDir = new File(traningTextDir.getPath() + File.separator + classification);
String[] ret = classDir.list();
for ( int i = 0 ; i < ret.length; i ++ )
{
ret[i] = traningTextDir.getPath() + File.separator + classification + File.separator + ret[i];
}
return ret;
}
public static String getText(String filePath) throws FileNotFoundException,IOException
{
InputStreamReader isReader = new InputStreamReader( new FileInputStream(filePath), " GBK " );
BufferedReader reader = new BufferedReader(isReader);
String aline;
StringBuilder sb = new StringBuilder();
while ((aline = reader.readLine()) != null )
{
sb.append(aline + " " );
}
isReader.close();
reader.close();
return sb.toString();
}
public int getTrainingFileCount()
{
int ret = 0 ;
for ( int i = 0 ; i < traningFileClassifications.length; i ++ )
{
ret += getTrainingFileCountOfClassification(traningFileClassifications[i]);
}
return ret;
}
public int getTrainingFileCountOfClassification(String classification)
{
File classDir = new File(traningTextDir.getPath() + File.separator + classification);
return classDir.list().length;
}
public int getCountContainKeyOfClassification(String classification,String key)
{
int ret = 0 ;
try
{
String[] filePath = getFilesPath(classification);
for ( int j = 0 ; j < filePath.length; j ++ )
{
String text = getText(filePath[j]);
if (text.contains(key))
{
ret ++ ;
}
}
}
catch (FileNotFoundException ex)
{
Logger.getLogger(TrainingDataManager. class .getName()).log(Level.SEVERE, null ,ex);
}
catch (IOException ex)
{
Logger.getLogger(TrainingDataManager. class .getName()).log(Level.SEVERE, null ,ex);
}
return ret;
}
}
先验概率
先验概率是我们需要计算的两大概率值之一
package com.vista;
public class PriorProbability
{
private static TrainingDataManager tdm = new TrainingDataManager();
public static float calculatePc(String c)
{
float ret = 0F;
float Nc = tdm.getTrainingFileCountOfClassification(c);
float N = tdm.getTrainingFileCount();
ret = Nc / N;
return ret;
}
}
分类条件概率
这是另一个影响因子，和先验概率一起来决定最终结果
package com.vista;
public class ClassConditionalProbability
{
private static TrainingDataManager tdm = new TrainingDataManager();
private static final float M = 0F;
public static float calculatePxc(String x, String c)
{
float ret = 0F;
float Nxc = tdm.getCountContainKeyOfClassification(c, x);
float Nc = tdm.getTrainingFileCountOfClassification(c);
float V = tdm.getTraningClassifications().length;
ret = (Nxc + 1 ) / (Nc + M + V); // 为了避免出现0这样极端情况，进行加权处理
return ret;
}
}
分类结果
用来保存各个分类及其计算出的概率值，
package com.vista;
public class ClassifyResult
{
public double probility; // 分类的概率
public String classification; // 分类
public ClassifyResult()
{
this .probility = 0 ;
this .classification = null ;
}
}
朴素贝叶斯分类器
利用样本数据集计算先验概率和各个文本向量属性在分类中的条件概率，从而计算出各个概率值，最后对各个概率值进行排序，选出最大的概率值，即为所属的分类。
package com.vista;
import com.vista.ChineseSpliter;
import com.vista.ClassConditionalProbability;
import com.vista.PriorProbability;
import com.vista.TrainingDataManager;
import com.vista.StopWordsHandler;
import java.util.ArrayList;
import java.util.Comparator;
import java.util.List;
import java.util.Vector;
public class BayesClassifier
{
private TrainingDataManager tdm; // 训练集管理器
private String trainnigDataPath; // 训练集路径
private static double zoomFactor = 10.0f ;
public BayesClassifier()
{
tdm = new TrainingDataManager();
}
float calcProd(String[] X, String Cj)
{
float ret = 1.0F ;
// 类条件概率连乘
for ( int i = 0 ; i < X.length; i ++ )
{
String Xi = X[i];
// 因为结果过小，因此在连乘之前放大10倍，这对最终结果并无影响，因为我们只是比较概率大小而已
ret *= ClassConditionalProbability.calculatePxc(Xi, Cj) * zoomFactor;
}
// 再乘以先验概率
ret *= PriorProbability.calculatePc(Cj);
return ret;
}
public String[] DropStopWords(String[] oldWords)
{
Vector < String > v1 = new Vector < String > ();
for ( int i = 0 ;i < oldWords.length; ++ i)
{
if (StopWordsHandler.IsStopWord(oldWords[i]) == false )
{ // 不是停用词
v1.add(oldWords[i]);
}
}
String[] newWords = new String[v1.size()];
v1.toArray(newWords);
return newWords;
}
@SuppressWarnings( " unchecked " )
public String classify(String text)
{
String[] terms = null ;
terms = ChineseSpliter.split(text, " " ).split( " " ); // 中文分词处理(分词后结果可能还包含有停用词）
terms = DropStopWords(terms); // 去掉停用词，以免影响分类
String[] Classes = tdm.getTraningClassifications(); // 分类
float probility = 0.0F ;
List < ClassifyResult > crs = new ArrayList < ClassifyResult > (); // 分类结果
for ( int i = 0 ; i < Classes.length; i ++ )
{
String Ci = Classes[i]; // 第i个分类
probility = calcProd(terms, Ci); // 计算给定的文本属性向量terms在给定的分类Ci中的分类条件概率
// 保存分类结果
ClassifyResult cr = new ClassifyResult();
cr.classification = Ci; // 分类
cr.probility = probility; // 关键字在分类的条件概率
System.out.println( " In process
. " );
System.out.println(Ci + " ： " + probility);
crs.add(cr);
}
// 对最后概率结果进行排序
java.util.Collections.sort(crs, new Comparator()
{
public int compare( final Object o1, final Object o2)
{
final ClassifyResult m1 = (ClassifyResult) o1;
final ClassifyResult m2 = (ClassifyResult) o2;
final double ret = m1.probility - m2.probility;
if (ret < 0 )
{
return 1 ;
}
else
{
return - 1 ;
}
}
});
// 返回概率最大的分类
return crs.get( 0 ).classification;
}
public static void main(String[] args)
{
String text = " 微软公司提出以446亿美元的价格收购雅虎中国网2月1日报道 美联社消息，微软公司提出以446亿美元现金加股票的价格收购搜索网站雅虎公司。微软提出以每股31美元的价格收购雅虎。微软的收购报价较雅虎1月31日的收盘价19.18美元溢价62%。微软公司称雅虎公司的股东可以选择以现金或股票进行交易。微软和雅虎公司在2006年底和2007年初已在寻求双方合作。而近两年，雅虎一直处于困境：市场份额下滑、运营业绩不佳、股价大幅下跌。对于力图在互联网市场有所作为的微软来说，收购雅虎无疑是一条捷径，因为双方具有非常强的互补性。(小桥) " ;
BayesClassifier classifier = new BayesClassifier(); // 构造Bayes分类器
String result = classifier.classify(text); // 进行分类
System.out.println( " 此项属于[ " + result + " ] " );
}
}
训练集与分类测试
作为测试，这里选用Sogou实验室的文本分类数据，我只使用了mini版本。迷你版本有10个类别 ，共计100篇文章，总大小244KB
使用的测试文本：
微软公司提出以446亿美元的价格收购雅虎
中国网2月1日报道 美联社消息，微软公司提出以446亿美元现金加股票的价格收购搜索网站雅虎公司。
微软提出以每股31美元的价格收购雅虎。微软的收购报价较雅虎1月31日的收盘价19 . 18美元溢价62%。微软公司称雅虎公司的股东可以选择以现金或股票进行交易。
微软和雅虎公司在2006年底和2007年初已在寻求双方合作。而近两年，雅虎一直处于困境：市场份额下滑、运营业绩不佳、股价大幅下跌。对于力图在互联网市场有所作为的微软来说，收购雅虎无疑是一条捷径，因为双方具有非常强的互补性。 ( 小桥 )
使用mini版本的测试结果：
In process
.
IT： 2.8119528E-5
In process
.
体育： 2.791735E-21
In process
.
健康： 3.3188528E-12
In process
.
军事： 2.532662E-19
In process
.
招聘： 2.3753596E-17
In process
.
教育： 4.2023427E-19
In process
.
文化： 6.0595915E-23
In process
.
旅游： 5.1286412E-17
In process
.
汽车： 4.085446E-8
In process
.
财经： 3.7337095E-10
此项属于[IT]
作者：洞庭散人
出处：http://phinecos.cnblogs.com/
本博客遵从 Creative Commons Attribution 3.0 License ，若用于非商业目的，您可以自由转载，但请保留原作者信息和文章链接URL。