`

极大特殊假设算法,候选消除算法,决策树表示法

 
阅读更多

 极大特殊假设算法:

样本:

 

算法描述

1. 将h初始化为H中特殊的假设
2. 对每个正例x
      对h的每个属性ai
         如果x满足ai,那么不做任何处理
          否则将h中的ai替换为x满足的下一个更一般的假设
3. 输出假设h

 

 

算法应用
    最特殊的假设:   h = <Æ, Æ, Æ, Æ, Æ, Æ, Æ>
    经过第1个样本: h = <Sunny, Warm, Normal, Strong, Warm, Same>
    经过第2个样本: h = <Sunny, Warm, ?, Strong, Warm, Same>
    经过第3个样本: 不处理,Find-S忽略每一个反例。
    经过第4个样本: h = <Sunny, Warm, ?, Strong, ?, ?>

 

 

分析Find-S算法
    只得到假设空间中的一个假设,而且是极大特殊的那个。对含有噪声的数据无能为力。要求属性值和输出值都是离散的。

 

 

候选消除算法

算法描述

1. 变型空间VersionSpace<-包含H中所有假设的列表
2. 对每个训练样例<x, c<x>>
   从变型空间中移除所有h(x)!=c(x)的假设h
3. 输出 VersionSpace中的假设列表 

 

使用变型空间的候选消除算法

把G集合初始化为H中的极大一般假设

把S集合初始化为H中的极大特殊假设

对每个训练样例d,进行以下操作:

·如果d是正例

    ·从G中移去所有与d不一致的假设

    ·对S中每个与d不一致的假设s

        ·从S中移去s

        ·把s的所有的极小一般化式h加入到S中,其中h满足:h与d一致,而且G的某个成员比h更一般

        ·从S中移去所有这样的假设:它比S中另一假设更一般

·如果d是反例

    ·从S中移去所有与d不一致的假设

    ·对G中每个与d不一致的假设g

        ·从G中把移去g

        ·把g的所有极小特殊化式h加入到G中,其中h满足:h与d一致,而且S的某个成员比h更特殊

 

        ·从G中移去所有这样的假设:它比G中另一假设更特殊

 

 算法实例:

http://blog.csdn.net/yang_zhe_/article/details/50570914

 

决策树表示法

http://blog.csdn.net/HerosOfEarth/article/details/52347820

  • 大小: 9.5 KB
分享到:
评论

相关推荐

    对数据挖掘决策树分类法的研究.pdf

    分类技术中的决策树分类法是一种非常有代表性的方法,它通过构建一棵树形结构来表示数据的分类规则,从而实现分类预测的目的。 决策树是一种以样本数据为基础的经典数据挖掘归纳算法,能够进行分类及预测,具有流程...

    回溯法 算法

    回溯法是一种用于解决组合问题的算法,其核心思想是通过探索所有可能的候选解来找出所有解,如果候选解被确认不是一个解,则回溯一步甚至多步,再尝试其他解。这一算法适用于那些解空间庞大且难以通过直接计算得到解...

    随机森林算法-中文

    在决策树的每个节点,随机森林算法会从全部预测变量中随机选择一部分作为候选变量,从中寻找最佳的划分变量。这一步骤增强了树之间的差异性,进一步提升了模型的预测准确度。而且,每棵树都会生长至最大规模而不进行...

    东北大学算法设计课程实验源码

    本篇文章旨在详细介绍东北大学算法设计课程实验源码中包含的三种基础且核心的算法思想:分治法、回溯法、以及动态规划,并探讨如何在实际编程和问题解决中灵活运用这些算法。 首先,让我们来深入探讨分治法。分治法...

    虹软算法岗笔试题

    基础的监督学习、无监督学习、强化学习的原理,以及常见的模型(如线性回归、逻辑回归、SVM、神经网络、决策树、K-means等)是必备知识。 6. **图像处理与计算机视觉**:虹软的主要业务领域,因此可能需要了解图像...

    天津科技大学算法设计样卷

    - **大O记号、Ω记号、Θ记号**:用来描述算法复杂性,其中大O表示算法复杂性的上界,Ω表示下界,Θ表示精确边界。 - **具体示例**:例如,f(n) = O(g(n)) 表示f(n)的增长速率不超过g(n);f(n) = Ω(g(n)) 表示f(n...

    算法导论_mit

    - **渐近符号**:在算法分析中,我们通常使用O(大O)、Ω(大欧米伽)、θ(大西塔)等渐近符号来表示算法的上界、下界以及精确边界。 - **标准符号与常见函数**:如多项式函数、指数函数、对数函数等,在算法分析...

    C++实现FP-Growth算法

    Apriori算法基于“频繁项集的任何子集也必须是频繁的”这一先验性质,通过迭代生成候选集并检查其支持度来找到频繁项集。然而,这种方法在处理大数据时效率较低,因为它会产生大量的中间结果。 结合C++的FP-Growth...

    算法导论3rd

    渐近表示法是算法分析中用来描述函数增长趋势的数学工具,包括大O表示法、Ω表示法、Θ表示法等。其中,大O表示法用于上界估计,描述算法在最坏情况下的时间复杂度;Ω表示法用于下界估计,反映算法在最好情况下的...

    Apriori算法 matlab

    - **Eclat**(垂直数据表示法):通过数据的位向量表示,减少内存需求和计算时间。 - **FP-Growth**:利用频繁模式树(FP-Tree)结构,只扫描数据一次,显著提高效率。 - **Bite** 和 **Closet**:这些算法适用于...

    数据结构-五子棋核心算法

    核心算法包括初始化一个具有负无穷大值的`value`(表示当前机器的盘面评分),通过`calseveralgoodplace`函数找到当前盘面的高分候选位置,形成搜索的第一层节点。然后,使用深度优先搜索(DFS)遍历所有可能的走法...

    算法设计与分析 回溯法与分支限界法

    ### 算法设计与分析:回溯法与分支限界法 #### 一、回溯法 **1.0-1背包问题** - **问题描述**:设有n种物品和一个容量为C的背包,每种物品都有固定的重量Wi和价值Vi。目标是从这n种物品中选择一些放入背包,使得...

    基于FP增长算法的数据挖掘技术

    #### 四、FP树表示法 FP树是一种紧凑的数据结构,用于存储数据集中的信息。它通过将每个事务映射为FP树中的一条路径来构造。不同事务之间可能会有一些相同的项,这使得它们的路径在FP树中可能存在重叠。路径重叠越...

    采用优先队列式分枝限界法求解0/1背包问 题.pdf

    分枝策略涉及通过决策树的方法系统地枚举所有可能的候选解。限界策略则是在搜索过程中,通过剪枝技术减少需要考虑的节点数量,提高算法效率。 优先队列式分枝限界法是分枝限界法的一种改进形式,它利用优先队列...

    李航《统计学习方法》笔记 --从原理到实现:基于R.pdf

    6. 决策树算法:包括信息增益和信息增益比的概念,以及如何构建决策树,如ID3算法和C4.5算法。决策树的剪枝过程是防止过拟合、提高模型泛化能力的重要步骤。 7. 逻辑斯蒂回归与最大熵模型:逻辑斯蒂回归是一种广泛...

    算法课程设计,界面可视化

    Java和Python都可以实现这个算法,通过创建一棵表示颜色分配状态的决策树,递归地尝试给每个未着色的省份涂色,直到所有省份都被覆盖,或者发现无法满足条件时回溯。 4. **超市最佳选址 - 蛮力法** 超市最佳选址...

    计算机算法导论

    - **方法**:通常使用大O符号表示算法的最坏情况下的时间复杂度,同时也要考虑平均情况和最好情况下的性能。 - **2.3 设计算法** - **策略**:常见的算法设计策略包括贪心算法、分治算法、动态规划等。 - **步骤...

    基本算法实现

    5. **贪心算法**:每一步都采取当前最优决策,但不保证全局最优,如霍夫曼编码、Prim算法(最小生成树)。 6. **回溯法**:在解决问题时尝试所有可能的解决方案,并在遇到错误时返回,常用于解决组合优化问题,如八...

Global site tag (gtag.js) - Google Analytics