机器学习试题

精品文档 2010 年春硕士研究生 机器学习 试题 下列各题每个大题 10 分，共 8 道大题，卷面总分 80 分 注意：在给出算法时，非标准（自己设计的）部分应给出说明。特别是自己设置的参数及变 量的意义要说明。 1. 下面是一个例子集。其中，三个正例，一个反例。 “P”为正例、 “N”为反例。这些例子 是关于汽车的。例子有 4 个属性，分别是“产地” 、 “生产商” 、 “颜色” 、 “年代” 。 产地 Japan Japan USA Japan 生产商 Honda Honda Chrysler Honda 颜色 Blue Blue Red Red 年代 1980 1990 1980 1980 类别 P P N P 其中： “产地”的值域为(Japan,USA)、 “生产商”的值域为(Honda, Chrysler)、 “颜色”的 值域为(Blue,Red)、 “年代”的值域为(1980,1990)。这里规定“假设”的形式为4 个属性值 约束的合取；每个约束可以为：一个特定值(比如 Japan、Blue 等)、?（表示接受任意值） 和（表示拒绝所有值） 。例如，下面假设： （Japan, ?, Red, ?） 表示日本生产的、红色的汽车。 1） 根据上述提供的训练样例和假设表示，手动执行候选消除算法。特别是要写出处理 了每一个训练样例后变型空间的特殊和一般边界； 2） 列出最后形成的变型空间中的所有假设。 2. 写出 ID3 算法。(要求：除标准ID3 算法外，要加入“未知属性值”和“过适合”两种情 况的处理)。 3. 给出一个求最小属性子集的算法。 4. 给定训练例子集如下表。依据给定的训练例子，使用朴素贝叶斯分类器进行分类。 给定类别未知例子，计算这个例子的类别。 （计算类别时要 先列出式子，然后再代入具体的数） 。 例子号 1 2 3 4 5 6 7 8 高度 矮 高 高 高 矮 高 高 矮 头发 淡黄 淡黄 红 淡黄 黑 黑 黑 红 眼睛 兰 兰 兰 褐 兰 兰 褐 褐 类别 + + + ― ― ― ― ― ˆ(x)  w  w x   w x 及误差定义 E  1 5. 给定线性函数f 011nn ˆ(x)) ( f (x)  f  2 xD 2 。1欢迎下载 精品文档 其中，xi是例子 x 的第 i 个属性值， f(x)是目标函数， D 是训练例子集合。 请给出一个算法， ˆ(x) 逼近目标函数 f(x)（本题要求写出算法的这个算法能求出一组 Wi 值，使得线性函数f 步骤，算法步骤的详细程度要符合书中算法的标准） 。 6. 给定例子集（如下表） ，要求：1）用平面图直观画出例子的分布； 2）给出一种规则好坏 的评判标准；3)写出概念聚类算法。 例子 e1 e2 e3 e4 e5 e6 e7 e8 X1 0 0 0 1 1 2 2 2 X2 A B C A C A B B X3 0 0 1 0 1 1 0 1 X4 1 0 2 2 1 0 1 2 7. 简述题 1) 简述“机器发现”的三个定律； 2) KBANN、EBNN、FOCL 是分析学习和归纳学习结合的三个算法。简述这三个算法与单纯的 归纳学习方法相比，分别有什么区别或优点。 8. 关于模式定理 1) 分析“选择步”对群体遗传的影响：令m(s,t)是群体中模式 s 在时间 t（或第 t 代）的 实例数量，f(h)是个体 h 的适应度，f (t)是时间 t（或第 t 代）群体中所有个体的平均 ˆ(s,t)是时间 t（或第 t 代）群体中模式 s 的实例 适应度，n 为群体中个体的总数量，u 的平均适应度。在“选择步”中，每个个体被选中的概率为 Pr(h)（Pr(h)的计算见公式 (1)） ，如果共进行了n 次独立选择，请给出在第(t+1)代（即下一代）的群体中，模式s 的实例存在的期望数量 E[m(s,t+1)]（要求给出分析过程） 。 Pr(h)  f (h)  n i1 f (h i ) (1) 2) 分析“变异步”对群体遗传的影响：令m(s,t)是群体中模式 s 在时间 t（或第 t 代）的 实例数量。设在模式s 中有 R(s)个确定位，变异操作以概率Pm 选择一位并改变这位上 的值。如果只考虑变异步对群体遗传的影响，请给出在第(t+1)代（即下一代）的群体 中，模式 s 的实例存在的期望数量 E[m(s,t+1)]（要求给出分析过程） 。 。2欢迎下载