大数据，机器学习，人工智能人工智能/模式识别/机器学习精华专题机器学习和人工智能入门

决策树

2019-05-12  本文已影响3人  山雾幻华

决策树

正方形代表判断模块（decision block），椭圆形代表终止模块（terminating block），表示已经得出结论，可以终止运行。从判断模块引出的左右箭头称作分支（branch），它可以到达另一个判断模块或者终止模块。

决策树的主要优势就在于数据形式非常容易理解。

检测数据集中的每个子项是否属于同一分类：
If so return 类标签；
Else
    寻找划分数据集的最好特征
    划分数据集
    创建分支节点
        for每个划分的子集
            调用函数createBranch并增加返回结果到分支节点中
    return分支节点

划分数据集的大原则是将无序的数据变得更加有序。

- C4.5
    (a)以基于信息增益的增益率（gain ratio）作为树的分裂准则，解决了ID3的偏向于多值属性问题
    (b)内部自己考虑了连续属性离散化过程，所以克服了ID3的没有考虑连续特征问题
    (c)内部考虑了缺失值的自动处理策略
    - 信息增益比
        特征$A$对训练数据集$D$的信息增益比$g_{R}(D, A)$定义为其信息增益$g(D, A)$与训练数据集D的经验熵$H(D)$之比：
        $$g_{R}(D, A)=\frac{g(D, A)}{H(D)}$$
    - 算法
        - 输入：训练数据集$D$，特征集$A$，阀值$\varepsilon$；
        - 输出：决策树T.
        - （1）若$D$中所有实例属于同一类$C_{k}$，则$T$为单结点树，并将类$C_{k}$作为该结点的类标记，返回$T$；
        - （2）若$A=\varnothing$，则$T$为单结点树，并将$D$中实例数最大的类$C_{k}$作为该结点的类标记，返回$T$；
        - （3）否则，按式\ref{equ:5_10}计算$A$中各特征对$D$的信息增益，选择信息增益最大的特征$A_{\mathrm{g}}$；
        - （4）如果$A_{\mathrm{g}}$的信息增益比小于阈值$\varepsilon$，则置$T$为单结点树，并将$D$中实例数最大的类$C_{k}$作为该结点的类标记，返回$T$；
        - （5）否则，对$A_{\mathrm{g}}$的每一可能值$a_{i}$，依$A_{g}=a_{i}$将$D$分割为若干非空子集$D_{i}$，将$D_{i}$中实例数最大的类作为标记，构建子结点，由结点及其子结点构成树$T$，返回$T$；
        - （6）对第$i$个子结点，以$D_{i}$为训练集，以$A-\left\{A_{g}\right\}$为特征集，递归地调用步（1）～步（5），得到子树$T_{i}$，返回$T_{i}$.
- CART
    ID3和C4.5只能处理分类问题，而CART可以处理分类和回归问题，CART考虑问题非常全面，有较多优点，可以自行深入研究

from math import log
import operator
def calcShannonEnt(dataSet):
    """
    计算给定数据集的经验熵(香农熵)
    params dataSet:数据集，要求列表类型，每行长度相同，最后一列为label
    returns shannonEnt:熵
    """
    numEntires = len(dataSet)                        #返回数据集的行数
    labelCounts = {}                                #保存每个标签(Label)出现次数的字典
    for featVec in dataSet:                            #对每组特征向量进行统计
        currentLabel = featVec[-1]                    #提取标签(Label)信息
        if currentLabel not in labelCounts.keys():    #如果标签(Label)没有放入统计次数的字典,添加进去
            labelCounts[currentLabel] = 0
        labelCounts[currentLabel] += 1                #Label计数
    shannonEnt = 0.0                                #经验熵(香农熵)
    for key in labelCounts:                            #计算香农熵
        prob = float(labelCounts[key]) / numEntires    #选择该标签(Label)的概率
        shannonEnt -= prob * log(prob, 2)            #利用公式计算
    return shannonEnt 
def splitDataSet(dataSet, axis, value): 
    """
    按照给定特征划分数据集
    params dataSet:数据集
    params axis:划分数据集的特征,第几列的特征
    params value:需要返回的特征的值
    returns retDataSet:返回划分后的数据集
    """      
    retDataSet = []                                        #创建返回的数据集列表
    for featVec in dataSet:                             #遍历数据集
        if featVec[axis] == value:
            reducedFeatVec = featVec[:axis]                #去掉axis特征
            reducedFeatVec.extend(featVec[axis+1:])     #将符合条件的添加到返回的数据集
            retDataSet.append(reducedFeatVec)
    return retDataSet                                      #返回划分后的数据集

def chooseBestFeatureToSplit(dataSet):
    """
    选择最优特征
    params dataSet:数据集
    returns bestFeature:信息增益最大的(最优)特征的索引值
    """
    numFeatures = len(dataSet[0]) - 1                    #特征数量
    baseEntropy = calcShannonEnt(dataSet)                 #计算数据集的香农熵
    bestInfoGain = 0.0                                  #信息增益
    bestFeature = -1                                    #最优特征的索引值
    for i in range(numFeatures):                         #遍历所有特征
        #获取dataSet的第i个所有特征
        featList = [example[i] for example in dataSet]
        uniqueVals = set(featList)                         #创建set集合{},元素不可重复
        newEntropy = 0.0                                  #经验条件熵
        for value in uniqueVals:                         #计算信息增益
            subDataSet = splitDataSet(dataSet, i, value)         #subDataSet划分后的子集
            prob = len(subDataSet) / float(len(dataSet))           #计算子集的概率
            newEntropy += prob * calcShannonEnt(subDataSet)     #根据公式计算经验条件熵
        infoGain = baseEntropy - newEntropy                     #信息增益
        # print("第%d个特征的增益为%.3f" % (i, infoGain))            #打印每个特征的信息增益
        if (infoGain > bestInfoGain):                             #计算信息增益
            bestInfoGain = infoGain                             #更新信息增益，找到最大的信息增益
            bestFeature = i                                     #记录信息增益最大的特征的索引值
    return bestFeature                                             #返回信息增益最大的特征的索引值

def majorityCnt(classList):
    """
    params classList:类标签列表
    returns sortedClassCount[0][0]:出现此处最多的元素(类标签)
    """
    classCount = {}
    for vote in classList:                                        #统计classList中每个元素出现的次数
        if vote not in classCount.keys():classCount[vote] = 0   
        classCount[vote] += 1
    sortedClassCount = sorted(classCount.items(), key = operator.itemgetter(1), reverse = True)        #根据字典的值降序排序
    return sortedClassCount[0][0]                                #返回classList中出现次数最多的元素


def createTree(dataSet, labels, featLabels):
    """
    params dataSet:训练数据集
    params labels:分类属性标签
    params featLabels:存储选择的最优特征标签
    returns myTree:决策树
    """
    classList = [example[-1] for example in dataSet]            #取分类标签(是否放贷:yes or no)
    if classList.count(classList[0]) == len(classList):            #如果类别完全相同则停止继续划分
        return classList[0]
    if len(dataSet[0]) == 1:                                    #遍历完所有特征时返回出现次数最多的类标签
        return majorityCnt(classList)
    bestFeat = chooseBestFeatureToSplit(dataSet)                #选择最优特征
    bestFeatLabel = labels[bestFeat]                            #最优特征的标签
    featLabels.append(bestFeatLabel)
    myTree = {bestFeatLabel:{}}                                    #根据最优特征的标签生成树
    del(labels[bestFeat])                                        #删除已经使用特征标签
    featValues = [example[bestFeat] for example in dataSet]        #得到训练集中所有最优特征的属性值
    uniqueVals = set(featValues)                                #去掉重复的属性值
    for value in uniqueVals:                                    #遍历特征，创建决策树。                       
        myTree[bestFeatLabel][value] = createTree(splitDataSet(dataSet, bestFeat, value), labels, featLabels)
    return myTree
if __name__ == '__main__':
    dataSet, labels = createDataSet()
    featLabels = []
    myTree = createTree(dataSet, labels, featLabels)
    print(myTree)


# 存储
import pickle
def storeTree(inputTree, filename):
    """
    params inputTree:已经生成的决策树
    params filename:决策树的存储文件名
    """
    with open(filename, 'wb') as fw:
        pickle.dump(inputTree, fw)

# 载入
def grabTree(filename):
    """
    params filename:决策树的存储文件名
    returns pickle.load(fr):决策树字典
    """
    fr = open(filename, 'rb')
    return pickle.load(fr)

参考

[1]作者：Jack-Cui
来源：CSDN
原文：https://blog.csdn.net/c406495762/article/details/76262487
版权声明：本文为博主原创文章，转载请附上博文链接！
[2]机器学习实战
[3]统计学习方法

上一篇 下一篇

猜你喜欢

热点阅读