基于C++的朴素贝叶斯分类器

基于C++的朴素贝叶斯分类器

github链接
使用c++编写的朴素贝叶斯分类器，其中似然中的离散分量，以及先验概率使用拉普拉斯平滑，连续分量为正态分布。

警告，此代码仅为初学学习之用，请勿用作任何工程项目！

一、跑起来

方式一

使用vscode+cmake插件或者Clion打开目录。然后直接编译运行。

方式二

1、确保安装cmake环境，没有请先装cmake。
2、在工程目录下键入：

mkdir build
cd build
cmake ..
make
1
2
3
4

3、运行build目录下的程序Bayers_classifier程序

二、用起来

1、建立模型

Simple_Bayes_Classifier::Info info;
/**
    struct Info {
        int sample_num; // 样例数量
        std::vector header; // 样例格式，
                                 // 如当前分量为离散值则为样例可能取值的数量，
                                 // 如为连续值则填0，
                                 // 例如，现有样例格式为这样 :
                                 //           x0 属于 {"东","南","西","北"}
                                 //           x1 属于 {"左","右"}
                                 //           x2 属于 {x|0
Simple_Bayes_Classifier model(info);
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

2、读取文件，训练模型

model.train("data/1.txt"); // 文件格式为：每行一个样例，每个样例n个分量用空格隔开，最后为该样例所属分类
1

示例文件格式：

3、开始分类, 构造出一个待分类的样例，然后分类结果赋值到样例的belong_to字段

Sample s;
s.add_parameter(x); s.add_parameter(y);
model.classify(s);
std::cout << s.belong_to << std::endl;
1
2
3
4

三、学起来

贝叶斯分类器的基石为Bayes公式：

$$P(A_i|B)=\frac{P(B|A_i)P(A_i)}{{\sum }_{j=1}^{n}P(B|A_j)P(A_j)}$$

若现在存在样例的向量为$\mathbf{x}$，而其所属分类为$c$的概率为：

$$P(c|\mathbf{x})=\frac{p(c)p(\mathbf{x}|c)}{p(\mathbf{x})}$$

其中，我们把$p(c)$称为先验概率（prior），而$p(\mathbf{x}|c)$则为似然（likelihood）而$p(\mathbf{x})$称为证据（evidence）。当分类器工作时，遵循$h(\mathbf{x})$，我们需要比较$n$种分类，选择概率最大的分类。
$$h(\mathbf{x})=argma{x}_{c\in Y}P(c|\mathbf{x})$$

而

$$P(c|\mathbf{x})\propto p(c)p(\mathbf{x}|c)$$

所以我们可以忽略证据，针对每个待分类的样例，对每种分类计算先验概率和似然即可。

先验概率$p(c)$一般直接进行数量统计，即:
$$p(c)=\frac{|D_c|}{|D|}$$

其中$D_c$为训练集中。所属类别$c$的样例集，而$|D|$为全体训练集。

而计算较为困难的是似然$p(\mathbf{x}|c)$，在朴素贝叶斯中，我们认为向量$\mathbf{x}$的所有分量的取值是独立的,此时有:
$$p(\mathbf{x}|c)=\prod _{i=0}^{n}p(x_i|c)$$

此时即可进行运算，这里如果$x_i$为离散值，则可以直接进行统计：

$$p(x_i|c)=\frac{|D_{i,c}|}{|D_c|}$$

其中$D_{i,c}$是训练集中满足：所属类别为$c$且$i$分量为$x_i$的集合。

而如果$x_i$为连续值，则这里可以将其看成正态分布:

$$p(x_i|c)=\frac{1}{\sqrt{2\pi }{\sigma }_{i,c}}{e}^{-\frac{(x_i-{\mu }_{i,c}{)}^2}{2{\sigma }_{i,c}^2}}$$

其中${\sigma }_{i,c}^2,{\mu }_{i,c}$分别为所属类别为$c$的训练集的$i$分量的方差和均值。

至此我们解决了朴素贝叶斯分类器。

在有些时候，向量$\mathbf{x}$的分量不是独立的，一种常见的情况是所有分量满足多维正态分布$N(\mu ,\Sigma )$。为了清晰设置$exp(x)=e^x$

$$p(\mathbf{x})=\frac{1}{(2\pi {)}^{\frac{d}{2}}|\Sigma {|}^{\frac{1}{2}}}exp\left(-\frac{1}{2}(\mathbf{x}-\mathbf{\mu }{)}^T{\Sigma }^{-1}(\mathbf{x}-\mathbf{\mu })\right)$$

其中

$${\mu }_i=E[x_i]$$
$${\Sigma }_{i,j}=E[(x_i-{\mu }_i)(x_j-{\mu }_j)]$$

这里我们将结果取对数

$$g_i(\mathbf{x})=ln(p(\mathbf{x}|c_i)p(c_i))=lnp(\mathbf{x}|c_i)+lnp(c_i)$$

$$g_i(\mathbf{x})=-\frac{1}{2}(\mathbf{x}-\mathbf{\mu }{)}^T{\Sigma }^{-1}(\mathbf{x}-\mathbf{\mu })-\frac{d}{2}ln2\pi -\frac{1}{2}ln|{\Sigma }_i|+lnp(c_i)$$

此时有决策函数：

$$g_{i,j}(x)=g_i(x)-g_j(x)$$

$g_{i,j}(x)=0$为决策界，当$g_{i,j}(x)\ge 0$归为$i$类，否则归为$j$。至此，我们讨论了贝叶斯分类器中，样例各分量满足多维正态分布的情况。