CART算法原理与理解
CART算法的全称是分类回归树算法，分类即划分离散变量；回归划分连续变量。他与C4.5很相似，但是一个二元分类，采用的是类似于熵的GINI指数作为分类决策，形成决策树之后还要进行剪枝，我自己在实现整个算法的时候采用的是代价复杂度算法。
GINI指数
在节点t时，GINI指数公式：
是节点t中类j所占的比例。GINI的值范围。
构建决策树
构建决策树时通常采用自上而下的方法，在每一步选择一个最好的属性来分裂。 "最好" 的定义是使得子节点中的训练集尽量的纯度。不同的算法使用不同的指标来定义"最好"。一般有4中不同的不纯度量可以用来发现CART模型的划分，，取决于目标变量的类型，对于分类的目标变量，可以选择GINI双化或有序双化；对于连续的目标变量，可以使用最小二乘偏差（LSD）或最小绝对偏差（LAD）。这里当然选择GINI指数。
算法的最佳分割点
数值型变量：（比如工资的高低）对记录的值从小到大排序，计算每个值作为临界点产生的子节点的异质性统计量。能够使异质性减小程度最大的临界值便是最佳的划分点。
分类型变量：列出划分为两个子集的所有可能组合，计算每种组合下生成子节点的异质性。同样，找到使异质性减小程度最大的组合作为最佳划分点。
决策树规模
一般在示例中展示的都是低深度模型，所以也不会出现决策树的规模的问题。在实际的应用中，决策树规模受用户对深度要求、节点纯度、节点样本个数等影响、，因此这就决定了需要对决策树进行停止生长的限制（剪枝）。
剪枝必要性：当分类回归过于细化，会导致过拟合问题。
前剪枝：停止生长策略（深度到达某个值就停止生长、纯度全都超过某个值时不再划分）；
后剪枝：在允许决策树达到充分伸张后，自下而上的逐层剪枝（GINI指数明显接近零，也就是属性分类的某一类特别占优势）。
示例（训练集）
对如下递归划分方式如何建立决策树？从而预测拖欠贷款的人群。
计算GINI指数，选择分割点
计算GINI指数，选择分割点
生成决策树
（不好意思，不想画表格，所以全部截图上传的，博文一直没更新就是不太想编辑）
参考文献
1.?url=-U2IM6cEZtFCgqYl1XRwrRwpsxmVde-x29iZpoo_GAtswaEeIchz-WOwjQcJe_2i7Kje2kVu_P_xi9SAfcA5ACWKk-lbZjmWx1MLsUVQIfW
曾经一直想让别人知道自己的心情，那些沉重，
