artificial-intelligence - FIND-S 算法 - 简单问题

Question

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 应用于此示例!一定很简单!一些提示或解决方案都很棒。

谢谢。

Answer 1

Find-S 寻找适合所有正例的最具限制性(即最“具体”)的假设(忽略负例)。

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

...这将是 a=4、b=6、c=3、d=5。

执行此操作的算法如下所示:

Define a hypothesis rectangle h[a,b,c,d], and initialise it to [-,-,-,-]
for each + example e {
    if e is not within h {
        enlarge h to be just big enough to hold e (and all previous e's)
    } else { do nothing: h already contains e }
}

如果我们使用您的训练集逐步完成此操作，我们会得到:

 0. h = [-,-,-,-] // initial value
 1. h = [4,4,4,4] // (4,4) is not in h: change h so it just contains (4,4)
 2. h = [4,5,3,4] // (5,3) is not in h, so enlarge h to fit (4,4) and (5,3)
 3. h = [4,6,3,5] // (6,5) is not in h, so enlarge again
 4. // no more positive examples left, so we're done.