决策树建模 | 广阔天地，大有作为

[laiqun]

https://laiqun.github.io/2018/02/02/decision-tree/#more

[laiqun]

决策树的剪枝

利用前述方法来训练决策树会有一个问题，那就是决策树可能会变得过度拟合（overfitted），它训练处的模式只能代表训练集，泛化能力差。通俗的说，就像数学一样，你可以死记硬背，也可以用公式融合贯通，过拟合就相当于死记硬背的效果。一个过度拟合的树的表现是创建分支后，熵只有轻微的改变，而且这个分支的条件显得很随意。

真实世界中的决策树
由于决策树具有易于解释的特点，因此它是商务分析、医疗决策和政策指定领域里应用最为广泛的数据挖掘方法之一。通常，决策树的构造是自动进行的，专家们可以利用生成的决策树来理论问题的某些关机因素，然后对其加以改进，以便好好地与他的观点相匹配。这一过程允许机器协助专家进行决策，并清晰的展示出推导的路径，从而我们可以据此来判断预测的质量。
如今，决策树以这样的形式被广泛运用在众多应用系统之中，其中就包括了顾客调查、金融风险分析、辅助诊断和交通预测。

[laiqun]

因为前述算法知道无法进一步降低熵的时候才会停止分支的创建过程，所以一种可能的解决方法是，只要当熵的减少的数量小于某个最小值时，我们就停止分支的创建。这种策略常常被人们采用，但是它有一个小小的缺陷——我们有可能遇到这样的训练集：某一次分支的创建并不会令熵降低多少，但是随后创建的分支却会使熵大幅降低。对此，一种替代的策略是，先构造好如前面所述的整棵树，然后再尝试消除多于的节点。这个过程就是剪枝。

[laiqun]

剪枝的过程就是对具有相同父节点的一组节点进行检查，如果将其合并，熵的增加量是否小于某个指定的阈值。如果确实如此，那么久把这些叶节点合并成一个单一的节点。合并后的新节点包含了所有可能的结果值。这种做法有助于避免过度拟合的情况，也使得根据决策树做出的预测结果，不至于像从训练集得出结论那样具有特例性。

[laiqun]

def prune(tree,mingain):
  # 如果左右分支不是叶节点，则对其进行剪枝操作
  if tree.tb.results == None:
    prune(tree.tb,mingain)
  if tree.fb.results == None:
    prune(tree.fb,mingain)
  #如果两个分支都是叶节点，则判断它们是否需要合并
  if tree.tb.results!=None and tree.fb.results!=None:
    #构造合并后的数据集
    tb,fb=[],[]
    for value,count in tree.tb.results.items():
      tb+=[value]*count
    for value,count in tree.fb.results.items():
      fb+=[value]*count
    #检查熵减少的情况
    delta = entropy(tb,fb)-(entropy(tb)+entropy(fb))/2 
    #这里除上2与前面buildtree函数中的计算加权平均熵原理是一样的
    #这里假设了fb和tb含义的元素数量相等,tb+fb的元素数量就是tb或fb的两倍
    #假设元素数量相等只是一种估算
    if delta<mingain:
      #合并分支
      tree.tb,tree.fb = None,None
      tree.results = uniquecounts(tb+fb)

[laiqun]

当我们在根节点上调用上述函数时，算法将沿着树的所有路径向下遍历，直到只包含叶节点的节点处。
函数会将两个叶子节点中的结果组合起来形成一个新的列表，同时，对两个旧列表的熵的加权平均与新列表的熵值做比较，如果熵的变化小于mingain参数指定的数值，则叶节点会被删除，并且响应的结果值也将被全部移入父节点。随后，合并形成的新节点也可能会与其他节点合并，使它成为删除对象。

[laiqun]

针对当前数据集，尝试调用上述函数，看看是否有节点会被合并：

prune(tree,0.1)
printtree(tree)
#0:google?
  #T-> 3:21?
    #T-> {'Premium': 3}
    #F-> 2:yes?
       #T-> {'Basic': 1}
       #F-> {'None': 1}
  #F-> 0:slashdot?
    #T-> {'None': 3}
    #F-> 2:yes?
      #T-> {'Basic': 4}
      #F-> 3:21?
        #T-> {'Basic': 1}
        #F-> {'None': 3}
prune(tree,1.0)
printtree(tree)
#0:google?
  #T-> 3:21?
    #T-> {'Premium': 3}
    #F-> 2:yes?
      #T-> {'Basic': 1}
      #F-> {'None': 1}
  #F-> {'None': 6, 'Basic': 5}

[laiqun]

在这个例子中，数据的拆分很容易，因此根据一个合理的最小增益值进行剪枝，实际上没有多少工作量。只有我们将最小增益调整的非常大的时候，某些叶子节点才会合并。现实世界中数据集的拆分往往不会像这个例子一样干净利落，在这种情况下，剪枝的效果会更加的明显。

[laiqun]

决策树除了易于解释的优点外，还有一个优点就是处理缺失数据的能力。我们所使用的数据也许会缺失信息。比如：在当前的例子中，用户的的地理位置信息未必能够从其IP地址中识别出来，所以这一字段或许会为空。为了使决策树能够处理这种情况，我们需要实现一个新的预测函数。

[laiqun]

如果我们确实某些数据，而这些数据是确定分支走向所必须的，那么实际上我们可以选择两个分支都走。
如果该数据集数据完整，经过条件判断后，必然会走true分支或false分支中的一个，其权重为1。如果该数据集在判断条件的数据是缺失的，我们需要计算其true分支和false分支的权重，两个权重相加的和为1。

权重的计算方式为：该分支的数据集大小/(该分支的数据集大小+另一条分支的数据集大小)

[laiqun]

def mdclassify(observation,tree):
  if tree.results!=None:#如果到达了叶节点
    return tree.results
  else:
    v= observation[tree.col]
    if v== None:
      tr,fr= mdclassify(observation,tree.tb),mdclassify(observation,tree.fb)
      tcount,fcount=sum(tr.values()),sum(fr.values())
      tw = float(tcount)/(tcount+fcount)
      fw = float(fcount)/(tcount+fcount)
      result={}
      for ker,value in tr.items():
        result[k]=v*tw
      for ker,value in fr.items():
        if k not in result:
          result[k] = 0
        result[k]+=v*fw
      return result
    else:
      if isinstance(v,int) or isinstance(v,float):
        if v>=tree.value:
          branch = tree.tb
        else:
          branch = tree.fb
      else:
        if v == tree.value:
          branch = tree.tb
        else:
          branch = tree.fb
      return mdclassify(observation,branch)

[laiqun]

mdclassify与classify相比，唯一的区别在于末尾处：如果发现有重要的数据缺失，则每个分支的对应结果值都会被计算一遍，并且最终的结果值会乘上他们各自的权重。
我们来尝试一下mdclassify：

mdclassify(['google',None,'yes',None],tree)
#{'Premium': 2.25, 'Basic': 0.25}
mdclassify(['google','France',None,None],tree)
#{'None': 0.125, 'Premium': 2.25, 'Basic': 0.125}

补上计算图

正如前面估计的那样，忽略浏览网页数的结果将导致"premium"的概率偏大，而"Basic"的概率偏小。对于”是否阅读FAQ“变量的忽略则会导致另一种不同的分布。此处，每个概率值都会乘以相应的权重值。

[laiqun]

处理数值型的结果

用户购买行为预测和水果分类的例子都是分类问题，因为最终的结果是分类而不是数字。那如何处理数值型结果呢？
如果在以数字作为输出的结果集上建立分类问题的决策树，那么所有数字都将看作不同的分类，那么算法也不会考虑这样一个事实：有些数字彼此非常的接近，而其他的数字则相差甚远；而我们现在讲数字看作了完全的离散。为了解决这个问题，当我们对数值型数据集训练决策树时，可以使用方差作为评价函数，而不是使用基尼不纯度和熵。

def variance(rows):
  if len(rows)==0:
    return 0
  last_column = len(row)-1
  data = [float(row[last_column]) for row in rows]
  mean = sum(data)/len(data)
  variance = sum( [ (d-mean)**2 for d in data])/len(data)

该函数可以作为bulidtree的一个参数，它的作用是计算一个数据集的统计方差。偏低的方差代表数字批次都非常的接近，而偏高的方差意味着数据分散的很开。当使用方差作为评价函数来构造决策树时，我们选择节点判断条件的依据就变成了：拆分之后，数据较大者位于树的一侧，数字较小的位于树的另一侧，这样就可以降低分支的总体方差。

[laiqun]

什么时候使用决策树

或许决策树最大的优势就在它可以轻易地对一个受训模型给予解释。在本章的例子里，执行完算法程序之后，我们不仅可以得到一颗用以预测新用户的购买行为的决策树，而且还可以得到一个有助于我们做出判断的问题列表。从中我们可以发现，从Slashdot网站找到该网站的用户从来都不会成为付费用户。根据这一特点，我们可以调整我们的广告策略，使其更加倾向于那些能够为我们带来更高收益的站点。除此之外，在图形化决策树时，我们发现这颗决策树根本就没有使用位置信息，这说明位置信息对输出结果并没有产生多大作用。通过训练决策树，我们可能找到很多变量，对最终的输出结果几乎没什么作用。知道这些的好处是：假如有些数据难以收集或者收集的成本高昂，而且我们又知道这些数据无关紧要，那么我们完全可以不收集这些信息。

[laiqun]

决策树可以同时接受分类数据和数值数据作为输入，在本章的例子中，浏览网页数是数值数据，而其他的几个都是分类数据。这一点与很多机器学习算法不同，许多算法运行之前都要求我们必须对输入数据做预处理，或者归一化处理。

[laiqun]

决策树还允许数据的不确定性分配，即允许数据的缺失。由于种种原因，我们并不一定能够掌握足够的信息来做出正确的分类——一颗决策树上也许会有一部分节点，他们具有很多可能的结果，却无法进一步拆分。本章的代码会返回一个字典对象，其中包含了针对不同结果的统计量，借助这一信息我们可以判断出结果的可信度。要知道，不是所有算法都能够评估出一个不确定性的概率出来的。

[laiqun]

不过，此处所使用的决策树算法的确还是有缺陷的。虽然对于只包含少数几种可能结果的问题而言，算法处理起来非常高效，但是当面对拥有大量可能结果的数据集时，算法就变得不那么有效了。在同一个例子中，仅有的输出结果包括了None、Basic、Premium。而当输出结果有上百个的时候，决策树就会变得异常复杂，而且预测的结果也会大打折扣。

[laiqun]

本章介绍的决策树还有另外一个较大的缺陷，尽管它可以处理简单的数值型数据，但是它只能创建满足“大于/小于”条件的节点。对于某些数据集，当我们对其进行分类的时候，决定分类的因素往往取决于更多变量的复杂组合，此时要根据前面所述的决策树进行分类就比较困难了。例如，假设结果值是由两个变量的差来决定的，那么这棵树就会变得非常庞大，而且预测的准确性也会迅速下降。

[laiqun]

总之，对于有大量数值输入和输出的问题，决策树未必是一个好的选择；如果数值输入直接存在许多错综复杂的关系，比如当我们进行金融数据分析或影响分析的时候，决策树不一定会是一个好的选择。决策树最适合处理的，是那些带分界点的，由大量分类数据和数值型数据共同组成的数据集。如果理解决策过程非常重要，那么采用决策树就非常合适了；如同前面所述，明白推理过程会给与我们很多参考信息，这会比直接预测到结果更加重要。

[laiqun]

修改第一章： 机器学习的相关定义 理解定义很重要，它能避免你走弯路
为什么我们需要机器学习？

机器学习可以解决人类不能直接用编程来应对的复杂难题，因此，我们喂给机器学习算法大量的数据，以期得到想要的答案。

我们来看看这两个例子：

• 编写解决问题的程序是非常困难的，比如在杂乱的场景中，在新的照明条件下从新的角度来识别三维物体。我们不知道要如何通过代码来解决这个问题，因为这个识别过程在大脑中完成情况对我们来说还是未解之谜。 即使我们知道该怎么做，要编写的程序可能会非常复杂。
• 编写一个程序来预测信用卡交易欺诈发生的概率也是很难的，这可能也不存在任何简单而可靠的规则。因为欺诈是一个动态的目标，但程序需要不断变化。我们需要做的是结合大量的弱项规则来进行欺诈预测。

再者是机器学习方法。我们并不需要为每个特定的任务手动编写程序，而是收集大量的例子，为给定的输入指定正确的输出。然后，机器学习算法拿这些例子，并产生一个程序来完成这项工作。
这个过程像是训练狗狗学会“闻一闻找到它”。
学习算法产生的程序可能与典型的手写程序看起来非常不同。它可能包含数百万的数字。如果方法得当，该计划将适用于新案例以及我们训练的案例。如果数据改变，程序也可以通过对新数据进行训练来改变。你应该注意到，现在大量的计算比支付某人编写任务特定的程序来的更廉价。
鉴于此，机器学习能够很好地解决一些任务，包括：

• 模式识别：真实场景中的对象，面部识别或面部表情，口语等；
• 异常情况识别：信用卡交易的异常顺序，核电厂传感器读数的异常模式等；
• 预测：未来的股票价格或货币汇率，一个人会喜欢的电影等。

什么是神经网络？

神经网络是一般机器学习中的一类模型，它是一套特定的算法，受到生物神经网络的启发，彻底改变了机器学习的领域。目前所谓的深度神经网络的出现就已经证明它能够工作得非常好。

神经网络本身就是一般泛函数的逼近，这就是为什么它们几乎可以应用于任何机器学习问题，因为所有的机器学习都是学习从输入到输出空间的复杂映射。

以下是说服你学习神经计算的三个理由：

能够理解大脑是如何工作的：这是非常大且复杂的问题，并且是个令人绞尽脑汁去思考的问题，因此我们需要使用计算机来模拟。

能够了解受神经元和自适应连接启发的并行计算风格：这是一种与顺序计算非常不同的风格。

通过使用受大脑启发的新颖学习算法来解决实际问题：即使这不是大脑实际工作的方式，但这样的学习算法也是非常有用的。
神经网络是有史以来最棒的编程范例之一。在传统的编程方法中，我们告诉计算机做什么，将大问题分解成精确定义的小问题，这样计算机可以轻松地执行。相比之下，在神经网络中，我们不告诉计算机如何解决问题，而让神经网络能够从观测数据中学习，找出手头问题的解决办法。

今天，深度神经网络和深度学习技术在计算机视觉，语音识别和自然语言处理等许多重要问题上取得了出色的表现，它们正在被Google，微软和Facebook等公司大规模部署。

[laiqun]

练习

1. 针对结果的概率 目前，classify和mdclassify函数都是以总计数值的形式给出最终结果的。请对它们进行修改，使它给出最终结果属于某个分类的概率。
   指定分类的计数/该分支下数据集的大小
2. 缺失数据的范围 mdclassify 允许我们使用“None”来表示一个值的缺失。对数值型数据而言，其结果未必是却对未知的，也许相应的取值会落在某个已知的范围内。请修改mdclassify函数，允许使用一个如(20,25)这样的元组来代替原来的单一值，并且如果有必要的话，对两个分支都进行遍历。
   略
3. 提早停止向下拆分 不同于决策树的剪枝，buildtree 可以在它到达某个节点，而该节点处对应的熵下降的比较小的时候，停止向下拆分。有时候这种做法未必能达到理想效果，比如第一步拆分熵下降比较小，而随后的一次拆分，熵大大降低。但是这种做法可以省去额外的剪枝操作。请修改buildtree 函数，令其接受一个代表最小增益的参数，一旦不满足最小增益的条件，则停止拆分。
   修改buildtree函数的判断条件即可
4. 数据有缺失的决策树训练 我们编写了一个可以处理数据缺失的预测函数。那如果训练集中有数据缺失应该怎么办？ 请修改buildtree函数，令其可以检查数据是否有缺失的情况，当我们无法沿着某个分支向下传递的时候，令其同时沿着两个分支向下传递。
   略
5. 多路径拆分(有难度) 本章中所构建的所有树都是严格的二叉决策树。然而，有些数据集却允许我们可以将一个节点拆分成两个以上的分支，根据这些数据集构造出来的决策树也许会更加简单。如果是这样的话，如果表达此类决策树？又如何对其进行训练呢？
   略