2.回归、KNN、K-Means、搜索方法思想及算法实现步骤

线性回归

线性回归概述

已知样本的特征值和样本的结果，推测特征与值之间的函数，从而在获取新样本的特征值后根据推测的函数模型计算出样本的值。

线性回归模型表示

关键点：确定参数θ，使代价函数最小化

假设函数h(x)

定义：假设函数是线性回归模型的核心部分，它表示了输入特征 x 与输出值 y 之间的线性关系。假设函数的形式通常为：

其中，θ 是模型参数，x 是输入特征向量。

作用：假设函数的作用是根据输入特征 x 和模型参数 θ 来预测输出值 y。在线性回归中，假设函数是一个线性方程，它描述了输入特征与目标值之间的线性关系。

确定参数：为了得到最佳的预测结果，需要确定假设函数中的参数 θ。这通常通过最小化代价函数来实现。一旦找到了最佳的参数 θ，假设函数就可以用于对未知数据进行预测。

⭐️总之，函数就是拿来预测的；假设函数根据θ的取值不同，假设函数不同。θ越小，根据假设函数h算出来的值与训练样本的y值误差尽量小。
⭐️怎么算出最小θ值？通过计算代价函数。

代价函数

定义：代价函数是用于评价线性回归模型性能的函数，它计算的是模型预测值与实际值之间的误差。在线性回归中，常用的代价函数是均方误差（Mean Squared Error, MSE），其公式为：

其中，m 是样本数量，hθ​(x(i)) 是模型对第 i 个样本的预测值，y(i) 是第 i 个样本的实际值，θ 是模型参数。

作用：代价函数的主要作用是量化模型预测值与实际值之间的差异。通过最小化代价函数，可以找到最佳的模型参数 θ，使得模型对未知数据的预测能力最强。

⭐️怎么最小化代价函数找到最佳θ？两个方法：正规方程法？和梯度下降法。

正规化法（正规方程法）求解线性回归模型

正规方程法求线性回归模型的优缺点

优点：一次计算即可得到参数值，算法简单，特征向量个数少于10000时运算速度快，准确性高；
缺点：因为有求逆矩阵步骤，所以算法对特征维度敏感，算法复杂度为 o(n3)，复杂度高，当特征纬度超过 10000 时，运算速度急剧下降0，运算速度慢。

梯度下降法求解线性回归模型

方法：通过减小J(θ₀,θ₁)，改变θ₀,θ₁，直到J(θ₀,θ₁)达到最小。

提高梯度下降法效率，减少迭代次数的小技巧：归一化

目标：将样本每个特征向量的取值归一化到大致(-1，1)之间
方法：调用公式，其中u_i表示第i个特征向量在所有样本中的平均值，S_i表示第i个特征向量在所有样本中所取的最大值减去最小值。

梯度下降法求线性回归模型的优缺点

优点：

• 适用于大规模数据集：梯度下降法在处理大规模数据集时表现良好，因为它不需要一次性计算整个数据集的逆矩阵。
• 灵活性高：梯度下降法可以通过调整学习率等参数来控制算法的收敛速度和稳定性。

缺点：

• 需要迭代：梯度下降法需要多次迭代才能收敛到最优解，这可能导致算法运行时间较长。
• 依赖于初始值和学习率：梯度下降法的收敛速度和结果可能受到初始值和学习率的影响。如果初始值选择不当或学习率过大/过小，可能导致算法无法收敛或收敛到局部最优解。

⭐️总结

逻辑回归

线性回归与逻辑回归的异同

💩

KNN

KNN(K近邻算法)

近朱者赤,近墨者黑
K近邻是监督学习，训练集的类别事先标记好。而K均值聚类是无监督学习，初始训练样本同样没有类别。

KNN算法流程

KNN算法是一种基于实例的学习方法，用于分类和回归任务。在分类任务中，KNN算法通过找到与给定测试样本最近的K个训练样本（即邻居），然后根据这些邻居的类别来预测测试样本的类别。具体步骤如下：

1. 选择K值：K是一个正整数，表示考虑的最近邻居的数量。K值的选择对算法的性能有重要影响。
2. 计算距离：对于测试样本，计算它与训练集中每个样本的距离。常用的距离度量包括欧氏距离、曼哈顿距离等。
3. 找到最近的K个邻居：根据计算的距离，选择距离最近的K个训练样本作为邻居。
4. 投票决定类别：在K个邻居中，出现次数最多的类别即为测试样本的预测类别。

KNN算法优缺点

优点：

1. 简单，易于理解，易于实现，无需估计参数，无需训练；
2. 适合对稀有事件进行分类；
3. 特别适合于多分类问题

缺点：

1. 懒惰算法，对测试样本分类时的计算量大，内存开销大，评分慢
2. 当样本不平衡时，如一个类的样本容量很大，而其他类样本容量很小时，有可能导致当输入一个新样本时，该样本的K个邻居中大容量类的样本占多数
3. 可解释性较差，无法给出决策树那样的规则

KNN算法的改进策略

针对以上算法的不足，算法的改进方向主要分成了分类效率和分类效果两方面。
1.分类效率：事先对样本属性进行约简，删除对分类结果影响较小的属性，快速的得出待分类样本的类别。该算法比较适用于样本容量比较大的类域的自动分类，而那些样本容量较小的类域采用这种算法比较容易产生误分。
2.分类效果：采用权值的方法（和该样本距离小的邻居权值大）来改进。

K-Means

K-Means(K均值聚类算法)

K近邻是监督学习，训练集的类别事先标记好。而K均值聚类是无监督学习，初始训练样本同样没有类别。
强推！公认最强的人工智能入门课程！大佬66集精讲！20小时带你吃透AI必备知识点！ p17 17. Kmeans-KNN-Meanshift

K-Means算法流程

ppt：
（1） 从 n个数据样本所在范围中随机生成k 个样本作为初始聚类中心；
（2） 根据每个聚类对象的均值（中心对象），计算每个对象与这些中心对象的距离；并根据最小距离重新对相应对象进行划分；
（3） 重新计算每个（有变化）聚类的均值（中心对象）；
（4） 循环（2）到（3）直到每个聚类不再发生变化为止。
⭐️图示：

K-Means算法优缺点

优点：
1、原理简单，实现容易，收敛速度快
2、参数少，方便使用
缺点：
1、必须设置簇的数量
2、随机选择初始聚类中心，结果可能缺乏一致性

搜索方法思想及算法实现步骤

1.概述

🍔搜索分类
根据是否使用启发式信息分为：

• 盲目搜索
• 启发式搜索

按表示方式分为：

• 状态空间搜索：用状态空间法来求解问题所进行的搜索
• 与或树搜索：用问题规约方法来求解问题时所进行的搜索

🍔搜索策略评价标准:

• 完备性：如果存在一个解答，该策略是否保证能够找到?
• 时间复杂性：需要多长时间可以找到解答?
• 空间复杂性：执行搜索需要多少存储空间?
• 最优性：如果存在不同的几个解答，该策略是否可以发现最高质量的解答?

🍔搜索控制策略：

不可撤回的控制策略：（例：八数码问题）
试探性控制策略：回溯型（例：四皇后问题）、图搜索

2.盲目搜索方法

有界深度优先搜索思想

迭代加深搜索思想

宽度优先搜索需要指数数量的空间，深度优先搜索的空间复杂度和最大搜索深度呈线性关系。
迭代加深搜索对一棵深度受控的树采用深度优先的搜索。它结合了宽度优先和深度优先搜索的优点。和宽度优先搜索一样，它是最优的，也是完备的。但对空间要求和深度优先搜索一样是适中的。

3.启发式搜索⭐️

3.1 启发式搜索思想

⭐️启发式搜索思想：在选择节点时能充分利用与问题有关的特征信息，估计出节点的重要性，在搜索时选择重要性较高的节点，以便求得最优解。

🍔评估函数

⭐️评估函数就是利用h(x)评估代价，如果代价过大就不用继续往下搜索了。
3.3评估函数

3.2 启发式搜索分类

启发式搜索用于两种不同类型的问题：

• 前向推理一般用于状态空间的搜索。在前向推理中，推理是从预选定义的初始状态出发向目标状态方向执行。
• 反向推理一般用于问题规约中。在反向推理中，推理是从给定的目标状态向初始状态执行。

3.3 评估函数

（以八数码问题为例）

3.4 图通用搜索算法

3.6 A算法⭐️

估计函数：

f(n)=g(n)+h(n)

其中g(n)表示从S₀到n点费用的估计，因为n为当前节点，搜索已达到n点，所以g(n)可计算出。h(n)表示从n到S_g接近程度的估计，因为尚未找到解路径，所以h(n)仅仅是估计值。

在八数码难题中:
g(n)=d(n)深度，定义为n在搜索树中的深度h(n)定义为不在目标状态中相应位置的数码个数。

3.7 A*算法⭐️

🍔
评估函数f*

f*(n) = g*(n) + h*(n)

• g*(n)为起始节点到节点n的最短路径的代价。
• h*(n)是从n到目标节点的最短路径的代价。
• 这样f*(n)就是从起始节点出发通过节点n到达目标节点的最佳路径的总代价的估值。
• 把估价函数f(n)和f*(n)相比较，g(n)是对g*(n)的估价。h(n)是对h*(n)的估价。

🍔

• 在这两个估价中，尽管g(n)容易计算，但它不一定就是从起始节点S,到节点n的真正的最短路径的代价，很可能从初始节点S,到节点n的真正最短路径还没有找到，所以一般都有：g(n)≥g*(n)。
• 有了g*(n)和h*(n)的定义，如果对最好优先的启发式搜索算法中的g(n)和h(n)做如下的限制:
  (1)g(n)是对g*(n)估计，且g (n)>0
  (2)h(n)是h*(n)的下界，即对任意节点n均有：h(n)≤h*(n)。

称这样得到的算法为A*算法。

⭐️带*号的是准确值？不带*的是估计值。满足上面两个条件的是A*算法。

3.8 迭代加深A*搜索算法(IDA*)

4.1 问题规约⭐️

📖考点：怎么算路径

问题规约的概念：在问题求解过程中,将一个大的问题变换成若干子问题,子问题又可分解成更小的子问题，这样一直分解到可以直接求解为止，全部子问题的解即为大的问题的解,这样的过程称为问题的规约。并称大的问题为初始问题，可直接求解的问题为本原问题。

⭐️类似于分治算法

归约方法求解问题三大要素
1.初试问题的描述。
2.一组将问题变换成子问题的变换规则.
3.一组本原问题的描述。

4.2 与或图表示法⭐️

父节点、子(后继)节点、弧线
起始节点:对于于原始问题描述的节点
终叶节点:对应于本原问题的节点
或节点:只要解决某个问题就可解决其父辈问题的节点集合，如(M，N，H)。
与节点:只有解决所有子问题，才能解决其父辈问题的节点集合，如(B，C)和(D，E，F)。各个节点之间用一段小圆弧连接标记。
K连接弧，表示问题由某个操作算子作用后产生K个问题，用圆弧表示。
与或图:由与节点、或节点及K连接弧组成的结构图

与或图搜索费用计算

假币问题

练习：有12枚硬币，凡轻于或重于真币者即为假币(只有一枚假币)，要设计一个搜索算法来识别假币并指出它是轻于还是重于真币，且利用天平的次数不多于3次。

这个问题可以通过一种称为“三分法”的策略来解决。以下是详细的步骤

1.将硬币分成三组，每组四枚，分别表示为：G1=(1,2,3,4)，G2=(5,6,7,8)，G3=(9,10,11,12)。
2.在第一次称量时比较G1和G2，它们或者平衡或者一组更重些，下面分别考虑这两种情况：
  1.如果G1和G2平衡，那么假币必定在G3中，即G1和G2中的所有硬币都是真的。这样，在第二次称量中，就可以比较任意三枚真币（比如1,2和3）和G3中的三枚硬币：（1,2,3）和（9,10,11）
    1.硬币平衡。这表明假币为12，因为它是G3中唯一在第二次称量中未出现的硬币，再进行第三次称量（比如1与12）就可以确知假币比其他硬币重还是轻。
    2硬币不平衡。这表明假币是9、10、11中的某一个，并且还可以知道假币是轻些还是重些。如果（1、2、3）比（9、10、11）重些，那么假币就轻些，反之亦然。再进行第三次称量（比如9与10）就可以确定是哪一枚是赝品。如果9和10平衡，那么假币是11，如果不平衡，那么根据前面已知的假币是轻些还是重些的信息就可以知道它们中的哪一枚是假币。
  2.如果G1和G2不平衡，那么我们可以知道，假币在G1或G2中。把G2中的一枚硬币（比如5）移到天平的左边，在天平的右边加一枚真币（比如12）。这样第二次称量就是（1、2和5）与（3、4、12）。
    1.假设在第一次称量中，硬币（1、2、3、4）比（5、6、7、8）重些，那么在第二次称量中有三种可能的结果：
    2.硬币（1、2、5）重些。这表明硬币3、4和5是真的，因为我们改变了它们在天平中的位置，但称量的结果仍然不变（即左边重些）。由于硬币12是真的，那么假币就是1或2，并且假币重些。再进行第三次称量（1与2）就可以马上确定哪枚是假币。
    3.硬币（3、4、12）重些。由于两车称量的结果发生了改变（也就是第一次称量天平左边重些，而现在右边重些），那么假币一定是从天平的一端移到了另一端。因此，或者硬币3或4是假的，并且重些。或者硬币5是假的，且轻些。这样再进行第三次称量（3与4）就可以确定出赝品。如果平衡，则假币是5，否则，较重的那个是假币。
    4.硬币（1、2、5）和（3、4、12）平衡。这表明假币必定不包含在第二次称量中，而必为6、7或8中的一枚。同时，从第一次称量的结果可知假币较轻。这样，再进行第三次称量（比如6与7）就可以确定出赝品。
通过上述步骤，你可以有效地在三次称量内找到那枚假币，并确定它比真币轻还是重。
⭐️（绿色为鉴定为真币，红色为问题出现在它身上）

5 博弈概述

5.1 博弈概述

博弈可分为零和博弈和非零和博弈：
二人博弈、二人零和、全信息、非偶然博弈：博弈双方的利益是完全对立的。
非零和博弈：囚徒困境。

5.2 博弈示例

假设有七枚钱币，任一选手只能将已分好的一堆钱币分成两堆个数不等的钱币，两位选手轮流进行，直到每一堆都只有一个或两个钱币，不能再分为止，哪个选手遇到不能再分的情况，则为输。


⭐️粗箭头是MAX获胜的路径。

⭐️轮到MAX走时，只能选择一条路径，所以方案对MAX来说是“或”的关系；轮到MIN走时，在MAX眼里，MIN可能会走很多条路径，所以方案对MAX来说是“与”的关系。

5.3 博弈树

5.4 极大极小值搜索过程⭐️

5.5 极大极小值搜索过程实例

极大极小过程计算决策树节点

⭐️0表示对MAX来说是输的，1表示对MAX来说是赢的。

5.6 α-β剪枝算法⭐️

Alpha-Beta剪枝算法(极大极小算法-人工智能)

Alpha-Beta剪枝算法（人工智能）

⭐️
α-β剪枝算法：
0. α初值+∞，β初值-∞；
1.MAX层只改变α，取（自己，下一层α，下一层β）的最大；
MIN层只改变β，取（自己，下一层α，下一层β）的最小；
2.α和β值的传递：先左子树，后右子树；
3.触发剪枝：α＞β。

高级搜索技术⭐️

📖考点：
爬山、模拟退火、遗传算法的思想
算法流程、步骤
伪代码
（可能会在简答题）

1 爬山法搜索

爬山法搜索——局部搜索(贪婪局部搜索)

登高——一直向值增加的方向持续移动，将会在到达一个“峰顶”时终止，并且在相邻状态中没有比它更高的值。

这个算法不维护搜索树，因此当前节点的数据结构只需要记录当前状态和它的目标函数值。爬山法不会预测与当前状态不直接相邻的那些状态的值。
⭐️没有搜索树。

八皇后问题


⭐️先全部放上去，再计算彼此攻击的皇后对数量（每次只移动一个皇后，从而计算了8×8=64种情况的彼此攻击皇后对数量）；然后每一列的皇后再移动到数量最少的格子上，得到图b。
但图b是一种局部极大值的情况，不管哪一列的皇后在它的列上如何移动，情况都会比原来的差。

爬山法经常会遇到的问题

（1）局部极大值
局部极大值是一个比它的每个邻居状态都高的峰顶
但是比全局最大值要低。
爬山法算法到达局部极大值附近就会被拉向峰顶，然后被卡在局部极大值处无处可走。

（2）山脊
山脊造成的是一系列的局部极大值，贪婪算法处理这种情况是很难的。
（3）高原
状态空间地形图上评价函数值平坦的一块区域。高原是在它可能是一块平的局部极大值，不存在上山的出路，或者是一个山肩，从山肩还有可能取得进展爬山法搜索可能无法找到离开高原的道路。

针对爬山法的不足，有许多变化的形式。

• 随机爬山法，它在上山移动中随机地选择下一步;选择的概率随着上山移动的陡峭程度而变化。这种算法通常比最陡上升算法的收敛速度慢不少，但是在某些状态空间地形图上能找到更好的解。
• 首选爬山法，它在实现随机爬山法的基础上，采用的方式是随机地生成后继节点直到生成一个优于当前节点的后继。这个算法在有很多后继节点的情况下有很好的效果。
• 随机重新开始的爬山法，它通过随机生成的初始状态来进行一系列的爬山法搜索找到目标时停止搜索。这个算法是完备的概率接近于1，原因是它最终会生成一个目标状态作为初始状态。
  ⭐️随机爬山法可能往下走，往不陡的地方走等；首选爬山法往不是最陡的地方走；随机重新开始爬山法卡住的时候重新生成起点开始爬，可能生成的起点就是终点。

2 模拟退火搜索

模拟退火搜索的思想

将温度T当作控制参数，目标函数值f视为内能E，而固体在某温度T时的一个状态对应一个解x;，然后算法试图随着控制参数T的降低，使目标函数f(内能E)也逐渐降低，直至趋于全局最小值(退火中低温时的最低能量状态)，就像金属退火过程一样。

模拟退火搜索流程⭐️

💩

以最小化问题为例，模拟退火算法的流程如下：
（1）初始化：初始温度T0，初始解X0，每个温度T下的迭代次数L；
（2）对k = 1，… ，L做（3）——（6）步；
（3）产生新解X’；
（4）计算增量f(X’) - f(X)，其中f(X) 这里可以理解为优化问题的目标函数；
（5）当Δf(x) < 0时，直接接受X’作为新解，否则以概率exp（-Δf（x）/T）接收机X’作为新的当前解；
（6）如果满足终止条件，则输出当前解为最优解，结束程序；
（7）T逐渐减小，且T→0，然后转（2）。

模拟退火搜索优点

• 类比优化搜索过程，本模拟退火搜索在一定温度下，搜索从一个状态随机地变化到另一个状态，随着温度的不断降低，直至最低温度，搜索过程以接近1的概率停留在最优解。
• 模拟退火算法是对爬山算法的优化改进，爬山算法在搜索过程中只接受更优的邻近解直至搜索不到更优解为止，算法简单易实现，但是却极有可能停止在局部最优解。（模拟退火算法拥有跳出局部最优解的潜力。）

3.遗传算法

遗传算法的思想

遗传算法将“优胜劣汰，适者生存”的生物进化原理引入优化参数形成的编码串群体中，按所选择的适应度函数并通过遗传中的复制、交叉及变异对个体进行筛选，适应度高的个体被保留下来，组成新的群体，新的群体既继承了上一代的信息，又优于上一代。这样周而复始，群体中个体适应度不断提高，直到满足一定的条件。遗传算法的算法简单，可并行处理，并能到全局最优解。

遗传算法示例

（1）编码
（2）产生初始种群

（3）计算适应度

遗传算法伪代码⭐️

1. 初始化：
   a. 生成一个初始种群 P(0)，种群大小为 N。
   b. 设置遗传算法的参数：交叉率pc、变异率pm，以及迭代次数。
2. 评估：
   a. 计算种群 P(0) 中每个个体的适应度。
3. 迭代：
   a. 对于每一代 t = 1, 2, …：
   i. 选择：根据适应度从当前种群 Pt 中选择个体，以形成新的种群 Pt+1。
   ii. 交叉：以概率 pc 随机配对 Pt+1 中的个体，并产生后代。
   iii. 变异：以概率 pm 随机改变 Pt+1 中个体的某些基因。
   iv. 评估 Pt+1 中每个个体的适应度。
   v. 如果满足终止条件（如达到最大代数或找到满意的解），则停止迭代。
   vi. 用 Pt+1 替换 Pt，即 Pt = Pt+1。
4. 输出：
   a. 返回适应度最高的个体作为问题的解。

遗传算法特点

• 本质并行性。遗传算法按并行方式搜索一个种群数目的点，而不是单点。
• 不需要求导或其他辅助知识，而只需要影响搜索方向的目标函数和相应的适应度函数。
• 强调概率转换规则，而不是确定的转换规则。
• 可以更加直接地应用。
• 对给定问题，可以产生许多的潜在解，最终选择可以由使用者确定(在某些特殊情况下，如多目标优化问题不止一个解存在，有一组pareto最优解。这种遗传算法对于确认可替代解集而言是特别合适的)。

遗传算法的应用情况
函数优化、组合优化、生产调度问题、自动控制、机器人智能控制 、图像处理和模式识别。

3.知识表示基本概念

知识表示概述⭐️

• 知识表示就是研究用机器表示上述这些知识的可行性、有效性的一般方法，可以看作是将知识符号化并输入到计算机的过程和方法。
• 知识表示 = 数据结构 + 处理机制
• 知识表示的观点：陈述性知识表示，过程性知识表示

AI对知识表示的要求

• 表示能力正确、有效
• 可理解性好
• 便于知识的获取
• 便于搜索
• 便于推理

产生式系统

采用产生式系统的理由

• 用产生式系统结构求解问题的过程和人类求解问题时的思维过程很相象。
• 可以把产生式系统作为 A 系统的基本结构单元或基本模式看待。

产生式系统的要素

• 一个综合数据库：用来表述问题状态或有关事实，即它含有所求解问题的信息，其中有些部分可以是不变的，有些部分则可能只与当前问题的解有关。
• 一组产生式规则：表示为if…then…一条产生式规则满足了应用的先决条件之后，就可对综合数据库进行操作，使其发生变化。
• 一个控制系统：控制系统或策略是规则的解释程序。它规定了如何选择一条可应用的规则对数据库进行操作 产生式系统可用来模拟任一可计算过程

产生式系统的优点

• 适合于模拟强数据驱动特点的智能行为。当一些新的数据输入时，系统的行为就要改变。
• 易于添加新规则去适应新的情况，而不会破坏系统的其他部分。

产生式系统的控制策略
控制策略可分为两类：
1.不可撤回方式；
2.试探性方式：回溯方式、图搜索方式。

问题求解技术主要是两个方面：问题的表示、求解的方法

4.状态空间的相关概念、表示方法及应用

状态空间的相关概念

状态空间：是一个表示该问题全部可能状态及其关系的集合。可把状态空间记为三元组：（S(初始状态)，F(算子)，G(目标状态)）

状态空间表示方法⭐️

• 状态：表示问题解法中每一步问题状况的数据结构
• 操作符或算子：把问题从一种状态变换为另一种状态的手段，可能是走步(下棋)、过程、规则、数学算子、运算符号或逻辑运算符等。
• 状态空间：是一个表示该问题全部可能状态及其关系的集合。可把状态空间记为三元组：S(初始状态)，F(算子)，G(目标状态)

🍔状态空间法基本思想
(1)将问题中的已知条件看成状态空间中初始状态;将问题中要求的目标看成状态空间中目标状态;将问题中其它可能的情况看成状态空间的任一状态。
(2)设法在状态空间寻找一条路径，由初始状态出发，能够沿着这条路径达到目标状态

🍔状态空间基本算法:

• 根据问题，定义出相应的状态空间，确定出状态的一般表示，它含有相关对象的各种可能的排列。这里仅仅是定义这个空间的状态，而不必枚举该状态空间的所有状态，但由此可以得出问题的初始状态、目标状态，并能够表示出所有其它状态。
• 规定一组操作(算子)，能够使状态从一个状态变为另
• 一个状态。 决定一种搜索策略，使得能够从初始状态出发，沿某个路径达到目标状态。

🍔状态空间图

• 状态空间图是一个有向图
• 结点表示问题的各种状态
• 弧表示操作符或算子，它可把一种状态导向另一状态

状态空间法，就是从状态空间图中搜索出一条解路径的过程。

状态空间的应用

5.图搜索策略及应用

图搜索策略

图搜索应用

3.6 A算法（跳转往后都是图搜索的应用）
（应用的算法表示 详见ppt 和 配套视频讲解）

6.问题规约概念、与或图搜索、博弈树搜索与剪枝

问题规约概念

4.1 问题规约

与或图搜索

4.2 与或图表示法

博弈树搜索

5 博弈概述

剪枝

5.6 α-β剪枝算法

7.决策树、贝叶斯决策算法及其应用

决策树

1.1 决策树概述

1.2 决策树算法思想

策略：分而治之。
自根至叶的递归过程
在每个中间结点寻找一个“划分"属性

三种停止条件：
(1)当前结点包含的样本全属于同一类别，无需划分
(2)当前属性集为空，或是所有样本在所有属性上取值相同，无法划分
(3)当前结点包含的样本集合为空，不能划分

2.1 ID3算法⭐️

12-1 信息熵与决策树（信息熵）

信息熵

⭐️信息熵表示集合混乱程度，信息熵越小，集合越纯。

信息增益


⭐️信息增益就是集合分割之后的纯度增长率，也是混乱度下降量，用来看集合分的好不好：数值越大，分的越好。

🌰例子
（先计算好瓜坏瓜所占样本集合比例，再计算样本集合 信息熵）

ID3算法缺点

• ID3 没有剪枝策略，容易过拟合
• 信息增益准则对可取值数目较多的特征有所偏好，类似“编号”的特征其信息增益接近于 1;
• 只能用于处理离散分布的特征
• 没有考虑缺失值。

3.1 预剪枝和后剪枝⭐️

贝叶斯决策算法⭐️

贝叶斯公式

🌰例子

拉普拉斯修正

📖练习
数据集

8.神经网络与深度学习基本概念

神经网络基本概念

神经网络是一类仿生算法，通过连接不同的节点（即神经元），实现信息的传递和处理。每个神经元都能接收多个输入信号，经过加权求和后通过激活函数产生输出。

激活函数

感知机

神经网络分类

• 前馈型
• 反馈性
• 随机型
• 自组织竞争型

NN(neural network)的性质取决于

• 网络的拓扑结构
• 网络的权值、工作规则
• 随着网络结构和功能的不同，网络权值的学习算法也不同

NN的学习问题就是网络的权值调整问题
神经网络的连接权值的确定一般有两种方式。

• 通过设计计算确定，即所谓死记式学习；
• 网络按一定的规则通过学习(训练)得到的。

深度学习基本概念

深度学习是一种使用多层神经网络模型的方法，以模仿人脑在多个抽象层次上处理数据的方式。它可以自动学习和提取数据的特征，从而在各种任务中取得卓越的表现。

卷积神经网络

卷积的主要作用是抽取特征，使网络具有一定转移不变性，也有一定降维作用。在图像处理中，卷积需要三个参数:一个输入图像;将应用到图像上的卷积核(kernel)；存储卷积后的输出结果的输出图像。

• 卷积层：抽取特征，有一定降维作用
• 池化层：通过池化来降低卷积层输出的特征向量，起到降维作用，同时改善结果(不易出现过拟合）。分为最大池化或平均池化
• Dropout层：以一定的概率随机地关闭当前层中神经元激活值
• softmax 层：输出预测分类值

深度学习常用库

• Numpy（计算）：处理大型多维数组和矩阵，广泛的高级数学函数和实现的方法集合，可以使用这些对象执行各种操作。
• Pandas：是基于NumPy 的一种工具，该工具是为解决数据分析任务而创建的，提供了高级数据结构和各种分析工具。
• Matplotlib（绘图）：是一个用于创建二维图表和图形的低级库，同时它也提供了一部分 3D 绘图接口。
• Seaborn：本质上是基于matplotlib 库的更高级别的 API。
• SciPy（计算）：基于NumPy，该软件包包含有助于解决线性代数，概率论，积分计算和更多任务的工具

学习通题目

第七章 知识表示与推理

选择题

（机器学习知识点）
1【单选题】过拟合是指（）
A、在训练集表现非常好，在测试集上表现也非常好
B、在训练集表现非常好，但在测试集上表现很差
C、在训练集表现非常差，但在测试集上表现也很差
D、在训练集表现非常差，但在测试集上表现非常好

⭐️模型“过度学习”了训练数据，把数据中的噪声也学习了进来，导致它失去了对未来数据的预测能力。

2【单选题】欠拟合是指（）
A、在训练集表现非常好，但是在测试集上表现很差
B、在训练集表现非常好，在测试集上表现也很好
C、在训练集表现非常差，在测试集上表现也很差
D、在训练集表现非常差，但是在测试集上表现非常好

⭐️欠拟合指的是模型在训练过程中未能捕捉到数据集中的有效规律或模式，导致模型过于简单，无法正确预测结果。

课后巩固

设有三根头朝上的火柴，允许一次倒置两根相邻的火柴，问能否出现三根火柴的头都朝下的状态？画出状态空间图（标明状态、操作），并说明是否有解，如果有解给出解。

人工智能：状态空间图（超详细经典例题讲解，通过例题教会你如何解决状态空间图问题）的第2题。

第八章搜索技术

选择题

（知识表示知识点）
1【单选题】（ ）可看成是一组描述事物的约定，把人类知识表示成机器能处理的数据结构
A、知识获取
B、知识存储
C、知识表示
D、知识利用

2【单选题】知识表示起源于人工智能的（ ）
A、行为主义
B、连接主义
C、符号主义
D、表示主义

课后巩固

剪枝：下图为一使用极小极大搜索方法对某个对弈问题的求解过程，请使用a-b剪枝算法对其进行剪枝，以便加速求解过程。

第九章 高级搜索技术

（搜索技术知识点）
（考试不考判断题）
1【判断题】若任一极小值层节点的β值小于或等于它任一先辈极大值层节点的α值，即α（先辈层）≥β（后继层），则可中止该极小值层中这个节点以下的搜索。该节点最终的倒推值就确定为这个β值。（对）

课后巩固

请用爬山法来解决TSP问题，并比较爬山法的不同变种的效果，说明有什么优势，存在什么缺点。

随机爬山法
优势：避免局部最优陷阱；适应不规则地形。
缺点：收敛速度慢；结果不稳定。
首选爬山法
优势：避免局部最优陷阱，高效利用后继节点。
缺点：生成后继结点具有盲目性；不保证全局最优。
随机重新开始爬山法
优势：完备性高，近乎 1 的概率找到目标状态；每次从全新的随机初始状态开始爬山搜索，降低错过全局最优解的可能性。
缺点：计算成本大；计算冗余，造成计算资源浪费。

第十章 决策树

选择题

（高级搜索技术知识点）
1【单选题】遗传算法一般包含下面几个步骤：1、交叉，2、产生初始种群，3、变异，4、选择，5、计算适应度，6、编码，请问下面哪一个顺序是正确的
A、123456
B、654321
C、625413
D、624513

⭐️编码（6）：这是遗传算法的起始步骤，把实际问题的解空间映射到遗传算法能够处理的编码空间。
产生初始种群（2）：在完成编码后，随机生成一组初始个体，这些个体组成了初始种群，作为算法迭代的起点。
计算适应度（5）：依据给定的目标函数，对种群中的每个个体计算适应度值，以此衡量个体对环境的适应程度，适应度高的个体更有可能被保留并参与后续繁殖。
选择（4）：按照适应度值从种群里挑选个体，适应度高的个体有更大机会被选中，目的是让优良基因有更高概率传递下去。
交叉（1）：对选出来的部分个体执行交叉操作，交换它们的部分基因，模拟生物遗传中的基因重组，产生新的个体，拓展搜索空间。
变异（3）：以较小概率对个体的某些基因进行变异，引入全新的基因信息，避免算法过早收敛到局部最优解，维持种群的多样性。

2【单选题】模拟退火算法中，下面哪一个是其能不陷入局部极小值，最终找到最做优解的原因。
A、选择当前最好的解作为新解
B、以一定的概率选择新解
C、随机选取一个新解
D、都不正确

课后巩固🌟

贷款审批：如下为是否批准客户贷款申请的部分数据：

（四）统计学习方法 | 决策树
（例题有相似的地方，分析得不错，可以借鉴一下）

第十一章 朴素贝叶斯分类

选择题

（决策树知识点）
1【单选题】下面哪一项不是决策树对属性进行划分所使用的准则
A、信息增益
B、信息率
C、基尼指数
D、增益率

⭐️信息增益：是决策树 ID3 算法划分属性时所采用的准则。
基尼指数：CART算法使用基尼指数来选择划分属性。
增益率：C4.5 算法为了克服信息增益偏向选择取值较多属性的问题，采用增益率来对属性进行划分。

1【填空题】决策树剪枝算法主要有（）和（）两种
预剪枝 后剪枝

预剪枝：在决策树生成过程中，对每个节点在划分之前先进行估计，若当前节点的划分不能带来决策树泛化性能的提升，则停止划分，并将当前节点标记为叶节点。
后剪枝：先从训练集中生成一课完整的决策树，然后自底向上对非叶子节点进行考察，若将该节点对应的子树替换为叶子结点能带来决策树泛化性能的提升，则将该子树替换为叶节点。

课后巩固

?

第十二章 深度学习

（贝叶斯分类器知识点）
（填空题）

这种估计后验概率的策略称为（），



这种估计后验概率的策略称为（）。
第一空： 判别式模型
第二空： 生成式模型

课后巩固

卷积计算的具体方法和演示如下
⭐️

2024年期末考内容

⭐️趁我刚考完给你们总结一下，上哪找这么好心的学长，还不快给我把关注点点。

算法解答题

1.K-Means算法思路
2.状态空间表示方法
（考了学习通的题目）
3.A*算法
4.与或图搜索

综合题

1.极大极小值搜索
α-β剪枝
⭐️搜索树要自己画，再进行剪枝

2.ID3算法
⭐️跟学习通的题目差不多，能做对学习通题目考试就没问题。

🍊考了三年试，第一次碰到打铃收卷时教室里还是满人的，祝你们好运吧！
🍊完结撒花~~