摘要：前言決策樹算法，是指一類通過對數據集中特征的選擇，構造一個樹，實現對數據的分類的算法。算法首先，讓我們以例子來看看算法的實現過程。假設我們現在要做一次決策判斷一個人會買什么類型的保險。個人理解信息熵就是描述給出的這組數據的分類有多不確定。

決策樹算法，是指一類通過對數據集中特征的選擇，構造一個樹，實現對數據的分類的算法。
這棵樹的每一個節點都是選中的其中一種特征，而該節點的邊則是這種特征的分類。
更詳細的定義可以Google之。

首先，讓我們以例子來看看ID3算法的實現過程。
假設我們現在要做一次決策：判斷一個人會買什么類型的保險。在這個例子中有如下特征：

性別（男、女）

年齡（<21、>=21and=<25、>25）

婚姻狀況（已婚、未婚）

而根據這些特征，我們會有最終每個人購買的保險類型（A、B、C），以下給出數據：

接下來，ID3算法根據每個特征的重要程度（該值通過信息熵來判斷，但是信息熵這個概念等下具體實現時候再說XD），構造如下的一個樹：
對于如上格式的每個樣例，首先判斷性別（男或女），如果是男的，就需要用婚姻狀況來判斷；如果是女的，則需要用年齡來判斷。這樣迭代判斷直到到達葉子節點，也就得出了可能選擇的保險類型。

那么，此時重點來了，我們該如何判斷選擇哪個特征最合適呢？？

經過許多大神的不懈研究，借鑒了物理學上的熵的概念，信息領域提出了如下幾個定義：

信息熵（Entropy）

    用于描述一組數據的混亂、不確定程度
    計算公式如下：
    

用上述例子來說，p（Xi）指所有數據中A、B、C這三個各自出現的概率，就是A、B、C各自的個數/總個數。
個人理解信息熵就是描述給出的這組數據的分類有多不確定。就比如預測明天下不下雨這一問題，信息熵就很大；而預測每一個人明天吃不吃飯這一問題，信息熵就很小。因為絕大部分人，明天肯定是要吃飯的orz。。。。

條件熵

     用于描述一組數據的子數據的混亂、不確定程度

這是什么意思呢？個人理解就是確定數據的某一特征之后，在這一特征上的數據分類的不確定程度。比如依舊是預測明天下不下雨這一問題，如果現在明確告訴你，明天云的情況（多云、少云、沒有云），那么在明天云情況這一特征上的每個分類都能計算相應的信息熵。

信息增益

       用于描述某一特征對整體的重要程度
       根據定義，可以知道，信息增益就是總信息熵減去某個特征上各個分類的條件熵，如下：
       
       

1、被減數就是總信息熵。
2、減數中的value（T）是指在某一個特征的一種分類，如性別就包含兩個分類（男、女），entropy（Sv）就是在該特征的某個分類上的條件熵。
3、S是指所有數據個數
4、Sv是指在該特征的一種分類下數據個數。

在了解了這些定義后，我們回到最開始的問題：如何判斷哪個特征最合適你？

上面說到，信息熵越大，數據集就越混亂，就越難得到準確的結果，所以我們要選擇的特征應該能使得在
確定這個特征后的信息熵越小，也就是條件熵越小，亦即信息增益最大。
因此，具體實現思路如下：
**遍歷所有特征，根據遍歷的每個特征進行數據集分類，算出每個特征下的條件熵，然后取條件熵最小
的，信息增益最大的特征。接著，根據選擇的特征進行分類，得到的子數據在刪除選擇的特征后，遞歸
選擇下一個特征**   

#coding=utf-8
import csv
import pandas as pd
import math
import drewTree

def readData(path):
    df=pd.read_csv(path)
    return df.values.tolist(),df.columns.values.tolist()

#計算信息熵
def countEntropy(data):
    sumEg=len(data)
    labelCount={}
    #計算不同保險類別的數量
    for example in data:
        if example[-1] not in labelCount.keys():
            labelCount[example[-1]]=0
        labelCount[example[-1]]+=1
    #開始計算信息熵
    ent=0
    for key in labelCount:
        prop=float(labelCount[key])/sumEg
        ent-=prop*math.log(prop,2)
    return ent
#根據特征分類劃分數據集
def splitData(data,featureNum):
    res={}
    for example in data:
        if example[featureNum] not in res.keys():
            res[example[featureNum]]=[]
        res[example[featureNum]].append(example)
    return res
#移除數據中已經選擇的特征值
def removeFeature(data,featureNum):
    res=[]
    for example in data:
        example.pop(featureNum)
        res.append(example)
    return res
#單特征投票
#當所有特征都選擇完時，還有多于1個以上的樣例，則直接根據保險類型投票，票高者得勝
def vote(classData):
    count={}
    for example in classData:
        if example not in count.keys():
            count[example]=0
        count[example]+=1
    return max(count)
#選擇信息增益最大的特征
def selectBestFeature(data,dataLabel):
    sumEnt=countEntropy(data)
    sumFeatureNum=len(data[0])-1
    minConditionEnt = 999999
    bestFeature = []
    bfNum = -2
    #計算每個特征的信息增益
    for i in range(sumFeatureNum):
        spData=splitData(data,i)
        num=len(data)
        conditionEnt=0
        for key in spData:
            conditionEnt+=float(len(spData[key]))/num*countEntropy(spData[key])
        if (conditionEnt < minConditionEnt):
            minConditionEnt = conditionEnt
            bestFeature =dataLabel[i]
            bfNum=i
    return bestFeature,bfNum

def createTree(data,dataLabel):
    #只剩保險類型時，根據剩余的數據集進行投票
    if len(data[0])==1:
        return vote(example[-1] for example in data)
    bestFeature,bfNum=selectBestFeature(data,dataLabel)
    dicisionTree={bestFeature:{}}
    bestFeatureData=splitData(data,bfNum)
    label=dataLabel
    temp=label.pop(bfNum)
    #剩余特征進行遞歸構造決策樹
    for key in bestFeatureData:
        rmFData=removeFeature(bestFeatureData[key],bfNum)
        dicisionTree[bestFeature][key]=createTree(rmFData,label)
    label.insert(bfNum,temp)
    return dicisionTree
    
#調用
data,dataLabel=readData("./ID3New.csv")
res=createTree(data,dataLabel)

參考博客：http://blog.csdn.net/wzmsltw/...