精华内容
下载资源
问答
  • CART分类回归树的介绍

    2014-04-22 11:32:51
    关于CART分类回归树的详细介绍以及它的应用实例。对于想要了解或学习CART分类回归树的同学,会有所帮助。
  • 1、CART分类回归树简介   CART分类回归树是一种典型的二叉决策树,可以处理连续型变量和离散型变量。如果待预测分类是离散型数据,则CART生成分类决策树;如果待预测分类是连续型数据,则CART生成回归决策树。...
  • CART分类回归树

    千次阅读 2015-11-20 23:03:52
    这一篇主要是CART,有几个重点的词语先写下来,重点哦:基尼指数(Gini index,跟经济学的基尼系数长这么像...分类回归树。 简单的说呢,CART就是个二叉树(广义的决策树并不一定就是二叉树,可能好几叉。。。哈哈),所

    这一篇主要是CART,有几个重点的词语先写下来,重点哦:基尼指数(Gini index)、最小二乘回归树(least squares regression tree)
    CART:classification and regression tree。分类回归树。
    简单的说呢,CART就是个二叉树(广义的决策树并不一定就是二叉树,可能好几叉。。。哈哈),所以内部节点的取值就是“是”“否”的了。
    直接介绍算法吧,CART的基本原理和广义的决策树是一样的,就相当于二叉树都有普通树的特征。

    下面直接介绍回归树的算法:
    1. 回归树的生成:基于训练数据集生成决策树,尽量大点。
    2. 回归树剪枝:用验证数据集对已生成的树进行剪枝并选择最优子树,这时用损失函数最小作为剪枝的标准。
    完了,,,很简单的。哈哈

    下面介绍一下详细的算法,重点还是大多参考了统计学习方法的:
    简单介绍一下理论:给定数据集这里写图片描述
    假设已经将输入空间划分为M个单元R_1、R_2、…R_M,并且每个单元都有一个固定的输出值C_m,则回归树的模型为:
    这里写图片描述

    训练数据集的预测误差为:平方误差这里写图片描述
    平方误差是用来球每个单元上的最优输出值
    即:这里写图片描述
    那么怎么选择划分的那条线呢?
    选择第j个变量x_j和取得值s,定义两个区域:
    这里写图片描述
    那么在这里我们就寻找最优的j和s,也就是求解:
    这里写图片描述
    书上是这样的,但是我感觉中括号里的两个min就不要了。删掉就好。
    求解的过程待会见回归树生成算法。

    通常,通过以上过程建立的回归树叫做最小二乘回归树。
    最小二乘回归树的生成算法:
    输入:训练数据集D
    输出:回归树f(x)
    在训练数据集所在的输入空间中,递归的将每个区域划分为两个子区域并决定每个子区域上的输出值,构建二车决策树:
    1). 选择最优划分变量j和s;
    求解:
    这里写图片描述

    遍历变量j,对固定的j扫描s,选择是上式最小值的(j,s);
    2). 用选定的(j,s)划分区域并决定相应的输出值;
    这里写图片描述
    这里写图片描述
    3). 继续1)、2)步骤,直至满足条件;
    4).将输入空间划为M个区域,R_1…….R_m,生成决策树:
    这里写图片描述

    接下来是什么呢?上边是回归,下边就是分类了,分类树的生成是怎么做的呢?
    最开始的基尼指数就要开始登场了:
    分类树是通过基尼指数来选择最优特征的,同时决定该特征的最优切分点。
    基尼指数:假设有k个类,样本属于第k个类的概率为P_k, 则此概率分布的基尼指数定义为:这里写图片描述
    对于给定的离散数据集D, 其基尼指数为:这里写图片描述
    如果样本集合D根据特征A是否去某一个值a被分割为D_1、D_2,
    即: 这里写图片描述
    那么这就是在特征A的条件下D的基尼指数是:
    这里写图片描述
    基尼指数求出来了,那么基尼指数有什么意义呢?
    基尼指数表示集合D的不确定性,基尼指数这里写图片描述 表示经过特征A分割后D的不确定性,跟条件熵是不是很相似。。。Gini(D)和熵也是很类似的。
    CART的分类树生成算法:
    输入: 训练数据集D,停止计算的条件。
    输出: CART决策树.
    根据训练数据集,从根节点开始,递归的对每一个结点进行以下操作,构建决策树。
    1. 设结点的训练集为D,计算现有特征对该数据集的基尼指数,此时,对每一个特征A,对其可能取的每一个值a,根据样本点对A=a的测试是“是”还是“否”,将D分割成D_1,D_2,利用上边的式子计算A=a时的基尼指数。
    2. 在所有可能的特征A以及它们所有可能的切分点a中,选择基尼指数最小的特征及其对应的切分点作为最优特征与最优切分点(基尼指数越大不确定性越大,不好,所以选小的)。依最优特征与最优切分点,从现结点生成两个子结点,将训练数据集依特征分配到两个子结点中去。
    3. 对两个子结点递归的调用步骤1. 2.直至满足条件。
    4. 生成CART决策树。
    算法停止的条件是结点中的样本个数小于预定阈值,或样本的基尼指数小于预定阈值(样本基本属于同一类),或者没有更多特征了。

    完了。。。。。这就是分类回归树的理论原理,还剩了个剪枝没记录,但是剪枝就涉及自己实现的时候用到的,等以后自己实现的时候用到了再详细解释吧。下一个是随机森林和随机蕨。

    展开全文
  • CART分类回归树算法

    万次阅读 2015-01-09 18:37:27
    CART分类回归树算法 与上次文章中提到的ID3算法和C4.5算法类似,CART算法也是一种决策树分类算法。CART分类回归树算法的本质也是对数据进行分类的,最终数据的表现形式也是以树形的模式展现的,与ID3,C4.5算法不同...

    CART分类回归树算法

    与上次文章中提到的ID3算法和C4.5算法类似,CART算法也是一种决策树分类算法。CART分类回归树算法的本质也是对数据进行分类的,最终数据的表现形式也是以树形的模式展现的,与ID3,C4.5算法不同的是,他的分类标准所采用的算法不同了。下面列出了其中的一些不同之处:

    1、CART最后形成的树是一个二叉树,每个节点会分成2个节点,左孩子节点和右孩子节点,而在ID3和C4.5中是按照分类属性的值类型进行划分,于是这就要求CART算法在所选定的属性中又要划分出最佳的属性划分值,节点如果选定了划分属性名称还要确定里面按照那个值做一个二元的划分。

    2、CART算法对于属性的值采用的是基于Gini系数值的方式做比较,gini某个属性的某次值的划分的gini指数的值为:

    ,pk就是分别为正负实例的概率,gini系数越小说明分类纯度越高,可以想象成与熵的定义一样。因此在最后计算的时候我们只取其中值最小的做出划分。最后做比较的时候用的是gini的增益做比较,要对分类号的数据做出一个带权重的gini指数的计算。举一个网上的一个例子:

    比如体温为恒温时包含哺乳类5个、鸟类2个,则:

    体温为非恒温时包含爬行类3个、鱼类3个、两栖类2个,则

    所以如果按照“体温为恒温和非恒温”进行划分的话,我们得到GINI的增益(类比信息增益):

    最好的划分就是使得GINI_Gain最小的划分。

    通过比较每个属性的最小的gini指数值,作为最后的结果。

    3、CART算法在把数据进行分类之后,会对树进行一个剪枝,常用的用前剪枝和后剪枝法,而常见的后剪枝发包括代价复杂度剪枝,悲观误差剪枝等等,我写的此次算法采用的是代价复杂度剪枝法。代价复杂度剪枝的算法公式为:

    α表示的是每个非叶子节点的误差增益率,可以理解为误差代价,最后选出误差代价最小的一个节点进行剪枝。

    里面变量的意思为:

    是子树中包含的叶子节点个数;

    是节点t的误差代价,如果该节点被剪枝;

    r(t)是节点t的误差率;

    p(t)是节点t上的数据占所有数据的比例。

    是子树Tt的误差代价,如果该节点不被剪枝。它等于子树Tt上所有叶子节点的误差代价之和。下面说说我对于这个公式的理解:其实这个公式的本质是对于剪枝前和剪枝后的样本偏差率做一个差值比较,一个好的分类当然是分类后的样本偏差率相较于没分类(就是剪枝掉的时候)的偏差率小,所以这时的值就会大,如果分类前后基本变化不大,则意味着分类不起什么效果,α值的分子位置就小,所以误差代价就小,可以被剪枝。但是一般分类后的偏差率会小于分类前的,因为偏差数在高层节点的时候肯定比子节点的多,子节点偏差数最多与父亲节点一样。

    CART算法实现

    首先是程序的备用数据,我是把他存在了一个文字中,通过程序进行逐行的读取:

    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
    下面是主程序,里面有具体的注释:

    package DataMing_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.Map;
    import java.util.Queue;
    
    import javax.lang.model.element.NestingKind;
    import javax.swing.text.DefaultEditorKit.CutAction;
    import javax.swing.text.html.MinimalHTMLWriter;
    
    /**
     * CART分类回归树算法工具类
     * 
     * @author lyq
     * 
     */
    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];
    
    		/*
    		 * for (int i = 0; i < data.length; i++) { for (int j = 0; j <
    		 * data[0].length; j++) { System.out.print(" " + data[i][j]); }
    		 * System.out.print("\n"); }
    		 */
    
    	}
    
    	/**
    	 * 首先初始化每种属性的值的所有类型,用于后面的子类熵的计算时用
    	 */
    	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);
    		}
    
    		/*
    		 * for (Map.Entry entry : attrValue.entrySet()) {
    		 * System.out.println("key:value " + entry.getKey() + ":" +
    		 * entry.getValue()); }
    		 */
    	}
    
    	/**
    	 * 计算机基尼指数
    	 * 
    	 * @param remainData
    	 *            剩余数据
    	 * @param attrName
    	 *            属性名称
    	 * @param value
    	 *            属性值
    	 * @param beLongValue
    	 *            分类是否属于此属性值
    	 * @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;
    
    		// 返回计算基尼指数
    		return gini;
    	}
    
    	/**
    	 * 计算属性划分的最小基尼指数,返回最小的属性值划分和最小的基尼指数,保存在一个数组中
    	 * 
    	 * @param remainData
    	 *            剩余谁
    	 * @param attrName
    	 *            属性名称
    	 * @return
    	 */
    	public String[] computeAttrGini(String[][] remainData, String attrName) {
    		String[] str = new String[2];
    		// 最终该属性的划分类型值
    		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) {
    			// 重新计数的时候,数字归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;
    		str[1] = minGini + "";
    
    		return str;
    	}
    
    	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) {
    			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]);
    				}
    				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);
    
    		// 孩子节点,分类回归树中,每次二元划分,分出2个孩子节点
    		AttrNode[] childNode = new AttrNode[2];
    		String[][] rData;
    
    		boolean[] bArray = new boolean[] { true, false };
    		for (int i = 0; i < bArray.length; i++) {
    			// 二元划分属于属性值的划分
    			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);
    		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;
    		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
    			minAlphaNode.setChildAttrNode(null);
    		}
    	}
    
    	/**
    	 * 为非叶子节点计算误差代价,这里的后剪枝法用的是CCP代价复杂度剪枝
    	 * 
    	 * @param node
    	 *            待计算的非叶子节点
    	 */
    	private void computeAlpha(AttrNode node) {
    		double rt = 0;
    		double Rt = 0;
    		double alpha = 0;
    		// 当前节点的数据总数
    		int sumNum = 0;
    		// 最少的偏差数
    		int minNum = 0;
    
    		ArrayList<String> dataIndex;
    		ArrayList<AttrNode> leafNodes = new ArrayList<>();
    
    		addLeafNode(node, leafNodes);
    		node.setLeafNum(leafNodes.size());
    		for (AttrNode attrNode : leafNodes) {
    			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;
    
    			// 取小数量的值部分
    			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);
    		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) {
    					// 说明此节点为叶子节点
    					leafNode.add(childNode);
    				} else {
    					// 如果还是非叶子节点则继续递归调用
    					addLeafNode(childNode, leafNode);
    				}
    			}
    		}
    	}
    
    }
    
    AttrNode节点的设计和属性:

    /**
     * 回归分类树节点
     * 
     * @author lyq
     * 
     */
    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;
    	.....
    get,set方法自行补上。客户端的场景调用:

    package DataMing_CART;
    
    public class Client {
    	public static void main(String[] args){
    		String filePath = "C:\\Users\\lyq\\Desktop\\icon\\input.txt";
    		
    		CARTTool tool = new CARTTool(filePath);
    		
    		tool.startBuildingTree();
    	}
    }
    
    数据文件路径自行修改,否则会报错(特殊情况懒得处理了.....)。最后程序的输出结果,请自行从左往右看,从上往下,左边的是父亲节点,上面的是考前的子节点:

    剪枝前:
    
        --!--【1:Age】
            --MiddleAged--【2】类别:Yes[3, 7, 12, 13, ]
            --!MiddleAged--【3:Student】
                    --No--【4:Income】
                                    --High--【6】类别:No[1, 2, ]
                                    --!High--【7:CreditRating】
                                                                    --Fair--【10】类别:Yes[4, 8, ]
                                                                    --!Fair--【11】类别:No[14, ]
                    --!No--【5:CreditRating】
                                    --Fair--【8】类别:Yes[5, 9, 10, ]
                                    --!Fair--【9:Income】
                                                                    --Medium--【12】类别:Yes[11, ]
                                                                    --!Medium--【13】类别:No[6, ]
    剪枝后:
    
        --!--【1:Age】
            --MiddleAged--【2】类别:Yes[3, 7, 12, 13, ]
            --!MiddleAged--【3:Student】
                    --No--【4:Income】【  Child Null】
                    --!No--【5:CreditRating】
                                    --Fair--【8】类别:Yes[5, 9, 10, ]
                                    --!Fair--【9:Income】
                                                                    --Medium--【12】类别:Yes[11, ]
                                                                    --!Medium--【13】类别:No[6, ]

    结果分析:

    我在一开始的时候根据的是最后分类的数据是否为同一个类标识的,如果都为YES或者都为NO的,分类终止,一般情况下都说的通,但是如果最后属性划分完毕了,剩余的数据还有存在类标识不一样的情况就会偏差,比如说这里的7号CredaRating节点,下面Fair分支中的[4,8]就不是同类的。所以在后面的剪枝算法就被剪枝了。因为后面的4和7号节点的误差代价率为0,说明分类前后没有类偏差变化,这也见证了后剪枝算法的威力所在了。

    在coding遇到的困难和改进的地方:

    1、先说说在编码时遇到的困难,在对节点进行赋索引标号值的时候出了问题,因为是之前生成树的时候采用了DFS的思想,如果编号时也采用此方法就不对了,于是就用到了把节点取出放入队列这样的遍历方式,就是BFS的方式为节点标号。

    2、程序的一个改进的地方在于算一个非叶子节点的时候需要计算他所包含的叶子节点数,采用了从当前节点开始从上往下递归计算,而且每个非叶子节点都计算一遍,显然这样做的效率是不高,后来想到了一种从叶子节点开始计算,从下往上直到根节点,对父亲节点的非叶子节点列表做更新操作,就只要计算一次,这有点dp的思想在里面了,由于时间关系,没有来得及实现。

    3、第二个优化点就是后剪枝算法的多样化,我这里采用的是CCP代价复杂度算法,大家可以试着实现其他的诸如悲观误差算法进行剪枝,看看能不能把程序中4和7号节点识别出来,并且剪枝掉。

    最后声明一下,用了里面的一点点的公式和例子,参考资料:http://blog.csdn.net/tianguokaka/article/details/9018933

    展开全文
  • 回归树三、剪枝算法 2021人工智能领域新星创作者,带你从入门到精通,该博客每天更新,逐渐完善机器学习各个知识体系的文章,帮助大家更高效学习。 一、概述 针对于ID3和C4.5只能处理分类的问题,后来有人提出了...

    如果需要完整代码可以关注下方公众号,后台回复“代码”即可获取,阿光期待着您的光临~


    2021人工智能领域新星创作者,带你从入门到精通,该博客每天更新,逐渐完善机器学习各个知识体系的文章,帮助大家更高效学习。


    一、概述

    针对于ID3和C4.5只能处理分类的问题,后来有人提出了CART,该模型是由Breima等人在1984年提出的,它是被应用广泛的决策树学习方法,它可以用于分类与回归问题,同样CART也是由特征选择、树的生成以及剪枝组成。

    所以针对于该算法可以分为几种情况:

    数据:离散型特征、连续型特征

    标签:离散值、连续值

    针对于不同的场景处理方式也大不相同,一般情况下选择特征划分节点时,如果标签为离散的,我们可以使用基尼系数作为划分标准,在ID3和C4.5中是使用信息增益方式进行评估,在CART中是使用基尼系数,如果标签是连续性的,显然不能够使用基尼系数,因为此时无法计算每个节点不同类别的概率,应使用均方误差来进行评估,原来是使用每个节点的熵值期望与原来的熵做差,如果标签连续使用均方误差,每个节点的均方误差与分割前节点的均方误差做对比。

    二、CART决策树

    1.分类树

    其实CART分类树和ID3和C4.5的树生成算法差不多,只不过是在特征选择是采用了基尼系数

    1.1 基尼系数

    基尼系数公式的定义如下:
    G i n i ( p ) = ∑ i = k K p k ( 1 − p k ) = 1 − ∑ k = 1 K p k 2 Gini(p)=\sum_{i=k}^Kp_k(1-p_k)=1-\sum_{k=1}^Kp_k^2 Gini(p)=i=kKpk(1pk)=1k=1Kpk2

    G i n i ( D ) = 1 − ∑ k = 1 K ( ∣ C k ∣ ∣ D ∣ ) 2 Gini(D)=1-\sum_{k=1}^K(\frac{|C_k|}{|D|})^2 Gini(D)=1k=1K(DCk)2

    • K:样本的类别个数
    • p k p_k pk :每个类别的概率
    • C k C_k Ck :每个类别的样本数
    • D:样本总数

    所以我们需要计算根据一个特征分割后的基尼系数与分割前的基尼系数做差:

    假设A特征有两个值,所以可以分成两个节点,那么分割后的基尼系数为:
    G i n i ( D , A ) = p 1 G i n i ( D 1 ) + p 2 G i n i ( D 2 ) = ∣ D 1 ∣ ∣ D ∣ G i n i ( D 1 ) + ∣ D 2 ∣ ∣ D ∣ G i n i ( D 2 ) Gini(D,A)=p_1Gini(D_1)+p_2Gini(D_2)\\=\frac{|D_1|}{|D|}Gini(D_1)+\frac{|D_2|}{|D|}Gini(D_2) Gini(D,A)=p1Gini(D1)+p2Gini(D2)=DD1Gini(D1)+DD2Gini(D2)
    我们也需要获得增益:
    G i n i ( D , A ) − G i n i ( D ) Gini(D,A)-Gini(D) Gini(D,A)Gini(D)
    其实这个和熵非常相似,只不过是换个衡量指标罢了。

    1.1 特征离散

    如果特征是离散的,那么它就是按照特征的可选值进行划分节点,该特征有几个离散值,那么就划分成几个节点,和ID3、C4.5决策树一样。

    1.2 特征连续

    如果特征值是连续的,划分节点时就不能够按照特征的可选数量进行分割节点,因为连续特征有很多可选值,所以肯定不能和离散特征一样的分割方式,它是采用二叉树的方式,每次按照连续特征分成两个分支,分割方式为将待分割特征的所有值从小到大排序,然后选中其中一个值作为划分点,将样本划分为两个部分。

    比如说,有一列特征A,值为 [ 1 , 5 , 2 , 6 , 8 , 3 ] [1,5,2,6,8,3] [1,5,2,6,8,3]​ ,按照顺序进行排序, [ 1 , 2 , 3 , 5 , 6 , 8 ] [1,2,3,5,6,8] [1,2,3,5,6,8]​ ,所以可选的值很多,我们假设选中3作为划分点,将原始样本划分为: [ 1 , 2 , 3 ] [1,2,3] [1,2,3]​ 和 [ 5 , 6 , 8 ] [5,6,8] [5,6,8]​ 。

    image-20210826145838753

    按照连续型特征分割后然后在用基尼系数进行评估。

    2.回归树

    其实回归树就是标签为连续型的,所以此时不能够使用基尼系数、熵这种的概率评估作为评估指标,因为不是分类不能够利用古典概型求出概率,所以我们考虑使用均方误差作为特征划分的好坏,将划分后的每个节点所有样本的均方误差之和之前没划分的节点的均方误差做差来代替基尼系数。

    之前分类问题是计算所有特征的信息增益,此时我们会计算每个特征按照每个划分点的均方误差:
    m i n j , s [ m i n c 1 ∑ x i ∈ R 1 ( j , s ) ( y i − c 1 ) 2 + m i n c 2 ∑ x i ∈ R 2 ( j , s ) ( y i − c 2 ) 2 ] min_{j,s}[min_{c_1}\sum_{xi\in R_1(j,s)}(y_i-c1)^2+min_{c_2}\sum_{xi\in R_2(j,s)}(y_i-c2)^2] minj,s[minc1xiR1(j,s)(yic1)2+minc2xiR2(j,s)(yic2)2]
    上面的j是不同的特征,s是对应每个特征可供选择的划分点,因为一个连续特征的值很多,所以划分点很多,要选择最优的。

    中括号内的意思就是找出针对特征j的最优划分点s,采用均方误差,最外层是特征,计算不同特征。

    回归的比分类相对麻烦一些,分类只需要计算每个特征的信息增益,回归是计算每个特征的均方误差增益,但是它多了一个步骤就是求每个特征增益的时候还要找出最优划分值s。

    这样生成的树成为最小二乘回归树。

    算法流程:

    1. 选择最优切分特征j和切分点s

    m i n j , s [ m i n c 1 ∑ x i ∈ R 1 ( j , s ) ( y i − c 1 ) 2 + m i n c 2 ∑ x i ∈ R 2 ( j , s ) ( y i − c 2 ) 2 ] min_{j,s}[min_{c_1}\sum_{xi\in R_1(j,s)}(y_i-c1)^2+min_{c_2}\sum_{xi\in R_2(j,s)}(y_i-c2)^2] minj,s[minc1xiR1(j,s)(yic1)2+minc2xiR2(j,s)(yic2)2]

    1. 用选定的对(j,s)划分区域并决定相应的输出值:

    R 1 ( j , s ) = { x ∣ x ( j ) ≤ s } R 2 ( j , s ) = { x ∣ x ( j ) > s } R_1(j,s)=\{x|x^{(j)}\leq s\}\quad R_2(j,s)=\{x|x^{(j)}> s\} R1(j,s)={xx(j)s}R2(j,s)={xx(j)>s}

    c m = 1 N m ∑ x i ∈ R m ( j , s ) y i x ∈ R m , m = 1 , 2 c_m=\frac{1}{N_m}\sum_{x_i\in R_m(j,s)}y_i \quad x\in R_m,m=1,2 cm=Nm1xiRm(j,s)yixRm,m=1,2

    第一个式子是将数据按照切分点分成两个节点,第二个是求每个节点的均方误差之和。

    1. 继续对两个子区域调用步骤1,2直至满足停止条件
    2. 将输入空间划分为M个区域, R 1 , R 2 , . . . R M R_1,R_2,...R_M R1,R2,...RM ,生成决策树:

    f ( x ) = ∑ i = 1 M c m I ( x ∈ R m ) f(x)=\sum_{i=1}^Mc_mI(x\in R_m) f(x)=i=1McmI(xRm)

    该式子的意思是求分到相同节点的均值作为预测值,后面的指示函数作为划分到那么区域。

    三、剪枝算法

    同样针对于CART决策树也存在防止过拟合的方法剪枝,CART剪枝算法由两步组成,首先从生成算法产生的决策树 T 0 T_0 T0 底端开始不断剪枝,直到 T 0 T_0 T0 的根节点,形成一个子树序列 { T 0 , T 1 , . . . , T n } \{T_0,T_1,...,T_n\} {T0,T1,...,Tn} ,然后通过交叉验证法在独立的验证数据集熵对于子树序列进行测试,从中选择最优子树。

    我们定义树模型的损失函数为:
    C a ( T ) = C ( T ) + a ∣ T ∣ C_a(T)=C(T)+a|T| Ca(T)=C(T)+aT
    其中 C ( T ) C(T) C(T) 为模型的预测误差(基尼系数、熵信息增益等), a ∣ T ∣ a|T| aT 代表模型的复杂度,其中 ∣ T ∣ |T| T 代表模型叶节点的个数,所以 C a ( T ) C_a(T) Ca(T) 可以作为树的整体损失,参数 a用于权衡训练数据的拟合程度与模型的复杂度。

    取两个极端情况,如果a=0,那么此时的树是最茂盛的,如果a趋于无穷大,那么此时的树就为一个根节点,所以随着a的增大,我们的树会不断变小。

    首先对 T 0 T_0 T0​ 的任意内部节点t,以t为单节点树的损失函数为:
    C a ( t ) = C ( t ) + a C_a(t)=C(t)+a Ca(t)=C(t)+a
    因为此时只有一个叶子节点。

    以t为根节点的子树 T t T_t Tt 的损失函数为:
    C a ( T t ) = C ( T t ) + a ∣ T t ∣ C_a(T_t)=C(T_t)+a|T_t| Ca(Tt)=C(Tt)+aTt
    当a=0时,有:
    C a ( T t ) < C a ( t ) C_a(T_t)<C_a(t) Ca(Tt)<Ca(t)
    因为此时此时过拟合,很显然可以看出,当a增大时,存在a使得:
    C a ( T t ) = C a ( t ) C_a(T_t)=C_a(t) Ca(Tt)=Ca(t)
    此时我们认为t节点和以该节点为根节点的子树损失值相同,损失同等情况下,我们选择复杂度小的t,所以进行剪枝,将t作为叶子节点。

    此时的a为:
    g ( t ) = a = C ( t ) − C ( T t ) ∣ T t ∣ − 1 g(t)=a=\frac{C(t)-C(T_t)}{|T_t|-1} g(t)=a=Tt1C(t)C(Tt)
    T 0 T_0 T0 中减去 g ( t ) g(t) g(t) 最小的 T ( t ) T(t) T(t) ,将得到的子树作为 T 1 T_1 T1 ,同时将最小的 g ( t ) g(t) g(t) 设为 a 1 a_1 a1 ,如此剪枝下去,直至得到根节点,然后利用独立的验证数据集取交叉验证获得的子树序列 T 0 , T 1 , . . . T n T_0,T_1,...T_n T0,T1,...Tn 获得最优决策树 T a T_a Ta ,其中每个决策子树对应一个 a。

    写在最后

            大家好,我是阿光,觉得文章还不错的话,记得“一键三连”哦!!!

    img

    展开全文
  • CART分类回归树分析与python实现

    千次阅读 2017-11-01 16:27:16
    引言前面我们分享过一篇决策算法叫ID3:ID3决策原理分析及python实现。首先我们来回顾下ID3算法。ID3每次选取最佳特征来分割数据,这个最佳特征的判断原则是通过信息增益来实现的。这种按某种特征切分完数据集后...

    引言

    前面我们分享过一篇决策树算法叫ID3:ID3决策树原理分析及python实现。首先我们来回顾下ID3算法。ID3每次选取最佳特征来分割数据,这个最佳特征的判断原则是通过信息增益来实现的。这种按某种特征切分完数据集后,当前特征在下次切分数据集时就不再起作用,因此会存在切分方式过于迅速地问题。ID3算法还存在另一个问题就是它不能直接处理连续型特征,因此算法需要改进。于是有人提出了二元切分法很好的解决了连续性变量问题及切分迅速的问题。其中代表性算法就是CART。

    CART分类回归树

    CART是Classification And Regression Trees的缩写叫做“分类回归树”。它既能做分类任务又能做回归任务。

    • 分类树:目标变量是类别数据,树被用来识别目标变量可能属于哪个类
      cla
    • 回归树:目标变量是连续数据,树被用来预测目标变量的值是多少
      reg

    CART树的典型代表就是二叉树,如下图所示:
    cart-bin

    CART树构建算法

    因为ID3决策树分享时,我们已经分享过树构建算法的流程,这里我们就直接来实现CART树构建的过程。

    树构建框架

    在树的构建过程中,与ID3类似采用字典来存储树的数据结构,该字典包含以下4种元素:

    • 待切分的特征
    • 待切分的特征值
    • 右子树。当不再需要切分的时候,也可以是单个值
    • 左子树。与右子树类似

    函数createTree()伪代码如下:
    createTree
    可以很明显的发现这是个典型的递归算法。
    这个算法与ID3创建分支的算法createBranch()十分类似:
    id3
    划分数据集的代码如下:

    def binSplitDataSet(dataSet, feature, value):
        mat0 = dataSet[nonzero(dataSet[:,feature] > value)[0],:]
        mat1 = dataSet[nonzero(dataSet[:,feature] <= value)[0],:]
        return mat0,mat1

    通过数组过滤方式将数据集合切分得到两个子集并返回。

    划分数据点

    创建二进制决策树本质上就是递归划分输入空间的过程。有一种贪心的算法用来划分这个空间被称为递归二进制划分。所有输入变量和所有可能的分割点都以贪婪的方式进行评估和选择(例如,每次选择最佳的分割点)。

    对分类问题来说,基尼指数(Gini index)被用来选择划分的属性,数据集的纯度可用基尼值来衡量:

    Gini(D)=1k=1|y|p2k

    直观地来说,Gini(D)反映了从数据集D中随机抽取两个样本,其类别标记不一致的概率。因此Gini(D)越小,则数据集D的纯度越高。对于二分类问题,这就可以写成:
    Gini(D)=1p21p22

    那么属性a的基尼指数定义为
    Gini_index(D,a)=v=1V|Dv||D|Gini(Dv)

    于是,我们在候选属性集合A中,选择那个使得划分后基尼指数最小的属性作为最优划分属性。
    对回归问题来说,用最小代价函数来划分数据点,度量方法就是平方误差的总值(总方差)

    构建树

    在我们构建树的伪代码中有一个“find the best feature to split data”函数,前面我们已经分析了构建回归树时的误差计算方法,根据这个方法就能找到数据集上最佳的二元切分方式。因此这个函数将会完成两部分内容:1.用最佳方式切分数据集 2.生成相应的叶节点
    我们实现“find the best feature to split data”函数chooserBestSplit(),它的伪代码如下:
    choose
    上述伪代码的目标是找到数据集切分的最佳位置。它遍历所有的特征及其可能的取值来确定使误差最小化的切分阈值。
    代码如下:

    def chooseBestSplit(dataSet, leafType=regLeaf, errType=regErr, ops=(1,4)):
        tolS = ops[0]; tolN = ops[1]
        #if all the target variables are the same value: quit and return value
        if len(set(dataSet[:,-1].T.tolist()[0])) == 1: #exit cond 1
            return None, leafType(dataSet)
        m,n = shape(dataSet)
        #the choice of the best feature is driven by Reduction in RSS error from mean
        S = errType(dataSet)
        bestS = inf; bestIndex = 0; bestValue = 0
        for featIndex in range(n-1):
            for splitVal in set(dataSet[:,featIndex]):
                mat0, mat1 = binSplitDataSet(dataSet, featIndex, splitVal)
                if (shape(mat0)[0] < tolN) or (shape(mat1)[0] < tolN): continue
                newS = errType(mat0) + errType(mat1)
                if newS < bestS: 
                    bestIndex = featIndex
                    bestValue = splitVal
                    bestS = newS
        #if the decrease (S-bestS) is less than a threshold don't do the split
        if (S - bestS) < tolS: 
            return None, leafType(dataSet) #exit cond 2
        mat0, mat1 = binSplitDataSet(dataSet, bestIndex, bestValue)
        if (shape(mat0)[0] < tolN) or (shape(mat1)[0] < tolN):  #exit cond 3
            return None, leafType(dataSet)
        return bestIndex,bestValue#returns the best feature to split on
                                  #and the value used for that split

    上述代码有出返回即函数退出条件:1.剩余特征数目为1;直接返回 2.切分数据集后效果提升不大,不需进行切分操作而直接创建叶节点;3提前终止条件均不满足,返回切分特征和特征值。

    剪枝

    在决策树的学习中,有时会造成决策树分支过多,这时就需要去掉一些分支从而降低过拟合的风险。通过降低决策树复杂度来避免过拟合的过程称为剪枝。一种是预剪枝,一种是后剪枝。

    预剪枝

    前面我们的chooseBestSplit()代码里已经有了预减枝的处理就是提前终止条件。但是树构建算法对这些提前终止条件很敏感,通过不断地修改停止条件来得到合理地结果并不是很好的办法。于是就有人提出了利用测试集对树进行减枝就是我们接下来要分析的后剪枝。

    后剪枝

    后剪枝需要从训练集生成一棵完整的决策树,然后自底向上对非叶子结点进行考察,利用测试集判断若将该结点对应的子树替换成叶结点,能否带来决策树泛化性能的提升?将上述思路转换成伪代码如下:
    prune

    总结

    本次博文主要分享了CART树的构建过程,然后稍稍介绍了下剪枝的方法

    展开全文
  • classification and regression trees 简称分类回归树,可以用来处理分类或者回归问题。 分类树的节点split依据选择gini系数最小的分裂点,gini系数越小不确定性越小。 回归树的节点分类采用最小方差作为分裂点的...
  • CART分类回归树

    万次阅读 2018-09-10 11:30:04
    一、CART分类回归树 资料转载: http://dataunion.org/5771.html http://blog.sina.com.cn/s/blog_afe2af380102x020.html  Classification And Regression Tree(CART)是决策树的一种,并且是非常重要的决策树...
  • 机器学习--CART分类回归树

    千次阅读 2018-10-30 17:09:04
    许多问题都是非线性的,用线性模型并不能很好的拟合数据,这种情况下可以使用树回归来拟合数据。介绍CART, 树剪枝,模型树。...CART 分类回归树,既能分类又能回归。CRAT来进行节点决策时,使用二元...
  • 本文记录一下关于CART的相关知识其中包括(回归树、树的后剪枝、模型树、树回归模型的预测(树回归模型的评估))。在之前学习完ID3算法有记录一篇相关的学习笔记,所以后面学习CART算法能有一个比较和熟悉的理解。 ...
  • 决策树之CART分类回归树)详解

    万次阅读 多人点赞 2017-05-15 22:20:30
    CART分类回归树简介 CART分类回归树分裂属性的选择 CART分类回归树的剪枝 1、CART分类回归树简介   CART分类回归树是一种典型的二叉决策树,可以做分类或者回归。如果待预测结果是离散型数据,则CART生成分类...
  • CART(Classification and Regression Tree)即分类回归树算法。其决策树的生成就是递归的构建二叉决策树的过程。每次划分都把当前样本集划分为两个子样本集。对回归树用平方误差最小化准则,对分类树用基尼指数最小...
  • CART 生成1.1 回归树生成最小二乘回归树生成算法1.2 分类树生成基尼指数CART 生成算法参考文献 相关文章: 机器学习 | 目录 监督学习 | ID3 决策树原理及Python实现 监督学习 | ID3 & C4.5 决策树原理 监督学习...
  • 决策树系列(三):CART(分类回归树)-详细原理解析

    千次阅读 热门讨论 2019-03-21 17:34:21
    CART分类回归树,是几乎所有复杂决策树算法的基础。下面简单介绍其算法原理。
  • 分类树CART树python实现(含数据集),结构清晰易懂,适合初学者
  • 这是一个用python实现的cart回归树(不是调用sklearn的), 可以调整参数,并且打印决策树并用plt展示数据和回归线,demo是回归模型,返回的值是平均值,稍微修改后可以用于分类
  • CART回归树CART分类树的区别

    千次阅读 2018-07-15 00:57:33
    除了概念的不同,CART回归树CART分类树的建立和预测的区别主要有下面两点:1)连续值的处理方法不同2)决策树建立后做预测的方式不同。对于连续值的处理,CART分类树采用的是用基尼系数的大小来度量特征的各个划分点...
  • 决策树算法(CART分类树和回归树

    千次阅读 2019-05-27 13:53:21
    1、CART树:可以解决分类回归问题 2、分裂节点的选择: CART树选取特征是根据基尼系数,基尼系数越小,模型的不纯度越小。ID3、C4.5都是基于熵的运存,会涉及大量的对数运算,为了解决这个问题,CART树用基尼...
  • '''建立回归树''' feat,val=choose_best_split(data,leaftype,errtype,ops) #分类特征,分类值 if feat == None:return val #如果分类特征为空,则返回分类值。应该理解为样本数据根据单一值就可以很好的划分。...
  • 机器学习实战-CART分类回归树

    千次阅读 2017-03-18 12:00:54
    树回归  虽然线性回归有强大的功能,但是在遇到数据具有很多特征时且特征之间具有复杂的关系时,构建全局的模型就显得比较难,而且也比较笨重,而且实际中处理的数据一般都是非线性的,不可能用全局线性模型来...
  • CART-分类回归树CART 算法的思路 特征选择:最优属性划分依据是 基尼系数(分类)/平方误差(回归); CART 树是二叉树结构。 主要就两步骤: 树的生成 树的剪枝 分类树 分类树与ID3, C4.5的流程一致。 回归树...
  • 分类回归树CART)C ++实现 目录 介绍 资料格式 介绍 CART分类树和回归树的C ++实现,这是DM(数据挖掘)的著名算法。 这是此实现的源代码。 资料格式 培训和测试数据文件的格式为: ::...。 。 。 每行...
  • CART-分类回归树

    千次阅读 2018-08-15 20:28:19
    然而决策不仅可以用来做数据分类,也可用于做数据回归。1984年Breiman,Friedman,Olshen等人出版了著作《Classification and Regression Trees》(简称CART)介绍了二叉决策的产生。他们给出了用二叉决策进行...
  • CART分类回归树-(python3)

    千次阅读 2017-10-10 20:24:33
    一、树回归 1、简介 假设X与Y分别是输入和输出向量,并且Y是连续变量,给定训练数据集 考虑如何生成回归树。...,于是回归树模型可表示为(简单来说就是把数据集划分为多份数据,且每份数据集里面
  • matlab实现cart回归分类树

    千次阅读 2017-03-20 16:13:00
    作为机器学习的小白和matlab的小白自己参照 python的 《机器学习实战》 写了一下分类回归树,这里记录一下。 关于决策树的基础概念就不过多介绍了,至于是分类还是回归。。我说不清楚。。我用的数据集是这个...
  • 分类回归树 该软件使用随机森林中的回归树对数据矩阵进行分类。 该软件有两个版本:python 文件夹中的 Python 版本。 有一个 C++ 版本,它在根文件夹中更快更准确。 两个版本都采用并行编程并在多个线程或进程中...
  • 分类-回归树模型(CART)在R语言中的实现
  • Classification And Regression Tree(CART)是一种很重要的机器学习算法,既可以用于创建分类树(Classification Tree),也可以用于创建回归树(Regression Tree),本文介绍了CART用于离散标签分类决策和连续特征...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 14,320
精华内容 5,728
关键字:

cart分类回归树