搜索引擎之朴素贝叶斯文本分类
搜索引擎之朴素贝叶斯文本分类
潘少online 发表于2年前
搜索引擎之朴素贝叶斯文本分类
  • 发表于 2年前
  • 阅读 97
  • 收藏 1
  • 点赞 0
  • 评论 0

文本分类(Text Classification)

  • 文本分类的任务

      • 把一个未见过的文档分成已知类别中的一个或多个

      • 单层分类

      • 多层分类

  • 应用文本分类

      • 对新闻或商品网页分类。例如:新闻是国内新闻还是国际新闻

      • 基于内容的个性化新闻推荐。判断用户是否感兴趣

      • 垃圾邮件过滤。判断是否垃圾邮件

      • 识别网页语言:英语、法语、汉语...

      • 判断情感极性:正面、负面、中性 


基于机器学习的文本分类简化版本

基于机器学习的文本分类


  • 训练数据

      • 人工整理训练文档集

      • 爬虫按目录抓取

  • 分类方法:有监督的机器学习

      • 朴素贝叶斯

      • 支持向量机(SVM)

      • 规则的方法

      • 最大熵

举例说明贝叶斯理论(Bayes' Theorem)

在四十岁这个年龄段参加例行检查的妇女有1%的概率有乳腺癌。80%患有乳腺癌的妇女做透视会得到阳性结果。9.6%没有得乳腺癌的妇女也会得到阳性的透视结果。一个妇女在这个年龄段例行检查的时候得到阳性的透视结果。问她确实患有乳腺癌的概率?

一个得到阳性透视结果的妇女大概有多少概率会真的患有乳腺癌?正确答案是7.8%。

10000个妇女中,100个人会患有乳腺癌,这患有乳腺癌的100个人中有80个人会得到阳性的透视结果。在10000名妇女中9900不患乳腺癌,这些人中有950人中也会得到阳性的透视结果。这表明得到阳性透视结果的妇女人数是(80+950)=1030人。这1030人中有80人患有癌症。结果为(80/1030)=0.07767即7.8%。 


概率

  • 先验概率:得乳腺癌的病人的原始概率

  • 条件概率:患有乳腺癌的的病人得到透视阳性的概率,没有患乳腺癌的病人得到透视阳性的概率

  • 后验概率:最终的答案——从透视中是阳性的结果得出病人得乳腺癌的估计概率

推导过程

推导贝叶斯公式


贝叶斯公式用于文本分类

对于一个文档d和一个类别c

构建一个生成式模型估计数据是如何产生的


计算后验概率

判断文档类别

计算文档d最有可能的类别=后验概率最大的类别



把文档看成词的序列。假设d=w1,w2,…,wn,则



假设词与词之间独立出现,则




如何估计P(wi|c)

  • 词是否在文档中出现(根据type分类)

      • 多变量伯努利(Multiple Bernoulli)事件空间

      • 这里,dfw, c是在类c中包含词w的训练文档的数量,Nc是类c的训练文档的总数 

  • 词在文档中出现的频率(根据token分类)

      • 多项(multinomial)事件空间

      • 这里,tfw, c是在类c中词w出现的次数,|c|是类c中的词总数(token总数)


统计语言模型

为生成一个语言中的字符串的概率建模 。例如,一个一元模型


不同的模型生成同样的字符串的概率不一样


一元和高阶模型


  • 其他的语言模型

      • 基于文法的模型(PCFGs)等

      • 在信息检索中不太常用


一个类别的语言模型 = 多项朴素贝叶斯

每个类别的条件概率通过类别特定的一元语言模型计算


垃圾邮件分类的例子

在一个训练集中有10个文档,每个文档用唯一的id标识,两个类别(spam和not spam),词汇表包含“cheap”,“buy”,“banking”,“dinner”和“the”

先验概率P(spam)=3/10,P(not spam)=7/10

条件概率

P(the|spam)=1

P(the |not spam)=1

P(dinner|spam)=0

P(dinner|not spam)=1/7




零概率问题

假设我们接收一封垃圾邮件包含“dinner”一词。无论电子邮件包含或不包含其它的词,任何包含词“dinner”的邮件将都会自动计算成是垃圾邮件的概率是零,也就是P(d|c)一直是0 。因为P(dinner|spam)=0,而这个词在文档中出现了。这个问题比较普遍,因为每当一个文档包含一个词,而那个词从来不出现在一个或多个类时,零概率问题就会产生。这里的问题是最大似然估计是基于训练集中的出现计数。然而,这个训练集是有限的,因此不可能观察到所有可能的事件。这就是所谓的数据稀疏。稀疏往往是因为训练集太小,但是在比较大的数据集上也存在数据稀疏。因此,我们必须改变这样一种方式的估计,对所有词,包括那些没有在给定类中观察到的,给予一些概率量。我们必须为所有在词表中的项确保P(w|c)是非零的。通过这样做,就能避免所有的与零概率相关的问题。平滑技术可以克服零概率问题。

平滑P(wi|c)

  • 加一平滑

  • Dirichlet平滑

多变量伯努利分类模型代码实现

  • 计算先验概率(Prior Probability)

private static TrainingData trainingData=TrainingData.getInstance();//得到训练集
/**
* 先验概率
* @param c 给定的分类
* @return 给定条件下的先验概率
*/
public static float calculatePc(String c)
{
  float Nc = trainingData.getClassDocNum(c);//给定分类的训练文本数
  float N = trainingData.getTotalNum();//训练集中文本总数
  return (Nc / N);
}

/**
* 计算类条件概率
* @param w 给定的词
* @param c 给定的分类
* @return 给定条件下的类条件概率
*/
public static float calculatePwc(String w, String c) 
{
  //返回给定分类中包含分类特征词w的训练文本的数目
  float dfwc = tdm.getCountContainKeyOfClassification(c, w);
  //返回训练文本集中在给定分类下的训练文本数目
  float Nc = tdm.getClassDocNum(c);
  //类别数量
  float V = tdm.getTraningClassifications().length;
  return ( (dfwc + 1) / (Nc + M + V)); //M值用于平滑,如果训练集很大,则可以设M=0
} 

//计算文档的后验概率
/**
* @param d 给定文本的属性向量
* @param Cj 给定的类别
* @return 类别概率
*/
float calcProd(String[] d, String Cj)
{
  float ret = 0.0F;
  //类条件概率连乘
  for (int i = 0; i <d.length; i++)
  {
  String wi = d[i];
  //因为连乘结果过小,所以把转成取对数
  //对分类的最终结果无影响,因为只是比较概率大小而已
  ret+=Math.log(ClassConditionalProbability.calculatePwc(wi, Cj));
  }
  // 再乘以先验概率
  ret += Math.log(PriorProbability.calculatePc(Cj));
  return ret;
}

//返回最大的概率对应的类 
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个分类
  //计算给定的文本属性向量terms在给定的分类Ci中的分类条件概率
  probility = calcProd(terms, ci);
  //保存分类结果
  ClassifyResult cr = new ClassifyResult(ci,probility);
  crs.add(cr);
}
//返回概率最大的分类
float maxPro = crs.get(0).probility;
String c = crs.get(0).classification;
for(ClassifyResult cr:crs){
  if(cr.probility>maxPro) {
  c = cr.classification;
  maxPro = cr.probility;
  }
}
return c;

分类过程

  • 朴素贝叶斯文本分类

      • 学习阶段: 给定一个训练集C, 存储每个类的先验概率P(ci) 和每个词的条件概率P(wj|ci)到表中


      • 测试阶段: 给定一个待分类文档X,假设X中有n个词

                  查表计算 



测试阶段实现

/**
 * Calculates the prob of the testExample being generated by each category
 *
 * @param testExample The test example to be categorized
 */
protected double[] calculateProbs(Example testExample) {
  //set initial probabilities to the prior probs
  double[] probs = trainResult.getClassPriors().clone();
  Hashtable<String, double[]> hashTable = trainResult.getFeatureTable();
  for (Map.Entry<String, Weight> entry : testExample.getHashMapVector().entrySet()) {
    // An entry in the HashMap maps a token to a Weight
    String token = entry.getKey();
    // The count for the token is in the value of the Weight
    int count = (int) entry.getValue().getValue();
    if (hashTable.containsKey(token)) {//ignore unknowns
      double[] countArray = hashTable.get(token); // stores the category array for one token
      for (int k = 0; k < numCategories; k++)
        probs[k] += count * countArray[k];//multiplying the probs == adding the logs
    }
  }
  return probs;
}


共有 人打赏支持
粉丝 9
博文 54
码字总数 94075
×
潘少online
如果觉得我的文章对您有用,请随意打赏。您的支持将鼓励我继续创作!
* 金额(元)
¥1 ¥5 ¥10 ¥20 其他金额
打赏人
留言
* 支付类型
微信扫码支付
打赏金额:
已支付成功
打赏金额: