简述ID3算法的基本思想及其主算法和建树算法的基本步骤。
题目
简述ID3算法的基本思想及其主算法和建树算法的基本步骤。
相似考题
更多“简述ID3算法的基本思想及其主算法和建树算法的基本步骤。”相关问题
-
第1题：
简述最大载干比算法的基本思想。
正确答案: 按照载干比从大到小的顺序选择调度用户，让信道条件最好的哦能更好优先占用资源传输数据，若有剩余资源，再分配给信道条件次好的用户，以此类推，直到没有资源可以分配或所用用户都被调度。最大载干比算法在提升小区吞吐量方面有优势。 -
第2题：
ID3算法主要存在的缺点是什么？
正确答案:（1）ID3算法在选择根结点和各内部结点中的分枝属性时，使用信息增益作为评价标准。信息增益的缺点是倾向于选择取值较多的属性，在有些情况下这类属性可能不会提供太多有价值的信息。
（2）ID3算法只能对描述属性为离散型属性的数据集构造决策树。 -
第3题：
简述回溯法的基本思想，采用这种算法的关键是什么？
正确答案:回溯法是一种有组织的系统化搜索问题解的技术，它是对穷举搜索的改进，其采用的 是“向前走，碰壁回头”思想。具体的说，首先要对问题进行分析，确定问题的所有可能解，即确定问题的解空间，然后沿着所确定的路线搜索向前搜索。在搜索过程中，对每一步得到的部分解进行判断，如果该部分解有可能构成一个完整解，说明这一步走得通，则继续向前走，也就是进一步构造问题解。否则，说明“此路不同”，则需要回退，找另一条路线再搜索，也就是回溯，从新的路线上继续构造问题的解。
由回溯法的求解过程可以看出，采用回溯法的关键是确定正确的解空间，即确定解的搜索范围，并确定搜索的路线，只有做到这两步，才可能有效地对问题解进行搜索。
例如，“给定一个正整数集合X={ x1， x2， …， xn }和一个正整数 y，求集合X的一个子集Y，使得Y中的元素之和等于y。”，这个问题可以采用回溯法来求解。其求解思路是：
从X集合中依次选取各元素并将其与Y中的元素相加，考察相加结果。具体做法是：
·初始子集Y为空，其元素和等于0；
·选取x1 ，将其与子集Y的元素和相加，检查结果：
若相加结果大于y，则放弃当前所选xi ：
若X中还有后续元素，继续选取xi+1 再试；
否则，回溯：放弃xi之前一个选中的元素，继续向后选取；
若相加结果小于y，做Y=Y+xi，继续向后选取xi+1 再试；
若相加结果等于y，输出Y中的元素。 由于这个问题的解空间比较明确（求X的子集），因此，实现这个回溯算法的关键，是确定求满足条件的子集的思路确定对当前项xi取或舍的准则。即，确定对x1， x2， …， xn 求和的顺序以及判断当前和是否满足条件的准则。确定了这两个条件，这个回溯算法的搜索路线也就确定了。算法思路也就明确了。 -
第4题：
简述动态规划算法的基本步骤。
正确答案: 设计一个标准的动态规划算法，通常可按以下几个步骤进行：
（1）划分阶段：按照问题的时间或空间特征，把问题分为若干个阶段。注意这若干个阶段一定要是有序的或者是可排序的（即无后向性），否则问题就无法用动态规划求解。
（2）选择状态：将问题发展到各个阶段时所处于的各种客观情况用不同的状态表示出来。当然，状态的选择要满足无后效性。
（3）确定决策并写出状态转移方程：之所以把这两步放在一起，是因为决策和状态转移有着天然的联系，状态转移就是根据上一阶段的状态和决策来导出本阶段的状态。所以，如果我们确定了决策，状态转移方程也就写出来了。但事实上，我们常常是反过来做，根据相邻两段的各状态之间的关系来确定决策。
（4）写出规划方程（包括边界条件）：动态规划的基本方程是规划方程的通用形式化表达式。
一般说来，只要阶段、状态、决策和状态转移确定了，这一步还是比较简单的。动态规划的主要难点在于理论上的设计，一旦设计完成，实现部分就会非常简单。根据动态规划的基本方程可以直接递归计算最优值，但是一般将其改为递推计算。实际应用当中经常不显式地按照上面步骤设计动态规划，而是按以下几个步骤进行：
（1）分析最优解的性质，并刻划其结构特征。
（2）递归地定义最优值。
（3）以自底向上的方式或自顶向下的记忆化方法（备忘录法）计算出最优值。
（4）根据计算最优值时得到的信息，构造一个最优解。
步骤（1）～（3）是动态规划算法的基本步骤。在只需要求出最优值的情形，步骤（4）可以省略，若需要求出问题的一个最优解，则必须执行步骤（4）。此时，在步骤（3）中计算最优值时，通常需记录更多的信息，以便在步骤（4）中，根据所记录的信息，快速地构造出一个最优解。
总结：动态规划实际上就是最优化的问题，是指将原问题的大实例等价于同一最优化问题的较小实例，自底向上的求解最小实例，并将所求解存放起来，存放的结果就是为了准备数据。与递归相比，递归是不断的调用子程序求解，是自顶向下的调用和求解。 -
第5题：
ID3，C4.5，CART等分类算法均是在（）的基础上改进得到。
- A、Apriori算法
- B、SVD算法
- C、Hunt算法
- D、EM算法
正确答案:C -
第6题：
简述EPON动态带宽分配中分配准许算法的基本思想。
正确答案: 各ONU利用上行可分割时隙反映信元到达的时间分布并请求带宽，OLT根据各ONU的请求公平合理地分配带宽，并同时考虑处理超载、信道有误码、有信元丢失等情况的处理。 -
第7题：
试述优化算法的基本思想。
正确答案:在设计空间中选定一个初始点，从这一点出发，按照某一优化方法所规定的原则，确定适当的搜索方向与步长，在此方向上获得一个使目标函数数值有所下降的设计点，然后以点作为新的初始点，重复上面的过程，直至得到满足精度要求的最优点。 -
第8题：
问答题简述回溯法的基本思想，采用这种算法的关键是什么？正确答案： 回溯法是一种有组织的系统化搜索问题解的技术，它是对穷举搜索的改进，其采用的 是“向前走，碰壁回头”思想。具体的说，首先要对问题进行分析，确定问题的所有可能解，即确定问题的解空间，然后沿着所确定的路线搜索向前搜索。在搜索过程中，对每一步得到的部分解进行判断，如果该部分解有可能构成一个完整解，说明这一步走得通，则继续向前走，也就是进一步构造问题解。否则，说明“此路不同”，则需要回退，找另一条路线再搜索，也就是回溯，从新的路线上继续构造问题的解。
由回溯法的求解过程可以看出，采用回溯法的关键是确定正确的解空间，即确定解的搜索范围，并确定搜索的路线，只有做到这两步，才可能有效地对问题解进行搜索。
例如，“给定一个正整数集合X={ x1， x2， …， xn }和一个正整数 y，求集合X的一个子集Y，使得Y中的元素之和等于y。”，这个问题可以采用回溯法来求解。其求解思路是：
从X集合中依次选取各元素并将其与Y中的元素相加，考察相加结果。具体做法是：
·初始子集Y为空，其元素和等于0；
·选取x1 ，将其与子集Y的元素和相加，检查结果：
若相加结果大于y，则放弃当前所选xi ：
若X中还有后续元素，继续选取xi+1 再试；
否则，回溯：放弃xi之前一个选中的元素，继续向后选取；
若相加结果小于y，做Y=Y+xi，继续向后选取xi+1 再试；
若相加结果等于y，输出Y中的元素。 由于这个问题的解空间比较明确（求X的子集），因此，实现这个回溯算法的关键，是确定求满足条件的子集的思路确定对当前项xi取或舍的准则。即，确定对x1， x2， …， xn 求和的顺序以及判断当前和是否满足条件的准则。确定了这两个条件，这个回溯算法的搜索路线也就确定了。算法思路也就明确了。解析： 暂无解析 -
第9题：
问答题简述常用的页面置换算法的基本思想.正确答案： 在请求分页面置换算法是一个核心的问题.常用的页面置换算法有如下三种：
（1）先进先出算法FIFO：总是先淘汰那些驻留内存时间最长的页面，即先进入主存的页面先淘汰.
（2）最近最久末用置换算法LRU：该算法的思想是基于程序设计的局部化程度，即若某一页被访问了，则它很可能马上又被访问；反之若某一页很久末被访问，则最近也不会再被访问，所以先置换出主存，即当需要淘汰一页时，选择在最近王码电脑公司软件中心段时间内，最长时间没有被访问的页.
（3）LRU近算法：LRU算法的一种简单实现.在时间T内，将被访问过的页面的"访问位"置1，而末被访问过的页面置0.当需要置换页面时，只需选择"访问位"为0的页面即可.解析： 暂无解析 -
第10题：
问答题简述BP神经网络中，BP算法的基本思想。正确答案： 误差反向传播的学习算法简称BP算法，其基本思想是按梯度下降法进行学习。它采用梯度搜索技术，以期使网络的实际输出值与期望的输出值的误差均方值为最小。解析： 暂无解析 -
第11题：
问答题说明ID3方法的建树算法步骤？正确答案： （1）对当前例子集合，计算各特征的互信息。
（2）选择互信息最大的特征Ak，作为树（或子树）的根节点。
（3）把在Ak处取值相同的例子归于同一子集，该取值作为树的分支。Ak取几个值就得到几个子集，各取指作为树的一个分支。
（4）对既含正例又含反例的子集，递归调用建树算法。
（5）若自己仅含正例或反例，对应分支标上P或N，返回调用处。解析： 暂无解析 -
第12题：
问答题简述图像分割中区域生长算法和分水岭算法的基本原理和步骤。正确答案： 区域生长算法是预先定义的生长准则，以一组“种子”点开始形成生长区域，把预先定义好属性与种子类似的领域象素加入到种子点上。
步骤：
1、根据图像的不同应用选择一个或一组“种子”点；
2、定义一个描述符；
3、“种子”点开始扩散，加入到象素的区域集合，与集合中的每个象素联通；
4、直到没有任何新的象素点加入为止。
分水岭算法是根据测地学的拓扑原理，极小值与区域为汇水盆，汇水盆的边缘为分水岭，以象素的灰度值来体现其3D的高度。
步骤：假设有水从各谷底涌出并且水位逐渐增高，如果从两个相邻谷底涌出的水的水位高过其间的山峰，这些水就会汇合，根据分割目标的要求控制汇合的程度来达到分割的目的。解析： 暂无解析 -
第13题：
ID3算法是一种贪心算法，它以自顶向下递归各个击破方式构造决策树（）
正确答案:正确 -
第14题：
简述Tomasulo算法的基本思想。
正确答案: 核心思想是：
①记录和检测指令相关，操作数一旦就绪就立即执行，把发生RAW冲突的可能性减小到最少；
②通过寄存器换名来消除WAR冲突和WAW冲突。寄存器换名是通过保留站来实现，它保存等待流出和正在流出指令所需要的操作数。
基本思想：只要操作数有效，就将其取到保留站，避免指令流出时才到寄存器中取数据，这就使得即将执行的指令从相应的保留站中取得操作数，而不是从寄存器中。指令的执行结果也是直接送到等待数据的其它保留站中去。因而，对于连续的寄存器写，只有最后一个才真正更新寄存器中的内容。一条指令流出时，存放操作数的寄存器名被换成为对应于该寄存器保留站的名称（编号）。 -
第15题：
试描述边界跟踪算法的基本思想。
正确答案:若已知前继点Q，当前点P，从P的邻域（8或者4）中按顺（逆）时针方向发现下一个边界点，直到遇到P点为止，跟踪结束；若图象有多个区域则需要对已经跟踪过的区域进行标记，以避免跟踪过程的重复。 -
第16题：
主要的数据挖掘算法有（）。
- A、分割聚类法
- B、ID3算法
- C、Apriori算法
- D、遗传算法
正确答案:A,B,C -
第17题：
简述种子填充算法与栅格算法的基本思想。
正确答案: 种子填充算法（内部点扩散法）：由一个内部的种子法，向其四个方向的邻点扩散。判断新加入的点是否是否在多边形边界上。如果是，就不作为种子点，否则当作新的种子点，直到区域填满，无种子点为止。该算法比较复杂，而且可能造成阻塞而造成扩散不能完成。此外若多边形不完全闭合时，会扩散出去。栅格算法：栅格指的是一条与扫描线垂直的直线，栅格位置通常取多边形的顶点，并且把多边形分为左右两半。基本思想是对于每个扫描线与多边形的交点，将交点与栅格之间的像素用多边形的属性值填补。若交点位于栅格左边，则将交点右边，栅格左边的所有像素取补；若交点位于右边，则把栅格右边交点左边的像素取补。 -
第18题：
算法设计中的递归、穷举、递推和迭代等算法的基本思想是什么？
正确答案: 递推法：是利用问题本身所具有的一种递推关系求解问题的一种方法。它把问题求解分成若干步，找出相邻几步的关系，从而达到求解问题的目的。具有如下性质的问题可以采用递推法：当得到问题规模为i-1的解后，由问题的递推性质，能构造出问题规模为i的解。因此，程序可以从i=0或i=1出发，由已知i-1规模的解，通过递推，获得问题规模为i的解，直至得到问题规模为n的解。
递归法：递归策略是利用函数直接或间接地调用自身来完成某个计算过程。能采用递归描述的算法通常有这样的特征：为求解规模为n的问题，设法将它分解成规模较小的问题，然后从这些小问题的解方便地构造出更大问题的解，并且这些规模较小的问题也能采用同样的分解和综合方法，分解成规模更小的问题，并从这些更小问题的解构造出较大规模问题的解。
穷举法：穷举搜索法也称穷举法或搜索法是对可能是解的众多候选解按某种顺序进行逐一枚举和检验，并从中找出那些符合要求的候选解作为问题的解。
迭代法：数值分析中通过从一个初始估计出发寻找一系列近似解来解决问题（一般是解方程或者方程组）的过程，为实现这一过程所使用的方法统称为迭代法。 -
第19题：
简述常用的页面置换算法的基本思想.
正确答案: 在请求分页面置换算法是一个核心的问题.常用的页面置换算法有如下三种：
（1）先进先出算法FIFO：总是先淘汰那些驻留内存时间最长的页面，即先进入主存的页面先淘汰.
（2）最近最久末用置换算法LRU：该算法的思想是基于程序设计的局部化程度，即若某一页被访问了，则它很可能马上又被访问；反之若某一页很久末被访问，则最近也不会再被访问，所以先置换出主存，即当需要淘汰一页时，选择在最近王码电脑公司软件中心段时间内，最长时间没有被访问的页.
（3）LRU近算法：LRU算法的一种简单实现.在时间T内，将被访问过的页面的"访问位"置1，而末被访问过的页面置0.当需要置换页面时，只需选择"访问位"为0的页面即可. -
第20题：
问答题简述EPON动态带宽分配中分配准许算法的基本思想。正确答案： 各ONU利用上行可分割时隙反映信元到达的时间分布并请求带宽，OLT根据各ONU的请求公平合理地分配带宽，并同时考虑处理超载、信道有误码、有信元丢失等情况的处理。解析： 暂无解析 -
第21题：
问答题简述种子填充算法与栅格算法的基本思想。正确答案： 种子填充算法（内部点扩散法）：由一个内部的种子法，向其四个方向的邻点扩散。判断新加入的点是否是否在多边形边界上。如果是，就不作为种子点，否则当作新的种子点，直到区域填满，无种子点为止。该算法比较复杂，而且可能造成阻塞而造成扩散不能完成。此外若多边形不完全闭合时，会扩散出去。栅格算法：栅格指的是一条与扫描线垂直的直线，栅格位置通常取多边形的顶点，并且把多边形分为左右两半。基本思想是对于每个扫描线与多边形的交点，将交点与栅格之间的像素用多边形的属性值填补。若交点位于栅格左边，则将交点右边，栅格左边的所有像素取补；若交点位于右边，则把栅格右边交点左边的像素取补。解析： 暂无解析 -
第22题：
问答题简述动态规划算法的基本步骤。正确答案： 设计一个标准的动态规划算法，通常可按以下几个步骤进行：
（1）划分阶段：按照问题的时间或空间特征，把问题分为若干个阶段。注意这若干个阶段一定要是有序的或者是可排序的（即无后向性），否则问题就无法用动态规划求解。
（2）选择状态：将问题发展到各个阶段时所处于的各种客观情况用不同的状态表示出来。当然，状态的选择要满足无后效性。
（3）确定决策并写出状态转移方程：之所以把这两步放在一起，是因为决策和状态转移有着天然的联系，状态转移就是根据上一阶段的状态和决策来导出本阶段的状态。所以，如果我们确定了决策，状态转移方程也就写出来了。但事实上，我们常常是反过来做，根据相邻两段的各状态之间的关系来确定决策。
（4）写出规划方程（包括边界条件）：动态规划的基本方程是规划方程的通用形式化表达式。
一般说来，只要阶段、状态、决策和状态转移确定了，这一步还是比较简单的。动态规划的主要难点在于理论上的设计，一旦设计完成，实现部分就会非常简单。根据动态规划的基本方程可以直接递归计算最优值，但是一般将其改为递推计算。实际应用当中经常不显式地按照上面步骤设计动态规划，而是按以下几个步骤进行：
（1）分析最优解的性质，并刻划其结构特征。
（2）递归地定义最优值。
（3）以自底向上的方式或自顶向下的记忆化方法（备忘录法）计算出最优值。
（4）根据计算最优值时得到的信息，构造一个最优解。
步骤（1）～（3）是动态规划算法的基本步骤。在只需要求出最优值的情形，步骤（4）可以省略，若需要求出问题的一个最优解，则必须执行步骤（4）。此时，在步骤（3）中计算最优值时，通常需记录更多的信息，以便在步骤（4）中，根据所记录的信息，快速地构造出一个最优解。
总结：动态规划实际上就是最优化的问题，是指将原问题的大实例等价于同一最优化问题的较小实例，自底向上的求解最小实例，并将所求解存放起来，存放的结果就是为了准备数据。与递归相比，递归是不断的调用子程序求解，是自顶向下的调用和求解。解析： 暂无解析 -
第23题：
问答题简述零基预算法的基本思想。正确答案： 零基预算的基本思想是：在每个预算年度开始时，把所有还在继续开展的活动都视为是从零开始的，重新编制预算。预算人员以一切从头开始的思想为指导，根据各项活动的实际需要，安排各项活动及各个部门的资源分配和收支。解析： 暂无解析