决策树

基本概念

分类是一种重要的数据分析形式,例如有一批教师家访的数据,要根据这些数据来将教师分成敬业的非敬业的两类,这个数据分析任务就叫做分类(classification)

分类需要构造一个叫分类器(classifer)的模型来预测类标号,例如教师敬业是0,非敬业是1。像这种只有有限个分类结果的分类,分类结果可以用离散值来表示,且值之间的次序没有意义。

而如果你是要预测某顾客在某商场的一次购物要花多少钱,这种分析任务就属于数值预测(numeric prediction),它预测一个连续值或者有序值。这种模型就叫预测器(predictor)回归分析(regression analysis)是数值预测中最常用的统计学方法。本篇主要讲解分类。

分类的一般过程

分类一般有两个阶段

  • 学习阶段(构建分类器)

通过已知类标号的数据集进行分析训练,构造分类器,训练数据集中的每一条数据由N个属性和当前数据的所属类标号构成。类标号是离散的、无序的。因为提供了每条数据的所属类标号,因此属于监督学习(supervised learning)。此阶段可以看成构造一个映射函数y=f(X),X是数据集中的某一条数据,y是X所属的类标号。

  • 分类阶段(用分类器预测给定数据的类标号)

如果使用训练集来度量分类器的准确率,结果可能是乐观的,因为分类器趋向于过拟合(overfit),它可能在学习期间包含了一些特殊的异常数据,而这些异常数据在实际中并不存在。因此应该用独立的于训练集的一组数据来进行准确率的检测。

决策树

为什么用决策树进行分类:

  • 顾名思义,决策树是一种树结构,用树的方式表示分类条件是直观的,且容易被人理解。
  • 决策树分类器的构造不需要任何领域的知识或参数设置,因此适合探索式知识发现。
  • 决策树可以处理高维数据。
  • 决策树的归纳学习和分类步骤是简单而又快速的,而且具有很好的准确率。

例如根据顾客信息预测顾客是否购买计算机的决策树如下图: 有帮助的截图

决策树归纳

现实中人通过主观意念来构造决策树,而机器是怎么构造决策树的呢?

决策树的主要算法包括ID3、C4.5、CART,它们采用贪心策略,以自顶向下递归的分治方法构造决策树。

算法的三个输入参数:D,attribute_list,attribute_selection_method

  • D: 训练数据集,包含N条数据,每条数据由M个属性的值和所属的类标号构成。
  • attribute_list: 候选属性的集合,初始是除所属类标号之外的所有属性,后续会随着算法的分支而减少。
  • attribute_selection_method: 选择属性的度量方式,例如信息增益、基尼系数等。树是否会被构造成严格的二叉树取决于属性的度量方式,如基尼系数强制结果树是二叉树,而信息增益允许多路划分。

算法 generate_decision_tree(Dj, attribute_list),由数据集D中的训练数据产生决策树。 大致流程如下:

  1. 创建一个节点N;
  2. if \( D \) 中所有数据都属于同一类 \( C \) ,(例如上图中所有的中年都属于购买计算机的一类。)
  3.  then 将节点N置为叶节点,并以类 \( C \) 标记,返回叶节点N
  4. if attribute_list.size == 0,即所有的属性都已经作为分裂属性用过了
  5.  then 将节点N置为叶节点,以多数表决的方式,选取D中数据占比最大的类标号对节点进行标记,返回N
  6. else 使用attribute_selection_method(D, attribute_list)找出最好的分裂标准(能将D划分的更纯,划分出的每一个子类的绝大多数数据的所属类标号相同),并用分裂标准标记节点N
  7. if 分裂标准中的分裂属性A是离散的且允许多路划分
  8.  then 将分裂属性A从attribute_list移除
  9. for 分裂标准中的每个输出 j (划分数据并对每个分区产生子树),设\( D_j \)是\( D \)中划分到 \( j \) 数据分区的数据集
  10.  if \( D_j \) 为空,即当前分支没有数据
  11.   then 加一个树叶到节点N,标记为D中的多数类
  12.  else 加一个由 generate_decision_tree(Dj, attribute_list) 返回的节点到N
  13. endfor
  14. 返回结果决策树N

属性的度量方式

属性选择度量是一种分裂标准,选择哪个属性按什么标准进行划分能将数据分类分的更纯——即分完的类中的绝大多数数据都属于同一类标号。属性选择度量给所有的属性提供了秩评定,选取当前评分最高的属性(即将数据分的最纯的属性)作为当前的分裂属性。

常用的三种评分方式:

  • 信息增益:

选择具有最高信息增益的属性作为节点N的分裂属性,该属性使结果分区中对数据分类所需要的信息量最小,并反映这些分区中的不纯性。此种方式使得对分区进行分类所需要的期望测试数目最小,并确保找到一个简单的(但不一定是最简单的)树。

对D中数据分类所需要的期望信息由下式给出: \[ Info(D) = - \sum_{i=1}^m p_i\log_2(p_i) \]

其中 \( p_i \) 是数据集D中的任意数据 \( x \) 属于类 \( C_i \) 的概率,\( p_i = | C_i | / | D | \),\( Info(D) \)是要识别D中数据的类标号所需要的平均信息量,又称为 \( D \) 的熵(entropy)。熵越大,数据 \( x \) 所属类的不确定性就越大。例如 \( p_1 = 0.5 \), \( p_2 = 0.5 \) 和 \( p_1 = 1.0 \), \( p_2 = 0.0 \),很明显第一种的熵更大。

现假设我们要按属性A将 \( D \) 中的数据进行划分,其中A属性根据训练数据的观测有 \( v \) 个不同值 \( { a_1,a_2,\ldots,a_v} \),如果A是离散的,那么这 \( v \) 个值将对应与属性A上测试的 \( v \) 个输出分区 \( {D_1,D_2,\ldots,D_v } \),对于 \( D_j \) 中的数据,他们的属性A都是 \( a_j \)。这些分区对应于从节点N生长出来的 \( v \) 个分支。我们希望此次划分能将每个分区都划分的更纯,但实际上多半是不纯的,例如 \( D_1 \) 中可能70%是 \( C_1 \) 类,30%是 \( C_2 \) 类。在此次划分之后,为了得到更准确的分类,我们还需要多少信息呢?这个量由下面的式子来描述: \[ Info_A(D) = \sum_{j=1}^v \frac{|D_j|}{|D|}*Info(D_j) \]

其中\( \frac{|D_j|}{|D|} \)是第\( j \)个分区的权重。\( Info_A(D) \)是对 \( D \) 按属性A进行数据分类后还需要的期望信息量,需要的期望信息越小,分区的纯度越高。

信息增益描述了本次划分后,我们得到了多少信息量,即原来的信息需求量减去划分后的信息需求量: \[ Gain(A) = Info(D) - Info_A(D) \]

所以,我们选择拥有最大信息增益的属性作为当前的分裂属性。对于一个数据集D,它的熵 \( Info(D) \) 是固定的,所以我们只需要计算最小的 \( Info_A(D) \),就可以选出当前的最佳分裂属性。

上面的例子是在属性A是离散的情况下,那么如果属性A的值是连续的值呢?在这种情况下,就需要确定A的最佳分裂点了,分裂点是A上的阈值。

首先,将A的值进行递增排序,典型的,每对相邻值的中点看作是可能的分裂点,这样如果 A 有 \( n \) 个值,那么就需要计算 \( n-1 \) 次分裂点。对A的每个可能的分裂点,计算其 \( Info_A(D) \),其中 \( v=2 \),共两个数据分区\( D_1 \)(\( A\leq split\_point \))、\( D_2 \)(\( A\geq split\_point \)),选择最小\( Info_A(D) \)的点作为分裂点。

  • 增益率:

信息增益度量倾向于选择具有大量值的属性。例如,当某一属性productId是数据的唯一标识,当按此属性进行数据划分时,每个数据分区都只有一条数据,所以每个数据分区中的数据都是纯的,它属于某一类的概率都是1.0,所以 \( Info(D_j) \) = 0, 所以\( Info_{productId}(D) \) = 0。因此对该属性的划分得到的信息增益一定是最大的。然而这种划分对数据分类没有任何意义。

ID3的后继C4.5使用增益率(gain ratio)作为信息增益的扩充,试图克服这种偏倚。它用分裂信息将信息增益规范化。分裂信息的定义: \[ SplitInfo_A(D)= - \sum_{j=1}^v \frac{|D_j|}{|D|}*\log_2(\frac{|D_j|}{|D|}) \]

该值代表由训练数据集D划分成对应与属性A的 \( v \) 个输出的不确定性 ,它与熵\( Info(D) \)不同,熵考虑的是数据分类的不确定性。

增益率定义: \[ GainRate(A)=\frac{Gain(A)}{SplitInfo_A(D)} \]

选择最大增益率的属性作为分裂属性。然而分裂信息趋向于0时,改比率会变得不稳定。为了避免这种状况,增加一个约束:选取的测试的分裂信息增益必须要大,至少与考察的所有测试的平均增益一样大,这样就避免了分裂信息的值趋于0。

  • 基尼系数:

基尼系数(Gini index)CART中使用,基尼系数度量数据分区或数组集D的不纯度,定义如下: \[ Gini(D)=1-\sum_{i=1}^m p_i^{2} \]

其中 \( p_i \) 和熵中的含义相同。

基尼系数考虑每个属性的二元划分。首先来看离散值属性的情况。假设属性A有 \( v \) 个不同值 \( { a_1,a_2,\ldots,a_v} \) 。为确定A上最好的二元划分,需要知道A所有可能值构成集合的所有子集,每个子集\( S_A \)可以看作是 \( A\in S_A? \) 的二元测试。A 存在 \( 2^v \) 个子集,去掉 \( { a_1,a_2,\ldots,a_v} \) 和 \( \phi \),基于A的二元划分,存在 \( \frac{2^v-2}{2} \) 种形成数据集D的两个分区的可能方法。

按A属性进行二元划分,计算每个结果分区的不纯度的加权和,有如下公式: \[ Gini_A(D) = \frac{|D_1|}{|D|}Gini(D_1) + \frac{|D_2|}{|D|}Gini(D_2) \]

对于离散属性,选择该属性产生的最小基尼系数的子集作为它的分裂子集。而对于连续值属性,需要考虑每一个可能的分裂点,策略类似与信息增益,在此不再赘述。对离散或连续属性的二元划分导致的不纯度的降低为: \[ Gini(D)-Gini_A(D) \]

具有最大不纯度降低,或者最小基尼系数的属性作为分裂属性。该属性和它的分裂子集或分裂点一起构成分裂准则。

qin

取消

感谢您的支持,我会继续努力的!

扫码支持
扫码支持
扫码打赏

打开支付宝扫一扫,即可进行扫码打赏哦