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

一、概述

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

我们可以简单的把决策树的构建规则看作是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 = ['色泽', '根蒂', '敲击', '纹理', '脐部', '触感']

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

实现效果如下所示：

决策树实现效果图

最后编辑于：2019.08.07 09:10:11

人面猴
序言：七十年代末，一起剥皮案震惊了整个滨河市，随后出现的几起案子，更是在滨河造成了极大的恐慌，老刑警刘岩，带你破解...
沈念sama阅读 211,376评论 6赞 491
死咒
序言：滨河连续发生了三起死亡事件，死亡现场离奇诡异，居然都是意外死亡，警方通过查阅死者的电脑和手机，发现死者居然都...
沈念sama阅读 90,126评论 2赞 385
救了他两次的神仙让他今天三更去死
文/潘晓璐我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
开封第一讲书人阅读 156,966评论 0赞 347
道士缉凶录：失踪的卖姜人
文/不坏的土叔我叫张陵，是天一观的道长。经常有香客问我，道长，这世上最难降的妖魔是什么？我笑而不...
开封第一讲书人阅读 56,432评论 1赞 283
港岛之恋（遗憾婚礼）
正文为了忘掉前任，我火速办了婚礼，结果婚礼上，老公的妹妹穿的比我还像新娘。我一直安慰自己，他们只是感情好，可当我...
茶点故事阅读 65,519评论 6赞 385
恶毒庶女顶嫁案：这布局不是一般人想出来的
文/花漫我一把揭开白布。她就那样静静地躺着，像睡着了一般。火红的嫁衣衬着肌肤如雪。梳的纹丝不乱的头发上，一...
开封第一讲书人阅读 49,792评论 1赞 290
城市分裂传说
那天，我揣着相机与录音，去河边找鬼。笑死，一个胖子当着我的面吹牛，可吹牛的内容都是我干的。我是一名探鬼主播，决...
沈念sama阅读 38,933评论 3赞 406
双鸳鸯连环套：你想象不到人心有多黑
文/苍兰香墨我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
开封第一讲书人阅读 37,701评论 0赞 266
万荣杀人案实录
序言：老挝万荣一对情侣失踪，失踪者是张志新（化名）和其女友刘颖，没想到半个月后，有当地人在树林里发现了一具尸体，经...
沈念sama阅读 44,143评论 1赞 303
护林员之死
正文独居荒郊野岭守林人离奇死亡，尸身上长有42处带血的脓包…… 初始之章·张勋以下内容为张勋视角年9月15日...
茶点故事阅读 36,488评论 2赞 327
白月光启示录
正文我和宋清朗相恋三年，在试婚纱的时候发现自己被绿了。大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
茶点故事阅读 38,626评论 1赞 340
活死人
序言：一个原本活蹦乱跳的男人离奇死亡，死状恐怖，灵堂内的尸体忽然破棺而出，到底是诈尸还是另有隐情，我是刑警宁泽，带...
沈念sama阅读 34,292评论 4赞 329
日本核电站爆炸内幕
正文年R本政府宣布，位于F岛的核电站，受9级特大地震影响，放射性物质发生泄漏。R本人自食恶果不足惜，却给世界环境...
茶点故事阅读 39,896评论 3赞 313
男人毒药：我在死后第九天来索命
文/蒙蒙一、第九天我趴在偏房一处隐蔽的房顶上张望。院中可真热闹，春花似锦、人声如沸。这庄子的主人今日做“春日...
开封第一讲书人阅读 30,742评论 0赞 21
一桩弑父案，背后竟有这般阴谋
文/苍兰香墨我抬头看了看天上的太阳。三九已至，却和暖如春，着一层夹袄步出监牢的瞬间，已是汗流浃背。一阵脚步声响...
开封第一讲书人阅读 31,977评论 1赞 265
情欲美人皮
我被黑心中介骗来泰国打工，没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留，地道东北人。一个月前我还...
沈念sama阅读 46,324评论 2赞 360
代替公主和亲
正文我出身青楼，却偏偏与公主长得像，于是被迫代替她去往敌国和亲。传闻我的和亲对象是个残疾皇子，可洞房花烛夜当晚...
茶点故事阅读 43,494评论 2赞 348

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

一、概述

二、特征选择

三、python实现

推荐阅读更多精彩内容