本文結(jié)構(gòu)：
- 是什么？
- 有什么算法？
- 數(shù)學(xué)原理？
- 編碼實現(xiàn)算法？
1. 是什么？
簡單地理解，就是根據(jù)一些 feature 進行分類，每個節(jié)點提一個問題，通過判斷，將數(shù)據(jù)分為幾類，再繼續(xù)提問。這些問題是根據(jù)已有數(shù)據(jù)學(xué)習(xí)出來的，再投入新數(shù)據(jù)的時候，就可以根據(jù)這棵樹上的問題，將數(shù)據(jù)劃分到合適的葉子上。
2. 有什么算法？
常用的幾種決策樹算法有ID3、C4.5、CART：
ID3：選擇信息熵增益最大的feature作為node，實現(xiàn)對數(shù)據(jù)的歸納分類。
C4.5：是ID3的一個改進，比ID3準(zhǔn)確率高且快，可以處理連續(xù)值和有缺失值的feature。
CART：使用基尼指數(shù)的劃分準(zhǔn)則，通過在每個步驟最大限度降低不純潔度，CART能夠處理孤立點以及能夠?qū)杖敝颠M行處理。
3. 數(shù)學(xué)原理？
ID3: Iterative Dichotomiser 3
下面這個數(shù)據(jù)集，可以同時被上面兩顆樹表示，結(jié)果是一樣的，而我們更傾向于選擇簡單的樹。
那么怎樣做才能使得學(xué)習(xí)到的樹是最簡單的呢？
下面是 ID3（ Iterative Dichotomiser 3 ）的算法：
例如下面數(shù)據(jù)集，哪個是最好的 Attribute？
用熵Entropy來衡量：
E(S) 是數(shù)據(jù)集S的熵
i 指每個結(jié)果，即 No，Yes的概率
E越大意味著信息越混亂，我們的目標(biāo)是要讓E最小。
E在0-1之間，如果P＋的概率在0.5， 此時E最大，這時候說明信息對我們沒有明確的意義，對分類沒有幫助。
但是我們不僅僅想要變量的E最小，還想要這棵樹是 well organized。
所以用到 Gain：信息增益
意思是如果我后面要用這個變量的話，它的E會減少多少。
例如下面的數(shù)據(jù)集：
-
先計算四個feature的熵E，及其分支的熵，然后用Gain的公式計算信息增益。
再選擇Gain最大的特征是 outlook。
-
第一層選擇出來后，各個分支再繼續(xù)選擇下一層，計算Gain最大的，例如分支 sunny 的下一層節(jié)點是 humidity。
詳細(xì)的計算步驟可以參考這篇博文。
C4.5
ID3有個局限是對于有大量數(shù)據(jù)的feature過于敏感，C4.5是它的一個改進，通過選擇最大的信息增益率 gain ratio 來選擇節(jié)點。而且它可以處理連續(xù)的和有缺失值的數(shù)據(jù)。
P’ (j/p) is the proportion of elements present at the position p, taking the value of j-th test.
例如 outlook 作為第一層節(jié)點后，它有 3 個分支，分別有 5，4，5 條數(shù)據(jù)，則 SplitInfo(5,4,5) = -5/14log(5,14)-4/14log(4,14)-5/14(5,14) ，其中 log(5,14) 即為 log2(5/14)。
下面是一個有連續(xù)值和缺失值的例子：
連續(xù)值
第一步計算 Gain，除了連續(xù)值的 humudity，其他步驟和前文一樣。
要計算 humudity 的 Gain 的話，先把所有值升序排列：
{65, 70, 70, 70, 75, 78, 80, 80, 80, 85, 90, 90, 95, 96}
然后把重復(fù)的去掉：
{65, 70, 75, 78, 80, 85, 90, 95, 96}
如下圖所示，按區(qū)間計算 Gain，然后選擇最大的 Gain (S, Humidity) = 0.102
因為 Gain(S, Outlook) = 0 .246，所以root還是outlook：
缺失值
處理有缺失值的數(shù)據(jù)時候，用下圖的公式：
例如 D12 是不知道的。
-
計算全集和 outlook 的 info，
-
其中幾個分支的熵如下，再計算出 outlook 的 Gain：
比較一下 ID3 和 C4.5 的準(zhǔn)確率和時間：
accuracy ：
execution time：
4. 編碼實現(xiàn)算法？
代碼可以看《機器學(xué)習(xí)實戰(zhàn)》這本書和這篇博客。
完整代碼可以在 github 上查看。
接下來以 C4.5 的代碼為例：
** 1. 定義數(shù)據(jù)：**
def createDataSet():
dataSet = [[0, 0, 0, 0, 'N'],
[0, 0, 0, 1, 'N'],
[1, 0, 0, 0, 'Y'],
[2, 1, 0, 0, 'Y'],
[2, 2, 1, 0, 'Y'],
[2, 2, 1, 1, 'N'],
[1, 2, 1, 1, 'Y']]
labels = ['outlook', 'temperature', 'humidity', 'windy']
return dataSet, labels
** 2. 計算熵：**
def calcShannonEnt(dataSet):
numEntries = len(dataSet)
labelCounts = {}
for featVec in dataSet:
currentLabel = featVec[-1]
if currentLabel not in labelCounts.keys():
labelCounts[currentLabel] = 0
labelCounts[currentLabel] += 1 # 數(shù)每一類各多少個， {'Y': 4, 'N': 3}
shannonEnt = 0.0
for key in labelCounts:
prob = float(labelCounts[key])/numEntries
shannonEnt -= prob * log(prob, 2)
return shannonEnt
** 3. 選擇最大的gain ratio對應(yīng)的feature：**
def chooseBestFeatureToSplit(dataSet):
numFeatures = len(dataSet[0]) - 1 #feature個數(shù)
baseEntropy = calcShannonEnt(dataSet) #整個dataset的熵
bestInfoGainRatio = 0.0
bestFeature = -1
for i in range(numFeatures):
featList = [example[i] for example in dataSet] #每個feature的list
uniqueVals = set(featList) #每個list的唯一值集合
newEntropy = 0.0
splitInfo = 0.0
for value in uniqueVals:
subDataSet = splitDataSet(dataSet, i, value) #每個唯一值對應(yīng)的剩余feature的組成子集
prob = len(subDataSet)/float(len(dataSet))
newEntropy += prob * calcShannonEnt(subDataSet)
splitInfo += -prob * log(prob, 2)
infoGain = baseEntropy - newEntropy #這個feature的infoGain
if (splitInfo == 0): # fix the overflow bug
continue
infoGainRatio = infoGain / splitInfo #這個feature的infoGainRatio
if (infoGainRatio > bestInfoGainRatio): #選擇最大的gain ratio
bestInfoGainRatio = infoGainRatio
bestFeature = i #選擇最大的gain ratio對應(yīng)的feature
return bestFeature
** 4. 劃分?jǐn)?shù)據(jù)，為下一層計算準(zhǔn)備: **
def splitDataSet(dataSet, axis, value):
retDataSet = []
for featVec in dataSet:
if featVec[axis] == value: #只看當(dāng)?shù)趇列的值＝value時的item
reduceFeatVec = featVec[:axis] #featVec的第i列給除去
reduceFeatVec.extend(featVec[axis+1:])
retDataSet.append(reduceFeatVec)
return retDataSet
** 5. 多重字典構(gòu)建樹：**
def createTree(dataSet, labels):
classList = [example[-1] for example in dataSet] # ['N', 'N', 'Y', 'Y', 'Y', 'N', 'Y']
if classList.count(classList[0]) == len(classList):
# classList所有元素都相等，即類別完全相同，停止劃分
return classList[0] #splitDataSet(dataSet, 0, 0)此時全是N，返回N
if len(dataSet[0]) == 1: #[0, 0, 0, 0, 'N']
# 遍歷完所有特征時返回出現(xiàn)次數(shù)最多的
return majorityCnt(classList)
bestFeat = chooseBestFeatureToSplit(dataSet) #0－> 2
# 選擇最大的gain ratio對應(yīng)的feature
bestFeatLabel = labels[bestFeat] #outlook -> windy
myTree = {bestFeatLabel:{}}
#多重字典構(gòu)建樹{'outlook': {0: 'N'
del(labels[bestFeat]) #['temperature', 'humidity', 'windy'] -> ['temperature', 'humidity']
featValues = [example[bestFeat] for example in dataSet] #[0, 0, 1, 2, 2, 2, 1]
uniqueVals = set(featValues)
for value in uniqueVals:
subLabels = labels[:] #['temperature', 'humidity', 'windy']
myTree[bestFeatLabel][value] = createTree(splitDataSet(dataSet, bestFeat, value), subLabels)
# 劃分?jǐn)?shù)據(jù)，為下一層計算準(zhǔn)備
return myTree
** 6. 可視化決策樹的結(jié)果: **
dataSet, labels = createDataSet()
labels_tmp = labels[:]
desicionTree = createTree(dataSet, labels_tmp)
treePlotter.createPlot(desicionTree)
我是 不會停的蝸牛 Alice
85后全職主婦
喜歡人工智能，行動派
創(chuàng)造力，思考力，學(xué)習(xí)力提升修煉進行中
歡迎您的喜歡，關(guān)注和評論！
