Перегляд вихідного коду сторінки Обирання ознак

{{short description|процедура в машинному навчанні та статистиці}}
{{Машинне навчання|Задачі}}

В [[Машинне навчання|машинному навчанні]] та [[Статистика|статистиці]] '''обира́ння озна́к''', відоме також як '''обира́ння змі́нних''', '''обира́ння атрибу́тів''' та '''обира́ння підмножини́ змі́нних''' ({{lang-en|feature selection, variable selection, attribute selection, variable subset selection}})&nbsp;— це процес обирання підмножини доречних [[Ознака (машинне навчання)|ознак]] (змінних, провісників) для використання в побудові моделі. Методики обирання ознак застосовують із декількома цілями:

:* спрощення моделей, щоби зробити їх легшими для інтерпретування дослідниками/користувачами,<ref name="islr">{{cite book |author1=Gareth James |author2=Daniela Witten |author3=Trevor Hastie |author4=Robert Tibshirani |title=An Introduction to Statistical Learning |publisher=Springer |year=2013 |url=http://www-bcf.usc.edu/~gareth/ISL/ |page=204 |accessdate=2016-01-20 |archive-date=2019-06-23 |archive-url=https://web.archive.org/web/20190623150237/http://www-bcf.usc.edu/~gareth/ISL/ }} {{ref-en}}</ref>
:* скорочення тривалостей тренування,
:* уникання [[прокляття розмірності]],
:* покращення узагальнення шляхом зниження [[перенавчання]]<ref name="Bermingham-prolog">{{cite journal |title= Application of high-dimensional feature selection: evaluation for genomic prediction in man |first1=Mairead L. |last1=Bermingham |first2=Ricardo |last2=Pong-Wong | first3=Athina|last3=Spiliopoulou | first4=Caroline|last4=Hayward |first5=Igor|last5=Rudan |first6=Harry|last6=Campbell |first7=Alan F.|last7=Wright |first8=James F.|last8=Wilson |first9=Felix |last9=Agakov |first10=Pau|last10=Navarro |first11=Chris S.|last11=Haley |journal=[[Scientific Reports|[[Sci. Rep.]]]] |volume=5 |year=2015 |doi=10.1038/srep10312 |pmid=25988841 |pmc=4437376 |page=10312|bibcode=2015NatSR...510312B}} {{ref-en}}</ref> (формально, зниження [[Компроміс зсуву та дисперсії|дисперсії]]{{r|islr}}).

Центральною передумовою при застосуванні методики обирання ознак є те, що дані містять деякі ознаки, що є або ''надлишковими'', або ''недоречними'', і тому їх може бути усунено без спричинення значної втрати інформації.<ref name="Bermingham-prolog"/> «Надлишкові» та «недоречні» є двома різними поняттями, оскільки одна доречна ознака може бути надлишковою в присутності іншої доречної ознаки, з якою вона сильно [[Кореляція|корелює]].{{r|guyon-intro}}

Методики обирання ознак слід відрізняти від [[виділяння ознак]]. Виділяння ознак створює нові ознаки з функцій від первинних ознак, тоді як обирання ознак повертає підмножину ознак.
Методики обирання ознак часто використовують у тих областях, де є багато ознак, і порівняно мало зразків (або точок даних). До споконвічних випадків застосування обирання ознак належать аналіз [[Стильометрія|писаних текстів]] та даних [[ДНК-мікрочип]]ів, де є багато тисяч ознак, і лише від декількох десятків до сотень зразків.

== Введення ==

Алгоритм обирання ознак можливо розглядати як поєднання методики пошуку для пропонування нових підмножин ознак разом із мірою оцінки, яка встановлює бали різним підмножинам ознак. Найпростішим алгоритмом є перевіряти кожну можливу підмножину ознак, шукаючи таку, яка мінімізує рівень похибки. Це є вичерпним пошуком цим простором, і є обчислювально непіддатливим для будь-яких множин ознак, крім найменших. Вибір оцінювальної метрики сильно впливає на алгоритм, і саме ці оцінювальні метрики відрізняють три основні категорії алгоритмів пошуку ознак: обгорткові, фільтрові та вбудовані методи.<ref name="guyon-intro">{{cite journal |title=An Introduction to Variable and Feature Selection |first1=Isabelle |last1=Guyon |first2=André |last2=Elisseeff |journal=[[Journal of Machine Learning Research|JMLR]] |volume=3 |year=2003 |url=http://jmlr.csail.mit.edu/papers/v3/guyon03a.html}} {{ref-en}}</ref>

* Обгорткові методи для встановлення балів підмножинам ознак використовують передбачувальну модель. Кожну нову підмножину використовують для тренування моделі, яку перевіряють на [[Притриманий набір|притриманій множині]]. Підрахунок кількості помилок, зроблених на цій притриманій множині (рівень похибки моделі) дає бал цієї підмножини. Оскільки обгорткові методи тренують нову модель для кожної підмножини, вони є дуже обчислювально напруженими, але зазвичай пропонують множину ознак із найкращою продуктивністю для того окремого типу моделі.
* Фільтрові методи для встановлення балів підмножинам ознак замість рівня похибки використовують міру-заступницю. Цю міру обирають такою, щоби вона була швидкою, але все ще схоплювала корисність множини ознак. До поширених мір належать [[взаємна інформація]],<ref name="guyon-intro"/> [[поточкова взаємна інформація]],<ref name="textcat"/> [[коефіцієнт кореляції Пірсона]], {{нп|Relief (обирання ознак)|алгоритми на основі ''Relief''||Relief (feature selection)}}<ref>{{Cite arxiv|last=Urbanowicz|first=Ryan J.|last2=Meeker|first2=Melissa|last3=LaCava|first3=William|last4=Olson|first4=Randal S.|last5=Moore|first5=Jason H.|date=2017-11-22|title=Relief-Based Feature Selection: Introduction and Review|eprint=1711.08421|class=cs.DS}} {{ref-en}}</ref> та внутрішньо/міжкласова відстань або бали [[Критерій значущості|критеріїв значущості]] для кожної комбінації клас/ознака.<ref name="textcat">{{cite conference |last1=Yang |first1=Yiming |first2=Jan O. |last2=Pedersen |title=A comparative study on feature selection in text categorization |conference=ICML |year=1997|url=http://www.surdeanu.info/mihai/teaching/ista555-spring15/readings/yang97comparative.pdf}} {{ref-en}}</ref><ref>{{cite journal |last1=Forman |first1=George |title=An extensive empirical study of feature selection metrics for text classification |journal=Journal of Machine Learning Research |volume=3 |year=2003 |pages=1289–1305|url=http://www.jmlr.org/papers/volume3/forman03a/forman03a.pdf}} {{ref-en}}</ref> Фільтри зазвичай є менш напруженими обчислювально за обгортки, але вони пропонують набір ознак, що не налаштовано на конкретний тип передбачувальної моделі.<ref>{{cite journal|author1=Yishi Zhang|author2=Shujuan Li|author3=Teng Wang|author4=Zigang Zhang|title=Divergence-based feature selection for separate classes|journal=Neurocomputing|date=2013|volume=101|issue=4|pages=32–42|doi=10.1016/j.neucom.2012.06.036}} {{ref-en}}</ref> Цей брак налаштування означає, що набір ознак від фільтра є загальнішим за набір від обгортки, зазвичай даючи нижчу передбачувальну продуктивність, ніж обгортка. Проте такий набір ознак не містить припущень передбачувальної моделі, і тому є кориснішим для розкриття взаємозв'язків між ознаками. Багато фільтрів пропонують ранжування ознак замість явної найкращої підмножини ознак, а точку відсікання в рангу обирають за допомогою [[Перехресне затверджування|перехресного затверджування]]. Фільтрові методи також застосовували як передобробний етап для обгорткових методів, роблячи можливим застосування обгорток до більших задач. Одним з інших популярних підходів є алгоритм рекурсивного усунення ознак ({{lang-en|Recursive Feature Elimination}}),<ref>{{cite journal|author1=Guyon I.|author2=Weston J.|author3=Barnhill S.|author4=Vapnik V.|title=Gene selection for cancer classification using support vector machines|journal=Machine Learning|date=2002|volume=46|issue=1-3|pages=389–422|doi=10.1023/A:1012487302797}} {{ref-en}}</ref> зазвичай застосовуваний з [[Метод опорних векторів|методом опорних векторів]] для повторної побудови моделі та усунення ознак з низькими ваговими коефіцієнтами.
* Вбудовані методи є всеосяжною групою методик, що виконують обирання ознак як частину процесу побудови моделі. Примірником цього підходу є метод побудови лінійних моделей {{нп|LASSO|''LASSO''||Lasso (statistics)}}, який штрафує [[Лінійна регресія|коефіцієнти регресії]] штрафом ''L1'', скорочуючи багато з них до нуля. Будь-які ознаки, що мають ненульові коефіцієнти регресії, є «обраними» алгоритмом ''LASSO''. До покращень ''LASSO'' належать ''Bolasso'', яке [[Бутстрепова агрегація|бутстрепує]] вибірки,<ref name=Bolasso>{{Cite book|last1=Bach|first1=Francis R|title=Bolasso: model consistent lasso estimation through the bootstrap|journal=Proceedings of the 25th International Conference on Machine Learning|date=2008|pages=33–40|doi=10.1145/1390156.1390161|isbn=9781605582054}} {{ref-en}}</ref>, {{нп|еластично-сіткова регуляризація|||Elastic net regularization}}, яка поєднує штраф ''L1'' ''LASSO'' із штрафом ''L2'' [[Гребенева регресія|гребеневої регресії]], та ''FeaLect'', яке встановлює бали всім ознакам на основі комбінаторного аналізу коефіцієнтів регресії.<ref name=FeaLect>{{cite journal|last1=Zare|first1=Habil|title=Scoring relevancy of features based on combinatorial analysis of Lasso with application to lymphoma diagnosis|journal=BMC Genomics|date=2013|volume=14|pages=S14|doi=10.1186/1471-2164-14-S1-S14|pmid=23369194|pmc=3549810}} {{ref-en}}</ref> Ці підходи з погляду обчислювальної складності тяжіють до знаходження між фільтрами та обгортками.

У традиційному [[Регресійний аналіз|регресійному аналізі]] найпопулярнішим видом обирання ознак є {{нп|поетапна регресія|||Stepwise regression}}, яка є обгортковою методикою. Це [[жадібний алгоритм]], що під час кожного раунду додає найкращу ознаку (або видаляє найгіршу). Головним питанням у керуванні є вирішування, коли зупинити алгоритм. У машинному навчанні це зазвичай здійснюють за допомогою [[Перехресне затверджування|перехресного затверджування]]. У статистиці деякі критерії є оптимізованими. Це призводить до проблеми, притаманної вкладеності. Було досліджено надійніші методи, такі як [[Метод гілок і меж|гілки і межі]], та кусково-лінійна мережа.

== Обирання підмножин ==

Обирання підмножини оцінює на придатність підмножину ознак як групу. Алгоритми обирання підмножин можливо розділити на обгорткові, фільтрові та вбудовані методи. Обгорткові використовують пошуковий алгоритм для пошуку простором можливих ознак, і оцінки кожної підмножини запуском моделі на ній. Обгортки можуть бути обчислювально витратними, і мати ризик перенавчитися моделі. Фільтри є схожими на обгортки в підході до пошуку, але замість оцінки проти моделі виводять простіший фільтр. Вбудовані методики є вбудованими в модель, і особливими для моделі.

Багато популярних підходів до пошуку використовують [[Жадібний алгоритм|жадібний]] [[Алгоритм сходження на вершину|підйом схилом]], що ітеративно оцінює кандидата-підмножину ознак, а потім змінює цю підмножину й оцінює, чи є нова підмножина покращенням відносно старої. Оцінка підмножин вимагає оцінкової [[Метрика (математика)|метрики]], що реалізує градацію підмножин ознак. Вичерпний пошук в загальному випадку є непрактичним, тому на певній визначеній реалізатором (або оператором) точці зупинки підмножину ознак із найвищим знайденим до цієї точки балом обирають задовільною підмножиною ознак. Критерій зупинки залежить від алгоритму; до можливих критеріїв належать: перевищення порогу балом підмножини, перевищення максимального допустимого часу виконання програми тощо.

Альтернативні методики на основі пошуку ґрунтуються на {{нп|Націлений пошук найкращої проєкції|націленому пошуку найкращої проєкції||Targeted projection pursuit}}, який знаходить низькорозмірні проєкції даних, що мають високий бал: тоді обирають ознаки, що мають найбільші проєкції в низькорозмірному просторі.

До пошукових підходів належать:

* Вичерпний
* [[Пошук за першим найкращим збігом|Перший-ліпший]]
* [[Алгоритм імітації відпалу|Імітація відпалу]]
* [[Генетичний алгоритм]]<ref>{{Cite journal|last=Soufan|first=Othman|last2=Kleftogiannis|first2=Dimitrios|last3=Kalnis|first3=Panos|last4=Bajic|first4=Vladimir B.|date=2015-02-26|title=DWFS: A Wrapper Feature Selection Tool Based on a Parallel Genetic Algorithm|journal=PLOS One|language=en|volume=10|issue=2|pages=e0117988|doi=10.1371/journal.pone.0117988|pmid=25719748|pmc=4342225|issn=1932-6203|bibcode=2015PLoSO..1017988S}} {{ref-en}}</ref>
* [[Жадібний алгоритм|Жадібне]] поступальне обирання ({{lang-en|Greedy forward selection}})<ref>{{cite journal|last1=Figueroa|first1=Alejandro|title=Exploring effective features for recognizing the user intent behind web queries|journal=Computers in Industry|date=2015|volume=68|pages=162–169|url=https://www.researchgate.net/publication/271911317|doi=10.1016/j.compind.2015.01.005}} {{ref-en}}</ref><ref>{{cite conference |last=Figueroa|first=Alejandro |author2=Guenter Neumann  |url=https://www.researchgate.net/publication/259174469_Learning_to_Rank_Effective_Paraphrases_from_Query_Logs_for_Community_Question_Answering  |title=Learning to Rank Effective Paraphrases from Query Logs for Community Question Answering |conference= AAAI |year=2013}} {{ref-en}}</ref><ref>{{cite journal|last=Figueroa|first=Alejandro |author2=Guenter Neumann|title=Category-specific models for ranking effective paraphrases in community Question Answering|journal=Expert Systems with Applications|date=2014|volume=41|issue=10 |pages=4730–4742|url=https://www.researchgate.net/publication/260519271|doi=10.1016/j.eswa.2014.02.004}} {{ref-en}}</ref>
* Жадібне зворотне усунення ({{lang-en|Greedy backward elimination}})
* [[Метод рою часток]]<ref name="sciencedirect.com">{{cite journal|last1=Zhang|first1=Y.|last2=Wang|first2=S.|last3=Phillips|first3=P.|title=Binary PSO with Mutation Operator for Feature Selection using Decision Tree applied to Spam Detection|journal=Knowledge-Based Systems|date=2014|volume=64|pages=22–31|doi=10.1016/j.knosys.2014.03.015}} {{ref-en}}</ref>
* {{нп|Націлений пошук найкращої проєкції|||Targeted projection pursuit}}
* Пошук врозсип ({{lang-en|Scatter Search}})<ref>F.C. Garcia-Lopez, M. Garcia-Torres, B. Melian, J.A. Moreno-Perez, J.M. Moreno-Vega. [https://jamoreno.webs.ull.es/www/papers/EJOR06.pdf Solving feature subset selection problem by a Parallel Scatter Search], ''European Journal of Operational Research'', vol. 169, no. 2, pp. 477–489, 2006.
{{ref-en}}</ref>
* {{нп|Пошук змінними околами|||Variable neighborhood search}}<ref>F.C. Garcia-Lopez, M. Garcia-Torres, B. Melian, J.A. Moreno-Perez, J.M. Moreno-Vega. [https://pdfs.semanticscholar.org/9428/2985d2c2ea4eb9f49846bedc12003a47db49.pdf Solving Feature Subset Selection Problem by a Hybrid Metaheuristic] {{Webarchive|url=https://web.archive.org/web/20190830132140/https://pdfs.semanticscholar.org/9428/2985d2c2ea4eb9f49846bedc12003a47db49.pdf |date=30 серпня 2019 }}. In ''First International Workshop on Hybrid Metaheuristics'', pp. 59–68, 2004. {{ref-en}}</ref><ref>M. Garcia-Torres, F. Gomez-Vela, B. Melian, J.M. Moreno-Vega. [https://www.researchgate.net/profile/Miguel_Garcia_Torres/publication/229763203_Parallel_Scatter_Search/links/5b2788a00f7e9be8bdaeb0d0/Parallel-Scatter-Search.pdf High-dimensional feature selection via feature grouping: A Variable Neighborhood Search approach], ''Information Sciences'', vol. 326, pp. 102-118, 2016. {{ref-en}}</ref>

Двома популярними фільтровими метриками для [[Задача класифікації|задач класифікації]] є [[кореляція]] та [[взаємна інформація]], хоча жодна з них не є справжньою [[Метрика (математика)|метрикою]], або «мірою відстані», в математичному сенсі, оскільки вони не підкоряються [[Нерівність трикутника|нерівності трикутника]], і відтак не обчислюють жодної дійсної «відстані»&nbsp;— їх слід було би швидше розглядати як «бали». Ці бали обчислюють між ознаками-кандидатами (або наборами ознак) та бажаною категорією виходу. Проте існують і справжні метрики, що є простою функцією взаємної інформації;<ref>{{Cite journal|arxiv=q-bio/0311039|last1=Kraskov|first1=Alexander|title=Hierarchical Clustering Based on Mutual Information|last2=Stögbauer|first2=Harald|last3=Andrzejak|first3=Ralph G|last4=Grassberger|first4=Peter|year=2003|bibcode=2003q.bio....11039K}} {{ref-en}}</ref> див. [[Метрика взаємної інформації|тут]].

До інших доступних фільтрових метрик належать:

* Віддільність класів ({{lang-en|class separability}})
** Імовірність похибки ({{lang-en|error probability}})
** Міжкласова відстань ({{lang-en|inter-class distance}})
** Імовірнісна відстань ({{lang-en|probabilistic distance}})
** [[Інформаційна ентропія]]
* Обирання ознак на основі узгодженості ({{lang-en|consistency-based feature selection}})
* Обирання ознак на основі кореляції ({{lang-en|correlation-based feature selection}})

== Критерій оптимальності ==

Обирання критерію оптимальності є складним, оскільки в завдання обирання ознак є кілька цілей. Багато поширених критеріїв включають міру точності, штрафовану кількістю обраних ознак. До прикладів належать [[інформаційний критерій Акаіке]] (ІКА, {{lang-en|AIC}}) та {{нп|Cp Меллоуза|''C<sub>p</sub>'' Меллоуза||Mallows's Cp}}, що мають штраф у <math>2</math> для кожної доданої ознаки. ІКА ґрунтується на [[Теорія інформації|теорії інформації]], й практично виводиться з {{нп|Принцип максимуму ентропії|принципу максимуму ентропії||Principle of maximum entropy}}.<ref>{{Citation | first= H. | last= Akaike | authorlink= Хіроцуґу Акаіке | contribution= Prediction and entropy | pages= 1–24 | title= A Celebration of Statistics | editor1-first= A. C. | editor1-last= Atkinson | editor2-first= S. E. | editor2-last= Fienberg | editor2-link= Стівен Фейнберг | year= 1985 | publisher= Springer | url= https://apps.dtic.mil/dtic/tr/fulltext/u2/a120956.pdf | accessdate= 2019-09-08 | archive-date= 2019-08-30 | archive-url= https://web.archive.org/web/20190830132141/https://apps.dtic.mil/dtic/tr/fulltext/u2/a120956.pdf | url-status= dead }}. {{ref-en}}</ref><ref>{{Citation |last=Burnham |first=K. P. |last2=Anderson |first2=D. R. |year=2002 |title=Model Selection and Multimodel Inference: A practical information-theoretic approach |edition=2nd |publisher= [[Springer-Verlag]] |url=https://books.google.com/books?id=fT1Iu-h6E-oC&printsec=frontcover#v=onepage&q=%22maximum%20entropy%22&f=false}}. {{ref-en}}</ref>

Іншими критеріями є [[баєсів інформаційний критерій]] (БІК, {{lang-en|BIC}}), що використовує штраф у <math>\sqrt{\log{n}}</math> для кожної доданої ознаки, принцип [[Мінімальна довжина опису|мінімальної довжини опису]] (МДО, {{lang-en|MDL}}), що асимптотично використовує <math>\sqrt{\log{n}}</math>, {{нп|Бонферроні|||Bonferroni}} / {{H:title|Критерій роздування ризику|КРР}} ({{lang-en|{{H:title|Risk Inflation Criterion|RIC}}}}), який використовує <math>\sqrt{2\log{p}}</math>, обирання ознак максимальної залежності ({{lang-en|maximum dependency feature selection}}) та ряд нових критеріїв, обґрунтованих {{нп|Рівень хибного виявляння|рівнем хибного виявляння||False discovery rate}} ({{lang-en|false discovery rate, FDR}}), який використовує щось близьке до <math>\sqrt{2\log{\frac{p}{q}}}</math>. Для обирання найвідповіднішої множини ознак можна також використовувати й критерій максимальної [[Ентропійна швидкість|ентропійної швидкості]].<ref>{{cite journal |last1=Einicke |first1=G. A. |title=Maximum-Entropy Rate Selection of Features for Classifying Changes in Knee and Ankle Dynamics During Running |journal=IEEE Journal of Biomedical and Health Informatics |volume=28 |issue=4 |pages=1097–1103 |year=2018 |doi= 10.1109/JBHI.2017.2711487 |pmid=29969403 }} {{ref-en}}</ref>

== Навчання структури ==

Фільтрове обирання ознак є окремим випадком загальнішої парадигми, що називають [[Навчання структури|навчанням структури]]. Обирання ознак знаходить доречний набір ознак для конкретної цільової змінної, тоді як навчання структури знаходить взаємозв'язки між усіма змінними, зазвичай виражаючи ці взаємозв'язки як граф. Найпоширеніші алгоритми навчання структури виходять із того, що дані було породжено [[Баєсова мережа|баєсовою мережею]], і тому структурою є [[Орієнтований граф|орієнтована]] [[графова модель]]. Оптимальним розв'язком задачі фільтрового обирання ознак є [[марковське покриття]] цільового вузла, і в баєсовій мережі існує єдине марковське покриття для кожного вузла.<ref>{{cite journal|last1=Aliferis|first1=Constantin|title=Local causal and markov blanket induction for causal discovery and feature selection for classification part I: Algorithms and empirical evaluation|journal=Journal of Machine Learning Research|date=2010|volume=11|pages=171–234|url=http://jmlr.org/papers/volume11/aliferis10a/aliferis10a.pdf}} {{ref-en}}</ref>

== Механізми обирання ознак на основі теорії інформації ==

Існують різні механізми обирання ознак, що для оцінювання різних ознак використовують [[Взаємна інформація|взаємну інформацію]]. Вони зазвичай використовують один і той же алгоритм:

# Обчислити [[Взаємна інформація|взаємну інформацію]] як оцінку між усіма ознаками (<math> f_{i} \in F </math>) та цільовим класом ( <math> c </math> )
# Обрати ознаку з найвищим балом (наприклад, <math>argmax_{f_{i} \in F}(I(f_{i},c))</math>), і додати її до набору обраних ознак (<math> S </math>)
# Обчислити похідну оцінку, яку може бути виведено із [[Взаємна інформація|взаємної інформації]]
# Обрати ознаку з найвищим балом, і додати її до набору обраних ознак (наприклад, <math>argmax_{f_{i} \in F}(I_{derived}(f_{i},c))</math> )
# Повторювати 3. та 4., допоки не буде обрано певне число ознак (наприклад, <math>|S|=l</math> )

Найпростіший підхід як цю «похідну» оцінку використовує власне [[Взаємна інформація|взаємну інформацію]].<ref name="Brown">{{cite journal|last1=Brown|first1=Gavin|last2=Pocock|first2=Adam|last3=Zhao|first3=Ming-Jie|last4=Luján|first4=Mikel|date=2012|title=Conditional Likelihood Maximisation: A Unifying Framework for Information Theoretic Feature Selection|url=http://dl.acm.org/citation.cfm?id=2188385.2188387|journal=[[Journal of Machine Learning Research]]|volume=13|pages=27–66}}[http://www.jmlr.org/papers/volume13/brown12a/brown12a.pdf] {{ref-en}}</ref>

Проте існують різні підходи, що намагаються знижувати надлишковість серед ознак.

=== Обирання ознак мінімальної-надлишковості-максимальної-доречності (''mRMR'') ===

Пен та ін.<ref>{{cite journal |last1=Peng |first1=H. C. |last2=Long |first2=F. |last3=Ding |first3=C. |title=Feature selection based on mutual information: criteria of max-dependency, max-relevance, and min-redundancy |journal={{нп|IEEE Transactions on Pattern Analysis and Machine Intelligence}} |volume=27 |issue=8 |pages=1226–1238 |year=2005 |doi=10.1109/TPAMI.2005.159 |pmid=16119262|citeseerx=10.1.1.63.5765 }} {{ref-en}} [http://home.penglab.com/proj/mRMR/index.htm Програма]</ref> запропонували метод обирання ознак, що може використовувати для обирання ознак або взаємну інформацію, кореляцію, або відстань/бали схожості. Мета полягає у штрафуванні доречності ({{lang-en|relevancy}}) ознаки її надлишковістю ({{lang-en|redundancy}}) в присутності інших обраних ознак. Доречність набору ознак {{mvar|S}} для класу {{mvar|c}} визначають усередненим значенням усіх значень взаємної інформації між окремою ознакою {{math|''f<sub>i</sub>''}} та класом {{mvar|c}} таким чином:

: <math> D(S,c) = \frac{1}{|S|}\sum_{f_{i}\in S}I(f_{i};c) </math>.

Надлишковістю всіх ознак у множині {{mvar|S}} є усереднене значення всіх значень взаємної інформації між ознакою {{math|''f<sub>i</sub>''}} та ознакою {{math|''f<sub>j</sub>''}}:

: <math> R(S) = \frac{1}{|S|^{2}}\sum_{f_{i},f_{j}\in S}I(f_{i};f_{j})</math>

Критерій мінімальної-надлишковості-максимальної-доречності ({{lang-en|minimum-redundancy-maximum-relevance, mRMR}}) є поєднанням двох наведених вище мір, і його визначено наступним чином:

: <math>\mathrm{mRMR}= \max_{S}
\left[\frac{1}{|S|}\sum_{f_{i}\in S}I(f_{i};c) - 
\frac{1}{|S|^{2}}\sum_{f_{i},f_{j}\in S}I(f_{i};f_{j})\right].</math>

Припустімо, що є {{mvar|n}} ознак повної множини. Нехай {{math|''x<sub>i</sub>''}} буде [[Індикаторна функція|індикаторною функцією]] членства ознаки {{math|''f<sub>i</sub>''}} в множині, такою, що {{math|1=''x<sub>i</sub>''=1}} показує наявність, а {{math|1=''x<sub>i</sub>''=0}} показує відсутність ознаки {{math|''f<sub>i</sub>''}} в глобально оптимальній множині ознак. Нехай <math>c_i=I(f_i;c)</math>, а <math>a_{ij}=I(f_i;f_j)</math>. Наведене вище може бути записано як задачу оптимізації:

: <math>\mathrm{mRMR}= \max_{x\in \{0,1\}^{n}} 
\left[\frac{\sum^{n}_{i=1}c_{i}x_{i}}{\sum^{n}_{i=1}x_{i}} -
\frac{\sum^{n}_{i,j=1}a_{ij}x_{i}x_{j}}
{(\sum^{n}_{i=1}x_{i})^{2}}\right].</math>

Алгоритм ''mRMR'' є наближенням теоретично оптимального максимально-залежнісного алгоритму обирання ознак, який максимізує взаємну інформацію між спільним розподілом обраних ознак та змінною класифікації. Оскільки ''mRMR'' наближує задачу комбінаторної оцінки рядом набагато менших задач, кожна з яких включає лише дві змінні, він таким чином використовує попарні спільні ймовірності, що є надійнішими. В деяких ситуаціях цей алгоритм може недооцінювати корисність ознак, оскільки він не має способу вимірювати взаємодії між ознаками, що можуть збільшувати доречність. Це може призводити до поганої продуктивності,<ref name="Brown" /> коли ознаки є марними поодинці, але корисними у поєднанні (патологічний випадок трапляється, коли клас є {{нп|Функція парності|функцією парності||Parity function}} ознак). В цілому цей алгоритм є ефективнішим (у термінах кількості потрібної інформації) за теоретично оптимальне максимально-залежнісне обирання, хоча й виробляє набір ознак із невеликою попарною надлишковістю.

''mRMR'' є примірником більшого класу фільтрових методів, які шукають компроміс між доречністю та надлишковістю відмінними шляхами.<ref name="Brown" /><ref name="docs.google">Nguyen, H., Franke, K., Petrovic, S. (2010). "Towards a Generic Feature-Selection Measure for Intrusion Detection", In Proc. International Conference on Pattern Recognition (ICPR), Istanbul, Turkey. [https://www.researchgate.net/publication/220928649_Towards_a_Generic_Feature-Selection_Measure_for_Intrusion_Detection?ev=prf_pub] {{ref-en}}</ref>

=== Обирання ознак квадратичним програмуванням ===

''mRMR'' є типовим прикладом приростової жадібної стратегії обирання ознак: щойно ознаку було обрано, її не може бути виключено на пізнішому етапі. І хоча ''mRMR'' може бути оптимізовано застосуванням рухливого пошуку ({{lang-en|floating search}}) для скорочування деяких ознак, його також може бути переформульовано як задачу глобальної оптимізації [[Квадратичне програмування|квадратичного програмування]] ({{lang-en|quadratic programming feature selection, QPFS}}) таким чином:<ref name="QPFS">{{cite journal |first1=I. |last1=Rodriguez-Lujan |first2=R. |last2=Huerta |first3=C. |last3=Elkan |first4=C. |last4=Santa Cruz |title=Quadratic programming feature selection |journal=[[Journal of Machine Learning Research|JMLR]] |volume=11 |pages=1491–1516 |year=2010 |url=http://jmlr.csail.mit.edu/papers/volume11/rodriguez-lujan10a/rodriguez-lujan10a.pdf}} {{ref-en}}</ref>

: <math>
\mathrm{QPFS}: \min_\mathbf{x}  \left\{ \alpha \mathbf{x}^T H \mathbf{x} -  \mathbf{x}^T F\right\} \quad </math> т.&nbsp;щ. <math> \ \sum_{i=1}^n x_i=1, x_i\geq 0
</math>

де <math>F_{n\times1}=[I(f_1;c),\ldots, I(f_n;c)]^T</math> є вектором доречності ознак, за припущення, що загалом є {{mvar|n}} ознак, <math>H_{n\times n}=[I(f_i;f_j)]_{i,j=1\ldots n}</math> є матрицею попарної надлишковості ознак, а <math>\mathbf{x}_{n\times 1}</math> представляє відносні ваги ознак. ''QPFS'' розв'язується за допомогою [[Квадратичне програмування|квадратичного програмування]]. Нещодавно було показано, що ''QPFS'' має схильність до ознак із меншою ентропією,<ref name="CMI" /> тому що воно ставить член самонадлишковості ознаки <math>I(f_i;f_i)</math> на діагональ {{mvar|H}}.

=== Умовна взаємна інформація ===

Інша оцінка, що виводять із взаємної інформації, ґрунтується на умовній доречності:<ref name="CMI">Nguyen X. Vinh, Jeffrey Chan, Simone Romano and James Bailey, "Effective Global Approaches for Mutual Information based Feature Selection". Proceedings of the 20th ACM SIGKDD Conference on Knowledge Discovery and Data Mining (KDD'14), August 24–27, New York City, 2014. "[http://people.eng.unimelb.edu.au/baileyj/papers/frp0038-Vinh.pdf]" {{ref-en}}</ref>

: <math>
\mathrm{SPEC_{CMI}}: \max_{\mathbf{x}} \left\{\mathbf{x}^T Q \mathbf{x}\right\} \quad </math> т.&nbsp;щ. <math>\ \|\mathbf{x}\|=1, x_i\geq 0
</math>

де <math>Q_{ii}=I(f_i;c)</math>, а <math>Q_{ij}=I(f_i;c|f_j), i\ne j</math>.

Перевага {{math|SPEC<sub>CMI</sub>}} полягає в тому, що воно може розв'язуватися просто знаходженням домінантного власного вектора {{mvar|Q}}, і тому є дуже масштабовуваним. Також {{math|SPEC<sub>CMI</sub>}} обробляє взаємодії ознак другого порядку.

=== Спільна взаємна інформація ===

У дослідженні різних балів Браун та ін.<ref name="Brown" /> рекомендували як добрий бал для обирання ознак {{нпні|Спільна взаємна інформація|спільну взаємну інформацію||Joint mutual information}}.<ref>{{cite journal |last1=Yang |first1=Howard Hua |last2=Moody |first2=John |title=Data visualization and feature selection: New algorithms for nongaussian data |journal=Advances in Neural Information Processing Systems |date=2000 |pages=687–693 |url=https://papers.nips.cc/paper/1779-data-visualization-and-feature-selection-new-algorithms-for-nongaussian-data.pdf}} {{ref-en}}</ref> Цей бал намагається знайти ознаку, що додає найбільше нової інформації до вже відомих ознак, щоби уникати надмірності. Цей бал сформульовано наступним чином:

<math>
\begin{align}
JMI(f_i) &= \sum_{f_j \in S} (I(f_i;c) + I(f_i;c|f_j)) \\
         &= \sum_{f_j \in S} \bigl[ I (f_j;c) + I (f_i;c) - \bigl(I (f_i;f_j) - I (f_i;f_j|c)\bigr)\bigr]
\end{align}
</math>

Цей бал використовує {{нп|Умовна взаємна інформація|умовну взаємну інформацію||Conditional mutual information}} для оцінювання надмірності між вже обраними ознаками (<math> f_j \in S </math>) та досліджуваною ознакою (<math>f_i</math>).

== Обирання ознак на основі ''LASSO'' критерію незалежності Гільберта-Шмідта ==

Для даних із високою розмірністю та малою вибіркою (наприклад, розмірність > 10<sup>5</sup>, а кількість зразків < 10<sup>3</sup>) корисним є {{нп|LASSO|''LASSO''||Lasso (statistics)}} критерію незалежності Гільберта-Шмідта ({{lang-en|Hilbert-Schmidt Independence Criterion Lasso, HSIC Lasso}}).<ref name="HSICLasso">M. Yamada, W. Jitkrittum, L. Sigal, E. P. Xing, M. Sugiyama, High-Dimensional Feature Selection by Feature-Wise Non-Linear Lasso. ''Neural Computation'', vol.26, no.1, pp.185-207, 2014. {{ref-en}}</ref> Задачу оптимізації ''HSIC Lasso'' задають як

: <math>
\mathrm{HSIC_{Lasso}}: \min_{\mathbf{x}} \frac{1}{2}\sum_{k,l = 1}^n x_k x_l {\mbox{HSIC}}(f_k,f_l) - \sum_{k = 1}^n x_k {\mbox{HSIC}}(f_k,c) +  \lambda \|\mathbf{x}\|_1, \quad </math> т.&nbsp;щ. <math> \ x_1,\ldots, x_n \geq 0,
</math>

де <math>{\mbox{HSIC}}(f_k,c) =\mbox{tr}(\bar{\mathbf{K}}^{(k)}  \bar{\mathbf{L}})</math> є мірою незалежності на ядровій основі, що називають (емпіричним) критерієм незалежності Гільберта-Шмідта ({{lang-en|Hilbert-Schmidt independence criterion, HSIC}}), <math>\mbox{tr}(\cdot)</math> позначає [[Слід матриці|слід]], <math>\lambda</math> є регуляризаційним параметром, <math>\bar{\mathbf{K}}^{(k)} = \mathbf{\Gamma} \mathbf{K}^{(k)} \mathbf{\Gamma}</math> та <math>\bar{\mathbf{L}} = \mathbf{\Gamma} \mathbf{L} \mathbf{\Gamma}</math> є центрованими [[Матриця Грама|матрицями Ґрама]] входу та виходу, <math>K^{(k)}_{i,j} = K(u_{k,i},u_{k,j})</math> та <math>L_{i,j} = L(c_i,c_j)</math> є матрицями Ґрама, <math>K(u,u')</math> та <math>L(c,c')</math> є ядровими функціями, <math>\mathbf{\Gamma} = \mathbf{I}_m - \frac{1}{m}\mathbf{1}_m \mathbf{1}_m^T</math> є центрувальною матрицею, <math>\mathbf{I}_m</math> є {{mvar|m}}-вимірною [[Одинична матриця|одиничною матрицею]] ({{mvar|m}}&nbsp;— кількість зразків), <math>\mathbf{1}_m</math> є {{mvar|m}}-вимірним вектором з усіма одиницями, а <math>\|\cdot\|_{1}</math> є <math>\ell_1</math>-нормою. ''HSIC'' завжди набуває невід'ємного значення, і є нулем [[тоді й лише тоді]], коли дві випадкові змінні є статистично незалежними при використанні універсального відтворювального ядра, такого як ґаусове.

''HSIC Lasso'' також може бути записано як

: <math>
\mathrm{HSIC_{Lasso}}: \min_{\mathbf{x}} \frac{1}{2}\left\|\bar{\mathbf{L}} - \sum_{k = 1}^{n} x_k \bar{\mathbf{K}}^{(k)} \right\|^2_{F}  +  \lambda \|\mathbf{x}\|_1, \quad </math> т.&nbsp;щ. <math> \ x_1,\ldots,x_n \geq 0,
</math>

де <math>\|\cdot\|_{F}</math> є [[Норма Фробеніуса|нормою Фробеніуса]]. Ця задача оптимізації є задачею {{нп|LASSO|''LASSO''||Lasso (statistics)}}, і відтак її можливо ефективно розв'язувати передовим розв'язувачем ''LASSO'', таким як подвійний {{нп|метод розширеного Лагранжіана|||Augmented Lagrangian method}}.

== Кореляційне обирання ознак ==

Міра кореляційного обирання ознак ({{lang-en|Correlation Feature Selection, CFS}}) оцінює підможину ознак на основі наступної гіпотези: «Добрі підмножини ознак містять ознаки, високо корельовані з класифікацією, але некорельовані між собою».<ref>M. Hall 1999, [http://www.cs.waikato.ac.nz/~mhall/thesis.pdf Correlation-based Feature Selection for Machine Learning] {{ref-en}}</ref><ref>Senliol, Baris, et al. "Fast Correlation Based Filter (FCBF) with a different search strategy." Computer and Information Sciences, 2008. ISCIS'08. 23rd International Symposium on. IEEE, 2008. [http://ieeexplore.ieee.org/xpl/articleDetails.jsp?tp=&arnumber=4717949] {{ref-en}}</ref> Наступне рівняння задає якість підмножини ознак ''S'', що складається із ''k'' ознак:

: <math> \mathrm{Merit}_{S_{k}} = \frac{k\overline{r_{cf}}}{\sqrt{k+k(k-1)\overline{r_{ff}}}}.</math>

Тут <math> \overline{r_{cf}} </math> є усередненим значенням усіх кореляцій ознака-класифікація, а <math> \overline{r_{ff}} </math> є усередненим значенням усіх кореляцій ознака-ознака. Критерій ''CFS'' визначають наступним чином:

: <math>\mathrm{CFS} = \max_{S_k}
\left[\frac{r_{c f_1}+r_{c f_2}+\cdots+r_{c f_k}}
{\sqrt{k+2(r_{f_1 f_2}+\cdots+r_{f_i f_j}+ \cdots
+ r_{f_k f_1 })}}\right].</math>

Змінні <math>r_{cf_{i}}</math> та <math>r_{f_{i}f_{j}}</math> називають кореляціями, але вони не обов'язково є [[Коефіцієнт кореляції Пірсона|коефіцієнтами кореляції Пірсона]] або [[Коефіцієнт кореляції рангу Спірмена|ρ Спірмена]]. Дисертація доктора Марка Голла ({{lang-en|Mark Hall}}) не використовує жодного з цих, але використовує три відмінні міри пов'язаності, [[Мінімальна довжина опису|мінімальну довжину опису]] ({{lang-en|minimum description length, MDL}}), [[Симетрична невизначеність|симетричну невизначеність]] та {{нп|Relief (обирання ознак)|''relief''||Relief (feature selection)}}.

Нехай ''x<sub>i</sub>'' буде [[Індикаторна функція|індикаторною функцією]] членства ознаки ''f<sub>i</sub>''; тоді наведене вище може бути переписано як задачу оптимізації:

: <math>\mathrm{CFS} = \max_{x\in \{0,1\}^{n}} 
\left[\frac{(\sum^{n}_{i=1}a_{i}x_{i})^{2}}
{\sum^{n}_{i=1}x_i + \sum_{i\neq j} 2b_{ij} x_i x_j }\right].</math>

Комбінаторні задачі вище є, фактично, задачами [[Цілочислове лінійне програмування|змішаного двійкового лінійного програмування]], які можливо розв'язувати застосуванням [[Метод гілок і меж|алгоритмів гілок та меж]].<ref>Hai Nguyen, Katrin Franke, and Slobodan Petrovic, Optimizing a class of feature selection measures, Proceedings of the NIPS 2009 Workshop on Discrete Optimization in Machine Learning: Submodularity, Sparsity & Polyhedra (DISCML), Vancouver, Canada, December 2009. [https://www.researchgate.net/publication/231175763_Optimizing_a_Class_of_Feature_Selection_Measures?ev=prf_pub] {{ref-en}}</ref>

== Регуляризовані дерева ==

Ознаки з [[Дерево прийняття рішень|дерева]] або [[Ансамблеве навчання|ансамблю]] дерев рішень виявляються надлишковими. Для обирання підмножини ознак можливо застосовувати нещодавній метод, названий регуляризованим деревом.<ref name="DengRunger2012">H. Deng, G. Runger, "[https://sites.google.com/site/houtaodeng/publications/FSRegularizedTrees.pdf?attredirects=0 Feature Selection via Regularized Trees] {{Webarchive|url=https://web.archive.org/web/20150912165654/https://sites.google.com/site/houtaodeng/publications/FSRegularizedTrees.pdf?attredirects=0 |date=2015-09-12 }}", Proceedings of the 2012 International Joint Conference on Neural Networks (IJCNN), IEEE, 2012 {{ref-en}}</ref> Регуляризовані дерева здійснюють штрафування, використовуючи для розділення поточного вузла змінну, подібну до змінних, вибраних на попередніх вузлах дерева. Регуляризовані дерева потребують побудови лише однієї деревної моделі (або однієї моделі ансамблю дерев), і, отже, є обчислювально ефективними.

Регуляризовані дерева природно обробляють числові та категорійні ознаки, взаємодії та нелінійності. Вони є інваріантними відносно масштабів (одиниць виміру) атрибутів та нечутливими до [[Викид (статистика)|викидів]], і, таким чином, вимагають незначної попередньої обробки даних, такої як {{нп|Нормалізація (статистика)|нормалізація||Normalization (statistics)}}. Одним із типів регуляризованих дерев є регуляризований випадковий ліс (РВЛ, {{lang-en|Regularized random forest, RRF}}).<ref name="RRF">[https://cran.r-project.org/web/packages/RRF/index.html RRF: Regularized Random Forest], пакет [[R (мова програмування)|R]] на [[CRAN (мова програмування R)|CRAN]] {{ref-en}}</ref> Цей керований РВЛ є розширеним РВЛ, що керується балами важливості зі звичайного випадкового лісу.

== Огляд метаевристичних методів ==

[[Метаевристики|Метаевристика]] є загальним описом алгоритму, присвяченого розв'язанню складних (зазвичай, [[NP-складна задача|''NP''-складних]]) задач оптимізації, для яких не існує класичних методів розв'язання. Загалом, метаевристика є стохастичним алгоритмом, який веде до досягнення глобального оптимуму. Існує багато метаевристик, від простого локального пошуку, і до алгоритму складного глобального пошуку.

=== Головні принципи ===

Методи обирання ознак зазвичай представляють трьома класами на основі того, як вони поєднують алгоритм обирання та побудову моделі.

==== Фільтровий метод ====
[[Файл:Filter Methode uk.png|thumb|300px|Фільтровий метод обирання ознак]]

Методи фільтрового типу обирають змінні незалежно від моделі. Вони ґрунтуються лише на загальних ознаках, таких як кореляція з передбачуваною змінною. Фільтрові методи придушують найменш цікаві змінні. Інші змінні будуть частиною моделі класифікації або регресії, яку застосовують для класифікування або передбачення даних. Ці методи є особливо ефективними з точки зору обчислювального часу, та стійкими до [[перенавчання]].<ref name="ReferenceA">J. Hammon. [https://tel.archives-ouvertes.fr/tel-00920205/document Optimisation combinatoire pour la sélection de variables en régression en grande dimension : Application en génétique animale.] November 2013 {{ref-fr}}</ref>

Фільтрові методи схильні обирати надлишкові змінні, коли вони не беруть до уваги взаємовідношення між змінними. Проте більш продумані функції, такі як алгоритм ''FCBF'',<ref>{{Cite web|url=https://www.aaai.org/Papers/ICML/2003/ICML03-111.pdf|title=https://www.aaai.org/Papers/ICML/2003/ICML03-111.pdf|last=|first=|date=|website=|archive-url=https://web.archive.org/web/20180712182422/http://www.aaai.org/Papers/ICML/2003/ICML03-111.pdf|archive-date=2018-07-12|dead-url=|access-date=}} {{ref-en}}</ref> намагаються й мінімізують цю проблему шляхом усування сильно корельованих між собою змінних.

==== Обгортковий метод ====
[[Файл:Feature selection Wrapper Method uk.png|thumb|300px|Обгортковий метод обирання ознак]]

Обгорткові методи оцінюють підмножини змінних, що дозволяє, на відміну від фільтрових підходів, виявляти можливі взаємодії між змінними.<ref name="M. Phuong, Z pages 301-309">T. M. Phuong, Z. Lin et R. B. Altman. [http://htsnp.stanford.edu/FSFS/TaggingSNP.pdf Choosing SNPs using feature selection.] {{Webarchive|url=https://web.archive.org/web/20160913211229/http://htsnp.stanford.edu/FSFS/TaggingSNP.pdf |date=13 вересня 2016 }} Proceedings / IEEE Computational Systems Bioinformatics Conference, CSB. IEEE Computational Systems Bioinformatics Conference, pages 301-309, 2005. {{PMID|16447987}}. {{ref-en}}</ref> Двома головними недоліками цих методів є:

* Підвищення ризику перенавчання за недостатньої кількості спостережень.
* Значний обчислювальний час за великої кількості змінних.

==== Вбудований метод ====
[[Файл:Feature selection Embedded Method uk.png|thumb|300px|Вбудований метод обирання ознак]]

Нещодавно було запропоновано вбудовані методи, які намагаються поєднувати переваги обох попередніх методів. Алгоритм навчання отримує перевагу від свого власного процесу обирання змінних, і виконує обирання ознак та класифікування одночасно, як це робить алгоритм ''FRMT''.<ref>Saghapour E, Kermani S, Sehhati M (2017) A novel feature ranking method for prediction of cancer stages using proteomics data. PLOS ONE 12(9): e0184203. https://doi.org/10.1371/journal.pone.0184203 {{ref-en}}</ref>

=== Застосування метаевристик обирання ознак ===

Це огляд застосувань метаевристик обирання ознак, що останнім часом використовували в літературі. Цей огляд було реалізовано Дж. Геммон ({{lang-en|J. Hammon}}) в її дисертації 2013 року.<ref name="ReferenceA"/>

{| class="wikitable sortable"
|-
! Застосування !! Алгоритм !! Підхід !! класифікатор !! [[Оцінювальна функція|Оцінна функція]] !! Посилання
|-
| [[Однонуклеотидний поліморфізм|ОНП]] || {{H:title|англ. Feature Selection using Feature Similarity, FSFS|Обирання ознак за схожістю}} || Фільтр ||   || ''r''<sup>2</sup> || Phuong 2005<ref name="M. Phuong, Z pages 301-309"/>
|-
| ОНП || [[Генетичний алгоритм]] || Обгортка || [[Дерева рішень у машинному навчанні|Дерево рішень]] || Точність класифікації (10-кратна) || Shah 2004<ref>{{cite journal | last1 = Shah | first1 = S. C. | last2 = Kusiak | first2 = A. | year = 2004 | title = Data mining and genetic algorithm based gene/SNP selection | url = | journal = Artificial Intelligence in Medicine | volume = 31 | issue = 3| pages = 183–196 | doi = 10.1016/j.artmed.2004.04.002 | pmid = 15302085 }} {{ref-en}}</ref>
|-
| ОНП || [[Алгоритм сходження на вершину|Підйом схилом]] || Фільтр + обгортка || [[Наївний баєсів класифікатор|Наївний баєсів]] || Predicted residual sum of squares || Long 2007<ref>{{cite journal | last1 = Long | first1 = N. | last2 = Gianola | first2 = D. | last3 = Weigel | first3 = K. A | year = 2011 | title = Dimension reduction and variable selection for genomic selection : application to predicting milk yield in Holsteins | url = | journal = Journal of Animal Breeding and Genetics | volume = 128 | issue = 4| pages = 247–257 | doi=10.1111/j.1439-0388.2011.00917.x| pmid = 21749471 }} {{ref-en}}</ref>
|-
| ОНП || [[Алгоритм імітації відпалу|Імітація відпалу]] ||  || Наївний баєсів || Точність класифікації (5-кратна) || Ustunkar 2011<ref>G. Ustunkar, S. Ozogur-Akyuz, G. W. Weber, C. M. Friedrich et Yesim Aydin Son. [https://link.springer.com/article/10.1007/s11590-011-0419-7 Selection of representative SNP sets for genome-wide association studies : a metaheuristic approach]. Optimization Letters, November 2011. {{ref-en}}</ref>
|-
| Мовна сегментація || [[Мурашиний алгоритм]] || Обгортка || [[Штучна нейронна мережа]] || [[Середньоквадратична похибка|СКП]] || Al-ani 2005 {{citation needed|reason=Need RS|date=липень 2016}}
|-
| Маркетинг || Імітація відпалу || Обгортка || Регресія || [[Інформаційний критерій Акаіке|ІКА]], ''r''<sup>2</sup> || Meiri 2006<ref>R. Meiri et J. Zahavi. [https://www.researchgate.net/profile/Jacob_Zahavi/publication/222966372_Using_simulated_annealing_to_optimize_feature_selection_problem_in_marketing_applications/links/5a8d2699a6fdcc786eb063d3/Using-simulated-annealing-to-optimize-feature-selection-problem-in-marketing-applications.pdf Using simulated annealing to optimize the feature selection problem in marketing applications]. European Journal of Operational Research, vol. 171, no. 3, pages 842-858, Juin 2006 {{ref-en}}</ref>
|-
| Економіка || Імітація відпалу, генетичний алгоритм || Обгортка || Регресія || [[Баєсів інформаційний критерій|БІК]] || Kapetanios 2005<ref>G. Kapetanios. [https://www.econstor.eu/bitstream/10419/62923/1/487170563.pdf Variable Selection using Non-Standard Optimisation of Information Criteria]. Working Paper 533, Queen Mary, University of London, School of Economics and Finance, 2005. {{ref-en}}</ref>
|-
| Спектральна маса || Генетичний алгоритм || Обгортка || Множинна лінійна регресія, {{нп|Метод частинних найменших квадратів|частинні найменші квадрати||Partial least squares regression}} || {{нп|Кореневе середньоквадратичне відхилення|Коренева середньоквадратична похибка||Root-mean-square deviation}} передбачення || Broadhurst 2007<ref>D. Broadhurst, R. Goodacre, A. Jones, J. J. Rowland et D. B. Kell. [http://www.biospec.net/pubs/pdfs/Broadhurst-ACA1997.pdf Genetic algorithms as a method for variable selection in multiple linear regression and partial least squares regression, with applications to pyrolysis mass spectrometry]. [[Analytica Chimica Acta]], vol. 348, no. 1-3, pages 71-86, August 1997. {{ref-en}}</ref>
|-
| Спам || Двійковий [[Метод рою часток|МРЧ]] + {{нп|Мутація (генетичний алгоритм)|мутація||Mutation (genetic algorithm)}} || Обгортка || [[Дерево ухвалення рішень|Дерево рішень]] || Зважені витрати || Zhang 2014<ref name="sciencedirect.com"/>
|-
| [[ДНК-мікрочип|Мікрочипи]] || [[Табу-пошук]] + [[Метод рою часток|МРЧ]] || Обгортка || [[Метод опорних векторів]], [[Метод найближчих k-сусідів|''k'' найближчих сусідів]] || [[Евклідова відстань]]  || Chuang 2009<ref>{{cite journal | last1 = Chuang | first1 = L.-Y. | last2 = Yang | first2 = C.-H. | year = 2009 | title = Tabu search and binary particle swarm optimization for feature selection using microarray data | url = | journal = Journal of Computational Biology | volume = 16 | issue = 12| pages = 1689–1703 | doi = 10.1089/cmb.2007.0211 | pmid = 20047491 }} {{ref-en}}</ref>
|-
| Мікрочипи || МРЧ + генетичний алгоритм || Обгортка || Метод опорних векторів || Точність класифікації (10-кратна) || Alba 2007<ref>E. Alba, J. Garia-Nieto, L. Jourdan et E.-G. Talbi. [http://neo.lcc.uma.es/presentacionesCongreso/JMcec2007.pdf Gene Selection in Cancer Classification using PSO-SVM and GA-SVM Hybrid Algorithms.] {{Webarchive|url=https://web.archive.org/web/20160818135718/http://neo.lcc.uma.es/presentacionesCongreso/JMcec2007.pdf |date=2016-08-18 }} Congress on Evolutionary Computation, Singapor : Singapore (2007), 2007 {{ref-en}}</ref>
|-
| Мікрочипи || Генетичний алгоритм + {{нп|ітеративний локальний пошук|||Iterated local search}} || Вбудований || Метод опорних векторів || Точність класифікації (10-кратна) || Duval 2009<ref name="B. Duval, J pages 201-208">B. Duval, J.-K. Hao et J. C. Hernandez Hernandez. [http://www.info.univ-angers.fr/pub/hao/papers/GECCO09.pdf A memetic algorithm for gene selection and molecular classification of an cancer.] In Proceedings of the 11th Annual conference on Genetic and evolutionary computation, GECCO '09, pages 201-208, New York, NY, USA, 2009. ACM. {{ref-en}}</ref>
|-
| Мікрочипи || Ітеративний локальний пошук || Обгортка || Регресія || [[Апостеріорна ймовірність]] || Hans 2007<ref>C. Hans, A. Dobra et M. West. [https://www.researchgate.net/profile/Adrian_Dobra/publication/228388856_Shotgun_Stochastic_Search_for_Large_p_Regression/links/02bfe5125185997d06000000.pdf Shotgun stochastic search for 'large p' regression]. Journal of the American Statistical Association, 2007. {{ref-en}}</ref>
|-
| Мікрочипи || Генетичний алгоритм || Обгортка || ''k'' найближчих сусідів || Точність класифікації ([[перехресне затверджування з виключенням по одному]]) || Jirapech-Umpai 2005<ref>{{cite journal | last1 = Aitken | first1 = S. | year = 2005 | title = Feature selection and classification for microarray data analysis : Evolutionary methods for identifying predictive genes | doi = 10.1186/1471-2105-6-148 | pmid = 15958165 | pmc = 1181625 | journal = BMC Bioinformatics | volume = 6 | issue = 1| page = 148 }} {{ref-en}}</ref>
|-
| Мікрочипи || {{нп|Гібридний генетичний алгоритм|||Hybrid genetic algorithm}} || Обгортка || ''k'' найближчих сусідів || Точність класифікації (перехресне затверджування з виключенням по одному) || Oh 2004<ref>{{cite journal | last1 = Oh | first1 = I. S. | last2 = Moon | first2 = B. R. | year = 2004 | title = Hybrid genetic algorithms for feature selection | url = | journal = {{нп|IEEE Transactions on Pattern Analysis and Machine Intelligence}} | volume = 26 | issue = 11| pages = 1424–1437 | doi=10.1109/tpami.2004.105| pmid = 15521491 | citeseerx = 10.1.1.467.4179 }} {{ref-en}}</ref>
|-
| Мікрочипи || Генетичний алгоритм || Обгортка || Метод опорних векторів || [[Чутливість і специфічність]] || Xuan 2011<ref>{{cite journal | last1 = Xuan | first1 = P. | last2 = Guo | first2 = M. Z. | last3 = Wang | first3 = J. | last4 = Liu | first4 = X. Y. | last5 = Liu | first5 = Y. | year = 2011 | title = Genetic algorithm-based efficient feature selection for classification of pre-miRNAs | url = | journal = Genetics and Molecular Research | volume = 10 | issue = 2| pages = 588–603 | doi = 10.4238/vol10-2gmr969 | pmid = 21491369 }} {{ref-en}}</ref>
|-
| Мікрочипи || Генетичний алгоритм || Обгортка || {{H:title|англ. All paired|Повноспарований}} метод опорних векторів || Точність класифікації (перехресне затверджування з виключенням по одному) || Peng 2003<ref>{{cite journal | last1 = Peng | first1 = S. | year = 2003 | title = Molecular classification of cancer types from microarray data using the combination of genetic algorithms and support vector machines | url = | journal = FEBS Letters | volume = 555 | issue = 2| pages = 358–362 | doi=10.1016/s0014-5793(03)01275-4}} {{ref-en}}</ref>
|-
| Мікрочипи || Генетичний алгоритм || Вбудований || Метод опорних векторів || Точність класифікації (10-кратна) || Hernandez 2007<ref>J. C. H. Hernandez, B. Duval et J.-K. Hao. [https://www.researchgate.net/profile/Jin-Kao_Hao/publication/220867307_A_Genetic_Embedded_Approach_for_Gene_Selection_and_Classification_of_Microarray_Data/links/09e41505b5f5036af3000000/A-Genetic-Embedded-Approach-for-Gene-Selection-and-Classification-of-Microarray-Data.pdf A genetic embedded approach for gene selection and classification of microarray data]. In Proceedings of the 5th European conference on Evolutionary computation, machine learning and data mining in bioinformatics, EvoBIO'07, pages 90-101, Berlin, Heidelberg, 2007. SpringerVerlag. {{ref-en}}</ref>
|-
| Мікрочипи || Генетичний алгоритм || Гібридний || Метод опорних векторів || Точність класифікації (перехресне затверджування з виключенням по одному) || Huerta 2006<ref>E. B. Huerta, B. Duval et J.-K. Hao. [https://www.researchgate.net/profile/Jin-Kao_Hao/publication/220867778_A_Hybrid_GASVM_Approach_for_Gene_Selection_and_Classification_of_Microarray_Data/links/09e41505b5f500ddc4000000.pdf A hybrid GA/SVM approach for gene selection and classification of microarray data]. evoworkshops 2006, LNCS, vol. 3907, pages 34-44, 2006. {{ref-en}}</ref>
|-
| Мікрочипи || Генетичний алгоритм ||  || Метод опорних векторів || Точність класифікації (10-кратна) || Muni 2006<ref>D. P. Muni, N. R. Pal et J. Das. [http://library.isical.ac.in:8080/jspui/bitstream/10263/2810/1/Binder11.pdf Genetic programming for simultaneous feature selection and classifier design]. IEEE Transactions on Systems, Man, and Cybernetics - Part B: Cybernetics : Cybernetics, vol. 36, no. 1, pages 106-117, February 2006. {{ref-en}}</ref>
|-
| Мікрочипи || Генетичний алгоритм || Обгортка || Метод опорних векторів || ''EH-DIALL'', ''CLUMP'' || Jourdan 2004<ref>L. Jourdan, C. Dhaenens et E.-G. Talbi. Linkage disequilibrium study with a parallel adaptive GA. International Journal of Foundations of Computer Science, 2004. {{ref-en}}</ref>
|-
|[[Хвороба Альцгеймера]] || {{нп|t-перевірка Велша|''t''-перевірка Велша||Welch's t-test}} || Фільтр || Ядровий метод опорних векторів || Точність класифікації (10-кратна) || Zhang 2015<ref>{{cite journal|last1=Zhang|first1=Y.|last2=Dong|first2=Z.|last3=Phillips|first3=P.|last4=Wang|first4=S.|title=Detection of subjects and brain regions related to Alzheimer's disease using 3D MRI scans based on eigenbrain and machine learning|journal=Frontiers in Computational Neuroscience|date=2015|volume=9|page=66|doi=10.3389/fncom.2015.00066|pmid=26082713|pmc=4451357}} {{ref-en}}</ref>
|-
|[[Комп'ютерне бачення]]
|[https://it.mathworks.com/matlabcentral/fileexchange/56937-feature-selection-library {{H:title|англ. Infinite Feature Selection|Нескінченне обирання ознак}}]
|Фільтр
|Незалежний
|{{нп|Усереднена чіткість|||Average Precision}}, [[ППК РХП]]
|Roffo 2015<ref>{{Cite book|last=Roffo|first=G.|last2=Melzi|first2=S.|last3=Cristani|first3=M.|date=2015-12-01|title=Infinite Feature Selection|journal=2015 IEEE International Conference on Computer Vision (ICCV)|pages=4202–4210|doi=10.1109/ICCV.2015.478|isbn=978-1-4673-8391-2}} {{ref-en}}</ref>
|-
|Мікрочипи
|[https://it.mathworks.com/matlabcentral/fileexchange/56937-feature-selection-library {{H:title|англ. Eigenvector Centrality FS|ВО центральністю власного вектора}}]
|Фільтр
|Незалежний
|Усереднена чіткість, Точність, {{H:title|англ. ROC AUC|ППК РХП}}
|Roffo & Melzi 2016<ref>{{Cite web|url=http://www.di.uniba.it/~loglisci/NFmcp2016/NFmcp2016_paper_13.pdf|title=Features Selection via Eigenvector Centrality|last=Roffo|first=Giorgio|last2=Melzi|first2=Simone|date=September 2016|website=|publisher=NFmcp2016|accessdate=12 листопада 2016}} {{ref-en}}</ref>
|-
|[[XML]]
|Симетрична Тау ({{lang-en|{{H:title|Symmetrical Tau|ST}}}})
|Фільтр
|Структурна асоціативна класифікація
|Точність, Покриття
|Shaharanee & Hadzic 2014
|}

== Обирання ознак, вбудоване до алгоритмів навчання ==

Деякі алгоритми навчання виконують обирання ознак як частину своєї загальної роботи. До них належать:

* Методики {{tmath|l_1}}-регуляризації, такі як розріджена регресія, {{нп|LASSO|||Lasso (statistics)}}, та {{tmath|l_1}}-[[Метод опорних векторів|МОВ]]
* Регуляризовані дерева,<ref name="DengRunger2012" /> наприклад, регуляризований випадковий ліс, втілений у пакеті RRF<ref name="RRF" />
* [[Дерева рішень у машинному навчанні|Дерева рішень]]<ref>R. Kohavi and G. John, "[https://ai.stanford.edu/~ronnyk/wrappersPrint.pdf Wrappers for feature subset selection]", {{нп|Artificial intelligence|''Artificial intelligence''||Artificial Intelligence (journal)}} 97.1-2 (1997): 273-324 {{ref-en}}</ref>
* {{нп|Меметичний алгоритм|||Memetic algorithm}}
* {{нп|Випадковий поліноміальний логіт|||Random multinomial logit}}<!-- Проблема вікіфікації: Сторінка [[:en:Random multinomial logit]] (→ [[:en:Random forest#Variants]]) перекладена як [[Random forest]], хоча хотіли [[Випадковий поліноміальний логіт]] (SashkoR0B0T)--> ({{lang-en|Random multinomial logit, RMNL}})
* [[Автокодувальник|Автокодувальні]] мережі з рівнем&nbsp;— вузьким місцем
* {{нп|Субмодулярна функція множини|Субмодулярне||Submodular set function}} обирання ознак<ref>{{cite arxiv|eprint=1102.3975|last1=Das|first1=Abhimanyu|title=Submodular meets Spectral: Greedy Algorithms for Subset Selection, Sparse Approximation and Dictionary Selection|last2=Kempe|first2=David|class=stat.ML|year=2011}} {{ref-en}}</ref><ref>Liu et al, [http://melodi.ee.washington.edu/~bilmes/mypubs/liu-submodfeature2013-icassp.pdf Submodular feature selection for high-dimensional acoustic score spaces] {{Webarchive|url=https://web.archive.org/web/20151017122628/http://melodi.ee.washington.edu/~bilmes/mypubs/liu-submodfeature2013-icassp.pdf |date=17 жовтня 2015 }} {{ref-en}}</ref><ref>Zheng et al, [http://papers.nips.cc/paper/5565-deep-convolutional-neural-network-for-image-deconvolution Submodular Attribute Selection for Action Recognition in Video] {{Webarchive|url=https://web.archive.org/web/20151118001059/http://papers.nips.cc/paper/5565-deep-convolutional-neural-network-for-image-deconvolution |date=18 листопада 2015 }} {{ref-en}}</ref>
* Обирання ознак на основі локального навчання.<ref>Y. Sun, S. Todorovic, S. Goodison (2010), "[https://ieeexplore.ieee.org/abstract/document/5342431/ Local-Learning-Based Feature Selection for High-Dimensional Data Analysis]", {{нп|IEEE Transactions on Pattern Analysis and Machine Intelligence|''IEEE Transactions on Pattern Analysis and Machine Intelligence''}}, 32(9): 1610-1626 {{ref-en}}</ref> В порівнянні з традиційними методами, він не передбачає жодного евристичного пошуку, може легко впоруватися з полікласовими задачами, і працює як для лінійних, так і для нелінійних задач. Він також підтримується сильним теоретичним підґрунтям. Чисельні експерименти показали, що цей метод може досягати близького до оптимального розв'язку навіть коли дані містять понад мільйон недоречних ознак.

== Див. також ==

* [[Кластерний аналіз]]
* [[Добування даних]]
* [[Зниження розмірності]]
* [[Виділяння ознак]]
* [[Оптимізація гіперпараметрів]]
* {{нп|Relief (обирання ознак)|||Relief (feature selection)}}

== Примітки ==

{{Примітки|30em}}

== Література ==

{{Refbegin}}
* {{citation | author-first= F. | author-last= Harrell | title= Regression Modeling Strategies | year= 2001 | publisher= {{нп|Springer Publishing|Springer}}}} {{ref-en}}
* {{citation| title= Feature Selection for Knowledge Discovery and Data Mining | author1-first= Huan | author1-last=Liu | author2-first= Hiroshi | author2-last= Motoda | year= 1998 | publisher= Springer|url=https://books.google.com/books?id=aaDbBwAAQBAJ&printsec=frontcover#v=onepage&q&f=false}} {{ref-en}}
* [http://jmlr.csail.mit.edu/papers/special/feature03.html Special Issue on Variable and Feature Selection] —''[[Journal of Machine Learning Research]]'' (2003) {{ref-en}}
* [http://jmlr.csail.mit.edu/papers/volume3/guyon03a/guyon03a.pdf An Introduction to Variable and Feature Selection] (огляд) {{ref-en}}
* [http://www.public.asu.edu/~huanliu/papers/tkde05.pdf Toward integrating feature selection algorithms for classification and clustering] (огляд) {{ref-en}}
* [http://library.utia.cas.cz/separaty/2010/RO/somol-efficient%20feature%20subset%20selection%20and%20subset%20size%20optimization.pdf Efficient Feature Subset Selection and Subset Size Optimization] (огляд 2010 року) {{ref-en}}
* "[http://www.ijcai.org/papers07/Papers/IJCAI07-187.pdf Searching for Interacting Features]" —Zhao & Liu, представлена на [[Міжнародна об'єднана конференція зі штучного інтелекту|IJCAI]] (2007) {{ref-en}}
{{Refend}}

== Посилання ==
* [https://web.archive.org/web/20120511162342/http://featureselection.asu.edu/software.php Пакет обирання ознак, Університет штату Аризона (код Matlab)]
* [http://www.clopinet.com/isabelle/Projects/NIPS2003/ Змагання NIPS 2003 року] (див. також {{нп|Конференція із нейронних систем обробки інформації|NIPS||Conference on Neural Information Processing Systems}})
* [http://paul.luminos.nl/documents/show_document.php?d=198 Реалізація наївного баєсового класифікатора із обиранням ознак на Visual Basic] (включає виконуваний та джерельний код)
* [http://home.penglab.com/proj/mRMR/index.htm Програма обирання ознак мінімальної-надлишковості-максимальної-доречності (minimum-redundancy-maximum-relevance, mRMR)]
* [http://mloss.org/software/view/386/ FEAST] (відкриті алгоритми обирання ознак на [[C (мова програмування)|C]] та [[MATLAB]])
* {{Cite web|title=Automated feature selection with boruta|url=https://kaggle.com/code/residentmario/automated-feature-selection-with-boruta|website=kaggle.com|accessdate=2023-03-04|language=en}}

[[Категорія:Обирання моделі|Ознак]]
[[Категорія:Зниження розмірності]]