文章目录
0. 引言
前情提要:
《NLP深入学习(一):jieba 工具包介绍》
《NLP深入学习(二):nltk 工具包介绍》
《NLP深入学习(三):TF-IDF 详解以及文本分类/聚类用法》
《NLP深入学习(四):贝叶斯算法详解及分类/拼写检查用法》
《NLP深入学习(五):HMM 详解及字母识别/天气预测用法》
《NLP深入学习(六):n-gram 语言模型》
《NLP深入学习(七):词向量》
《NLP深入学习(八):感知机学习》
《NLP深入学习(九):KNN 算法及分类用法》
1. 什么是决策树
决策树是一种监督学习算法,用于分类和回归分析。它通过图形化的方式来表示一系列规则或条件测试,以确定给定输入数据的输出类别或数值预测。在构建决策树的过程中,主要任务是选择最优特征及其分割点来划分数据集,以便最大化信息增益、信息增益比、基尼不纯度减少或其他相似的指标。
以下是决策树算法的关键步骤:
属性选择:
- 在每个节点上,算法会选择一个最优属性作为分割标准。这一过程可以通过计算不同属性的信息增益(ID3)、信息增益比(C4.5)或基尼不纯度(CART)来进行。
- 信息增益:衡量的是划分后熵的减少程度,即基于某个属性划分前后的信息不确定性变化。
- 信息增益比:为了避免偏向具有较多取值的属性,C4.5 引入了信息增益比,它是信息增益与属性固有值的熵之比。
- 基尼不纯度:CART 算法使用基尼指数,其描述了一个集合中各类别的不确定性。基尼不纯度越小,说明数据集纯度越高。
- 在每个节点上,算法会选择一个最优属性作为分割标准。这一过程可以通过计算不同属性的信息增益(ID3)、信息增益比(C4.5)或基尼不纯度(CART)来进行。
分割数据集:
- 根据所选属性的最佳分割点将当前节点下的样本划分为若干子集,并为每个子集生成新的分支节点。
递归建树:
- 对于每个新生成的子集节点,重复上述属性选择和分割的过程,直至达到停止条件(如所有样本属于同一类、没有剩余属性可分割或者达到预设的最大深度等)。
剪枝处理:
- 决策树容易过拟合,为了提高泛化能力,通常需要对生成的树进行剪枝操作,移除那些可能带来过拟合影响的复杂分支。
预测阶段:
- 构建完成的决策树可以用来预测未知数据的类别或连续值,只需将新数据沿树的路径向下传递,直到到达叶节点,该叶节点对应的类别或数值即为预测结果。
2. ID3 算法
ID3(Iterative Dichotomiser 3)决策树算法是由 Ross Quinlan 在1986年提出的,主要用于分类问题的处理。它是基于信息论中的熵和信息增益来构建决策树模型的一种方法。
2.1 ID3算法的关键步骤
初始化:
- ID3 算法从根节点开始构建决策树,该节点代表的是整个训练数据集。
计算熵:
- 熵是衡量数据集纯度的一个指标。对于一个类别变量 C 的数据集 D,其熵定义为:
E n t r o p y ( D ) = − ∑ i = 1 n c P ( c i ) log 2 P ( c i ) Entropy(D) = -\sum_{i=1}^{n_c} P(c_i) \log_2 P(c_i) Entropy(D)=−i=1∑ncP(ci)log2P(ci)
其中, n c n_c nc 是类别 C 的个数, P ( c i ) P(c_i) P(ci) 是类别 c i c_i ci 在数据集 D 中出现的概率。
- 熵是衡量数据集纯度的一个指标。对于一个类别变量 C 的数据集 D,其熵定义为:
计算信息增益:
- 信息增益是通过属性 A 对数据集 D 划分后熵减少的程度,表示为:
G a i n ( D , A ) = E n t r o p y ( D ) − ∑ v = 1 V ∣ D v ∣ ∣ D ∣ E n t r o p y ( D v ) Gain(D, A) = Entropy(D) - \sum_{v=1}^{V} \frac{|D_v|}{|D|} Entropy(D_v) Gain(D,A)=Entropy(D)−v=1∑V∣D∣∣Dv∣Entropy(Dv)
其中, V V V 是属性 A 的不同取值个数, D v D_v Dv 表示在属性 A 上取值为 v 时数据集 D 的子集, ∣ D v ∣ |D_v| ∣Dv∣ 和 ∣ D ∣ |D| ∣D∣ 分别表示子集和总数据集的样本数量。
- 信息增益是通过属性 A 对数据集 D 划分后熵减少的程度,表示为:
选择最佳属性:
- 对于数据集 D 中的每一个属性 A,计算其信息增益,并从中选择具有最大信息增益的属性作为当前节点的分割依据。
生成分支节点:
- 根据所选的最佳属性及其各个可能取值,将数据集划分为多个子集,并为每个子集创建新的分支节点。
递归构建子树:
- 对每个子集重复上述过程,在子集中继续寻找最优属性进行划分,直到达到以下停止条件之一:
- 所有实例属于同一类。
- 没有更多的属性可以用来划分。
- 达到预设的最大深度或满足其他剪枝条件。
- 对每个子集重复上述过程,在子集中继续寻找最优属性进行划分,直到达到以下停止条件之一:
生成叶节点:
- 当不能进一步划分时,以该节点下的实例最多的类别作为叶节点的类别标记。
完成决策树:
- 经过以上步骤,最终得到一棵能够根据输入特征预测输出类别的决策树。
ID3 算法有一个主要限制,即偏向于选择具有较多属性值的特征,这可能导致过拟合问题。为了解决这个问题,Quinlan 后来提出了改进版的C4.5 算法,它使用了信息增益比作为属性选择的准则,从而更好地处理连续性和离散性特征不均衡的问题。
2.2 例子
为了更清晰地说明 ID3 算法的计算过程,我们可以考虑一个二分类问题,预测一个人是否购买电脑(Yes/No),属性包括年龄(Young/Middle-aged/Senior)、收入(Low/Medium/High)、学生身份(Yes/No)、信用等级(Fair/Excellent)。
下面是一个小型数据集:
| Age | Income | Student | Credit Rating | Buys Computer |
|--------------|--------------|--------------|---------------|---------------|
| Young | High | No | Fair | No |
| Young | High | No | Excellent | No |
| Young | Medium | No | Fair | Yes |
| Young | Low | Yes | Fair | Yes |
| Young | Low | Yes | Excellent | No |
| Middle-aged | Low | Yes | Excellent | Yes |
| Middle-aged | Low | Yes | Fair | Yes |
| Middle-aged | High | No | Fair | Yes |
| Middle-aged | High | Yes | Excellent | Yes |
| Senior | Low | Yes | Fair | Yes |
| Senior | High | Yes | Excellent | No |
| Senior | Medium | No | Excellent | Yes |
| Senior | Medium | No | Fair | Yes |
接下来,我们将使用ID3算法构建一个决策树。ID3的核心思想是选择每一步中信息增益最大的属性进行划分。信息增益的计算基于信息熵的概念。
计算整个数据集的信息熵(Entropy):
- 计算Yes和No的概率:P(Yes) = 9/14, P(No) = 5/14
- 计算信息熵:Entropy(S) = - P(Yes) * log2(P(Yes)) - P(No) * log2(P(No))
这里,Entropy(S) ≈ - (9/14) * log2(9/14) - (5/14) * log2(5/14) ≈ 0.94。
计算每个属性的信息增益:
- 对于年龄(Age):
- 计算每个值的条件概率和信息熵(例如,对于Young,计算P(Yes|Young)和P(No|Young),然后计算Entropy(Young))
- 计算信息增益:Information Gain(Age) = Entropy(S) - [P(Young) * Entropy(Young) + P(Middle-aged) * Entropy(Middle-aged) + P(Senior) * Entropy(Senior)]
类似地,对于其他属性(Income、Student、Credit Rating)也进行计算信息增益。
- 对于年龄(Age):
选择信息增益最大的属性进行划分:
- 在这个例子中,我们假设Age的信息增益最大,因此选择Age作为树的根节点。
递归地应用ID3算法:
- 对于每个Age的取值,继续应用ID3算法,重复上述步骤。
3. C4.5 算法
C4.5 算法是 ID3 决策树算法的一个重要扩展和改进版本,由 Ross Quinlan 在1990年代提出。C4.5 旨在克服 ID3 中的一些局限性,尤其是对于处理连续属性、缺失值以及过拟合问题的不足。以下是 C4.5 算法的主要特点和步骤:
3.1 特点与改进
信息增益率:
- 虽然 ID3 使用信息增益来选择划分数据集的最佳特征,但C4.5使用了信息增益率(Information Gain Ratio, IGR),它是信息增益除以属性的固有熵(即该属性在数据集中包含的信息量)。这样可以更公正地对待具有不同数量类别值的属性,避免过分偏好拥有较多取值的属性。
处理连续属性:
- ID3 只能处理离散属性,而 C4.5 则引入了一种将连续属性离散化的方法。通过查找最佳分割点,它可以对连续属性进行二分或多分,从而将其转化为离散属性来进行决策树的构建。
缺失值处理:
- C4.5 提供了处理数据中缺失值的能力。它可以通过观察其他样本的属性值分布,或者利用平均数、中位数等统计量来填充缺失值,使得含有缺失值的样本也能参与到决策树的构建过程中。
剪枝处理:
- 为了避免过拟合,C4.5 实现了后剪枝技术。它首先构造一个完整的决策树,然后通过评估子树的错误率和复杂度来决定是否对其进行简化,最终得到一个简化版的决策树模型,这通常会带来更好的泛化性能。
3.2 C4.5 算法步骤
初始化:
- 同ID3一样,从根节点开始,整个训练数据集作为当前数据集。
计算信息增益率:
- 计算当前数据集中每个属性的信息增益率,并选择最高增益率的属性作为当前节点的分裂依据。
创建分支节点:
- 根据所选属性的不同取值或分割点将数据集划分为多个子集,并为每个子集生成新的节点。
递归构建子树:
- 对每个子集重复上述过程,直到达到停止条件,如所有实例属于同一类、没有剩余属性可分割或者满足预设的最小叶子节点样本数等。
剪枝操作(可选):
- 在完成整个决策树构建之后,根据预定义的准则(例如悲观错误估计或代价复杂度剪枝)进行剪枝,形成一个简化且可能泛化能力更强的决策树。
转换成规则集(可选):
- C4.5 还可以输出对应的IF-THEN规则集,便于解释和应用。
处理连续属性和缺失值:
- 在划分数据集时,对连续属性进行离散化,对缺失值进行合理填充或特殊处理。
通过这些改进,C4.5 不仅保留了 ID3 的直观易懂和易于实现的优点,还在实际应用中提高了分类性能和对复杂数据集的适应能力。
4. CART 算法
CART(Classification and Regression Trees)是一种用于分类和回归问题的决策树算法。与 ID3 和 C4.5 算法不同,CART 决策树既能处理分类问题,也能处理回归问题。CART 算法由 Breiman 等人提出,其核心思想是递归地将数据集划分为较小的子集,直到满足停止条件为止。
4.1 主要特点:
二叉树结构: CART 生成的决策树是二叉树,每个非叶子节点都有两个子节点。
划分准则: CART 使用基尼不纯度(Gini Impurity)作为划分准则。对于分类问题,基尼不纯度表示一个数据集中随机抽取两个样本,它们属于不同类别的概率。
对于给定的数据集 D,基尼不纯度 Gini(D) 的计算公式为:
G i n i ( D ) = 1 − ∑ i = 1 k ( p i ) 2 Gini(D) = 1 - \sum_{i=1}^{k} (p_i)^2 Gini(D)=1−i=1∑k(pi)2
其中, p i p_i pi 是样本属于第 i 类别的概率。划分属性选择: 对于每个非叶子节点,CART 算法选择使得划分后基尼不纯度最小的属性进行划分。
剪枝: CART 生成的决策树可能存在过拟合的问题,因此在生成树之后,通常会进行剪枝操作,以提高泛化性能。
4.2 计算过程:
选择初始节点: 将整个数据集作为初始节点。
选择最优划分属性: 对于当前节点,计算每个属性的基尼不纯度,选择使得基尼不纯度最小的属性进行划分。如果属性是离散的,可以尝试所有可能的划分点;如果属性是连续的,可以考虑不同的阈值。
递归划分: 根据最优属性划分数据集,对每个子节点重复上述过程,直到满足停止条件。停止条件可以是达到最大深度、样本数小于阈值等。
剪枝: 生成完整的决策树后,通过剪枝操作减小过拟合风险。剪枝的目标是在保持模型性能的同时,减小树的复杂度。
CART 算法既可以应用于分类问题,也可以应用于回归问题。对于回归问题,CART 使用均方误差(Mean Squared Error)作为划分准则,而不是基尼不纯度。CART 的灵活性使得它在多种问题上都能表现出色。在实际应用中,可以通过调整超参数(如树的深度、最小样本数等)来优化 CART 生成的决策树。
4.3 例子
为了演示 CART 算法的具体计算过程,我们将考虑一个简单的分类问题,该问题涉及两个特征:Outlook(晴天、多云、雨天)和 Temperature(热、温暖、冷)。我们的目标是预测是否玩网球(PlayTennis:Yes或No)。
下面是一个小型的训练数据集:
| Outlook | Temperature | PlayTennis |
|----------|-------------|------------|
| Sunny | Hot | No |
| Sunny | Hot | No |
| Overcast | Hot | Yes |
| Rain | Mild | Yes |
| Rain | Cool | Yes |
| Rain | Cool | No |
| Overcast | Cool | Yes |
| Sunny | Mild | No |
| Sunny | Cool | Yes |
| Rain | Mild | Yes |
现在,我们将使用 CART 算法构建一个决策树,通过计算基尼不纯度选择最优划分属性。
计算基尼不纯度:
计算整个数据集的基尼不纯度 (Gini(D)):
G i n i ( D ) = 1 − ( ( 6 10 ) 2 + ( 4 10 ) 2 ) Gini(D) = 1 - \left( \left(\frac{6}{10}\right)^2 + \left(\frac{4}{10}\right)^2 \right) Gini(D)=1−((106)2+(104)2)
计算得到 G i n i ( D ) = 0.48 Gini(D) = 0.48 Gini(D)=0.48。
按照每个特征计算条件基尼不纯度 (Gini_feature):
对于 Outlook 的三个取值(Sunny、Overcast、Rain):
- 对于 Outlook=Sunny:
G i n i _ f e a t u r e ( S u n n y ) = 1 − ( ( 3 5 ) 2 + ( 2 5 ) 2 ) Gini\_feature(Sunny) = 1 - \left( \left(\frac{3}{5}\right)^2 + \left(\frac{2}{5}\right)^2 \right) Gini_feature(Sunny)=1−((53)2+(52)2) - 对于 Outlook=Overcast:
G i n i _ f e a t u r e ( O v e r c a s t ) = 1 − ( ( 4 4 ) 2 + ( 0 4 ) 2 ) Gini\_feature(Overcast) = 1 - \left( \left(\frac{4}{4}\right)^2 + \left(\frac{0}{4}\right)^2 \right) Gini_feature(Overcast)=1−((44)2+(40)2) - 对于 Outlook=Rain:
G i n i _ f e a t u r e ( R a i n ) = 1 − ( ( 3 4 ) 2 + ( 1 4 ) 2 ) Gini\_feature(Rain) = 1 - \left( \left(\frac{3}{4}\right)^2 + \left(\frac{1}{4}\right)^2 \right) Gini_feature(Rain)=1−((43)2+(41)2)
对于 Temperature 的三个取值(Hot、Mild、Cool):
- 对于 Temperature=Hot:
G i n i _ f e a t u r e ( H o t ) = 1 − ( ( 2 2 ) 2 + ( 0 2 ) 2 ) Gini\_feature(Hot) = 1 - \left( \left(\frac{2}{2}\right)^2 + \left(\frac{0}{2}\right)^2 \right) Gini_feature(Hot)=1−((22)2+(20)2) - 对于 Temperature=Mild:
G i n i _ f e a t u r e ( M i l d ) = 1 − ( ( 2 4 ) 2 + ( 2 4 ) 2 ) Gini\_feature(Mild) = 1 - \left( \left(\frac{2}{4}\right)^2 + \left(\frac{2}{4}\right)^2 \right) Gini_feature(Mild)=1−((42)2+(42)2) - 对于 Temperature=Cool:
G i n i _ f e a t u r e ( C o o l ) = 1 − ( ( 4 4 ) 2 + ( 0 4 ) 2 ) Gini\_feature(Cool) = 1 - \left( \left(\frac{4}{4}\right)^2 + \left(\frac{0}{4}\right)^2 \right) Gini_feature(Cool)=1−((44)2+(40)2)
- 对于 Outlook=Sunny:
选择最优划分:
选择使得条件基尼不纯度 G i n i _ f e a t u r e Gini\_feature Gini_feature 最小的特征作为划分特征。在这个例子中,选择 Outlook=Overcast,因为它具有最小的条件基尼不纯度。
递归划分:
对于 Outlook=Overcast 的分支,由于所有样本都属于同一类别(PlayTennis=Yes),因此这个分支成为叶节点。
对于 Outlook=Sunny 和 Outlook=Rain 的分支,我们将递归地重复上述步骤,直到满足停止条件。
这个过程会一直进行下去,构建整个决策树。在实际应用中,通常还需要进行剪枝操作以防止过拟合。
5. 参考
《NLP深入学习(一):jieba 工具包介绍》
《NLP深入学习(二):nltk 工具包介绍》
《NLP深入学习(三):TF-IDF 详解以及文本分类/聚类用法》
《NLP深入学习(四):贝叶斯算法详解及分类/拼写检查用法》
《NLP深入学习(五):HMM 详解及字母识别/天气预测用法》
《NLP深入学习(六):n-gram 语言模型》
《NLP深入学习(七):词向量》
《NLP深入学习(八):感知机学习》
《NLP深入学习(九):KNN 算法及分类用法》
欢迎关注本人,我是喜欢搞事的程序猿; 一起进步,一起学习;
也欢迎关注我的wx公众号:一个比特定乾坤