Обирання ознак

В машинному навчанні та статистиці обира́ння озна́к, відоме також як обира́ння змі́нних, обира́ння атрибу́тів та обира́ння підмножини́ змі́нних (Шаблон:Lang-en) — це процес обирання підмножини доречних ознак (змінних, провісників) для використання в побудові моделі. Методики обирання ознак застосовують із декількома цілями:

• спрощення моделей, щоби зробити їх легшими для інтерпретування дослідниками/користувачами,
• скорочення тривалостей тренування,
• уникання прокляття розмірності,
• покращення узагальнення шляхом зниження перенавчання (формально, зниження дисперсіїШаблон:R).

Центральною передумовою при застосуванні методики обирання ознак є те, що дані містять деякі ознаки, що є або надлишковими, або недоречними, і тому їх може бути усунено без спричинення значної втрати інформації. «Надлишкові» та «недоречні» є двома різними поняттями, оскільки одна доречна ознака може бути надлишковою в присутності іншої доречної ознаки, з якою вона сильно корелює.Шаблон:R

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

Введення

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

• Обгорткові методи для встановлення балів підмножинам ознак використовують передбачувальну модель. Кожну нову підмножину використовують для тренування моделі, яку перевіряють на притриманій множині. Підрахунок кількості помилок, зроблених на цій притриманій множині (рівень похибки моделі) дає бал цієї підмножини. Оскільки обгорткові методи тренують нову модель для кожної підмножини, вони є дуже обчислювально напруженими, але зазвичай пропонують множину ознак із найкращою продуктивністю для того окремого типу моделі.
• Фільтрові методи для встановлення балів підмножинам ознак замість рівня похибки використовують міру-заступницю. Цю міру обирають такою, щоби вона була швидкою, але все ще схоплювала корисність множини ознак. До поширених мір належать взаємна інформація, поточкова взаємна інформація, коефіцієнт кореляції Пірсона, Шаблон:Нп та внутрішньо/міжкласова відстань або бали критеріїв значущості для кожної комбінації клас/ознака. Фільтри зазвичай є менш напруженими обчислювально за обгортки, але вони пропонують набір ознак, що не налаштовано на конкретний тип передбачувальної моделі. Цей брак налаштування означає, що набір ознак від фільтра є загальнішим за набір від обгортки, зазвичай даючи нижчу передбачувальну продуктивність, ніж обгортка. Проте такий набір ознак не містить припущень передбачувальної моделі, і тому є кориснішим для розкриття взаємозв'язків між ознаками. Багато фільтрів пропонують ранжування ознак замість явної найкращої підмножини ознак, а точку відсікання в рангу обирають за допомогою перехресного затверджування. Фільтрові методи також застосовували як передобробний етап для обгорткових методів, роблячи можливим застосування обгорток до більших задач. Одним з інших популярних підходів є алгоритм рекурсивного усунення ознак (Шаблон:Lang-en), зазвичай застосовуваний з методом опорних векторів для повторної побудови моделі та усунення ознак з низькими ваговими коефіцієнтами.
• Вбудовані методи є всеосяжною групою методик, що виконують обирання ознак як частину процесу побудови моделі. Примірником цього підходу є метод побудови лінійних моделей Шаблон:Нп, який штрафує коефіцієнти регресії штрафом L1, скорочуючи багато з них до нуля. Будь-які ознаки, що мають ненульові коефіцієнти регресії, є «обраними» алгоритмом LASSO. До покращень LASSO належать Bolasso, яке бутстрепує вибірки,, Шаблон:Нп, яка поєднує штраф L1 LASSO із штрафом L2 гребеневої регресії, та FeaLect, яке встановлює бали всім ознакам на основі комбінаторного аналізу коефіцієнтів регресії. Ці підходи з погляду обчислювальної складності тяжіють до знаходження між фільтрами та обгортками.

У традиційному регресійному аналізі найпопулярнішим видом обирання ознак є Шаблон:Нп, яка є обгортковою методикою. Це жадібний алгоритм, що під час кожного раунду додає найкращу ознаку (або видаляє найгіршу). Головним питанням у керуванні є вирішування, коли зупинити алгоритм. У машинному навчанні це зазвичай здійснюють за допомогою перехресного затверджування. У статистиці деякі критерії є оптимізованими. Це призводить до проблеми, притаманної вкладеності. Було досліджено надійніші методи, такі як гілки і межі, та кусково-лінійна мережа.

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

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

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

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

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

• Вичерпний
• Перший-ліпший
• Імітація відпалу
• Генетичний алгоритм
• Жадібне поступальне обирання (Шаблон:Lang-en)
• Жадібне зворотне усунення (Шаблон:Lang-en)
• Метод рою часток
• Шаблон:Нп
• Пошук врозсип (Шаблон:Lang-en)
• Шаблон:Нп

Двома популярними фільтровими метриками для задач класифікації є кореляція та взаємна інформація, хоча жодна з них не є справжньою метрикою, або «мірою відстані», в математичному сенсі, оскільки вони не підкоряються нерівності трикутника, і відтак не обчислюють жодної дійсної «відстані» — їх слід було би швидше розглядати як «бали». Ці бали обчислюють між ознаками-кандидатами (або наборами ознак) та бажаною категорією виходу. Проте існують і справжні метрики, що є простою функцією взаємної інформації; див. тут.

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

• Віддільність класів (Шаблон:Lang-en)
  • Імовірність похибки (Шаблон:Lang-en)
  • Міжкласова відстань (Шаблон:Lang-en)
  • Імовірнісна відстань (Шаблон:Lang-en)
  • Інформаційна ентропія
• Обирання ознак на основі узгодженості (Шаблон:Lang-en)
• Обирання ознак на основі кореляції (Шаблон:Lang-en)

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

Обирання критерію оптимальності є складним, оскільки в завдання обирання ознак є кілька цілей. Багато поширених критеріїв включають міру точності, штрафовану кількістю обраних ознак. До прикладів належать інформаційний критерій Акаіке (ІКА, Шаблон:Lang-en) та Шаблон:Нп, що мають штраф у $2$ для кожної доданої ознаки. ІКА ґрунтується на теорії інформації, й практично виводиться з Шаблон:Нп.

Іншими критеріями є баєсів інформаційний критерій (БІК, Шаблон:Lang-en), що використовує штраф у $\sqrt{\log n}$ для кожної доданої ознаки, принцип мінімальної довжини опису (МДО, Шаблон:Lang-en), що асимптотично використовує $\sqrt{\log n}$, Шаблон:Нп / Шаблон:H:title (Шаблон:Lang-en), який використовує $\sqrt{2\log p}$, обирання ознак максимальної залежності (Шаблон:Lang-en) та ряд нових критеріїв, обґрунтованих Шаблон:Нп (Шаблон:Lang-en), який використовує щось близьке до $\sqrt{2\log \frac{p}{q}}$. Для обирання найвідповіднішої множини ознак можна також використовувати й критерій максимальної ентропійної швидкості.

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

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

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

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

1. Обчислити взаємну інформацію як оцінку між усіма ознаками ($f_i\in F$) та цільовим класом ( $c$ )
2. Обрати ознаку з найвищим балом (наприклад, $argma{x}_{f_i\in F}(I(f_i,c))$), і додати її до набору обраних ознак ($S$)
3. Обчислити похідну оцінку, яку може бути виведено із взаємної інформації
4. Обрати ознаку з найвищим балом, і додати її до набору обраних ознак (наприклад, $argma{x}_{f_i\in F}(I_{derived}(f_i,c))$ )
5. Повторювати 3. та 4., допоки не буде обрано певне число ознак (наприклад, $|S|=l$ )

Найпростіший підхід як цю «похідну» оцінку використовує власне взаємну інформацію.

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

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

Пен та ін. запропонували метод обирання ознак, що може використовувати для обирання ознак або взаємну інформацію, кореляцію, або відстань/бали схожості. Мета полягає у штрафуванні доречності (Шаблон:Lang-en) ознаки її надлишковістю (Шаблон:Lang-en) в присутності інших обраних ознак. Доречність набору ознак Шаблон:Mvar для класу Шаблон:Mvar визначають усередненим значенням усіх значень взаємної інформації між окремою ознакою Шаблон:Math та класом Шаблон:Mvar таким чином:

$D(S,c)=\frac{1}{|S|}\sum _{f_i\in S}I(f_i;c)$.

Надлишковістю всіх ознак у множині Шаблон:Mvar є усереднене значення всіх значень взаємної інформації між ознакою Шаблон:Math та ознакою Шаблон:Math:

$R(S)=\frac{1}{|S{|}^2}\sum _{f_i,f_j\in S}I(f_i;f_j)$

Критерій мінімальної-надлишковості-максимальної-доречності (Шаблон:Lang-en) є поєднанням двох наведених вище мір, і його визначено наступним чином:

$\mathrm{m}\mathrm{R}\mathrm{M}\mathrm{R}=\underset{S}{\max }[\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)].$

Припустімо, що є Шаблон:Mvar ознак повної множини. Нехай Шаблон:Math буде індикаторною функцією членства ознаки Шаблон:Math в множині, такою, що Шаблон:Math показує наявність, а Шаблон:Math показує відсутність ознаки Шаблон:Math в глобально оптимальній множині ознак. Нехай $c_i=I(f_i;c)$, а $a_{ij}=I(f_i;f_j)$. Наведене вище може бути записано як задачу оптимізації:

$\mathrm{m}\mathrm{R}\mathrm{M}\mathrm{R}=\underset{x\in \{0,1{\}}^n}{\max }[\frac{\sum _{i=1}^n{c}_i{x}_i}{\sum _{i=1}^n{x}_i}-\frac{\sum _{i,j=1}^n{a}_{ij}{x}_i{x}_j}{(\sum _{i=1}^n{x}_i{)}^2}].$

Алгоритм mRMR є наближенням теоретично оптимального максимально-залежнісного алгоритму обирання ознак, який максимізує взаємну інформацію між спільним розподілом обраних ознак та змінною класифікації. Оскільки mRMR наближує задачу комбінаторної оцінки рядом набагато менших задач, кожна з яких включає лише дві змінні, він таким чином використовує попарні спільні ймовірності, що є надійнішими. В деяких ситуаціях цей алгоритм може недооцінювати корисність ознак, оскільки він не має способу вимірювати взаємодії між ознаками, що можуть збільшувати доречність. Це може призводити до поганої продуктивності, коли ознаки є марними поодинці, але корисними у поєднанні (патологічний випадок трапляється, коли клас є Шаблон:Нп ознак). В цілому цей алгоритм є ефективнішим (у термінах кількості потрібної інформації) за теоретично оптимальне максимально-залежнісне обирання, хоча й виробляє набір ознак із невеликою попарною надлишковістю.

mRMR є примірником більшого класу фільтрових методів, які шукають компроміс між доречністю та надлишковістю відмінними шляхами.

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

mRMR є типовим прикладом приростової жадібної стратегії обирання ознак: щойно ознаку було обрано, її не може бути виключено на пізнішому етапі. І хоча mRMR може бути оптимізовано застосуванням рухливого пошуку (Шаблон:Lang-en) для скорочування деяких ознак, його також може бути переформульовано як задачу глобальної оптимізації квадратичного програмування (Шаблон:Lang-en) таким чином:

$\mathrm{Q}\mathrm{P}\mathrm{F}\mathrm{S}:\underset{𝐱}{\min }\{\alpha {𝐱}^{T}H𝐱-{𝐱}^{T}F\}$ т. щ. $\sum _{i=1}^n{x}_i=1,x_i\ge 0$

де $F_{n\times 1}=[I(f_1;c),\dots ,I(f_n;c){]}^T$ є вектором доречності ознак, за припущення, що загалом є Шаблон:Mvar ознак, $H_{n\times n}=[I(f_i;f_j){]}_{i,j=1\dots n}$ є матрицею попарної надлишковості ознак, а ${𝐱}_{n\times 1}$ представляє відносні ваги ознак. QPFS розв'язується за допомогою квадратичного програмування. Нещодавно було показано, що QPFS має схильність до ознак із меншою ентропією, тому що воно ставить член самонадлишковості ознаки $I(f_i;f_i)$ на діагональ Шаблон:Mvar.

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

Інша оцінка, що виводять із взаємної інформації, ґрунтується на умовній доречності:

$\mathrm{S}\mathrm{P}\mathrm{E}{\mathrm{C}}_{\mathrm{C}\mathrm{M}\mathrm{I}}:\underset{𝐱}{\max }\left\{{𝐱}^{T}Q𝐱\right\}$ т. щ. $\Vert 𝐱\Vert =1,x_i\ge 0$

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

Перевага Шаблон:Math полягає в тому, що воно може розв'язуватися просто знаходженням домінантного власного вектора Шаблон:Mvar, і тому є дуже масштабовуваним. Також Шаблон:Math обробляє взаємодії ознак другого порядку.

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

У дослідженні різних балів Браун та ін. рекомендували як добрий бал для обирання ознак Шаблон:Нпні. Цей бал намагається знайти ознаку, що додає найбільше нової інформації до вже відомих ознак, щоби уникати надмірності. Цей бал сформульовано наступним чином:

$\begin{array}{cc}JMI(f_i)& =\sum _{f_j\in S}(I(f_i;c)+I(f_i;c|f_j))\\ & =\sum _{f_j\in S}[I(f_j;c)+I(f_i;c)-(I(f_i;f_j)-I(f_i;f_j|c))]\end{array}$

Цей бал використовує Шаблон:Нп для оцінювання надмірності між вже обраними ознаками ($f_j\in S$) та досліджуваною ознакою ($f_i$).

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

Для даних із високою розмірністю та малою вибіркою (наприклад, розмірність > 10⁵, а кількість зразків < 10³) корисним є Шаблон:Нп критерію незалежності Гільберта-Шмідта (Шаблон:Lang-en). Задачу оптимізації HSIC Lasso задають як

$\mathrm{H}\mathrm{S}\mathrm{I}{\mathrm{C}}_{\mathrm{L}\mathrm{a}\mathrm{s}\mathrm{s}\mathrm{o}}:\underset{𝐱}{\min }\frac{1}{2}\sum _{k,l=1}^n{x}_k{x}_l\text{HSIC}(f_k,f_l)-\sum _{k=1}^n{x}_k\text{HSIC}(f_k,c)+\lambda \Vert 𝐱{\Vert }_1,$ т. щ. $x_1,\dots ,x_n\ge 0,$

де $\text{HSIC}(f_k,c)=\text{tr}({\overline{𝐊}}^{(k)}\overline{𝐋})$ є мірою незалежності на ядровій основі, що називають (емпіричним) критерієм незалежності Гільберта-Шмідта (Шаблон:Lang-en), $\text{tr}(\cdot )$ позначає слід, $\lambda$ є регуляризаційним параметром, ${\overline{𝐊}}^{(k)}=\mathrm{\Gamma }{𝐊}^{(k)}\mathrm{\Gamma }$ та $\overline{𝐋}=\mathrm{\Gamma }𝐋\mathrm{\Gamma }$ є центрованими матрицями Ґрама входу та виходу, $K_{i,j}^{(k)}=K(u_{k,i},u_{k,j})$ та $L_{i,j}=L(c_i,c_j)$ є матрицями Ґрама, $K(u,u^{\prime })$ та $L(c,c^{\prime })$ є ядровими функціями, $\mathrm{\Gamma }={𝐈}_m-\frac{1}{m}{\mathrm{𝟏}}_m{\mathrm{𝟏}}_m^T$ є центрувальною матрицею, ${𝐈}_m$ є Шаблон:Mvar-вимірною одиничною матрицею (Шаблон:Mvar — кількість зразків), ${\mathrm{𝟏}}_m$ є Шаблон:Mvar-вимірним вектором з усіма одиницями, а $\Vert \cdot {\Vert }_1$ є ${\ell }_1$-нормою. HSIC завжди набуває невід'ємного значення, і є нулем тоді й лише тоді, коли дві випадкові змінні є статистично незалежними при використанні універсального відтворювального ядра, такого як ґаусове.

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

$\mathrm{H}\mathrm{S}\mathrm{I}{\mathrm{C}}_{\mathrm{L}\mathrm{a}\mathrm{s}\mathrm{s}\mathrm{o}}:\underset{𝐱}{\min }\frac{1}{2}{\Vert \overline{𝐋}-\sum _{k=1}^n{x}_k{\overline{𝐊}}^{(k)}\Vert }_F^2+\lambda \Vert 𝐱{\Vert }_1,$ т. щ. $x_1,\dots ,x_n\ge 0,$

де $\Vert \cdot {\Vert }_F$ є нормою Фробеніуса. Ця задача оптимізації є задачею Шаблон:Нп, і відтак її можливо ефективно розв'язувати передовим розв'язувачем LASSO, таким як подвійний Шаблон:Нп.

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

Міра кореляційного обирання ознак (Шаблон:Lang-en) оцінює підможину ознак на основі наступної гіпотези: «Добрі підмножини ознак містять ознаки, високо корельовані з класифікацією, але некорельовані між собою». Наступне рівняння задає якість підмножини ознак S, що складається із k ознак:

${\mathrm{M}\mathrm{e}\mathrm{r}\mathrm{i}\mathrm{t}}_{S_k}=\frac{k\overline{r_{cf}}}{\sqrt{k+k(k-1)\overline{r_{ff}}}}.$

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

$\mathrm{C}\mathrm{F}\mathrm{S}=\underset{S_k}{\max }\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].$

Змінні $r_{c{f}_i}$ та $r_{f_i{f}_j}$ називають кореляціями, але вони не обов'язково є коефіцієнтами кореляції Пірсона або ρ Спірмена. Дисертація доктора Марка Голла (Шаблон:Lang-en) не використовує жодного з цих, але використовує три відмінні міри пов'язаності, мінімальну довжину опису (Шаблон:Lang-en), симетричну невизначеність та Шаблон:Нп.

Нехай x_i буде індикаторною функцією членства ознаки f_i; тоді наведене вище може бути переписано як задачу оптимізації:

$\mathrm{C}\mathrm{F}\mathrm{S}=\underset{x\in \{0,1{\}}^n}{\max }\left[\frac{(\sum _{i=1}^n{a}_i{x}_i{)}^2}{\sum _{i=1}^n{x}_i+\sum _{i\ne j}2b_{ij}{x}_i{x}_j}\right].$

Комбінаторні задачі вище є, фактично, задачами змішаного двійкового лінійного програмування, які можливо розв'язувати застосуванням алгоритмів гілок та меж.

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

Ознаки з дерева або ансамблю дерев рішень виявляються надлишковими. Для обирання підмножини ознак можливо застосовувати нещодавній метод, названий регуляризованим деревом. Регуляризовані дерева здійснюють штрафування, використовуючи для розділення поточного вузла змінну, подібну до змінних, вибраних на попередніх вузлах дерева. Регуляризовані дерева потребують побудови лише однієї деревної моделі (або однієї моделі ансамблю дерев), і, отже, є обчислювально ефективними.

Регуляризовані дерева природно обробляють числові та категорійні ознаки, взаємодії та нелінійності. Вони є інваріантними відносно масштабів (одиниць виміру) атрибутів та нечутливими до викидів, і, таким чином, вимагають незначної попередньої обробки даних, такої як Шаблон:Нп. Одним із типів регуляризованих дерев є регуляризований випадковий ліс (РВЛ, Шаблон:Lang-en). Цей керований РВЛ є розширеним РВЛ, що керується балами важливості зі звичайного випадкового лісу.

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

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

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

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

Фільтровий метод

Фільтровий метод обирання ознак

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

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

Обгортковий метод

Обгортковий метод обирання ознак

Обгорткові методи оцінюють підмножини змінних, що дозволяє, на відміну від фільтрових підходів, виявляти можливі взаємодії між змінними. Двома головними недоліками цих методів є:

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

Вбудований метод

Вбудований метод обирання ознак

Нещодавно було запропоновано вбудовані методи, які намагаються поєднувати переваги обох попередніх методів. Алгоритм навчання отримує перевагу від свого власного процесу обирання змінних, і виконує обирання ознак та класифікування одночасно, як це робить алгоритм FRMT.

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

Це огляд застосувань метаевристик обирання ознак, що останнім часом використовували в літературі. Цей огляд було реалізовано Дж. Геммон (Шаблон:Lang-en) в її дисертації 2013 року.

Застосування	Алгоритм	Підхід	класифікатор	Оцінна функція	Посилання
ОНП	Шаблон:H:title	Фільтр		r2	Phuong 2005
ОНП	Генетичний алгоритм	Обгортка	Дерево рішень	Точність класифікації (10-кратна)	Shah 2004
ОНП	Підйом схилом	Фільтр + обгортка	Наївний баєсів	Predicted residual sum of squares	Long 2007
ОНП	Імітація відпалу		Наївний баєсів	Точність класифікації (5-кратна)	Ustunkar 2011
Мовна сегментація	Мурашиний алгоритм	Обгортка	Штучна нейронна мережа	СКП	Al-ani 2005 Шаблон:Citation needed
Маркетинг	Імітація відпалу	Обгортка	Регресія	ІКА, r2	Meiri 2006
Економіка	Імітація відпалу, генетичний алгоритм	Обгортка	Регресія	БІК	Kapetanios 2005
Спектральна маса	Генетичний алгоритм	Обгортка	Множинна лінійна регресія, Шаблон:Нп	Шаблон:Нп передбачення	Broadhurst 2007
Спам	Двійковий МРЧ + Шаблон:Нп	Обгортка	Дерево рішень	Зважені витрати	Zhang 2014
Мікрочипи	Табу-пошук + МРЧ	Обгортка	Метод опорних векторів, k найближчих сусідів	Евклідова відстань	Chuang 2009
Мікрочипи	МРЧ + генетичний алгоритм	Обгортка	Метод опорних векторів	Точність класифікації (10-кратна)	Alba 2007
Мікрочипи	Генетичний алгоритм + Шаблон:Нп	Вбудований	Метод опорних векторів	Точність класифікації (10-кратна)	Duval 2009
Мікрочипи	Ітеративний локальний пошук	Обгортка	Регресія	Апостеріорна ймовірність	Hans 2007
Мікрочипи	Генетичний алгоритм	Обгортка	k найближчих сусідів	Точність класифікації (перехресне затверджування з виключенням по одному)	Jirapech-Umpai 2005
Мікрочипи	Шаблон:Нп	Обгортка	k найближчих сусідів	Точність класифікації (перехресне затверджування з виключенням по одному)	Oh 2004
Мікрочипи	Генетичний алгоритм	Обгортка	Метод опорних векторів	Чутливість і специфічність	Xuan 2011
Мікрочипи	Генетичний алгоритм	Обгортка	Шаблон:H:title метод опорних векторів	Точність класифікації (перехресне затверджування з виключенням по одному)	Peng 2003
Мікрочипи	Генетичний алгоритм	Вбудований	Метод опорних векторів	Точність класифікації (10-кратна)	Hernandez 2007
Мікрочипи	Генетичний алгоритм	Гібридний	Метод опорних векторів	Точність класифікації (перехресне затверджування з виключенням по одному)	Huerta 2006
Мікрочипи	Генетичний алгоритм		Метод опорних векторів	Точність класифікації (10-кратна)	Muni 2006
Мікрочипи	Генетичний алгоритм	Обгортка	Метод опорних векторів	EH-DIALL, CLUMP	Jourdan 2004
Хвороба Альцгеймера	Шаблон:Нп	Фільтр	Ядровий метод опорних векторів	Точність класифікації (10-кратна)	Zhang 2015
Комп'ютерне бачення	Шаблон:H:title	Фільтр	Незалежний	Шаблон:Нп, ППК РХП	Roffo 2015
Мікрочипи	Шаблон:H:title	Фільтр	Незалежний	Усереднена чіткість, Точність, Шаблон:H:title	Roffo & Melzi 2016
XML	Симетрична Тау (Шаблон:Lang-en)	Фільтр	Структурна асоціативна класифікація	Точність, Покриття	Shaharanee & Hadzic 2014

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

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

• Методики Шаблон:Tmath-регуляризації, такі як розріджена регресія, Шаблон:Нп, та Шаблон:Tmath-МОВ
• Регуляризовані дерева, наприклад, регуляризований випадковий ліс, втілений у пакеті RRF
• Дерева рішень
• Шаблон:Нп
• Шаблон:Нп (Шаблон:Lang-en)
• Автокодувальні мережі з рівнем — вузьким місцем
• Шаблон:Нп обирання ознак
• Обирання ознак на основі локального навчання. В порівнянні з традиційними методами, він не передбачає жодного евристичного пошуку, може легко впоруватися з полікласовими задачами, і працює як для лінійних, так і для нелінійних задач. Він також підтримується сильним теоретичним підґрунтям. Чисельні експерименти показали, що цей метод може досягати близького до оптимального розв'язку навіть коли дані містять понад мільйон недоречних ознак.

Див. також

• Кластерний аналіз
• Добування даних
• Зниження розмірності
• Виділяння ознак
• Оптимізація гіперпараметрів
• Шаблон:Нп

Література

• Шаблон:Citation Шаблон:Ref-en
• Шаблон:Citation Шаблон:Ref-en
• Special Issue on Variable and Feature Selection —Journal of Machine Learning Research (2003) Шаблон:Ref-en
• An Introduction to Variable and Feature Selection (огляд) Шаблон:Ref-en
• Toward integrating feature selection algorithms for classification and clustering (огляд) Шаблон:Ref-en
• Efficient Feature Subset Selection and Subset Size Optimization (огляд 2010 року) Шаблон:Ref-en
• "Searching for Interacting Features" —Zhao & Liu, представлена на IJCAI (2007) Шаблон:Ref-en

Посилання

• Пакет обирання ознак, Університет штату Аризона (код Matlab)
• Змагання NIPS 2003 року (див. також Шаблон:Нп)
• Реалізація наївного баєсового класифікатора із обиранням ознак на Visual Basic (включає виконуваний та джерельний код)
• Програма обирання ознак мінімальної-надлишковості-максимальної-доречності (minimum-redundancy-maximum-relevance, mRMR)
• FEAST (відкриті алгоритми обирання ознак на C та MATLAB)
• Шаблон:Cite web