【原理】CART分类树构建算法实现

本站原创文章，转载请说明来自《老饼讲解-机器学习》www.bbbdata.com

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

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

   算法流程来源   

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

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

本节展示CART决策树在代码实现时的算法流程

   实现流程   

决策树的实现逻辑是非常简单的，
无非就是不断地让未长生的节点继续长生，直到生长完成
具体流程图如下：

   代码实现的难点   

决策树的实现逻辑是非常简单的，
 但真正去实现决策树时，会发现有两个难点
 👉 1. 如何表达决策树中树的结构    
👉2. 如何对树进行历遍          

   02. 关于树结构的存储  

本节介绍CART决策树结构信息的两种存储方法

   两种常见的实现方案   

目前较常见的方案有两种 ，
第一种是用链表，程序员的至爱。

 第二种用左右节点编号数组
 

   两种方案的利弊   

两者各有好处，又各有弊端
链表形式的利弊
第一种链表形式，
优点是增删时非常方便，
缺点是除非画图，不然非常不直观，
而且动不动就要历遍，
例如要找叶子节点，就需要历遍，
要知道有多少个节点，也要历遍

 矩阵记录形式的利弊
第二种矩阵记录，
看起来没什么毛病，但逻辑上非常不直观，
在删掉某个节点下所有节点时，逻辑非常绕

   03. 关于树历遍  

本节介绍CART决策树中两种对树历遍的常见方案

   两种常见的实现方案   

树历遍的根本难点在于，历遍过程是动态的，
必须历遍到具体节点，才知道该节点下还有没有子节点
树的历遍也有两个方案：
 👉1.节点栈方案
👉2. 递归方案  
 
 1.节点栈方案
 节点栈方案的处理方式如下：
 
建立一个节点栈，将未处理的节点放在栈中，
每次出栈处理一个节点，处理完后，把该节点的子节点入栈
直到栈中节点数为空，则完成历遍  

  2. 递归方案
递归方案的处理方式如下：

 递归就是处理函数只要还有子节点，就不断自身调用自身。

   ✍️两种方案的利弊   
递归的好处是简洁，但代码难理解
而节点栈相对较好理解些，但没有递归简洁

   笔者语   

由于决策树的实现上存在这两个难点，注定代码不能简单明了，
matlab自身是使用 “左右节点编号数组+节点栈的方式”，
 而 笔者最终选用“链表+递归”的方式去复现算法，
主要是笔者需要自行拓展一些功能，以 “链表+递归”更加简洁灵活和方便。
具体复现代码见《CART决策树-代码自实现》

 End