朴素贝叶斯分类算法

优质

小牛编辑

125浏览

2023-12-01

参考资料地址： http://www.cnblogs.com/leoo2sk/archive/2010/09/17/naive-bayesian-classifier.html

我的数据挖掘算法实现源码地址：https://github.com/linyiqun/DataMiningAlgorithm

介绍

要介绍朴素贝叶斯算法(Naive Bayes)，那就得先介绍贝叶斯分类算法，贝叶斯分类算法是统计分类算法的一种，他是一类利用概率统计知识进行的一种分类算法。而朴素贝叶斯算法就是里面贝叶斯算法中最简单的一个算法。为什么叫做朴素贝叶斯，因为他里面的各个类条件是独立的，所以一会在后面的计算中会起到很多方便的作用。

朴素贝叶斯算法原理

首先在这里用到了一个概率公式：

$P(B|A)=\frac{P(A|B)P(B)}{P(A)}$

P(B|A)的意思是在A事件的情况下，发生B事件的概率，可以理解为概率论中的条件概率，而贝叶斯公式的巨大作用就是对因果关系进行了交换，通过上面的公式就可以计算P(A|B)的概率，只要通过上述的转换。

上面的资源地址上已经对朴素贝叶斯算法的原理描述的非常清楚了，我在他的基础上做了点注释方便于后面代码的理解：

朴素贝叶斯分类的正式定义如下：

1、设 $x=\{a_1,a_2,...,a_m\}$ 为一个待分类项，而每个a为x的一个特征属性。(在后面的例子中x={"Youth", "Medium", "Yes", "Fair"},里面的4个因子为他的特征向量)

2、有类别集合 $C=\{y_1,y_2,...,y_n\}$ 。(在后面的类别中只有buy_computer的分类yes， no，C={yes, no})

3、计算。(在后面的计算的任务就是计算在X事件的条件下，yes和no事件的发生概率，P(Yes|X, P(No|X)))

4、如果 $P(y_k|x)=max\{P(y_1|x),P(y_2|x),...,P(y_n|x)\}$ ，则 $x \in y_k$ 。(计算出上面的结果值，拥有最大概率的值的yi就是他的分类，这个很好理解，在X条件下，那个分类类型概率高就属于哪个分类，在这里比的就是P(Yes|X, P(No|X))

那么现在的关键就是如何计算第3步中的各个条件概率。我们可以这么做：

1、找到一个已知分类的待分类项集合，这个集合叫做训练样本集。

2、统计得到在各类别下各个特征属性的条件概率估计。即。

3、如果各个特征属性是条件独立的，则根据贝叶斯定理有如下推导：

$P(y_i|x)=\frac{P(x|y_i)P(y_i)}{P(x)}$

因为分母对于所有类别为常数，因为我们只要将分子最大化皆可。又因为各特征属性是条件独立的，所以有：

$P(x|y_i)P(y_i)=P(a_1|y_i)P(a_2|y_i)...P(a_m|y_i)P(y_i)=P(y_i)\prod^m_{j=1}P(a_j|y_i)$

p(ai|yi)可以根据数量上的统计进行计算，在后面的程序中会有所体现。

朴素贝叶斯算法的代码实现：

输入的训练集数据input.txt：

Rid Age Income Student CreditRating BuysComputer
1 Youth High No Fair No
2 Youth High No Excellent No
3 MiddleAged High No Fair Yes
4 Senior Medium No Fair Yes
5 Senior Low Yes Fair Yes
6 Senior Low Yes Excellent No
7 MiddleAged Low Yes Excellent Yes
8 Youth Medium No Fair No
9 Youth Low Yes Fair Yes
10 Senior Medium Yes Fair Yes
11 Youth Medium Yes Excellent Yes
12 MiddleAged Medium No Excellent Yes
13 MiddleAged High Yes Fair Yes
14 Senior Medium No Excellent No

朴素贝叶斯工具调用类：

package DataMining_NaiveBayes;

import java.io.BufferedReader;
import java.io.File;
import java.io.FileReader;
import java.io.IOException;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.Map;

/**
 * 朴素贝叶斯算法工具类
 * 
 * @author lyq
 * 
 */
public class NaiveBayesTool {
  // 类标记符，这里分为2类，YES和NO
  private String YES = "Yes";
  private String NO = "No";

  // 已分类训练数据集文件路径
  private String filePath;
  // 属性名称数组
  private String[] attrNames;
  // 训练数据集
  private String[][] data;

  // 每个属性的值所有类型
  private HashMap<String, ArrayList<String>> attrValue;

  public NaiveBayesTool(String filePath) {
    this.filePath = filePath;

    readDataFile();
    initAttrValue();
  }

  /**
   * 从文件中读取数据
   */
  private void readDataFile() {
    File file = new File(filePath);
    ArrayList<String[]> dataArray = new ArrayList<String[]>();

    try {
      BufferedReader in = new BufferedReader(new FileReader(file));
      String str;
      String[] tempArray;
      while ((str = in.readLine()) != null) {
        tempArray = str.split(" ");
        dataArray.add(tempArray);
      }
      in.close();
    } catch (IOException e) {
      e.getStackTrace();
    }

    data = new String[dataArray.size()][];
    dataArray.toArray(data);
    attrNames = data[0];

    /*
     * for(int i=0; i<data.length;i++){ for(int j=0; j<data[0].length; j++){
     * System.out.print(" " + data[i][j]); }
     * 
     * System.out.print("\n"); }
     */
  }

  /**
   * 首先初始化每种属性的值的所有类型，用于后面的子类熵的计算时用
   */
  private void initAttrValue() {
    attrValue = new HashMap<>();
    ArrayList<String> tempValues;

    // 按照列的方式，从左往右找
    for (int j = 1; j < attrNames.length; j++) {
      // 从一列中的上往下开始寻找值
      tempValues = new ArrayList<>();
      for (int i = 1; i < data.length; i++) {
        if (!tempValues.contains(data[i][j])) {
          // 如果这个属性的值没有添加过，则添加
          tempValues.add(data[i][j]);
        }
      }

      // 一列属性的值已经遍历完毕，复制到map属性表中
      attrValue.put(data[0][j], tempValues);
    }

  }

  /**
   * 在classType的情况下，发生condition条件的概率
   * 
   * @param condition
   *            属性条件
   * @param classType
   *            分类的类型
   * @return
   */
  private double computeConditionProbably(String condition, String classType) {
    // 条件计数器
    int count = 0;
    // 条件属性的索引列
    int attrIndex = 1;
    // yes类标记符数据
    ArrayList<String[]> yClassData = new ArrayList<>();
    // no类标记符数据
    ArrayList<String[]> nClassData = new ArrayList<>();
    ArrayList<String[]> classData;

    for (int i = 1; i < data.length; i++) {
      // data数据按照yes和no分类
      if (data[i][attrNames.length - 1].equals(YES)) {
        yClassData.add(data[i]);
      } else {
        nClassData.add(data[i]);
      }
    }

    if (classType.equals(YES)) {
      classData = yClassData;
    } else {
      classData = nClassData;
    }

    // 如果没有设置条件则，计算的是纯粹的类事件概率
    if (condition == null) {
      return 1.0 * classData.size() / (data.length - 1);
    }

    // 寻找此条件的属性列
    attrIndex = getConditionAttrName(condition);

    for (String[] s : classData) {
      if (s[attrIndex].equals(condition)) {
        count++;
      }
    }

    return 1.0 * count / classData.size();
  }

  /**
   * 根据条件值返回条件所属属性的列值
   * 
   * @param condition
   *            条件
   * @return
   */
  private int getConditionAttrName(String condition) {
    // 条件所属属性名
    String attrName = "";
    // 条件所在属性列索引
    int attrIndex = 1;
    // 临时属性值类型
    ArrayList<String[]> valueTypes;
    for (Map.Entry entry : attrValue.entrySet()) {
      valueTypes = (ArrayList<String[]>) entry.getValue();
      if (valueTypes.contains(condition)
          && !((String) entry.getKey()).equals("BuysComputer")) {
        attrName = (String) entry.getKey();
      }
    }

    for (int i = 0; i < attrNames.length - 1; i++) {
      if (attrNames[i].equals(attrName)) {
        attrIndex = i;
        break;
      }
    }

    return attrIndex;
  }

  /**
   * 进行朴素贝叶斯分类
   * 
   * @param data
   *            待分类数据
   */
  public String naiveBayesClassificate(String data) {
    // 测试数据的属性值特征
    String[] dataFeatures;
    // 在yes的条件下，x事件发生的概率
    double xWhenYes = 1.0;
    // 在no的条件下，x事件发生的概率
    double xWhenNo = 1.0;
    // 最后也是yes和no分类的总概率，用P(X|Ci)*P(Ci)的公式计算
    double pYes = 1;
    double pNo = 1;

    dataFeatures = data.split(" ");
    for (int i = 0; i < dataFeatures.length; i++) {
      // 因为朴素贝叶斯算法是类条件独立的，所以可以进行累积的计算
      xWhenYes *= computeConditionProbably(dataFeatures[i], YES);
      xWhenNo *= computeConditionProbably(dataFeatures[i], NO);
    }

    pYes = xWhenYes * computeConditionProbably(null, YES);
    pNo = xWhenNo * computeConditionProbably(null, NO);
    
    return (pYes > pNo ? YES : NO);
  }

}

最后的测试结果是：

Youth Medium Yes Fair 数据的分类为:Yes

朴素贝叶斯算法的注意点：

1、当特征属性值的值类型不是离散值而是连续值的时候，需要通过高斯分布做概率的计算

$g(x,\eta ,\sigma )=\frac{1}{\sqrt{2\pi }\sigma }e^-\frac{(x-\eta)^2}{2\sigma^2}$

而 $P(a_k|y_i)=g(a_k,\eta_{y_i},\sigma_{y_i})$ 因此只要计算出训练样本中各个类别中此特征项划分的各均值和标准差，代入上述公式即可得到需要的估计值。均值与标准差的计算在此不再赘述。

2、为了避免统计概率中出现概率为0的情况，在这里引入了Laplace校准，它的思想非常简单，就是对没类别下所有划分的计数加1