机器学习-决策树算法_决策树 算法

决策树算法简介

决策树：是一种树形结构，其中每个内部节点表示一个属性上的判断，每个分支代表一个判断结果的输出，最后每个叶节点代表一种分类结果，本质是一颗由多个判断节点组成的树。
决策树定义：

• 是一种树形结构，
• 本质是一颗由多个判断节点组成的树

决策树分类原理

熵Entropy

物理学上，熵 Entropy 是“混乱”程度的量度。
系统越有序，熵值越低；系统越混乱或者分散，熵值越高。
信息熵：
1、从信息的完整性上进行的描述:
当系统的有序状态一致时，数据越集中的地方熵值越小，数据越分散的地方熵值越大。
2、从信息的有序性上进行的描述:
当数据量一致时，系统越有序，熵值越低；系统越混乱或者分散，熵值越高。

当前样本集合 D 中第 k 类样本所占的比例为 p​k(k = 1, 2,. . . , |y|) ，
pk=C^k/D, D为样本的所有数量，
C^k为第k类样本的数量。
Ent(D) 的值越小，则 D 的纯度越高.
D的信息熵定义为:

数据越纯,信息熵就越低,越不纯,信息熵就越高

信息增益

• 决策树的划分依据
• 信息增益：以某特征划分数据集前后的熵的差值。可以使用划分前后集合熵的差值来衡量使用当前特征对于样本集合D划分效果的好坏。
• 信息增益 = entroy(前) - entroy(后)
  • 注：信息增益表示得知特征X的信息而使得类Y的信息熵减少的程度

特征a对训练数据集D的信息增益Gain(D,a),定义为集合D的信息熵Ent(D)与给定特征a条件下D的信息条件熵Ent(D|a)Ent(D∣a)之差。

信息熵的计算：

条件熵的计算：

D​^v表示a属性中第v个分支节点包含的样本数
C^kv表示a属性中第v个分支节点包含的样本数中，第k个类别下包含的样本数。
信息增益越大，则意味着使用属性 a 来进行划分所获得的"纯度提升"越大。

• 信息增益准则对可取值数目较多的属性有所偏好
• 可以分更过的子集,减熵最多

案例

信息增益率

信息增益准则对可取值数目较多的属性有所偏好，为减少这种偏好可能带来的不利影响
C4.5 决策树算法不直接使用信息增益，而是使用"增益率" (gain ratio) 来选择最优划分属性.

• 属性 a 的可能取值数目越多(即 V 越大)，则 IV(a) 的值通常会越大.

信息增益率=信息增益/特征分割熵
特征a分叉较多,分子会变大,分母也会变大
解决了信息增益偏向取值种类数较多的特征的缺点

案例

接上一个案例

基尼值和基尼指数

CART 决策树 使用"基尼指数" (Gini index)来选择划分属性.
基尼值Gini（D）：从数据集D中随机抽取两个样本，其类别标记不一致的概率。Gini（D）值越小，数据集D的纯度越高。

案例

总结

两个"不纯度”指标

• 信息熵：不纯度越高,熵越大、不纯度越低 熵越小

• gini系数(基尼系数)： 也是来衡量不纯度的、 不纯度越高,gini系数值越高,不纯度越低,gini系数值越低

• gini系数好：计算简单

  • 熵:对数计算 (在计算机中对数是不能直接计算的,是通过级数进行近似计算,计算复杂)
  • gini系数:乘法

• 对比: 二者意义一模一样

• 计算复杂度:

  • gini系数采用乘法计算,简单快
  • 熵采用对数计算,对数计算复杂,慢

三个"最优分割"指标

• 信息增益–ID3：信息增益=entropy(前)-entropy(后)

  • 减熵=信息增益
  • 信息增益准则对可取值数目较多的属性有所偏好
    • 可以分更过的子集,减熵最多
    • 选择信息增益最大的特征作为划分特征
    • 公式解释: 分割前的熵(整体熵)-分割后的熵(每一个子集的熵的加权(每个子集的样本比例)平均值)
    • 注意:信息增益会选择取值种类多的特征(分叉多的特征)

• 信息增益率–C4.5：解决信息增益偏向选择属性值比较多的特征的缺点

• gini信息增益—cart树

  • 对比
    • 信息增益=entropy(前)-entropy(后)
    • gini信息增益=gini系数(前)-gini系数(后)
  • 同样存在信息增益的缺点:
    • 偏向选择属性值比较多的特征的缺点
  • 如何解决: 采用强制二叉树
  • 特征处理方式
    • 二类特征— 直接二叉
    • 多类特征 —A,B,C,D
      • 遍历每一种不同的二分模式,分别计算gini系数
    • 数值特征
      • 排序
      • 找相邻点的中点作为分割点
        • 如何优化? 可以只对两边类别不一致的分割点进行计算

• 做回归:mse均方差—方差最小化
  

常见决策树的启发函数比较

ID3,c4.5,cart对比

ID3 算法

• 采用信息增益
• 缺点:偏向选择属性值较多的特征
• 只能处理离散类别特征

C4.5
(1) 用信息增益率来选择属性
(2) 可以处理连续数值型属性
(3)采用了一种后剪枝方法
(4)对于缺失值的处理
（5）解决了偏向取值较多的特征这个问题
CART算法

• 采用gini信息增益
• 强制二叉树
• 既能做分类也能做回归
  • 分类:gini信息增益/信息增益
  • 回归:mse/mae
• 特征处理
  • 离散类别: ==
  • 连续数值:<某个值 >=某个值
• 决策树选择最优特征原理:
  • 贪心算法:每一步选择当前利益最大化的决策
    • 每一部分割选择能够让当前数据减熵最多的特征
  • 是近似解 不是最优解
  • 最小子集覆盖问题

多变量决策树(multi-variate decision tree)

• 选择多个特征的线性组合来进行分割

决策树变量的两种类型：

• 数值型：排序、相邻点中点作为分割点 < 和 >= 分两叉
• 类别型： 使用“=”来分割 是不是

评估分割点的好坏

• 指标： 信息增益、 信息增益率、 gini信息增益
• 思想: 贪心算法 当前利益最大化

cart剪枝

剪枝原因【了解】

• 防止决策树过拟合
• 决策树一个非线性模型,拟合能力强

噪声、样本冲突，即错误的样本数据
特征即属性不能完全作为分类标准
巧合的规律性，数据量不够大。

常用剪枝方法

• 预剪枝----设置参数限制树的生长
  在构建树的过程中，同时剪枝
  限制节点最小样本数
  指定数据高度
  指定熵值的最小值
• 后剪枝—先生长,再剪枝 c4.5
  把一棵树，构建完成之后，再进行从下往上的剪枝

特征工程-特征提取

将任意数据（如文本或图像）转换为可用于机器学习的数字特征
注：特征值化是为了计算机更好的去理解数据
特征提取分类:
字典特征提取(特征离散化)
文本特征提取
图像特征提取（深度学习将介绍）

• sklearn.feature_extraction

字典特征提取

• 实现类别特征onehot映射
  作用：对字典数据进行特征值化

• sklearn.feature_extraction.DictVectorizer(sparse=True,…)

• DictVectorizer.fit_transform(X)

  • X:字典或者包含字典的迭代器返回值
  • sparse=True:返回sparse矩阵 默认的
  • sparse=False:返回完整矩阵

• DictVectorizer.get_feature_names() 返回类别名称

• 接收的数据必须是字典构成的列表

• 仅对离散特征做onehot映射,连续特征保持不动

from sklearn.feature_extraction import DictVectorizer

#获取数据
data = [{'city': '北京','temperature':100}, {'city': '上海','temperature':60}, {'city': '深圳','temperature':30}]
#实例化对象
transfer=DictVectorizer()
#进行转换
new_data=transfer.fit_transform(data)
#打印结果
print(new_data)  #返回的是稀疏矩阵  很多0的矩阵  少部分元素有值

#实例化对象
transfer=DictVectorizer(sparse=False)
#进行转换
new_data=transfer.fit_transform(data)
#打印结果
print(new_data)#返回的就是完整矩阵

#转换成dataFrame
import pandas as pd
pd.DataFrame(new_data,columns=transfer.get_feature_names())

文本特征提取

作用：对文本数据进行特征值化

• sklearn.feature_extraction.text.CountVectorizer(stop_words=[])

• 返回词频矩阵

• CountVectorizer.fit_transform(X)

  • X:文本或者包含文本字符串的可迭代对象
  • 返回值:返回sparse矩阵

• CountVectorizer.get_feature_names() 返回值:单词列表

• sklearn.feature_extraction.text.TfidfVectorizer —— tfidf特征
  调用fit_transform方法输入数据并转换 （注意返回格式，利用toarray()进行sparse矩阵转换array数组）

• 统计每句话出现的词频

• 词典:所有文本中出现不同词

  • 由于词典往往很大,向量一定是极度稀疏的

• 特点:词频越大,这个词就越重要
  常用词:所有文章中都出现,而且挺多
  放大了常用词的重要性

# 英文特征提取
from sklearn.feature_extraction.text import CountVectorizer
#获取数据
data=["life is short,i like like python", "life is too long,i dislike python"]
#实例化对象
vector=CountVectorizer()
#转换
new_data=vector.fit_transform(data)
print(new_data.toarray())#词频向量

#封装dataFrame
pd.DataFrame(new_data.toarray(),columns=vector.get_feature_names())

# #输出词典
vector.vocabulary_

jieba库

jieba分词处理

pip install jieba

• jieba.cut()
  • 返回词语组成的生成器

## 中文特征提取
data=["人生苦短，我喜欢Python","生活太长久，我不喜欢Python"]
#实例化对象
vector=CountVectorizer()
#转换
new_data=vector.fit_transform(data)
print(new_data.toarray())#词频向量
#封装dataFrame
pd.DataFrame(new_data.toarray(),columns=vector.get_feature_names())

## 用空格隔开
data=["人生 苦短，我 喜欢 Python","生活 太 长久，我 不喜欢 Python"]
#实例化对象
vector=CountVectorizer()
#转换
new_data=vector.fit_transform(data)
print(new_data.toarray())#词频向量
#封装dataFrame
pd.DataFrame(new_data.toarray(),columns=vector.get_feature_names())

利用jieba进行分词

两种返回结果

三种分词模式

此种方法会自动省略标点、单个字

#利用jieba进行分词
import jieba
def cut_words(text):
    return " ".join(jieba.lcut(text))

测试函数
cut_words("一种还是一种今天很残酷，明天更残酷，后天很美好，但绝对大部分是死在明天晚上，所以每个人不要放弃今天。")

data=["一种还是一种今天很残酷，明天更残酷，后天很美好，但绝对大部分是死在明天晚上，所以每个人不要放弃今天。",
            "我们看到的从很远星系来的光是在几百万年之前发出的，这样当我们看到宇宙时，我们是在看它的过去。",
            "如果只用一种方式了解某样事物，你就不会真正了解它。了解事物真正含义的秘密取决于如何将其与我们所了解的事物相联系。"]
#进行分词
sentences=[]
for sentence in data:
    sentences.append(cut_words(sentence))
print(sentences)

#实例化对象
vector=CountVectorizer()
#转换
new_data=vector.fit_transform(sentences)
print(new_data.toarray())#词频向量
#封装dataFrame
pd.DataFrame(new_data.toarray(),columns=vector.get_feature_names())
## 此种方法会自动省略标点、单个字

给定分词器

#实例化对象
#tokenizer  传给一个函数  功能是来做分词
vector=CountVectorizer(tokenizer=jieba.lcut)
#转换
new_data=vector.fit_transform(data)#直接将原文本传给对象进行提取
print(new_data.toarray())#词频向量
#封装dataFrame
pd.DataFrame(new_data.toarray(),columns=vector.get_feature_names()).T

# 给定停用词
#实例化对象
#tokenizer  传给一个函数  功能是来做分词
stop_words={'。','，','的','你','我','它','还是'}
#实力阿虎对象  给定参数
vector=CountVectorizer(tokenizer=jieba.lcut,stop_words=stop_words)
#转换
new_data=vector.fit_transform(data)#直接将原文本传给对象进行提取
print(new_data.toarray())#词频向量
#封装dataFrame
pd.DataFrame(new_data.toarray(),columns=vector.get_feature_names()).T

• jieba使用:
  • jieba.cut 返回迭代器 节省内存
  • jieba.lcut 返回词构成的列表
  • 三种模式
    • 精确模式 jieba.cut(text)
    • 全模式 jieba.cut(text,cut_all=True)
    • 搜索引擎模式 jieba.cut_for_search
• 词频特征提取
  • 英文提取 本身有空格
  • 中文提取：手动打空格、 利用jieba进行分词打空格、直接将jieba.cut给到CountVectorizer

    • #tokenizer  传给一个函数  功能是来做分词
      vector=CountVectorizer(tokenizer=jieba.lcut)
      

    • 给定停用词
      • 停用词:对文本分类没有意义的词

      • #tokenizer  传给一个函数  功能是来做分词
        stop_words={'。','，','的','你','我','它','还是'}
        #实力化对象  给定参数
        vector=CountVectorizer(tokenizer=jieba.lcut,stop_words=stop_words)
        

  • 词频特征有一个缺点:
    • 会放大常用词的重要性

Tf-idf文本特征提取

如果某个词或短语在一篇文章中出现的概率高，并且在其他文章中很少出现，则认为此词或者短语具有很好的类别区分能力，适合用来分类。
TF-IDF作用：用以评估一字词对于一个文件集或一个语料库中的其中一份文件的重要程度。

公式

词频（term frequency，tf）指的是某一个给定的词语在该文件中出现的频率
逆向文档频率（inverse document frequency，idf）是一个词语普遍重要性的度量。某一特定词语的idf，可以由总文件数目除以包含该词语之文件的数目，再将得到的商取以10为底的对数得到

data=["一种还是一种今天很残酷，明天更残酷，后天很美好，但绝对大部分是死在明天晚上，所以每个人不要放弃今天。",
            "我们看到的从很远星系来的光是在几百万年之前发出的，这样当我们看到宇宙时，我们是在看它的过去。",
            "如果只用一种方式了解某样事物，你就不会真正了解它。了解事物真正含义的秘密取决于如何将其与我们所了解的事物相联系。"]
#进行分词
sentences=[]
for sentence in data:
    sentences.append(cut_words(sentence))
print(sentences)

from sklearn.feature_extraction.text import TfidfVectorizer
#实例化对象
vector=TfidfVectorizer()
#转换
new_data=vector.fit_transform(sentences)
print(new_data.toarray())#词频向量   都哦是小数  做了正则化(单位向量) 

#封装dataFrame
pd.DataFrame(new_data.toarray(),columns=vector.get_feature_names()).T

#实例化对象
#tokenizer  传给一个函数  功能是来做分词
stop_words={'。','，','的','你','我','它','还是'}
#实力化对象  给定参数
vector=TfidfVectorizer(tokenizer=jieba.lcut,stop_words=stop_words)
#转换
new_data=vector.fit_transform(data)#直接将原文本传给对象进行提取
print(new_data.toarray())#词频向量
#封装dataFrame
pd.DataFrame(new_data.toarray(),columns=vector.get_feature_names()).T

• tfidf
  • tf – 词频
  • idf – 逆向文档频率
    • 一个词出现的文章数越多,idf越小
    • 出现的文章数越小,idf越大
• api:sklearn.feature_extraction.text.TfidfVectorizer
• 注意：分类机器学习算法进行文章分类中前期数据处理方式

注意点

初始化OneHotEncoder实例时，默认sparse参数为True，编码后返回的是一个稀疏矩阵的对象，如果要使用，一般要调用toarray()方法转化成array对象。若将sparse参数设置为False，则直接生成array对象，可直接使用。

决策树算法api

• 分类：class sklearn.tree.DecisionTreeClassifier(criterion=’gini’, max_depth=None,random_state=None)
  回归:DecisionTreeRegressor()
• criterion:计算不纯度的指标
  • 分类:gini或者entropy
  • 注意:不管是那种,最终都是二叉树,所以都是cart树
  • 回归:mse或者mae
• min_samples_split=n 少于n个不能分了
  • 越大,树被限制的越厉害
• min_samples_leaf =k 分了之后子节点样本数少于k个就不能分
  • 越大,树被限制的越厉害
• max_depth 深度
  • 越小,树被限制的越厉害

回归:class sklearn.tree.DecisionTreeRegressor(criterion=’mse’, max_depth=None,random_state=None)

• criterion=’mse’,mae

案例：泰坦尼克号乘客生存预测

1.获取数据
2.数据基本处理
2.1 确定特征值,目标值
2.2 缺失值处理
2.3 数据集划分
3.特征工程(字典特征抽取)
4.机器学习(决策树)
5.模型评估

导入需要的模块
import pandas as pd
import numpy as np
from sklearn.feature_extraction import DictVectorizer
from sklearn.model_selection import train_test_split
from sklearn.tree import DecisionTreeClassifier, export_graphviz

导入数据
# 1、获取数据
titan = pd.read_csv("http://biostat.mc.vanderbilt.edu/wiki/pub/Main/DataSets/titanic.txt")
titan.head()

titan.describe()
数据处理
#2.1 确定特征值,目标值
x=titan[['pclass','age','sex']]
y=titan['survived']
#2.2 缺失值处理
x=x.fillna(x.mean())
x.info()
#2.3 数据集划分
x_train, x_test, y_train, y_test = train_test_split(x, y, random_state=22)

字典特征提取
#实例化对象
dictvector=DictVectorizer()
#转换
#特征中出现类别符号，需要进行one-hot编码处理(DictVectorizer)，x.to_dict(orient="records") 需要将数组特征转换成字典数据
# new_x=dictvector.fit_transform(x_train)# 报错 'str' object has no attribute 'items'
new_x_train=dictvector.fit_transform(x_train.to_dict(orient="records"))
new_x_test=dictvector.transform(x_test.to_dict(orient="records"))
#输出特征名
dictvector.get_feature_names()

模型训练
#实例化决策树
tree=DecisionTreeClassifier(max_depth=3)
#训练
tree.fit(new_x_train,y_train)

模型的评估
print("训练集准确率:",tree.score(new_x_train,y_train))
print("测试集准确率:",tree.score(new_x_test,y_test))

树的可视化
export_graphviz(tree, out_file="data/tree.dot", feature_names=['age', 'pclass=1st', 'pclass=2nd', 'pclass=3rd', '女性', '男性'])

决策树可视化-------保存树的结构到dot文件
sklearn.tree.export_graphviz() 该函数能够导出DOT格式
tree.export_graphviz(estimator,out_file='tree.dot’,feature_names=[‘’,’’])
决策树总结

• 优点：可解释性强、 模型能力强
• 缺点： 容易过拟合、 不适用于复杂数据集(特征太多)
• 改进： 减枝、模型融合–集成学习

总结

• 两个不纯度指标
  • 熵:对数运算
  • gini系数: 乘法运算
  • 二者区别:
    • 计算方式不同
    • 作用和意义都一样
      • 不纯度衡量指标 不纯度越高,值越大
• 特征重要性
  • 信息增益:entropy(前)-entropy(后) id3
    • 缺点:偏向取值种类较多的特征
  • 信息增益率: 信息增益/特征分割熵 c4.5
    • 分叉越多,特征分割熵 就愈大,解决了问题
  • gini信息增益 cart
    • gini替换熵
    • 强制二叉树:解决信息增益存在的问题