数据挖掘读书笔记--第八章(中)：分类：贝叶斯分类法 、基于规则分类
散记知识点
——“继续学习经典分类算法”
3. 贝叶斯分类法(Naive Bayesian)
贝叶斯分类法是统计学分类方法，基于贝叶斯定理。朴素贝叶斯分类法可以与决策树和经过挑选的神经网络分类器相媲美。用于大型数据库，贝叶斯分类法也表现出高准确率和高速度。
3.1 贝叶斯定理
设数据元组X有n个属性，给定的个属性值已知的条件下，被认定为类别C的概率为P(C|X)，称为后验概率也即我们要求的概率。
P(X)、P(C)称为先验概率 ，其中P(X)可以用出现的概率来估计。比如，在顾客集合中，年龄为35岁且收入为4万美元的概率。P(C)为类别的先验概率，可以用类在整个数据集出现的频率来估计。
P(X|C)是在类别为的条件下，的后验概率。例如，已知类别为顾客购买计算机，则的年龄为35岁收入为4万元的概率。
根据已知数据集D，我们可以得到P(X)、P(C)和P(X|C)，则在给定一个新的数据元组，来判断它是否属于某类的概率为：（例如，已知年龄为30岁收入为3万美元顾客，则他会购买计算机的概率为：)
即为贝叶斯公式 。
3.2 朴素贝叶斯分类
朴素贝叶斯分类法有个前提条件 ：为了简化运算，假设在给定类别的条件下，每个属性相互独立。这一假设称为类条件独立性 ，大大简化的计算量，故被称为**“朴素”** 贝叶斯分类。
朴素贝叶斯分类的主要过程 如下：
-
(1) 数据集中，每个数据元组有个属性A_1, A_2,..., A_{n}的属性值组成：X=\{x_1, x_2, ..., x_n\}。同时，有m个类C_1, C_2,...,C_n。
- (2) 给定数据元组，使用贝叶斯定理预测属于使得P(C_i|X)最大的类C_{i}:
的类称为最大后验假设。则：
* **(3)** 由于$P(X)=\sum_{i=1}^m P(X|C_i)P(C_i)$对所有类为常数。所以只需关心$P(X|C_i)P(C_i)$最大即可。
* **①** 如果类先验概率可知，类先验概率可用$P(C_i)=|C_{i,D}|\ /\ |D|$估计，其中$|C_{i,D}|$是中$C_i$类的训练元组个数。
* **②** 如果类别的先验概率未知，则通常假定这些类是等概率的，即$P(C_1)=P(C_2)=...=P(C_m)$，据此简化为对最大化。
* **(4)** 若数据集具有许多属性，计算$P(X|C_i)$开销很大，使用类条件独立的朴素假定：即在给定类别条件下，属性值相互独立：其中，x_k为元组在属性A_k的值。对于属性，考察两种情况:
* 如果是离散属性，则$P(x_k|C_i)$是中属性的值为的类的元组数除以中类的元组数。
* 如果是连续值属性，通常假定连续值服从均值为$\mu$、标准差为$\sigma$的高斯分布：因此 其中\mu_{C_i},\sigma_{C_i}分别是类训练元组属性A_{k}的均值和标准差。
* **(5)** 对给定数据元组预测它的类标号:
* * * *3.3 Python简单实现朴素贝叶斯分类器
# -*- coding: utf-8 -*-
__author__ = "Yunfan Yang"
def data_prep(filename):
"""数据预处理，属性列表以及数据元组列表"""
with open(filename,'r') as f:
raw_data = f.read() # 读取数据
# print(raw_data)
data_list = raw_data.split('\n')[:-1] # 将文本数据转换为列表
Attributes = [] # 属性和类别名称列表
X_list = [] # 数据元组列表
for i in range(len(data_list)):
X = []
if i == 0:
Attributes = data_list[i].split(',') # 创建属性列表
else:
X = data_list[i].split(',') # 元组列表
X_list.append(X)
return Attributes, X_list
def get_class_value(Attributes, X_list):
"""获取类别列表"""
classes_values = []
for X in X_list:
if X[-1] not in classes_values:
classes_values.append(X[-1])
return classes_values
def calculate_prob(attribute_and_value, classes_values, Attributes, X_list):
"""计算概率（先验概率和后验概率）"""
for key,value in attribute_and_value.items():
index = Attributes.index(key) # 获取属性在属性列表中的索引
attribute_value = value
prior_prob = {}
posterior_prob = {}
for label in classes_values: # 遍历类别列表
class_count = 0
attribute_count = 0
for X in X_list: # 遍历数据集
if X[-1] == label:
class_count += 1
if X[index] == attribute_value:
attribute_count += 1
prior_prob[label] = class_count / len(X_list) # 类别自身的先验概率
posterior_prob[label] = attribute_count / class_count # 类别条件下，属性值的后验概率
return prior_prob, posterior_prob
def Bayesian_Predict(input_X, classes_values, Attributes, X_list):
"""朴素贝叶斯分类预测"""
pre_dict = {}
for label in classes_values: # 遍历类别值列表
X_C_prob = 1
for key,value in input_X.items(): # 遍历输入数据元组的键值对
attribute_and_value = {}
attribute_and_value[key]=value # 生成属性和属性值字典
prior_prob, posterior_prob = calculate_prob(attribute_and_value, classes_values, Attributes, X_list) # 计算概率值
X_C_prob *= posterior_prob[label] # 累乘得到，类别条件下，数据元组的后验概率
C_X_prob = X_C_prob * prior_prob[label] # 给定数据元组条件下的类别概率
pre_dict[label] = C_X_prob # 键为类别值，值为后验假设概率
# 按照从大到小排列
predict = sorted(pre_dict.items(), reverse=True, key=lambda x:x[1])
# 最可能的类别值
result = predict[0][0]
# 最可能类别值的概率
sum = 0
for value in predict:
sum+=value[1]
result_prob = predict[0][1] / sum # 预测类别的概率
print("\n该数据元组最可能的类别是：", result)
print("判断为该类别的概率为：{}%".format(round(result_prob*100,1)))
if __name__=="__main__":
filename = 'raw_data.csv' # 读取文件，数据预处理
Attributes, X_list = data_prep(filename) # 对于每个X，第一个值时标号，最后一个是类别，中间都是属性值
# print(Attributes)
# print(X_list)
classes_values = get_class_value(Attributes, X_list)
# 输入的未知分类元组
input_X = {'age':'youth', 'income':'high', 'student': 'yes', 'credit_rating':'fair'}
# 进行分类预测
Bayesian_Predict(input_X, classes_values, Attributes, X_list)
运行结果为：
该数据元组最可能的类别是： yes
判断为该类别的概率为：67.3%
3.4 零概率值处理
在计算的过程中，有可能会出现某个后验概率值P(x_k|C_i)=0的情况。考虑这个零概率值，会使得P(X|C_{i})为0，一个零概率值将消除概率累乘中涉及到的所有属性值的后验概率影响。
可以使用拉普拉斯校准法 避免这个问题：在计算时，分子分母计数同时加1。
4. 基于规则分类
4.1 IF-THEN规则分类
IF-THEN 规则表达式形如： IF条件THEN结论 例如，R1：IF age=youth AND student=yes THEN buys_computer=yes
规则R可以用覆盖率和准确率评估，在数据集，设n_{covers}为规则R覆盖的元组数，n_{correct}为R正确分类的元组数，则R的覆盖率 和准确率 定义为：
4.2 由决策树提取规则
提取方法 ：
* 对每条从根结点到树叶结点的路径创建一条规则。
* 沿着给定路径上的每个分裂准则的逻辑（根结点=分枝）AND形成规则的前件(IF部分)。
* 存放类预测的树叶结点形成规则的后件(THEN部分)。与决策树相比， IF-THEN 规则更容易理解，特别当决策树非常大时。
4.3 顺序覆盖算法的规则归纳
使用顺序覆盖算法可以直接从训练数据提取 IF-THEN 规则（不需要产生决策树）。顺序覆盖算法是最广泛使用的挖掘分类规则析取集的方法。
(1) 顺序覆盖算法
算法的一般策略 如下：
* 一次学习一个规则。每学习一个规则，就删除该规则覆盖的元组，并在剩下的元组上重复该过程。
* 在为类学习规则时，希望规则覆盖类所有（或很多）训练元组，并且没有（或很少）覆盖其他类的元组，以此来保证规则的高准确率。
* 继续执行直到满足**终止条件** ：①不在有训练元组；②返回规则质量低于设定阈值。 
(2) 规则质量度量
单纯地考虑规则准确率和覆盖率有的时候并不可靠。
假设学习类c的规则，当前规则为R：IF \ \ condition \ \ THEN\ \ class=c，考虑一个新的规则R^{'}：IF \ \ condition^{'} \ \ THEN\ \ class=c，比较前后两个规则谁比较好，则可以使用以下度量：
* **① 熵** ：考虑 $condition^{'}$覆盖的数据元组集合，$p_i$为中类的概率。则熵越小，越好，规则就越好。
* **② 信息增益** ：在机器学习中，用于学习规则的元组为**正元组** ，其余元组为**负元组** ，设$pos(neg)$和$pos^{'}(neg^{'})$为被$R$和$R{’}$覆盖的正（负）元组数。在一阶归纳学习器FOIL中，估计扩展的信息增益： 它偏向于具有**高准确率且覆盖许多正元组** 的规则。
* **③ 统计显著性检验** ：确定规则的效果是否并非出于偶然性，而是预示**属性值与类之间的真实相关性** 。该检验将规则付该元组的观测类分布与规则随机预测产生的期望类分布进行比较，评估这两个分布之间的观测差是否是随机的，使用**似然率统计量** : 其中，为类数，$f_i$是满足规则的元组中类$i$的观测频率。$e_i$是规则随机预测时类的期望频率。该统计量服从自由度为$m-1$的$\chi^2$分布。似然率越高，规则正确预测数与“随机猜测”的差距越明显。似然率有助于识别具有显著覆盖率的规则。(3) 规则剪枝
为防止过拟合，对规则剪枝，如果在独立的元组集上评估，剪枝后具有更好的质量。与决策树一样，这些元组集称为剪枝集。给定规则，FOIL剪枝策略：
这个值将随着在剪枝集上的准确率增加而增加。因此，如果剪枝后FOIL_Prune值较高，则对剪枝。