神刀安全网

机器学习实战之决策树

决策树的算法可谓是贴近我们的生活,通过下面的案例,你就会发现我们每天都在有意无意的使用着决策树算法(好厉害的样子)。
小明同学每天早上都要去学校,可步行、乘公交和坐隔壁老王叔叔的车(皮一下很开心)。这时,小明就开始做决策了:首先看天气,不下雨时就选择步行去学校;下雨时就看隔壁老王叔叔是否有空,有空就乘老王的车去学校,没空就选择乘公交去学校。如图所示。

机器学习实战之决策树

案例

决策树定义

通过上述案例,就可以对决策树下定义了:上图就是决策树(嗯。。。有点敷衍)。决策树由结点和有向边组成。结点有两种类型:内部节点和叶节点,内部节点表示一个特征或属性(天气,是否有空),叶节点表示一个类(步行、乘公交和坐隔壁老王叔叔的车)。

决策树算法原理

那怎么通过决策树算法来构造这棵树呢?(难道是上帝之手么?)上述案例较简单,我们现在提出一个很经典的案例,如图所示,我们首先到底是通过天气、湿度还是风级来进行决策了?这里就要提出熵和信息增益。

机器学习实战之决策树

案例

首先,我们看什么是熵。简单来说,熵是描述事物的混乱程度的(也可以说是不确定性)。例如:中国足球进入世界杯,这个不确定性可能是0,所以熵可能就是0;6面的色子的不确定性比12面色子的要低,所以熵也会比其低。现在就来看熵的公式:H = -∑ni=1p(xi)log2p(xi)
那6面色子的熵:1/6*log21/6的6倍,也就是2.585
以此类推,那12面的熵就是:3.585
最后,我们计算下该案例的信息熵:不打球为5,打球为9,因此熵计算为:

-(5/14 * log(5/14,2) + 9/14 * log(9/14,2)) 0.940 
信息增益

到底先按哪个特征划分数据集呢?我们有个原则,就是将无序的数据变得有序,换句话说,就是让熵变小,变的越小越好。而信息增益就是划分数据集前后熵的变化,这里就是要让信息增益越大越好。
我们以天气为例,计算划分后的信息增益:

  • 晴天时:2/5打球,3/5不打球,熵为:
-(2/5 * log(2/5,2) + 3/5 * log(3/5,2)) 0.971 
  • 阴天熵:0
  • 雨天熵:0.971

    机器学习实战之决策树

    天气

    天气为晴天、阴天和雨天的概率为5/14,4/14和5/14,所以划分后的熵为:5/14 * 0.971+4/14 * 0+5/14 * 0.971得0.693,信息增益为0.940-0.693为0.247,同理可以求出其他特征的信息增益。
    这里的天气信息增益最大,所以选择其为初始的划分依据。
    选择完天气做为第一个划分依据后,能够正确分类的就结束划分,不能够正确分类的就继续算其余特征的信息增益,继续前面的操作,结果如图所示。

    机器学习实战之决策树

    结果

伪代码

所以决策树是一个递归算法,伪代码如下:

def createBranch():     检测数据集中的所有数据的分类标签是否相同:         If so return 类标签         Else:             寻找划分数据集的最好特征(划分之后信息熵最小,也就是信息增益最大的特征)             划分数据集             创建分支节点                 for 每个划分的子集                     调用函数 createBranch (创建分支的函数)并增加返回结果到分支节点中             return 分支节点 

决策树之海洋生物分类

问题描述与数据

数据为判断是否为鱼类,有两个特征:

  • 在水中是否生存
  • 是否有脚蹼

    机器学习实战之决策树

    案例

    这里需要我们自己手动构造数据:

def creatDataSet():     dataSet = [         [1, 1, 'yes'],         [1, 1, 'yes'],         [1, 0, 'no'],         [0, 1, 'no'],         [0, 1, 'no']     ]     labels = ['no surfacing', 'flippers']     return dataSet, labels 

这里的dataSet为数据,labels是两个特征的名称。

计算熵

这里我们定义一个计算数据集熵的函数:

from math import log  def calcshannon(dataSet):     num = len(dataSet)     labelCounts = {}     for featVec in dataSet:         currentLabel = featVec[-1]         if currentLabel not in labelCounts.keys():             labelCounts[currentLabel] = 0         labelCounts[currentLabel] += 1     shannon = 0.0     for key in labelCounts:         prob = float(labelCounts[key])/num         shannon -= prob * log(prob, 2)     return shannon 

这个代码比较简单,就是对传入的数据,以最后一列(也就是分类label)求熵。

划分数据集

首先设置一个划分数据集的函数,参数为:待划分的数据,划分的特征和返回的特征值,该函数会在choose函数中被调用,用于计算最好的划分特征。

def splitDataSet(dataSet, axis, value):     retDataSet = []     for featVec in dataSet:         if featVec[axis] == value:             reduce = featVec[:axis]             reduce.extend(featVec[axis+1:])             retDataSet.append(reduce)     return retDataSet 
def choose(dataSet):     numfeature = len(dataSet[0]) - 1     baseEntropy = calcshannon(dataSet)     bestinfogain = 0.0     bestfeature = -1     for i in range(numfeature):         featlist = [example[i] for example in dataSet]         vals = set(featlist)         newEntropy = 0.0         for value in vals:             subDataSet = splitDataSet(dataSet, i, value)             prob = len(subDataSet)/float(len(dataSet))             newEntropy += prob*calcshannon(subDataSet)         infoGain = baseEntropy - newEntropy         if (infoGain > bestinfogain):             bestinfogain = infoGain             bestfeature = i         return bestfeature 
创建树

在所有特征使用完时,也没法对数据进行彻底的划分时,就需要使用多数表决来确定叶子节点的分类,代码如下,类似前文中KNN中的排序。

import operator def majority(classList):     classCount = {}     for vote in classList:         if vote not in classCount.keys():             classCount[vote] = 0         classCount[vote] += 1     sortedcount = sorted(classCount.items(),  key=operator.itemgetter(1), reverse=True)     return sortedcount[0][0] 

最后就是创建树的代码:

def createTree(dataSet, labels):     classList = [example[-1] for example in dataSet]     if classList.count(classList[0]) == len(classList):         return classList[0]     if len(dataSet[0]) == 1:         return majority(classList)     bestFeat = choose(dataSet)     bestFeatLabel = labels[bestFeat]     myTree = {bestFeatLabel:{}}     del (labels[bestFeat])     Vals = [example[bestFeat] for example in dataSet]     uvals = set(Vals)     for value in uvals:         sublabels = labels[:]         myTree[bestFeatLabel][value] = createTree(splitDataSet(dataSet, bestFeat, value), sublabels)     return myTree 

这里有两个终止递归的条件:一是所有类别能正确的划分了,二是特征使用完成。

机器学习实战之决策树

结果

算法优缺点

  • 优点:利于理解
  • 缺点:容易过拟合

转载本站任何文章请注明:转载至神刀安全网,谢谢神刀安全网 » 机器学习实战之决策树

分享到:更多 ()