Decision Tree

①Aggregation Model

回顾上一篇文章讲到的聚合模型,三个臭皮匠顶一个诸葛亮。于是出现了blending,bagging,boost,stacking。blending有uniform和non-uniform,stacking是属于条件类的,而boost里面的Adaboost是边学习边做linear,bagging也是属于边学习边做uniform的。Decision Tree就是属于边做学习然后按照条件分的一种。如下图,aggregation model就是是补全了:

②Decision Tree Hypothesis

决策树是一种很传统的算法,出现的很早,例如下面,按照下班时间,是否约会,提交截止时间进行判断,和人的处理方式很像:

上面的菱形就像是很简单的分割平面,而箭头就是判断过程,其实就是学习过程,最后的Y和N就是分出来的结果。可以对应到下面的式子:

最后那些小小的Y,N就是g(x),和之前的SVM他们都不太一样,这里的g(x)通常就是一个常数了,也叫base hypothesis;箭头就是q(x)判断条件,红色就是找到了最好split method的地方。 从另一个方面来看决策树:

和上面理解是一样的。

Strengths and Weaknesses 优点: 模型直观,便于理解,应用很广泛 简单,容易实现。 训练和预测的时候,时间短预测准确率高 缺点 缺少足够的理论支持,后面给出的VC dimension没有什么太完备的道理。 对于找到合适的树要花额外的时间。 决策树代表性的演算法比较少

③Decision Tree Algorithm

根据上面的公式,基本算法:

base algorithm

按照决策树执行流程,可以分成四个部分:

首先学习设定划分不同分支的标准和条件是什么;接着将整体数据集D根据分支个数C和条件,划为不同分支下的子集Dc;然后对每个分支下的Dc进行训练,得到相应的机器学习模型Gc;最后将所有分支下的Gc合并到一起,组成大矩G(x)。但值得注意的是,这种递归的形式需要终止条件,否则程序将一直进行下去。当满足递归的终止条件之后,将会返回基本的hypothesis gt(x)。 所以,包含了四个基本算法选择: 分支个数 分支条件 终止条件 基本算法

常用决策树算法模型——CART

CART算法对决策树算法追加了一些限制: ①c = 2,分支的个数要等于2,和二叉树有点想。 ②本着g(x)simplify的原则,g(x)规定他就是一个常数,也就是类别。 ③按照Ein最小化的原则每一次选择condition。

其实决策树的分类有点像Adaboost的stump分类。但是Adaboost的stump仅仅是按照准确率来了,而decision tree的标准是purity,纯净度。意思就是熵了。purifying的核心思想就是每次切割都尽可能让左子树和右子树中同类样本占得比例最大或者yn都很接近(regression),即错误率最小。比如说classifiacation问题中,如果左子树全是正样本,右子树全是负样本,那么它的纯净度就很大,说明该分支效果很好。

所以主要问题就变成了如何寻找纯净度最好的问题了。

④purifying

纯净度其实就是熵了。熵是代表混乱程度的。几个比较常见的算法:ID3,ID4.5,gini系数。

ID3

以信息论为基础,以信息熵和信息增益为衡量标准,从而实现对数据的归纳分类。

信息增益,就是指split前后熵的变化,选择最好的一个,也就是说由于使用这个属性分割样例而导致的期望熵降低。信息增益就是原有信息熵与属性划分后信息熵(需要对划分后的信息熵取期望值)的差值。 但是他的缺点也很明显: 1.没有剪枝过程,为了去除过渡数据匹配的问题,可通过裁剪合并相邻的无法产生大量信息增益的叶子节点。因为选择的已经是最好的了,如果合并了肯定不够之前的好。 2.信息增益的方法偏向选择具有大量值的属性,也就是说某个属性特征索取的不同值越多,那么越有可能作为分裂属性,这样是不合理的。比如前面的ID编号,1/N再来个log很小的。 3.只可以处理离散分布的数据特征。这个很明显了,如果是连续型数据,很难分的。 基于以上缺点又改进了一下。

ID4.5

改进就是ID4.5了,这个就不是信息增益了,是信息增益率。

第c个子集的信息熵

信息增益率

信息增益率是信息增益与信息熵的比例 这样的改进其实就是使得离散化可以连续化而已,二分就好了。 优点: 1.面对数据遗漏和输入字段很多的问题时非常稳健。 2.通常不需要很长的训练次数进行估计。工作原理是基于产生最大信息增益的字段逐级分割样本。 3.比一些其他类型的模型易于理解,模型推出的规则有非常直观的解释。 4.允许进行多次多于两个子组的分割。目标字段必须为分类字段。

CART

Cart算法里面用的是gini系数,但是还是有必要说一下decision tree做拟合的时候Ein要怎么optimal。

regression

对于regression问题,首先想到的肯定是均方差了:

均方差

y杆就是yn的平均。

classification

对于分类:

y表示类别最多的。

以上都是借鉴前面algorithm的思想推导的,现在回到纯度。想要purity最小,那么就是y要多了,最好全部都是了,所以classification error:

classification error

上面的只是考虑了分支最大的,我们需要把所有的都考虑进去,于是:

gini系数就出来了:

Gini

可以看到gini系数和熵差不了多少,一定程度上可以代表熵。

对于CART的Teminal condition,自然就是两个条件:1.首先是yn只有一个种类,分不了了。2.其次就是Xn都是一样的不能再分。

⑤Decision Tree Heuristics in CART

基本流程:

可以看到CART算法在处理binary classification和regression问题时非常简单实用,而且,处理muti-class classification问题也十分容易。 但是要注意一个问题,既然有错误就分,那么到最后肯定是一个二分完全树,Ein一定是0,这样是有过拟合的。对于overfit,要引入的就是过拟合:

regularization

既然是过拟合了,这棵树不要这么大就行了,于是进行修剪,pruning,剪枝操作。比如,总共是10片叶子,我们取掉1片,剩下9片,9种情况,我们比较这9种情况哪种好。

这里其实就是刚刚说的decision tree理论不是特别的完善,事实上NumberOfLeaves ≈ Ω其实我们在实践中得到的。因为叶子越多复杂度越大。所以就直接把叶子数量当做是复杂度Ω了。

在决策树中预测中,还会遇到一种问题,就是当某些特征缺失的时候,没有办法进行切割和分支选择。一种常用的方法就是surrogate branch,即寻找与该特征相似的替代feature。如何确定是相似的feature呢?做法是在决策树训练的时候,找出与该特征相似的feature,如果替代的feature与原feature切割的方式和结果是类似的,那么就表明二者是相似的,就把该替代的feature也存储下来。当预测时遇到原feature缺失的情况,就用替代feature进行分支判断和选择。

⑥Decision Tree in action

貌似和Adaboost很像啊!

最后在总结一下:

⑦代码实现Decision Tree

包括创建树,预测,可视化树,这篇东西内容不多,代码讲解多。 首先引入一个计算gini系数:

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

传进的是一个list,计算这个list里面label数量,然后统计gini系数返回。 还有一个分别计算类别数量的函数,刚刚的gini系数用到的:

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

这个就是tool文件里面的。 创建节点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就是当前分割的维度,value就是分割的值,result就是label,right右子树,left左子树。 接下来就是主要创建树的类了:

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

其实很简单,就是按照feature和value分类。忘了这个是前向还是后向了,我是看那个二叉树跟着搞的,大一的时候学过,过了半年差不多忘光了。 看看预测效果吧! 使用的数据还是iris数据集,可视化还得降维,麻烦,于是就是可视化树了,发现更麻烦:

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))

准确率还是蛮高的。 首先要求树的叶子数: 一样是递归。

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)

之后就是画节点了,求深度和叶子数只是想着可以按照深度把树画的分开点。 还有一个装parent节点坐标的:

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

最后就是主要的画图了:

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))是因为那个注释死活画不出来,应该是挡住了。主要还是draw函数,drawNode只是画而已,判断都是为了加注释的,来看看效果图:

如果当时学数据结构用的是python多好!

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

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 从yield 到yield from再到python协程

    yield 是在:PEP 255 -- Simple Generators 这个pep引入的

    coders
  • Python与机器学习算法频道,文章和精华资料一键get

    以上,公众号后台,回复对应关键词,即可获取资料。希望能方便大家查阅,更多资料和原创好文,敬请期待。

    double
  • 浅谈unicode编码和utf-8编码的关系

    字符串编码在Python里边是经常会遇到的问题,特别是写文件以及网络传输的过程中,当调用某些函数的时候经常会遇到一些字符串编码提示错误,所以有必要弄清楚这些编码...

    Python进阶者
  • JavaScript获取本机浏览器UA助力Python爬取糗事百科首页

    使用Python编写爬虫时,经常会遇到反爬机制,例如网站要求必须使用浏览器访问。就像下面的403错误:

    Python小屋屋主
  • Python带我飞:50个有趣而又鲜为人知的Python特性

    Python, 是一个设计优美的解释型高级语言, 它提供了很多能让程序员感到舒适的功能特性。但有的时候, Python 的一些输出结果对于初学者来说似乎并不是那...

    新智元
  • 0473-如何使用Python3访问Kerberos环境的Hive和Impala

    随着Hadoop平台的流行,越来越多的开发语言访问Hadoop平台的组件,比较常见的Java、Scala、Python、R等。在前面的多篇文章中Fayson介绍...

    Fayson
  • 教你在Python中实现潜在语义分析(附代码)

    你有没有去过那种运营良好的图书馆?我总是对图书馆馆员通过书名、内容或其他主题保持一切井井有条的方式印象深刻。但是如果你给他们数千本书,要求他们根据书的种类整理出...

    数据派THU
  • 鲜为人知的 Python 语法

    所有人(好吧,不是所有人)都知道 python 是一门用途广泛、易读、而且容易入门的编程语言。但同时 python 语法也允许我们做一些很奇怪的事情。

    CSDN技术头条
  • 4种更快更简单实现Python数据可视化的方法

    数据可视化是数据科学或机器学习项目中十分重要的一环。通常,你需要在项目初期进行探索性的数据分析(EDA),从而对数据有一定的了解,而且创建可视化确实可以使分析的...

    机器之心
  • Python堆排序之heapq

    heapq模块实现了Python中的堆排序,并提供了有关方法。让用Python实现排序算法有了简单快捷的方式。

    小歪

扫码关注云+社区

领取腾讯云代金券