机器学习-决策树-ID3决策树

原理看上一篇，这篇只有代码实现

它以信息熵为度量标准，划分出决策树特征节点，每次优先选取信息量最多的属性，也就是使信息熵变为最小的属性，以构造一颗信息熵下降最快的决策树。

缺点

ID3算法的节点划分度量标准采用的是信息增益，信息增益偏向于选择特征值个数较多的特征。而取值个数较多的特征并不一定是最优的特征，所以需要改进选择属性的节点划分度量标准

ID3算法递归过程中需要依次计算每个特征值，对于大型数据会生成比较复杂的决策树：层次和分支都很多，而其中某些分支的特征值概率很小，如果不加忽略就会造成过拟合的问题。即决策树对样本数据的分类精度较高，但在测试集上，分类的结果受决策树分支的影响很大。

代码

from numpy import *
import math
import copy
import pickle

# ID3决策树的实现
class ID3DTree(object):
    def __init__(self): # 构造方法
        self.tree = {}  # 生成的树
        self.dataSet = []   # 数据集
        self.labels = []    # 标签集

    # 数据导入函数
    def loadDataSet(self, path, labels):
        recordlist = []
        fp = open(path, "r")   # 读取文件内容
        content = fp.read()
        fp.close()
        rowlist = content.splitlines()  # 按行转换为一维表
        recordlist = [row.split("\t") for row in rowlist if row.strip()]
        self.dataSet = recordlist
        self.labels = labels

    # 执行决策树函数
    def train(self):
        labels = copy.deepcopy(self.labels)
        self.tree = self.buildTree(self.dataSet, labels)

    # 创建决策树主程序
    def buildTree(self, dataSet, labels):
        cateList = [data[-1] for data in dataSet]   # 抽取源数据集的决策标签列
        # 程序终止条件1：如果classList只有一种决策标签，停止划分，返回这个决策标签
        if cateList.count(cateList[0]) == len(cateList):
            return cateList[0]
        # 程序终止条件2：如果数据集的第一个决策标签只有一个，则返回这个决策标签
        if len(dataSet[0]) == 1:
            return self.maxCate(cateList)
        # 算法核心：
        bestFeat = self.getBestFeat(dataSet)    # 返回数据集的最优特征轴
        bestFeatLabel = labels[bestFeat]
        tree = {bestFeatLabel:{}}
        del(labels[bestFeat])
        #抽取最优特征轴的列向量
        uniqueVals = set([data[bestFeat] for data in dataSet])  #去重
        for value in uniqueVals:    # 决策树递归生长
            subLabels = labels[:]   # 将删除后的特征类别集建立子类别集
            # 按最优特征列和值分隔数据集
            splitDataset = self.splitDataSet(dataSet, bestFeat, value)
            subTree = self.buildTree(splitDataset, subLabels)   # 构建子树
            tree[bestFeatLabel][value] = subTree
        return tree

    # 计算出现次数最多的类别标签
    def maxCate(self, catelist):
        items = dict([(catelist.count(i), i) for i in catelist])
        return items[max(items.keys())]

    # 计算最优特征
    def getBestFeat(self, dataSet):
        # 计算特征向量维，其中最后一列用于类别标签，因此要减去
        numFeatures = len(dataSet[0]) - 1   # 特征向量维数=行向量维度-1
        baseEntropy = self.computeEntropy(dataSet)  # 基础熵：源数据的香农熵
        bestInfoGain = 0.0  # 初始化最优的信息增益
        bestFeature = -1    # 初始化最优的特征轴
        # 外循环：遍历数据集各列，计算最优特征轴
        # i 为数据集列索引：取值范围 0-（numFeatures-1）
        for i in range(numFeatures):    # 抽取第i列的列向量
            uniqueVals = set([data[i] for data in dataSet]) # 去重：该列的唯一值集
            newEntropy = 0.0    # 初始化该列的香农熵
            for value in uniqueVals:    # 内循环：按列和唯一值计算香农熵
                # 按选定列i和唯一值分隔数据集
                subDataSet = self.splitDataSet(dataSet, i, value)
                prob = len(subDataSet) / float(len(dataSet))    # 即类别发生的概率
                newEntropy += prob * self.computeEntropy(subDataSet)    # 子集信息熵或期望=类别子集发生的概率 * 信息熵
            infoGain = baseEntropy - newEntropy # 计算最大增益
            if (infoGain > bestInfoGain):   # 如果信息增益>0
                bestInfoGain = infoGain     # 用当前信息增益值替代之前的最优增益值
                bestFeature = i             # 重置最优特征为当前列
        return bestFeature

    # 计算信息熵
    def computeEntropy(self, dataSet):
        datalen = float(len(dataSet))
        cateList = [data[-1] for data in dataSet]   # 从数据集中得到类别标签
        # 得到类别为key、出现次数value的字典
        items = dict([(i, cateList.count(i)) for i in cateList])
        infoEntropy = 0.0   # 初始化香农熵
        for key in items:   # 香农熵：
            prob = float(items[key]) / datalen
            infoEntropy -= prob * math.log(prob, 2)
        return infoEntropy

    # 划分数据集；分隔数据集；删除特征轴所在的数据列，返回剩余的数据集
    # dataSet:数据集   axis：特征轴    value:特征轴的取值
    def splitDataSet(self, dataSet, axis, value):
        rtnList = []
        for featVec in dataSet:
            if featVec[axis] == value:
                rFeatVec = featVec[:axis]   # list操作：提取0~(axis-1)的元素
                rFeatVec.extend(featVec[axis+1:])   # list操作：将特征轴（列）之后的元素加回
                rtnList.append(rFeatVec)
        return rtnList

    # 分类
    def predict(self, inputTree, featLabels, testVec):
        root = list(inputTree.keys())[0]  # 树根节点
        secondDict = inputTree[root]    # value-子树结构或分类标签
        featIndex = featLabels.index(root) # 根节点在分类标签集中的位置
        key = testVec[featIndex]    # 测试集数组取值
        valueOfFeat = secondDict[key]
        if isinstance(valueOfFeat, dict):
            classLabel = self.predict(valueOfFeat, featLabels, testVec) #递归分类
        else: classLabel = valueOfFeat
        return classLabel

    # 持久化
    def storeTree(self, inputTree, filename):
        fw = open(filename, 'wb')
        pickle.dump(inputTree, fw)
        fw.close()

    # 从文件抓取树
    def grabTree(self, filename):
        fr = open(filename,'rb')
        return pickle.load(fr)


#训练
dtree = ID3DTree()
dtree.loadDataSet("/Users/FengZhen/Desktop/accumulate/机器学习/决策树/决策树训练集.txt", ["age", "revenue", "student", "credit"])
dtree.train()
print(dtree.tree)

#持久化
# dtree.storeTree(dtree.tree, "/Users/FengZhen/Desktop/accumulate/机器学习/决策树/决策树.tree")
mytree = dtree.grabTree("/Users/FengZhen/Desktop/accumulate/机器学习/决策树/决策树.tree")
print(mytree)

#测试
labels = ["age", "revenue", "student", "credit"]
vector = ['0','1','0','0']
print(dtree.predict(mytree, labels, vector))