決策樹：決策樹是一個預(yù)測模型，他代表的是對象屬性與對象值之間的一種映射關(guān)系。Entropy(熵) = 系統(tǒng)的凌亂程度，使用算法ID3, C4.5和C5.0生成樹算法得出熵掏父，這一度量是基于信息學(xué)理論中熵的概念。決策樹是一種樹形結(jié)構(gòu)秆剪，其中每個內(nèi)部節(jié)點表示一個屬性上的測試赊淑，每個分支代表一個測試輸出爵政，每個葉節(jié)點代表一種類別。決策樹是一種十分常用的分類方法陶缺，是一種監(jiān)督學(xué)習(xí)钾挟。
決策樹的構(gòu)造
在構(gòu)造決策樹時，我們需要解決的第一個問題就是饱岸，當前數(shù)據(jù)集上那個特征在劃分數(shù)據(jù)分類時起決定性的作用掺出。為了找到?jīng)Q定性的特征，劃分出最好的結(jié)果伶贰，我們必須評估每個特征蛛砰。完成測試之后，原始數(shù)據(jù)集就會被劃分為幾個數(shù)據(jù)子集黍衙。這些數(shù)據(jù)子集會分布在第一個決策點的所有分支上。如果某個分支下的數(shù)據(jù)屬于同一類型荠诬，則已正確劃分數(shù)據(jù)類型琅翻，如過不同，則需重復(fù)劃分數(shù)據(jù)子集柑贞。劃分數(shù)據(jù)子集的算法和原始數(shù)據(jù)相同方椎，直到所有的節(jié)點都是同一類型為止。
信息增益
上面說到我們需要找到?jīng)Q定性的特征來劃分出最好的結(jié)果钧嘶，這也是決策樹核心問題所在棠众，那怎么確定這個最優(yōu)特征呢？我們常用的方法就是用信息論中的信息增益來確定這個特征有决。
在劃分數(shù)據(jù)集之前之后信息發(fā)生的變化叫做信息增益闸拿，知道如何計算信息增益，獲得計算增益最高的特征就是最好的選擇书幕。
在1948年新荤，香農(nóng)引入了信息熵，將其定義為離散隨機事件出現(xiàn)的概率台汇，一個系統(tǒng)越有序苛骨，信息熵就越低，反之一個系統(tǒng)越混亂苟呐，它的信息熵就越高痒芝。所以信息熵可以被認為是系統(tǒng)有序化程度的一個度量。
熵定義為信息的期望值牵素，既然是要算期望严衬，就得先知道信息的定義。如果待分類的事件可能劃分在多個分類之中两波，則事件(Xi)的信息定義為：
info(xi) = -log2p(xi)
其中p(xi)是選擇該類別的概率瞳步。
為了計算熵闷哆，需要計算出信息的期望，即：(這里要吐槽一下簡書单起，不支持MathJax抱怔，所以只能找圖片替代公式)
接下來以氣象數(shù)據(jù)為例子，來說明決策樹的構(gòu)建過程：
| outlook | temperature | humidity | windy | play |
|---|---|---|---|---|
| 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 |
在沒有使用特征劃分類別的情況下嘀倒，有9個yes和5個no屈留，當前的熵為：
假設(shè)我們以 outlook 特征劃分數(shù)據(jù)集，對該特征每項指標分別統(tǒng)計：在不同的取值下 play 和 no play 的次數(shù)：
| outlook | yes | no |
|---|---|---|
| sunny | 2 | 3 |
| overcast | 4 | 0 |
| rainy | 3 | 2 |
此時各分支的熵計算如下：
因此如果用特征outlook來劃分數(shù)據(jù)集的話测蘑，總的熵為：
那么最終得到特征屬性outlook帶來的信息增益為：IG(outlook)=0.940?0.694=0.246灌危，然后用同樣的方法，可以分別求出temperature碳胳，humidity勇蝙，windy的信息增益。IG(temperature)=0.029挨约，IG(humidity)=0.152味混，IG(windy)=0.048〗氩眩可以得出使用outlook特征所帶來的信息增益最大翁锡，所以應(yīng)該首先選擇outlook來劃分數(shù)據(jù)集。然后繼續(xù)劃分各個分支的數(shù)據(jù)集夕土，知道每個分支下的所有實例都具有相同的分類馆衔。最終構(gòu)造出決策樹：
決策樹代碼實現(xiàn)
1. 計算香農(nóng)熵
# 計算香農(nóng)熵
def calShannonEntropy(dataSet):
numEntries = len(dataSet) # 數(shù)據(jù)總數(shù)
labelCounts = {}
for featureVect in dataSet:
currentLabel = featureVect[-1]
if currentLabel not in labelCounts.keys():
labelCounts[currentLabel] = 0
labelCounts[currentLabel] += 1
shannonEnt = 0.0
for key in labelCounts:
probability = float(labelCounts[key]) / numEntries
shannonEnt -= probability * log(probability, 2)
return shannonEnt
2. 按照給定的特征劃分數(shù)據(jù)集
# 劃分數(shù)據(jù)集
def splitDataSet(dataSet, featureIndex, featureValue):
newDataSet = []
for featVec in dataSet:
if featVec[featureIndex] == featureValue:
reducedFeatVec = featVec[:featureIndex]
reducedFeatVec.extend(featVec[featureIndex+1:])
newDataSet.append(reducedFeatVec)
return newDataSet
3. 選擇最佳特征值劃分數(shù)據(jù)集
def chooseBestFeatureToSplit(dataSet):
numFeature = len(dataSet[0]) - 1
baseEntropy = calShannonEntropy(dataSet)
bestFeature = -1; bestInfoGain = 0
for i in range(numFeature):
featList = [entry[i] for entry in dataSet] # 取出每一種屬性
uniqueValue = set(featList) # 得到該屬性有哪些值(用集合的方法去掉重復(fù)值)
newEntropy = 0.0
for value in uniqueValue:
subDataSet = splitDataSet(dataSet, i, value)
probility = len(subDataSet) / float(len(dataSet))
newEntropy += probility * calShannonEntropy(subDataSet)
infoGain = baseEntropy - newEntropy
if infoGain > bestInfoGain:
bestInfoGain = infoGain
bestFeature = i
return bestFeature
4. 投票決定不確定結(jié)果
如果數(shù)據(jù)集已經(jīng)處理了所有屬性，但是類標簽依然不是唯一的怨绣，通常我們才有多數(shù)表決的方法決定該葉子節(jié)點的分類角溃。
# 找出票數(shù)最多的標簽
def majorityVote(classList):
classCount = {}
for vote in classList:
if vote not in classList.keys():
classCount[vote] = 0
classCount[vote] += 1
sortedClassCount = sorted(classCount.items(), key=operator.itemgetter(1), reversed=True)
return sortedClassCount[0][0]
5. 創(chuàng)建決策樹
def createTree(dataset, labels):
# 取出位于最后一列的類別標簽
classList = [label[-1] for label in dataset]
if classList.count(classList[0]) == len(classList): # 類別完全相同時，停止劃分
return classList[0] # 返回唯一特征值
if len(dataset[0]) == 1: # 已經(jīng)遍歷完所有特征梨熙，只剩最后一列類別標簽
return majorityVote(classList) # 返回票數(shù)最多的類標簽
# 開始劃分
# 先選取最好的劃分特征值
bestFeature = chooseBestFeatureToSplit(dataset)
bestFeatureLabel = labels[bestFeature]
# 初始化樹
myTree = {bestFeatureLabel: {}}
subLabels = labels[:]
del subLabels[bestFeature]
# 遞歸構(gòu)建決策樹
featList = [entry[bestFeature] for entry in dataset]
uniqueValues = set(featList)
for value in uniqueValues:
myTree[bestFeatureLabel][value] = createTree(splitDataSet(dataset, bestFeature, value), subLabels)
return myTree
6. 使用決策樹執(zhí)行分類
# 使用決策樹執(zhí)行分類
def classify(inputTree, featLabels, testVec):
# 取出根節(jié)點,python2直接寫成inputTree.keys()[0]
firstStr = list(inputTree.keys())[0]
# 找到根節(jié)點下面的分支(該分類特征的分支)
childDict = inputTree[firstStr]
featIndex = featLabels.index(firstStr)
# 遍歷分類特征的所有取值
for key in childDict.keys():
# 如果測試向量的該類值等于分類特征的第key個節(jié)點
if testVec[featIndex] == key:
# 判斷該節(jié)點是否為字典類型
if type(childDict[key]).__name__ == 'dict':
# 是字典類型开镣，繼續(xù)遍歷
classLabel = classify(childDict[key], featLabels, testVec)
else:
# 不是字典，返回最終結(jié)果
classLabel = childDict[key]
return classLabel
7. 存儲決策樹
構(gòu)建決策樹是非常耗時的任務(wù)咽扇，即使很小的數(shù)據(jù)集邪财，也要花費幾秒的時間來構(gòu)建決策樹，這樣顯然耗費計算時間质欲。所以树埠，我們可以將構(gòu)建好的決策樹保存在磁盤中，這樣當我們需要的時候嘶伟，再從磁盤中讀取出來使用即可怎憋。為了解決這個問題，可以使用pickle序列化對象，任何對象都可以執(zhí)行序列化操作绊袋，字典對象也不例外毕匀。
