在实际的数据集中,算法首先会评估数据集里所有的特征,来决定哪一个因素在这个决策过程中起到了关键作用,然后选择这个特征作为决策树的“分支“。它会计算每个特征能带来多大的“决策助力”(具体由信息增益、信息增益率、基尼指数等指标表现),简单来说,就是这个特征能给我们带来多少有用的信息,帮助我们减少选择时的不确定性。特征越能帮我们明确地划分数据,它给决策结果带来的助力就越大。
决策树算法就是不断地重复这个评估和选择特征的过程,这就是所谓的“递归”。我们可以想象大树的每一个分支都代表一个问题和它的答案。每次选择一个特征后,数据集就被分成几个小群体,每个群体都比之前更加纯净,也就是说,群体内部的成员更加相似。然后,算法会在每个小群体上重复之前的评估和选择特征的过程,直到每个群体不能再被细分,或者说,我们已经有足够的信息来作出决定了。
咱们买手机,一般都会关注几个点:价格、品牌、性能、外观、电池续航力等等。这些点就好比是决策树里面的“特征”,它们都会影响咱们最后的选择。
现在,假设你要帮朋友选一款手机,你朋友给你说了她的一些需求。比方说,她希望手机不要太贵,电池要用得久,还要能拍出好看的照片。这时,你就要在所有的特征中选出几个最关键的来决定买哪款手机。这个过程,就叫做特征选择。
我们可以把这个过程想象成一棵树,树的根部是你帮你朋友开始选手机的那一刻。每一个分叉点就是一个决策点,也就是需要考虑的一个特征。
首先,你可能会先看价格,因为你朋友说了不要太贵的。那么价格这个特征就好比是决策树的第一个分叉点,你会根据价格把手机分成两拨:贵的一拨,便宜的一拨。
然后,在价格合适的那一拨里面,你可能会考虑电池续航力。这个电池续航力就是决策树的第二个分叉点。这样一来,便宜的手机里面,又被你分出了电池续航力好和不好的两类。
最后,你可能会在电池续航力好的这一类中,再根据拍照功能来选。拍照功能就是决策树的第三个也是最后一个分叉点。这步操作之后,你就能挑出几款既便宜、电池又耐用、拍照又好的手机了。
通过这样一层层筛选下来,你就能把最适合你朋友的那款手机选出来。这整个过程,就像是一棵树一样,从树根到树梢,一步步缩小选择的范围,直到挑选出最佳的选项。
所以,特征选择就是要在众多可能影响决策的特征中挑出最有帮助、最能影响最终决策的那几个关键点。就像是在选手机时筛选出价格、电池续航力和拍照功能这几个最关键的特征,帮助我们做出最后的购买决定一样。
特征选择决定了每个节点应该基于哪个特征进行分割。特征选择的目标是选择出能最有效地分割数据集的特征,即选择出能使得分割后的子集尽可能纯净(即同一子集中的样本尽可能属于同一类别)的特征。
特征选择主要有三种评估指标。
在了解信息增益之前,我们先来聊一聊“熵”这个概念。在信息论的世界里,熵是用来描述信息有多么“杂乱无章”的一个量度。你可以把它想象成一个盛满了各种颜色小球的大罐子,如果小球的颜色五花八门,那么你随手抓一把出来,每次都会有新奇的颜色组合,这个状态就很“熵”。而如果小球都是一个颜色,那么每次看到的都是一样的,就没有什么“熵”了。
那么,信息增益又是什么呢?它其实跟我们生活中的“排除法”很像。想象一下,你在猜谜,谜底是一种水果,有很多种可能。如果有人告诉你这个水果是黄色的,那么你的猜测范围就缩小了,不确定性减少了。同样,在决策树中,我们希望找到那种能让我们的“猜测”更准确的线索,这种线索就是特征。通过计算不同特征的信息增益,我们能知道哪个特征在分类时更有帮助,更能减少不确定性。
信息增益(Information Gain)来源于信息论中的熵(Entropy)概念。在决策树中,我们使用信息增益来度量通过某特征对数据集进行划分,能够减少多少信息的不确定性。也就是说,我们通过计算每个特征的信息增益,来选择信息增益最大的特征进行分割,即选择这个特征对数据集进行划分,目的是最大化减少后续决策的不确定性,从而提高模型对数据的分类准确性。
信息增益计算公式为:
其中,熵的计算公式为:
其中 是该节点中每个类别的样本占比。这个公式表示,如果我们随机抽取一个样本,那么我们的不确定性(也就是需要多少信息才能确定这个样本的类别)是多少。
对于所有子节点的熵之和,计算步骤如下:
假设一个父节点被分割成了多个子节点,我们需要计算每个子节点的熵,然后再计算所有这些子节点熵的加权和。以下是分步骤的解释:
计算每个子节点的熵: 对于每个子节点,我们使用熵的公式来计算其熵值。如果子节点 有 个类别,那么子节点 的熵 可以计算如下: 其中 是子节点 中第 个类别的样本所占的比例。
计算每个子节点的权重: 每个子节点的权重是它的样本数量除以父节点的总样本数量。如果子节点 有 个样本,父节点有 个样本,那么子节点 的权重 是: 。
计算加权熵: 最后,我们计算每个子节点的加权熵,然后将它们加起来得到所有子节点的熵之和(简称总熵)。加权熵是每个子节点的熵乘以其权重:
其中 是子节点的索引。
例如,如果我们有一个数据集,其中有15个样本是正例,5个样本是反例,那么这个数据集的熵就是 。
接下来,根据某个特征划分得到两个子节点:
所以通过这个特征进行划分后,我们得到的总熵就是,所以这个特征的信息增益就是原始熵0.81减去0.5,等于0.31。
在决策树中,我们通常选择信息增益最大的特征进行划分。
然而信息增益有一个缺点: 对可取值数目多的特征有所偏好 。比方说,如果有个属性能取好多种值,用它来给数据分组,那结果就是能分出一堆细分得跟扁豆米似的小组。这种分法好像很细致,因为它把不确定性降到很低,但这其实可能是假象,因为这个属性有可能跟我们要预测的结果只是不经意间撞个正着,并不是真的有什么预测的大能力。结果就是,咱们的模型就好比小孩子画饼,看着美味实则泛不起波澜——就是过拟合了,拿去应对新情况的时候,它可能就束手无策了。举个例子,就像用指纹来判断人是不是爱吃巧克力。指纹这东西嘛,每个人的都不一样,看似能帮我们把人群分得清清楚楚,每个人都归到自己专属的小组里。但这真能告诉我们谁嘴馋谁不馋吗?显然是行不通的。如果我们真的用指纹来判断爱好,那遇到新人的时候,这招就不灵了,因为它根本就没有办法预测出新的情况。简而言之,这就好比是没有远见的小聪明,学到的东西只能在旧知识里打转,一旦要跳出来面对新场景,就束手无策了。
信息增益率(Information Gain Ratio)是对信息增益的一种改进,目的是为了减少信息增益对可取值数目多的特征的偏好。
信息增益率是在信息增益的基础上,加入了一个调整因子,这个调整因子是特征A的熵(也叫做固有值Intrinsic Value,也就是被选择用来划分这个数据集的特征的熵),它与数据集的熵不同。特征的熵计算的是特征A的不同取值所产生的分布的熵,它反映了特征A的取值的多样性。如果特征A的取值非常多样,每个取值的样本数量大致相等,那么特征A的熵就会很高。通过这个值来调整信息增益,可以减少信息增益对多值特征的偏好。
信息增益率的计算公式为:
其中,特征的熵计算公式与上述熵的计算公式相同,只是 变为该特征每个取值的样本占比。
例如,假设我们有一个关于天气情况的数据集,我们想要预测是否适合户外活动(是或否),数据集中有两个特征:风速(高、中、低)和温度(热、温和、凉爽)。我们的目标是决定使用哪个特征来分割数据集。
我们假设原数据集的分布如下:
数据集的原始熵(H)为:
现在我们假设“风速”特征的分布如下,以便符合原始的类别分布:
每个子集的熵计算如下:
“风速”特征的条件熵:
“风速”特征的信息增益:
然后,我们计算“风速”特征的熵:
得到信息增益率:
在决策树中,我们通常会选择信息增益率最大的特征进行划分。
基尼指数(Gini Index)来源于经济学中的基尼系数,用来度量财富分配的不均匀性。在决策树中,基尼指数用来度量数据的不纯度或者混乱度,基尼指数越小,数据的不纯度越低,分类效果越好。
基尼指数的计算公式为:
其中 是该节点中每个类别的样本占比。
这个公式实际上表示的是,如果我们随机抽取两个样本,它们属于不同类别的概率。因此,基尼指数实际上反映了分类错误的概率,这也就是为什么基尼指数越小,分类效果越好的原因。
例如,如果我们有一个数据集,其中有15个样本是正例,5个样本是反例,那么这个数据集的基尼指数就是 。
在构造决策树时,我们通常会选择基尼指数最小的特征进行划分。
决策树生成主要有三种算法。
ID3 (Iterative Dichotomiser 3) 算法是一种贪心算法,由罗斯·昆兰在1986年提出,用于生成决策树。其主要步骤如下:
从根节点开始,对每个节点进行以下操作:
ID3 算法使用信息增益作为特征选择的标准。信息增益计算公式如下:
其中, 是特征 的信息增益, 是数据集 的熵, 是特征 的所有取值, 是数据集 中特征 取值为 的样本子集, 是子集 的熵。
熵的计算公式如下:
其中, 是类别数目, 是数据集 中类别 的样本占比。
ID3 算法的缺点:
C4.5 算法是罗斯·昆兰在1993年提出的,是对 ID3 算法的改进。C4.5 算法在特征选择时使用信息增益率,而不是信息增益,以此来减少对取值多的特征的偏好。此外,C4.5 算法对连续特征进行了处理,并引入了剪枝技术来处理过拟合问题。
C4.5 算法的主要步骤如下:
从根节点开始,对每个节点进行以下操作:
生成完整的决策树后,对决策树进行剪枝。
在 C4.5 算法中,信息增益率的计算公式为:
其中, 是特征 的信息增益率, 是特征 的信息增益, 是特征 的固有值(Intrinsic Value),用来度量特征 的取值分布情况。
对于连续特征,C4.5 算法会先对其进行离散化处理,具体方法是将连续特征的所有可能取值按照升序排序,然后取相邻两个取值的中点作为候选切分点,选择信息增益率最大的切分点进行分割。
对于过拟合问题,C4.5 算法在生成完整的决策树后,会使用剪枝处理。
CART(Classification and Regression Tree)算法是由Breiman等人在1984年提出的。CART算法是一种二叉决策树,即每个内部节点都有两个子节点。并且,CART算法既可以用于分类问题,也可以用于回归问题。
CART算法的主要步骤如下:
从根节点开始,对每个节点进行以下操作:
在分类问题中,基尼指数的计算公式为:
其中, 是特征 的基尼指数, 是类别数目, 是数据集 中类别 的样本占比。
在回归问题中,平方误差的计算公式为:
其中, 是平方误差, 是样本数目, 是第 个样本的输出值, 是所有样本输出值的均值。
CART算法也使用剪枝处理来解决过拟合问题。