Алгоритм 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.