机器学习实战之决策树

2018-08-10 15:15:11 浏览数 (1)

-- Illustrations by Cornelius Bierer --

决策树的算法可谓是贴近我们的生活，通过下面的案例，你就会发现我们每天都在有意无意的使用着决策树算法（好厉害的样子）。

小明同学每天早上都要去学校，可步行、乘公交和坐隔壁老王叔叔的车（皮一下很开心）。这时，小明就开始做决策了：首先看天气，不下雨时就选择步行去学校；下雨时就看隔壁老王叔叔是否有空，有空就乘老王的车去学校，没空就选择乘公交去学校。如图所示。

案例

决策树定义

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

决策树算法原理

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

案例

熵

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

  1. -(5/14 * log(5/14,2) 9/14 * log(9/14,2))
  2. 0.940

信息增益

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

  • 晴天时：2/5打球，3/5不打球，熵为：
  1. -(2/5 * log(2/5,2) 3/5 * log(3/5,2))
  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，同理可以求出其他特征的信息增益。

这里的天气信息增益最大，所以选择其为初始的划分依据。

选择完天气做为第一个划分依据后，能够正确分类的就结束划分，不能够正确分类的就继续算其余特征的信息增益，继续前面的操作，结果如图所示。

结果

伪代码

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

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

决策树之海洋生物分类

问题描述与数据

数据为判断是否为鱼类，有两个特征：

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

案例

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

  1. def creatDataSet():
  2. dataSet = [
  3. [1, 1, 'yes'],
  4. [1, 1, 'yes'],
  5. [1, 0, 'no'],
  6. [0, 1, 'no'],
  7. [0, 1, 'no']
  8. ]
  9. labels = ['no surfacing', 'flippers']
  10. return dataSet, labels

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

计算熵

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

  1. from math import log
  3. def calcshannon(dataSet):
  4. num = len(dataSet)
  5. labelCounts = {}
  6. for featVec in dataSet:
  7. currentLabel = featVec[-1]
  8. if currentLabel not in labelCounts.keys():
  9. labelCounts[currentLabel] = 0
  10. labelCounts[currentLabel] = 1
  11. shannon = 0.0
  12. for key in labelCounts:
  13. prob = float(labelCounts[key])/num
  14. shannon -= prob * log(prob, 2)
  15. return shannon

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

划分数据集

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

  1. def splitDataSet(dataSet, axis, value):
  2. retDataSet = []
  3. for featVec in dataSet:
  4. if featVec[axis] == value:
  5. reduce = featVec[:axis]
  6. reduce.extend(featVec[axis 1:])
  7. retDataSet.append(reduce)
  8. return retDataSet
  9. def choose(dataSet):
  10. numfeature = len(dataSet[0]) - 1
  11. baseEntropy = calcshannon(dataSet)
  12. bestinfogain = 0.0
  13. bestfeature = -1
  14. for i in range(numfeature):
  15. featlist = [example[i] for example in dataSet]
  16. vals = set(featlist)
  17. newEntropy = 0.0
  18. for value in vals:
  19. subDataSet = splitDataSet(dataSet, i, value)
  20. prob = len(subDataSet)/float(len(dataSet))
  21. newEntropy = prob*calcshannon(subDataSet)
  22. infoGain = baseEntropy - newEntropy
  23. if (infoGain > bestinfogain):
  24. bestinfogain = infoGain
  25. bestfeature = i
  26. return bestfeature

创建树

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

  1. import operator
  2. def majority(classList):
  3. classCount = {}
  4. for vote in classList:
  5. if vote not in classCount.keys():
  6. classCount[vote] = 0
  7. classCount[vote] = 1
  8. sortedcount = sorted(classCount.items(), key=operator.itemgetter(1), reverse=True)
  9. return sortedcount[0][0]

最后就是创建树的代码：

  1. def createTree(dataSet, labels):
  2. classList = [example[-1] for example in dataSet]
  3. if classList.count(classList[0]) == len(classList):
  4. return classList[0]
  5. if len(dataSet[0]) == 1:
  6. return majority(classList)
  7. bestFeat = choose(dataSet)
  8. bestFeatLabel = labels[bestFeat]
  9. myTree = {bestFeatLabel:{}}
  10. del (labels[bestFeat])
  11. Vals = [example[bestFeat] for example in dataSet]
  12. uvals = set(Vals)
  13. for value in uvals:
  14. sublabels = labels[:]
  15. myTree[bestFeatLabel][value] = createTree(splitDataSet(dataSet, bestFeat, value), sublabels)
  16. return myTree

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

结果

算法优缺点

  • 优点：利于理解
  • 缺点：容易过拟合
机器学习 决策树 编程算法

0 人点赞