决策树算法

决策树思想的来源非常朴素，程序设计中的条件分支结构就是if-else结构，最早的决策树就是利用这类结构分割数据的一种分类学习方法

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

简介

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

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

熵 Entropy 

1948年香农提出了 信息熵（Entropy）的概念，  是度量样本集合纯度最常用的一种指标。

Ent(D) 的值越小，则 D 的纯度越高

信息熵、交叉熵、相对熵

信息熵

以某特征划分数据集前后的熵的差值。熵可以表示样本集合的不确定性，熵越大，样本的不确定性就越大。因此可以使用划分前后集合熵的差值来衡量使用当前特征对于样本集合D划分效果的好坏，  信息增益越大，则意味着使用属性 $a$ 来进行划分所获得的\"纯度提升\"越大



1. 计算整体信息熵

每一个分支权重 这个分支信息熵的和

2. 计算按照某个属性划分后的信息熵

3. 整体信息熵 - 按照某个属性划分后的信息熵

4. 选择信息增益大的属性进行划分

计算过程

信息增益（ID3）

信息增益准则对可取值数目较多的属性（类型多）有所偏好（信息增益倾向于选择类别多属性进行划分），为减少这种偏好可能带来的不利影响，著名的 C4.5 决策树算法 [Quinlan， 1993J 不直接使用信息增益，而是使用\"增益率\" (gain ratio) 来选择最优划分属性

用分裂信息度量来考虑某种属性进行分裂时分支的数量信息和尺寸信息，我们把这些信息称为属性的内在信息（instrisic information）。信息增益率用信息增益/内在信息，会导致属性的重要性随着内在信息的增大而减小（也就是说，如果这个属性本身不确定性就很大，那我就越不倾向于选取它），这样算是对单纯用信息增益有所补偿。

span style=\"font-size: inherit;\

1. 计算分类[整体]信息熵

2. 计算每一个属性划分后信息熵

3. 计算每一个属性信息增益

4. 计算每一个属性分裂信息度量（固有值）

5. 计算信息增益率

6. 选择信息增益率最大属性进行划分

信息增益率算法流程:

 C4.5 画出的决策树

处理缺少属性值的一种策略是赋给它结点n所对应的训练实例中该属性的最常见值另外一种更复杂的策略是为A的每个可能值赋予一个概率。例如，给定一个布尔属性A，如果结点n包含6个已知A=1和4个A=0的实例，那么A(x)=1的概率是0.6，而A(x)=0的概率是0.4。于是，实例x的60%被分配到A=1的分支，40%被分配到另一个分支。C4.5就是使用这种方法处理缺少的属性值。

3. 对缺失值进行了处理.

C4.5算法的优点

信息增益率（C4.5）

基尼值Gini（D）：从数据集D中随机抽取两个样本，其类别标记不一致的概率。故，Gini（D）值越小，数据集D的纯度越高。计算公式: 1 - 每一个类别概率平方的和

基尼指数Gini_index（D）：一般，选择使划分后基尼系数最小的属性作为最优化分属性font color=\"#e74f4c\

2. 选择基尼系数最小的分割方式进行划分（选取基尼系数最小的值进行分类）

4. 直到所有节点都足够纯了

CART决策树算法流程

Gini系数 （CART）

决策树分类原理

随着树节点的增长，在训练样集上的精度是单调上升的， 然而在独立的测试样例上测出的精度先上升后下降出现这种情况的原因：噪声、样本冲突，即错误的样本数据。特征即属性不能完全作为分类标准。巧合的规律性，数据量不够大。

在决策树学习中，为了尽可能正确分类训练样本，结点划分过程将不断重复，有时会造成决策树分支过多，这时就可能因训练样本学得\"太好\"了，以致于把训练集自身的一些特点当作所有数据都具有的一般性质而导致过拟合。因此，可通过主动去掉一些分支来降低过拟合的风险

剪枝 (pruning)是 决策树学习算法对付\"过拟合\"的主要手段

为什么要减枝 ？ 

树的高度或深度; 一旦达到这个深度了就不在分了

预剪枝: 在生成决策树过程中剪枝

- c4.5 决策树算法就是采用后剪枝.

常用剪枝方法

CART剪枝

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

字典特征提取（特征离散化）

文本特征提取

图像特征提取（深度学习）

特征提取分类

对类别属性进行one-hot编码

sparse矩阵/稀疏矩阵的优点：节省内容提高读取效率

参数:

参数: 需要处理的数据

fit_transform(x)

获取特征名称

get_feature_names() :

方法:

sklearn.feature_extraction.DictVectorizer(sparse=True)

API

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

one-hot编码 

字典特征提取

对文本数据进行特征值化(统计每个单词出现次数) 【单字符不统计】

作用: 统计每个单词出现次数

font color=\"#ed9745\

get_feature_names() : 获取单词列表

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

pip3 install jieba

安装

参数: 需要分割中文文本字符串

返回值: 分词后的生成器

方法: cut(text)

使用:

' '.join(list(jieba.cut(text)))

一般处理:

中文分词(jieba分词)

用于评估一个词在一个文件集或语料库中一份文件中的重要程度

TF-IDF作用

主要思想： 如果某个词或短语在一篇文章中出现的概率高，并且在其他文章中很少出现，则认为此词或者短语具有很好的类别区分能力，适合用来分类

词频（term frequency，tf）：指的是某一个给定的词语在该文件中出现的频率  `该指标通常会被归一化定义为TF=（某词在文档中出现的次数/文档的总词量），这样可以防止结果偏向过长的文档（同一个词语在长文档里通常会具有比短文档更高的词频）`逆向文档频率（inverse document frequency，idf）： 是一个词语普遍重要性的度量。某一特定词语的idf，可以由总文件数目除以包含该词语之文件的数目，再将得到的商取以10为底的对数得到  `包含某词语的文档越少，IDF值越大，说明该词语具有很强的区分能力`

API : sklearn.feature_extraction.text.TfidfVectorizer

TF-IDF算法与SEO搜索引擎优化

Tf-idf

特征工程—特征提取

API： font color=\"#ed9745\

特征选择标准gini 或者\"entropy\"，前者代表基尼系数，后者代表信息增益。一默认\"gini\"，即CART算法。

criterion

内部节点再划分所需最小样本数这个值限制了子树继续划分的条件，如果某节点的样本数少于min_samples_split，则不会继续再尝试选择最优特征来进行划分。 默认是2。如果样本量不大，不需要管这个值。如果样本量数量级非常大，则推荐增大这个值。我之前的一个项目例子，有大概10万样本，建立决策树时，我选择了min_samples_split=10。可以作为参考。

min_samples_split

min_samples_leaf

决策树最大深度决策树的最大深度，默认可以不输入，如果不输入的话，决策树在建立子树的时候不会限制子树的深度。一般来说，数据少或者特征少的时候可以不管这个值。如果模型样本量多，特征也多的情况下，推荐限制这个最大深度，具体的取值取决于数据的分布。常用的可以取值10-100之间

max_depth

随机数种子

random_state

参数

加载数据

1. 选择特征值和目标值

2. 缺失值处理

3.数据分割

数据的基本处理

特征工程(特征提取-字典特征提取)

机器学习(模型训练)

模型评估

步骤

estimator: 决策树评估器

out_file: 可视化文件输出路径

feature_names: 特征值的名称

API : font color=\"#ed9745\

决策树可视化

案例实现

决策树算法API

作用： 主要用于处理连续型数据

如何选择划分点？

如何决定叶节点的输出值？

核心问题

算法描述

回归决策树和线性回归的对比

回归决策树

决策树 decision-tree