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)

调用代码

# -*- coding: utf-8 -*-

from numpy import *
from ID3DTree import *

dtree = ID3DTree()
# ["age", "revenue", "student", "credit"]对应年龄、收入、学生、信誉4个特征
dtree.loadDataSet("dataset.dat", ["age", "revenue", "student", "credit"])
dtree.train()

dtree.storetree(dtree.tree, "data.tree")
mytree = dtree.grabTree("data.tree")
print mytree

来源：https://blog.csdn.net/yjIvan/article/details/71194383