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