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.