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