決策樹ID3原理及R語言python程式碼實現（西瓜書）

2019 年 10 月 3 日
筆記

決策樹ID3原理及R語言python程式碼實現（西瓜書）

摘要：

決策樹是機器學習中一種非常常見的分類與回歸方法，可以認為是if-else結構的規則。分類決策樹是由節點和有向邊組成的樹形結構，節點表示特徵或者屬性，
而邊表示的是屬性值，邊指向的葉節點為對應的分類。在對樣本的分類過程中，由頂向下，根據特徵或屬性值選擇分支，遞歸遍歷直到葉節點，將實例分到葉節點對應的類別中。
決策樹的學習過程就是構造出一個能正取分類（或者誤差最小）訓練數據集的且有較好泛化能力的樹，核心是如何選擇特徵或屬性作為節點，
通常的演算法是利用啟發式的演算法如ID3，C4.5，CART等遞歸的選擇最優特徵。選擇一個最優特徵，然後按照此特徵將數據集分割成多個子集，子集再選擇最優特徵，
直到所有訓練數據都被正取分類，這就構造出了決策樹。決策樹有如下特點：

原理簡單, 計算高效；使用基於資訊熵相關的理論劃分最優特徵，原理清晰，計算效率高。
解釋性強；決策樹的屬性結構以及if-else的判斷邏輯，非常符合人的決策思維，使用訓練數據集構造出一個決策樹後，可視化決策樹，
可以非常直觀的理解決策樹的判斷邏輯，可讀性強。
效果好，應用廣泛;其擬合效果一般很好，分類速度快，但也容易過擬合，決策樹擁有非常廣泛的應用。

本文主要介紹基於ID3的演算法構造決策樹。

決策樹原理

訓練數據集有多個特徵，如何遞歸選擇最優特徵呢？資訊熵增益提供了一個非常好的也非常符合人們日常邏輯的判斷準則，即資訊熵增益最大的特徵為最優特徵。在資訊理論中，熵是用來度量隨機變數不確定性的量綱，熵越大，不確定性越大。熵定義如下:

此處log一般是以2為底，假設一個產品成品率為100%次品率為0%那麼熵就為0，如果是成品率次品率各為50%，那麼熵就為1，熵越大，說明不確定性越高，非常符合我們人類的思維邏輯。假設分類標記為隨機變數Y，那麼H(Y)表示隨機變數Y的不確定性，我們依次選擇可選特徵，如果選擇一個特徵後，隨機變數Y的熵減少的最多，表示得知特徵X後，使得類Y不確定性減少最多，那麼就把此特徵選為最優特徵。資訊熵增益的公式如下：

ID3演算法

決策樹基於資訊熵增益的ID3演算法步驟如下：

如果數據集類別只有一類，選擇這個類別作為，標記為葉節點。
從數據集的所有特徵中，選擇資訊熵增益最大的作為節點，特徵的屬性分別作為節點的邊。
選擇最優特徵後，按照對應的屬性，將數據集分成多個，依次將子數據集從第1步遞歸進行構造子樹。

python實現

#encoding:utf-8    import pandas as pd  import numpy  as np    class DecisionTree:      def __init__(self):          self.model = None      def calEntropy(self, y): # 計算熵          valRate = y.value_counts().apply(lambda x : x / y.size) # 頻次匯總 得到各個特徵對應的概率          valEntropy = np.inner(valRate, np.log2(valRate)) * -1          return valEntropy        def fit(self, xTrain, yTrain = pd.Series()):          if yTrain.size == 0:#如果不傳，自動選擇最後一列作為分類標籤              yTrain = xTrain.iloc[:,-1]              xTrain = xTrain.iloc[:,:len(xTrain.columns)-1]          self.model = self.buildDecisionTree(xTrain, yTrain)          return self.model      def buildDecisionTree(self, xTrain, yTrain):          propNamesAll = xTrain.columns          #print(propNamesAll)          yTrainCounts = yTrain.value_counts()          if yTrainCounts.size == 1:              #print('only one class', yTrainCounts.index[0])              return yTrainCounts.index[0]          entropyD = self.calEntropy(yTrain)            maxGain = None          maxEntropyPropName = None          for propName in propNamesAll:              propDatas = xTrain[propName]              propClassSummary = propDatas.value_counts().apply(lambda x : x / propDatas.size)# 頻次匯總 得到各個特徵對應的概率                sumEntropyByProp = 0              for propClass, dvRate in propClassSummary.items():                  yDataByPropClass = yTrain[xTrain[propName] == propClass]                  entropyDv = self.calEntropy(yDataByPropClass)                  sumEntropyByProp += entropyDv * dvRate              gainEach = entropyD - sumEntropyByProp              if maxGain == None or gainEach > maxGain:                  maxGain = gainEach                  maxEntropyPropName = propName          #print('select prop:', maxEntropyPropName, maxGain)          propDatas = xTrain[maxEntropyPropName]          propClassSummary = propDatas.value_counts().apply(lambda x : x / propDatas.size)# 頻次匯總 得到各個特徵對應的概率            retClassByProp = {}          for propClass, dvRate in propClassSummary.items():              whichIndex = xTrain[maxEntropyPropName] == propClass              if whichIndex.size == 0:                  continue              xDataByPropClass = xTrain[whichIndex]              yDataByPropClass = yTrain[whichIndex]              del xDataByPropClass[maxEntropyPropName]#刪除已經選擇的屬性列                #print(propClass)              #print(pd.concat([xDataByPropClass, yDataByPropClass], axis=1))                retClassByProp[propClass] = self.buildDecisionTree(xDataByPropClass, yDataByPropClass)            return {'Node':maxEntropyPropName, 'Edge':retClassByProp}      def predictBySeries(self, modelNode, data):          if not isinstance(modelNode, dict):              return modelNode          nodePropName = modelNode['Node']          prpVal = data.get(nodePropName)          for edge, nextNode in modelNode['Edge'].items():              if prpVal == edge:                  return self.predictBySeries(nextNode, data)          return None      def predict(self, data):          if isinstance(data, pd.Series):              return self.predictBySeries(self.model, data)          return data.apply(lambda d: self.predictBySeries(self.model, d), axis=1)    dataTrain = pd.read_csv("xiguadata.csv", encoding = "gbk")    decisionTree = DecisionTree()  treeData = decisionTree.fit(dataTrain)  print(pd.DataFrame({'預測值':decisionTree.predict(dataTrain), '正取值':dataTrain.iloc[:,-1]}))    import json  print(json.dumps(treeData, ensure_ascii=False))

訓練結束後，使用一個遞歸的字典保存決策樹模型，使用格式json工具格式化輸出後，可以簡潔的看到樹的結構。

R語言實現

    dataTrain <- read.csv("xiguadata.csv", header = TRUE)    trainDecisionTree <- function(dataTrain){      calEntropy <- function(y){ # 計算熵            values <- table(unlist(y)); # 頻次匯總 得到各個特徵對應的概率            valuesRate <- values / sum(values);            logVal = log2(valuesRate);# log2(0) == infinite          logVal[is.infinite(logVal)]=0;            valuesEntropy <- -1 * t(valuesRate) %*% logVal;          if (is.nan(valuesEntropy)){              valuesEntropy = 0;          }          return(valuesEntropy);      }        propNamesAll <- names(dataTrain)      propNamesAll <- propNamesAll[length(propNamesAll) * - 1]      print(propNamesAll)      buildDecisionTree <- function(propNames, dataSet){              classColumn = dataSet[, length(dataSet)]#最後一列是類別標籤            classSummary <- table(unlist(classColumn))# 頻次匯總            defaultRet = c(propNames[1], names(classSummary)[which.max(classSummary)]);          if (length(classSummary) == 1){#如果所有的都是同一類別，那麼標記為葉節點              return(defaultRet);          }          if (length(propNames) == 1){#如果只剩一種屬性了，那麼返回樣本數量最多的類別作為節點              return(defaultRet);          }          entropyD <- calEntropy(classColumn)          propGains = sapply(propNames, function(propName){ # propName 對應的是"色澤" "根蒂" "敲聲" "紋理" "臍部" "觸感"              propDatas <- dataSet[c(propName)]                propClassSummary <- table(unlist(propDatas))# 頻次匯總                retGain <- sapply(names(propClassSummary), function(propClass){# propClass 對應色澤的種類 如 淺白 青綠 烏黑                  dataByPropClass <- subset(dataSet, dataSet[c(propName)] == propClass); #篩選出色澤等於 種類 propClass 的數據集                  entropyDv <- calEntropy(dataByPropClass[, length(dataByPropClass)]) #最後一列是標記是否為好瓜                  Dv = propClassSummary[c(propClass)][1]                  return(entropyDv * Dv);# 這裡沒有直接除|D|,最後累加後再除，等價的              });                return(entropyD - sum(retGain)/sum(propClassSummary));          });          #print(propGains);          maxEntropyProp = propGains[which.max(propGains)];#選擇資訊熵增益最大的屬性          propName = names(maxEntropyProp)[1]          #print(propName)          propDatas <- dataSet[c(propName)]            propClassSummary <- table(unlist(propDatas))# 頻次匯總            propClassSummary <- propClassSummary[which(propClassSummary > 0)]          propClassNames <- names(propClassSummary)            #propClassNames = c(propClassNames[1])          retGain <- sapply(propClassNames, function(propClass){# propClass 對應色澤的種類 如 淺白 青綠 烏黑                dataByPropClass <- subset(dataSet, dataSet[c(propName)] == propClass); #篩選出色澤等於 種類 propClass 的數據集              leftClassNames = propNames[which(propNames==propName) * -1] #去掉這個屬性，遞歸構造決策樹              ret = buildDecisionTree(leftClassNames, dataByPropClass);              return(ret);          });          #names(retGain) = propClassNames          retList = retGain          #retList = list()          #for (propClass in propClassNames){          #    retList[propClass] = retGain[propClass]          #}          #print(retList)            #索引1表示選擇的屬性名稱 索引2對應的類別，如果有子樹那麼就是frame，否則就是類別          ret  = list(propName, retList)          #ret = data.frame(c(retList))          #names(ret) = c(propName)          return(ret);      }      retProp = buildDecisionTree(propNamesAll, dataTrain);      return(retProp);  }  decisionTree = trainDecisionTree(dataTrain)  #print(decisionTree)      library("rpart")  library("rpart.plot")  dataTrain <- read.csv("xiguadata.csv", header = TRUE)  print(dataTrain)  fit <- rpart(HaoGua~.,data=dataTrain,control = rpart.control(minsplit = 1, minbucket = 1),method="class")  printcp(fit)    rpart.plot(fit, branch = 1, branch.type = 1, type = 2, extra = 102,shadow.col='gray', box.col='green',border.col='blue', split.col='red',main="DecisionTree")    #library(jsonlite)  #dataJson = toJSON(decisionTree)  #c <- file( "result.txt", "w" )  #writeLines(dataJson, c )  #close( c )   #這裡需要主動關閉文件    #for (k in propNames) {  #    eachData <- dataSet[c(k)]  #    values <- table(unlist(eachData))# 頻次匯總  #    #print(values)  #    print(k)  #    total <- 0  #    for (m in names(values)) {  #        #print(m)  #        #print(values[m][1])  #        data3 <- subset(dataSet, dataSet[c(k)] == m)  #        entropyDv <- calEntropy(data3[, length(data3)])  #        #print(entropyDv)  #        total = total + entropyDv*values[c(m)][1]  #    }  #    GainDv <- entropyD - total /  sum(values);+  #    print(GainDv)  #}

R語言程式碼包含本人自己編寫的R語言ID3演算法，最後使用R的rpart包訓練了一個決策樹。

總結：

ID3演算法簡潔清晰，符合人類思路方式。
決策樹的解釋性強，可視化後也方便理解模型和驗證正確性。
ID3演算法時候標籤類特徵的樣本，對應具有連續型數值的特徵，無法運行此演算法。
有過擬合的風險，要通過剪枝來避免過擬合。
資訊增益有時候偏愛屬性很多的特徵，C4.5和CART演算法可以對此有優化。
這是我的github主頁https://github.com/fanchy，有些有意思的分享。
python相比R語言寫起來還是溜多了，主要是遍歷和嵌套，python比R要容易很多，R的數據篩選和選擇方便一點，這個python版本的id3演算法寫的還是很清晰簡潔的正是Talk is cheap. Show me the code。這是在網上可以看到原生實現版本中，最精簡的版本之一。

對應的西瓜書數據集為

色澤  根蒂  敲聲  紋理  臍部  觸感  HaoGua  青綠  蜷縮  濁響  清晰  凹陷  硬滑  是  烏黑  蜷縮  沉悶  清晰  凹陷  硬滑  是  烏黑  蜷縮  濁響  清晰  凹陷  硬滑  是  青綠  蜷縮  沉悶  清晰  凹陷  硬滑  是  淺白  蜷縮  濁響  清晰  凹陷  硬滑  是  青綠  稍蜷  濁響  清晰  稍凹  軟粘  是  烏黑  稍蜷  濁響  稍糊  稍凹  軟粘  是  烏黑  稍蜷  濁響  清晰  稍凹  硬滑  是  烏黑  稍蜷  沉悶  稍糊  稍凹  硬滑  否  青綠  硬挺  清脆  清晰  平坦  軟粘  否  淺白  硬挺  清脆  模糊  平坦  硬滑  否  淺白  蜷縮  濁響  模糊  平坦  軟粘  否  青綠  稍蜷  濁響  稍糊  凹陷  硬滑  否  淺白  稍蜷  沉悶  稍糊  凹陷  硬滑  否  烏黑  稍蜷  濁響  清晰  稍凹  軟粘  否  淺白  蜷縮  濁響  模糊  平坦  硬滑  否  青綠  蜷縮  沉悶  稍糊  稍凹  硬滑  否

Tags: