ML | Найти S-алгоритм

Опубликовано: 23 Июля, 2021

Вступление :
Алгоритм Find-S - это базовый алгоритм обучения концепции в машинном обучении. Алгоритм Find-S находит наиболее конкретную гипотезу, подходящую для всех положительных примеров. Здесь следует отметить, что алгоритм учитывает только положительные обучающие примеры. Алгоритм Find-S начинается с наиболее конкретной гипотезы и обобщает эту гипотезу каждый раз, когда ему не удается классифицировать наблюдаемые положительные данные обучения. Следовательно, алгоритм Find-S переходит от наиболее конкретной гипотезы к наиболее общей.

Важное представление:

  1. ? указывает, что для атрибута допустимо любое значение.
  2. укажите единственное обязательное значение (например, Холодное) для атрибута.
  3. ϕ указывает, что значение неприемлемо.
  4. Самая общая гипотеза представлена: {?,?,?,?,?,?}
  5. Наиболее конкретная гипотеза представлена следующим образом: {ϕ, ϕ, ϕ, ϕ, ϕ, ϕ}

Шаги, связанные с Find-S:

  1. Начнем с самой конкретной гипотезы.
    h = {ϕ, ϕ, ϕ, ϕ, ϕ, ϕ}
  2. Возьмем следующий пример, и если он отрицательный, то гипотеза не изменится.
  3. Если пример положительный и мы обнаруживаем, что наша первоначальная гипотеза слишком конкретна, мы обновляем нашу текущую гипотезу до общего состояния.
  4. Продолжайте повторять вышеуказанные шаги, пока не будут завершены все обучающие примеры.
  5. После того, как мы завершим все обучающие примеры, у нас будет окончательная гипотеза, когда ее можно будет использовать для классификации новых примеров.

Пример :

Рассмотрим следующий набор данных, содержащий данные о том, какие именно семена ядовиты.

Сначала мы рассматриваем гипотезу как более конкретную гипотезу. Следовательно, наша гипотеза была бы такой:
h = {ϕ, ϕ, ϕ, ϕ, ϕ, ϕ}

Рассмотрим пример 1:

Данные в примере 1: {ЗЕЛЕНЫЙ, ЖЕСТКИЙ, НЕТ, МОРЩАННЫЙ}. Мы видим, что наша исходная гипотеза более конкретна, и мы должны обобщить ее для этого примера. Следовательно, гипотеза принимает следующий вид:
h = {ЗЕЛЕНЫЙ, ЖЕСТКИЙ, НЕТ, МОРЩАННЫЙ}

Рассмотрим пример 2:
Здесь мы видим, что этот пример имеет отрицательный результат. Поэтому мы пренебрегаем этим примером, и наша гипотеза остается прежней.
h = {ЗЕЛЕНЫЙ, ЖЕСТКИЙ, НЕТ, МОРЩАННЫЙ}

Рассмотрим пример 3:
Здесь мы видим, что этот пример имеет отрицательный результат. Поэтому мы пренебрегаем этим примером, и наша гипотеза остается прежней.
h = {ЗЕЛЕНЫЙ, ЖЕСТКИЙ, НЕТ, МОРЩАННЫЙ}

Рассмотрим пример 4:
В примере 4 представлены следующие данные: {ОРАНЖЕВЫЙ, ЖЕСТКИЙ, НЕТ, МОРЩАННЫЙ}. Мы сравниваем каждый атрибут с исходными данными, и если обнаруживается какое-либо несоответствие, мы заменяем этот конкретный атрибут общим регистром («?»). После выполнения процесса гипотеза принимает следующий вид:
h = {?, ЖЕСТКИЙ, НЕТ, МОРЩАННЫЙ}

Рассмотрим пример 5:
В примере 5 представлены следующие данные: {ЗЕЛЕНЫЙ, МЯГКИЙ, ДА, ГЛАДКИЙ}. Мы сравниваем каждый атрибут с исходными данными, и если обнаруживается какое-либо несоответствие, мы заменяем этот конкретный атрибут общим регистром («?»). После выполнения процесса гипотеза принимает следующий вид:
h = {?,?,?,? }
Поскольку мы достигли точки, когда все атрибуты в нашей гипотезе имеют общее состояние, пример 6 и пример 7 приведут к одинаковым гипотезам со всеми общими атрибутами.
h = {?,?,?,? }

Следовательно, для данных данных окончательной гипотезой будет:
Заключительная гипотеза: h = {?,?,?,? }


Алгоритм:

1. Инициализируйте h для наиболее конкретной гипотезы в H
2. Для каждого положительного обучающего примера x
    Для каждого ограничения атрибута a, в h
        Если ограничению a, удовлетворяет x
        Тогда ничего не делай
        В противном случае замените a в h следующим более общим ограничением, которому удовлетворяет x
3. Выходная гипотеза h