与上篇文章中提到的ID3算法和C4.5算法类似，CART算法也是一种决策树分类算法。CART分类回归树算法的本质也是对数据进行分类的，最终数据的表现形式也是以树形的模式展现的，CART与ID3，C4.5所采用的分类标准是不同了。
下面列出了其中的一些不同之处：
1、CART最后形成的树是一个二叉树，每个节点会分成2个节点，左孩子节点和右孩子节点，于是这就要求CART算法在所选定的属性中又要划分出最佳的属性划分值，节点如果选定了划分属性名称还要确定里面按照哪个值做一个二元的划分（为属性的值为一类，否则为零另一类）
而在ID3和C4.5中是按照分类属性的值类型进行划分（属性的取值可以为1个也可以为多个）
2、CART算法对于属性的值采用的是基于Gini系数值的方式做比较，gini某个属性的某次值的划分的gini指数的值为：
，pk就是分别为正负实例的概率，gini系数越小说明分类纯度越高，可以想象成与熵的定义一样。因此在最后计算的时候我们只取其中值最小的做出划分。最后做比较的时候用的是gini的增益做比较，要对分类号的数据做出一个带权重的gini指数的计算
3
CART算法在按照Gini指数构建好的树，但是这样构建的树和ID3和C4.5一样，容易导致过拟合现象，在数据集中，在测试集中过拟合的决策树的错误率比经过简化的决策树的错误率要高，过拟合的决策树对训练集拟合的很好，错误率很低（但这并不代表这样的模型是最好的）。
现在问题就在于，如何(HOW)在原生的过拟合决策树的基础上，生成简化版的决策树，可以通过剪枝的方法来简化过拟合的决策树。剪枝可以分为两种：预剪枝(Pre-Pruning)和后剪枝(Post-Pruning),下面我们来详细学习下这两种方法：
PrePrune：预剪枝，及早的停止树增长，方法可以参考见上面树停止增长的方法。
PostPrune：后剪枝，在已生成过拟合决策树上进行剪枝，可以得到简化版的剪枝决策树。
常见的后剪枝发包括代价复杂度剪枝，悲观误差剪枝等等。为非叶子节点计算误差代价，这里的后剪枝法用的是CCP代价复杂度剪枝，代价复杂度剪枝的算法公式为：
α表示的是每个非叶子节点的误差增益率，可以理解为误差代价，最后选出误差代价最小的一个节点进行剪枝（减掉此分支和原来的树的训练集的准确度相差最小）。
里面变量的意思为：
是子树中包含的叶子节点个数;
是节点t的误差代价，如果该节点被剪枝;
r(t)是节点t的误差率;
p(t)是节点t上的数据占所有数据的比例。
是子树Tt的误差代价，如果该节点不被剪枝。它等于子树Tt上所有叶子节点的误差代价之和。下面说说我对于这个公式的理解：其实这个公式的本质是对于剪枝前和剪枝后的样本偏差率做一个差值比较，一个好的分类当然是分类后的样本偏差率相较于没分类（就是剪枝掉的时候）的偏差率小，所以这时的值就会大，如果分类前后基本变化不大，则意味着分类不起什么效果，α值的分子位置就小，所以误差代价就小，可以被剪枝。但是一般分类后的偏差率会小于分类前的，因为偏差数在高层节点的时候肯定比子节点的多，子节点偏差数最多与父亲节点一样。
主程序如下：
package DataMining_CART;
public class Client {
public static void main(String[] args){
String filePath = "E:\\code\\data mining\\DataMining_CART\\src\\DataMining_CART\\input.txt";//训练数据集的路径
CARTTool tool = new CARTTool(filePath);//构造函数
tool.startBuildingTree();//CART主程序的入口
}
}
每个节点的类如下
package DataMining_CART; import java.util.ArrayList; /**
* 回归分类树节点
*
* @author clj
*
*/
public class AttrNode {
// 节点属性名字
private String attrName;
// 节点索引标号
private int nodeIndex;
//包含的叶子节点数
private int leafNum;//记录叶子节点的个数的目的是什么呢
// 节点误差率
private double alpha;
// 父亲分类属性值
private String parentAttrValue;
// 孩子节点
private AttrNode[] childAttrNode;
// 数据记录索引
private ArrayList<String> dataIndex; public String getAttrName() {
return attrName;
} public void setAttrName(String attrName) {
this.attrName = attrName;
} public int getNodeIndex() {
return nodeIndex;
} public void setNodeIndex(int nodeIndex) {
this.nodeIndex = nodeIndex;
} public double getAlpha() {
return alpha;
} public void setAlpha(double alpha) {
this.alpha = alpha;
} public String getParentAttrValue() {
return parentAttrValue;
} public void setParentAttrValue(String parentAttrValue) {
this.parentAttrValue = parentAttrValue;
} public AttrNode[] getChildAttrNode() {
return childAttrNode;
} public void setChildAttrNode(AttrNode[] childAttrNode) {
this.childAttrNode = childAttrNode;
} public ArrayList<String> getDataIndex() {
return dataIndex;
} public void setDataIndex(ArrayList<String> dataIndex) {
this.dataIndex = dataIndex;
} public int getLeafNum() {
return leafNum;
} public void setLeafNum(int leafNum) {
this.leafNum = leafNum;
} }
关键程序CARTTool如下
package DataMining_CART; import java.io.BufferedReader;
import java.io.File;
import java.io.FileReader;
import java.io.IOException;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.Queue; /**
* CART分类回归树算法工具类
* 本文是使用的后剪枝的方法
* @author clj
*
*/
public class CARTTool {
// 类标号的值类型
private final String YES = "Yes";
//private final String NO = "No"; // 所有属性的类型总数,在这里就是data源数据的列数
private int attrNum;
private String filePath;
// 初始源数据，用一个二维字符数组存放模仿表格数据
private String[][] data;
// 数据的属性行的名字
private String[] attrNames;
// 每个属性的值所有类型
private HashMap<String, ArrayList<String>> attrValue; public CARTTool(String filePath) {
this.filePath = filePath;
attrValue = new HashMap<>();
} /**
* 从文件中读取数据
*/
public void readDataFile() {
File file = new File(filePath);
ArrayList<String[]> dataArray = new ArrayList<String[]>(); try {
BufferedReader in = new BufferedReader(new FileReader(file));
String str;
String[] tempArray;
while ((str = in.readLine()) != null) {
tempArray = str.split(" ");
dataArray.add(tempArray);
}
in.close();
} catch (IOException e) {
e.getStackTrace();
} data = new String[dataArray.size()][];
dataArray.toArray(data);
attrNum = data[0].length;
attrNames = data[0];
} /**
* 首先初始化每种属性的值的所有类型，用于后面的子类熵的计算时用
*/
public void initAttrValue() {
ArrayList<String> tempValues; // 按照列的方式，从左往右找
for (int j = 1; j < attrNum; j++) {
// 从一列中的上往下开始寻找值
tempValues = new ArrayList<>();
for (int i = 1; i < data.length; i++) {
if (!tempValues.contains(data[i][j])) {
// 如果这个属性的值没有添加过，则添加
tempValues.add(data[i][j]);
}
} // 一列属性的值已经遍历完毕，复制到map属性表中
attrValue.put(data[0][j], tempValues);
}
} /**
* 计算机基尼指数
*
* @param remainData
* 剩余数据
* @param attrName
* 属性名称
* @param value
* 属性值
* @param beLongValue
* 分类是否属于此属性值，这里的作用是ID3Tool中的isParent的作用是相同的
* 在belongValue的模式下，在remainData数据中计算属性为atrrName，属性值为value的Gini数
* @return
*/
public double computeGini(String[][] remainData, String attrName,
String value, boolean beLongValue) {
// 实例总数
int total = 0;
// 正实例数
int posNum = 0;
// 负实例数
int negNum = 0;
// 基尼指数
double gini = 0; // 还是按列从左往右遍历属性
for (int j = 1; j < attrNames.length; j++) {
// 找到了指定的属性
if (attrName.equals(attrNames[j])) {
for (int i = 1; i < remainData.length; i++) {
// 统计正负实例按照属于和不属于值类型进行划分
if ((beLongValue && remainData[i][j].equals(value))
|| (!beLongValue && remainData[i][j].equals(value))) {
if (remainData[i][attrNames.length - 1].equals(YES)) {
// 判断此行数据是否为正实例
posNum++;
} else {
negNum++;
}
}
}
}
} total = posNum + negNum;
double posProbobly = (double) posNum / total;//计算得到的正比例
double negProbobly = (double) negNum / total;
gini = 1 - posProbobly * posProbobly - negProbobly * negProbobly;//统计学习方法中P69中5.24相同 // 返回计算基尼指数
return gini;
} /**
* 计算属性划分的最小基尼指数，返回最小的属性值划分和最小的基尼指数，保存在一个数组中
*
* @param remainData
* 剩余谁
* @param attrName
* 属性名称
* 与ID3中的概念是不同的，在查找最优的属性是时查找的基尼指数最小的，而在ID3中查找的是信息增益的最大值
* @return
*/
public String[] computeAttrGini(String[][] remainData, String attrName) {
String[] str = new String[2];//第一个返回值是应该以哪个属性为分割属性，第二个返回值是此值对应的Gini属性
// 最终该属性的划分类型值
String spiltValue = "";
// 临时变量
int tempNum = 0;
// 保存属性的值划分时的最小的基尼指数，开始并对其进行初始化
double minGini = Integer.MAX_VALUE;
ArrayList<String> valueTypes = attrValue.get(attrName);
// 属于此属性值的实例数
HashMap<String, Integer> belongNum = new HashMap<>(); for (String string : valueTypes) {//计算每个atrr的值的在剩余的集合中占有多少
// 重新计数的时候，数字归0
tempNum = 0;
// 按列从左往右遍历属性
for (int j = 1; j < attrNames.length; j++) {
// 找到了指定的属性
if (attrName.equals(attrNames[j])) {
for (int i = 1; i < remainData.length; i++) {
// 统计正负实例按照属于和不属于值类型进行划分
if (remainData[i][j].equals(string)) {
tempNum++;
}
}
}
} belongNum.put(string, tempNum);
} double tempGini = 0;
double posProbably = 1.0;
double negProbably = 1.0;
for (String string : valueTypes) {
tempGini = 0; posProbably = 1.0 * belongNum.get(string) / (remainData.length - 1);
negProbably = 1 - posProbably; tempGini += posProbably
* computeGini(remainData, attrName, string, true);
tempGini += negProbably
* computeGini(remainData, attrName, string, false); if (tempGini < minGini) {
minGini = tempGini;
spiltValue = string;
}
} str[0] = spiltValue;//某个属性的值可能不止一个，所以某属性的Gini应该为选择某属性的最小值 str[1] = minGini + ""; return str;
}
/*
* 构建的树的过程，与ID3是差不多的，只不过使用的策略不一样
* 在CART中重点是剪枝，应为只是构建树的过程就会导致树的构建是过拟合的过程，通过对树的剪枝，少去过拟合的现象
*/ public void buildDecisionTree(AttrNode node, String parentAttrValue,
String[][] remainData, ArrayList<String> remainAttr,
boolean beLongParentValue) {
// 属性划分值
String valueType = "";
// 划分属性名称
String spiltAttrName = "";
double minGini = Integer.MAX_VALUE;
double tempGini = 0;
// 基尼指数数组，保存了基尼指数和此基尼指数的划分属性值
String[] giniArray; if (beLongParentValue) {//belongparentValue指的是否是父节点指定的属性
node.setParentAttrValue(parentAttrValue);
} else {
node.setParentAttrValue("!" + parentAttrValue);
} if (remainAttr.size() == 0) {
if (remainData.length > 1) {
ArrayList<String> indexArray = new ArrayList<>();
for (int i = 1; i < remainData.length; i++) {
indexArray.add(remainData[i][0]);//0标记是id 编号
}
node.setDataIndex(indexArray);//数据记录索引，用来区分这个节点有哪些个节点
}
System.out.println("attr remain null");
return;
} for (String str : remainAttr) {//选择属性中的最小基尼指数
giniArray = computeAttrGini(remainData, str);
tempGini = Double.parseDouble(giniArray[1]); if (tempGini < minGini) {
spiltAttrName = str;
minGini = tempGini;
valueType = giniArray[0];
}
}
// 移除划分属性
remainAttr.remove(spiltAttrName);
node.setAttrName(spiltAttrName);//那么Node节点是按照splitAttrName进行划分的，所以Node.setAttrName是splitAttrName // 孩子节点,分类回归树中，每次二元划分，分出2个孩子节点，孩子节点是和此节点是具有相同的属性
AttrNode[] childNode = new AttrNode[2];
String[][] rData; boolean[] bArray = new boolean[] { true, false };
for (int i = 0; i < bArray.length; i++) {
// 二元划分属于属性值的划分，第一次循环中得到的属于splitAttraname 并且属于valueType的节点，第二次循环不属于这个valueType的节点
rData = removeData(remainData, spiltAttrName, valueType, bArray[i]); boolean sameClass = true;
ArrayList<String> indexArray = new ArrayList<>();
for (int k = 1; k < rData.length; k++) {
indexArray.add(rData[k][0]);
// 判断是否为同一类的
if (!rData[k][attrNames.length - 1]
.equals(rData[1][attrNames.length - 1])) {
// 只要有1个不相等，就不是同类型的
sameClass = false;
break;
}
} childNode[i] = new AttrNode();
if (!sameClass) {
// 创建新的对象属性，对象的同个引用会出错
ArrayList<String> rAttr = new ArrayList<>();
for (String str : remainAttr) {
rAttr.add(str);
}
buildDecisionTree(childNode[i], valueType, rData, rAttr,
bArray[i]);
} else {
String pAtr = (bArray[i] ? valueType : "!" + valueType);
childNode[i].setParentAttrValue(pAtr);
childNode[i].setDataIndex(indexArray);
}
} node.setChildAttrNode(childNode);//肯定是要等到子节点处理完了才能把子节点放到孩子节点结合中去。
} /**
* 属性划分完毕，进行数据的移除
*
* @param srcData
* 源数据
* @param attrName
* 划分的属性名称
* @param valueType
* 属性的值类型
* @parame beLongValue 分类是否属于此值类型
*/
private String[][] removeData(String[][] srcData, String attrName,
String valueType, boolean beLongValue) {
String[][] desDataArray;
ArrayList<String[]> desData = new ArrayList<>();
// 待删除数据
ArrayList<String[]> selectData = new ArrayList<>();
selectData.add(attrNames); // 数组数据转化到列表中，方便移除
for (int i = 0; i < srcData.length; i++) {
desData.add(srcData[i]);
} // 还是从左往右一列列的查找
for (int j = 1; j < attrNames.length; j++) {
if (attrNames[j].equals(attrName)) {
for (int i = 1; i < desData.size(); i++) {
if (desData.get(i)[j].equals(valueType)) {
// 如果匹配这个数据，则移除其他的数据
selectData.add(desData.get(i));
}
}
}
} if (beLongValue) {
desDataArray = new String[selectData.size()][];
selectData.toArray(desDataArray);
} else {
// 属性名称行不移除
selectData.remove(attrNames);
// 如果是划分不属于此类型的数据时，进行移除
desData.removeAll(selectData);//这里就相当于求了一个补集，与上面的区别就是差这一步和上一步
desDataArray = new String[desData.size()][];
desData.toArray(desDataArray);
} return desDataArray;
} public void startBuildingTree() {
readDataFile();//将一些文件读入到里面，一些变量进行初始化
initAttrValue(); ArrayList<String> remainAttr = new ArrayList<>();
// 添加属性，除了最后一个类标号属性
for (int i = 1; i < attrNames.length - 1; i++) {
remainAttr.add(attrNames[i]);
} AttrNode rootNode = new AttrNode();
buildDecisionTree(rootNode, "", data, remainAttr, false);//所有都全部初始化
setIndexAndAlpah(rootNode, 0, false);
System.out.println("剪枝前：");
showDecisionTree(rootNode, 1);//1指的是blankNum
setIndexAndAlpah(rootNode, 0, true);
System.out.println("\n剪枝后：");
showDecisionTree(rootNode, 1);
} /**
* 显示决策树
*
* @param node
* 待显示的节点
* @param blankNum
* 行空格符，用于显示树型结构
*/
private void showDecisionTree(AttrNode node, int blankNum) {
System.out.println();
for (int i = 0; i < blankNum; i++) {
System.out.print(" ");
}
System.out.print("--");
// 显示分类的属性值
if (node.getParentAttrValue() != null
&& node.getParentAttrValue().length() > 0) {
System.out.print(node.getParentAttrValue());
} else {
System.out.print("--");
}
System.out.print("--"); if (node.getDataIndex() != null && node.getDataIndex().size() > 0) {
String i = node.getDataIndex().get(0);
System.out.print("【" + node.getNodeIndex() + "】类别:"
+ data[Integer.parseInt(i)][attrNames.length - 1]);
System.out.print("[");
for (String index : node.getDataIndex()) {
System.out.print(index + ", ");
}
System.out.print("]");
} else {
// 递归显示子节点
System.out.print("【" + node.getNodeIndex() + ":"
+ node.getAttrName() + "】");
if (node.getChildAttrNode() != null) {
for (AttrNode childNode : node.getChildAttrNode()) {
showDecisionTree(childNode, 2 * blankNum);
}
} else {
System.out.print("【 Child Null】");
}
}
} /**
* 为节点设置序列号，并计算每个节点的误差率，用于后面剪枝
*
* @param node
* 开始的时候传入的是根节点
* @param index
* 开始的索引号，从1开始
* @param ifCutNode
* 是否需要剪枝
* 计算的过程应该是自上而下的进行
*/
private void setIndexAndAlpah(AttrNode node, int index, boolean ifCutNode) {
AttrNode tempNode;
// 最小误差代价节点，即将被剪枝的节点
AttrNode minAlphaNode = null;
double minAlpah = Integer.MAX_VALUE;//即设置alpha的初始值
Queue<AttrNode> nodeQueue = new LinkedList<AttrNode>(); nodeQueue.add(node);
while (nodeQueue.size() > 0) {
index++;
// 从队列头部获取首个节点并给予编号，并移除，使用队列，是使用的是宽度优先搜索
tempNode = nodeQueue.poll();
tempNode.setNodeIndex(index);
if (tempNode.getChildAttrNode() != null) {
for (AttrNode childNode : tempNode.getChildAttrNode()) {
nodeQueue.add(childNode);
}
computeAlpha(tempNode);
if (tempNode.getAlpha() < minAlpah) {
minAlphaNode = tempNode;
minAlpah = tempNode.getAlpha();
} else if (tempNode.getAlpha() == minAlpah) {
// 如果误差代价值一样，比较包含的叶子节点个数，剪枝有多叶子节点数的节点
if (tempNode.getLeafNum() > minAlphaNode.getLeafNum()) {
minAlphaNode = tempNode;
}
}
}
} if (ifCutNode) {
// 进行树的剪枝，让其左右孩子节点为null,ifCutNode为真是指的是剪枝之后，ifCutNode为假的指的是剪枝之前
minAlphaNode.setChildAttrNode(null);
}
} /**
* 为非叶子节点计算误差代价，这里的后剪枝法用的是CCP代价复杂度剪枝
*
* @param node
* 待计算的非叶子节点
*/
private void computeAlpha(AttrNode node) {
double rt = 0;//这里的rt和Rt和P73中C（t）的表达是相同的
double Rt = 0;
double alpha = 0;
// 当前节点的数据总数
int sumNum = 0;
// 最少的偏差数
int minNum = 0; ArrayList<String> dataIndex;
ArrayList<AttrNode> leafNodes = new ArrayList<>(); addLeafNode(node, leafNodes);//leafNodes开始为空，在addLeafNode函数中进行更新
/*
* System.out.println("node.attr="+node.getAttrName()+"\tleafNodes.length="+leafNodes.size());//输出每个节点分成的叶子节点的信息 for(int i=0;i<leafNodes.size();i++)
System.out.print(leafNodes.get(i).getDataIndex()+"\t");
System.out.println();
*/
node.setLeafNum(leafNodes.size());
for (AttrNode attrNode : leafNodes) {//leafNodes中包含Node所分的所有的叶子节点
dataIndex = attrNode.getDataIndex(); int num = 0;
sumNum += dataIndex.size();
for (String s : dataIndex) {
// 统计分类数据中的正负实例数
if (data[Integer.parseInt(s)][attrNames.length - 1].equals(YES)) {
num++;
}
}
minNum += num;//minNum保存着node中正实例的个数 // 取小数量的值部分
if (1.0 * num / dataIndex.size() > 0.5) {
num = dataIndex.size() - num;
} rt += (1.0 * num / (data.length - 1));
} //同样取出少偏差的那部分，因为要找到损失函数，所以是要把正实例和负实例中较小的部分
if (1.0 * minNum / sumNum > 0.5) {
minNum = sumNum - minNum;
} Rt = 1.0 * minNum / (data.length - 1);
alpha = 1.0 * (Rt - rt) / (leafNodes.size() - 1);//计算G（t）
node.setAlpha(alpha);
} /**
* 筛选出节点所包含的叶子节点数
*
* @param node
* 待筛选节点
* @param leafNode
* 叶子节点列表容器
*/
private void addLeafNode(AttrNode node, ArrayList<AttrNode> leafNode) {
ArrayList<String> dataIndex; if (node.getChildAttrNode() != null) {
for (AttrNode childNode : node.getChildAttrNode()) {
dataIndex = childNode.getDataIndex();
if (dataIndex != null && dataIndex.size() > 0) {//dataIndex这个集合的元素
// 说明此节点为叶子节点
//System.out.println("leafNode.getLeafNum="+childNode.getLeafNum()); leafNode.add(childNode);
} else {
// 如果还是非叶子节点则继续递归调用 //System.out.println("middle Node.getLeafNum="+childNode.getLeafNum());
addLeafNode(childNode, leafNode);
}
}
}
} }
训练数据input.txt
Rid Age Income Student CreditRating BuysComputer
1 Youth High No Fair No
2 Youth High No Excellent No
3 MiddleAged High No Fair Yes
4 Senior Medium No Fair Yes
5 Senior Low Yes Fair Yes
6 Senior Low Yes Excellent No
7 MiddleAged Low Yes Excellent Yes
8 Youth Medium No Fair No
9 Youth Low Yes Fair Yes
10 Senior Medium Yes Fair Yes
11 Youth Medium Yes Excellent Yes
12 MiddleAged Medium No Excellent Yes
13 MiddleAged High Yes Fair Yes
14 Senior Medium No Excellent No
输出的结果如图所示：
attr remain null
attr remain null
剪枝前： --!--【1:Age】
--MiddleAged--【2】类别:Yes[3, 7, 12, 13, ]
--!MiddleAged--【3:Income】
--High--【4】类别:No[1, 2, ]
--!High--【5:Student】
--Yes--【6:CreditRating】
--Fair--【8】类别:Yes[5, 9, 10, ]
--!Fair--【9】类别:No[6, 11, ]
--!Yes--【7:CreditRating】
--Excellent--【10】类别:No[14, ]
--!Excellent--【11】类别:Yes[4, 8, ]
剪枝后： --!--【1:Age】
--MiddleAged--【2】类别:Yes[3, 7, 12, 13, ]
--!MiddleAged--【3:Income】
--High--【4】类别:No[1, 2, ]
--!High--【5:Student】
--Yes--【6:CreditRating】【 Child Null】
--!Yes--【7:CreditRating】
--Excellent--【10】类别:No[14, ]
--!Excellent--【11】类别:Yes[4, 8, ]