[機器學習演算法]決策樹

來自專欄 數據分析入門

構造決策樹的關鍵步驟是進行屬性度量選擇，一般使用自頂向下遞歸分治法

決策樹構建的一般流程：

第一步：計算類別的熵

第二步：按照給定特徵劃分數據集

給定特徵值所在列，及特徵的值

第三步：計算條件熵，選擇最大的作為最好的劃分方式

第四步：創建決策樹

用到遞歸函數，出口有兩個：

1.所有類別都相同停止劃分

2.所有特徵都遍歷完還未確定分類的，返回次數最多的分類（此處用到判斷葉子結點分類的函數，也正是因為這個原因，導致決策樹的預測不是百分之百）

當某個特徵被選定為最優使用之後就刪除掉，再利用剩下的數據集進行遞歸

第五步：可視化決策樹

• ID3演算法

以信息增益作為屬性選擇標準

缺點：對可取值數目較多的屬性有所偏好

原因：信息增益認定如果根據某個特徵劃分後得到的數個樣本集純度越高那麼這個劃分方式的信息增益就越大，那麼理論上講，只要該特徵中包含的屬性越多，劃分後的每個樣本集合中的樣本數量就越傾向於更小，樣本越少樣本集合「純度」自然就更容易變高

• C4.5演算法

以信息增益率作為屬性選擇標準，克服了ID3演算法中採用信息增益劃分導致屬性選擇偏向取值多的屬性

• 基尼指數（CART決策樹中使用）

Gini(D)越小，則數據集D的純度越高

• 剪枝

在決策樹學習中，為了儘可能正確分類訓練樣本，結點劃分過程將不斷重複，有時會造成決

策樹分支過多，而導致過擬合。

剪枝是決策樹學習演算法對付"過擬合"的主要手段，分為「預剪枝」和「後剪枝」。

預剪枝：基於「貪心」演算法（當前最優，並非全局最優），很容易欠擬合，但時間複雜度低

後剪枝：比預剪枝保留更多的分枝，泛化能力更好，但因為要生成完整的一棵決策樹之後才剪枝，時間複雜度更高

• 如何處理連續屬性

決策樹的生成都是基於離散屬性，如果出現連續屬性，可以採用連續屬性離散化技術（二分法等）

• 如果屬性用完了怎麼辦

所有屬性都作為分裂屬性用光了，集合內的元素不屬於同一類別。在這種情況下，由於沒有更多信息可以使用了，一般對這些子集進行「多數表決」，即使用此子集中出現次數最多的類別作為此節點類別

相關代碼：

from math import logimport operator#創建數據集def createDataset(): # 為了區分，false代表no，real代表yes dataset = [[1, 1, 1], [1, 1, 1], [1, 0, 0], [0, 1, 0], [0, 1, 0]] labels = [A, B] return dataset,labels#計算數據集的香濃熵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 shannonEnt = 0.0 for key in labelCounts: prob = float(labelCounts[key])/numEntries #以2為底求對數 shannonEnt -= prob * log(prob,2) return shannonEnt#按照給定特徵劃分數據集def spiltDataSet(dataset, axis, value): #axis控制第幾列數據 #創建新的list retDataSet = [] for featVec in dataset: if featVec[axis] == value: #抽取 reducedFeatVec = featVec[:axis] #axis之前（不含axis）所有列的數據 reducedFeatVec.extend(featVec[axis+1:]) #axis+1及之後所有列的數據 retDataSet.append(reducedFeatVec) return retDataSet#選擇最好的數據集劃分方式def chooseBestFeatureToSpilt(dataset): numFeatures = len(dataset[0]) - 1 baseEntropy = calcShannonEnt(dataset) bestInfoGain = 0.0 bestFeature = -1 for i in range(numFeatures): #創建唯一的分類標籤列表 featList = [example[i] for example in dataset] # print(featList) uniqueVals = set(featList) # print(uniqueVals) newEntropy = 0.0 #計算每種劃分方式的信息熵 for value in uniqueVals: subDataSet = spiltDataSet(dataset, i, value) prob = len(subDataSet)/float(len(dataset)) newEntropy += prob*calcShannonEnt(subDataSet) infoGain = baseEntropy - newEntropy if (infoGain) > bestInfoGain: #計算最好的信息增益 bestInfoGain = infoGain bestFeature = i return bestFeature#決定葉子結點的分類def majorityCnt(classList): classCount = {} for vote in classList: if vote not in classCount.keys(): classCount[vote] = 0 classCount[vote] += 1 sortedClassCount = sorted(classCount.items(), key = operator.itemgetter(1), reverse = True) return sortedClassCount[0][0]#創建決策樹def createTree(dataSet, labels): classList = [example[-1] for example in dataSet] # print(classList) #類別完全相同則停止繼續劃分 if classList.count(classList[0]) == len(classList): return classList[0] #遍歷完所有特徵時返回出現次數最多的 if len(dataSet[0]) == 1: return majorityCnt(classList) bestFeat = chooseBestFeatureToSpilt(dataSet) bestFeatLabel = labels[bestFeat] myTree = {bestFeatLabel:{}} #得到列表包含的所有屬性值 del(labels[bestFeat]) featValues = [example[bestFeat] for example in dataSet] uniqueVals = set(featValues) for value in uniqueVals: subLabels = labels[:] myTree[bestFeatLabel][value] = createTree(spiltDataSet(dataSet, bestFeat, value), subLabels) return myTreemyDat, labels = createDataset()print(calcShannonEnt(myDat))print(spiltDataSet(myDat, 0, 1))print(chooseBestFeatureToSpilt(myDat))myTree = createTree(myDat, labels)print(myTree) #輸出嵌套的字典，不形象直觀，後續繪製成決策樹形式

參考鏈接：

分類演算法之決策樹

數據挖掘面試題之決策樹必知必會

未經許可，禁止轉載！！！