老饼讲解-机器学习
本站原创文章，转载请说明来自《老饼讲解-机器学习》www.bbbdata.com
本文梳理CART决策树的算法流程，并分析代码实现的难点及解决方案
本文是决策树的自实现的基础，具体的实现代码在《CART决策树自实现代码》
算法流程来源
本文是笔者扒取matlab决策树函数fitctree的源码后，梳理整合得到的算法实现流程，
本文中的算法流程，即matlab的决策树函数fitctree的算法流程
而sklearn包中决策树tree.DecisionTreeClassifier与该流程在细节上有所出入，主体上仍然是保持一致的
本节展示CART决策树的构建算法流程图，并说明其中的实现难点
实现流程
CART决策树构建的实现逻辑是非常简单的，
无非就是不断地让未长生的节点继续长生，直到生长完成
算法流程图如下
😡 代码实现的难点
决策树的实现逻辑是非常简单的，
但真正去实现决策树时，会发现有两个难点
👉 如何表达决策树中树的结构
👉 如何对树进行历遍
本节讨论CART决策树算法在代码实现上的难点一："如何记录树结构"的相关方案和利弊
两种常见的实现方案
目前较常见的方案有两种
方案一：链表
第一种是用链表，程序员的至爱，如下
每个节点是一个独立对象，然后用指针指向子节点、父节点
方案一：左右节点编号
第二种用左右节点编号数组，如下
数组的索引代表节点编号，左右节点数组里记录的是左右节点的编号
两种方案的利弊
两种方案各有好处，又各有弊端
链表方案的利弊
第一种链表形式，
优点是增删时非常方便，
缺点是除非画图，不然非常不直观，
而且动不动就要历遍，
例如要找叶子节点，就需要历遍，
要知道有多少个节点，也要历遍。
左右节点编号方案的利弊
第二种左右节点编号记录方式，
看起来没什么毛病，但逻辑上非常不直观，
在删掉某个节点下所有节点时，逻辑非常绕。
本节讨论CART决策树算法在代码实现上的难点二："树历遍"的相关方案和利弊
树历遍的难点
树历遍的根本难点在于，历遍过程是动态的，
必须历遍到具体节点，才知道该节点下还有没有子节点
两种常见的实现方案
树的历遍也有两个方案：节点栈与递归
节点栈方案
节点栈方案的处理流程如下：
建立一个节点栈，将未处理的节点放在栈中，
每次出栈处理一个节点，处理完后，把该节点的子节点入栈
直到栈中节点数为空，则完成历遍
递归方案
递归方案的处理方式如下：
递归就是处理函数只要还有子节点，就不断自身调用自身
两种方案的利弊
递归的好处是简洁，但代码难理解
而节点栈相对较好理解些，但没有递归简洁
笔者语
由于决策树的实现上存在这两个难点，注定代码不能简单明了，
网上一些看来起简单明了的代码，实则是功能不全的，
上面说了，两种存储方式在实现某些功能时，都会不方便，
这些就需要大量代码去把功能堆出来
matlab自身是使用 “左右节点编号数组+节点栈的方式”，
而 笔者最终选用“链表+递归”的方式去复现matlab中的算法，
主要是笔者需要自行拓展一些功能，以 “链表+递归”更加简洁灵活和方便
具体复现代码见《CART决策树代码复现》
End
