决策树算法概述
简单的说,决策树算法可以从训练数据集中提取出一系列规则,这种根据数据集创建规则的过程,就是机器学习的过程。学习的结果就是得到了“知识信息”,即可以复用的“决策树模型”。
专家系统中经常使用决策树,而且决策树给出的结果往往可以匹敌在当前领域具有几十年工作经验的人类专家。
优点:计算复杂度不高,输出结果易于理解,对中间值的缺失不敏感,可以处理不相关特征数据。
缺点:可能会产生过渡匹配问题。
适用数据类型:数值型和标称型。
入门案例
“20Q”游戏的规则很简单:一个人在心里想一个事物(但不说出来),另一个人用不断提问的方式才出答案,如果问题设计得当,一般在20个回合内就能猜出答案(开玩笑,2的20次方已经足够大了,可以试试在线游戏http://www.20q.net/)。其示例过程如下图所示:
上图就是一个“决策树模型”,“20Q”游戏的决策的过程就是用“特征”不断的对数据进行划分。其实决策过程不复杂,关键点是怎样定义合适的“决策问题”,即怎样从“样本数据集”中学习得到“决策树模型”。
工作原理
存在一个样本数据集合,也称作“训练样本集”,利用算法从“训练样本集”中找出“决定性的特征”,作为划分数据子集的依据。这个过程是递归的,直至数据子集中的数据都具有相同特征,即完成了“决策树”的构造。然后再复用“决策树模型”对新数据进行分类(贴标签 )。
划分数据集的大原则是:将无序的数据变得有序。可以使用信息论度量信息,如用“香农熵”(entropy)(这个名字来源于信息论之父:克劳德.香农)计算信息增益(information gain),从而获得最好的分类选择。
虽然“k-近邻算法”和“决策树算法”都属于“分类算法”,但“k-近邻算法”具有如下缺点:
1.必须有贴合真实情况的“训练样本集”,否则偏差会较大;
2.理论上“训练样本集”越大 ,计算结果越精确,但会占用大量的内存;
3.必须与“训练样本集”中的每个数据进行距离计算,可能非常耗时。
而“决策树算法”是首先根据“训练样本集”学习得到“决策树模型”,这个过程可能比较耗时。但是,“决策树模型”的构建是一次性的,可以把模型持久化(如存储在硬盘上),并在需要对事物进行分类时,再调出模型进行计算,这时对内存、CPU的消耗都比“k-近邻算法”更小。
一般流程
1.收集数据:可以使用任何方法;
2.准备数据:树构造算法只适用于标称型数据,因此数值型数据必须离散化;
3.分析数据:可以使用任何方法,树构造完成之后,我们应该检查是否符合预期;
4.训练算法:构造树的数据结构;
5.测试算法:使用经验树计算错误率;
6.使用算法:此步骤可以适用于任何监督学习算法,而使用决策树可以更好地理解数据的内在含义。
可使用场景
1.分析客户是否具有偿还债务的能力,指导借贷业务;
2.根据诊断报告,推荐治疗方案;
......