机器学习算法 --- 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时所用的指标(表达式)不同而已。

  

目录
相关文章
|
21天前
|
机器学习/深度学习 人工智能 自然语言处理
【MM2024】阿里云 PAI 团队图像编辑算法论文入选 MM2024
阿里云人工智能平台 PAI 团队发表的图像编辑算法论文在 MM2024 上正式亮相发表。ACM MM(ACM国际多媒体会议)是国际多媒体领域的顶级会议,旨在为研究人员、工程师和行业专家提供一个交流平台,以展示在多媒体领域的最新研究成果、技术进展和应用案例。其主题涵盖了图像处理、视频分析、音频处理、社交媒体和多媒体系统等广泛领域。此次入选标志着阿里云人工智能平台 PAI 在图像编辑算法方面的研究获得了学术界的充分认可。
【MM2024】阿里云 PAI 团队图像编辑算法论文入选 MM2024
|
8天前
|
机器学习/深度学习 算法 Java
机器学习、基础算法、python常见面试题必知必答系列大全:(面试问题持续更新)
机器学习、基础算法、python常见面试题必知必答系列大全:(面试问题持续更新)
|
17天前
|
机器学习/深度学习 人工智能 算法
【玉米病害识别】Python+卷积神经网络算法+人工智能+深度学习+计算机课设项目+TensorFlow+模型训练
玉米病害识别系统,本系统使用Python作为主要开发语言,通过收集了8种常见的玉米叶部病害图片数据集('矮花叶病', '健康', '灰斑病一般', '灰斑病严重', '锈病一般', '锈病严重', '叶斑病一般', '叶斑病严重'),然后基于TensorFlow搭建卷积神经网络算法模型,通过对数据集进行多轮迭代训练,最后得到一个识别精度较高的模型文件。再使用Django搭建Web网页操作平台,实现用户上传一张玉米病害图片识别其名称。
38 0
【玉米病害识别】Python+卷积神经网络算法+人工智能+深度学习+计算机课设项目+TensorFlow+模型训练
|
25天前
|
机器学习/深度学习 算法 决策智能
【机器学习】揭秘深度学习优化算法:加速训练与提升性能
【机器学习】揭秘深度学习优化算法:加速训练与提升性能
|
21天前
|
机器学习/深度学习 算法 Python
探索机器学习中的决策树算法:从理论到实践
【10月更文挑战第5天】本文旨在通过浅显易懂的语言,带领读者了解并实现一个基础的决策树模型。我们将从决策树的基本概念出发,逐步深入其构建过程,包括特征选择、树的生成与剪枝等关键技术点,并以一个简单的例子演示如何用Python代码实现一个决策树分类器。文章不仅注重理论阐述,更侧重于实际操作,以期帮助初学者快速入门并在真实数据上应用这一算法。
|
26天前
|
机器学习/深度学习 算法 大数据
机器学习入门:梯度下降算法(下)
机器学习入门:梯度下降算法(下)
|
18天前
|
机器学习/深度学习 算法 数据处理
EM算法对人脸数据降维(机器学习作业06)
本文介绍了使用EM算法对人脸数据进行降维的机器学习作业。首先通过加载ORL人脸数据库,然后分别应用SVD_PCA、MLE_PCA及EM_PCA三种方法实现数据降维,并输出降维后的数据形状。此作业展示了不同PCA变种在人脸数据处理中的应用效果。
22 0
|
7天前
|
算法 安全 数据安全/隐私保护
基于game-based算法的动态频谱访问matlab仿真
本算法展示了在认知无线电网络中,通过游戏理论优化动态频谱访问,提高频谱利用率和物理层安全性。程序运行效果包括负载因子、传输功率、信噪比对用户效用和保密率的影响分析。软件版本:Matlab 2022a。完整代码包含详细中文注释和操作视频。
|
26天前
|
机器学习/深度学习 算法 数据安全/隐私保护
基于MSER和HOG特征提取的SVM交通标志检测和识别算法matlab仿真
### 算法简介 1. **算法运行效果图预览**:展示算法效果,完整程序运行后无水印。 2. **算法运行软件版本**:Matlab 2017b。 3. **部分核心程序**:完整版代码包含中文注释及操作步骤视频。 4. **算法理论概述**: - **MSER**:用于检测显著区域,提取图像中稳定区域,适用于光照变化下的交通标志检测。 - **HOG特征提取**:通过计算图像小区域的梯度直方图捕捉局部纹理信息,用于物体检测。 - **SVM**:寻找最大化间隔的超平面以分类样本。 整个算法流程图见下图。
|
5天前
|
人工智能 算法 数据安全/隐私保护
基于遗传优化的SVD水印嵌入提取算法matlab仿真
该算法基于遗传优化的SVD水印嵌入与提取技术,通过遗传算法优化水印嵌入参数,提高水印的鲁棒性和隐蔽性。在MATLAB2022a环境下测试,展示了优化前后的性能对比及不同干扰下的水印提取效果。核心程序实现了SVD分解、遗传算法流程及其参数优化,有效提升了水印技术的应用价值。