错位的梦寐

朴素贝叶斯

2019-12-16

Machine-learning
   

贝叶斯分类是一类分类算法的总称，这类算法均以贝叶斯定理为基础，故统称为贝叶斯分类。

1. 贝叶斯公式

如果X和Y相互独立:

\[P(A, B)=P(A) P(B)\]

条件概率：

\[P(B | A)=\frac{P(A, B)}{P(A)}\]

全概率公式：

\[\operatorname{P}(A)=\sum_{n} \operatorname{P}\left(A | B_{n}\right) \operatorname{P}\left(B_{n}\right)\]

贝叶斯公式：

\[P\left(B_{i} | A\right)=\frac{P\left(B_{i}\right) P\left(A | B_{i}\right)}{P(A)}=\frac{P\left(B_{i}\right) P\left(A | B_{i}\right)}{\sum_{j=1}^{n} P\left(B_{j}\right) P\left(A | B_{j}\right)}\]

2. 朴素贝叶斯的模型

从统计学知识回到我们的数据分析。假如我们的分类模型样本是：

\[\left(x_{1}^{(1)}, x_{2}^{(1)}, \ldots x_{n}^{(1)}, y_{1}\right),\left(x_{1}^{(2)}, x_{2}^{(2)}, \ldots x_{n}^{(2)}, y_{2}\right), \ldots\left(x_{1}^{(m)}, x_{2}^{(m)}, \ldots x_{n}^{(m)}, y_{m}\right)\]

即我们有m个样本，每个样本有n个特征，特征输出有K个类别，定义为$C_1,C_2,…,C_K$ 。

从样本我们可以学习得到朴素贝叶斯的先验分布 \(P(Y=C_k)(k=1,2,...K)\) , 接着学习到条件概率分布 \(P(X=x\) l \(Y=C_k)\) =\(P(X_1=x_1, X_2=x_2,...X_n=\) \(x_n\)l\(Y=C_k)\), 然后我们就可以用贝叶斯公式得到X和Y的联合分布 $P(X,Y)$ 了。联合分布 $P(X,Y)$ 定义为：

\[\begin{align} P(X,Y=C_k) &= P(Y=C_k)P(X=x|Y=C_k) \\&= P(Y=C_k)P(X_1=x_1, X_2=x_2,...X_n=x_n|Y=C_k) \end{align}\]

从上面的式子可以看出 $P(Y=C_k)$ 比较容易通过最大似然法求出, 得到的 $P(Y=C_k)$ 就是类别 $C_k$ 在训练集里面出现的频数。但是 $P(X_1=x_1, X_2=x_2,…X_n=x_n$ l $Y=C_k)$ 很难求出,这是一个超级复杂的有n个维度的条件分布。朴素贝叶斯模型在这里做了一个大胆的假设，即X的n个维度之间相互独立，这样就可以得出:

\[P(X_1=x_1, X_2=x_2,...X_n=x_n|Y=C_k) = \\P(X_1=x_1|Y=C_k)P(X_2=x_2|Y=C_k)... .P(X_n=x_n|Y=C_k)\]

从上式可以看出，这个很难的条件分布大大的简化了，但是这也可能带来预测的不准确性。你会说如果我的特征之间非常不独立怎么办？如果真是非常不独立的话，那就尽量不要使用朴素贝叶斯模型了，考虑使用其他的分类方法比较好。但是一般情况下，样本的特征之间独立这个条件的确是弱成立的，尤其是数据量非常大的时候。虽然我们牺牲了准确性，但是得到的好处是模型的条件分布的计算大大简化了，这就是贝叶斯模型的选择。

最后回到我们要解决的问题，我们的问题是给定测试集的一个新样本特征 $(x_1^{(test)}, x_2^{(test)}, …x_n^{(test)})$ , 我们如何判断它属于哪个类型？

既然是贝叶斯模型，当然是后验概率最大化来判断分类了。我们只要计算出所有的$K$ 个条件概率 \(P(Y=C_k\) l \(X=X^{(test)})\) , 然后找出最大的条件概率对应的类别，这就是朴素贝叶斯的预测了。

基于贝叶斯定理与特征条件独立假设的分类方法。

模型：

  • 高斯模型
  • 多项式模型
  • 伯努利模型

3. 朴素贝叶斯的推断过程

我们预测的类别 $C_{result}$ 是使 $P(Y=C_k$l$X=X^{(test)})$ 最大化的类别，数学表达式为：

\[\begin{align} C_{result} & = \underbrace{argmax}_{C_k}P(Y=C_k|X=X^{(test)}) \\& = \underbrace{argmax}_{C_k}P(X=X^{(test)}|Y=C_k)P(Y=C_k) \Bigg{/}P(X=X^{(test)}) \end{align}\]

由于对于所有的类别计算 \(P(Y=C_k\) l $X=X^{(test)})$ 时，上式的分母是一样的，都$P(X=X^{(test)}$ ，因此，我们的预测公式可以简化为：

\[C_{result} = \underbrace{argmax}_{C_k}P(X=X^{(test)}|Y=C_k)P(Y=C_k)\]

接着我们利用朴素贝叶斯的独立性假设，就可以得到通常意义上的朴素贝叶斯推断公式:

\[C_{result} = \underbrace{argmax}_{C_k}P(Y=C_k)\prod_{j=1}^{n}P(X_j=X_j^{(test)}|Y=C_k)\]

4. 朴素贝叶斯的参数估计

我们知道只要求出$P(Y=C_k)和P(X_j=X_j^{(test)}$ l$Y=C_k)(j=1,2,…n)$ ，我们通过比较就可以得到朴素贝叶斯的推断结果。怎么通过训练集计算这两个概率?

对于$P(Y=C_k)$ , 比较简单，通过极大似然估计我们很容易得到$P(Y=C_k)$ 为样本类别$C_k$ 出现的频率，即样本类别 $C_k$ 出现的次数 $m_k$ 除以样本总数 $m$ 。

对于$P(X_j=X_j^{(test)}$ l$Y=C_k)(j=1,2,…n)$ ,这个取决于我们的先验条件：

  1. 如果我们的$X_j$ 是离散的值，那么我们可以假设$X_j$符合多项式分布，这样得到$P(X_j=X_j^{(test)}$l$Y=C_k)$ 是在样本类别$C_k$ 中，特征$X_j^{(test)}$ 出现的频率。即：

    \[P(X_j=X_j^{(test)}|Y=C_k) = \frac{m_{kj^{test}}}{m_k}\]

    其中$m_k$ 为样本类别 $C_k$ 总的特征计数，而 $m_{kj^{test}}$ 为类别为$C_k$ 的样本中，第 j 维特征$X_j^{(test)}$ 出现的计数。

    某些时候，可能某些类别在样本中没有出现，这样可能导致 $P(X_j=X_j^{(test)}$ l$Y=C_k)$ 为0，这样会影响后验的估计，为了解决这种情况，我们引入了拉普拉斯平滑，即此时有：

    \[P(X_j=X_j^{(test)}|Y=C_k) = \frac{m_{kj^{test}} + \lambda}{m_k + O_j\lambda}\]

    其中$λ$ 为一个大于0的常数，常常取为1。$O_j$ 为第j个特征的取值个数。

  2. 如果我们我们的$X_j$ 是非常稀疏的离散值，即各个特征出现概率很低，这时我们可以假设$X_j$ 符合伯努利分布，即特征$X_j$ 出现记为1，不出现记为0。即只要$X_j$ 出现即可，我们不关注$X_j$ 的次数。这样得到 $P(X_j=X_j^{(test)}$l$Y=C_k)$ 是在样本类别$C_k$ 中, $X_j^{(test)}$ 出现的频率。此时有：

    \[P(X_j=X_j^{(test)}|Y=C_k) = P(X_j=1|Y=C_k)X_j^{(test)} + (1 - P(X_j=1|Y=C_k))(1-X_j^{(test)})\]

其中，$X_j^{(test)}$ 取值为 0 和 1。

  1. 如果我们我们的 $X_j$ 是连续值，我们通常取 $X_j$ 的先验概率为正态分布，即在样本类别$C_k$ 中，$X_j$的值符合正态分布。这样$P(X_j=X_j^{(test)}$ l$Y=C_k)$ 的概率分布是：

    \[P(X_j=X_j^{(test)}|Y=C_k) = \frac{1}{\sqrt{2\pi\sigma_k^2}}exp\Bigg{(}-\frac{(X_j^{(test)} - \mu_k)^2}{2\sigma_k^2}\Bigg{)}\]

    其中 $\mu_k和\sigma_k^2$ 是正态分布的期望和方差，可以通过极大似然估计求得。$\mu_k$ 为在样本类别$C_k$ 中，所有$X_j$ 的平均值。$\sigma_k^2$ 为在样本类别$C_k$中，所有$X_j$ 的方差。对于一个连续的样本值，带入正态分布的公式，就可以求出概率分布了。

5. 朴素贝叶斯算法过程

假设训练集为m个样本n个维度，如下：

\[(x_1^{(1)}, x_2^{(1)}, ...x_n^{(1)}, y_1), (x_1^{(2)}, x_2^{(2)}, ...x_n^{(2)},y_2), ... (x_1^{(m)}, x_2^{(m)}, ...x_n^{(m)}, y_m)\]

共有K个特征输出类别，分别为${C_1,C_2,…,C_K}$ , 每个特征输出类别的样本个数为 ${m_1,m_2,…,m_K}$ 在第k个类别中，如果是离散特征，则特征 $X_j$ 各个类别取值为 $ m_{kjl}$ , 其中$l$ 取值为$1,2,…S_j$ , $S_j$ 为特征j不同的取值数。

输出为实例 $X^{(test)}$ 的分类。

算法流程如下：

  1. 如果没有Y的先验概率，则计算Y的K个先验概率：$P(Y=C_k) = (m_k+\lambda)/(m+K\lambda)$ , 否则 $P(Y=C_k)$ 为输入的先验概率。

  2. 分别计算第$k$ 个类别的第j维特征的第l个个取值条件概率：$P(X_j=x_{jl}$ l$Y=C_k)$

    • 如果是离散值:

      \[P(X_j=x_{jl}|Y=C_k) = \frac{m_{kjl} + \lambda}{m_k + S_j\lambda}\]

      $λ$ 可以取值为1，或者其他大于0的数字。

    • 如果是稀疏二项离散值:

      \[P(X_j=x_{jl}|Y=C_k) = P(j|Y=C_k)x_{jl} + (1 - P(j|Y=C_k)(1-x_{jl})\]

      此时$l$ 只有两种取值。

    • 如果是连续值不需要计算各个 $l$ 的取值概率，直接求正态分布的参数:

      \[P(X_j=x_j|Y=C_k) = \frac{1}{\sqrt{2\pi\sigma_k^2}}exp\Bigg{(}-\frac{(x_j - \mu_k)^2}{2\sigma_k^2}\Bigg{)}\]

      需要求出 $\mu_k和\sigma_k^2$ , $\mu_k$ 为在样本类别$C_k$ 中，所有$X_j$ 的平均值。$\sigma_k^2$ 为在样本类别$C_k$ 中，所有$X_j$ 的方差。

  3. 对于实例 $X^{(test)}$ ，分别计算：

    \[P(Y=C_k)\prod_{j=1}^{n}P(X_j=x_j^{(test)}|Y=C_k)\]

  4. 确定实例 $X^{(test)}$ 的分类 $C_{result}$ :

    \[C_{result} = \underbrace{argmax}_{C_k}P(Y=C_k)\prod_{j=1}^{n}P(X_j=X_j^{(test)}|Y=C_k)\]

    从上面的计算可以看出，没有复杂的求导和矩阵运算，因此效率很高。

6. GaussianNB 高斯朴素贝叶斯

特征的可能性被假设为高斯

概率密度函数：

\[P(x_i | y_k)=\frac{1}{\sqrt{2\pi\sigma^2_{yk}}}exp(-\frac{(x_i-\mu_{yk})^2}{2\sigma^2_{yk}})\]

数学期望(mean)：$\mu$，

方差：$\sigma^2=\frac{\sum(X-\mu)^2}{N}$ (or N-1)

7. python 实现 Naive Bayes Tutorial (in 5 easy steps)

Step 1: Separate By Class

将数据根据标签进行分类

#Split the dataset by class values, returns a dictionary
def separate_by_class(dataset):
	separated = dict()
	for i in range(len(dataset)):
		vector = dataset[i]
        # 获取标签
		class_value = vector[-1]
		if (class_value not in separated):
			separated[class_value] = list()
		separated[class_value].append(vector)
	return separated

测试：

# Test separating data by class
dataset = [[3.393533211,2.331273381,0],
	[3.110073483,1.781539638,0],
	[1.343808831,3.368360954,0],
	[3.582294042,4.67917911,0],
	[2.280362439,2.866990263,0],
	[7.423436942,4.696522875,1],
	[5.745051997,3.533989803,1],
	[9.172168622,2.511101045,1],
	[7.792783481,3.424088941,1],
	[7.939820817,0.791637231,1]]
separated = separate_by_class(dataset)
for label in separated:
	print(label)
	for row in separated[label]:
		print(row)

输出：

0
[3.393533211, 2.331273381, 0]
[3.110073483, 1.781539638, 0]
[1.343808831, 3.368360954, 0]
[3.582294042, 4.67917911, 0]
[2.280362439, 2.866990263, 0]
1
[7.423436942, 4.696522875, 1]
[5.745051997, 3.533989803, 1]
[9.172168622, 2.511101045, 1]
[7.792783481, 3.424088941, 1]
[7.939820817, 0.791637231, 1]

Step 2: Summarize Dataset

计算每个特征的均值、方差，进而可以根据概率密度函数计算概率。（均值和方差的计算可以用python提供的函数，也可以自己实现）

  • 计算均值

    def mean(numbers):
	return sum(numbers)/float(len(numbers))

  • 计算方差，方差依据上述的公式进行计算，(除以 N、N-1 的区别，无偏估计 )

    from math import sqrt
   
# Calculate the standard deviation of a list of numbers
def stdev(numbers):
	avg = mean(numbers)
	variance = sum([(x-avg)**2 for x in numbers]) / float(len(numbers)-1)
	return sqrt(variance)

  • 将上面两个步骤算的结果（根据不同的类别的特征）进行汇总；

    # Calculate the mean, stdev and count for each column in a dataset
def summarize_dataset(dataset):
	summaries = [(mean(column), stdev(column), len(column)) for column in zip(*dataset)]
	# 将依据标签计算的均值方差剔除掉
    del(summaries[-1])
	return summaries

zip(*iterable) 可以将二维数组进行解压序列，再将其进行打包成元组，在这里是将二维数组的每一列打包成一个元组。

测试：

# Test summarizing a dataset
dataset = [[3.393533211,2.331273381,0],
	[3.110073483,1.781539638,0],
	[1.343808831,3.368360954,0],
	[3.582294042,4.67917911,0],
	[2.280362439,2.866990263,0],
	[7.423436942,4.696522875,1],
	[5.745051997,3.533989803,1],
	[9.172168622,2.511101045,1],
	[7.792783481,3.424088941,1],
	[7.939820817,0.791637231,1]]
summary = summarize_dataset(dataset)
print(summary)

结果：

[(5.178333386499999, 2.7665845055177263, 10), (2.9984683241, 1.218556343617447, 10)]

(5.178333386499999, 2.7665845055177263, 10) 表示 dataset 的第一列计算的均值、方差和元素个数

(2.9984683241, 1.218556343617447, 10) 表示 dataset 的第二列计算的均值、方差和元素个数

Step 3: Summarize Data By Class

根据不同的类别进行统计；

# Split dataset by class then calculate statistics for each row
def summarize_by_class(dataset):
	separated = separate_by_class(dataset)
	summaries = dict()
	for class_value, rows in separated.items():
		summaries[class_value] = summarize_dataset(rows)
	return summaries

separate_by_class() 返回一个字典，key 为标签，value 为每个标签下的样本。

summarize_by_class() 返回一个字典，key 为标签，value 为标签对应下的样本每个特征的统计量 (每一列的特征通缉令为一个元组)。

测试：

# Test summarizing by class
dataset = [[3.393533211,2.331273381,0],
	[3.110073483,1.781539638,0],
	[1.343808831,3.368360954,0],
	[3.582294042,4.67917911,0],
	[2.280362439,2.866990263,0],
	[7.423436942,4.696522875,1],
	[5.745051997,3.533989803,1],
	[9.172168622,2.511101045,1],
	[7.792783481,3.424088941,1],
	[7.939820817,0.791637231,1]]
summary = summarize_by_class(dataset)
for label in summary:
	print(label)
	for row in summary[label]:
		print(row)

结果：

0
(2.7420144012, 0.9265683289298018, 5)
(3.0054686692, 1.1073295894898725, 5)
1
(7.6146523718, 1.2344321550313704, 5)
(2.9914679790000003, 1.4541931384601618, 5)

Step 4: Gaussian Probability Density Function

概率密度函数： \(P(x_i | y_k)=\frac{1}{\sqrt{2\pi\sigma^2_{yk}}}exp(-\frac{(x_i-\mu_{yk})^2}{2\sigma^2_{yk}})\)

# Calculate the Gaussian probability distribution function for x
def calculate_probability(x, mean, stdev):
	exponent = exp(-((x-mean)**2 / (2 * stdev**2 )))
	return (1 / (sqrt(2 * pi) * stdev)) * exponent

测试：

# Example of Gaussian PDF
from math import sqrt
from math import pi
from math import exp
 
# Calculate the Gaussian probability distribution function for x
def calculate_probability(x, mean, stdev):
	exponent = exp(-((x-mean)**2 / (2 * stdev**2 )))
	return (1 / (sqrt(2 * pi) * stdev)) * exponent
 
# Test Gaussian PDF
print(calculate_probability(1.0, 1.0, 1.0))
print(calculate_probability(2.0, 1.0, 1.0))
print(calculate_probability(0.0, 1.0, 1.0))

结果：

0.3989422804014327 0.24197072451914337 0.24197072451914337

Step 5: Class Probabilities

The probability that a piece of data belongs to a class is calculated as follows:

P(class l data) = P(X l class) * P(class)

For the above example where we have 2 input variables, the calculation of the probability that a row belongs to the first class 0 can be calculated as:

P(class=0 l X1,X2) = P(X1 l class=0) * P(X2 l class=0) * P(class=0)

# Calculate the probabilities of predicting each class for a given row
def calculate_class_probabilities(summaries, row):
	total_rows = sum([summaries[label][0][2] for label in summaries])
	probabilities = dict()
	for class_value, class_summaries in summaries.items():
		probabilities[class_value] = summaries[class_value][0][2]/float(total_rows)
		for i in range(len(class_summaries)):
			mean, stdev, count = class_summaries[i]
			probabilities[class_value] *= calculate_probability(row[i], mean, stdev)
	return probabilities

测试：

# Test calculating class probabilities
dataset = [[3.393533211,2.331273381,0],
	[3.110073483,1.781539638,0],
	[1.343808831,3.368360954,0],
	[3.582294042,4.67917911,0],
	[2.280362439,2.866990263,0],
	[7.423436942,4.696522875,1],
	[5.745051997,3.533989803,1],
	[9.172168622,2.511101045,1],
	[7.792783481,3.424088941,1],
	[7.939820817,0.791637231,1]]
summaries = summarize_by_class(dataset)
probabilities = calculate_class_probabilities(summaries, dataset[0])
print(probabilities)

输出：{0: 0.05032427673372075, 1: 0.00011557718379945765}

参考

  1. 朴素贝叶斯算法原理小结
  2. Naive Bayes Classifier From Scratch in Python
  3. 朴素贝叶斯
  4. 为什么样本方差（sample variance）的分母是 n-1？

上一篇 LeetCode刷题（python）—— 434、438、459、520

下一篇 PCA中协方差矩阵、矩阵特征值、特征向量的计算

Comments

Content