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

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

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

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

一、跑起来 方式一

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

方式二

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

mkdir build
cd build
cmake ..
make

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);

2、读取文件，训练模型

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

示例文件格式：

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

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

三、学起来

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

P ( A i ∣ B ) = P ( B ∣ A i ) P ( A i ) ∑ j = 1 n P ( B ∣ A j ) P ( A j ) P(A_i|B)=\frac{P(B|A_i)P(A_i)}{\sum_{j=1}^nP(B|A_j)P(A_j)} P(Ai​∣B)=∑j=1n​P(B∣Aj​)P(Aj​)P(B∣Ai​)P(Ai​)​

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

P ( c ∣ x ) = p ( c ) p ( x ∣ c ) p ( x ) P(c|\boldsymbol{x})=\frac{p(c)p(\boldsymbol{x}|c)}{p(\boldsymbol{x})} P(c∣x)=p(x)p(c)p(x∣c)​

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

而

P ( c ∣ x ) ∝ p ( c ) p ( x ∣ c ) P(c|\boldsymbol{x}) \propto p(c)p(\boldsymbol{x}|c) P(c∣x)∝p(c)p(x∣c)

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

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

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

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

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

p ( x i ∣ c ) = ∣ D i , c ∣ ∣ D c ∣ p(x_i|c)=\frac{|D_{i,c}|}{|D_c|} p(xi​∣c)=∣Dc​∣∣Di,c​∣​

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

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

p ( x i ∣ c ) = 1 2 π σ i , c e − ( x i − μ i , c ) 2 2 σ i , c 2 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}} p(xi​∣c)=2π ​σi,c​1​e−2σi,c2​(xi​−μi,c​)2​

其中 σ i , c 2 , μ i , c \sigma_{i,c}^2,\mu_{i,c} σi,c2​,μi,c​分别为所属类别为 c c c的训练集的 i i i分量的方差和均值。

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

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

p ( x ) = 1 ( 2 π ) d 2 ∣ Σ ∣ 1 2 e x p ( − 1 2 ( x − μ ) T Σ − 1 ( x − μ ) ) p(\boldsymbol{x})=\frac{1}{(2\pi)^{\frac{d}{2}}|\Sigma|^{\frac{1}{2}}}exp\left ( -\frac{1}{2} (\boldsymbol{x}-\boldsymbol{\mu} )^T\Sigma^{-1}(\boldsymbol{x}-\boldsymbol{\mu} ) \right ) p(x)=(2π)2d​∣Σ∣21​1​exp(−21​(x−μ)TΣ−1(x−μ))

其中

μ i = E [ x i ] \mu_i=E[x_i] μi​=E[xi​]
Σ i , j = E [ ( x i − μ i ) ( x j − μ j ) ] \Sigma_{i,j}=E[(x_i-\mu_i)(x_j-\mu_j)] Σi,j​=E[(xi​−μi​)(xj​−μj​)]

这里我们将结果取对数

g i ( x ) = l n ( p ( x ∣ c i ) p ( c i ) ) = l n p ( x ∣ c i ) + l n p ( c i ) g_i(\boldsymbol{x})=ln(p(\boldsymbol{x}|c_i)p(c_i))=lnp(\boldsymbol{x}|c_i)+lnp(c_i) gi​(x)=ln(p(x∣ci​)p(ci​))=lnp(x∣ci​)+lnp(ci​)

g i ( x ) = − 1 2 ( x − μ ) T Σ − 1 ( x − μ ) − d 2 l n 2 π − 1 2 l n ∣ Σ i ∣ + l n p ( c i ) g_i(\boldsymbol{x})=-\frac{1}{2} (\boldsymbol{x}-\boldsymbol{\mu} )^T\Sigma^{-1}(\boldsymbol{x}-\boldsymbol{\mu} )-\frac{d}{2}ln2\pi -\frac{1}{2}ln|\Sigma_i|+lnp(c_i) gi​(x)=−21​(x−μ)TΣ−1(x−μ)−2d​ln2π−21​ln∣Σi​∣+lnp(ci​)

此时有决策函数：

g i , j ( x ) = g i ( x ) − g j ( x ) g_{i,j}(x)=g_i(x)-g_j(x) gi,j​(x)=gi​(x)−gj​(x)

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