决策树(decision tree)是一种基本的分类与回归方法。在分类问题中,它可以认为是if-then规则的集合,也可以认为是定义在特征空间与类空间上的条件概率分布。在学习时,利用训练数据,根据损失函数最小化的原则建立决策树模型;在预测时,对新的数据,利用决策树模型进行分类。
1、决策树
1)决策树是一种树形结构,其中每个内部节点表示在一个属性上的测试,每个分支代表一个测试输出,每个节点代表一种类别。
2)决策树学习是以实例为基础的归纳学习,在本质上是从训练数据集中归纳出一组分类规则,其学习的策略是以损失函数(损失函数通常是正则化的极大似然函数)为目标函数的极小化。
3)决策树学习采用的是自顶向下的递归方法,其基本思想是以信息熵为度量构造一棵熵值下降最快的树,到叶子节点处的熵值为零,此时每个叶子节点中的实例都属于一类。
2、特征选择
特征选择在于选取对训练数据具有分类能力的特征,以提高决策树学习的效率。通常特征选择的准则是信息增益或信息增益比,在CART树里使用的是Gini指数。
2.1 信息增益(information gain)
首先来了解下熵和条件熵的定义。
熵(entropy)是表示随机变量不确定性的度量。设X是一个取有限个值的离散随机变量,其概率分布为
则随机变量X的熵定义为
在上式中的对数通常以2为底或以e为底(自然对数),这时熵的单位是比特(bit)或纳特(nat).
**条件熵(conditional entropy)**H(Y|X)表示在已知随机变量X的条件下随机变量Y的不确定性。定义为X给定条件下随机变量Y的条件概率分布的熵对X的数学期望
当熵和条件熵中的概率由数据估计(特别是极大似然估计)得到时,所对应的熵和条件熵分别成为经验熵和经验条件熵
信息增益(information gain)表示得知特征X的信息而使得类Y的信息的不确定性减少的程度。
定义:特征A对训练数据集D的信息增益g(D,A),定义集合D的经验熵H(D)与特征A给定条件下D的经验条件熵H(D|A)之差,即:
一般地,熵与条件熵之差成为互信息(mutual information),决策树学习中的信息增益等价于训练数据集中类与特征的互信息。
根据信息增益准则的特征选择方法是:对训练数据集(或子集)D,计算其每个特征的信息增益,并比较它们的大小,选择信息增益最大的特征。
2.2 信息增益比(information gain ratio)
信息增益的大小是相对于训练数据集而言的,并没有绝对意义。在训练数据集的经验熵大的时候,信息增益值会偏大。反之,信息增益值会偏小。使用信息增益比可以对这一问题进行校正。
定义:特征A对训练数据集D的信息增益比定义为信息增益g(D,A)与训练集D的经验熵H(D)之比:
2.3 Gini指数
定义:分类问题中,假设有K个类,样本点属于第k类的概率为pk,则概率分布的基尼指数定义为
对于给定的样本集合D,其基尼指数为
这里Ck是D中属于第k类的样本子集,K是类的个数。
基尼指数Gini(D)表示集合D的不确定性。基尼指数越大,样本集合的不确定性也就越大,这一点与熵值类似。
关于基尼指数的讨论,邹博老师也给除了如下图所示的解释:
总结:一个属性的信息增益(率)/gini指数越大,表明属性对样本的熵减少的能力更强,这个属性使得数据由不确定性变成确定性的能力越强。
3、决策树的生成
3.1 ID3算法
ID3算法的核心是在决策树各个结点上应用信息增益准则来选择特征,递归地构建决策树。ID3相当于用极大似然法进行概率模型的选择。
算法1 (ID3算法)
输入:训练数据集D,特征集A,阈值;
输出:决策树T。
(1)若D中所有实例属于同一类Ck,则T为单节点树,并将类Ck作为该节点的类标记,返回T;
(3)否则,计算A中各特征的对D的信息增益,选择信息增益最大的特征Ag;
(4)如果Ag的信息增益小于阈值,则置T为单结点树,并将D中实例数最大的类为该节点的类标记,返回T;
(5)否则,对Ag的每一可能值ai,依Ag=ai将D分割为若干非空子集Di,将Di中实例数最大的类作为标记,构建子节点,由结点及其子结点构成树T,返回T;
(6)对第i个子节点,以Di为训练集,以A-{Ag}为特征集,递归地调用步(1)~步(5),得到子树Ti,返回Ti。
3.2 C4.5的生成算法
C4.5算法与ID3算法相似,C4.5是对ID3的改进,C4.5在生成的过程中,用信息增益比来选择特征,其他步骤与ID3一样。
3.3 CART算法
CART是在给定输入随机变量X条件下输出随机变量Y的条件概率分布的学习方法。CART假设决策树是二叉树,内部节点特征的取值为“是”和“否”,左分支是取值为“是”的分支,右分支是取值为“否”的分支。这样的决策树等价于递归地二分每个特征,将输入控件即特征空间划分为有限个单元,并在这些单元上确定预测的概率分布,也就是在输入给定的条件下输出的条件概率分布。
算法2(CART生成算法)
输入:训练数据集D,停止计算的条件;
输出:CART决策树。
根据训练数据集,从根节点开始,递归地对每个结点进行以下操作,构建二叉决策树:
(1)设结点的训练数据集为D,计算现有特征对该数据集的基尼指数,此时,对每一个特征A,对其可能取的每个值a,根据样本点对A=a的测试为“是”或“否”将D分割成D1和D2两部分,利用上述所给的gini求解公式计算A=a的基尼指数。
(2)在所有可能的特征A以及它们所有可能的切分点a中,选择基尼指数最小的特征及其对应的切分点作为最优特征与最优切分点。依最优特征与最优切分点,从现结点生成两个子结点,将训练数据集依特征分配到两个子节点中去。
(3)对两个子节点递归地调用步骤(1)、(2),直至满足停止条件。
(4)生成CART决策树。
算法停止的条件是节点中的样本个数小于预定的阈值,或样本集的基尼指数小于预定阈值,或者没有更多特征。
4、决策树的剪枝
决策树生成算法递归地产生决策树,直到不能继续为止,这样产生的树容易过拟合。过拟合的原因在于学习时过多地考虑如何提高对训练数据的正确分类,从而构建出过于复杂的决策树。解决这个问题的办法就是简化决策树,即剪枝。
三种决策树的剪枝过程算法相同,区别的仅是对于当前树的评价标准不同。(信息增益,信息增益率,基尼指数)
通常情况下剪枝有两种:
先剪枝——在构造过程中,当某个节点满足剪枝条件,则直接停止此分支的构造。 后剪枝——先构造完成完整的决策树,再通过某些条件遍历树进行剪枝。数据分析师培训
剪枝的总体思路:
由完全树T0开始,剪枝部分结点得到T1,再次剪枝部分结点得到T2,……,直到仅剩树根的树Tk;
在验证数据集上对这K个树分别评价,选择损失函数最小的树Ta
决策树的剪枝往往通过极小化决策树整体的损失函数(loss function)或代价函数(cost function)来实现。设树T的叶结点个数为|T|,t是树T的叶结点,该叶节点有个样本点,其中k类的样本点有个,k=1,2,…,K,为叶节点t上的经验熵,为参数,则决策树学习的损失函数可以定义为:
其中经验熵为
在上述损失函数的式中,第一项表示模型对训练数据的预测误差,|T|表示模型复杂度,参数控制两者之间的影响,较大的促使选择较简单的模型(树),较小的a促使选择较复杂的模型(树)。a=0意味着只考虑模型与训练数据的拟合程度,不考虑模型的复杂度。
剪枝,就是当s确定时,选择损失函数最小的模型,即损失函数最小的子树。利用损失函数的极小化等价于正则化的极大似然估计进行模型选择。
剪枝系数a的确定,如下所示:
剪枝算法:
数据分析咨询请扫描二维码
在当今以数据为导向的商业环境中,数据分析师的角色变得越来越重要。无论是揭示消费者行为的趋势,还是优化企业运营的效率,数据 ...
2024-11-17在当今以数据为导向的商业环境中,数据分析师的角色变得越来越重要。无论是揭示消费者行为的趋势,还是优化企业运营的效率,数据 ...
2024-11-17金融数学是一门充满挑战和机遇的专业,它将数学、统计学和金融学的知识有机结合,旨在培养能够运用数学和统计方法解决复杂金融市 ...
2024-11-16在信息时代的浪潮中,大数据已成为推动创新的重要力量。无论是在商业、医疗、金融,还是在日常生活中,大数据扮演的角色都愈发举 ...
2024-11-16随着大数据技术的迅猛发展,数据已经成为现代商业、科技乃至生活各个方面的重要资产。大数据专业的毕业生在这一变革背景下,拥有 ...
2024-11-15随着大数据技术的迅猛发展,数据已经成为现代商业、科技乃至生活各个方面的重要资产。大数据专业的毕业生在这一变革背景下,拥有 ...
2024-11-15在快速演变的数字时代,数据分析已成为多个行业的核心驱动力。无论你是刚刚踏入数据分析领域,还是寻求进一步发展的专业人士,理 ...
2024-11-15Python作为一种通用编程语言,以其简单易学、功能强大等特点,成为众多领域的核心技术驱动者。无论是初学者还是有经验的编程人员 ...
2024-11-15在当今数据驱动的世界中,数据分析已成为许多行业的基础。无论是商业决策,产品开发,还是市场策略优化,数据分析都扮演着至关重 ...
2024-11-15数据分析作为现代商业和研究领域不可或缺的一部分,吸引了越来越多的初学者。然而,自学数据分析的过程中,初学者常常会遇到许多 ...
2024-11-15在当今的数据驱动世界中,机器学习方法在数据挖掘与分析中扮演着核心角色。这些方法通过从数据中学习模式和规律来构建模型,实现 ...
2024-11-15随着数据在各个行业的重要性日益增加,数据分析师在商业和技术领域的角色变得至关重要。其核心职责之一便是通过数据可视化,将复 ...
2024-11-15数据分析师的职责不仅仅局限于解析数据和得出结论,更在于将这些复杂的信息转换为清晰、易懂且具有影响力的沟通。良好的沟通能力 ...
2024-11-15数字化转型是企业提升竞争力和实现可持续发展的关键路径。面对快速变化的市场环境,以及技术的飞速发展,企业在数字化转型过程中 ...
2024-11-15CDA数据分析师认证:CDA认证分为三个等级:Level Ⅰ、Level Ⅱ和Level Ⅲ,每个等级的报考条件如下: Le ...
2024-11-14自学数据分析可能是一条充满挑战却又令人兴奋的道路。随着数据在现代社会中的重要性日益增长,掌握数据分析技能不仅能提升你的就 ...
2024-11-14数据分析相关职业选择 数据分析领域正在蓬勃发展,为各种专业背景的人才提供了丰富的职业机会。从初学者到有经验的专家,每个人 ...
2024-11-14数据挖掘与分析在金融行业的使用 在当今快速发展的金融行业中,数据挖掘与分析的应用愈发重要,成为驱动行业变革和提升竞争力的 ...
2024-11-14学习数据挖掘需要掌握哪些技能 数据挖掘是一个不断发展的领域,它结合了统计学、计算机科学和领域专业知识,旨在从数据中提取有 ...
2024-11-14统计学作为一门基于数据的学科,其广泛的应用领域和多样的职业选择,使得毕业生拥有丰厚的就业前景。无论是在政府还是企业,统计 ...
2024-11-14