《机器学习实战》(笔记)— 理解和实现决策树

作者:杨润炜
日期:2018/2/21 22:22

决策树

学习内容

  • 1.了解信息增益
  • 2.理解决策树原理
  • 3.决策树的简单实现

我的理解

  • 信息增益是信息论中的熵,表示信息的期望值。
    类别C是变量,它可能的取值是C1,C2,……,Cn,而每一个类别出现的概率是P(C1),P(C2),……,P(Cn),因此n就是类别的总数。此时分类系统的熵就可以表示为:

  • 决策树结构类似于数据结构里的二叉树,通常用来做一些分类任务,样本输入后,经过分支到达叶子节点,该节点代表的分类就是样本数据的识别类别。训练就是构造决策树的过程,节点是由特征来决定的,而特征选用的顺序需要由信息增益(即信息论中的熵)来决定,哪个特征能使信息增益增大(即熵值减小),就先使用该特征作为分支条件,这样递归下去就得到了整棵决策树。

  • 创建数据集:每个样本都是一个三维数组,前两维分别表示两种特征的数值,最后一个元素表示此样本所属类别。代码略。
    计算数据集的信息熵:

    1. def calcShannonEnt(dataSet):
    2. # 数据集总样本数量
    3. numEntries = len(dataSet)
    4. # 计算数据集里各个类别的样本数量
    5. labelCounts = {}
    6. for featVec in dataSet:
    7. currentLabel = featVec[-1]
    8. if currentLabel not in labelCounts.keys(): labelCounts[currentLabel] = 0
    9. labelCounts[currentLabel] += 1
    10. shannonEnt = 0.0
    11. # 根据公式计算些数据集的信息熵
    12. for key in labelCounts:
    13. prob = float(labelCounts[key])/numEntries
    14. shannonEnt -= prob * log(prob,2)
    15. return shannonEnt

    划分节点的数据集:

    1. def splitDataSet(dataSet, axis, value):
    2. retDataSet = []
    3. # 遍历父数据集,找出axis对应的分类value数据,返回新的子节点数据集
    4. for featVec in dataSet:
    5. if featVec[axis] == value:
    6. reducedFeatVec = featVec[:axis]
    7. reducedFeatVec.extend(featVec[axis+1:])
    8. retDataSet.append(reducedFeatVec)
    9. return retDataSet

    选择最好的数据集划分方式:

    1. def chooseBestFeatureToSplit(dataSet):
    2. # 计算数据集的特征数量
    3. numFeatures = len(dataSet[0]) - 1
    4. # 计算数据集的信息熵
    5. baseEntropy = calcShannonEnt(dataSet)
    6. bestInfoGain = 0.0; bestFeature = -1
    7. for i in range(numFeatures):
    8. # 创建具有某特征的值列表,且去重
    9. featList = [example[i] for example in dataSet]
    10. uniqueVals = set(featList)
    11. newEntropy = 0.0
    12. for value in uniqueVals:
    13. # 划分特征节点的数据集
    14. subDataSet = splitDataSet(dataSet, i, value)
    15. # 计算此特征节点数据集的信息熵
    16. prob = len(subDataSet)/float(len(dataSet))
    17. newEntropy += prob * calcShannonEnt(subDataSet)
    18. infoGain = baseEntropy - newEntropy
    19. # 拿到最小的信息熵,并记录该特征
    20. if (infoGain > bestInfoGain):
    21. bestInfoGain = infoGain
    22. bestFeature = i
    23. # 返回能使数据集信息熵最小的特征
    24. return bestFeature

    递归构建决策树:

    1. def createTree(dataSet,labels):
    2. classList = [example[-1] for example in dataSet]
    3. # 类别完全相同则直接返回该类别
    4. if classList.count(classList[0]) == len(classList):
    5. return classList[0]
    6. # 遍历完所有特征时返回出现次数最多的类别
    7. if len(dataSet[0]) == 1:
    8. return majorityCnt(classList)
    9. # 获取最佳节点特征并赋给决策树节点
    10. bestFeat = chooseBestFeatureToSplit(dataSet)
    11. bestFeatLabel = labels[bestFeat]
    12. myTree = {bestFeatLabel:{}}
    13. del(labels[bestFeat])
    14. # 得到列表包含的所有特征值,并进行递归构建决策树
    15. featValues = [example[bestFeat] for example in dataSet]
    16. uniqueVals = set(featValues)
    17. for value in uniqueVals:
    18. subLabels = labels[:]
    19. myTree[bestFeatLabel][value] = createTree(splitDataSet(dataSet, bestFeat, value),subLabels)
    20. return myTree

    运行结果:

    1. >>> import trees
    2. >>> myDat, labels = trees.createDataSet()
    3. >>> myTree = trees.createTree(myDat, labels)
    4. >>> myTree
    5. {'no surfacing': {0: 'no', 1: {'flippers': {0: 'no', 1: 'yes'}}}}

    完整代码请查看:决策树的实现

    意义

    了解了信息熵的定义和计算公式,对机器学习的分类算法决策树有了一定的理解。

感谢您的阅读!
如果看完后有任何疑问,欢迎拍砖。
欢迎转载,转载请注明出处:http://www.yangrunwei.com/a/94.html
邮箱:glowrypauky@gmail.com
QQ: 892413924