В машинному навчанні та статистиці обира́ння озна́к, відоме також як обира́ння змі́нних, обира́ння атрибу́тів та обира́ння підмножини́ змі́нних () — це процес обирання підмножини доречних ознак (змінних, провісників) для використання в побудові моделі. Методики обирання ознак застосовують із декількома цілями:
спрощення моделей, щоби зробити їх легшими для інтерпретування дослідниками/користувачами, скорочення тривалостей тренування, уникання прокляття розмірності, покращення узагальнення шляхом зниження перенавчання (формально, зниження дисперсії).
Центральною передумовою при застосуванні методики обирання ознак є те, що дані містять деякі ознаки, що є або надлишковими, або недоречними, і тому їх може бути усунено без спричинення значної втрати інформації. «Надлишкові» та «недоречні» є двома різними поняттями, оскільки одна доречна ознака може бути надлишковою в присутності іншої доречної ознаки, з якою вона сильно корелює.
Методики обирання ознак слід відрізняти від виділяння ознак. Виділяння ознак створює нові ознаки з функцій від первинних ознак, тоді як обирання ознак повертає підмножину ознак. Методики обирання ознак часто використовують у тих областях, де є багато ознак, і порівняно мало зразків (або точок даних). До споконвічних випадків застосування обирання ознак належать аналіз писаних текстів та даних ДНК-мікрочипів, де є багато тисяч ознак, і лише від декількох десятків до сотень зразків.
Введення
Алгоритм обирання ознак можливо розглядати як поєднання методики пошуку для пропонування нових підмножин ознак разом із мірою оцінки, яка встановлює бали різним підмножинам ознак. Найпростішим алгоритмом є перевіряти кожну можливу підмножину ознак, шукаючи таку, яка мінімізує рівень похибки. Це є вичерпним пошуком цим простором, і є обчислювально непіддатливим для будь-яких множин ознак, крім найменших. Вибір оцінювальної метрики сильно впливає на алгоритм, і саме ці оцінювальні метрики відрізняють три основні категорії алгоритмів пошуку ознак: обгорткові, фільтрові та вбудовані методи.
Обгорткові методи для встановлення балів підмножинам ознак використовують передбачувальну модель. Кожну нову підмножину використовують для тренування моделі, яку перевіряють на притриманій множині. Підрахунок кількості помилок, зроблених на цій притриманій множині (рівень похибки моделі) дає бал цієї підмножини. Оскільки обгорткові методи тренують нову модель для кожної підмножини, вони є дуже обчислювально напруженими, але зазвичай пропонують множину ознак із найкращою продуктивністю для того окремого типу моделі. Фільтрові методи для встановлення балів підмножинам ознак замість рівня похибки використовують міру-заступницю. Цю міру обирають такою, щоби вона була швидкою, але все ще схоплювала корисність множини ознак. До поширених мір належать взаємна інформація, поточкова взаємна інформація, коефіцієнт кореляції Пірсона, та внутрішньо/міжкласова відстань або бали критеріїв значущості для кожної комбінації клас/ознака. Фільтри зазвичай є менш напруженими обчислювально за обгортки, але вони пропонують набір ознак, що не налаштовано на конкретний тип передбачувальної моделі. Цей брак налаштування означає, що набір ознак від фільтра є загальнішим за набір від обгортки, зазвичай даючи нижчу передбачувальну продуктивність, ніж обгортка. Проте такий набір ознак не містить припущень передбачувальної моделі, і тому є кориснішим для розкриття взаємозв'язків між ознаками. Багато фільтрів пропонують ранжування ознак замість явної найкращої підмножини ознак, а точку відсікання в рангу обирають за допомогою перехресного затверджування. Фільтрові методи також застосовували як передобробний етап для обгорткових методів, роблячи можливим застосування обгорток до більших задач. Одним з інших популярних підходів є алгоритм рекурсивного усунення ознак (), зазвичай застосовуваний з методом опорних векторів для повторної побудови моделі та усунення ознак з низькими ваговими коефіцієнтами. Вбудовані методи є всеосяжною групою методик, що виконують обирання ознак як частину процесу побудови моделі. Примірником цього підходу є метод побудови лінійних моделей , який штрафує коефіцієнти регресії штрафом L1, скорочуючи багато з них до нуля. Будь-які ознаки, що мають ненульові коефіцієнти регресії, є «обраними» алгоритмом LASSO. До покращень LASSO належать Bolasso, яке бутстрепує вибірки, , , яка поєднує штраф L1 LASSO із штрафом L2 гребеневої регресії, та FeaLect, яке встановлює бали всім ознакам на основі комбінаторного аналізу коефіцієнтів регресії. Ці підходи з погляду обчислювальної складності тяжіють до знаходження між фільтрами та обгортками.
У традиційному регресійному аналізі найпопулярнішим видом обирання ознак є , яка є обгортковою методикою. Це жадібний алгоритм, що під час кожного раунду додає найкращу ознаку (або видаляє найгіршу). Головним питанням у керуванні є вирішування, коли зупинити алгоритм. У машинному навчанні це зазвичай здійснюють за допомогою перехресного затверджування. У статистиці деякі критерії є оптимізованими. Це призводить до проблеми, притаманної вкладеності. Було досліджено надійніші методи, такі як гілки і межі, та кусково-лінійна мережа.
Обирання підмножин
Обирання підмножини оцінює на придатність підмножину ознак як групу. Алгоритми обирання підмножин можливо розділити на обгорткові, фільтрові та вбудовані методи. Обгорткові використовують пошуковий алгоритм для пошуку простором можливих ознак, і оцінки кожної підмножини запуском моделі на ній. Обгортки можуть бути обчислювально витратними, і мати ризик перенавчитися моделі. Фільтри є схожими на обгортки в підході до пошуку, але замість оцінки проти моделі виводять простіший фільтр. Вбудовані методики є вбудованими в модель, і особливими для моделі.
Багато популярних підходів до пошуку використовують жадібний підйом схилом, що ітеративно оцінює кандидата-підмножину ознак, а потім змінює цю підмножину й оцінює, чи є нова підмножина покращенням відносно старої. Оцінка підмножин вимагає оцінкової метрики, що реалізує градацію підмножин ознак. Вичерпний пошук в загальному випадку є непрактичним, тому на певній визначеній реалізатором (або оператором) точці зупинки підмножину ознак із найвищим знайденим до цієї точки балом обирають задовільною підмножиною ознак. Критерій зупинки залежить від алгоритму; до можливих критеріїв належать: перевищення порогу балом підмножини, перевищення максимального допустимого часу виконання програми тощо.
Альтернативні методики на основі пошуку ґрунтуються на , який знаходить низькорозмірні проєкції даних, що мають високий бал: тоді обирають ознаки, що мають найбільші проєкції в низькорозмірному просторі.
До пошукових підходів належать:
Вичерпний Перший-ліпший Імітація відпалу Генетичний алгоритм Жадібне поступальне обирання () Жадібне зворотне усунення () Метод рою часток
Пошук врозсип ()F.C. Garcia-Lopez, M. Garcia-Torres, B. Melian, J.A. Moreno-Perez, J.M. Moreno-Vega. Solving feature subset selection problem by a Parallel Scatter Search, European Journal of Operational Research, vol. 169, no. 2, pp. 477–489, 2006. F.C. Garcia-Lopez, M. Garcia-Torres, B. Melian, J.A. Moreno-Perez, J.M. Moreno-Vega. Solving Feature Subset Selection Problem by a Hybrid Metaheuristic . In First International Workshop on Hybrid Metaheuristics, pp. 59–68, 2004. M. Garcia-Torres, F. Gomez-Vela, B. Melian, J.M. Moreno-Vega. High-dimensional feature selection via feature grouping: A Variable Neighborhood Search approach, Information Sciences, vol. 326, pp. 102-118, 2016.
Двома популярними фільтровими метриками для задач класифікації є кореляція та взаємна інформація, хоча жодна з них не є справжньою метрикою, або «мірою відстані», в математичному сенсі, оскільки вони не підкоряються нерівності трикутника, і відтак не обчислюють жодної дійсної «відстані» — їх слід було би швидше розглядати як «бали». Ці бали обчислюють між ознаками-кандидатами (або наборами ознак) та бажаною категорією виходу. Проте існують і справжні метрики, що є простою функцією взаємної інформації; див. тут.
До інших доступних фільтрових метрик належать:
Віддільність класів () Імовірність похибки () Міжкласова відстань () Імовірнісна відстань () Інформаційна ентропія Обирання ознак на основі узгодженості () Обирання ознак на основі кореляції ()
Критерій оптимальності
Обирання критерію оптимальності є складним, оскільки в завдання обирання ознак є кілька цілей. Багато поширених критеріїв включають міру точності, штрафовану кількістю обраних ознак. До прикладів належать інформаційний критерій Акаіке (ІКА, ) та , що мають штраф у для кожної доданої ознаки. ІКА ґрунтується на теорії інформації, й практично виводиться з .. .
Іншими критеріями є баєсів інформаційний критерій (БІК, ), що використовує штраф у для кожної доданої ознаки, принцип мінімальної довжини опису (МДО, ), що асимптотично використовує , / (), який використовує , обирання ознак максимальної залежності () та ряд нових критеріїв, обґрунтованих (), який використовує щось близьке до . Для обирання найвідповіднішої множини ознак можна також використовувати й критерій максимальної ентропійної швидкості.
Навчання структури
Фільтрове обирання ознак є окремим випадком загальнішої парадигми, що називають навчанням структури. Обирання ознак знаходить доречний набір ознак для конкретної цільової змінної, тоді як навчання структури знаходить взаємозв'язки між усіма змінними, зазвичай виражаючи ці взаємозв'язки як граф. Найпоширеніші алгоритми навчання структури виходять із того, що дані було породжено баєсовою мережею, і тому структурою є орієнтована графова модель. Оптимальним розв'язком задачі фільтрового обирання ознак є марковське покриття цільового вузла, і в баєсовій мережі існує єдине марковське покриття для кожного вузла.
Механізми обирання ознак на основі теорії інформації
Існують різні механізми обирання ознак, що для оцінювання різних ознак використовують взаємну інформацію. Вони зазвичай використовують один і той же алгоритм:
Обчислити взаємну інформацію як оцінку між усіма ознаками () та цільовим класом ( ) Обрати ознаку з найвищим балом (наприклад, ), і додати її до набору обраних ознак () Обчислити похідну оцінку, яку може бути виведено із взаємної інформації Обрати ознаку з найвищим балом, і додати її до набору обраних ознак (наприклад, ) Повторювати 3. та 4., допоки не буде обрано певне число ознак (наприклад, )
Найпростіший підхід як цю «похідну» оцінку використовує власне взаємну інформацію.
Проте існують різні підходи, що намагаються знижувати надлишковість серед ознак.
Обирання ознак мінімальної-надлишковості-максимальної-доречності (mRMR)
Пен та ін. Програма запропонували метод обирання ознак, що може використовувати для обирання ознак або взаємну інформацію, кореляцію, або відстань/бали схожості. Мета полягає у штрафуванні доречності () ознаки її надлишковістю () в присутності інших обраних ознак. Доречність набору ознак для класу визначають усередненим значенням усіх значень взаємної інформації між окремою ознакою та класом таким чином:
.
Надлишковістю всіх ознак у множині є усереднене значення всіх значень взаємної інформації між ознакою та ознакою :
Критерій мінімальної-надлишковості-максимальної-доречності () є поєднанням двох наведених вище мір, і його визначено наступним чином:
Припустімо, що є ознак повної множини. Нехай буде індикаторною функцією членства ознаки в множині, такою, що показує наявність, а показує відсутність ознаки в глобально оптимальній множині ознак. Нехай , а . Наведене вище може бути записано як задачу оптимізації: