`
frankdou
  • 浏览: 2615 次
  • 来自: ...
最近访客 更多访客>>
文章分类
社区版块
存档分类
最新评论

分类算法学习总结-决策树

阅读更多

table { font-size: 10pt;}

分类算法学习总结 - 决策树     

     因为最近在工作上的需要,对基于机器学习的分类算法比较感兴趣

     对事物进行分类是比较常见的一种应用,包括对邮件,文本进行分类,对会员,行为,安全性等方面做处分类。 目前了解的情况:贝叶斯,决策树,神经网络, SVM 是比较流行的几种分类算法, 比如文本分类中经常用到 贝叶斯算法。

这篇文章主要介绍一下决策树

下面是一个很多书上经常给出的,根据各种天气情况,判断是否适合运动的决策树



 

相对于其他分类算法,决策树的优点是:

1 、决策过程易于理解

2 、可以转换成逻辑表达式的形式。

3 、可接受非数值型输入 ( 相对神经网络来说,不需要做预处理方面工作 )

决策树主要的适用场景是:

1 、各个决策的属性可以用 key=value 形式来表示

2 、结论并不特别多,可以用离散的值来表示

不太适用的场合:

大量数值型输入和输出的情况,树会比较庞大,准确性下降。

 

决策树的使用方法:

1 、根据训练数据,生成决策树

2 、使用生成好的决策树,接受新信息进行决策。

 

下面是《 Collective Intelligence 》上的一个例子,

网站提供了 None, Basic, Premium 三种会员级别,是根据一个网站根据访问用户的一些行为,预测哪些用户可能成为哪种类型的会员,下表列出了网站上的一些历史统计数据:

其中最后一列 Service chosen 是结果,表示会员选择了哪种服务。

一、决策树建立过程

建立决策树常见算法有 CART, C4.5

过程是一个自顶向下的递归过程,每一步都需要选择一个 合适的属性 - 值对 ,把整个集合拆分成左右两个子树。

假设我们随便选一个属性:所在地 =USA ,集合被拆成以下两个:

集合:所在地 =USA



集合:所在地 <>USA

 



这时我们会发现,按照会员所在地 =USA 来判断是不合适的,因为两个列表中,都包括了各种类型的会员。

我们换一个属性,用来源 =Google 来拆分,结果如下:

集合:来源 =google

 



集合:来源 <>google



 

这次的结果比通过地区 =USA 来拆分好多了,已经可以看出一些规律,历史的付费会员都是从 Google 引入的,假设网站要做一些推广的话,可能在 Google 上花点钱更值,呵呵。

那么问题就是,这么多的属性,怎么才能选出合适的呢?

      从上面例子可以看出,有一种选择属性的标准,就是每次进行拆分后,被拆分出的两个集合应该倾向于更有序,即出现的可能结果 ( 上例:加入的服务 ) 越少越好。

在信息学上,可以用 来表示一个集合的混乱程度,熵的定义如下:



 

 

     

其中, p(x) 是表示某一种可能的结果在集合中出现的概率 ,b 通常取 2 为底的对数,熵越高,集合越混乱,熵越低,集合越有序,当熵 =0 时,集合中只有一种结果,是最理想的状况。

例如 , 来源 =google 的集合中 ,Premium 出现概率是 3/5,Basic None 出现概率都是 1/5

H X = -(0.6*log2(0.6) + 0.2*log2(0.2) + 0.2*log2(0.2)) = 1.37

同样计算得出其他集合的值:

按照所在地 =USA 拆分:

集合 ( 所在地 =USA) 的熵是: 1.5

集合 ( 所在地 <>USA) 的熵是: 1.48

按照来源 =Google 拆分:

集合 ( 来源 =Google) 的熵是: 1.37

集合 ( 来源 <>Google) 的熵是: 1.0

从熵上可以看出,按照来源 =google 拆分出的两个集合熵更低,所以比按照所在地 =USA 拆分更理想。

所以,在递归创建每一层子树时,可以这样来做:

1 )计算当前集合 X 的熵

2 )尝试用每一个属性 = 值对,把当前集合拆分成 X1,X2 两个集合

3 )分别计算两个子集合的熵,并计算相对于当前集合 X X1 X2 熵的降低幅度。

4 )选出拆分后熵降低最多的属性 = 值对,以此来进行拆分。

 

其中 3 )中的拆分后熵降低程度,可以用信息增益来表示:

GAIN=H(X) – P(X1)H(X1) – P(X2)H(X2)

上面的例子中整个原始集合有 15 行数据,熵是 1.50, 按照来源 =google 拆分后:

X1 5 行数据,熵是 1.37

X2 10 行数据,熵是 1.0

GAIN = 1.50 – 5/15 * 1.37 – 10/15 * 1.0 = 0.5

同样,按照所在地 =USA 拆分,可以算出,信息增益基本接近 0 。所以按照来源 =google 拆分,对集合向有序的方向发展,贡献更大。

 

每一级都按照信息增益选择属性拆分,最终递归创建的决策树是:

 

 

二、使用创建好的决策树进行分类

使用创建好的决策树进行分类比较简单,只要从根节点开始,对这个决策树递归访问即可:

input 表示待分类的数据,例如

input = [ 来源 :google, 所在地 :USA...........]

node = tree 的根节点

classify(input,node){

   if 已经是叶子节点:

       返回 node.value

   key = node key

   value = input[key]

   if value == node.value:

      return classify(input, 右子树 )

   else

      return classify(input, 左子树 )

}

 

三、决策树的剪枝

根据训练数据建立起来的决策树,可能存在一个问题,就是过于精确,那么在真实情况下,可能并不能完全达到理想的效果,下面这个例子,看得会比较明显:



这是一个关于调整薪资方案的一个例子,右侧的树看似包含了所有情况,但实际上过分依赖了测试数据,过于精确,实用性并不大。因为在这家公司现实中看的话,加薪比例 <=2.5 ,基本上就不能说是一个好方案了。

决策树修剪是一个比较复杂的问题,一般都采用先用训练数据建好树,再后修剪的方式。

例如,创建好树后,可以自底向上,判断每一组有相同父节点的叶子节点,如果合并之后,熵的增加小于某个阀值,就合并成一个节点。例如上面 b ,假设合并到根节点 (wage increase first year) 的时候,不能再合并了,就把原来整个子树中最可能出现的结果 ( 图中看是 bad) ,挂到合并好的节点下面。

不过,关于修剪方面,我还没能了解很深,还望有经验的朋友指点。

分享到:
评论

相关推荐

    机器学习决策树分类算法实验报告-机器学习高分大作业

    决策树分类算法实验报告18页-作者原创机器学习大作业-目录内容: 1.研究意义2.数据描述3.模型描述4.算法实现5.运行结果及意义说明6.总结-包含算法流程图,运行结果截图

    机器学习实战 - 决策树PDF知识点总结 + 代码实现

    决策树(Decision Tree)是监督学习中的一种算法,并且是一种基本的分类与回归的方法 决策树(Decision Tree)是在已知各种情况发生概率的基础上,通过构成决策树来求取净现值的期望值大于等于零的概率,评价项目风险,...

    决策树算法原理详解

    决策树算法效果评估 决策树生成算法 ID3算法 ID3算法优缺点 C4.5算法 8 CART算法 8 ID3\C4.5\CART分类回归树算法总结 分类树和回归树的区别 决策树优化策略 决策树的剪枝 决策树剪枝过程 附录:

    大数据决策树算法数据挖掘分类算法之决策树

    Quinlan 给出ID3算法,并在1983年和1986年对ID3 进行了总结和简化,使其成为决策树学习算法的典型。 3、Schlimmer 和Fisher 于1986年对ID3进行改造,在每个可能的决策树节点创建缓冲区,使决策树可以递增式生成,...

    决策树算法及其核心技术

    概述了决策树分类算法, 指出了决策树算法的核心技术: 测试属性的选择和树枝修剪技术。通过对当前数据挖掘中具有代表性的优秀分类算法进行分析和比较, 总结出了各种算法的特性, 为使用者选择算法或研究者改进算法...

    机器学习决策树与分类方法课程报告

    机器学习决策树与分类方法课程报告,内部包含代码、算法思想、算法原理、算法分析、课程总结。机器学习决策树与分类方法课程报告,内部包含代码、算法思想、算法原理、算法分析、课程总结。机器学习决策树与分类方法...

    机器学习算法笔记

    本文总结博客中关于机器学习十大算法的详细过程,进行汇总,包括广义线性模型、softmax 回归 、逻辑回归、梯度下降法、Logistic 回归与牛顿迭代法、两种梯度下降法、相对熵(KL 散度)、K-Means 聚类算法 、朴素...

    机器学习报告-基于PCA和KNN算法的毒蘑菇分类预测实验报告-机器学习高分大作业

    机器学习报告-机器学习大作业16页-基于PCA和KNN算法的毒蘑菇分类预测-1.研究意义2.数据描述3.模型描述4.算法实现5.运行结果及意义说明6.总结(原创资源,作者的机器学习课程报告)

    机器学习分类算法实验报告.docx

    对于KNN,SVM,adaboost以及决策树等分类算法对数据集运行结果进行总结,代码点我博文

    论文研究-用决策树指导TBL进行多音字消歧.pdf

    构建了一个平均每个多音字(词)5 000句的语料库,并且提出了一种结合决策树和基于转换的错误驱动的学习(Transformation- Based error-driven Learning,TBL)的混合算法。该方法根据决策树的指导,自动生成TBL算法...

    基于python实现的机器学习预测系统汇总+GUI界面(贝叶斯网络、马尔科夫模型、线性回归、岭回归多项式回归、决策树等).zip

    (1)分类算法: k-近邻算法、贝叶斯分类器、支持向量机、决策树分类、神经网络、AdaBoost、GBDT、随机森林、逻辑回归、softmax回归等 (2)预测:贝叶斯网络、马尔科夫模型、条件随机场、线性回归、XGBoost、岭...

    决策树与朴素贝叶斯算法原理

    在学习《数据科学导引》第四章分类算法——决策树及朴素贝叶斯时可以参考本课件,基本原理通俗易懂,并举了相关例子,在决策树剪枝部分对课本内容做了补充,有兴趣可以翻阅。 汇报前查阅了很多相关资料,进行了整合...

    清华出品 机器学习技术课程 统计学习方法第二版系列课程 第5章 决策树 共98页.pptx

    第5章 决策树 共98页.pptx 第6章 Logistic回归 共75页.pptx 第7章 SVM及核函数 共159页.pptx 第8章 adaboost 共75页.pptx 第9章 EM算法 共48页.pptx 第10章 隐马尔科夫模型 共64页.pptx 第11章 条件随机场 共63页....

    《KNN&决策树》实验

    2、决策树-隐形眼镜分类 认真分析、理解绘制决策树的6个函数,复现使用决策树预测隐形眼镜类型的程序 a)仅需对你认为最重要、难以理解的代码块进行展示,但要求进行语句注解; b)请把最后构造出的决策树贴在实验报告...

    人工智能机器学习常用算法总结及各个常用算法精确率对比

    主要介绍了人工智能机器学习常用算法总结及各个常用算法精确率对比,需要的朋友可以参考下

    分类算法具体算法的优缺点

    目前看到的比较全面的分类算法,总结的还不错. 2.4.1 主要分类方法介绍解决分类问题的方法很多[40-42] ,单一的分类方法主要包括:决策树、贝叶斯、人工神经网络、K-近邻、支持向量机和基于关联规则的分类等;

    机器学习数据挖掘作业.rar

    对于决策树分类算法,前期的数据预处理很重要,如果标签类太多,条件太多,决策树可能会变得很庞大,加入旧的数据效果可能不错,但当加入一个全新的数据,决策树分类效果可能会下降。 对于神经网络分类算法,其能够...

    常用数据挖掘算法总结及Python实现

    第四章 KNN(k 最邻近分类算法) 16 第五章 决策树19 第六章 朴素贝叶斯分类29 第七章 Logistic 回归 .32 第八章 SVM 支持向量机42 第九章 集成学习(Esemble Learning)43 第十一章 模型评估46 第四部分 非监督学习--...

Global site tag (gtag.js) - Google Analytics