决策树-特征选择及python实现

作者: wensong_kevin | 来源:发表于2019-08-03 11:18 被阅读0次

决策树-特征选择及python实现
统计学习方法思路疏导—决策树
用于分类的决策树的理解
李航-第5章决策树
特征工程（二）特征选择及python实现
十大数据挖掘算法之CART回归树
决策树: 特征选择之寻找最优划分
python实现svm和使用f-score
利用python实现对csv,arff,libsvm特征文件的导
决策树要点总结

一、概述

众所周知，决策树的引入是为了解决分类问题。提起决策树，很难不想到数据结构中的树。其实决策树就是一个树结构(二叉树或者非二叉树)，如果把给定的一组样本数据构建成一棵决策树，那么叶子节点就是该组数据的分类结果，而非叶子节点呢就是样本数据的各个特征值，分支就是每个特征在其值域内的取值，现在脑海中是不是已经有一棵树状结构了呢。构造好的树我已经有画面了，那么问题来了，该如何去构建这棵树呢？

我们可以简单的把决策树的构建规则看作是if-then规则，我个人对if-then的理解就是if-elif-else。根据对不同的特征值做出不同的判断，从而采取不同的措施。张口就来——“构建一棵树决策树就完事了”，关键在于如何去构建呢？总不能就依次选择样本数据给的特征，然后按照树的形状排开吧，这也太暴力了。那么该如何去构建一棵能够很好拟合样本数据并且能够对新输入的数据做出很准确的分类的决策树呢？这正是本片博客想要讨论的。决策树的构建主要有ID3、C4.5、CART算法，其实三者都大同小异，主要是特征选择的方式不同，下面我就详细的讲讲特征选择。

二、特征选择

其实所谓的特征选择，听起来感觉高大上，其实不然。在我们着手解决特征选择之前，我需要引入几个跟“熵”有关的概念。

(1) 信息熵。

假设一个取值为离散值的随机变量 $X$ 的概率是 $p_{i}$ ，那么 $X$ 的熵就是 $H(X)=-\sum_{i=1}^n(p_{i}*log(p_{i}) )$ ，所要表示的意思就是一个随机变量的不确定性(纯度)。信息熵也被称作经验熵

样本数据集的信息熵的计算公式是： $H(D)=-\sum_{k=1}^K(\frac{|C_{k} |}{|D|} *\log_2 \frac{|C_{k} |}{|D|} ) )$ 其中 $|D|$ 是样本数据的总数，样本中一共有 $K$ 个类，| $C_{k}$ |是某个类别的数量，那么 $\frac{|C_{k} |}{|D|}$ 就是某个类别的概率咯。

(2)条件熵。

类比条件概率的概念我们很容易理解，其实条件熵就是在整个样本数据的条件，每个特征(随机变量)的不确定性。同样的，条件熵也被称作经验条件熵。

特征A对数据集D的条件熵的计算公式： $H(D|A)=-\sum_{i=1}^n (\frac{|D_{i} |}{|D|} ) \sum_{k=1}^K(\frac{|D_{ik} |}{|D_{i} |} *\log_2 \frac{|D_{ik} |}{|D_{i} |} ) ) )$ 其中 $D_{i}$ 是样本集 $D$ 的子集， $D_{ik}$ 是子集 $D_{i}$ 中分类结果为 $C_{k}$ 的样本数据。

(3)信息增益。

信息增益可以理解为某一个特征在得知某一条件之后，其不确定性减少的程度。

信息增益的计算公式： $g(D,A) = H(D)-H(D|A)$ 即为集合 $D$ 的经验熵与特征 $A$ 给定条件下的经验条件熵的差值。

(4)信息增益比。

从名称也能看出，信息增益比是信息增益比上样本集 $D$ 关于特征 $A$ 的值的熵。

信息增益比的计算公式： $g_{R} = \frac{g(D,A)}{H_{A}(D) }$ 其中信息增益上式已求， $H_{A}= -\sum_{i=1}^n(\frac{|D_{i} |}{|D_{} |} *\log_2 \frac{|D_{i} |}{|D_{} |} ) )$ 注意，此时的 $n$ 是特征 $A$ 取值的个数。

(5)基尼指数。

我们首先要知道分类问题中，概率分布的基尼指数的定义是：

$Gini(p)=\sum_{k=1}^K p_{k}(1-p_{k} ) = 1-\sum_{k=1}^K p_{k} ^2$ 其中 $K$ 代表样本中类别数， $p_{k}$ 是某个类别的概率。

我们引申到样本集合 $D$ 来，那基尼指数就是： $Gini(D)= 1-\sum_{k=1}^K (\frac{|C_{k} |}{|D|} ) ^2$ 其中 $C_{k}$ 是样本集 $D$ 中第 $k$ 类的子集。

那么样本集合 $D$ 跟据特征 $A$ 是否取某一可能值被分割成 $D_{1} 、D_{2}$ ，则在特征 $A$ 的条件下，集合 $D$ 的基尼指数是：

$Gini(D，A)= \frac{|D_{1} |}{|D|} Gini(D_{1} )+ \frac{|D_{2} |}{|D|} Gini(D_{2} )$

好了，弄清楚上面这些公式，就可以开始特征选择啦。决策树构造的好坏，即泛化能力的强弱也在此一举了。我们都知道每次选择一个特征作为节点，选择标注就显得很重要了，如何选择呢？

ID3算法看了上面几个概念，心里默念到，既然要构建的树稳定可靠，而信息增益能够很好的反应特征的纯度并且计算起来相对简单，那我选择信息增益作为我的特征选择标准吧。

C4.5算法狡猾的看了一ID3，选择信息增益的话，会很偏袒那些取值选择较多种类的特征啊！我选信息增益比作为我的特征选择标准。

CART算法想了一下，既然基尼指数也表示样本集合的不确定性，基尼指数越小代表样本数据集越稳定，那我选择基尼指数作为特征选择的标准好了。

至此，决策树生成最关键的部分已经解决了，ID3算法、C4.5算法和CART算法分别选择信息增益、信息增益比和基尼指数作为各自的特征选择标准。

三、python实现

我选用周志华老师的《机器学习》一书中的西瓜数据作为样本数据集。

dataset=[ ['青绿', '蜷缩', '浊响', '清晰', '凹陷', '硬滑', '好瓜'],

['乌黑', '蜷缩', '沉闷', '清晰', '凹陷', '硬滑', '好瓜'],

['乌黑', '蜷缩', '浊响', '清晰', '凹陷', '硬滑', '好瓜'],

['青绿', '蜷缩', '沉闷', '清晰', '凹陷', '硬滑', '好瓜'],

['浅白', '蜷缩', '浊响', '清晰', '凹陷', '硬滑', '好瓜'],

['青绿', '稍蜷', '浊响', '清晰', '稍凹', '软粘', '好瓜'],

['乌黑', '稍蜷', '浊响', '稍糊', '稍凹', '软粘', '好瓜'],

['乌黑', '稍蜷', '浊响', '清晰', '稍凹', '硬滑', '好瓜'],

['乌黑', '稍蜷', '沉闷', '稍糊', '稍凹', '硬滑', '坏瓜'],

['青绿', '硬挺', '清脆', '清晰', '平坦', '软粘', '坏瓜'],

['浅白', '硬挺', '清脆', '模糊', '平坦', '硬滑', '坏瓜'],

['浅白', '蜷缩', '浊响', '模糊', '平坦', '软粘', '坏瓜'],

['青绿', '稍蜷', '浊响', '稍糊', '凹陷', '硬滑', '坏瓜'],

['浅白', '稍蜷', '沉闷', '稍糊', '凹陷', '硬滑', '坏瓜'],

['乌黑', '稍蜷', '浊响', '清晰', '稍凹', '软粘', '坏瓜'],

['浅白', '蜷缩', '浊响', '模糊', '平坦', '硬滑', '坏瓜'],

['青绿', '蜷缩', '沉闷', '稍糊', '稍凹', '硬滑', '坏瓜'] ]

labels = ['色泽', '根蒂', '敲击', '纹理', '脐部', '触感']

由于本人代码能力差，所以代码很臃肿，就不一一展示，附上代码链接。

实现效果如下所示：

决策树实现效果图

决策树-特征选择及python实现
一、概述众所周知，决策树的引入是为了解决分类问题。提起决策树，很难不想到数据结构中的树。其实决策树就是一个树结构...
统计学习方法思路疏导—决策树
决策树算法过程特征选择生成决策树决策树兼职特征选择选择下面 2 指标作为特征选择的依据信息增益：使用...
用于分类的决策树的理解
决策树学习的三个步骤：特征选择，决策树生成，决策树剪枝。特征选择特征选择在于选取对训练数据具有分类能力的特征。...
李航-第5章决策树
决策树的学习算法包特征选择、决策树的生成与决策树的剪枝过程。决策树学习应用信息增益准则选择特征。信息增益大的特征具...
特征工程（二）特征选择及python实现
什么是特征选择特征工程(Feature Selection)，也叫做特征子集选择(Feature Subset ...
十大数据挖掘算法之CART回归树
一、CART回归树概述决策树算法的关键在于选择最佳划分特征及特征重最佳划分点位置，即划分算法。ID3决策树的划分...
决策树: 特征选择之寻找最优划分
前言决策树算法的三个步骤：特征选择、决策树生成、决策树剪枝。其中特征选择要解决的核心问题就是：每个节点在哪个维度上...
python实现svm和使用f-score
使用方法使用python语言实现对于支持向量机（SVM）特征选择的实现，特征选择算法为f-score,该程序的主...
利用python实现对csv,arff,libsvm特征文件的导
使用方法使用python语言实现对于支持向量机（SVM）特征选择的实现，特征选择算法为f-score,该程序的主...
决策树要点总结
1、决策树的学习：特征选择、决策树的生成、决策树的剪枝 2、Greedy decision tree learni...

决策树-特征选择及python实现

一、概述

二、特征选择

三、python实现

相关文章

决策树-特征选择及python实现

统计学习方法思路疏导—决策树

用于分类的决策树的理解

李航-第5章决策树

特征工程（二）特征选择及python实现

十大数据挖掘算法之CART回归树

决策树: 特征选择之寻找最优划分

python实现svm和使用f-score

利用python实现对csv,arff,libsvm特征文件的导

决策树要点总结

网友评论

延伸阅读

深度阅读

栏目导航

热点阅读