（一） 信息熵
信息熵是信息的期望值，描述信息的不確定度。熵越大，表明集合信息的混亂程度越高，換句話說，集合信息混沌，其包含信息價值少。
信息熵計算公式：
（二）信息增益
信息增益是對信息前后變化量的描述。
計算公式：
infoGain = baseEntropy - EntropyAfter
當(dāng)infoGain > 0 ,表明集合信息熵減小，包含的信息更純更有序，價值得到提高。
當(dāng)infoGain < 0，信息變得混沌。
infoGain = 0，信息量沒有變化，但不表明信息沒有變化。
我們要依據(jù)樣本特征來分割數(shù)據(jù)集以使數(shù)據(jù)變得更加有序的過程就是要求一個使得infoGain> 0的分類特征，而且是在所有的特征中使得infoGain值最大的特征。
在決策樹分類中，數(shù)據(jù)集包含的分類特征不止一個，那么，在第一次劃分?jǐn)?shù)據(jù)集時如何從整個特征集中抽出一個特征？第二次呢。信息增益便是對這種劃分?jǐn)?shù)據(jù)集前后信息是更有序了，還是更混亂的度量。
選出取得信息增益最大的特征，以該特征對數(shù)據(jù)集分類，如果該特征共有n個特征值，那么劃分?jǐn)?shù)據(jù)集后會生成n個節(jié)點(diǎn)。這些n個節(jié)點(diǎn)再計算信息增益，并選出最大的特征，以此往復(fù)，直到最終節(jié)點(diǎn)僅包含同一類數(shù)據(jù)為止。
（三）Python代碼實(shí)現(xiàn)
1，劃分?jǐn)?shù)據(jù)
splitDataSet方法接收待分類的數(shù)據(jù)集、預(yù)選中的分類特征featIndex及特征的值featValue。如果樣本預(yù)特征featIndex的值與featValue值相等，則歸集該樣本且移除該分類特征。返回的retDataSet即為移除分類特征的子數(shù)據(jù)集。
def splitDataSet(dataSet, featIndex, featValue):
retDataSet = []
for singleData in dataSet:
if singleData[featIndex] == featValue:
reducedFeatVect = singleData[:featIndex]
reducedFeatVect.extend(single[featIndex + 1:])
retDataSet.append(reducedFeatVect)
return retDataSet
2，選出最佳分類特征
試探性選出最佳分類特征的過程是：
第一步，先從數(shù)據(jù)集的第一列作為分割數(shù)據(jù)的特征，接著第二列，第三列直到最后一列。取出第一列的所有值，并存入集合以去重復(fù)。
第二步，遍歷集合中的分類特征的值，把每一個值傳入splitDataSet方法來判斷該樣本是否應(yīng)該化為該特征的值代表的同質(zhì)集，換句話說，與該特征的值相等的歸集到一類。
第三步，對同一個分類特征而言，可能具有不同的值。特征的值有多少個，對應(yīng)節(jié)點(diǎn)分支有多少支。因此，在對一個分類特征計算信息熵大小時，必須把各個特征的值的信息熵相加，這才代表該分類特征所具有的信息熵。
第四步，原信息熵baseEntropy與分類后的信息熵newEntropy相減即求得信息增益。該次迭代求出的信息增益與上次相比較，若大于上次的信息增益，說明集合信息變得更純些（熵減），則把此次信息增益賦給變量bestInfoFain 并把該特征所在列表索引賦給變量bestFeature ，最后返回最佳的分類特征
def chooseBestFeature(dataSet):
numFeatures = len(dataSet[0]) - 1
baseEntropy = calcShonnonEnt(dataSet)
bestInfoGain = 0.0
bestFeature = -1
for i in range(numFeatures):
featList = [ds[i] for ds in dataSet]
uniqueVals = set(featList)
newEntropy = 0.0
for value in uniqueVals:
subDataSet = splitDataSet(dataSet, i, value)
prob = float(len(subDataSet)) / len(dataSet)
newEntropy += prob * calcShannonEnt(subDataSet)
infoGain = baseEntropy - newEntropy
if infoGain > bestInfoGain:
bestInfoGain = infoGain
bestFeature = i
return bestFeature
3，計算信息熵
def calcShanonnEnt(dataSet):
numberEnt = len(dataSet)
labelCounts = {}
for feat in dataSet:
currentLabel = feat[-1]
if currentLabel not in labelCounts.keys():
labelCounts[currentLabel] = 0
labelCounts[currentLabel] += 1
shannonEnt = 0.0
for key in labelCounts:
prob = float(labelCounts[key]) / numberEntries
shannonEnt -= prob * log(prob, 2)
return shannonEnt