10-决策树与贝叶斯

一.什么是决策树

决策树分类的思想类似于找对象。现想象一个女孩的母亲要给这个女孩介绍男朋友，于是有了下面的对话：

女儿：多大年纪了？
母亲：26。
女儿：长的帅不帅？
母亲：挺帅的。
女儿：收入高不？
母亲：不算很高，中等情况。
女儿：是公务员不？
母亲：是，在税务局上班呢。
女儿：那好，我去见见

决策树.png

二.决策树原理

决策树：信息论
逻辑斯蒂回归、贝叶斯：概率论

• 构造决策树(ID3算法)

不同于逻辑斯蒂回归和贝叶斯算法，决策树的构造过程不依赖领域知识，它使用属性选择度量来选择将元组最好地划分成不同的类的属性。所谓决策树的构造就是进行属性选择度量确定各个特征属性之间的拓扑结构。
构造决策树的关键步骤是分裂属性。所谓分裂属性就是在某个节点处按照某一特征属性的不同划分构造不同的分支，其目标是让各个分裂子集尽可能地“纯”。尽可能“纯”就是尽量让一个分裂子集中待分类项属于同一类别。
分裂属性分为三种不同的情况：
1、属性是离散值且不要求生成二叉决策树。此时用属性的每一个划分作为一个分支。
2、属性是离散值且要求生成二叉决策树。此时使用属性划分的一个子集进行测试，按照“属于此子集”和“不属于此子集”分成两个分支。
3、属性是连续值。此时确定一个值作为分裂点split_point，按照>split_point和<=split_point生成两个分支。
构造决策树的关键性内容是进行属性选择度量，属性选择度量是一种选择分裂准则，它决定了拓扑结构及分裂点split_point的选择。
属性选择度量算法有很多，一般使用自顶向下递归分治法，并采用不回溯的贪心策略。这里介绍常用的ID3算法。
贪心算法（又称贪婪算法）是指，在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，他所做出的是在某种意义上的局部最优解

划分原则：将无序的数据变得更加有序

熵:熵这个概念最早起源于物理学，在物理学中是用来度量一个热力学系统的无序程度。
而在信息学里面，熵是对不确定性的度量。
在1948年，香农引入了信息熵，将其定义为离散随机事件出现的概率，一个系统越是有序，信息熵就越低，反之一个系统越是混乱，它的信息熵就越高。所以信息熵可以被认为是系统有序化程度的一个度量。

信息增益:我们可以使用多种方法划分数据集，但是每种方法都有各自的优缺点。组织杂乱无章数据的一种方法就是使用信息论度量信息，信息论是量化处理信息的分支科学。我们可以在划分数据之前使用信息论量化度量信息的内容。
在划分数据集之前之后信息发生的变化称为信息增益，知道如何计算信息增益，我们就可以计算每个特征值划分数据集获得的信息增益，获得信息增益最高的特征就是最好的选择。
在可以评测哪种数据划分方式是最好的数据划分之前，我们必须学习如何计算信息增益。集合信息的度量方式称为香农熵或者简称为熵，这个名字来源于信息论之父克劳德•香农。
熵定义为信息的期望值，在明晰这个概念之前，我们必须知道信息的定义。如果待分类的事务可能划分在多个分类之中，则符号x的信息定义为：

p(x)是选择该分类的概率.png
计算熵:为了计算熵，我们需要计算所有类别所有可能值包含的信息期望值，通过下面的公式得到： n是分类的数目.png 在决策树当中，设D为用类别对训练元组进行的划分，则D的熵（entropy）表示为：其中pi表示第i个类别在整个训练元组中出现的概率，可以用属于此类别元素的数量除以训练元组元素总数量作为估计。熵的实际意义表示是D中元组的类标号所需要的平均信息量 entropy.png
现在我们假设将训练元组D按属性A进行划分，则A对D划分的期望信息为 期望信息.png
信息增益即为两者的差值
差值.png

ID3算法就是在每次需要分裂时，计算每个属性的增益率，然后选择增益率最大的属性进行分裂

下面我们继续用SNS社区中不真实账号检测的例子说明如何使用ID3算法构造决策树。为了简单起见，我>>们假设训练集合包含10个元素


#在决策树当中，设D用为类别对训练元组进行的划分，则D的熵（entropy）表示为：
info_D = -0.7*math.log2(0.7)-0.3*math.log2(0.3)
#计算日志密度的信息增益
info_L = 0.3*(-1/3*math.log2(1/3)-2/3*math.log2(2/3))+0.4*(-1/4*math.log2(1/4)-3/4*math.log2(3/4))+0.3*(-math.log2(1))
l = info_D - info_L

#计算是否使用真是头像的信息增益
info_H = 0.5*(-2/5*math.log2(2/5)-3/5*math.log2(3/5))+0.5*(-1/5*math.log2(1/5)-4/5*math.log2(4/5))
h = info_D - info_H

#计算好友密度的信息增益
info_F = 0.4*(-3/4*math.log2(3/4)-1/4*math.log2(1/4))+0.4*(-math.log2(1))+0.2*(-math.log2(1))
f = info_D - info_F
print(l,h,f)

分裂.png
公式.png
分裂1.png

在上图的基础上，再递归使用这个方法计算子节点的分裂属性，最终就可以得到整个决策树

实战

• 比较KNN、逻辑斯蒂、决策树进行分类
  1.导入包

from sklearn import datasets
from sklearn.tree import DecisionTreeClassifier
from sklearn.neighbors import KNeighborsClassifier
from sklearn.linear_model import LogisticRegression

2.导入数据

iris = datasets.load_iris()
X = iris.data
y = iris.target

3.使用决策树

#max_depth 设置决策树的最大深度
reg1 = DecisionTreeClassifier(max_depth=5)
reg1.fit(X,y).score(X,y)

4.使用KNN

reg2 = KNeighborsClassifier()
reg2.fit(X,y).score(X,y)

5.使用逻辑斯蒂

reg3 = LogisticRegression()
reg3.fit(X,y).score(X,y)

从结果可知，决策树得分最高，预测最准确

• 使用回归预测一个椭圆

方法介绍：np.random.RandomState == np.random.seed()
真正意义上的随机数（或者随机事件）在某次产生过程中是按照实验过程中表现的分布概率随机产生的，其结果是不可预测的，是不可见的。
计算机中的随机函数是按照一定算法模拟产生的，其结果是确定的，是可见的。我们可以这样认为这个可预见的结果其出现的概率是100%。所以用计算机随机函数所产生的“随机数”并不随机，是伪随机数

1.导入包

import numpy as np
import matplotlib.pyplot as plt
from sklearn.tree import DecisionTreeRegressor

2.创造数据，椭圆

# 创建X与y
rng = np.random.RandomState(1) #伪随机数 == np.random.seed(1)

#随机生成-100 到100的数字,这些数字就是角度
X = np.sort(200 * rng.rand(100,1) - 100,axis = 0)
#根据角度生成正弦值和余弦值，这些值就是圆上面的点
y = np.array([np.pi * np.sin(X).ravel(),np.pi * np.cos(X).ravel()]).transpose()
y[::5,:] += (0.5 -rng.rand(20,2))#添加噪声

3.训练数据

参数max_depth越大，越容易过拟合
# 第1步：训练
regr1 = DecisionTreeRegressor(max_depth=2)
regr2 = DecisionTreeRegressor(max_depth=5)
regr3 = DecisionTreeRegressor(max_depth=8)

regr1.fit(X,y)
regr2.fit(X,y)
regr3.fit(X,y)

4.预测数据

# 第2步：预测
X_test = np.arange(-100.0,100.0,0.01)[:,np.newaxis]
y_1 = regr1.predict(X_test)
y_2 = regr2.predict(X_test)
y_3 = regr3.predict(X_test)

5.根据数据绘制椭圆

# 显示图像
plt.figure(figsize=(12,8))
s = 50

plt.subplot(221)
plt.scatter(y[:,0],y[:,1],c='navy',s=s,label='data')
plt.legend()

plt.subplot(222)
plt.scatter(y_1[:,0],y_1[:,1],c='b',s=s,label='data')
plt.legend()

plt.subplot(223)
plt.scatter(y_2[:,0],y_2[:,1],c='r',s=s,label='data')
plt.legend()

plt.subplot(224)
plt.scatter(y_3[:,0],y_3[:,1],c='g',s=s,label='data')
plt.legend()

plt.show()

椭圆.png

三.贝叶斯

一.什么是贝叶斯

公式.png
例如：一座别墅在过去的 20 年里一共发生过 2 次被盗，别墅的主人有一条狗，狗平均每周晚上叫 3 次，在盗贼入侵时狗叫的概率被估计为 0.9，问题是：在狗叫的时候发生入侵的概率是多少？
我们假设 A 事件为狗在晚上叫，B 为盗贼入侵，则以天为单位统计，P(A) = 3/7，P(B) = 2/(20365) = 2/7300，P(A|B) = 0.9，按照公式很容易得出结果：P(B|A) = 0.9(2/7300) / (3/7) = 0.00058

另一个例子，现分别有 A、B 两个容器，在容器 A 里分别有 7 个红球和 3 个白球，在容器 B 里有 1 个红球和 9 个白球，现已知从这两个容器里任意抽出了一个球，且是红球，问这个红球是来自容器 A 的概率是多少?
假设已经抽出红球为事件 B，选中容器 A 为事件 A，则有：P(B) = 8/20，P(A) = 1/2，P(B|A) = 7/10，按照公式，则有：P(A|B) = (7/10)*(1/2) / (8/20) = 0.875

一般公式.png

二.朴素贝叶斯原理

原理公式.png

主要核心思想:
朴素贝叶斯的思想基础是这样的：对于给出的待分类样本特征x，求解在此样本出现的条件下各个类别出现的概率，哪个最大，就认为此待分类样本属于哪个类别。
朴素的概念：独立性假设，假设各个特征之间是独立不相关的。

三.贝叶斯模型

• 高斯分布朴素贝叶斯
  特征值为连续型变量

高斯模型假设某一特征属于某一类别的观测值符合高斯分布，比如身高小于160，160~170和170以上

高斯分布就是正态分布
【用途】用于一般分类问题
使用自带的鸢尾花数据

from sklearn import datasets
iris = datasets.load_iris()
X = iris.data
y = iris.target

from sklearn.naive_bayes import GaussianNB
gnb = GaussianNB()

gnb.fit(X,y).score(X,y)

• 多项式分布朴素贝叶斯
  文本分类，特征是单词，值是单词的出现次数

多项式分布：
【用途】适用于文本数据（特征表示的是次数，例如某个词语的出现次数
from sklearn.naive_bayes import MultinomialNB

mnb = MultinomialNB()
mnb.fit(X,y).score(X,y)

• 伯努利分布朴素贝叶斯
  特征值取bool类型，文本分类中表示一个值（单词）有没有出现过

伯努利分布：
【用途】适用于伯努利分布，也适用于文本数据（此时特征表示的是是否出现，例如某个词语的出现为1，不出现为0）
绝大多数情况下表现不如多项式分布，但有的时候伯努利分布表现得要比多项式分布要好，尤其是对于小数量级的文本数据

from sklearn.naive_bayes import BernoulliNB

bnb = BernoulliNB()
bnb.fit(X,y).score(X,y)

得分要比多项式分布朴素贝叶斯差

四.实战

4.1 文本分类，对短信进行二分类--->使用多项式分布朴素贝叶斯
1.导包加载数据

import pandas as pd
from sklearn.naive_bayes import MultinomialNB
#转换数据，String串分析起来不方便，所以需要将字符串转进行转换
from sklearn.feature_extraction.text import TfidfVectorizer 
data = pd.read_table('../data/SMSSpamCollection',header = None)

2.处理数据

tf = TfidfVectorizer()
display(data[1].shape,type(data[1]))
X = tf.fit_transform(data[1])
y = data[0]

3.训练数据

mnb = MultinomialNB()
#训练数据
mnb.fit(X,y)

4.预测数据

# 使用tf.transform把文本变成能处理的数字，生成一个测试数据
X_test = tf.transform(['07732584351 - Rodger Burns - MSG = We tried to call you re your reply to our sms for a free nokia mobile + free camcorder. Please call now 08000930705 for delivery tomorrow'])

#预测数据
mnb.predict(X_test)

输出结果显示这是一条垃圾短信

4.2 对email进行二分类，两种邮件分别在ham和spam目录下
1.导包

import numpy as np
import pandas as pd
# 把文本处理成稀疏矩阵（向量）
from sklearn.feature_extraction.text import TfidfVectorizer
# 【注意】一般使用多项式分布朴素贝叶斯
from sklearn.naive_bayes import MultinomialNB

2.读取文本数据

path1 = './data/email/ham/'
label1 = 'ham'
path2 = './data/email/spam/'
label2 = 'spam'

#定义方法，读取文本数据
def file2df(label,path):
    l = []
    #循环遍历每个文件
    for i in range(25):
        #file 路径是字符串的相加
        data = open(file = path+str(1+i)+'.txt',errors = 'ignore').read()
        l.append([data,label])
    df = pd.DataFrame(l)
    return df
df1 = file2df(label1,path1)
df2 = file2df(label2,path2)

#合并邮件的数据
df = pd.concat([df1,df2])

3.处理数据获取测试数据以及预测数据：

# 得到X
X = df[0]
# 使用内置转换器TfidfVectorizer，把X由文本转化为向量，这样X就是二维矩阵
tf = TfidfVectorizer()
X = tf.fit_transform(X)

# 使用train_test_split自动打乱顺序，并得到训练和测试数据集
from sklearn.model_selection import train_test_split
X_train,X_test = train_test_split(X,test_size=0.2,random_state=2)
y_train,y_test = train_test_split(df[1],test_size=0.2,random_state=2)

4.训练数据预测数据

# 建立模型
mnb = MultinomialNB()
# 训练模型
mnb.fit(X_train,y_train)
# 打分
# mnb.score(X_test,y_test)
p_data = mnb.predict(X_test)
display(p_data,y_test)