ID3決策樹是以信息增益作為決策標準的一種貪心決策樹算法

# -*- coding: utf-8 -*-from numpy import *import mathimport copyimport cPickle as pickleclass 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)