贝叶斯分类算法

贝叶斯分类算法是指基于贝叶斯定理的分类算法，本篇文章介绍最简单的两个：朴素贝叶斯分类算法和树增强型朴素贝叶斯算法（TAN算法）。

一、贝叶斯定理

P(A|B) 表示在事件B发生的前提下，事件A发生的概率，也称为事件B发生下事件A的条件概率。其基本的求解公式为：

$$P(A|B) = P(AB)/P(B)$$

贝叶斯定理用于已知P(A|B)的前提下求解P(B|A),公式为：

$$P(B|A) = P(A|B)P(B)/P(A)$$

二、朴素贝叶斯分类

基于贝叶斯定理，朴素贝叶斯分类的基本思想为：对于给出的待分类项，求解在此项出现的条件下各个类别出现的概率，认定此分类项属于出现概率最大的那个类别。就好比你在街上看到一个黑人，让你猜他是哪里来的，你一定会猜非洲：因为黑人中非洲人比例最高–在无其他信息可用的前提下，选择条件概率最大的类别。

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

  1. 设 $$x = {a_1,a_2,…a_m}$$ 为待分类项，而每个a为x的一个特征属性。
  2. 有类别集合 $$C ＝\{y_1,y_2,...y_n\}$$
  3. 计算 $$P(y_1|x),P(y_2|x),…P(y_n|x)$$
  4. 如果 $$P(y_k|x) = max{\{P(y_1|x),P(y_2|x),...P(y_n|x)\}}$$,则$$x∈y_k$$

可以看出关键步骤就是3中的条件概率：

  1. 找到一个已知分类的待分类项集合（训练样本集）。
  2. 计算得到在各类别下各个特征属性的条件概率估计。
  3. 在各类别下各个特征属性条件独立的前提下，应用贝叶斯公式：
    $$P(y_i|x) = 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)$$

总结起来朴素贝叶斯分类算法主要有以下几个步骤：

  1. 确定特征属性。
  2. 获取训练样本。
  3. 对每个类别计算 $$P(y_i)$$
  4. 对每个特征属性计算所有划分的条件概率。
  5. 对每个类分别计算 $$P(x|y_i)P(y_i)$$
  6. 以 $$P(x|y_i)P(y_i)$$ 最大项作为 x 的所属类别。

可以看到，整个朴素贝叶斯分类分为三个阶段：

第一阶段——准备工作阶段，这个阶段的任务是为朴素贝叶斯分类做必要的准备，主要工作是根据具体情况确定特征属性，并对每个特征属性进行适当划分，然后由人工对一部分待分类项进行分类，形成训练样本集合。这一阶段的输入是所有待分类数据，输出是特征属性和训练样本。这一阶段是整个朴素贝叶斯分类中唯一需要人工完成的阶段，其质量对整个过程将有重要影响，分类器的质量很大程度上由特征属性、特征属性划分及训练样本质量决定。

第二阶段——分类器训练阶段，这个阶段的任务就是生成分类器，主要工作是计算每个类别在训练样本中的出现频率及每个特征属性划分对每个类别的条件概率估计，并将结果记录。其输入是特征属性和训练样本，输出是分类器。这一阶段是机械性阶段，根据前面讨论的公式可以由程序自动计算完成。

第三阶段——应用阶段。这个阶段的任务是使用分类器对待分类项进行分类，其输入是分类器和待分类项，输出是待分类项与类别的映射关系。这一阶段也是机械性阶段，由程序完成。

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

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
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

朴素贝叶斯工具调用类：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
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);
    }

}

测试结果：

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

三、TAN算法

朴素贝叶斯分类算法本身非常简单高效，可以应用在大型数据库中，但其基于的贝叶斯定理的前提条件是假设一个属性值对给定类的影响独立于其他属性的值，而这种情况在实际应用中通常是不成立的，简单的朴素贝叶斯算法在这种情况下分类准确率会下降，因此衍生出了降低独立性假设的TAN算法。