今天是机器学习专题的第23篇文章，我们今天分享的内容是十大数据挖掘算法之一的CART算法。
CART算法全称是Classification and regression tree，也就是分类回归树的意思。和之前介绍的ID3和C4.5一样，CART算法同样是决策树模型的一种经典的实现。决策树这个模型一共有三种实现方式，前面我们已经介绍了ID3和C4.5两种，今天刚好补齐这最后一种。
算法特点
CART称为分类回归树，从名字上我们也看得出来，它既能支持分类又可以支持回归。的确如此，决策树的确支持回归操作，但是我们一般不会用决策树来进行回归。这里面的原因很多，除了树模型拟合能力有限效果不一定好之外，还与特征的模式有关系，树回归模型受到特征的影响非常大。这个部分我们不做太多深入，之后会在回归树的文章当中详细探讨。
正因为回归树模型效果表现都不太理想，所以CART算法实现决策树基本都是用来做分类问题。那么在分类问题上，它与之前的ID3算法和C4.5算法又有什么不同呢？
主要细究起来大约有两点，第一点是CART算法使用Gini指数而不是信息增益来作为划分子树的依据，第二点是CART算法每次在划分数据的时候，固定将整份数据拆分成两个部分，而不是多个部分。由于CART每次将数据拆分成两个部分，所以它对于拆分的次数没有限制，而C4.5算法对特征进行了限制，限制了每个特征最多只能使用一次。因为这一点，同样CART对于剪枝的要求更高，因为不剪枝的话很有可能导致树过度膨胀，以至于过拟合。
Gini指数
在ID3和C4.5算法当中，在拆分数据的时候用的是信息增益和信息增益比，这两者都是基于信息熵模型。信息熵模型本身并没有问题，也是非常常用的模型。唯一的问题是，在计算熵的时候需要涉及到log运算，相比于四则运算来说，计算log要多耗时很多。
Gini指数本质上也是基于信息熵模型，只是我们在计算的时候做了一些转化，从而避免了使用log进行计算，加速了计算的过程。两者的内在逻辑是一样的。那怎么实现的加速计算呢？这里用到了高等数学当中的泰勒展开，我们将log运算通过泰勒公式展开，转化成多项式的计算，从而加速信息熵的计算。
我们来做一个简单的推导：
\[\begin{aligned} \ln(x) \approx \ln(x_0) + (x-x_0)\ln'(x_0) + o(x) \end{aligned} \]