决策树的算法可谓是贴近我们的生活,通过下面的案例,你就会发现我们每天都在有意无意的使用着决策树算法(好厉害的样子)。
小明同学每天早上都要去学校,可步行、乘公交和坐隔壁老王叔叔的车(皮一下很开心)。这时,小明就开始做决策了:首先看天气,不下雨时就选择步行去学校;下雨时就看隔壁老王叔叔是否有空,有空就乘老王的车去学校,没空就选择乘公交去学校。如图所示。
通过上述案例,就可以对决策树下定义了:上图就是决策树(嗯。。。有点敷衍)。决策树由结点和有向边组成。结点有两种类型:内部节点和叶节点,内部节点表示一个特征或属性(天气,是否有空),叶节点表示一个类(步行、乘公交和坐隔壁老王叔叔的车)。
那怎么通过决策树算法来构造这棵树呢?(难道是上帝之手么?)上述案例较简单,我们现在提出一个很经典的案例,如图所示,我们首先到底是通过天气、湿度还是风级来进行决策了?这里就要提出熵和信息增益。
首先,我们看什么是熵。简单来说,熵是描述事物的混乱程度的(也可以说是不确定性)。例如:中国足球进入世界杯,这个不确定性可能是0,所以熵可能就是0;6面的色子的不确定性比12面色子的要低,所以熵也会比其低。现在就来看熵的公式:H = -∑<sup>n</sup><sub>i=1</sub>p(xi)log<sub>2</sub>p(xi)
那6面色子的熵:1/6*log<sub>2</sub>1/6的6倍,也就是2.585
以此类推,那12面的熵就是:3.585
最后,我们计算下该案例的信息熵:不打球为5,打球为9,因此熵计算为:
-(5/14 * log(5/14,2) + 9/14 * log(9/14,2))
0.940
到底先按哪个特征划分数据集呢?我们有个原则,就是将无序的数据变得有序,换句话说,就是让熵变小,变的越小越好。而信息增益就是划分数据集前后熵的变化,这里就是要让信息增益越大越好。
我们以天气为例,计算划分后的信息增益:
数据为判断是否为鱼类,有两个特征:
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
这里有两个终止递归的条件:一是所有类别能正确的划分了,二是特征使用完成。
原创声明:本文系作者授权腾讯云开发者社区发表,未经许可,不得转载。
如有侵权,请联系 cloudcommunity@tencent.com 删除。
原创声明:本文系作者授权腾讯云开发者社区发表,未经许可,不得转载。
如有侵权,请联系 cloudcommunity@tencent.com 删除。