首页  思维导图  详情

决策树算法

2023-09-09 12:06:00   41  举报





AI智能生成

机器学习—决策树算法—一种分类学习方法

机器学习

决策树算法

机器学习算法

Machine Learning

作者其他创作

大纲/内容

简介

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

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

决策树分类原理

熵 Entropy

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

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

信息熵

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

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

信息熵、交叉熵、相对熵

信息增益（ID3）

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

计算过程

1. 计算整体信息熵

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

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

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

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

信息增益率（C4.5）

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

增益率：增益率是用前面属性a的信息增益Gain(D, a) 和属性a对应的"固有值"(intrinsic value)

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

信息增益率算法流程:

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

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

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

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

5. 计算信息增益率

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

7. 如果节点不纯, 就重复1-6过程, 直到所有节点都纯了为止.

C4.5 画出的决策树

C4.5算法的优点

1. 采用信息增益率来划分属性, 避免使用信息增益倾向于选择多个值属性.

2. 采用后剪枝的技术, 避免树高度无节制的增长，避免过拟合，同时减少了欠拟合的风险

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

处理缺少属性值的一种策略是赋给它结点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就是使用这种方法处理缺少的属性值。

Gini系数（CART）

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

计算公式: 1 - 每一个类别概率平方的和

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

按照某种分割方式, 分割后的基尼值

CART决策树算法流程

1. 计算各个属性, 每一种分割方式的基尼系数

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

3. 如果划分后节点不纯, 继续使用前面两个步骤进行划分

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

CART剪枝

为什么要减枝？

随着树节点的增长，在训练样集上的精度是单调上升的，然而在独立的测试样例上测出的精度先上升后下降

出现这种情况的原因：

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

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

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

常用剪枝方法

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

叶子节点最少样本数量, 如果小于这个样本就不在分了

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

规定叶子点信息熵阈值, 一旦达到这个阈值了就不在分了.

后剪枝: 生成决策树后, 再进行剪枝

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

特征工程—特征提取

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

特征提取分类

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

文本特征提取

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

字典特征提取

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

API

sklearn.feature_extraction.DictVectorizer(sparse=True)

参数:

sparse: 是否是稀疏矩阵, True,是(默认)

sparse矩阵/稀疏矩阵的优点：

节省内容
提高读取效率

方法:

fit_transform(x)

参数: 需要处理的数据

get_feature_names() :

获取特征名称

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

注意：对于值比较少的类别特征使用one-hot编码, 如果类别值很多就是对类别进行编号, 转换为数字特征即可

one-hot编码

文本特征提取

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

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

参数: stop_words=[] : 停用词, 这里出现的词就不统计了

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

方法:

fit_transform(x), 返回稀疏矩阵, 转不是稀疏矩阵, toarray()

get_feature_names() : 获取单词列表

中文分词(jieba分词)

安装

pip3 install jieba

使用:

方法: cut(text)

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

返回值: 分词后的生成器

一般处理:

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

Tf-idf

TF-IDF作用

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

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

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

API : sklearn.feature_extraction.text.TfidfVectorizer

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

决策树算法API

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