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