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.