第三课:决策树
决策树
【原理】CART决策树算法实现流程
作者 : 老饼 日期 : 2022-06-26 03:41:18 更新 : 2022-11-29 16:28:05
本站原创文章,转载请说明来自《老饼讲解-机器学习》ml.bbbdata.com


本文梳理CART决策树的算法流程,并分析代码实现的难点及解决方案

本文是决策树的自实现的基础,具体的实现代码在《CART决策树自实现代码》



   算法流程来源   


本文是笔者扒取matlab决策树函数fitctree的源码后,梳理整合得到的算法实现流程,
本文中的算法流程,即matlab的决策树函数fitctree的算法流程
而sklearn包中决策树tree.DecisionTreeClassifier与该流程在细节上有所出入,主体上仍然是保持一致的





  01. CART决策树构建算法实现流程  


本节展示CART决策树的构建算法流程图,并说明其中的实现难点



   实现流程   


CART决策树构建的实现逻辑是非常简单的,
无非就是不断地让未长生的节点继续长生,直到生长完成
 算法流程图如下
 
  😡 代码实现的难点   
 
决策树的实现逻辑是非常简单的,
  但真正去实现决策树时,会发现有两个难点
 
   👉 如何表达决策树中树的结构    
  👉 如何对树进行历遍  
        




   02. 难点一:如何记录树结构  



本节讨论CART决策树算法在代码实现上的难点一:"如何记录树结构"的相关方案和利弊



   两种常见的实现方案   


目前较常见的方案有两种
方案一:链表
 第一种是用链表,程序员的至爱,如下
 
 
 
每个节点是一个独立对象,然后用指针指向子节点、父节点

 
方案一:左右节点编号
 
第二种用左右节点编号数组,如下
 
 
 数组的索引代表节点编号,左右节点数组里记录的是左右节点的编号



   两种方案的利弊   


两种方案各有好处,又各有弊端
 链表方案的利弊
第一种链表形式,
优点是增删时非常方便,
缺点是除非画图,不然非常不直观,
而且动不动就要历遍,
例如要找叶子节点,就需要历遍,
要知道有多少个节点,也要历遍。
左右节点编号方案的利弊
第二种左右节点编号记录方式,
看起来没什么毛病,但逻辑上非常不直观,
在删掉某个节点下所有节点时,逻辑非常绕。




   03. 难点二:树历遍  



本节讨论CART决策树算法在代码实现上的难点二:"树历遍"的相关方案和利弊



    树历遍的难点    


树历遍的根本难点在于,历遍过程是动态的,
必须历遍到具体节点,才知道该节点下还有没有子节点



   两种常见的实现方案   


树的历遍也有两个方案:节点栈与递归

   节点栈方案  
节点栈方案的处理流程如下:
 
建立一个节点栈,将未处理的节点放在栈中,
每次出栈处理一个节点,处理完后,把该节点的子节点入栈
直到栈中节点数为空,则完成历遍

  
 
 递归方案
 
递归方案的处理方式如下:
 

 递归就是处理函数只要还有子节点,就不断自身调用自身
两种方案的利弊   
递归的好处是简洁,但代码难理解
而节点栈相对较好理解些,但没有递归简洁




     笔者语     


由于决策树的实现上存在这两个难点,注定代码不能简单明了,
网上一些看来起简单明了的代码,实则是功能不全的,
上面说了,两种存储方式在实现某些功能时,都会不方便,
这些就需要大量代码去把功能堆出来
matlab自身是使用 “左右节点编号数组+节点栈的方式”,
 
而 笔者最终选用“链表+递归”的方式去复现matlab中的算法,
主要是笔者需要自行拓展一些功能,以 “链表+递归”更加简洁灵活和方便
 
具体复现代码见《CART决策树代码复现》







 End 







联系老饼