ID3决策树与C4.5决策树分类算法简述

Let’s begin with ID3 decision tree:
The ID3 algorithm tries to get the most information gain when grow the decision trees. The information gain is defined as

Gain(A)=I(s1,s2,…,sm)−E(A)

where I is the information entropy of a given sample setting,

I(s1,s2,…,sm)=−∑i=1mpilog2(pi)

E(A) is the information entropy of the subset classified by attribute A=(a1,a2,…,av),

E(A)=∑j=1vsij+s2j+⋯+smjsI(s1,s2,…,sm)

Moreover, pi is the probability of an sample belonging to class Ci, which can be estimated as pi=si|S| and pij is the probability an sample belonging to class Ci with attribute A=aj, i.e. pij+sij|Sj|.
ID3 algorithm can be simplified as follows:

  1. For every attribute A, we calculate its information gain E(A).
  2. Pick up the attribute who is of the largest E(A) as the root node or internal node.
  3. Get rid of the grown attribute A, and for every value aj of attribute A, calculate the next node to be grown.
  4. Keep steps 1~3 until each subset has only one label/class Ci.

ID3 algorithm is an old machine learning algorithm created in 1979 based on information entropy, however, there are several problems of it:

  1. ID3 prefers the attribute with more values, though it turns out not to be the optimal one.
  2. ID3 has to calculate the information entropy of every value of every attribute. Hence it always leads to many levels and branches with very little probability, as a result of which it tends to overfit classification in the test set.

C4.5 decision tree
C4,.5 algorithm makes use of Grain Ratio instead of Gain to select attributes.

GainRatio(S,A)=Gain(S,A)SplitInfo(S,A)

where Gain(S,A) is nothing more than Gain(A) in ID3, and SplitInfo(S,A) is defined as

SplitInfo(S,A)=−∑i=1c|si||S|log2(|S||si|)

in which si to sc are the sample sets divided by c values of attribute A.

时间: 2024-11-01 19:38:42

ID3决策树与C4.5决策树分类算法简述的相关文章

Logistic回归与最小二乘概率分类算法简述与示例

Logistic Regression & Least Square Probability Classification 1. Logistic Regression Likelihood function, as interpreted by wikipedia: https://en.wikipedia.org/wiki/Likelihood_function plays one of the key roles in statistic inference, especially met

数据挖掘中分类算法小结

数据仓库,数据库或者其它信息库中隐藏着许多可以为商业.科研等活动的决策提供所需要的知识.分类与预测是两种数据分析形式,它们可以用来抽取能够描述重要数据集合或预测未来数据趋势的模型.分类方法(Classification)用于预测数据对象的离散类别(Categorical Label);预测方法(Prediction )用于预测数据对象的连续取值. 分类技术在很多领域都有应用,例如可以通过客户分类构造一个分类模型来对银行贷款进行风险评估;当前的市场营销中很重要的一个特点是强调客户细分.客户类别分析

分类算法总结

决策树分类算法 决策树归纳是经典的分类算法. 它采用自顶向下递归的各个击破方式构造决策树. 树的每一个结点上使用信息增益度量选择测试属性. 可以从生成的决策树中提取规则. KNN法(K-Nearest Neighbor): KNN法即K最近邻法,最初由Cover和Hart于1968年提出的,是一个理论上比较成熟的方法. 该方法的思路非常简单直观:如果一个样本在特征空间中的k个最相似(即特征空间中最邻近)的样本中的大多数属于某一个类别,则该样本也属于这个类别. 该方法在定类决策上只依据最邻近的一个

分类算法:决策树(C4.5)

C4.5是机器学习算法中的另一个分类决策树算法,它是基于ID3算法进行改进后的一种重要算法,相比于ID3算法,改进有如下几个要点: 用信息增益率来选择属性.ID3选择属性用的是子树的信息增益,这里可以用很多方法来定义信息,ID3使用的是熵(entropy, 熵是一种不纯度度量准则),也就是熵的变化值,而C4.5用的是信息增益率. 在决策树构造过程中进行剪枝,因为某些具有很少元素的结点可能会使构造的决策树过适应(Overfitting),如果不考虑这些结点可能会更好. 对非离散数据也能处理. 能够

分类算法:决策树(ID3)

决策树是以实例为基础的归纳学习算法. 它从一组无次序.无规则的元组中推理出决策树表示形式的分类规则.它采用自顶向下的递归方式,在决策树的内部结点进行属性值的比较,并根据不同的属性值从该结点向下分支,叶结点是要学习划分的类.从根到叶结点的一条路径就对应着一条合取规则,整个决策树就对应着一组析取表达式规则. 一棵决策树由以下3类结点构成: 根结点 内部结点(决策结点) 叶结点 其中,根结点和内部结点都对应着我们要进行分类的属性集中的一个属性,而叶结点是分类中的类标签的集合.如果一棵决策树构建起来,其

分类算法之决策树(Decision tree)

3.1.摘要       在前面两篇文章中,分别介绍和讨论了朴素贝叶斯分类与贝叶斯网络两种分类算法.这两种算法都以贝叶斯定理为基础,可以对分类及决策问题进行概率推断.在这一篇文章中,将讨论另一种被广泛使用的分类算法--决策树(decision tree).相比贝叶斯算法,决策树的优势在于构造过程不需要任何领域知识或参数设置,因此在实际应用中,对于探测式的知识发现,决策树更加适用. 3.2.决策树引导       通俗来说,决策树分类的思想类似于找对象.现想象一个女孩的母亲要给这个女孩介绍男朋友,

机器学习(二)--- 分类算法详解

感觉狼厂有些把机器学习和数据挖掘神话了,机器学习.数据挖掘的能力其实是有边界的.机器学习.数据挖掘永远是给大公司的业务锦上添花的东西,它可以帮助公司赚更多的钱,却不能帮助公司在与其他公司的竞争中取得领先优势,所以小公司招聘数据挖掘/机器学习不是为了装逼就是在自寻死路.可是相比Java和C++语言开发来说,机器学习/数据挖掘确实是新一些老人占的坑少一些,而且可以经常接触一些新的东西.还是赶紧再次抓住机会集中的再总结一下吧,不能再拖拖拉拉了.  其实数据挖掘的主要任务是分类.聚类.关联分析.预测.时

如何实现基于C4.5的Adaboost算法

问题描述 如何实现基于C4.5的Adaboost算法 现有的Adaboost算法只能对二类分类,而基于决策树的集成如何更新权重 解决方案 参考:http://www.docin.com/p-595686917.html

数据挖掘系列(7)分类算法评价

一.引言 分类算法有很多,不同分分类算法又用很多不同的变种.不同的分类算法有不同的特定,在不同的 数据集上表现的效果也不同,我们需要根据特定的任务进行算法的选择,如何选择分类,如何评价一 个分类算法的好坏,前面关于决策树的介绍,我们主要用的正确率(accuracy)来评价分类算法. 正确率确实是一个很好很直观的评价指标,但是有时候正确率高并不能代表一个算法就好.比如某 个地区某天地震的预测,假设我们有一堆的特征作为地震分类的属性,类别只有两个:0:不发生地震 .1:发生地震.一个不加思考的分类器