python实现ID3决策树算法-创新互联
ID3决策树是以信息增益作为决策标准的一种贪心决策树算法
成都创新互联专注于岭东企业网站建设,响应式网站开发,购物商城网站建设。岭东网站建设公司,为岭东等地区提供建站服务。全流程定制制作,专业设计,全程项目跟踪,成都创新互联专业和态度为您提供的服务# -*- coding: utf-8 -*- from numpy import * import math import copy import cPickle as pickle class ID3DTree(object): def __init__(self): # 构造方法 self.tree = {} # 生成树 self.dataSet = [] # 数据集 self.labels = [] # 标签集 # 数据导入函数 def loadDataSet(self, path, labels): recordList = [] fp = open(path, "rb") # 读取文件内容 content = fp.read() fp.close() rowList = content.splitlines() # 按行转换为一维表 recordList = [row.split("\t") for row in rowList if row.strip()] # strip()函数删除空格、Tab等 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, lables): 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 = lables[bestFeat] tree = {bestFeatLabel: {}} del (lables[bestFeat]) # 抽取最优特征轴的列向量 uniqueVals = set([data[bestFeat] for data in dataSet]) # 去重 for value in uniqueVals: # 决策树递归生长 subLables = lables[:] # 将删除后的特征类别集建立子类别集 # 按最优特征列和值分隔数据集 splitDataset = self.splitDataSet(dataSet, bestFeat, value) subTree = self.buildTree(splitDataset, subLables) # 构建子树 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 xrange(numFeatures): uniqueVals = set([data[i] for data in dataSet]) # 去重 newEntropy = 0.0 for value in uniqueVals: 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 # 计算信息熵 # @staticmethod 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: # 香农熵: = -p*log2(p) --infoEntropy = -prob * log(prob, 2) 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:]) rtnList.append(rFeatVec) return rtnList # 存取树到文件 def storetree(self, inputTree, filename): fw = open(filename,'w') pickle.dump(inputTree, fw) fw.close() # 从文件抓取树 def grabTree(self, filename): fr = open(filename) return pickle.load(fr)
当前名称:python实现ID3决策树算法-创新互联
网站URL:http://scyanting.com/article/jehee.html