# -*- 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