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

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

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

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

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

Алгоритм облегчения

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

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

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

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

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

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

Алгоритм ReliefF

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

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

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

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

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

Мультиклассовые задачи

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

Другие расширения и производные алгоритмов на основе облегчения

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

RELIEFF

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

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

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

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

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

I-RELIEF

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

TuRF (также известный как Tuned ReliefF)

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

Испарительное охлаждение F

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

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

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

VLSReliefF (он же очень крупномасштабный рельефF)

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

ReliefMSS

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

СЕРФ

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

SURF * (также известный как SURFStar)

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

SWRF *

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

MultiSURF * (также известный как MultiSURFStar)

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

ReliefSeq

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

MultiSURF

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

РАЗМЕШИВАТЬ

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

Приложения RBA

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

Смотрите также

Рекомендации

  1. ^ Кира, Кенджи и Ренделл, Ларри (1992). Проблема выбора характеристик: традиционные методы и новый алгоритм. AAAI-92 Труды.
  2. ^ а б Кира, Кенджи и Ренделл, Ларри (1992) Практический подход к выбору функций, Труды девятого международного семинара по машинному обучению, стр. 249-256.
  3. ^ а б Кононенко, Игорь и др. Преодоление близорукости алгоритмов индуктивного обучения с помощью RELIEFF (1997), Applied Intelligence, 7 (1), стр. 39-55.
  4. ^ а б c Кононенко, Игорь (1994-04-06). «Оценочные атрибуты: Анализ и расширения РЕЛЬЕФА». Машинное обучение: ECML-94. Конспект лекций по информатике. 784. Шпрингер, Берлин, Гейдельберг. С. 171–182. Дои:10.1007/3-540-57868-4_57. ISBN  978-3540578680. Отсутствует или пусто | название = (помощь)
  5. ^ а б Робник-Шиконья, Марко и Кононенко, Игорь (1997). Адаптация Relief для оценки атрибутов в регрессии. Машинное обучение: материалы четырнадцатой международной конференции (ICML’97) (стр. 296-304)
  6. ^ а б c Урбанович, Райан Дж .; Микер, Мелисса; ЛаКава, Уильям; Olson, Randal S .; Мур, Джейсон Х. (2018). «Выбор рельефа: введение и обзор». Журнал биомедицинской информатики. 85: 189–203. arXiv:1711.08421. Bibcode:2017arXiv171108421U. Дои:10.1016 / j.jbi.2018.07.014. ЧВК  6299836. PMID  30031057.
  7. ^ Кононенко, Игорь, Робник-Сиконья, Марко (2007-10-29). Оценка качества немиопических признаков с помощью (R) ReliefF. С. 169–192. Дои:10.1201/9781584888796-9 (неактивно 10.11.2020).CS1 maint: DOI неактивен по состоянию на ноябрь 2020 г. (связь)
  8. ^ Мур, Джейсон Х. (2015). «Анализ эпистаза с помощью ReliefF». Эпистаз. Методы молекулярной биологии. 1253. Humana Press, Нью-Йорк, Нью-Йорк. С. 315–325. Дои:10.1007/978-1-4939-2155-3_17. ISBN  9781493921546. PMID  25403540.
  9. ^ Тодоров, Александр (08.07.2016). Обзор алгоритма RELIEF и достижений. MIT Press. ISBN  9780262034685.
  10. ^ Кохави, Рон; Джон, Джордж Х (1997-12-01). «Оболочки для выбора подмножества функций». Искусственный интеллект. 97 (1–2): 273–324. Дои:10.1016 / S0004-3702 (97) 00043-X. ISSN  0004-3702.
  11. ^ Draper, B .; Kaito, C .; Бинс, Дж. (Июнь 2003 г.). «Итерационный рельеф». Конференция по компьютерному зрению и распознаванию образов, 2003 г.. 6: 62. Дои:10.1109 / CVPRW.2003.10065. S2CID  17599624.
  12. ^ Сунь Ицзюнь; Ли, Цзянь (25.06.2006). «Итеративная помощь при взвешивании характеристик». Материалы 23-й международной конференции по машинному обучению - ICML '06. ACM. С. 913–920. CiteSeerX  10.1.1.387.7424. Дои:10.1145/1143844.1143959. ISBN  978-1595933836. S2CID  1102692.
  13. ^ Солнце, Ю. (июнь 2007 г.). «Итеративное облегчение для взвешивания характеристик: алгоритмы, теории и приложения». IEEE Transactions по анализу шаблонов и машинному анализу. 29 (6): 1035–1051. Дои:10.1109 / TPAMI.2007.1093. ISSN  0162-8828. PMID  17431301. S2CID  14087053.
  14. ^ Sun, Y .; Todorovic, S .; Гудисон, С. (сентябрь 2010 г.). «Выбор функций на основе местного обучения для анализа многомерных данных». IEEE Transactions по анализу шаблонов и машинному анализу. 32 (9): 1610–1626. Дои:10.1109 / TPAMI.2009.190. ISSN  0162-8828. ЧВК  3445441. PMID  20634556.
  15. ^ Мур, Джейсон Х .; Уайт, Билл К. (11 апреля 2007 г.). Настройка ReliefF для полногеномного генетического анализа. Эволюционные вычисления, машинное обучение и интеллектуальный анализ данных в биоинформатике. Конспект лекций по информатике. 4447. Шпрингер, Берлин, Гейдельберг. С. 166–175. Дои:10.1007/978-3-540-71783-6_16. ISBN  9783540717829.
  16. ^ McKinney, B.A .; Reif, D.M .; White, B.C .; Crowe, J.E .; Мур, Дж. (2007-08-15). «Выбор функции испарительного охлаждения для генотипических данных, включающих взаимодействия». Биоинформатика. 23 (16): 2113–2120. Дои:10.1093 / биоинформатика / btm317. ISSN  1367-4803. ЧВК  3988427. PMID  17586549.
  17. ^ Парк, H .; Квон, Х.С. (август 2007 г.). Алгоритмы расширенного сброса при фильтрации функций на основе экземпляров. Шестая международная конференция по передовой обработке языков и веб-информационным технологиям (ALPIT 2007). С. 123–128. Дои:10.1109 / ALPIT.2007.16. ISBN  978-0-7695-2930-1. S2CID  15296546.
  18. ^ Eppstein, M. J .; Хааке, П. (сентябрь 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. Дои:10.1504 / ijbidm.2009.029085. S2CID  15242788.
  20. ^ а б Грин, Кейси С .; Penrod, Nadia M .; Киралис, Джефф; Мур, Джейсон Х. (22 сентября 2009 г.). «Spatially Uniform ReliefF (SURF) для эффективной с вычислительной точки зрения фильтрации взаимодействий генов». BioData Mining. 2 (1): 5. Дои:10.1186/1756-0381-2-5. ISSN  1756-0381. ЧВК  2761303. PMID  19772641.
  21. ^ а б Грин, Кейси С .; Himmelstein, Daniel S .; Киралис, Джефф; Мур, Джейсон Х. (07.04.2010). Информативные крайности: использование как ближайших, так и самых удаленных людей может улучшить алгоритмы оказания помощи в области генетики человека. Эволюционные вычисления, машинное обучение и интеллектуальный анализ данных в биоинформатике. Конспект лекций по информатике. 6023. Шпрингер, Берлин, Гейдельберг. С. 182–193. Дои:10.1007/978-3-642-12211-8_16. ISBN  9783642122101.
  22. ^ а б c d Урбанович, Райан Дж .; Olson, Randal S .; Шмитт, Питер; Микер, Мелисса; Мур, Джейсон Х. (22 ноября 2017 г.). «Сравнительный анализ методов выбора характеристик на основе рельефа для интеллектуального анализа данных биоинформатики». arXiv:1711.08477. Bibcode:2017arXiv171108477U. PMID  30030120.
  23. ^ Стоукс, Мэтью Э .; Висвесваран, Шьям (3 декабря 2012 г.). «Применение пространственно-взвешенного алгоритма рельефа для ранжирования генетических предикторов болезни». BioData Mining. 5 (1): 20. Дои:10.1186/1756-0381-5-20. ISSN  1756-0381. ЧВК  3554553. PMID  23198930.
  24. ^ а б Гранизо-Маккензи, Делани; Мур, Джейсон Х. (2013-04-03). Множественный пороговый пространственно-однородный рельеф для генетического анализа сложных болезней человека. Эволюционные вычисления, машинное обучение и интеллектуальный анализ данных в биоинформатике. Конспект лекций по информатике. 7833. Шпрингер, Берлин, Гейдельберг. С. 1–10. Дои:10.1007/978-3-642-37189-9_1. ISBN  9783642371882.
  25. ^ McKinney, Brett A .; Уайт, Билл С .; Гриль, Дайан Э .; Ли, Питер В .; Кеннеди, Ричард Б .; Польша, Григорий А .; Оберг, Энн Л. (2013-12-10). "ReliefSeq: Gene-Wise Adaptive-K инструмент выбора ближайшего соседа для поиска взаимодействий ген-ген и основных эффектов в данных экспрессии генов mRNA-Seq". PLOS ONE. 8 (12): e81527. Bibcode:2013PLoSO ... 881527M. Дои:10.1371 / journal.pone.0081527. ISSN  1932-6203. ЧВК  3858248. PMID  24339943.
  26. ^ Ле, Транг; Урбанович, Райан; Мур, Джейсон; Маккинни, Бретт (18 сентября 2018 г.). «Выбор функции статистического вывода (STIR)». Биоинформатика. 35 (8): 1358–1365. Дои:10.1093 / биоинформатика / bty788. ЧВК  6477983. PMID  30239600.
  27. ^ Ле, Транг (1 ноября 2018 г.). "СТИР Плакат". Фигшер. Дои:10.6084 / m9.figshare.7241417. Получено 24 января 2019.