本文主要是介绍机器学习算法面试—口述(4):决策树,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
From http://codecloud.net/105575.html
这个系列是为了应对找工作面试时面试官问的算法问题,所以只是也谢算法的简要介绍,后期会陆续补充关于此
算法的常见面问题!
决策树是一种依托于策略抉择而建立起来的树,是一种依托于分类、训练上的预测树,根据已知,预测和分类未来。
决策树的建立是不断的使用数据的特征将数据分类的过程,主要的问题在于如何选择划分的特征;
常用的几种决策树算法有ID3、C4.5、CART等;其中ID3使用的是信息熵增益选大的方法划分数据,C4.5是使用增益率选大的方法划分数据,CART使用的是基尼指数选小的划分方法;
ID3:
该算法是以信息论为基础,以信息熵和信息增益度为衡量标准,从而实现对数据的归纳分类。ID3算法往往偏向于选择取值较多的属性,而在很多情况下取值较多的属性并不总是最重要的属性。而且ID3算法不能处理具有连续值的属性,也不能处理具有缺失数据的属性。
具体怎么算可以看一个例子:http://wenku.baidu.com/link?url=V_-Eh4p8UVaV93xT2MKUlbDVT1k1b9khZNa1hJOb1Fx0mNTDaLYLNqs4Chlz5nErVTtRG7V60RzPggzuZk26gyocFYXbliZhZ7VjDFqjfHe
C4.5:
使用的是增益率的划分方法,是ID3的一个改进,具有较高的准确率且可以处理连续属性。在构造树的过程中进行剪枝,使用的是悲观剪枝法(使用错误率来评估)!在构造树的过程中需要对树进行多次顺序扫描和排序,因此效率比较低,并且C4.5只适用于能够滞留于内存的数据集。
具体怎么算可以看一个例子:http://blog.csdn.net/xuxurui007/article/details/18045943
关于树的剪枝,可以参考:http://blog.csdn.net/woshizhouxiang/article/details/17679015
CART:
使用基尼指数的划分准则;通过在每个步骤最大限度降低不纯洁度,CART能够处理孤立点以及能够对空缺值进行处理。
树划分的终止条件:1、节点达到完全纯度; 2、树的深度达到用户所要深度
3、节点中样本的数量属于用户指定的个数;
树的剪枝方法是代价复杂性的剪枝方法;
具体见:http://blog.csdn.net/tianguokaka/article/details/9018933
收集自互联网,仅供学习交流使用!
这篇关于机器学习算法面试—口述(4):决策树的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!