数据挖掘决策树的原理(常用数据挖掘算法从入门到精通)
数据挖掘决策树的原理(常用数据挖掘算法从入门到精通)对于连续值属性,必须考虑所有可能的划分点。其策略类似于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指数主要是度量数据划分或训练数据集D的不纯度为主,Gini值越小,表明样本的“纯净度”越高
对缺失值的处理详见《常用数据挖掘算法从入门到精通 第八章 C4.5决策树分类算法》中有介绍
对于离散值属性,在算法中递归的选择该属性产生最小Gini指标的子集作为它的分裂子集
对于连续值属性,必须考虑所有可能的划分点。其策略类似于C4.5算法中介绍的方法,利用Gini指数最小原则,选择划分点
-
创建根节点R
-
如果当前DataSet中的数据的类别相同,则标记R的类别标记为该类
-
如果决策树高度大于alpha,则不再分解,标记R的类别classify(DataSet)
-
递归情况:
-
标记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算法和ID3算法以及C4.5算法的过程基本都是相同的,主要的区别就是在属性选择标准上CART算法采用Gini指数作为选择标准,其他过程基本一样,《第七章 ID3决策树分类算法》和《 第八章 C4.5决策树分类算法》都给出了不同的案例和决策树具体计算构建过程,感兴趣的读者可以参照本章前面给出的Gini指数的计算方法,将前面给出的案例算一算用以构建CART决策树。