#!/usr/bin/env python
# -*- coding: utf-8 -*-
__author__ = 'qibin'

from math import log
import time

def createDataSet():
    dataSet = [[1, 1, 'yes'],
               [1, 1, 'yes'],
               [1, 0, 'no'],
               [0, 1, 'no'],
               [0, 1, 'no']
    ]
    label = ['no surfacing', 'flippers']
    return dataSet, label

def calcShangnonEnt(dataSet):
    numEntries = len(dataSet)
    labelCounts = {}
    for featVec in dataSet:
        currentLabel = featVec[-1]
        if currentLabel not in labelCounts.keys():
            labelCounts[currentLabel] = 0
        labelCounts[currentLabel] += 1
    shannonEnt = 0.0
    for key in labelCounts:
        prob =float(labelCounts[key])/numEntries
        shannonEnt -= prob * log(prob, 2)
    return shannonEnt

def splitDataSet(dataSet, axis, value):
    retDataSet = []
    for featVec in dataSet:
        if featVec[axis] == value:
            reducedFeatVec = featVec[:axis]
            reducedFeatVec.extend(featVec[axis+1:])
            retDataSet.append(reducedFeatVec)
    return retDataSet

def chooseBestFeatureToSplit(dataSet):
    numFeatures = len(dataSet[0]) - 1
    baseEntropy = calcShangnonEnt(dataSet)
    bestInfoGain = 0.0
    bestFeature = -1
    for i in range(numFeatures):
        featList = [example[i] for example in dataSet]
        uniqueVals = set(featList)
        newEntropy = 0.0
        for value in uniqueVals:
            subDataSet = splitDataSet(dataSet, i , value)
            prob = len(subDataSet)/float(len(dataSet))
            newEntropy += prob * calcShangnonEnt(subDataSet)
        infoGain = baseEntropy - newEntropy
        if (infoGain > baseEntropy):
            bestInfoGain = infoGain
            bestFeature = i
    return bestFeature

def majorityCnt(classList):
    classCount= {}
    for vote in  classList:
        if vote not in classCount.keys():
            classCount[vote]  = 0
        classCount[vote] +=1
    return max(classCount)

def createTree(dataSet, labels):
    classList = [example[-1] for example in dataSet]
    if classList.count(classList[0]) == len(classList):
        return classList[0]
    if len(dataSet[0]) == 1:
        return majorityCnt(classList)
    bestFeat = chooseBestFeatureToSplit(dataSet)
    bestFeatLabel = labels[bestFeat]
    myTree = {bestFeatLabel:{}}
    del(labels[bestFeat])
    featValues = [example[bestFeat] for example in dataSet]
    uniqueVales = set(featValues)
    for value in uniqueVales:
        subLabels = labels[:]
        myTree[bestFeatLabel][value] = createTree(splitDataSet(dataSet, bestFeat, value),subLabels)
    return myTree

def classify(inputTree,featLabels,testVec):
    """
    :param inputTree: 是输入的决策树对象
    :param featLabels:我们要预测的特征值的label
    :param testVec:是要预测的特征值向量
    :return:
    """
    #存储决策树第一个节点
    firstStr = inputTree.keys()[0]
    #将第一个节点的值存到secondDict字典中
    secondDict = inputTree[firstStr]
    #建立索引，知道对应到第几种特征值
    featIndex = featLabels.index(firstStr)
    key = testVec[featIndex]
    valueOfFeat = secondDict[key]
    #对比，判断当前的键值是否是一个dict类型，如果是就递归，不是就输出当前键值为结果
    if isinstance(valueOfFeat, dict):
        classLabel = classify(valueOfFeat, featLabels, testVec)
    else: classLabel = valueOfFeat
    return classLabel


def main():
    data, label = createDataSet()
    t1 = time.clock()
    myTree = createTree(data, label)
    t2 = time.clock()
    print myTree
    print 'execte for', t2 - t1



if __name__ == '__main__':
    main()


