cart（决策分类树）原理和实现

human    constant    hair    true    false    false    false    true    false    mammal
python    cold_blood    scale    false    true    false    false    false    true    reptile
salmon    cold_blood    scale    false    true    false    true    false    false    fish
whale    constant    hair    true    false    false    true    false    false    mammal
frog    cold_blood    none    false    true    false    sometime    true    true    amphibious
lizard    cold_blood    scale    false    true    false    false    true    false    reptile
bat    constant    hair    true    false    true    false    true    false    mammal
cat    constant    skin    true    false    false    false    true    false    mammal
shark    cold_blood    scale    true    false    false    true    false    false    fish
turtle    cold_blood    scale    false    true    false    sometime    true    false    reptile
pig    constant    bristle    true    false    false    false    true    true    mammal
eel    cold_blood    scale    false    true    false    true    false    false    fish
salamander    cold_blood    none    false    true    false    sometime    true    true    amphibious

["temperature","cover","viviparity","egg","fly","water","leg","hibernate"]

def calGini(dataSet):
    numEntries = len(dataSet)
    labelCounts={}
    for featVec in dataSet: 
        currentLabel = featVec[-1]
        if currentLabel not in labelCounts.keys(): labelCounts[currentLabel] = 0
        labelCounts[currentLabel] += 1
    gini=1
    for label in labelCounts.keys():
        prop=float(labelCounts[label])/numEntries
        gini -=prop*prop
    return gini

# 传入的是一个特征值的列表，返回特征值二分的结果
def featuresplit(features):
    count = len(features)#特征值的个数
    if count < 2:
        print "please check sample's features,only one feature value"
        return -1
    # 由于需要返回二分结果，所以每个分支至少需要一个特征值，所以要从所有的特征组合中选取1个以上的组合
    # itertools的combinations 函数可以返回一个列表选多少个元素的组合结果，例如combinations(list,2)返回的列表元素选2个的组合
    # 我们需要选择1-（count-1）的组合
    featureIndex = range(count)
    featureIndex.pop(0) 
    combinationsList = []    
    resList=[]
    # 遍历所有的组合
    for i in featureIndex:
        temp_combination = list(combinations(features, len(features[0:i])))
        combinationsList.extend(temp_combination)
        combiLen = len(combinationsList)
    # 每次组合的顺序都是一致的，并且也是对称的，所以我们取首尾组合集合
    # zip函数提供了两个列表对应位置组合的功能
    resList = zip(combinationsList[0:combiLen/2], combinationsList[combiLen-1:combiLen/2-1:-1])
    return resList

def splitDataSet(dataSet, axis, values):
    retDataSet = []
    for featVec in dataSet:
        for value in values:
            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      #
    bestGiniGain = 1.0; bestFeature = -1;bestBinarySplit=()
    for i in range(numFeatures):        #遍历特征
        featList = [example[i] for example in dataSet]#得到特征列
        uniqueVals = list(set(featList))       #从特征列获取该特征的特征值的set集合
        # 三个特征值的二分结果：
        # [(('young',), ('old', 'middle')), (('old',), ('young', 'middle')), (('middle',), ('young', 'old'))]
        for split in featuresplit(uniqueVals):
            GiniGain = 0.0
            if len(split)==1:
                continue
            (left,right)=split
            # 对于每一个可能的二分结果计算gini增益
            # 左增益
            left_subDataSet = splitDataSet(dataSet, i, left)
            left_prob = len(left_subDataSet)/float(len(dataSet))
            GiniGain += left_prob * calGini(left_subDataSet)
            # 右增益
            right_subDataSet = splitDataSet(dataSet, i, right)
            right_prob = len(right_subDataSet)/float(len(dataSet))
            GiniGain += right_prob * calGini(right_subDataSet)
            if (GiniGain <= bestGiniGain):       #比较是否是最好的结果
                bestGiniGain = GiniGain         #记录最好的结果和最好的特征
                bestFeature = i
                bestBinarySplit=(left,right)
    return bestFeature,bestBinarySplit    

def majorityCnt(classList):
    classCount={}
    for vote in classList:
        if vote not in classCount.keys(): classCount[vote] = 0
        classCount[vote] += 1
    sortedClassCount = sorted(classCount.iteritems(), key=operator.itemgetter(1), reverse=True)
    return sortedClassCount[0][0]

def createTree(dataSet,labels):
    classList = [example[-1] for example in dataSet]
    # print dataSet
    if classList.count(classList[0]) == len(classList): 
        return classList[0]#所有的类别都一样，就不用再划分了
    if len(dataSet) == 1: #如果没有继续可以划分的特征，就多数表决决定分支的类别
        # print "here"
        return majorityCnt(classList)
    bestFeat,bestBinarySplit = chooseBestFeatureToSplit(dataSet)
    # print bestFeat,bestBinarySplit,labels
    bestFeatLabel = labels[bestFeat]
    if bestFeat==-1:
        return majorityCnt(classList)
    myTree = {bestFeatLabel:{}}
    featValues = [example[bestFeat] for example in dataSet]
    uniqueVals = list(set(featValues))
    for value in bestBinarySplit:
        subLabels = labels[:]       # #拷贝防止其他地方修改
        if len(value)<2:
            del(subLabels[bestFeat])
        myTree[bestFeatLabel][value] = createTree(splitDataSet(dataSet, bestFeat, value),subLabels)
    return myTree 

def splitDataSet(dataSet, axis, values):
    retDataSet = []
    if len(values) < 2:
        for featVec in dataSet:
            if featVec[axis] == values[0]:#如果特征值只有一个，不抽取当选特征
                reducedFeatVec = featVec[:axis]     
                reducedFeatVec.extend(featVec[axis+1:])
                retDataSet.append(reducedFeatVec)
    else:
        for featVec in dataSet:
            for value in values:
                if featVec[axis] == value:#如果特征值多于一个，选取当前特征
                    retDataSet.append(featVec)

    return retDataSet

    for value in bestBinarySplit:
        if len(value)<2:
            del(labels[bestFeat])
        subLabels = labels[:]       #拷贝防止其他地方修改
        myTree[bestFeatLabel][value] = createTree(splitDataSet(dataSet, bestFeat, value),subLabels)

sunny    hot    high    FALSE    no
sunny    hot    high    TRUE    no
overcast    hot    high    FALSE    yes
rainy    mild    high    FALSE    yes
rainy    cool    normal    FALSE    yes
rainy    cool    normal    TRUE    no
overcast    cool    normal    TRUE    yes
sunny    mild    high    FALSE    no
sunny    cool    normal    FALSE    yes
rainy    mild    normal    FALSE    yes
sunny    mild    normal    TRUE    yes
overcast    mild    high    TRUE    yes
overcast    hot    normal    FALSE    yes
rainy    mild    high    TRUE    no

overcast    mild    normal    FALSE    no