机器学习-决策树-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(" ") 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))