FIND-S 算法可能是最简单的机器学习算法之一。然而，我找不到太多的例子…只有那些在机器学习中总是使用的标准的“晴天、雨天、打球”例子。请问有人能帮我解决这个问题吗（这是一个过去的机器学习考试题）。

假设的形式为 a <= x <= b, c <= y <= d，其中 x 和 y 是 x,y 平面中的点，而 c 和 d 是任何整数。 基本上，这些假设定义了 x,y 空间中的矩形。

以下是训练示例，其中 - 是负例，+ 是正例，这些对是 x,y 坐标：

 + 4, 4
 + 5, 3 
 + 6, 5 
 - 1, 3 
 - 2, 6 
 - 5, 1 
 - 5, 8 
 - 9, 4

我只想将 FIND-S 应用到这个例子中！它一定很简单！一些提示或解决方案将会非常棒。

谢谢。

回答：

Find-S 寻找最严格的（即最“具体的”）假设，使其符合所有正例（负例被忽略）。

在你的例子中，有一个明显的图形解释：“找到包含所有“+”坐标的最小矩形”……

…这将是 a=4, b=6, c=3, d=5。

用于执行此操作的算法如下所示：

定义一个假设矩形 h[a,b,c,d]，并将其初始化为 [-,-,-,-]
对于每个 + 示例 e {
    if e 不在 h 中 {
        扩大 h 以使其足够大以容纳 e（和所有先前的 e）
    } else { 什么也不做：h 已经包含 e }
}

如果我们使用你的训练集逐步执行此操作，我们会得到：

 0. h = [-,-,-,-] // 初始值
 1. h = [4,4,4,4] // (4,4) 不在 h 中：更改 h，使其仅包含 (4,4)
 2. h = [4,5,3,4] // (5,3) 不在 h 中，因此扩大 h 以适应 (4,4) 和 (5,3)
 3. h = [4,6,3,5] // (6,5) 不在 h 中，因此再次扩大
 4. // 没有剩余的正例，所以我们完成了。