构建决策树模型

在之前的章节中，我们使用了贝叶斯和神经网络来进行判断两者的关联度，但是在这个章节中，我们将使用决策树模型来进行模型的建立。

预测注册用户 #

当访问量很大的网站想要推出一个服务，判断这个服务是否愿意付费，这里首先会去采集一些基本的用户信息，下图收集了用户的 来源网站，位置，是否阅读 FAQ，浏览网页数量，选择服务类型

转为代码如下

my_data=[['slashdot','USA','yes',18,'None'],
        ['google','France','yes',23,'Premium'],
        ['digg','USA','yes',24,'Basic'],
        ['kiwitobes','France','yes',23,'Basic'],
        ['google','UK','no',21,'Premium'],
        ['(direct)','New Zealand','no',12,'None'],
        ['(direct)','UK','no',21,'Basic'],
        ['google','USA','no',24,'Premium'],
        ['slashdot','France','yes',19,'None'],
        ['digg','USA','no',18,'None'],
        ['google','UK','no',18,'None'],
        ['kiwitobes','UK','no',19,'None'],
        ['digg','New Zealand','yes',12,'Basic'],
        ['slashdot','UK','no',21,'None'],
        ['google','UK','yes',18,'Basic'],
        ['kiwitobes','France','yes',19,'Basic']]

决策树 #

决策树：是一种更为简单的机器学习方法。它是对被观测数据（observations）进行分类的一种相当直观的方法，决策树在经过训练之后，看起来就像是以树状形式排列的一系列 if-then 语句。

# 构造决策树的表达形式
class decisionnode:
    def __init__(self, col=-1, value=None, result=None, tb=None, fb=None):
        '''
        col是待检验的判断条件所对应的列索引，
        value对应于为了使结果为true，当前列必须匹配的值，
        tb和fb也是decisionnode，它们对应与结果分别为true或false时，树上相对于当前节点的子树上的节点，
        results保存的是针对于当前分支的结果，它是一个字典。除叶节点外，在其他节点上该值都为None。
        '''
        self.col = col
        self.value = value
        self.results = results
        self.tb = tb
        self.fb = fb

决策树的期望执行过程如下

对树进行训练 #

本章使用一种叫做 CART (classification and Regression Trees，即分类回归树)的算法：算法首先创建一个根节点。然后通过评估表中的所有观测变量，从中选出最合适的变量对数据进行拆分。

首先定义一个 divideset 函数，对某一栏的数据进行拆分，返回一个 Yes 的数据集和一个 No 的数据集源代码

def divideset(rows,column,value):
   # 定义拆分函数，如果是数值类型， >= 都是 True，如果是其他类型， == 才是 True
   split_function=None
   if isinstance(value,int) or isinstance(value,float):
      split_function=lambda row:row[column]>=value
   else:
      split_function=lambda row:row[column]==value
   
   # 拆分数据集
   set1=[row for row in rows if split_function(row)]
   set2=[row for row in rows if not split_function(row)]
   return (set1,set2)

如果按照 FAQ 执行如下

>>> treepredict.divideset(treepredict.my_data,2,'yes')
(
[['slashdot', 'USA', 'yes', 18, 'None'], ['google', 'France', 'yes', 23, 'Premium'], ['digg', 'USA', 'yes', 24, 'Basic'], ['kiwitobes', 'France', 'yes', 23, 'Basic'], ['slashdot', 'France', 'yes', 19, 'None'], ['digg', 'New Zealand', 'yes', 12, 'Basic'], ['google', 'UK', 'yes', 18, 'Basic'], ['kiwitobes', 'France', 'yes', 19, 'Basic']], 

[['google', 'UK', 'no', 21, 'Premium'], ['(direct)', 'New Zealand', 'no', 12, 'None'], ['(direct)', 'UK', 'no', 21, 'Basic'], ['google', 'USA', 'no', 24, 'Premium'], ['digg', 'USA', 'no', 18, 'None'], ['google', 'UK', 'no', 18, 'None'], ['kiwitobes', 'UK', 'no', 19, 'None'], ['slashdot', 'UK', 'no', 21, 'None']])

效果并不好，看起来都是无效的抉择。

选择最合适的拆分方案 #

显然我们需要找个合适的拆分方案，最好的方案，显然是 yes 和 no 之间的结果应该尽可能的少交错。那我们先准备一个计算交错的函数，先准备一个计算出现不同情况的辅助函数 treepredict.py

def uniquecounts(rows):
   results={}
   for row in rows:
      # 结果在最后一列
      r=row[len(row)-1]
      if r not in results: results[r]=0
      results[r]+=1
   return results

Gini Impurity 基尼不纯度 #

基尼不纯度，是指将来自集合中的某种结果随机应用于集合中某个数据项的预期误差率。这个算法利用集合中的每一项结果出现的次数除以集合的总行书来获得相应的概念，将这些概率相加，就得到某一行数据被随机分配到错误结果的总概率。概率为0说明非常理想，概率越高说明拆分越不理想。

def giniimpurity(rows):
  total=len(rows)
  counts=uniquecounts(rows)
  imp=0
  for k1 in counts:
    p1=float(counts[k1])/total
    for k2 in counts:
      if k1==k2: continue
      p2=float(counts[k2])/total
      imp+=p1*p2
  return imp

Entropy 熵 #

用来计算集合的无序程度，公式如下

\(\begin{aligned}&p(i)=frequency(outcome)=count(outcome)/count(totalrows)\\&Entropy=sum(p(i) * log(p(i)))\end{aligned}\)

def entropy(rows):
   from math import log
   log2=lambda x:log(x)/log(2)  
   results=uniquecounts(rows)
   # 这里开始计算
   ent=0.0
   for r in results.keys():
      p=float(results[r])/len(rows)
      ent=ent-p*log2(p)
   return ent

递归构造树 #

基于上面的几个函数，我们可以判断一个条件是否选择是否足够好

比如我们选择一个节点之后如下

在剩余的结果中继续构造，就会如下

通过一系列的递归操作自然就可以达成目标，代码如下 treepredict.py

def buildtree(rows,scoref=entropy):
  if len(rows)==0: return decisionnode()
  current_score=scoref(rows)

  # 定义最佳拆分的辅助变量
  best_gain=0.0
  best_criteria=None
  best_sets=None

  # 一共的列数
  column_count=len(rows[0])-1
  # 循环生成要拆分的 col 下标
  for col in range(0,column_count):
    # 这一列的出现的值
    column_values={}
    for row in rows:
       column_values[row[col]]=1
    # 根据这一列的值，拆分成两个子集
    for value in column_values.keys():
      (set1,set2)=divideset(rows,col,value)
      
      # 计算熵，和最好的进行比较
      p=float(len(set1))/len(rows)
      gain=current_score-p*scoref(set1)-(1-p)*scoref(set2)
      if gain>best_gain and len(set1)>0 and len(set2)>0:
        best_gain=gain
        best_criteria=(col,value)
        best_sets=(set1,set2)
  # 递归构建
  if best_gain>0:
    trueBranch=buildtree(best_sets[0])
    falseBranch=buildtree(best_sets[1])
    return decisionnode(col=best_criteria[0],value=best_criteria[1],
                        tb=trueBranch,fb=falseBranch)
  else:
    return decisionnode(results=uniquecounts(rows))

展示树 #

def printtree(tree,indent=''):
   # Is this a leaf node?
   if tree.results!=None:
      print str(tree.results)
   else:
      # Print the criteria
      print str(tree.col)+':'+str(tree.value)+'? '

      # Print the branches
      print indent+'T->',
      printtree(tree.tb,indent+'  ')
      print indent+'F->',
      printtree(tree.fb,indent+'  ')

结果如下

>>> tree = treepredict.buildtree(treepredict.my_data)
>>> tree
tree         treepredict  
>>> treepredict.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}

文中还有用打印成图的，参考 treepredict.py 这里忽略

预测分类 #

当我们构建好树之后，我们就可以接受参数来判断是不是会进行购买了

def classify(observation,tree):
  # 如果是叶子节点，直接返回结果
  if tree.results!=None:
    return tree.results
  else:
    v=observation[tree.col]
    branch=None
    # 数值类型
    if isinstance(v,int) or isinstance(v,float):
      if v>=tree.value: branch=tree.tb # true 分支
      else: branch=tree.fb # false 分支
    # 其他类型
    else:
      if v==tree.value: branch=tree.tb # true 分支
      else: branch=tree.fb # false 分支
    # 返回分类
    return classify(observation,branch)

执行过程如下图

剪枝 #

前述方法训练决策树会有一个问题，就是决策树可能会变得过度拟合(overfitted)。也就是说，它可能会变得过于针对训练数据。专门针对训练集所创建出来的分支，其熵值与真实情况相比可能会有所降低，但决策树上的判断条件实际上是完全随意的，因此一棵过度拟合的决策树所给出的答案也许比实际情况更具特殊性。

一种可能的解决办法是，只要当熵减少的数量小于某个最小值时，我们就停止分支的创建。但是它有一个小小的缺陷——我们有可能会遇到这样的数据集：某一次分支的创建并不会令熵降低多少，但是随后创建的分支却会使熵大幅度降低。对此，一种替代的策略是，先构造好如前所述的整颗树，然后在尝试消除多余的节点。这个过程就是剪枝。

剪枝算法：对具有相同父节点的一组节点进行检查，判断如果将其合并，熵的增加量是否会小于某个指定的阈值。如果确实如此，则这些节点会被合并成一个单一的节点，合并后的新节点包含了所有可能的结果值。这种做法有助于避免过度拟合的情况，也使得根据决策树作出的预测结果，不至于比从数据集中得到的实际结论还要特殊。

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 v,c in tree.tb.results.items():
      tb+=[[v]]*c
    for v,c in tree.fb.results.items():
      fb+=[[v]]*c
    
    # 计算熵的减少情况
    # 原文中代码应该写错了
    delta=entropy(tb+fb)-((entropy(tb)+entropy(fb))/2)
    # 如果熵减少小于某个阈值，则合并
    if delta<mingain:
      # 合并
      tree.tb,tree.fb=None,None
      tree.results=uniquecounts(tb+fb)

处理丢失数据 #

除了易于解释外，决策树还有一个优点，就是它处理缺失数据的能力。我们所使用的数据集也许会缺失某些信息。为了使决策树能够处理这种情况，我们须要实现一个新的预测函数。 treepredict.py

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=sum(tr.values())
      fcount=sum(fr.values())
      tw=float(tcount)/(tcount+fcount)
      fw=float(fcount)/(tcount+fcount)
      result={}
      # 这里进行权重的计算（乘以各自的权重）
      for k,v in tr.items(): result[k]=v*tw
      for k,v in fr.items(): result[k]=v*fw      
      return result
    # 这里的逻辑和 classify 一样的
    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)

处理数值型结果 #

如果我们将所有数字都看作是不同的分类，那么目前的算法将不会考虑这样一个事实：有些数字彼此非常的接近，而其他数字则相差很远；我们将这些数字完全看成了绝对的离散。为了解决这个问题，当我们拥有一棵以数字作为输出结果的决策树时，我们可以使用方差(variance)作为评价函数来取代熵或基尼不纯度。

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

对住房价格建模 & 对热度建模 #

这两个都无法访问了，忽略

什么时候使用决策树 #

或许决策树最大的优势在于它可以轻易地对一个受训模型给予解释。在本章的例子里，执行完算法程序之后，我们不仅可以得到一棵用以预测新用户的决策树，而且还可以得到一个有助于我们做出判断的问题列表。

与其他几种机器学习算法不同，决策树可以同时接受分类(categorical)数据和数值(numerical)数据作为输入。不仅如此，许多算法在运行之前都要求我们必须对输入数据做预处理，或是归一化处理，而本章的代码却可以接受包括分类数据和数值数据在内的任何数据列表，并据此构造出相应的决策树来。

决策树还允许数据的不确定性分配（即允许数据的缺失）。在一棵决策树上也许会存在一部分节点，它们具有多种可能的结果值，但是又无法再进一步拆分。本章中的代码会返回一个字典对象，其中包含了针对不同结果的统计量，借助这一信息我们可以判断出结果的可信度。并不是所有算法都能够评估出一个不确定结果的概率来。

缺陷：对于只包含少数几种可能结果的问题而言，算法处理起来非常有效，但是当面对拥有大量可能结果的数据集时，算法就变得不那么有效了。当输出结果有上百个的时候，决策树就会变得异常复杂，而且预测的效果也可能会大打折扣。只能创建满足“大于/小于”条件的节点。对于某些数据集，当我们对其进行分类的时候，决定分类的因素往往取决与更多变量的复杂组合，此时要根据前述的决策树进行分类就比较困难了。。例如，假设结果值是由两个变量的差来决定的，那么这棵树就会变得非常庞大，而且预测的准确性也会迅速下降。

总之，对于有大量数值型输入和输出的问题，决策树未必是一个好的选择；如果数值型输入之间存在许多错综复杂的关系，比如金融数据或影像，决策树同样也不一定是很好的选择。决策树最适合用来处理的，是那些带分界点(breakpoints)的、由大量分类数据和数值数据共同组成的数据集。如果对决策过程的理解至关重要，那么采用决策树就再合适不过了。