關於本文說明，本人原博客地址位於http://blog.csdn.net/qq_37608890，本文來自筆者於2017年12月06日 18:06:30所撰寫內容（http://blog.csdn.net/qq_37608890/article/details/78731169）。 本文根據最近學習 ...
關於本文說明，本人原博客地址位於http://blog.csdn.net/qq_37608890，本文來自筆者於2017年12月06日 18:06:30所撰寫內容（http://blog.csdn.net/qq_37608890/article/details/78731169）。
本文根據最近學習機器學習書籍 網路文章的情況,特將一些學習思路做了歸納整理,詳情如下.如有不當之處,請各位大拿多多指點,在此謝過.
一、決策樹(decision tree)概述
1、決策樹概念
決策樹（decision tree）是一個樹結構（可以是二叉樹或非二叉樹）。其每個非葉節點表示一個特征屬性上的測試，每個分支代表這個特征屬性在某個值域上的輸出，而每個葉節點存放一個類別。使用決策樹進行決策的過程就是從根節點開始，測試待分類項中相應的特征屬性，並按照其值選擇輸出分支，直到到達葉子節點，將葉子節點存放的類別作為決策結果。
2 工作原理
在構造決策樹時,需要解決的第一個問題就是,當前數據集上哪個特征在劃分數據分類時起到來決定性的作用。為了找到決定性的特征,我們需要對每個特征都要進行評估.完成測試後,原始數據就被劃分為幾個數據子集.這些數據子集會分佈在第一個決策點的所有分支上.若某一分支下的數據屬於同一類型,則當前無需閱讀的垃圾郵件已經被正確地劃分數據分類,沒必要再對數據集進行分類.否則,則需要重覆劃分數據子集的過程.這裡劃分子集的演算法和劃分原始數據集的方法相同,直至所有具有相同類型的數據都進入一個數據子集內.構造決策樹偽代碼函數createBranch()如下:
檢測數據集中的每個子項是否屬於同一分類:
IF so return 類標簽
Else
尋找劃分數據集的最好特征
劃分數據集
創建分支節點
for 每個劃分的子集
調用函數createBranch()並增加返回結果到分支節點中
return 分支節點
一旦我們構造了一個決策樹模型，以它為基礎來進行分類將是非常容易的。具體做法是，從根節點開始，對實例的某一特征進行測試，根據測試結構將實例分配到其子節點（也就是選擇適當的分支）；沿著該分支可能達到葉子節點或者到達另一個內部節點時，那麼就使用新的測試條件遞歸執行下去，直到抵達一個葉子節點。當到達葉子節點時，我們便得到了最終的分類結果。下麵介紹一個小例子。
通俗來說，決策樹分類的思想類似於找對象。現想象一個女孩的母親要給這個女孩介紹男朋友，於是有了下麵的對話：
女兒：多大年紀了？
母親：26。
女兒：長的帥不帥？
母親：挺帥的。
女兒：收入高不？
母親：不算很高，中等情況。
女兒：是公務員不？
母親：是，在稅務局上班呢。
女兒：那好，我去見見。
這個女孩的決策過程就是典型的分類樹決策。相當於通過年齡、長相、收入和是否公務員對將男人分為兩個類別：見和不見。假設這個女孩對男人的要求是：30歲以下、長相中等以上並且是高收入者或中等以上收入的公務員，那麼這個可以用下圖表示女孩的決策邏輯:
上圖完整表達了這個女孩決定是否見一個約會對象的策略，其中綠色節點表示判斷條件，橙色節點表示決策結果，箭頭表示在一個判斷條件在不同情況下的決策路徑，圖中紅色箭頭表示了上面例子中女孩的決策過程。
這幅圖基本可以算是一顆決策樹，說它“基本可以算”是因為圖中的判定條件沒有量化，如收入高中低等等，還不能算是嚴格意義上的決策樹，如果將所有條件量化，則就變成真正的決策樹了。
3、決策樹的相關特性
-
優點:計算複雜度不高,輸出結果易於理解,對中間值的缺失不敏感,可以處理不相關特征數據。
-
缺點:可能會產生過度匹配問題。
-
使用數據類型: 數值型和標稱型。
4、 一般流程
(1) 收集數據: 可以使用任何方法.
(2) 準備數據: 構造演算法只適用於標稱型數據,因此數值型數據必須離散化.
(3) 分析數據: 可以使用任何方法,構造樹完成之後,應該檢查圖形是否符合預期.
(4) 訓練演算法: 構造樹的數據結構.
(5) 測試演算法: 使用經驗樹計算錯誤率.
(6) 使用演算法: 此步驟可以適用於任何監督學習演算法,而使用決策樹可以更好地理解數據的內在含義.
二 決策樹場景
假設,現在有一個叫做 "十五個問題" 的游戲，游戲的規則很簡單：參與游戲的一方在腦海中想某個事物，其他參與者向他提問，只允許提 15個問題，問題的答案也只能用對或錯回答。問問題的人通過推斷分解，逐步縮小待猜測事物的範圍，最後得到游戲的答案。決策樹的工作原理與15個問題類似,用戶輸入一系列數據後給出游戲答案。
下圖給出了一個假想的郵件分類系統,它首先檢測發送郵件功能變數名稱.如果地址為myEmployer.com,則將其放在"無聊時需要閱讀的郵件"中。否則,則需要檢查郵件內容中是否包含單詞
曲棍球 ,若包含則將郵件歸入"需要及時處理的朋友郵件",否則則歸類到"無需閱讀的垃圾郵件"。
決策樹一個很重要的任務就是為了理解數據中所蘊含的知識信息(這與K-近鄰演算法無法給出數據的內在含義有著顯著不同),因此決策樹可以使用不熟悉的數據集合,並從中提取出一系列規則,這些機器根據數據集創建規則的過程,就是機器學習的過程。
三 決策樹項目案例一 對海洋生物進行魚和非魚判斷
1 項目情況
下表中的數據包含5個海洋生物,特征: 不浮出水面是否可以生存和是否有腳蹼.現將動物劃分為兩類: 魚和非魚.如果想依據給出的特征選出一個來劃分數據,就涉及到要將劃分數據的依據進行量化後才可以判斷出來.
我們先構造進行數據輸入的createDataSet()函數和計算給定數據集的香農熵函數calcShannonEnt()
def createDataSet():
dataSet = [[1,1,'yes'],
[1,1,'yes'],
[1,0,'no'],
[0,1,'no'],
[0,1,'no']]
labels=['no surfacing','flippers']
# change to discrete values
return dataSet,labels
#信息增益
#計算給定數據的香農熵
def calcShannonEnt(dataSet): #the the number of unique elements and their occurance
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.00000
for key in labelCounts:
prob = float(labelCounts[key]) /numEntries
shannonEnt -= prob * log(prob,2) #log base 2
return shannonEnt
執行
myDat,labels=createDataSet()
myDat
得到
[[1, 1, 'yes'], [1, 1, 'yes'], [1, 0, 'no'], [0, 1, 'no'], [0, 1, 'no']]
執行
calcShannonEnt(myDat)
得到
0.9709505944546686
熵越高,則混合的數據越多,我們可用在數據集中添加更多的分類,觀察熵是如何變化的.
按照給定特征劃分數據集,將指定特征的特征值等於 value 的行剩下列作為子數據集。
def splitDataSet(dataSet, index, value):
"""splitDataSet(通過遍歷dataSet數據集，求出index對應的colnum列的值為value的行)
就是依據index列進行分類，如果index列的數據等於 value的時候，就要將 index 劃分到我們創建的新的數據集中
Args:
dataSet 數據集 待劃分的數據集
index 表示每一行的index列 劃分數據集的特征
value 表示index列對應的value值 需要返回的特征的值。
Returns:
index列為value的數據集【該數據集需要排除index列】
"""
retDataSet = []
for featVec in dataSet:
# index列為value的數據集【該數據集需要排除index列】
# 判斷index列的值是否為value
if featVec[index] == value:
# chop out index used for splitting
# [:index]表示前index行，即若 index 為2，就是取 featVec 的前 index 行
reducedFeatVec = featVec[:index]
'''''
請百度查詢一下： extend和append的區別
list.append(object) 向列表中添加一個對象object
list.extend(sequence) 把一個序列seq的內容添加到列表中
1、使用append的時候，是將new_media看作一個對象，整體打包添加到music_media對象中。
2、使用extend的時候，是將new_media看作一個序列，將這個序列和music_media序列合併，並放在其後面。
result = []
result.extend([1,2,3])
print result
result.append([4,5,6])
print result
result.extend([7,8,9])
print result
結果：
[1, 2, 3]
[1, 2, 3, [4, 5, 6]]
[1, 2, 3, [4, 5, 6], 7, 8, 9]
'''
reducedFeatVec.extend(featVec[index+1:])
# [index+1:]表示從跳過 index 的 index+1行，取接下來的數據
# 收集結果值 index列為value的行【該行需要排除index列】
retDataSet.append(reducedFeatVec)
return retDataSet
選擇最好的數據集劃分方式:
def chooseBestFeatureToSplit(dataSet):
"""chooseBestFeatureToSplit(選擇最好的特征)
Args:
dataSet 數據集
Returns:
bestFeature 最優的特征列
"""
# 求第一行有多少列的 Feature, 最後一列是label列嘛
numFeatures = len(dataSet[0]) - 1
# 數據集的原始信息熵
baseEntropy = calcShannonEnt(dataSet)
# 最優的信息增益值, 和最優的Featurn編號
bestInfoGain, bestFeature = 0.0, -1
# iterate over all the features
for i in range(numFeatures):
# create a list of all the examples of this feature
# 獲取對應的feature下的所有數據
featList = [example[i] for example in dataSet]
# get a set of unique values
# 獲取剔重後的集合，使用set對list數據進行去重
uniqueVals = set(featList)
# 創建一個臨時的信息熵
newEntropy = 0.0
# 遍歷某一列的value集合，計算該列的信息熵
# 遍歷當前特征中的所有唯一屬性值，對每個唯一屬性值劃分一次數據集，計算數據集的新熵值，並對所有唯一特征值得到的熵求和。
for value in uniqueVals:
subDataSet = splitDataSet(dataSet, i, value)
# 計算概率
prob = len(subDataSet)/float(len(dataSet))
# 計算信息熵
newEntropy += prob * calcShannonEnt(subDataSet)
# gain[信息增益]: 劃分數據集前後的信息變化， 獲取信息熵最大的值
# 信息增益是熵的減少或者是數據無序度的減少。最後，比較所有特征中的信息增益，返回最好特征劃分的索引值。
infoGain = baseEntropy - newEntropy
print 'infoGain=', infoGain, 'bestFeature=', i, baseEntropy, newEntropy
if (infoGain > bestInfoGain):
bestInfoGain = infoGain
bestFeature = i
return bestFeature
訓練演算法：構造樹的數據結構
創建樹的函數
def createTree(dataSet, labels):
classList = [example[-1] for example in dataSet]
# 如果數據集的最後一列的第一個值出現的次數=整個集合的數量，也就說只有一個類別，就只直接返回結果就行
# 第一個停止條件：所有的類標簽完全相同，則直接返回該類標簽。
# count() 函數是統計括弧中的值在list中出現的次數
if classList.count(classList[0]) == len(classList):
return classList[0]
# 如果數據集只有1列，那麼最初出現label次數最多的一類，作為結果
# 第二個停止條件：使用完了所有特征，仍然不能將數據集劃分成僅包含唯一類別的分組。
if len(dataSet[0]) == 1:
return majorityCnt(classList)
# 選擇最優的列，得到最優列對應的label含義
bestFeat = chooseBestFeatureToSplit(dataSet)
# 獲取label的名稱
bestFeatLabel = labels[bestFeat]
# 初始化myTree
myTree = {bestFeatLabel: {}}
# 註：labels列表是可變對象，在PYTHON函數中作為參數時傳址引用，能夠被全局修改
# 所以這行代碼導致函數外的同名變數被刪除了元素，造成例句無法執行，提示'no surfacing' is not in list
del(labels[bestFeat])
# 取出最優列，然後它的branch做分類
featValues = [example[bestFeat] for example in dataSet]
uniqueVals = set(featValues)
for value in uniqueVals:
# 求出剩餘的標簽label
subLabels = labels[:]
# 遍歷當前選擇特征包含的所有屬性值，在每個數據集劃分上遞歸調用函數createTree()
myTree[bestFeatLabel][value] = createTree(splitDataSet(dataSet, bestFeat, value), subLabels)
# print 'myTree', value, myTree
return myTree
測試演算法：使用決策樹執行分類
def classify(inputTree, featLabels, testVec):
"""classify(給輸入的節點，進行分類)
Args:
inputTree 決策樹模型
featLabels Feature標簽對應的名稱
testVec 測試輸入的數據
Returns:
classLabel 分類的結果值，需要映射label才能知道名稱
"""
# 獲取tree的根節點對於的key值
firstStr = inputTree.keys()[0]
# 通過key得到根節點對應的value
secondDict = inputTree[firstStr]
# 判斷根節點名稱獲取根節點在label中的先後順序，這樣就知道輸入的testVec怎麼開始對照樹來做分類
featIndex = featLabels.index(firstStr)
# 測試數據，找到根節點對應的label位置，也就知道從輸入的數據的第幾位來開始分類
key = testVec[featIndex]
valueOfFeat = secondDict[key]
print '+++', firstStr, 'xxx', secondDict, '---', key, '>>>', valueOfFeat
# 判斷分枝是否結束: 判斷valueOfFeat是否是dict類型
if isinstance(valueOfFeat, dict):
classLabel = classify(valueOfFeat, featLabels, testVec)
else:
classLabel = valueOfFeat
return classLabel
三 項目案例2: 使用決策樹預測隱形眼鏡類型
項目概述
隱形眼鏡類型包括硬材質、軟材質以及不適合佩戴隱形眼鏡。我們需要使用決策樹預測患者需要佩戴的隱形眼鏡類型。
開發流程
(1)收集數據: 提供的文本文件。
(2)解析數據: 解析 tab 鍵分隔的數據行
(3)分析數據: 快速檢查數據，確保正確地解析數據內容，使用 createPlot() 函數繪製最終的樹形圖。
(4)訓練演算法: 使用 createTree() 函數。
(5)測試演算法: 編寫測試函數驗證決策樹可以正確分類給定的數據實例。
(6)使用演算法: 存儲樹的數據結構，以便下次使用時無需重新構造樹。
收集數據：提供的文本文件
文本文件數據格式如下:
young myope no reduced no lenses pre myope no reduced no lenses presbyopic myope no reduced no lenses
解析數據：解析 tab 鍵分隔的數據行
lecses = [inst.strip().split('\t') for inst in fr.readlines()]
lensesLabels = ['age', 'prescript', 'astigmatic', 'tearRate']
分析數據：快速檢查數據，確保正確地解析數據內容，使用 createPlot() 函數繪製最終的樹形圖。
treePlotter.createPlot(lensesTree)
訓練演算法：使用 createTree() 函數
>>> lensesTree = trees.createTree(lenses, lensesLabels)
>>> lensesTree
得到
{'tearRate': {'reduced': 'no lenses', 'normal': {'astigmatic':{'yes':
{'prescript':{'hyper':{'age':{'pre':'no lenses', 'presbyopic':
'no lenses', 'young':'hard'}}, 'myope':'hard'}}, 'no':{'age':{'pre':
'soft', 'presbyopic':{'prescript': {'hyper':'soft', 'myope':
'no lenses'}}, 'young':'soft'}}}}}
五 小結
其實決策樹跟帶終止塊的流程圖類似,所以這裡的終止塊就是分類結果.當我們進行數據處理時,首先要對集合中數據的不一致性進行測量評估,也就是計算香農熵,下一步才可以尋找最有方案劃分數據,最終實現所有具有相同類型的數據都劃分到同一個數據子集裡面.在構建數據樹時,我們一般採用遞歸方把數據集轉化為決策樹.多數情況下,我們不構造新的數據結構,而是採用Python語言內嵌的數據結構字典存儲樹節點信息.每一步選擇信息增益最大的特征作為決策塊,最終來完成決策樹的生成.
Matplotlib的註解功能,可以讓將存儲的樹結構轉化為容易理解的圖形.隱形眼鏡的例子說明決策樹可能會產生過多的數據集劃分,結果導致過度匹配數據集的問題.當然可以通過裁剪決策樹,合併相鄰的不能產生信息增益的葉節點,來解決這個問題(過度匹配).
關於決策樹的構造演算法,這裡本文只是用了ID3演算法,當然還有C4.5和CART演算法.對於決策樹的完整工作過程而言,包括三部分:
1 特征選擇;
2 生成決策樹;
3 剪枝部分
而除去ID3演算法,其他兩個演算法都有剪枝部分過程.所以這也迎合來隱形眼鏡過擬合的問題.
關於決策樹部分,筆者先整理到這裡,後續有機會會針對C4.5和CART演算法做些歸納整理.有不足之處,請各位同仁多多指導.
