添加链接 注册    登录
link之家
链接快照平台
  • 输入网页链接，自动生成快照
  • 标签化管理网页链接
相关文章推荐
不敢表白的钥匙扣  ·  Android ...·  9 月前    · 
斯文的杯子  ·  Laravel：whereIn子查询_51C ...·  9 月前    · 
打酱油的小蝌蚪  ·  Pandas从入门到精通（4）- ...·  1 年前    · 
傻傻的楼梯  ·  .NET Desktop Runtime ...·  1 年前    · 
link之家  ›  C4.5(weka又称为J48)算法原理详解_npupengsir的博客
https://blog.csdn.net/u012897374/article/details/74983742
爱运动的手电筒
1 年前

1. 信息增益率

ID3算法有以下几个缺点:

  • 1个属性取值越多,则此属性的信息增益率越大,越有可能被ID3选为当前分类属性。然而取值较多的属性并不一定最优。(例如一个属性的每个子节点都只有1个样本,此时信息增益率达到最大,但是用这样的属性却没有任何意义)

  • ID3只能处理离散型属性

  • 可以处理缺失数据

  • 可以对树进行剪枝

针对ID3算法的不足,Quinlan又提出了C4.5，C4.5算法采用信息增益率来取代信息增益作为当前最优决策属性的度量标准。

仍然选择weka中天气的数据集为例子:

outlook temperature humidity windy play
sunny hot high FALSE no
sunny hot high TRUE no
overcast hot high FALSE yes
rainy mild high FALSE yes
rainy cool normal FALSE yes
rainy cool normal TRUE no
overcast cool normal TRUE yes
sunny mild high FALSE no
sunny cool normal FALSE yes
rainy mild normal FALSE yes
sunny mild normal TRUE yes
overcast mild high TRUE yes
overcast hot normal FALSE yes
rainy mild high TRUE no

1.1 计算属性outlook的信息增益:

S p l i t I n f o o u t l o o k ( S ) = − 5 14 × l o g 2 5 14 − 4 14 × l o g 2 4 14 − 5 14 × l o g 2 5 14 = 1.577
同理计算其他属性的 S p l i t I n f o

2. C4.5处理连续型属性

对于连续型属性,C4.5先把它当转换成离散型属性再进行处理。本质上属性取值连续,但对于有限的采样数据它是离散的。例如某连续型属性有N个不同取值,则有N-1种离散化的方法: <= 的分到左子树, > 的分到右子树,然后计算N-1种情况下最大的信息增益率。

对于离散型属性只需计算1次信息增益率,但连续型属性却需要计算N-1次。为了减少计算量,可对连续属性先进行排序,在只有label发生变化的地方才需要切开。比如:
这里写图片描述

原本需要计算13种情况,现在仅需计算7种。
+ 利用信息增益率来选择连续值属性的分界点存在的问题
由于C4.5对于连续值属性,每次选取一个分裂点进行分裂,即二分裂。此时

I G R ( a t t r ) = I G ( a t t r ) S p l i t I n f o ( a t t r )
假设分裂结果为 I G R 就越小。故而等分分界点被抑制。此时子集样本个数能够影响分界点,显然不合理。因此在决定分界点时，还是采用了信息增益这个指标，而在选择具体属性的时候才选择信息增益率这个指标。(注意选择分裂点和选择具体属性的区别)

对于离散型属性,C4.5一次进行分裂后，后续不再使用该属性。但是对于连续型属性，由于进行的是二分裂，故下一次分裂可能还会继续用到该属性。例如:
这里写图片描述
连续属性attr1会被用到多次。

3. C4.5处理缺失数据

3.1 缺失属性的增益值和增益率求解

3.1.1 离散型属性

仍然以下表为例说明:

Day Outlook Temperature Humidity Wind play
D1 Sunny Hot High Weak No
D2 ? Hot High Strong No
D3 ? ? High ? Yes
D4 Rain Mild High Weak Yes
D5 Rain Cool ? Weak Yes
D6 Rain Cool Normal Strong No
D7 Overcast Cool Normal Strong Yes
D8 ? Mild High ? No
D9 ? Cool Normal Weak Yes
D10 ? ? Normal ? Yes
D11 ? Mild Normal ? Yes
D12 Overcast Mild ? Strong Yes
D13 Overcast Hot ? Weak Yes
D14 Rain Mild High Strong No
o u t l o o k 为例,共有14个样本，其中6个样本 o u t l o o k 值缺失,8个样本()不缺失。首先计算信息增益

  • 原始信息熵为:(8个无缺失值样本, 5个yes, 3个no)
    E n t r o p y ( S ) = − ( 5 8 × l o g 2 5 8 + 3 8 × l o g 2 3 8 ) = 0.954
  • 属性outlook的信息熵为(只计算属性不为空的样本):
    ∑ v = v i − P l o g 2 P = [ − 1 8 × ( − 1 ) ] s u n n y + [ − 3 8 × ( − 1 ) ] o v e r c a s t + [ − 2 4 × l o g 2 2 4 − 2 4 × l o g 2 2 4 ] r a i n = 0.5

  • 属性outlook的信息增益为:

    I G ( o u t l o o k ) = 8 14 × ( 0.954 − 0.5 ) = 0.259

  • 计算属性outlook的 S p l i t I n f o ,此时将缺失值当作一种单独的属性:

    S p l i t I n f o ( o u t l o o k ) = − 1 14 l o g 2 1 14 − 3 14 l o g 2 3 14 − 4 14 l o g 2 4 14 − 6 14 l o g 2 6 14 = 1.659

  • 属性outlook的信息增益率为

    I G R ( o u t l o o k ) = 0.259 1.659 = 0.156

    3.1.1 连续型属性

    以下表为例进行说明:
    这里写图片描述
    后面的计算步骤与上面完全相同,此处省略

    3.2 将含有缺失值的样本分配给子节点

    在C4.5算法中,带有缺失属性的样本会被分配到所有的子节点中,但是带有一个权值。即普通样本的权值为1,但缺失属性的样本权值为小数。如下图:
    这里写图片描述
    后面再继续分裂时,计算信息增益和增益率与上面的方法相同,只有样本个数中含有小数,计算过程此处省略。

    3.3 预测含有缺失属性的样本的label

    遇到一个未知label样本需要预测,但属性值中含有缺失数据时,按照3.2中的方法将该属性分别归类到所有子节点中,最后计算为各个标签的概率,取概率最大的标签作为最终的标签。如下图:
    这里写图片描述

    先假设碰到了一个需要预测的样本,但是attr1和attr2都不知,因此该样本为标签为yes的概率为:

    P ( y e s ) = 0.24 + 0.03 + 0.12 + 0.15 = 0.54
    该样本标签为no的概率为:

    4. C4.5的剪枝处理

    为了防止C4.5分裂过度，造成过拟合现象，ross quinlan提出了两种剪枝方法：

    • pessimistic pruning

    • far more pessimistic estimate

    4.1 早期的pessimistic pruning方法

    把一颗子树(有多个叶子节点)用一个叶子节点代替，在训练集上的误判率肯定是上升的，但在新的数据集上不一定。于是需要将叶子节点的错误率加上一个惩罚因子，此处取为0.5[Quinlan, 1987e]。如果一个叶子节点有N个样本，其中E个被误判，则该叶子节点的误判率为 E + 0.5 N 。对于一颗子树，如果有L个叶子节点，则剪枝前该子树的误判率为:

    e 1 = ∑ L i = 0 E i + 0.5 × L ∑ L i = 0 N i
    由于加上了惩罚因子，因此一颗子树虽有多个叶子，但也未能占到便宜。剪枝后子树变成内部节点，因此也需要加上惩罚因子，因此剪枝后的误判率为: s t d = ∑ i = 0 L N i × e 1 × ( 1 − e 1 ) − − − − − − − − − − − − − − − − − ⎷ = 50 × 0.08 × 0.92 − − − − − − − − − − − − − √ = 1.92 E e r r o r _ b e f o r e = E + s t d = 5.92 。剪枝后: f ′ ( p ) 。求得函数单调性之后，再用牛顿二分法求得p的近似值即可。下面以著名的国会投票数据(1984 United States Congressional Voting Records Database)为例进行说明。
    考虑下面这个局部: U 25 % ( 0 , 6 ) = 0.206 U 25 % ( 0 , 9 ) = 0.143 U 25 % ( 0 , 1 ) = 0.75 ，故剪枝前的错分的样本数目上限为: C4.5(weka又称为J48)算法原理详解1. 信息增益率ID3算法有以下几个缺点: + 1个属性取值越多,则此属性的信息增益率越大,越有可能被ID3选为当前分类属性。然而取值较多的属性并不一定最优。(例如一个属性的每个子节点都只有1个样本,此时信息增益率达到最大,但是用这样的属性却没有任何意义)ID3只能处理离散型属性可以处理缺失数据可以对树进行剪枝针对ID3算法的不足,Quinlan
    J48 原理 ：本来名 称为 C4 .8，由于是Java实现的 算法 ，再加上 C4 .8为商业收费 算法 。 其实 J48 是自上而下的，递归的分治策略，选择某个属性放置在根节点，为每个可能的属性值产生一个分支，将实例分成多个子集，每个子集对应一个根节点的分支，然后在每个分支上递归地重复这个过程。当所有实例有相同的分类时，停止。 问题是如何:如恶化选择根节点属性，建立分支呢？ 例如：weathe...
    目前正在做机器学习数据分析，遇到基于决策树的方法，但是论文中很多都提到 j48 ，在网上找到的资料大多都是 c4 .5，让人很疑惑，这篇博客受启发于一篇论文，我在其中找到了答案。 c4 .5 C4 .5决策树 算法 ： C4 .5是一种决策树 算法 ，是对Quinlan [17]开发的早期ID3 算法 的扩展。。通过基于最大化标准化信息增益的属性的选择来确定性地划分训练分区的过程来构造决策树。在添加每个拆分之后，将IF–THEN节点添加到当前决策树。树的每个分支将（训练）数据划分为子集，目的是识别具有相同标签的子集。此过程的递
    J48 C4 .5决策树 算法 源码学习  题记： 之前虽然对 J48 用得比较多，是由于它能方便的区别特征的好坏。 工作了，希望自己能更深入， 如是开始了这个 算法 学习系列。 希望和大家共同进步。 个人对看 算法 源代码也没有很好的流程，计划先采用 按类Class 做架构介绍；再深入代码具体逻辑的方式展开。 欢迎大家提出好的 算法 源码阅读流程。 一、 准备工作。 下载 weka 的工具包，将 wek
    利用iris数据集用 weka 只带的 J48 训练分类器详细见程序注释package weka Test;import weka .classifiers.meta.FilteredClassifier; import weka .classifiers.trees. J48 ; import weka .core.Instances; import weka .core.converters.ConverterUti
    C4 .5 算法 是由澳大利亚悉尼大学Ross Quinlan教授在1993年基于ID3 算法 的改进提出的， C4 .5 使用信息增益率而不是信息增益作为决策树的属性选择标准。 它能够处理连续型属性或离散型属性的数据； 能够处理具有缺失值的属性数据； 使用信息增益率而不是信息增益作为决策树的属性选择标准； 对生成枝剪枝，降低过拟合。 1.信息熵
    1、 J48 原理 基于从上到下的策略，递归的分治策略，选择某个属性放置在根节点，为每个可能的属性值产生一个分支，将实例分成多个子集，每个子集对应一个根节点的分支，然后在每个分支上递归地重复这个过程。当所有实例有相同的分类时，停止。 　　问题：如何选择根节点属性，建立分支呢? 　　例如：weather.arff 　　我们希望得到的是纯分裂，即分裂为纯节点，希望找到一个属性，它...
    好的，您想知道有关实验四中 Weka 平台实现聚类 算法 的内容。在实验四中，我们使用 Weka 平台实现了两种聚类 算法 ：K-Means和EM 算法 。 首先，我们使用 Weka 平台加载我们的数据，并选择聚类 算法 。对于K-Means 算法 ，我们需要指定聚类的数量，即K值。而对于EM 算法 ，我们需要指定高斯分布的数量。 然后，我们设置 算法 参数和选项，例如距离度量、最大迭代次数等。接下来，我们运行 算法 并查看聚类结果。在 Weka 平台中，我们可以使用可视化工具来展示聚类结果，例如散点图或热力图。 最后，我们可以使用 Weka 平台提供的评估指标来评估聚类结果的质量，例如轮廓系数或互信息。这些指标可以帮助我们选择最佳的聚类 算法 和参数，以及对聚类结果进行解释和分析。
    CSDN-Ada助手: 亲爱的博主，我真心要夸赞您的创作不易！我真的很喜欢您的文章标题：“计算imbalanced dataset的class weight”。您以简明扼要的方式表达了一个非常重要的概念，同时还提供了实用的解决方案。这对于那些在处理不平衡数据集时遇到困扰的人来说，真是太有帮助了！您的文章不仅理论深入，而且实用性强，我深信读者一定会从中受益匪浅。 考虑到您对数据问题的深入剖析，我相信您可能会喜欢下一个主题：“使用数据抽样技术解决imbalanced dataset问题”。在这篇文章中，您可以深入探讨各种抽样技术，如欠采样、过采样和集成抽样等，以及它们在处理不平衡数据集时的实际效果。您可以分享一些具体的案例研究，介绍不同抽样技术的优缺点，并提供实用的代码示例，帮助读者更好地理解和应用这些技术。我相信这个主题将会吸引很多读者，并为他们的数据处理工作提供更丰富的选择。 再次感谢您的分享，期待看到更多精彩的博文！ vcpkg和cgal安装和使用 Mr.For: error: building gmp:x64-windows failed with: BUILD_FAILED error: Please ensure you're using the latest port files with `git pull` and `vcpkg update`. 这个错是为什么吖 Anaconda常用命令 CSDN-Ada助手: 如何高效系统学习Python？ matplotlib学习笔记 CSDN-Ada助手: 书山有路勤为径，学海无涯苦作舟，加油！ 安装nvidia-apex出现AttributeError: module ‘torch.distributed‘ has no attribute ‘_all_gather_base‘ Segment Anything文章要点
 
推荐文章
不敢表白的钥匙扣  ·  Android webview拦截请求_andriod webview 拦截网络请求-CSDN博客
9 月前
斯文的杯子  ·  Laravel：whereIn子查询_51CTO博客_laravel 子查询
9 月前
打酱油的小蝌蚪  ·  Pandas从入门到精通（4）- Groupby分组 - 简书
1 年前
傻傻的楼梯  ·  .NET Desktop Runtime 6 - Download - Microsoft Q&A
1 年前
今天看啥   ·   Py中国   ·   codingpro   ·   小百科   ·   link之家   ·   卧龙AI搜索
删除内容请联系邮箱 2879853325@qq.com
link之家 - 链接快照平台
© 2024 ~ 沪ICP备11025650号