stringtranslate.com

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

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

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

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

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

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

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

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

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

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

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

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

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

Алгоритм ReliefF

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

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

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

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

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

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

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

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

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

РРЕЛИЭФФ

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

Облегчение-F

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

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

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

I-РЕЛЬЕФ

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

TuRF (он же Tuned ReliefF)

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

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

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

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

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

VLSReliefF (он же Very Large Scale ReliefF)

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

РельефМСС

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

СЕРФИНГ

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

SURF* (он же SURFStar)

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

SWRF*

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

MultiSURF* (он же MultiSURFStar)

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

РельефСек

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

MultiSURF

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

ПОМЕШИВАТЬ

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

Приложения RBA

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

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

Ссылки

  1. ^ Кира, Кенджи и Ренделл, Ларри (1992). Проблема выбора признаков: традиционные методы и новый алгоритм. Труды AAAI-92.
  2. ^ ab Кира, Кенджи и Ренделл, Ларри (1992) Практический подход к выбору признаков, Труды Девятого международного семинара по машинному обучению, стр. 249-256
  3. ^ ab Кононенко, Игорь и др. Преодоление близорукости индуктивных алгоритмов обучения с помощью RELIEFF (1997), Applied Intelligence, 7(1), стр. 39-55
  4. ^ abc Кононенко, Игорь (1994-04-06). "Оценка атрибутов: Анализ и расширения RELIEF". Машинное обучение: ECML-94 . Конспект лекций по информатике. Том 784. Springer, Берлин, Гейдельберг. С. 171–182. doi :10.1007/3-540-57868-4_57. ISBN 978-3540578680. S2CID  8190856.
  5. ^ ab Robnik-Šikonja, Marko, and Kononenko, Igor (1997). Адаптация Relief для оценки атрибутов в регрессии. Machine Learning: Proceedings of the Fourteenth International Conference (ICML'97) (стр. 296-304)
  6. ^ abc Urbanowicz, Ryan J.; Meeker, Melissa; LaCava, William; Olson, Randal S.; Moore, Jason H. (2018). «Выбор признаков на основе рельефа: введение и обзор». Journal of Biomedical Informatics . 85 : 189–203. arXiv : 1711.08421 . Bibcode : 2017arXiv171108421U. doi : 10.1016/j.jbi.2018.07.014. PMC 6299836. PMID  30031057 . 
  7. ^ Кононенко, Игорь, Робник-Сиконья, Марко (2007-10-29). Оценка качества немиопических признаков с помощью (R)ReliefF. Chapman и Hall/CRC. стр. 169–192. doi :10.1201/9781584888796-9. ISBN 9780429150418.{{cite book}}: CS1 maint: несколько имен: список авторов ( ссылка )
  8. ^ Мур, Джейсон Х. (2015). «Анализ эпистаза с использованием ReliefF». Эпистаз . Методы в молекулярной биологии. Т. 1253. Humana Press, Нью-Йорк, штат Нью-Йорк. С. 315–325. doi :10.1007/978-1-4939-2155-3_17. ISBN 9781493921546. PMID  25403540.
  9. ^ Тодоров, Александр (2016-07-08). Обзор алгоритма RELIEF и его усовершенствований. MIT Press. ISBN 9780262034685.
  10. ^ Кохави, Рон; Джон, Джордж Х (1 декабря 1997 г.). «Оболочки для выбора подмножества признаков». Искусственный интеллект . 97 (1–2): 273–324. doi : 10.1016/S0004-3702(97)00043-X . ISSN  0004-3702.
  11. ^ Draper, B.; Kaito, C.; Bins, J. (июнь 2003 г.). "Итеративный рельеф". Конференция 2003 г. по компьютерному зрению и распознаванию образов . Том 6. стр. 62. doi :10.1109/CVPRW.2003.10065. S2CID  17599624.
  12. ^ Сан, Ицзюнь; Ли, Цзянь (2006-06-25). "Итеративный RELIEF для взвешивания признаков". Труды 23-й международной конференции по машинному обучению - ICML '06 . ACM. С. 913–920. CiteSeerX 10.1.1.387.7424 . doi :10.1145/1143844.1143959. ISBN  978-1595933836. S2CID  1102692.
  13. ^ Sun, Y. (июнь 2007 г.). «Итеративный RELIEF для взвешивания признаков: алгоритмы, теории и приложения». Труды IEEE по анализу шаблонов и машинному интеллекту . 29 (6): 1035–1051. doi :10.1109/TPAMI.2007.1093. ISSN  0162-8828. PMID  17431301. S2CID  14087053.
  14. ^ Sun, Y.; Todorovic, S.; Goodison, S. (сентябрь 2010 г.). «Выбор признаков на основе локального обучения для анализа многомерных данных». Труды IEEE по анализу шаблонов и машинному интеллекту . 32 (9): 1610–1626. doi :10.1109/TPAMI.2009.190. ISSN  0162-8828. PMC 3445441. PMID 20634556  . 
  15. ^ Мур, Джейсон Х.; Уайт, Билл К. (2007-04-11). "Настройка ReliefF для геномного генетического анализа". Эволюционные вычисления, машинное обучение и интеллектуальный анализ данных в биоинформатике . Конспект лекций по информатике. Том 4447. Springer, Берлин, Гейдельберг. С. 166–175. doi :10.1007/978-3-540-71783-6_16. ISBN 9783540717829.
  16. ^ МакКинни, BA; Рейф, DM; Уайт, BC; Кроу, JE; Мур, JH (2007-08-15). «Выбор характеристик испарительного охлаждения для генотипических данных, включающих взаимодействия». Биоинформатика . 23 (16): 2113–2120. doi :10.1093/bioinformatics/btm317. ISSN  1367-4803. PMC 3988427. PMID  17586549 . 
  17. ^ Park, H.; Kwon, HC (август 2007). "Расширенные алгоритмы облегчения в фильтрации признаков на основе экземпляров". Шестая международная конференция по передовой языковой обработке и веб-информационным технологиям (ALPIT 2007) . стр. 123–128. doi :10.1109/ALPIT.2007.16. ISBN 978-0-7695-2930-1. S2CID  15296546.
  18. ^ Эппштейн, М. Дж.; Хааке, П. (сентябрь 2008 г.). «Очень крупномасштабный ReliefF для анализа ассоциаций на уровне генома». Симпозиум IEEE 2008 г. по вычислительному интеллекту в биоинформатике и вычислительной биологии . стр. 112–119. doi :10.1109/CIBCB.2008.4675767. ISBN 978-1-4244-1778-0. S2CID  9296768.
  19. ^ Чихи, Салим; Бенхаммада, Садек (2009-11-04). "ReliefMSS: вариация алгоритма ранжирования признаков ReliefF". Международный журнал бизнес-аналитики и интеллектуального анализа данных . 4 (3/4): 375. doi :10.1504/ijbidm.2009.029085. S2CID  15242788.
  20. ^ ab Грин, Кейси С.; Пенрод, Надя М.; Киралис, Джефф; Мур, Джейсон Х. (2009-09-22). "Пространственно-однородный рельефF (SURF) для вычислительно-эффективной фильтрации взаимодействий ген-ген". BioData Mining . 2 (1): 5. doi : 10.1186/1756-0381-2-5 . ISSN  1756-0381. PMC 2761303. PMID 19772641  . 
  21. ^ ab Greene, Casey S.; Himmelstein, Daniel S.; Kiralis, Jeff; Moore, Jason H. (2010-04-07). "Информативные крайности: использование как ближайших, так и самых дальних особей может улучшить алгоритмы облегчения в области генетики человека". Эволюционные вычисления, машинное обучение и интеллектуальный анализ данных в биоинформатике . Конспект лекций по информатике. Том 6023. Springer, Берлин, Гейдельберг. С. 182–193. doi :10.1007/978-3-642-12211-8_16. ISBN 9783642122101.
  22. ^ abcd Урбанович, Райан Дж.; Олсон, Рэндал С.; Шмитт, Питер; Микер, Мелисса; Мур, Джейсон Х. (2017-11-22). "Сравнительный анализ методов выбора признаков на основе рельефа для интеллектуального анализа данных в биоинформатике". arXiv : 1711.08477 . Bibcode :2017arXiv171108477U. PMID  30030120.
  23. ^ Стоукс, Мэтью Э.; Висвесваран, Шьям (2012-12-03). «Применение пространственно-взвешенного алгоритма Relief для ранжирования генетических предикторов заболеваний». BioData Mining . 5 (1): 20. doi : 10.1186/1756-0381-5-20 . ISSN  1756-0381. PMC 3554553. PMID 23198930  . 
  24. ^ ab Granizo-Mackenzie, Delaney; Moore, Jason H. (2013-04-03). "Multiple Threshold Spatially Uniform ReliefF for the Genetic Analysis of Complex Human Diseases". Эволюционные вычисления, машинное обучение и интеллектуальный анализ данных в биоинформатике . Конспект лекций по информатике. Том 7833. Springer, Берлин, Гейдельберг. С. 1–10. doi :10.1007/978-3-642-37189-9_1. ISBN 9783642371882.
  25. ^ МакКинни, Бретт А.; Уайт, Билл К.; Грилл, Дайан Э.; Ли, Питер В.; Кеннеди, Ричард Б.; Поланд, Грегори А.; Оберг, Энн Л. (10.12.2013). "ReliefSeq: инструмент выбора признаков ближайшего соседа с учетом генов и поиска взаимодействий генов и основных эффектов в данных по экспрессии генов mRNA-Seq". PLOS ONE . 8 (12): e81527. Bibcode : 2013PLoSO...881527M. doi : 10.1371/journal.pone.0081527 . ISSN  1932-6203. PMC 3858248. PMID 24339943  . 
  26. ^ Ле, Транг; Урбанович, Райан; Мур, Джейсон; МакКинни, Бретт (18 сентября 2018 г.). «Выбор признаков STatistical Inference Relief (STIR)». Биоинформатика . 35 (8): 1358–1365. doi :10.1093/bioinformatics/bty788. PMC 6477983. PMID  30239600 . 
  27. ^ Le, Trang (1 ноября 2018 г.). "STIR Poster". Figshare . doi :10.6084/m9.figshare.7241417 . Получено 24 января 2019 г. .