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

熵

物理学上，熵 Entropy 是“混乱”程度的量度。

系统越有序，熵值越低；系统越混乱或者分散，熵值越高。

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

1948年香农提出了信息熵（Entropy）的概念。
假如事件A的分类划分是（A1,A2,…,An），每部分发生的概率是(p1,p2,…,pn)，那信息熵定义为公式如下：（log是以2为底，lg是以10为底）

决策树的划分依据一------信息增益

信息增益：以某特征划分数据集前后的熵的差值。熵可以表示样本集合的不确定性，熵越大，样本的不确定性就越大。因此可以使用划分前后集合熵的差值来衡量使用当前特征对于样本集合D划分效果的好坏。
信息增益 = entroy(前) - entroy(后)

定义与公式

特征A对训练数据集D的信息增益g(D,A),定义为集合D的信息熵H(D)与特征A给定条件下D的信息条件熵H(D|A)之差，即公式为：

公式的详细解释：

注：信息增益表示得知特征X的信息而使得类Y的信息熵减少的程度

案例

如下左图，第一列为论坛号码，第二列为性别，第三列为活跃度，最后一列用户是否流失。
解决一个问题：性别和活跃度两个特征，哪个对用户流失影响更大？

通过计算信息增益可以解决这个问题，统计上右表信息
其中Positive为正样本（已流失），Negative为负样本（未流失），下面的数值为不同划分下对应的人数。
可得到三个熵：
整体熵：

性别熵：

性别信息增益：

活跃度熵：

活跃度信息增益：

活跃度的信息增益比性别的信息增益大，也就是说，活跃度对用户流失的影响比性别大。

决策树的划分依据二----信息增益率

增益率：增益比率度量是用前面的增益度量Gain(S，A)和所分离信息度量SplitInformation(如上例的性别，活跃度等)的比值来共同定义的。

详细解释

决策树的划分依据三——基尼值和基尼指数

基尼值Gini（D）：从数据集D中随机抽取两个样本，其类别标记不一致的概率。故，Gini（D）值越小，数据集D的纯度越高。

基尼指数Gini_index（D）：一般，选择使划分后基尼系数最小的属性作为最优化分属性。

案例

请根据下图列表，按照基尼指数的划分依据，做出决策树。

• 对数据集非类标号属性{是否有房，婚姻状况，年收入}分别计算它们的Gini系数增益，取Gini系数增益值最大的属性作为决策树的根节点属性。
  
• 根节点的Gini系数为：
  
• 当根据是否有房来进行划分时，Gini系数增益计算过程为：
  
  若按婚姻状况属性来划分，属性婚姻状况有三个可能的取值{married，single，divorced}，分别计算划分后的Gini系数增益。
  ​ {married} | {single,divorced}
  ​ {single} | {married,divorced}
  ​ {divorced} | {single,married}
  分组为{married} | {single,divorced}时：
  
  当分组为{single} | {married,divorced}时：
  
  当分组为{divorced} | {single,married}时：
  
  对比计算结果，根据婚姻状况属性来划分根节点时取Gini系数增益最大的分组作为划分结果，即:{married} | {single,divorced}

同理可得年收入Gini：
对于年收入属性为数值型属性，首先需要对数据按升序排序，然后从小到大依次用相邻值的中间值作为分隔将样本划分为两组。例如当面对年收入为60和70这两个值时，我们算得其中间值为65。以中间值65作为分割点求出Gini系数增益。



最大化增益等价于最小化子女结点的不纯性度量（Gini系数）的加权平均值，现在我们希望最大化Gini系数的增益。根据计算知道，三个属性划分根节点的增益最大的有两个：年收入属性和婚姻状况，他们的增益都为0.12。此时，选取首先出现的属性作为第一次划分。

接下来，采用同样的方法，分别计算剩下属性，其中根节点的Gini系数为（此时是否拖欠贷款的各有3个records）

对于是否有房属性，可得：

对于年收入属性则有：


决策树的变量可以有两种：

• 数字型（Numeric）：变量类型是整数或浮点数，如前面例子中的“年收入”。用“>=”，“>”,“<”或“<=”作为分割条件（排序后，利用已有的分割情况，可以优化分割算法的时间复杂度）。
• 名称型（Nominal）：类似编程语言中的枚举类型，变量只能从有限的选项中选取，比如前面例子中的“婚姻情况”，只能是“单身”，“已婚”或“离婚”，使用“=”来分割。

​ 如果一个分割点可以将当前的所有节点分为两类，使得每一类都很“纯”，也就是同一类的记录较多，那么就是一个好分割点。
​ 比如上面的例子，“拥有房产”，可以将记录分成了两类，“是”的节点全部都可以偿还债务，非常“纯”；“否”的节点，可以偿还贷款和无法偿还贷款的人都有，不是很“纯”，但是两个节点加起来的纯度之和与原始节点的纯度之差最大，所以按照这种方法分割。构建决策树采用贪心算法，只考虑当前纯度差最大的情况作为分割点。

D3 算法

存在的缺点
​ (1) ID3算法在选择根节点和各内部节点中的分支属性时，采用信息增益作为评价标准。信息增益的缺点是倾向于选择取值较多的属性，在有些情况下这类属性可能不会提供太多有价值的信息.
​ (2) ID3算法只能对描述属性为离散型属性的数据集构造决策树。

C4.5算法

​ (1) 用信息增益率来选择属性
​ (2) 可以处理连续数值型属性
​ (3)采用了一种后剪枝方法
​ (4)对于缺失值的处理
C4.5算法的优缺点

• 优点：
  • 产生的分类规则易于理解，准确率较高。
• 缺点：​
  • 在构造树的过程中，需要对数据集进行多次的顺序扫描和排序，因而导致算法的低效。

​ 此外，C4.5只适合于能够驻留于内存的数据集，当训练集大得无法在内存容纳时程序无法运行。

CART算法

CART算法相比C4.5算法的分类方法，采用了简化的二叉树模型，同时特征选择采用了近似的基尼系数来简化计算。
C4.5不一定是二叉树，但CART一定是二叉树。
同时，无论是ID3, C4.5还是CART,在做特征选择的时候都是选择最优的一个特征来做分类决策，但是大多数，分类决策不应该是由某一个特征决定的，而是应该由一组特征决定的。这样决策得到的决策树更加准确。这个决策树叫做多变量决策树(multi-variate decision tree)。在选择最优特征的时候，多变量决策树不是选择某一个最优特征，而是选择最优的一个特征线性组合来做决策。这个算法的代表是OC1

如果样本发生一点点的改动，就会导致树结构的剧烈改变。这个可以通过集成学习里面的随机森林之类的方法解决。

cart剪枝

• 横轴表示在决策树创建过程中树的结点总数，纵轴表示决策树的预测精度。
• 实线显示的是决策树在训练集上的精度，虚线显示的则是在一个独立的测试集上测量出来的精度。
• 随着树的增长，在训练样集上的精度是单调上升的， 然而在独立的测试样例上测出的精度先上升后下降。决策树复杂度较大，容易产生过拟合，因此需要剪枝

出现这种情况的原因：

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

常用的减枝方法

预剪枝

• 每一个结点所包含的最小样本数目，例如10，则该结点总样本数小于10时，则不再分；
• 指定树的高度或者深度，例如树的最大深度为4；
• 指定结点的熵小于某个值，不再划分。随着树的增长， 在训练样集上的精度是单调上升的， 然而在独立的测试样例上测出的精度先上升后下降。

后剪枝：

• 后剪枝，在已生成过拟合决策树上进行剪枝，可以得到简化版的剪枝决策树。

特征工程-特征提取

特征提取

将任意数据（如文本或图像）转换为可用于机器学习的数字特征
注：特征值化是为了计算机更好的去理解数据

特征提取分类:

• 字典特征提取(特征离散化)
• 文本特征提取
• 图像特征提取

特征提取API

sklearn.feature_extraction

字典特征提取

作用：对字典数据进行特征值化
sklearn.feature_extraction.DictVectorizer(sparse=True,…)

• DictVectorizer.fit_transform(X)
  • X:字典或者包含字典的迭代器返回值
  • 返回sparse矩阵
• DictVectorizer.get_feature_names() 返回类别名称

[{'city': '北京','temperature':100},
{'city': '上海','temperature':60},
{'city': '深圳','temperature':30}]

from sklearn.feature_extraction import DictVectorizerdata = [{'city':'北京','temperature':100},{'city':'上海','temperature':60},{'city':'深圳','temperature':30}
]# 实例化转换器  DictVectorizer(sparse = 是否转换为稀疏矩阵)
transform = DictVectorizer(sparse=False)
# 转化数据即提取特征
res = transform.fit_transform(data)
res # 自动将离散特征作one-hot编码,转换为哑变量矩阵

# 获取每列对应字段名
transform.get_feature_names()

# 稀疏矩阵 - 若0元素个数少于非0元素个数,且分布无规律则为稀疏矩阵
transfer = DictVectorizer(sparse=True)
res = transfer.fit_transform(data)
res

print(res)  # (x,y) value ,对应哑变量矩阵中每个非零元素的值和索引

# 稀疏矩阵转ndarry
res.toarray()

one-hot 编码

pandas 实现one-hot编码方式

pandas.get_dummies(data, prefix=None)

转化为：

对于特征当中存在类别信息的我们都会做one-hot编码处理

文本特征提取

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

• sklearn.feature_extraction.text.CountVectorizer(stop_words=[])
  返回词频矩阵
  • CountVectorizer.fit_transform(X)
    • X:文本或者包含文本字符串的可迭代对象
    • 返回值:返回sparse矩阵
  • CountVectorizer.get_feature_names() 返回值:单词列表
• sklearn.feature_extraction.text.TfidfVectorizer

from sklearn.feature_extraction.text import CountVectorizer  
data = ['life is to short,i like python','life is too long, i dislike python']
# 实例化转换器
transform = CountVectorizer()
# 进行提取
res = transform.fit_transform(data)  # 返回一个稀疏矩阵
res.toarray()  # 将稀疏矩阵转换为ndarry
# 结果为每个字段在第n个(行代表一个字符串)字符串中出现的次数

# 获取列名
transform.get_feature_names()

# 若采用中文
# CountVectorizer只支持英文,使用中文需要事先将每个词用blank分割
# 即data = ['人生 苦短,我 用 python','人生 太长,不用 python']
data = ['人生苦短,我用python','人生太长,不用python']transform = CountVectorizer()
res = transform.fit_transform(data)
res.toarray()

transform.get_feature_names()  

jieba分词处理

pip install jieba

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

import jieba
# 中文分词
res = list(jieba.cut('人生苦短,我用python')) # jieba 返回为一个迭代器,采用list 转换
res

# 采用特征提取,每个字符串需要以空格进行连接
' '.join(res)

def cut_words(s):return ' '.join(list(jieba.cut(s)))
cut_words('人生苦短,我用python')

# 将data进行中文分词
data = ['人生苦短,我用python','人生太长,不用python']
temp = list()
for i in data:temp.append(cut_words(i))
temp

# 进行文本特征提取
transform = CountVectorizer()
res = transform.fit_transform(temp)
print(res)

# 转换为ndarry
res.toarray()

# 获取字段名
transform.get_feature_names()

from sklearn.feature_extraction.text import CountVectorizer
import jiebadef cut_word(text):"""对中文进行分词"我爱北京天安门"————>"我 爱 北京 天安门":param text::return: text"""# 用结巴对中文字符串进行分词text = " ".join(list(jieba.cut(text)))return textdef text_chinese_count_demo2():"""对中文进行特征抽取:return: None"""data = ["一种还是一种今天很残酷，明天更残酷，后天很美好，但绝对大部分是死在明天晚上，所以每个人不要放弃今天。","我们看到的从很远星系来的光是在几百万年之前发出的，这样当我们看到宇宙时，我们是在看它的过去。","如果只用一种方式了解某样事物，你就不会真正了解它。了解事物真正含义的秘密取决于如何将其与我们所了解的事物相联系。"]# 将原始数据转换成分好词的形式text_list = []for sent in data:text_list.append(cut_word(sent))print(text_list)# 1、实例化一个转换器类# transfer = CountVectorizer(sparse=False)transfer = CountVectorizer()# 2、调用fit_transformdata = transfer.fit_transform(text_list)print("文本特征抽取的结果：\n", data.toarray())print("返回特征名字：\n", transfer.get_feature_names())return None

Building prefix dict from the default dictionary ...
Dumping model to file cache /var/folders/mz/tzf2l3sx4rgg6qpglfb035_r0000gn/T/jieba.cache
Loading model cost 1.032 seconds.
['一种 还是 一种 今天 很 残酷 ， 明天 更 残酷 ， 后天 很 美好 ， 但 绝对 大部分 是 死 在 明天 晚上 ， 所以 每个 人 不要 放弃 今天 。', '我们 看到 的 从 很 远 星系 来 的 光是在 几百万年 之前 发出 的 ， 这样 当 我们 看到 宇宙 时 ， 我们 是 在 看 它 的 过去 。', '如果 只用 一种 方式 了解 某样 事物 ， 你 就 不会 真正 了解 它 。 了解 事物 真正 含义 的 秘密 取决于 如何 将 其 与 我们 所 了解 的 事物 相 联系 。']
Prefix dict has been built succesfully.
文本特征抽取的结果：[[2 0 1 0 0 0 2 0 0 0 0 0 1 0 1 0 0 0 0 1 1 0 2 0 1 0 2 1 0 0 0 1 1 0 0 1 0][0 0 0 1 0 0 0 1 1 1 0 0 0 0 0 0 0 1 3 0 0 0 0 1 0 0 0 0 2 0 0 0 0 0 1 0 1][1 1 0 0 4 3 0 0 0 0 1 1 0 1 0 1 1 0 1 0 0 1 0 0 0 1 0 0 0 2 1 0 0 1 0 0 0]]
返回特征名字：['一种', '不会', '不要', '之前', '了解', '事物', '今天', '光是在', '几百万年', '发出', '取决于', '只用', '后天', '含义', '大部分', '如何', '如果', '宇宙', '我们', '所以', '放弃', '方式', '明天', '星系', '晚上', '某样', '残酷', '每个', '看到', '真正', '秘密', '绝对', '美好', '联系', '过去', '还是', '这样']

Tf-idf文本特征提取

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

公式

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

举例：
假如一篇文章的总词语数是100个，而词语"非常"出现了5次，那么"非常"一词在该文件中的词频就是5/100=0.05。
而计算文件频率（IDF）的方法是以文件集的文件总数，除以出现"非常"一词的文件数。
所以，如果"非常"一词在1,0000份文件出现过，而文件总数是10,000,000份的话，
其逆向文件频率就是lg（10,000,000 / 1,0000）=3。
最后"非常"对于这篇文档的tf-idf的分数为0.05 * 3=0.15

from sklearn.feature_extraction.text import TfidfVectorizer
data = ['人生苦短,我用python','人生太长,不用python']def cut_words(s):return ' '.join(list(jieba.cut(s)))temp = list()
for i in data:temp.append(cut_words(i))# 实例化转换器
transform = TfidfVectorizer()
# 特征提取
res = transform.fit_transform(temp)# 稀疏矩阵转为ndarry
res.toarray() # TF*IDF

# 获取字段信息
transform.get_feature_names()

from sklearn.feature_extraction.text import TfidfVectorizer
import jiebadef cut_word(text):"""对中文进行分词"我爱北京天安门"————>"我 爱 北京 天安门":param text::return: text"""# 用结巴对中文字符串进行分词text = " ".join(list(jieba.cut(text)))return textdef text_chinese_tfidf_demo():"""对中文进行特征抽取:return: None"""data = ["一种还是一种今天很残酷，明天更残酷，后天很美好，但绝对大部分是死在明天晚上，所以每个人不要放弃今天。","我们看到的从很远星系来的光是在几百万年之前发出的，这样当我们看到宇宙时，我们是在看它的过去。","如果只用一种方式了解某样事物，你就不会真正了解它。了解事物真正含义的秘密取决于如何将其与我们所了解的事物相联系。"]# 将原始数据转换成分好词的形式text_list = []for sent in data:text_list.append(cut_word(sent))print(text_list)# 1、实例化一个转换器类# transfer = CountVectorizer(sparse=False)transfer = TfidfVectorizer(stop_words=['一种', '不会', '不要'])# 2、调用fit_transformdata = transfer.fit_transform(text_list)print("文本特征抽取的结果：\n", data.toarray())print("返回特征名字：\n", transfer.get_feature_names())return None

Building prefix dict from the default dictionary ...
Loading model from cache /var/folders/mz/tzf2l3sx4rgg6qpglfb035_r0000gn/T/jieba.cache
Loading model cost 0.856 seconds.
Prefix dict has been built succesfully.
['一种 还是 一种 今天 很 残酷 ， 明天 更 残酷 ， 后天 很 美好 ， 但 绝对 大部分 是 死 在 明天 晚上 ， 所以 每个 人 不要 放弃 今天 。', '我们 看到 的 从 很 远 星系 来 的 光是在 几百万年 之前 发出 的 ， 这样 当 我们 看到 宇宙 时 ， 我们 是 在 看 它 的 过去 。', '如果 只用 一种 方式 了解 某样 事物 ， 你 就 不会 真正 了解 它 。 了解 事物 真正 含义 的 秘密 取决于 如何 将 其 与 我们 所 了解 的 事物 相 联系 。']
文本特征抽取的结果：[[ 0.          0.          0.          0.43643578  0.          0.          0.0.          0.          0.21821789  0.          0.21821789  0.          0.0.          0.          0.21821789  0.21821789  0.          0.436435780.          0.21821789  0.          0.43643578  0.21821789  0.          0.0.          0.21821789  0.21821789  0.          0.          0.218217890.        ][ 0.2410822   0.          0.          0.          0.2410822   0.24108220.2410822   0.          0.          0.          0.          0.          0.0.          0.2410822   0.55004769  0.          0.          0.          0.0.2410822   0.          0.          0.          0.          0.482164410.          0.          0.          0.          0.          0.24108220.          0.2410822 ][ 0.          0.644003    0.48300225  0.          0.          0.          0.0.16100075  0.16100075  0.          0.16100075  0.          0.161000750.16100075  0.          0.12244522  0.          0.          0.161000750.          0.          0.          0.16100075  0.          0.          0.0.3220015   0.16100075  0.          0.          0.16100075  0.          0.0.        ]]
返回特征名字：['之前', '了解', '事物', '今天', '光是在', '几百万年', '发出', '取决于', '只用', '后天', '含义', '大部分', '如何', '如果', '宇宙', '我们', '所以', '放弃', '方式', '明天', '星系', '晚上', '某样', '残酷', '每个', '看到', '真正', '秘密', '绝对', '美好', '联系', '过去', '还是', '这样']

决策树算法api

class sklearn.tree.DecisionTreeClassifier(criterion=’gini’, max_depth=None,random_state=None)

• criterion
  • 特征选择标准
  • “gini"或者"entropy”，前者代表基尼系数，后者代表信息增益。一默认"gini"，即CART算法。
• min_samples_split
  • 内部节点再划分所需最小样本数
  • 这个值限制了子树继续划分的条件，如果某节点的样本数少于min_samples_split，则不会继续再尝试选择最优特征来进行划分。 默认是2.如果样本量不大，不需要管这个值。如果样本量数量级非常大，则推荐增大这个值。例如，10万样本，建立决策树时，选择 min_samples_split=10，可以作为参考。
• min_samples_leaf
  • 叶子节点最少样本数
  • 这个值限制了叶子节点最少的样本数，如果某叶子节点数目小于样本数，则会和兄弟节点一起被剪枝。 默认是1,可以输入最少的样本数的整数，或者最少样本数占样本总数的百分比。如果样本量不大，不需要管这个值。如果样本量数量级非常大，则推荐增大这个值。10万样本使用min_samples_leaf的值为5，供参考。
• max_depth
  • 决策树最大深度
  • 决策树的最大深度，默认可以不输入，如果不输入的话，决策树在建立子树的时候不会限制子树的深度。一般来说，数据少或者特征少的时候可以不管这个值。如果模型样本量多，特征也多的情况下，推荐限制这个最大深度，具体的取值取决于数据的分布。常用的可以取值10-100之间
• random_state
  • 随机数种子

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

• 数据集
  在泰坦尼克号和titanic2数据帧描述泰坦尼克号上的个别乘客的生存状态。这里使用的数据集是由各种研究人员开始的。其中包括许多研究人员创建的旅客名单，由Michael A. Findlay编辑。我们提取的数据集中的特征是票的类别，存活，乘坐班，年龄，登陆，home.dest，房间，票，船和性别。
  数据集
  • 乘坐班是指乘客班（1，2，3），是社会经济阶层的代表。
  • 其中age数据存在缺失。

import pandas as pd 
from sklearn.model_selection import train_test_split
from sklearn.feature_extraction import DictVectorizer
from sklearn.tree import DecisionTreeClassifier
from sklearn.metrics import classification_report,roc_auc_scoredata = pd.read_csv('http://biostat.mc.vanderbilt.edu/wiki/pub/Main/DataSets/titanic.txt')
data.head()

# 2.数据基本处理-异常,缺失,数据集划分
# 获取特征和目标值
x = data[['pclass','age','sex']] # 取该3列作为特征值
y = data['survived'] # 目标值
# 处理缺失值 -age列,用平均值代替 inplace=是否生成新列替换原来列,True即原地修改
x['age'].fillna(x['age'].mean(),inplace = True)
# 划分数据集
x_train,x_test,y_train,y_test = train_test_split(x,y,test_size=0.2,random_state=10)

# 3.特征工程
# one-hot编码,采用字典特征提取
# 实例化转换器
trans_dict = DictVectorizer(sparse=False)# DictVectorizer 转换的变量类型为dict,x_train类型为ndarry,orient指定字典的类型,records为{'列':'值'}
x_train = trans_dict.fit_transform(x_train.to_dict(orient='records')) 
x_test = trans_dict.transform(x_test.to_dict(orient='records'))

# 4.决策树
# 构建模型
# 实例化估计器
estimator = DecisionTreeClassifier(criterion='gini',max_depth=5)
# 训练模型
estimator.fit(x_train,y_train)

# 5.模型评估
print('准确率为:\n',estimator.score(x_test,y_test))
# 5.模型评估
print('准确率为:\n',estimator.score(x_test,y_test))
# 准确率为:
# 0.8288973384030418

决策树可视化

保存树的结构到dot文件

• sklearn.tree.export_graphviz() 该函数能够导出DOT格式
  • tree.export_graphviz(estimator,out_file='tree.dot’,feature_names=[‘’,’’])

from sklearn.tree import export_graphviz
# 获取特征值名字
trans_dict.get_feature_names()

export_graphviz(estimator,out_file='./tree.dot',feature_names=trans_dict.get_feature_names())

dot文件当中的内容如下

digraph Tree {
node [shape=box] ;
0 [label="petal length (cm) <= 2.45\nentropy = 1.584\nsamples = 112\nvalue = [39, 37, 36]"] ;
1 [label="entropy = 0.0\nsamples = 39\nvalue = [39, 0, 0]"] ;
0 -> 1 [labeldistance=2.5, labelangle=45, headlabel="True"] ;
2 [label="petal width (cm) <= 1.75\nentropy = 1.0\nsamples = 73\nvalue = [0, 37, 36]"] ;
0 -> 2 [labeldistance=2.5, labelangle=-45, headlabel="False"] ;
3 [label="petal length (cm) <= 5.05\nentropy = 0.391\nsamples = 39\nvalue = [0, 36, 3]"] ;
2 -> 3 ;
4 [label="sepal length (cm) <= 4.95\nentropy = 0.183\nsamples = 36\nvalue = [0, 35, 1]"] ;
3 -> 4 ;
5 [label="petal length (cm) <= 3.9\nentropy = 1.0\nsamples = 2\nvalue = [0, 1, 1]"] ;
4 -> 5 ;
6 [label="entropy = 0.0\nsamples = 1\nvalue = [0, 1, 0]"] ;
5 -> 6 ;
7 [label="entropy = 0.0\nsamples = 1\nvalue = [0, 0, 1]"] ;
5 -> 7 ;
8 [label="entropy = 0.0\nsamples = 34\nvalue = [0, 34, 0]"] ;
4 -> 8 ;
9 [label="petal width (cm) <= 1.55\nentropy = 0.918\nsamples = 3\nvalue = [0, 1, 2]"] ;
3 -> 9 ;
10 [label="entropy = 0.0\nsamples = 2\nvalue = [0, 0, 2]"] ;
9 -> 10 ;
11 [label="entropy = 0.0\nsamples = 1\nvalue = [0, 1, 0]"] ;
9 -> 11 ;
12 [label="petal length (cm) <= 4.85\nentropy = 0.191\nsamples = 34\nvalue = [0, 1, 33]"] ;
2 -> 12 ;
13 [label="entropy = 0.0\nsamples = 1\nvalue = [0, 1, 0]"] ;
12 -> 13 ;
14 [label="entropy = 0.0\nsamples = 33\nvalue = [0, 0, 33]"] ;
12 -> 14 ;
}

决策树.dot在线显示
决策树优点：
* 简单的理解和解释，树木可视化。

决策树缺点：
* 决策树学习者可以创建不能很好地推广数据的过于复杂的树,容易发生过拟合。

改进：

• 减枝cart算法
• 随机森林（集成学习的一种）

集成学习

集成学习通过建立几个模型来解决单一预测问题。它的工作原理是生成多个分类器/模型，各自独立地学习和作出预测。这些预测最后结合成组合预测，因此优于任何一个单分类的做出预测。

集成学习中boosting和Bagging

只要单分类器的表现不太差，集成学习的结果总是要好于单分类器的

Bagging集成原理

目标：把下面的圈和方块进行分类

实现过程：
采样不同数据集

训练分类器

平权投票，获取最终结果

主要实现过程

随机森林构造过程

在机器学习中，随机森林是一个包含多个决策树的分类器，并且其输出的类别是由个别树输出的类别的众数而定。
随机森林 = Bagging + 决策树

随机森林够造过程中的关键步骤（用N来表示训练用例（样本）的个数，M表示特征数目）：

• 一次随机选出一个样本，有放回的抽样，重复N次（有可能出现重复的样本）
• ​随机去选出m个特征, m <<M，建立决策树

随机森林api介绍

• sklearn.ensemble.RandomForestClassifier(n_estimators=10, criterion=’gini’, max_depth=None, bootstrap=True, random_state=None, min_samples_split=2)
  • n_estimators：integer，optional（default = 10）森林里的树木数量120,200,300,500,800,1200
  • Criterion：string，可选（default =“gini”）分割特征的测量方法
  • max_depth：integer或None，可选（默认=无）树的最大深度 5,8,15,25,30
  • max_features="auto”,每个决策树的最大特征数量
    • If “auto”, then max_features=sqrt(n_features).
    • If “sqrt”, then max_features=sqrt(n_features)(same as “auto”).
    • If “log2”, then max_features=log2(n_features).
    • If None, then max_features=n_features.
  • bootstrap：boolean，optional（default = True）是否在构建树时使用放回抽样
  • min_samples_split:节点划分最少样本数
  • min_samples_leaf:叶子节点的最小样本数
• 超参数：n_estimator, max_depth, min_samples_split,min_samples_leaf

案例：随机森林实现泰坦尼克号生存预测

import pandas as pd 
from sklearn.model_selection import train_test_split
from sklearn.feature_extraction import DictVectorizer
from sklearn.ensemble import RandomForestClassifier
from sklearn.metrics import roc_auc_score
from sklearn.metrics import classification_report
from sklearn.model_selection import GridSearchCV# 1.获取数据
data = pd.read_csv('http://biostat.mc.vanderbilt.edu/wiki/pub/Main/DataSets/titanic.txt')
data.head()

# 2.数据处理-缺失值,数据集划分
# 获取特征值 
x = data[['pclass','age','sex']]
# 获取目标值
y = data['survived']
# 缺失值处理
x['age'].fillna(x['age'].mean(),inplace = True)
# 数据集划分
x_train,x_test,y_train,y_test = train_test_split(x,y,test_size=0.2,random_state=10)# 3.特征工程-特征字典
trans_dict = DictVectorizer(sparse=False)
x_train = trans_dict.fit_transform(x_train.to_dict(orient = 'records'))
x_test = trans_dict.fit_transform(x_test.to_dict(orient = 'records'))# 4.机器学习-随机森林
# 建立模型
estimator = RandomForestClassifier(n_estimators=100,criterion='gini',max_depth=5)
# 训练模型
estimator.fit(x_train,y_train)# 5.评估模型 - 准确率率
score = estimator.score(x_test,y_test)
print('准确率为',score)
# 精确率,召回率,f1-score
y_predict = estimator.predict(x_test)
res = classification_report(y_pred=y_predict,y_true=y_test)
print(res)
# AUC
roc_auc_score(y_true=y_test,y_score=y_predict)

网格搜索确定最优超参数

# 构建参数字典
params = {'n_estimators':[100,200,300],'max_depth':[5,8,10,15]
}
# 实例化随机森林估计器
estimator = RandomForestClassifier()
# 网格搜索
gc = GridSearchCV(estimator,param_grid=params,cv=2)
# 训练模型
gc.fit(x_train,y_train)

# 获得最优超参数
gc.best_params_

# 获得最优模型
gc.best_estimator_

bagging集成优点
​Bagging + 决策树/线性回归/逻辑回归/深度学习… = bagging集成学习方法
经过上面方式组成的集成学习方法:

• 均可在原有算法上提高约2%左右的泛化正确率
• 简单, 方便, 通用

Boosting集成原理

随着学习的积累从弱到强
简而言之：每新加入一个弱学习器，整体能力就会得到提升
代表算法：Adaboost，GBDT，XGBoost
串行建立N个模型，后建立的模型受之前建立模型的影响
实现过程：
训练第一个学习器

调整数据分布

训练第二个学习器

再次调整数据分布

依次训练学习器，调整数据分布

整体过程实现

关键点：
如何确认投票权重？
如何调整数据分布？

AdaBoost的构造过程小结

bagging集成与boosting集成的区别：

• 区别一:数据方面
  Bagging：对数据进行采样训练；
  Boosting：根据前一轮学习结果调整数据的重要性。
• 区别二:投票方面
  Bagging：所有学习器平权投票；
  Boosting：对学习器进行加权投票。
• 区别三:学习顺序
  Bagging的学习是并行的，每个学习器没有依赖关系；
  Boosting学习是串行，学习有先后顺序。
• 区别四:主要作用
  Bagging主要用于提高泛化性能（解决过拟合，也可以说降低方差）
  Boosting主要用于提高训练精度 （解决欠拟合，也可以说降低偏差）

API

from sklearn.ensemble import AdaBoostClassifier

GBDT

梯度提升决策树(GBDT Gradient Boosting Decision Tree) 是一种迭代的决策树算法，该算法由多棵决策树组成，所有树的结论累加起来做最终答案。它在被提出之初就被认为是泛化能力（generalization)较强的算法。
GBDT = 梯度下降 + Boosting + 决策树



GBDT执行流程

如果上式中的hi(x)=决策树模型,则上式就变为:
GBDT = 梯度下降 + Boosting + 决策树

案例
预测编号5的身高:

第一步:计算损失函数,并求出第一个预测值:

第二步:求解划分点

得出:年龄21为划分点的方差=0.01+0.0025=0.0125
第三步:通过调整后目标值,求解得出h₁(x)

第四步:求解h₂(x)

得出结果:

编号5身高 = 1.475 + 0.03 + 0.275 = 1.78
GBDT主要执行思想

• 使用梯度下降法优化代价函数；
• 使用一层决策树作为弱学习器，负梯度作为目标值；
• 利用boosting思想进行集成。

XGBoost

XGBoost= 二阶泰勒展开+boosting+决策树+正则化

• Boosting：XGBoost使用Boosting提升思想对多个弱学习器进行迭代式学习
• 二阶泰勒展开：每一轮学习中，XGBoost对损失函数进行二阶泰勒展开，使用一阶和二阶梯度进行优化。
• 决策树：在每一轮学习中，XGBoost使用决策树算法作为弱学习进行优化。
• 正则化：在优化过程中XGBoost为防止过拟合，在损失函数中加入惩罚项，限制决策树的叶子节点个数以及决策树叶子节点的值。

泰勒展开越多，计算结果越精确