Jump to content

Рельеф (выбор функции)

Relief — это алгоритм, разработанный Кирой и Ренделлом в 1992 году, который использует подход с фильтрацией для выбора признаков , который особенно чувствителен к взаимодействию признаков. [1] [2] Первоначально он был разработан для применения к задачам двоичной классификации с дискретными или числовыми признаками. Relief вычисляет оценку функции для каждой функции, которую затем можно применить для ранжирования и выбора функций с наивысшей оценкой для выбора функции. Альтернативно, эти оценки могут применяться в качестве весов признаков для дальнейшего моделирования. Оценка признаков рельефа основана на выявлении различий в значениях признаков между парами экземпляров ближайших соседей . Если разница в значениях признаков наблюдается в соседней паре экземпляров того же класса («попадание»), оценка признака снижается. Альтернативно, если разница в значениях признаков наблюдается в соседней паре экземпляров с разными значениями классов («промах»), оценка признака увеличивается. Оригинальный алгоритм Relief с тех пор вдохновил семейство алгоритмов выбора функций на основе Relief (RBA), включая ReliefF. [3] алгоритм. Помимо исходного алгоритма Relief, RBA были адаптированы для (1) более надежной работы в шумных задачах; [4] (2) обобщить на многоклассовые задачи [4] (3) обобщать задачи численного результата (т. е. регрессии), [5] и (4) сделать их устойчивыми к неполным (т.е. отсутствующим) данным. [4]

На сегодняшний день разработка вариантов и расширений RBA сосредоточена на четырех областях; (1) улучшение производительности «основного» алгоритма Relief, т.е. изучение стратегий выбора соседей и взвешивания экземпляров, (2) улучшение масштабируемости «основного» алгоритма Relief для более крупных пространств объектов посредством итеративных подходов, (3) методы гибкой адаптации Облегчение работы с различными типами данных и (4) повышение эффективности работы Relief. [6]

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

Алгоритм помощи

[ редактировать ]
Алгоритм помощи: выбор ближайших соседей экземпляра попадания и ближайшего промаха перед подсчетом очков.

Возьмите набор данных с n экземплярами p признаков, принадлежащих двум известным классам. В наборе данных каждый объект должен быть масштабирован до интервала [0 1] (двоичные данные должны оставаться как 0 и 1). Алгоритм будет повторен m раз. Начните с весового вектора (W) длиной p, состоящего из нулей.

На каждой итерации берите вектор признаков (X), принадлежащий одному случайному экземпляру, и векторы признаков экземпляра, ближайшего к X (по евклидову расстоянию) из каждого класса. Ближайший экземпляр того же класса называется «почти попадающим», а ближайший экземпляр другого класса называется «почти промахнувшимся». Обновите весовой вектор так, чтобы

где индексирует компоненты и работает от 1 до p.

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

После m итераций разделите каждый элемент весового вектора на m . Это становится вектором релевантности. Признаки выбираются, если их релевантность превышает пороговое значение τ .

Эксперименты Киры и Ренделла [2] показал четкий контраст между релевантными и нерелевантными признаками, что позволило τ определить путем проверки. Однако с помощью неравенства Чебышева для данного уровня достоверности ( α ) также можно определить, что τ , равное 1/sqrt(α*m), достаточно хорошее, чтобы сделать вероятность ошибки типа I меньше α , хотя утверждается что τ может быть намного меньше этого.

Рельеф также описывался как допускающий обобщение до полиномиальной классификации путем разложения на ряд бинарных задач.

Алгоритм РелифФ

[ редактировать ]

Кононенко и др. предложить ряд обновлений Relief. [3] Во-первых, они находят случаи, близкие к попаданию и промаху, используя манхэттенскую норму (L1) , а не евклидову норму (L2) , хотя обоснование не указано. взять абсолютные различия между xi и почти попаданием i , а также xi и почти попаданием i Кроме того, они обнаружили , что при обновлении вектора весов достаточно (а не квадратом этих различий).

Надежная оценка вероятности

[ редактировать ]

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

Неполные данные

[ редактировать ]

В ReliefF вклад пропущенных значений в вес объекта определяется с использованием условной вероятности того, что два значения должны быть одинаковыми или разными, аппроксимированной относительными частотами из набора данных. Это можно рассчитать, если одна или обе функции отсутствуют.

Многоклассовые проблемы

[ редактировать ]

Вместо того, чтобы использовать предложенное Кирой и Ренделлом разложение полиномиальной классификации на ряд биномиальных задач, ReliefF ищет k близких промахов из каждого класса и усредняет их вклады для обновления W, взвешенные с учетом априорной вероятности каждого класса.

Другие расширения/производные алгоритмов, основанные на рельефе

[ редактировать ]

Следующие РБА расположены в хронологическом порядке от самого старого к самому последнему. [6] Они включают методы улучшения (1) базовой концепции алгоритма Релифа, (2) итеративных подходов к масштабируемости, (3) адаптации к различным типам данных, (4) стратегий повышения эффективности вычислений или (5) некоторой комбинации этих целей. Дополнительную информацию о RBA см. в этих главах книги. [7] [8] [9] или этот самый последний обзорный документ. [6]

РРЕЛЬЕФФ

[ редактировать ]

Робник-Шиконья и Кононенко предлагают дальнейшие обновления ReliefF, делающие его пригодным для регрессии. [5]

С облегчением-F

[ редактировать ]

Представлен детерминированный подход к выбору соседей и новый подход к обработке неполных данных. [10]

Итеративное облегчение

[ редактировать ]

Реализован метод устранения смещения в отношении немонотонных функций. Представлен первый итеративный подход Relief. Впервые соседи однозначно определялись по пороговому радиусу, а экземпляры взвешивались по их расстоянию от целевого экземпляра. [11]

Я-РЕЛЬЕФ

[ редактировать ]

Введено сигмоидальное взвешивание на основе расстояния от целевого экземпляра. [12] [13] Все пары экземпляров (а не только определенное подмножество соседей) способствовали обновлению оценок. Предложил вариант онлайн-обучения «Рельеф». Расширена концепция итерационного рельефа. Введены обновления локального обучения между итерациями для улучшения конвергенции. [14]

TuRF (он же Tuned ReliefF)

[ редактировать ]

Специально стремился устранить шум в больших пространствах признаков посредством рекурсивного исключения признаков и итеративного применения ReliefF. [15]

Система испарительного охлаждения

[ редактировать ]

Аналогичным образом мы стремимся устранить шум в больших пространственных объектах. Использовалось итеративное «испарительное» удаление признаков самого низкого качества с использованием оценок ReliefF в сочетании с взаимной информацией. [16]

EReliefF (также известный как Extended ReliefF)

[ редактировать ]

Решение проблем, связанных с неполными и многоклассовыми данными. [17]

VLSReliefF (также известный как Очень крупномасштабная помощьF)

[ редактировать ]

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

РельефМСС

[ редактировать ]

Введен расчет весов признаков относительно средней разницы признаков между парами экземпляров. [19]

SURF идентифицирует ближайших соседей (как попаданий, так и промахов) на основе порогового значения расстояния от целевого экземпляра, определяемого средним расстоянием между всеми парами экземпляров в обучающих данных. [20] Результаты свидетельствуют о большей способности обнаруживать двусторонние эпистатические взаимодействия по сравнению с ReliefF.

SURF* (он же SURFStar)

[ редактировать ]

СЕРФ* [21] расширяет возможности SURF [20] Алгоритм позволяет использовать не только «ближних» соседей при обновлении оценки, но и «дальние» экземпляры, а также использовать инвертированные обновления оценки для пар «дальних экземпляров». Результаты предполагают улучшенную способность обнаружения двусторонних эпистатических взаимодействий по сравнению с SURF, но неспособность обнаружить простые основные эффекты (т. е. одномерные ассоциации). [22]

SWRF* расширяет алгоритм SURF*, применяя сигмовидное взвешивание для учета расстояния от порога. Также была представлена ​​модульная структура для дальнейшего развития РРУ под названием MoRF. [23]

MultiSURF* (он же MultiSURFStar)

[ редактировать ]

МультиSURF* [24] расширяет SURF* [21] алгоритм, адаптирующий границы ближнего/дальнего соседства на основе среднего и стандартного отклонения расстояний от целевого экземпляра до всех остальных. MultiSURF* использует стандартное отклонение для определения зоны нечувствительности, в которой экземпляры «среднего расстояния» не влияют на оценку. Опыт показывает, что MultiSURF* лучше всего справляется с обнаружением чисто двусторонних взаимодействий функций. [22]

РельефСек

[ редактировать ]

Вводит многофункциональный адаптивный параметр k для более гибкого обнаружения одномерных эффектов и эффектов взаимодействия. [25]

МультиСЕРФ

[ редактировать ]

МультиСЕРФ [22] упрощает MultiSURF* [24] алгоритм путем сохранения зоны нечувствительности и определения окрестности, ориентированного на целевой экземпляр, но исключая «дальнюю» оценку. Имеющиеся данные свидетельствуют о том, что MultiSURF является хорошо продуманным вариантом, способным обнаруживать двусторонние и трехсторонние взаимодействия, а также простые одномерные ассоциации. [22] Также представлен пакет программного обеспечения RBA под названием ReBATE, который включает реализации (Relief, ReliefF, SURF, SURF*, MultiSURF*, MultiSURF и TuRF).

ПОМЕШИВАТЬ

[ редактировать ]

ПОМЕШИВАТЬ [26] [27] переформулирует и слегка корректирует исходную формулу Рельефа, включая выборочную дисперсию расстояний до ближайших соседей в оценку важности атрибута. Эта дисперсия позволяет рассчитать статистическую значимость признаков и внести поправки для многократного тестирования оценок на основе Релифа. В настоящее время STIR поддерживает двоичную переменную результата, но вскоре будет расширен до многосостоятельного и непрерывного результата.

Приложения РБА

[ редактировать ]

Различные RBA применялись для выбора функций в различных проблемных областях.

См. также

[ редактировать ]
  1. ^ Кира, Кенджи и Ренделл, Ларри (1992). Проблема выбора признаков: традиционные методы и новый алгоритм . Дело AAAI-92.
  2. ^ Jump up to: а б Кира, Кенджи и Ренделл, Ларри (1992). Практический подход к выбору функций , материалы девятого международного семинара по машинному обучению, стр. 249-256.
  3. ^ Jump up to: а б Кононенко Игорь и др. Преодоление близорукости алгоритмов индуктивного обучения с помощью RELIEF (1997), Applied Intelligence, 7 (1), стр. 39-55.
  4. ^ Jump up to: а б с Кононенко, Игорь (6 апреля 1994 г.). «Оценка атрибутов: анализ и расширение RELIEF». Машинное обучение: ECML-94 . Конспекты лекций по информатике. Том. 784. Шпрингер, Берлин, Гейдельберг. стр. 171–182. дои : 10.1007/3-540-57868-4_57 . ISBN  978-3540578680 . S2CID   8190856 .
  5. ^ Jump up to: а б Робник-Шиконья, Марко и Кононенко, Игорь (1997). Адаптация Relief для оценки атрибутов в регрессии. Машинное обучение: материалы четырнадцатой международной конференции (ICML'97) (стр. 296-304).
  6. ^ Jump up to: а б с Урбанович, Райан Дж.; Микер, Мелисса; ЛаКава, Уильям; Олсон, Рэндал С.; Мур, Джейсон Х. (2018). «Выбор объектов на основе рельефа: введение и обзор» . Журнал биомедицинской информатики . 85 : 189–203. arXiv : 1711.08421 . Бибкод : 2017arXiv171108421U . дои : 10.1016/j.jbi.2018.07.014 . ПМК   6299836 . ПМИД   30031057 .
  7. ^ Кононенко, Игорь, Робник-Сиконя, Марко (29 октября 2007 г.). Оценка качества функций при неблизорукости с помощью (R)ReliefF . Чепмен и Холл/CRC. стр. 169–192. дои : 10.1201/9781584888796-9 . ISBN  9780429150418 . {{cite book}}: CS1 maint: несколько имен: список авторов ( ссылка )
  8. ^ Мур, Джейсон Х. (2015). «Анализ эпистаза с использованием рельефа». Эпистаз . Методы молекулярной биологии. Том. 1253. Humana Press, Нью-Йорк, штат Нью-Йорк. стр. 315–325. дои : 10.1007/978-1-4939-2155-3_17 . ISBN  9781493921546 . ПМИД   25403540 .
  9. ^ Тодоров, Александр (08.07.2016). Обзор алгоритма RELIEF и его усовершенствований . МТИ Пресс. ISBN  9780262034685 .
  10. ^ Кохави, Рон; Джон, Джордж Х (1 декабря 1997 г.). «Обертки для выбора подмножества функций» . Искусственный интеллект . 97 (1–2): 273–324. дои : 10.1016/S0004-3702(97)00043-X . ISSN   0004-3702 .
  11. ^ Дрейпер, Б.; Кайто, К.; Бинс, Дж. (июнь 2003 г.). «Итеративное облегчение». 2003 Конференция по компьютерному зрению и распознаванию образов . Том. 6. с. 62. дои : 10.1109/CVPRW.2003.10065 . S2CID   17599624 .
  12. ^ Сунь, Ицзюнь; Ли, Цзянь (25 июня 2006 г.). «Итеративный РЕЛЬЕФ для взвешивания признаков». Материалы 23-й международной конференции по машинному обучению — ICML '06 . АКМ. стр. 913–920. CiteSeerX   10.1.1.387.7424 . дои : 10.1145/1143844.1143959 . ISBN  978-1595933836 . S2CID   1102692 .
  13. ^ Сан, Ю. (июнь 2007 г.). «Итеративный РЕЛЬЕФ для взвешивания функций: алгоритмы, теории и приложения». Транзакции IEEE по анализу шаблонов и машинному интеллекту . 29 (6): 1035–1051. дои : 10.1109/TPAMI.2007.1093 . ISSN   0162-8828 . ПМИД   17431301 . S2CID   14087053 .
  14. ^ Сан, Ю.; Тодорович, С.; Гудисон, С. (сентябрь 2010 г.). «Выбор функций на основе локального обучения для анализа многомерных данных» . Транзакции IEEE по анализу шаблонов и машинному интеллекту . 32 (9): 1610–1626. дои : 10.1109/TPAMI.2009.190 . ISSN   0162-8828 . ПМЦ   3445441 . ПМИД   20634556 .
  15. ^ Мур, Джейсон Х.; Уайт, Билл К. (11 апреля 2007 г.). «Настройка ReliefF для полногеномного генетического анализа». Эволюционные вычисления, машинное обучение и интеллектуальный анализ данных в биоинформатике . Конспекты лекций по информатике. Том. 4447. Шпрингер, Берлин, Гейдельберг. стр. 166–175. дои : 10.1007/978-3-540-71783-6_16 . ISBN  9783540717829 .
  16. ^ МакКинни, бакалавр; Рейф, DM; Уайт, Британская Колумбия; Кроу, Дж. Э.; Мур, Дж. Х. (15 августа 2007 г.). «Выбор функции испарительного охлаждения для генотипических данных, включающих взаимодействия» . Биоинформатика . 23 (16): 2113–2120. doi : 10.1093/биоинформатика/btm317 . ISSN   1367-4803 . ПМЦ   3988427 . ПМИД   17586549 .
  17. ^ Парк, Х.; Квон, ХК (август 2007 г.). «Расширенные алгоритмы облегчения фильтрации объектов на основе экземпляров». Шестая международная конференция по усовершенствованной языковой обработке и веб-информационным технологиям (ALPIT 2007) . стр. 123–128. дои : 10.1109/ALPIT.2007.16 . ISBN  978-0-7695-2930-1 . S2CID   15296546 .
  18. ^ Эппштейн, MJ; Хааке, П. (сентябрь 2008 г.). «Очень крупномасштабный ReliefF для полногеномного анализа ассоциаций». Симпозиум IEEE 2008 г. по вычислительному интеллекту в биоинформатике и вычислительной биологии . стр. 112–119. дои : 10.1109/CIBCB.2008.4675767 . ISBN  978-1-4244-1778-0 . S2CID   9296768 .
  19. ^ Чихи, Салим; Бенхаммада, Садек (4 ноября 2009 г.). «ReliefMSS: вариант алгоритма ReliefF ранжирования функций». Международный журнал бизнес-аналитики и интеллектуального анализа данных . 4 (3/4): 375. doi : 10.1504/ijbidm.2009.029085 . S2CID   15242788 .
  20. ^ Jump up to: а б Грин, Кейси С.; Пенрод, Надя М.; Киралис, Джефф; Мур, Джейсон Х. (22 сентября 2009 г.). «Пространственно-равномерный рельеф (SURF) для эффективной в вычислительном отношении фильтрации взаимодействий ген-ген» . Добыча биоданных . 2 (1): 5. дои : 10.1186/1756-0381-2-5 . ISSN   1756-0381 . ПМЦ   2761303 . ПМИД   19772641 .
  21. ^ Jump up to: а б Грин, Кейси С.; Химмельштейн, Дэниел С.; Киралис, Джефф; Мур, Джейсон Х. (7 апреля 2010 г.). «Информационные крайности: использование как ближайших, так и самых дальних особей может улучшить алгоритмы помощи в области генетики человека». Эволюционные вычисления, машинное обучение и интеллектуальный анализ данных в биоинформатике . Конспекты лекций по информатике. Том. 6023. Шпрингер, Берлин, Гейдельберг. стр. 182–193. дои : 10.1007/978-3-642-12211-8_16 . ISBN  9783642122101 .
  22. ^ Jump up to: а б с д Урбанович, Райан Дж.; Олсон, Рэндал С.; Шмитт, Питер; Микер, Мелисса; Мур, Джейсон Х. (22 ноября 2017 г.). «Сравнительный анализ методов выбора признаков на основе рельефа для биоинформатического анализа данных». arXiv : 1711.08477 . Бибкод : 2017arXiv171108477U . ПМИД   30030120 .
  23. ^ Стоукс, Мэтью Э.; Висвесваран, Шьям (3 декабря 2012 г.). «Применение пространственно-взвешенного алгоритма Рельефа для ранжирования генетических предикторов заболеваний» . Добыча биоданных . 5 (1): 20. дои : 10.1186/1756-0381-5-20 . ISSN   1756-0381 . ПМЦ   3554553 . ПМИД   23198930 .
  24. ^ Jump up to: а б Гранизо-Маккензи, Делани; Мур, Джейсон Х. (3 апреля 2013 г.). «Многопороговый пространственно-равномерный рельеф для генетического анализа сложных заболеваний человека». Эволюционные вычисления, машинное обучение и интеллектуальный анализ данных в биоинформатике . Конспекты лекций по информатике. Том. 7833. Шпрингер, Берлин, Гейдельберг. стр. 1–10. дои : 10.1007/978-3-642-37189-9_1 . ISBN  9783642371882 .
  25. ^ МакКинни, Бретт А.; Уайт, Билл С.; Гриль, Дайан Э.; Ли, Питер В.; Кеннеди, Ричард Б.; Польша, Грегори А.; Оберг, Энн Л. (10 декабря 2013 г.). «ReliefSeq: инструмент выбора признаков ближайшего соседа Gene-Wise Adaptive-K для поиска межгенных взаимодействий и основных эффектов в данных экспрессии генов мРНК-Seq» . ПЛОС ОДИН . 8 (12): е81527. Бибкод : 2013PLoSO...881527M . дои : 10.1371/journal.pone.0081527 . ISSN   1932-6203 . ПМЦ   3858248 . ПМИД   24339943 .
  26. ^ Ле, Транг; Урбанович, Райан; Мур, Джейсон; МакКинни, Бретт (18 сентября 2018 г.). «Выбор функции статистического вывода (STIR)» . Биоинформатика . 35 (8): 1358–1365. doi : 10.1093/биоинформатика/bty788 . ПМК   6477983 . ПМИД   30239600 .
  27. ^ Ле, Транг (1 ноября 2018 г.). «Плакат СТИР» . Фиговая доля . doi : 10.6084/m9.figshare.7241417 . Проверено 24 января 2019 г.
Arc.Ask3.Ru: конец переведенного документа.
Arc.Ask3.Ru
Номер скриншота №: d7534be3a078e01b36357ff92d792d0e__1717532880
URL1:https://arc.ask3.ru/arc/aa/d7/0e/d7534be3a078e01b36357ff92d792d0e.html
Заголовок, (Title) документа по адресу, URL1:
Relief (feature selection) - Wikipedia
Данный printscreen веб страницы (снимок веб страницы, скриншот веб страницы), визуально-программная копия документа расположенного по адресу URL1 и сохраненная в файл, имеет: квалифицированную, усовершенствованную (подтверждены: метки времени, валидность сертификата), открепленную ЭЦП (приложена к данному файлу), что может быть использовано для подтверждения содержания и факта существования документа в этот момент времени. Права на данный скриншот принадлежат администрации Ask3.ru, использование в качестве доказательства только с письменного разрешения правообладателя скриншота. Администрация Ask3.ru не несет ответственности за информацию размещенную на данном скриншоте. Права на прочие зарегистрированные элементы любого права, изображенные на снимках принадлежат их владельцам. Качество перевода предоставляется как есть. Любые претензии, иски не могут быть предъявлены. Если вы не согласны с любым пунктом перечисленным выше, вы не можете использовать данный сайт и информация размещенную на нем (сайте/странице), немедленно покиньте данный сайт. В случае нарушения любого пункта перечисленного выше, штраф 55! (Пятьдесят пять факториал, Денежную единицу (имеющую самостоятельную стоимость) можете выбрать самостоятельно, выплаичвается товарами в течение 7 дней с момента нарушения.)