①Aggregation Model

回顧上一篇文章講到的聚合模型袄友，三個(gè)臭皮匠頂一個(gè)諸葛亮。于是出現(xiàn)了blending磁滚，bagging逼庞，boost，stacking闺鲸。blending有uniform和non-uniform筋讨，stacking是屬于條件類(lèi)的，而boost里面的Adaboost是邊學(xué)習(xí)邊做linear翠拣，bagging也是屬于邊學(xué)習(xí)邊做uniform的版仔。Decision Tree就是屬于邊做學(xué)習(xí)然后按照條件分的一種。如下圖误墓，aggregation model就是是補(bǔ)全了：

②Decision Tree Hypothesis

決策樹(shù)是一種很傳統(tǒng)的算法蛮粮，出現(xiàn)的很早，例如下面谜慌，按照下班時(shí)間然想，是否約會(huì)，提交截止時(shí)間進(jìn)行判斷欣范，和人的處理方式很像：

Strengths and Weaknesses
優(yōu)點(diǎn)：
模型直觀已日，便于理解，應(yīng)用很廣泛
簡(jiǎn)單栅屏，容易實(shí)現(xiàn)飘千。
訓(xùn)練和預(yù)測(cè)的時(shí)候，時(shí)間短預(yù)測(cè)準(zhǔn)確率高
缺點(diǎn)
缺少足夠的理論支持栈雳，后面給出的VC dimension沒(méi)有什么太完備的道理占婉。
對(duì)于找到合適的樹(shù)要花額外的時(shí)間。
決策樹(shù)代表性的演算法比較少

③Decision Tree Algorithm

根據(jù)上面的公式甫恩，基本算法：

base algorithm

常用決策樹(shù)算法模型——CART

CART算法對(duì)決策樹(shù)算法追加了一些限制：
①c = 2笛洛，分支的個(gè)數(shù)要等于2，和二叉樹(shù)有點(diǎn)想乃坤。
②本著g(x)simplify的原則苛让，g(x)規(guī)定他就是一個(gè)常數(shù)沟蔑，也就是類(lèi)別。
③按照Ein最小化的原則每一次選擇condition狱杰。

④purifying

純凈度其實(shí)就是熵了。熵是代表混亂程度的吴侦。幾個(gè)比較常見(jiàn)的算法：ID3屋休，ID4.5，gini系數(shù)备韧。

ID3

以信息論為基礎(chǔ)劫樟，以信息熵和信息增益為衡量標(biāo)準(zhǔn)，從而實(shí)現(xiàn)對(duì)數(shù)據(jù)的歸納分類(lèi)织堂。

熵

ID4.5

改進(jìn)就是ID4.5了荐糜，這個(gè)就不是信息增益了巷怜，是信息增益率。

第c個(gè)子集的信息熵

信息增益率

CART

Cart算法里面用的是gini系數(shù)务豺，但是還是有必要說(shuō)一下decision tree做擬合的時(shí)候Ein要怎么optimal磨总。

regression

對(duì)于regression問(wèn)題，首先想到的肯定是均方差了：

均方差

y桿就是yn的平均笼沥。

classification

對(duì)于分類(lèi)：

表示類(lèi)別最多的蚪燕。

以上都是借鑒前面algorithm的思想推導(dǎo)的，現(xiàn)在回到純度奔浅。想要purity最小邻薯，那么就是y

classification error

Gini

可以看到gini系數(shù)和熵差不了多少营勤，一定程度上可以代表熵。

對(duì)于CART的Teminal condition壹罚，自然就是兩個(gè)條件：1.首先是yn只有一個(gè)種類(lèi)葛作，分不了了。2.其次就是Xn都是一樣的不能再分猖凛。

⑤Decision Tree Heuristics in CART

基本流程：

可以看到CART算法在處理binary classification和regression問(wèn)題時(shí)非常簡(jiǎn)單實(shí)用赂蠢，而且，處理muti-class classification問(wèn)題也十分容易辨泳。
但是要注意一個(gè)問(wèn)題虱岂，既然有錯(cuò)誤就分玖院，那么到最后肯定是一個(gè)二分完全樹(shù)，Ein一定是0第岖，這樣是有過(guò)擬合的难菌。對(duì)于overfit，要引入的就是過(guò)擬合：

regularization

這里其實(shí)就是剛剛說(shuō)的decision tree理論不是特別的完善，事實(shí)上NumberOfLeaves ≈ Ω其實(shí)我們?cè)趯?shí)踐中得到的银亲。因?yàn)槿~子越多復(fù)雜度越大慢叨。所以就直接把葉子數(shù)量當(dāng)做是復(fù)雜度Ω了。

在決策樹(shù)中預(yù)測(cè)中务蝠，還會(huì)遇到一種問(wèn)題拍谐，就是當(dāng)某些特征缺失的時(shí)候，沒(méi)有辦法進(jìn)行切割和分支選擇馏段。一種常用的方法就是surrogate branch轩拨，即尋找與該特征相似的替代feature。如何確定是相似的feature呢院喜？做法是在決策樹(shù)訓(xùn)練的時(shí)候亡蓉，找出與該特征相似的feature，如果替代的feature與原feature切割的方式和結(jié)果是類(lèi)似的喷舀，那么就表明二者是相似的砍濒，就把該替代的feature也存儲(chǔ)下來(lái)。當(dāng)預(yù)測(cè)時(shí)遇到原feature缺失的情況硫麻，就用替代feature進(jìn)行分支判斷和選擇爸邢。

⑥D(zhuǎn)ecision Tree in action

貌似和Adaboost很像啊拿愧！

最后在總結(jié)一下：

⑦代碼實(shí)現(xiàn)Decision Tree

包括創(chuàng)建樹(shù)杠河，預(yù)測(cè)，可視化樹(shù)，這篇東西內(nèi)容不多券敌，代碼講解多唾戚。
首先引入一個(gè)計(jì)算gini系數(shù)：

def cal_gini(data):
  '''calculate the gini index
  input:data(list)
  output:gini(float)
  '''
  total_sample = len(data)
  if total_sample == 0:
      return 0
  label_count = label_uniqueness(data)
  gini = 0
  for label in label_count:
      gini = gini + pow(label_count[label] , 2)
  gini = 1 - float(gini) / pow(total_sample , 2)
  return gini
  pass

傳進(jìn)的是一個(gè)list，計(jì)算這個(gè)list里面label數(shù)量陪白，然后統(tǒng)計(jì)gini系數(shù)返回颈走。
還有一個(gè)分別計(jì)算類(lèi)別數(shù)量的函數(shù)，剛剛的gini系數(shù)用到的：

def label_uniqueness(data):
  '''Counting the number of defferent labels in the dataset
  input:dataset
  output:Number of labels
  '''
  label_uniq = {}
  for x in data:
      label = x[len(x) - 1]
      if label not in label_uniq:
          label_uniq[label] = 0
      label_uniq[label] += 1
  return label_uniq
  pass

這個(gè)就是tool文件里面的咱士。
創(chuàng)建節(jié)點(diǎn)node：

class node:
  '''Tree node
  '''
  def __init__(self , fea = -1, value = None, results = None, right = None, left = None):
      '''
      initialization function
      :param fea:column index value
      :param value:split value
      :param results:The class belongs to
      :param right:right side
      :param left:left side
      '''
      self.fea = fea
      self.value = value
      self.results = results
      self.right = right
      self.left = left
      pass

fea就是當(dāng)前分割的維度立由，value就是分割的值，result就是label序厉，right右子樹(shù)锐膜，left左子樹(shù)。
接下來(lái)就是主要?jiǎng)?chuàng)建樹(shù)的類(lèi)了：

class decision_tree(object):

  def build_tree(self,data):
      '''Create decision tree
      input:data
      output:root
      '''
      if len(data) == 0:
          return node()

      currentGini = tool.cal_gini(data)
      bestGain = 0.0
      bestCriterria = None # store the optimal cutting point
      bestSets = None # store two datasets which have been splited

      feature_num = len(data[0]) - 1 # Number of features
      for fea in range(0 , feature_num):
          feature_values = {}
          for sample in data:
              feature_values[sample[fea]] = 1 # store the value in the demension fea possibly
          for value in feature_values.keys():
              (set_first, set_second) = self.split_tree(data, fea, value)
              nowGini = float(len(set_first) * tool.cal_gini(set_first) + len(set_second) * tool.cal_gini(set_second)) / len(data)
              gain = currentGini - nowGini
              if gain > bestGain and len(set_first) > 0 and len(set_second) > 0:
                  bestGain = gain
                  bestCriterria = (fea , value)
                  bestSets = (set_first , set_second)
              pass
      if bestGain > 0:
          right = self.build_tree(bestSets[0])
          left = self.build_tree(bestSets[1])
          return node(fea = bestCriterria[0], value = bestCriterria[1], right = right, left = left)
      else:
          return node(results=tool.label_uniqueness(data))

  def split_tree(self , data , fea , value):
      '''split the dataset according demension and value
      input:data
      output:two data
      '''
      set_first = []
      set_second = []
      for x in data:
          if x[fea] >= value:
              set_first.append(x)
          else:
              set_second.append(x)
      return (set_first, set_second)
      pass

  def predict(self, sample, tree):
      '''prediction
      input:sample, the tree which we have been built
      output:label
      '''
      if tree.results != None:
          return tree.results

      else:
          val_sample = sample[tree.fea]
          branch = None
          if val_sample >= tree.value:
              branch = tree.right
          else:
              branch = tree.left
          return self.predict(sample, branch)

  def predcit_samples(self, samples, tree):
      predictions = []
      for sample in samples:
          predictions.append(self.predict(sample, tree))
      return predictions

  pass

其實(shí)很簡(jiǎn)單弛房，就是按照f(shuō)eature和value分類(lèi)道盏。忘了這個(gè)是前向還是后向了，我是看那個(gè)二叉樹(shù)跟著搞的文捶，大一的時(shí)候?qū)W過(guò)荷逞，過(guò)了半年差不多忘光了。
看看預(yù)測(cè)效果吧粹排！
使用的數(shù)據(jù)還是iris數(shù)據(jù)集种远，可視化還得降維，麻煩顽耳，于是就是可視化樹(shù)了坠敷，發(fā)現(xiàn)更麻煩：

if __name__ == '__main__':
  print('load_data......')
  dataSet = load_data()
  data = dataSet.data
  target = dataSet.target
  dataframe = pd.DataFrame(data = data, dtype = np.float32)
  dataframe.insert(4, 'label', target)
  dataMat = np.mat(dataframe)

  '''test and train
  '''
  X_train, X_test, y_train, y_test = train_test_split(dataMat[:, 0:-1], dataMat[:, -1], test_size=0.3, random_state=0)
  data_train = np.hstack((X_train, y_train))
  data_train = data_train.tolist()
  X_test = X_test.tolist()
  tree = decisionTree.decision_tree()
  tree_root = tree.build_tree(data_train)
  predictions = tree.predcit_samples(X_test, tree_root)
  pres = []
  for i in predictions:
      pres.append(list(i.keys()))

  y_test = y_test.tolist()
  accuracy = 0
  for i in range(len(y_test)):
      if y_test[i] == pres[i]:
          accuracy += 1
  print('Accuracy : ', accuracy / len(y_test))

準(zhǔn)確率還是蠻高的。
首先要求樹(shù)的葉子數(shù)：
一樣是遞歸射富。

def getNumLeafs(myTree):
  if myTree == None:
      return 0
  elif myTree.right == None and myTree.left == None:
      return 1
  else:
      return getNumLeafs(myTree.right) + getNumLeafs(myTree.left)

然后是求深度：

def getDepth(myTree):
  if myTree == None:
      return 0
  right = getDepth(myTree.right)
  left = getDepth(myTree.left)
  return max(right+1, left+1)

之后就是畫(huà)節(jié)點(diǎn)了膝迎，求深度和葉子數(shù)只是想著可以按照深度把樹(shù)畫(huà)的分開(kāi)點(diǎn)。
還有一個(gè)裝parent節(jié)點(diǎn)坐標(biāo)的：

class TreeNode(object):
  def __init__(self, x, y, parentX = None, parentY = None):
      self.x = x
      self.y = y
      self.parentX = parentX
      self.parentY = parentY
  pass

最后就是主要的畫(huà)圖了：

def drawNode(x, y ,parent,color, marker, myTree, position):
  if myTree.results == None or len(list(myTree.results.keys())) > 1:
      plt.scatter(x, y, c=color, marker=marker, s=200)

  if myTree.right == None and myTree.left == None:
      results = list(myTree.results.keys())
      plt.annotate(s = 'label == ' + str(results[0]), xy=(x - 15, y))
      if results[0] == 0.0:
         plt.annotate(s='label == 0.0', xy=(x , y))
         plt.scatter(x, y, c='orange', marker='H', s=100)
      if results[0] == 1.0:
         plt.scatter(x, y, c='pink', marker='8', s=100)
      if results[0] == 2.0:
         plt.scatter(x, y, c='r', marker='+', s=100)

  if myTree.value != None and myTree.fea != None:
      po = 5
      if position == 'right':
         plt.annotate(s = 'dimension' + str(myTree.fea) + '>' + str(round(myTree.value, 2)), xy = (x-25 - po, y))
      else:
         plt.annotate(s='dimension' + str(myTree.fea) + '>' + str(round(myTree.value, 2)), xy=(x - 25 + po, y))
  if parent != None:
     plt.plot([x, parent.x], [y, parent.y], color = 'gray', alpha = 0.5)
def draw(myTree, parent = None, x = 100, y = 100, color = 'r', marker = '^', position = None):
  NumberLeaf = getNumLeafs(myTree)
  Depth = getDepth(myTree)
  delta = (NumberLeaf+Depth)
  drawNode(x, y, parent, color, marker, myTree,position)
  if myTree.right != None:
      draw(myTree.right, parent=TreeNode(x, y) ,x=x+5*delta, y=y-5-delta,color='b', marker='x', position='right')
  if myTree.left != None:
      draw(myTree.left,parent=TreeNode(x, y) ,x=x-5*delta, y=y-2-delta, color='g', marker='o', position='left')
  pass

加上這句 plt.annotate(s='label == 0.0', xy=(x , y))是因?yàn)槟莻€(gè)注釋死活畫(huà)不出來(lái)胰耗，應(yīng)該是擋住了限次。主要還是draw函數(shù)，drawNode只是畫(huà)而已柴灯，判斷都是為了加注釋的卖漫，來(lái)看看效果圖：

如果當(dāng)時(shí)學(xué)數(shù)據(jù)結(jié)構(gòu)用的是python多好！

所有代碼在GitHub上：
https://github.com/GreenArrow2017/MachineLearning/tree/master/MachineLearning/DecisionTree