快捷搜索:  汽车  科技

数据挖掘决策树的原理(常用数据挖掘算法从入门到精通)

数据挖掘决策树的原理(常用数据挖掘算法从入门到精通)对于连续值属性,必须考虑所有可能的划分点。其策略类似于C4.5算法中介绍的方法,利用Gini指数最小原则,选择划分点对于离散值属性,在算法中递归的选择该属性产生最小Gini指标的子集作为它的分裂子集CART与前面介绍的ID3算法和C4.5算法不同的是,使用的属性度量标准是Gini指标Gini指数主要是度量数据划分或训练数据集D的不纯度为主,Gini值越小,表明样本的“纯净度”越高对缺失值的处理详见《常用数据挖掘算法从入门到精通 第八章 C4.5决策树分类算法》中有介绍

前面两篇文章给大家介绍了ID3和C4.5决策树分类算法,今天给大家介绍CART决策树分类算法

CART算法简介(Classification And Regression Tree)
  • CART同样由特征选择、树的生成及剪枝组成,即可以用于分类也可以用于回归

  • CART假设决策树是二叉树内部结点特征的取值为“是”和“否。这样的决策树等价于递归地二分每个特征

    • 二叉树不易产生数据碎片精确度往往也会高于多叉树,所以在CART算法中,采用了二元划分

  • CART与前面介绍的ID3算法和C4.5算法不同的是,使用的属性度量标准是Gini指标

Gini指数

Gini指数主要是度量数据划分或训练数据集D的不纯度为主Gini值越小,表明样本的“纯净度”越高

数据挖掘决策树的原理(常用数据挖掘算法从入门到精通)(1)

  • 缺失值的处理详见《常用数据挖掘算法从入门到精通 第八章 C4.5决策树分类算法》中有介绍

  • 对于离散值属性,在算法中递归的选择该属性产生最小Gini指标的子集作为它的分裂子集

  • 对于连续值属性,必须考虑所有可能的划分点。其策略类似于C4.5算法中介绍的方法,利用Gini指数最小原则,选择划分点

  • CART决策树的算法步骤
    1. 创建根节点R

    2. 如果当前DataSet中的数据的类别相同,则标记R的类别标记为该类

    3. 如果决策树高度大于alpha,则不再分解,标记R的类别classify(DataSet)

    4. 递归情况:

    • 标记R的类别classify(DataSet)

    • 从featureList中选择属性F(选择Gini(DataSet F)最小的属性划分,连续属性参考C4.5的离散化过程(以Gini最小作为划分标准))

    • 根据F,将DataSet做二元划分DS_L 和 DS_R:

      • 如果DS_L或DS_R为空,则不再分解

      • 如果DS_L和DS_R都不为空,节点:

    C_L= CART_classification(DS_L featureList alpha);

    C_R= CART_classification(DS_R featureList alpha)

      • 将节点C_L和C_R添加为R的左右子节点

    CART算法实例分析

    CART算法和ID3算法以及C4.5算法的过程基本都是相同的,主要的区别就是在属性选择标准上CART算法采用Gini指数作为选择标准,其他过程基本一样,《第七章 ID3决策树分类算法》和《 第八章 C4.5决策树分类算法》都给出了不同的案例和决策树具体计算构建过程,感兴趣的读者可以参照本章前面给出的Gini指数的计算方法,将前面给出的案例算一算用以构建CART决策树。

    猜您喜欢: