Глубокий анализ того, как работают алгоритмы Relief, где они используются, и пример на Python, как их использовать.

Содержание:

  1. Важность выбора функции
  2. Обзор семейства алгоритмов Relief.
  3. Базовый алгоритм разгрузки
  4. ReliefF - алгоритм расширения.
  5. Пример Python.
  6. Использованная литература.

1. Важность выбора функций:

Во многих задачах машинного обучения есть сотни или тысячи потенциальных функций, описывающих каждый входной объект. Большинство методов обучения плохо себя ведут в этих обстоятельствах по разным причинам, некоторые из них - Проклятие размерности (переобучения), зашумленные данные, длительное время обучения и т. Д. применяются селекционные приемы.

Более того, использование методов выбора характеристик имеет много преимуществ:

  1. Сокращенное время обучения
  2. Менее сложный, поэтому его легче интерпретировать.
  3. Повышенная точность, если выбрано правильное подмножество.
  4. Уменьшает переобучение.

Семейство алгоритмов сброса в основном используется на этапе предварительной обработки до того, как модель будет изучена как метод выбора подмножества признаков.

2. Обзор семейства алгоритмов Relief:

В семействе помощи есть три алгоритма:

  1. Базовый алгоритм облегчения: он ограничен задачами классификации с двумя классами.
  2. ReliefF: Расширение облегчения. Что может решить проблемы с мультиклассом.
  3. RReliefF: Затем ReliefF был адаптирован для задач непрерывного класса (регрессии)
    , результатом которых стал алгоритм RReliefF.

В этом посте мы обсудим Relief и ReliefF. Хотя основная идея во всех трех алгоритмах остается неизменной.

Основная идея алгоритмов Relief заключается в оценке качества атрибутов на основе того, насколько хорошо атрибут может различать экземпляры, которые находятся рядом друг с другом.

Преимущества алгоритмов разгрузки:

Хотя многие эвристические меры предполагают условную (от целевой переменной) независимость атрибутов для оценки качества атрибутов, алгоритмы Relief не делают этого предположения. Они эффективны, осведомлены о контекстной информации и могут правильно оценивать качество атрибутов в задачах с сильными зависимостями между атрибутами.

Алгоритмы сброса в основном рассматривались как метод выбора подмножества признаков, который применяется на этапе предварительной оценки до изучения модели и является одним из наиболее успешных алгоритмов предварительной обработки. На самом деле это средства оценки общих функций, которые успешно использовались в различных условиях.

3. Базовый алгоритм сброса давления

Алгоритм:

Входные данные: для каждого обучающего экземпляра вектор значений атрибутов и значение класса

Выход: вектор W оценок качеств атрибутов.

Псевдокод:

1. установить все веса W [A]: = 0.0;
2. для i: = от 1 до m действительно начать
3. произвольно выбрать экземпляр R ᵢ ;
4. найти ближайшее попадание H и ближайшее промах M;
5. for A: = 1 to a do
6. W [A]: = W [A] -diff (A , R ᵢ , H) / m + diff (A, R ᵢ , M) / m;
7. end;

Предположим, что I ₁, I ₂,…., I ₙ являются примерами в пространстве экземпляров, где каждый пример представляет собой вектор атрибутов A ᵢ, i = 1,…., A, где a - количество атрибутов, и каждый пример имеет целевое значение t ⱼ. Следовательно, примеры - это точки в размерном пространстве.

Работает:

Вес всех атрибутов изначально установлен на ноль (строка 1 псевдокода).

Затем мы выбираем случайный экземпляр Rᵢ (строка 3) и находим его двух ближайших соседей: один из того же класса, к которому принадлежит Rᵢ, известного как ближайшее попадание H, и другой из другого класса, известного как ближайший промах M (строка 4). Теперь веса всех атрибутов обновляются в зависимости от значений Rᵢ, M и H (строки 5 и 6). Весь этот процесс повторяется m раз, m - параметр, определяемый пользователем.

Функция различия:

Обновление веса атрибутов работает по простой идее (строка 6). Если экземпляры Rᵢ и H имеют разные значения (т.е. значение diff большое), это означает, что атрибут разделяет два экземпляра с одним и тем же классом, что нежелательно, поэтому мы уменьшаем вес атрибутов. С другой стороны, если экземпляры Rᵢ и M имеют разные значения, это означает, что атрибут разделяет два экземпляра с разными классами, что желательно.

Пример: (вручную)

Здесь строки 1,2, .., 5 - это экземпляры. D - целевой класс (имеющий два класса 0 или 1). A, B, C - атрибуты. Мы найдем веса атрибутов, а затем выберем 2 лучших атрибута, то есть атрибуты с наибольшим весом.

Пусть m = 2 (т.е. мы выполним 2 итерации).

Шаг 1. Пусть вес всех атрибутов равен 0, A = B = C = 0,

Первая итерация:

Шаг 2: Предположим, мы выбрали строку 5 в качестве случайно выбранного экземпляра. (т.е. 6,0,0)

Шаг 3: Найдите ближайший промах и ударьте. Используя расстояние Манхэттена, мы находим, что строка 4 является ближайшим совпадением (после попытки всех комбинаций одного класса): | 6–8 | + | 0–3 | + | 0–1 | = 6, а строка 2 - ближайший промах (после перебора всех комбинаций из разных классов): | 6–5 | + | 0–1 | + | 0–0 | = 2.

Шаг 4. Обновите все веса атрибутов.

A, B, C: текущий вес = 0

A = 0-((|6–8|/(9–5))/2) + ((|6–5|/(9–5))/2) = 0-(0.5/2)+(0.25/2) = -0.1875

B = 0-((|0–3|/(3–0))/2)+((|0–1|/(3–0))/2) = 0-(1/2)+(1/6) = -0.33

C = 0-((|0–1|/(2–0))/2)+((|0–0|/(2–0))/2) = 0-(1/4) + 0 = -0.25

Вторая итерация:

Шаг 2: Теперь снова предположим, что мы выбрали строку 4 в качестве случайно выбранного экземпляра. (т.е. 8,3,1)

Шаг 3: Найдите ближайший промах и ударьте. Используя расстояние Манхэттена, мы находим, что строка 3 является ближайшим совпадением: | 8–9 | + | 3–3 | + | 1–2 | = 2 и строка 1 является ближайшим промахом: | 8–9 | + | 3–2 | + | 1–2 | = 3.

Шаг 4. Обновите все веса атрибутов.

A, B, C: текущий вес = -0,1875, -0,33, -0,25.

A = -0.1875-((|8–9|/(9–5))/2) + ((|8–9|/(9–5))/2) = -0.1875

B = -0.33-((|3–3|/(3–0))/2)+((|3–2|/(3–0))/2)=-0.33 -0+0.166=-0.167

C = -0.25-((|1–2|/(2–0))/2)+((|1–2|/(2–0))/2) = -0.25

Таким образом, после 2 итераций мы имеем A = -0,1875, B = -0,167, C = -0,25

Поэтому мы можем выбрать A и B в качестве двух наших лучших характеристик, поскольку они имеют наименьший вес.

Исходный рельеф может работать с номинальными и числовыми атрибутами. Однако он не может работать с неполными данными и ограничивается проблемами двух классов.
Его расширение, которое решает эти и другие проблемы, называется ReliefF.

4. ReliefF-Extension:

Алгоритм ReliefF:

Входные данные: для каждого обучающего экземпляра вектор значений атрибутов и значение класса.

Выходные данные: вектор W оценок качеств атрибутов.

k - значение, определяемое пользователем. В большинстве случаев его можно смело установить на 10.

Работает:

Подобно Relief, ReliefF случайным образом выбирает экземпляр Rᵢ (строка 3), но затем ищет K ближайших соседей (строка 4) того же класса, известного как Hⱼ, а затем ищет k ближайших промахов Mⱼ (C) для каждого из другого класса ( строки 5 и 6). Затем, как и Relief, ReliefF обновляет вес каждого атрибута, но мы усредняем вклад всех попаданий и всех промахов (строки 7,8,9).

Вклад каждого класса промахов взвешивается с учетом априорной вероятности этого класса P (C). Поскольку в сумме отсутствует класс совпадений, мы должны разделить каждый вероятностный вес с коэффициентом 1-P (класс (Rᵢ)).

Выбор k попаданий и промахов является основным отличием от Relief и обеспечивает большую устойчивость алгоритма в отношении шума.

Чтобы иметь дело с неполными данными, мы меняем функцию diff. Отсутствующие значения
атрибутов обрабатываются вероятностно.

Ручной пример этого алгоритма будет утомительным, но его можно понять из примера выше.

5. Пример Python

Мы можем видеть, что в первом примере: проблема с двумя классами одни и те же кортежи выбираются python (то есть A и B).

6. Ссылки:

Робник-Шиконья М. и Кононенко И. Машинное обучение (2003) 53: 23. https://doi.org/10.1023/A:1025667309714