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寻找最符合所有正例（负数被忽略）的限制性（即最具体的）假设。

在你的情况，有一个明显的图形解释：“找到包含所有的‘+’坐标的最小矩形” ......

...这将是一个= 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.