机器学习算法 --- Decision Trees Algorithms

简介: 一、Decision Trees Agorithms的简介   决策树算法(Decision Trees Agorithms),是如今最流行的机器学习算法之一,它即能做分类又做回归(不像之前介绍的其他学习算法),在本文中,将介绍如何用它来对数据做分类。

一、Decision Trees Agorithms的简介

   决策树算法(Decision Trees Agorithms),是如今最流行的机器学习算法之一,它即能做分类又做回归(不像之前介绍的其他学习算法),在本文中,将介绍如何用它来对数据做分类。

  本文参照了Madhu Sanjeevi ( Mady )的Decision Trees Algorithms,有能力的读者可去阅读原文。

  说明:本文有几处直接引用了原文,并不是不想做翻译,而是感觉翻译过来总感觉不够清晰,而原文却讲的很明白清晰。(个人观点:任何语言的翻译都会损失一定量的信息,所以尽量支持原版)

二、Why Decision trees?

   在已经有了很多种学习算法的情况下,为什么还要创造出回归树这种学习算法呢?它相比于其他算法有和优点?

    至于为什么,原因有很多,这里主要讲两点,这两点也是在我看来相比于其他算法最大的优点。

    其一,决策树的算法思想与人类做决定时的思考方式很相似,它相比于其他算法,无需计算很多很多的各种参数,它能像人类一样综合各种考虑,做出很好的选择(不一定是最好啊ㄟ(▔,▔)ㄏ)。

    其二,它能将它做出决策的逻辑过程可视化(不同于SVM, NN, 或是神经网络等,对于用户而言是一个黑盒), 例如下图,就是一个银行是否给客户发放贷款使用决策树决策的一个过程。

 

 

三、What is the decision tree??

  A decision tree is a tree where each node represents a feature(attribute), each link(branch) represents a decision(rule) and each leaf represents an outcome(categorical or continues value).

  类似于下图中左边的数据,对于数据的分类我们使用右边的方式对其分类:

  step 1:判断Age,Age<27.5,则Class=High;否则,执行step 2。

  step 2: 判断CarType,CarType∈Sports,则Class=High;否则Class=Low。

  对于一组数据,只需按照决策树的分支一步步的走下去,便可得到最终的结果,有点儿类似于程序设计中的多分支选择结构。

 

四、How to build this??

  学习新知识,最主要的三个问题就是why,what,how。前两个问题已经在上面的介绍中解决了,接下来就是how,即如何建立一颗决策树?

  

  建立决策树,有很多种算法,本文主要讲解一下两种:

  1. ID3 (Iterative Dichotomiser 3) → uses Entropy function and Information gain as metrics.
  2. CART (Classification and Regression Trees) → uses Gini Index(Classification) as metric.         

————————————————————————————————————————————————————————————————————————————————————————————————————— 首先,我们使用第一种算法来对一个经典的分类问题建立决策树:

  

  Let’s just take a famous dataset in the machine learning world which is whether dataset(playing game Y or N based on whether condition).

  We have four X values (outlook,temp,humidity and windy) being categorical and one y value (play Y or N) also being categorical.

  So we need to learn the mapping (what machine learning always does) between X and y.

  This is a binary classification problem, lets build the tree using the ID3 algorithm.

  首先,决策树,也是一棵树,在计算机科学中,树是一种数据结构,它有根节点(root node),分枝(branch),和叶子节点(leaf node)。

  而对于一颗决策树,each node represents a feature(attribute),so first, we need to choose the root node from (outlook, temp, humidity, windy). 那么改如何选择呢?

  Answer: Determine the attribute that best classifies the training data; use this attribute at the root of the tree. Repeat this process at for each branch. 

  这也就意味着,我们要对决策树的空间进行自顶向下的贪婪搜索。

  所以问题又来了,how do we choose the best attribute? 

  Answer: use the attribute with the highest information gain in ID3.

  

  In order to define information gain precisely, we begin by defining a measure commonly used in information theory, called entropy(熵) that characterizes the impurity of an arbitrary collection of examples.”

  So what's the entropy? (下图是wikipedia给出的定义)

  从上面的公式中我们可以得到,对于一个二分类问题,如果entropy=0,则要么全为正样本,要么全为负样本(即理论上样本应该属于两个,实际上所有的样本全属于一类)。如果entropy=1,则正负样本各占一半。

  有了Entropy的概念,便可以定义Information gain:

  有了上述两个概念,便可建立决策树了,步骤如下:          

1.compute the entropy for data-set
2.for every attribute/feature:
       1.calculate entropy for all categorical values
       2.take average information entropy for the current attribute
       3.calculate gain for the current attribute
3. pick the highest gain attribute.
4. Repeat until we get the tree we desired.

 

  对于这个实例,我们来具体使用一下它:

    step1(计算数据集整体的entropy):

    step2(计算每一项feature的entropy and information gain):

      这里只计算了两项,其他两项的计算方法类似。

    step3 (选择Info gain最高的属性):

      

      上表列出了每一项feature的entropy and information gain,我们可以发现Outlook便是我们要找的那个attribute。

    So our root node is Outlook:

  

   接着对于图中左边的未知节点,我们将由sunny得来的数据当做数据集,然后从这些数据中按照上述的步骤选择其他三个属性的一种作为此节点,对于右边的节点做类似操作即可:

  最终,建立的决策树如下:

  

—————————————————————————————————————————————————————————————————————————————————————————————————————  接着,我们使用第二种算法来建立决策树(Classification with using the CART algorithm):

    CART算法其实与ID3非常相像,只是每次选择时的指标不同,在ID3中我们使用entropy来计算Informaition gain,而在CART中,我们使用Gini index来计算Gini gain。

    同样的,对于一个二分类问题而言(Yes or No),有四种组合:1 0 , 0 1 , 1 0 , 0 0,则存在

P(Target=1).P(Target=1) + P(Target=1).P(Target=0) + P(Target=0).P(Target=1) + P(Target=0).P(Target=0) = 1

P(Target=1).P(Target=0) + P(Target=0).P(Target=1) = 1 — P^2(Target=0) — P^2(Target=1)

    那么,对于二分类问题的Gini index定义如下:

  A Gini score gives an idea of how good a split is by how mixed the classes are in the two groups created by the split. A perfect separation results in a Gini score of 0, whereas the worst case split that results in 50/50 classes.

   所以,对于一个二分类问题,最大的Gini index:

  = 1 — (1/2)^2 — (1/2)^2
  = 1–2*(1/2)^2
  = 1- 2*(1/4)
  = 1–0.5
  = 0.5

  和二分类类似,我们可以定义出多分类时Gini index的计算公式:

  

  Maximum value of Gini Index could be when all target values are equally distributed.

  同样的,当取最大的Gini index时,可以写为(一共有k类且每一类数量相等时): = 1–1/k

  当所有样本属于同一类别时,Gini index为0。

  此时我们就可以根据Gini gani来选择所需的node,Gini gani的计算公式(类似于information gain的计算)如下:

  那么便可以使用类似于ID3的算法的思想建立decision tree,步骤如下:

1.compute the gini index for data-set
2.for every attribute/feature:
       1.calculate gini index for all categorical values
       2.take average information entropy(这里指GiniGain(A,S)的右半部分,跟ID3中的不同) for the current attribute 
3.calculate the gini gain
3. pick the best gini gain attribute.
4. Repeat until we get the tree we desired.

 

  最终,形成的decision tree如下:

  其实这两种算法本质没有任何区别,只是选择node时所用的指标(表达式)不同而已。

  

目录
相关文章
|
9天前
|
机器学习/深度学习 人工智能 算法
【手写数字识别】Python+深度学习+机器学习+人工智能+TensorFlow+算法模型
手写数字识别系统,使用Python作为主要开发语言,基于深度学习TensorFlow框架,搭建卷积神经网络算法。并通过对数据集进行训练,最后得到一个识别精度较高的模型。并基于Flask框架,开发网页端操作平台,实现用户上传一张图片识别其名称。
30 0
【手写数字识别】Python+深度学习+机器学习+人工智能+TensorFlow+算法模型
|
30天前
|
机器学习/深度学习 算法 Java
机器学习、基础算法、python常见面试题必知必答系列大全:(面试问题持续更新)
机器学习、基础算法、python常见面试题必知必答系列大全:(面试问题持续更新)
|
1月前
|
机器学习/深度学习 人工智能 算法
【玉米病害识别】Python+卷积神经网络算法+人工智能+深度学习+计算机课设项目+TensorFlow+模型训练
玉米病害识别系统,本系统使用Python作为主要开发语言,通过收集了8种常见的玉米叶部病害图片数据集('矮花叶病', '健康', '灰斑病一般', '灰斑病严重', '锈病一般', '锈病严重', '叶斑病一般', '叶斑病严重'),然后基于TensorFlow搭建卷积神经网络算法模型,通过对数据集进行多轮迭代训练,最后得到一个识别精度较高的模型文件。再使用Django搭建Web网页操作平台,实现用户上传一张玉米病害图片识别其名称。
56 0
【玉米病害识别】Python+卷积神经网络算法+人工智能+深度学习+计算机课设项目+TensorFlow+模型训练
|
1月前
|
机器学习/深度学习 算法 Python
探索机器学习中的决策树算法:从理论到实践
【10月更文挑战第5天】本文旨在通过浅显易懂的语言,带领读者了解并实现一个基础的决策树模型。我们将从决策树的基本概念出发,逐步深入其构建过程,包括特征选择、树的生成与剪枝等关键技术点,并以一个简单的例子演示如何用Python代码实现一个决策树分类器。文章不仅注重理论阐述,更侧重于实际操作,以期帮助初学者快速入门并在真实数据上应用这一算法。
|
18天前
|
机器学习/深度学习 人工智能 算法
探索机器学习中的决策树算法
【10月更文挑战第29天】本文将深入浅出地介绍决策树算法,一种在机器学习中广泛使用的分类和回归方法。我们将从基础概念出发,逐步深入到算法的实际应用,最后通过一个代码示例来直观展示如何利用决策树解决实际问题。无论你是机器学习的初学者还是希望深化理解的开发者,这篇文章都将为你提供有价值的见解和指导。
|
1月前
|
机器学习/深度学习 算法 数据处理
EM算法对人脸数据降维(机器学习作业06)
本文介绍了使用EM算法对人脸数据进行降维的机器学习作业。首先通过加载ORL人脸数据库,然后分别应用SVD_PCA、MLE_PCA及EM_PCA三种方法实现数据降维,并输出降维后的数据形状。此作业展示了不同PCA变种在人脸数据处理中的应用效果。
34 0
|
29天前
|
算法 安全 数据安全/隐私保护
基于game-based算法的动态频谱访问matlab仿真
本算法展示了在认知无线电网络中,通过游戏理论优化动态频谱访问,提高频谱利用率和物理层安全性。程序运行效果包括负载因子、传输功率、信噪比对用户效用和保密率的影响分析。软件版本:Matlab 2022a。完整代码包含详细中文注释和操作视频。
|
6天前
|
算法 数据安全/隐私保护 索引
OFDM系统PAPR算法的MATLAB仿真,对比SLM,PTS以及CAF,对比不同傅里叶变换长度
本项目展示了在MATLAB 2022a环境下,通过选择映射(SLM)与相位截断星座图(PTS)技术有效降低OFDM系统中PAPR的算法实现。包括无水印的算法运行效果预览、核心程序及详尽的中文注释,附带操作步骤视频,适合研究与教学使用。
|
14天前
|
算法 数据挖掘 数据安全/隐私保护
基于FCM模糊聚类算法的图像分割matlab仿真
本项目展示了基于模糊C均值(FCM)算法的图像分割技术。算法运行效果良好,无水印。使用MATLAB 2022a开发,提供完整代码及中文注释,附带操作步骤视频。FCM算法通过隶属度矩阵和聚类中心矩阵实现图像分割,适用于灰度和彩色图像,广泛应用于医学影像、遥感图像等领域。
|
15天前
|
算法 调度
基于遗传模拟退火混合优化算法的车间作业最优调度matlab仿真,输出甘特图
车间作业调度问题(JSSP)通过遗传算法(GA)和模拟退火算法(SA)优化多个作业在并行工作中心上的加工顺序和时间,以最小化总完成时间和机器闲置时间。MATLAB2022a版本运行测试,展示了有效性和可行性。核心程序采用作业列表表示法,结合遗传操作和模拟退火过程,提高算法性能。

热门文章

最新文章

下一篇
无影云桌面