写程序学ML:决策树算法原理及实现(一)

来源:转载




[题外话]近期申请了一个微信公众号:平凡程式人生。有兴趣的朋友可以关注,那里将会涉及更多机器学习、OpenCL+OpenCV以及图像处理方面的文章。


1、决策树算法的原理

决策树的工作原理是根据用户输入的一系列数据,给出最后的分类答案。


我们经常使用决策树处理分类问题,近来的调查表明决策树也是最经常使用的数据挖掘算法。K近邻算法的最大缺点是无法给出数据的内在含义,决策树的主要优势就在于数据形式非常容易理解。


决策树很多任务都是为了数据中所蕴含的知识信息,因此决策树可以使用不熟悉的数据集合,并从中提取出一系列规则,机器学习算法最终将使用这些机器从数据集中创造的规则。


决策树的优点和缺点:


优点:计算复杂度不高,输出结果易于理解,对中间值的缺失不敏感,可以处理不相关特征数据。


缺点:可能会产生过度匹配问题。


适用数据类型:数值型和标称型。


决策树的一般流程:


1> 收集数据:可以使用任何方法;


2> 准备数据:树构造算法只适用于标称型数据,因此数值型数据必须离散化;


3> 分析数据:可以使用任何方法,构造树完成之后,我们应该检查图形是否符合预期;


4> 训练算法:构造树的数据结构;


5> 测试算法:使用经验树计算错误率;


6> 使用算法:此步骤可以适用于任何监督学习算法,而使用决策树可以更好地理解数据的内在含义;



划分数据集的大原则是:将无序的数据变得更加有序。


组织杂乱无章数据的一种方法就是使用信息论度量信息,信息论是量化处理信息的分支科学。


在划分数据集之前之后信息发生的变化成为信息增益。计算每个特征值划分数据集获得的信息增益,获得信息增益最高的特征就是最好的选择。


集合信息的度量方式称为香农熵或者简称为熵,这个名字来源于信息论之父克劳德.香农。



如果待分类的事物可能划分在多个分类中,则符号xi的信息定义为:


L(xi) = -log2P(xi)


其中p(xi)是选择该分类的概率。


即:符号xi的信息是它的分类概率取以2为底的对数,然后再变为负数。p(xi)为分类概率,该值大于等于0,小于等于1。所以p(xi)等于1时,L(xi)为0,其他时候,L(xi)都为负数。也就是说符号xi的分类概率越小,它的信息量就越小,它属于该类的可能性就越小;分类概率越大,信息量就越大,它属于该类的可能性就越大。



熵定义为信息的期望值。为了计算熵,我们需要计算所有类别所有可能值包含的信息期望值:



在概率论和统计学中,数学期望(mean)(或均值,亦简称期望)是试验中每次可能结果的概率乘以其结果的总和,是最基本的数学特征之一。它反映随机变量平均取值的大小。


离散型随机变量的一切可能的取值xi 与对应的概率 p(xi) 乘积之和称为该离散型随机变量的数学期望(若该求和绝对收敛),记为E(x)。它是简单算术平均的一种推广,类似加权平均。


离散型随机变量X的取值为X1,X2,X3,….Xn,p(X1),p(X2),p(X3),…,p(Xn)为X对应取值的概率,可理解为数据X1,X2,X3,…,X4出现的频率f(Xi) ,则:




那对于信息熵:




递归构建决策树的工作原理:得到原始数据集,然后基于最好的属性值划分数据集,由于特征值可能多于两个,因此可能存在大于两个分支的数据集划分。第一次划分之后,数据将被向下传递到树分支的下一个节点,在这个节点上,我们可以再次划分数据。因此我们可以采用递归的原则处理数据集。


递归结束的条件是:程序遍历完所有划分数据集的属性,或者每个分支下的所有实例都具有相同的分类。如果所有实例具有相同的分类,则得到一个叶子节点或者终止块。任何到达叶子结点的数据必须属于叶子节点的分类。



决策树的主要优点就是直观易于理解。


MatPlot提供了一个注解工具annotations,可以在数据图形上添加文本注释。工具内嵌支持带箭头的划线工具,使得我们可以在其他恰当的地方指向数据位置,并在此处添加描述信息,解释数据内容。

(未完待续)




分享给朋友:
您可能感兴趣的文章:
随机阅读: