Selectarea funcției - Feature selection

În învățarea automată și statistică , selecția caracteristicilor , cunoscută și sub numele de selecție variabilă , selecție de atribute sau selecție de subset variabil , este procesul de selectare a unui subset de caracteristici relevante (variabile, predictori) pentru utilizare în construcția modelului. Tehnicile de selectare a caracteristicilor sunt utilizate din mai multe motive:

simplificarea modelelor pentru a le face mai ușor de interpretat de către cercetători / utilizatori,
timpi de antrenament mai scurți,
pentru a evita blestemul dimensionalității ,
îmbunătățiți compatibilitatea datelor cu o clasă de model de învățare,
codifică simetriile inerente prezente în spațiul de intrare.

Premisa centrală atunci când se utilizează o tehnică de selecție a caracteristicilor este aceea că datele conțin unele caracteristici care sunt fie redundante, fie irelevante și, astfel, pot fi înlăturate fără a atrage prea multe pierderi de informații. Redundant și irelevant sunt două noțiuni distincte, deoarece o caracteristică relevantă poate fi redundantă în prezența altei caracteristici relevante cu care este puternic corelată.

Tehnicile de selectare a caracteristicilor ar trebui să fie deosebite de extragerea caracteristicilor . Extragerea caracteristicilor creează noi caracteristici din funcțiile caracteristicilor originale, în timp ce selectarea caracteristicilor returnează un subset de caracteristici. Tehnicile de selectare a caracteristicilor sunt adesea folosite în domenii în care există multe caracteristici și relativ puține eșantioane (sau puncte de date). Cazurile arhetipale pentru aplicarea selecției caracteristicilor includ analiza textelor scrise și a datelor microarray de ADN , unde există multe mii de caracteristici și câteva zeci până la sute de eșantioane.

Introducere

Un algoritm de selecție a caracteristicilor poate fi văzut ca o combinație a unei tehnici de căutare pentru a propune noi subseturi de caracteristici, împreună cu o măsură de evaluare care marchează diferitele subseturi de caracteristici. Cel mai simplu algoritm este acela de a testa fiecare subset posibil de caracteristici găsindu-l pe cel care minimizează rata de eroare. Aceasta este o căutare exhaustivă a spațiului și este calculată intratabil pentru toate, cu excepția celor mai mici seturi de caracteristici. Alegerea metricei de evaluare influențează puternic algoritmul și aceste metrici de evaluare fac distincția între cele trei categorii principale de algoritmi de selecție a caracteristicilor: împachetări, filtre și metode încorporate.

Metodele Wrapper folosesc un model predictiv pentru a înscrie subseturi de caracteristici. Fiecare subset nou este folosit pentru a antrena un model, care este testat pe un set de rezistență. Numărarea numărului de greșeli făcute pe acel set de rezistență (rata de eroare a modelului) dă scorul pentru acel subset. Deoarece metodele de împachetare formează un nou model pentru fiecare subset, acestea sunt foarte intensive din punct de vedere al calculului, dar oferă, de obicei, cel mai performant set de caracteristici pentru acel tip particular de model sau problemă tipică.
Metodele de filtrare utilizează o măsură proxy în locul ratei de eroare pentru a înscrie un subset de caracteristici. Această măsură este aleasă pentru a fi rapidă la calcul, captând totuși utilitatea setului de caracteristici. Măsurile obișnuite includ informațiile reciproce , informațiile reciproce punctuale , coeficientul de corelație produs-moment Pearson , algoritmi bazați pe relief și distanța inter / intra clasă sau scorurile testelor de semnificație pentru fiecare combinație clasă / caracteristică. Filtrele sunt de obicei mai puțin intensive din punct de vedere al calculului decât ambalajele, dar produc un set de caracteristici care nu este acordat unui tip specific de model predictiv. Această lipsă de reglare înseamnă că un set de caracteristici dintr-un filtru este mai general decât setul dintr-un wrapper, oferind de obicei performanțe mai mici de predicție decât un wrapper. Cu toate acestea, setul de caracteristici nu conține ipotezele unui model de predicție și, prin urmare, este mai util pentru a expune relațiile dintre caracteristici. Multe filtre oferă o clasare a caracteristicilor, mai degrabă decât un subset de caracteristici explicite, iar punctul tăiat din clasament este ales prin validare încrucișată . Metodele de filtrare au fost, de asemenea, utilizate ca o etapă de preprocesare pentru metodele de înfășurare, permițând utilizarea unei înfășurări pe probleme mai mari. O altă abordare populară este algoritmul de eliminare a caracteristicilor recursive, utilizat în mod obișnuit cu mașinile vectoriale de asistență pentru a construi în mod repetat un model și a elimina caracteristici cu greutăți mici.
Metodele încorporate sunt un grup captivant de tehnici care efectuează selectarea caracteristicilor ca parte a procesului de construcție a modelului. Exemplul acestei abordări este metoda LASSO pentru construirea unui model liniar, care penalizează coeficienții de regresie cu o penalizare L1, micșorând mulți dintre ei la zero. Orice caracteristici care au coeficienți de regresie diferiți de zero sunt „selectate” de algoritmul LASSO. Îmbunătățirile aduse LASSO includ Bolasso care pornește mostre; Regularizarea elastică a rețelei , care combină pedeapsa L1 a lui LASSO cu pedeapsa L2 a regresiei creastei ; și FeaLect care marchează toate caracteristicile pe baza analizei combinatorii a coeficienților de regresie. AEFS extinde în continuare LASSO la scenariu neliniar cu autoencoderi. Aceste abordări tind să se situeze între filtre și împachetări în termeni de complexitate de calcul.

În analiza de regresie tradițională , cea mai populară formă de selectare a caracteristicilor este regresia în trepte , care este o tehnică de împachetare. Este un algoritm lacom care adaugă cea mai bună caracteristică (sau șterge cea mai proastă caracteristică) la fiecare rundă. Principala problemă de control este să decidem când să oprim algoritmul. În învățarea automată, acest lucru se face de obicei prin validare încrucișată . În statistici, unele criterii sunt optimizate. Acest lucru duce la problema inerentă a cuiburilor. Au fost explorate metode mai robuste, cum ar fi ramificația și rețeaua liniară legată și în bucăți.

Selecția subsetului

Selecția subsetului evaluează un subset de caracteristici ca grup pentru a se potrivi. Algoritmii de selecție a subseturilor pot fi împărțiți în împachetări, filtre și metode încorporate. Wrappers folosesc un algoritm de căutare pentru a căuta prin spațiul posibilelor caracteristici și pentru a evalua fiecare subset rulând un model pe subset. Împachetările pot fi costisitoare din punct de vedere al calculului și pot risca să se potrivească prea mult cu modelul. Filtrele sunt similare cu ambalajele din abordarea de căutare, dar în loc să se evalueze în raport cu un model, este evaluat un filtru mai simplu. Tehnicile încorporate sunt încorporate și specifice unui model.

Multe abordări de căutare populare folosesc alpinism lacom , care evaluează iterativ un subset de caracteristici candidat, apoi modifică subsetul și evaluează dacă noul subset este o îmbunătățire față de vechiul. Evaluarea subseturilor necesită o măsurătoare de notare care notează un subset de caracteristici. Căutarea exhaustivă este în general impracticabilă, astfel încât la un anumit punct de oprire definit de implementator (sau operator), subsetul de caracteristici cu cel mai mare scor descoperit până la acel punct este selectat ca subset de caracteristici satisfăcătoare. Criteriul de oprire variază în funcție de algoritm; criteriile posibile includ: un scor de subset depășește un prag, timpul maxim de rulare permis al unui program a fost depășit etc.

Tehnicile alternative bazate pe căutare se bazează pe urmărirea proiecției țintite care găsește proiecții cu dimensiuni reduse ale datelor care au un scor înalt: sunt selectate apoi caracteristicile care au cele mai mari proiecții în spațiul cu dimensiuni inferioare.

Abordările de căutare includ:

Două metrici populare de filtrare pentru problemele de clasificare sunt corelația și informațiile reciproce , deși nici nu sunt metrici adevărate sau „ măsurători de distanță” în sens matematic, deoarece nu reușesc să respecte inegalitatea triunghiului și, prin urmare, nu calculează nici o „distanță” reală - ar trebui mai degrabă să fie privit ca „scoruri”. Aceste scoruri sunt calculate între o caracteristică candidată (sau un set de caracteristici) și categoria de ieșire dorită. Există, totuși, valori adevărate care sunt o funcție simplă a informațiilor reciproce; vezi aici .

Alte valori de filtrare disponibile includ:

Separabilitatea clasei
- Probabilitate de eroare
- Distanța între clase
- Distanță probabilistică
- Entropie
Selectarea caracteristicilor bazate pe coerență
Selecție de caracteristici bazată pe corelație

Criterii de optimitate

Alegerea criteriilor de optimitate este dificilă, deoarece există mai multe obiective într-o sarcină de selecție a caracteristicilor. Multe criterii comune încorporează o măsură de precizie, penalizată de numărul de caracteristici selectate. Exemplele includ criteriul de informare Akaike (AIC) și C _p al lui Mallows , care au o penalizare de 2 pentru fiecare caracteristică adăugată. AIC se bazează pe teoria informației și este efectiv derivat prin principiul entropiei maxime .

Alte criterii sunt criteriul Bayesian de informații (BIC), care folosește o penalizare de pentru fiecare caracteristică adăugată, lungimea descrierii minime (MDL) care se folosește asimptotic , Bonferroni / RIC care utilizează , selectarea caracteristicii de dependență maximă și o varietate de noi criterii motivate prin rata de descoperire falsă (FDR), care utilizează ceva apropiat . Un criteriu al ratei de entropie maximă poate fi, de asemenea, utilizat pentru a selecta cel mai relevant subset de caracteristici. ${\ displaystyle {\ sqrt {\ log {n}}}}$ ${\ displaystyle {\ sqrt {\ log {n}}}}$ ${\ displaystyle {\ sqrt {2 \ log {p}}}}$ ${\ displaystyle {\ sqrt {2 \ log {\ frac {p} {q}}}}}$

Învățarea structurii

Selecția caracteristicilor de filtrare este un caz specific al unei paradigme mai generale numite învățarea structurii . Selecția de caracteristici găsește setul de caracteristici relevante pentru o anumită variabilă țintă, în timp ce învățarea structurii găsește relațiile dintre toate variabilele, de obicei prin exprimarea acestor relații ca grafic. Cei mai comuni algoritmi de învățare a structurii presupun că datele sunt generate de o rețea bayesiană , astfel încât structura este un model grafic direcționat . Soluția optimă pentru problema de selectare a caracteristicilor de filtrare este pătura Markov a nodului țintă, iar într-o rețea Bayesiană, există o pătură Markov unică pentru fiecare nod.

Mecanisme de selecție a caracteristicilor bazate pe teoria informației

Există diferite mecanisme de selecție a caracteristicilor care utilizează informații reciproce pentru a puncta diferitele caracteristici. De obicei utilizează același algoritm:

Calculați informațiile reciproce ca scor pentru toate caracteristicile ( ) și clasa țintă ( $c$ ) ${\ displaystyle f_ {i} \ în F}$
Selectați caracteristica cu cel mai mare scor (de exemplu ) și adăugați-o la setul de caracteristici selectate ( $S$ ) ${\ displaystyle {\ underset {f_ {i} \ în F} {\ operatorname {argmax}}} (I (f_ {i}, c))}$
Calculați scorul care ar putea fi derivat din informațiile reciproce
Selectați caracteristica cu cel mai mare scor și adăugați-o la setul de caracteristici selectate (de ex. ) ${\ displaystyle {\ underset {f_ {i} \ în F} {\ operatorname {argmax}}} (I_ {derivat} (f_ {i}, c))}$
Repetați 3. și 4. până când este selectat un anumit număr de caracteristici (de exemplu ) ${\ displaystyle | S | = l}$

Cea mai simplă abordare folosește informațiile reciproce ca scor „derivat”.

Cu toate acestea, există diferite abordări care încearcă să reducă redundanța dintre caracteristici.

Selecția caracteristicii Minim-redundanță-maximă-relevanță (mRMR)

Peng și colab. a propus o metodă de selectare a caracteristicilor care poate utiliza fie informații reciproce, corelație, fie scoruri de distanță / similaritate pentru a selecta caracteristici. Scopul este de a penaliza relevanța unei caracteristici prin redundanța acesteia în prezența celorlalte caracteristici selectate. Relevanța unui set de caracteristici $S$ pentru clasa $c$ este definită de valoarea medie a tuturor valorilor informațiilor reciproce dintre caracteristica individuală $f i$ și clasa $c$ după cum urmează:

{\ displaystyle D (S, c) = {\ frac {1} {| S |}} \ sum _ {f_ {i} \ in S} I (f_ {i}; c)}

.

Redundanța tuturor caracteristicilor din setul $S$ este valoarea medie a tuturor valorilor informațiilor reciproce dintre caracteristica $f i$ și caracteristica $f j$ :

{\ displaystyle R (S) = {\ frac {1} {| S | ^ {2}}} \ sum _ {f_ {i}, f_ {j} \ in S} I (f_ {i}; f_ { j})}

Criteriul RMN este o combinație a două măsuri date mai sus și este definit după cum urmează:

{\ displaystyle \ 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] .}

Să presupunem că există $n caracteristici$ complete. Fie $x i$ funcția indicatoare de setare pentru caracteristica $f i$ , astfel încât $x i = 1 să$ indice prezența și $x i = 0 să$ indice absența caracteristicii $f i$ în setul de caracteristici optim la nivel global. Să și . Cele de mai sus pot fi apoi scrise ca o problemă de optimizare: ${\ displaystyle c_ {i} = I (f_ {i}; c)}$ ${\ displaystyle a_ {ij} = I (f_ {i}; f_ {j})}$

{\ displaystyle \ mathrm {mRMR} = \ max _ {x \ in \ {0,1 \} ^ {n}} \ left [{\ 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}}} \ right].}

Algoritmul RMN este o aproximare a algoritmului teoretic optim de selectare a caracteristicilor de dependență maximă care maximizează informațiile reciproce între distribuția comună a caracteristicilor selectate și variabila de clasificare. Deoarece mRMR aproximează problema de estimare combinatorie cu o serie de probleme mult mai mici, fiecare dintre acestea implicând doar două variabile, se folosește astfel probabilități articulare perechi care sunt mai robuste. În anumite situații, algoritmul poate subestima utilitatea caracteristicilor, deoarece nu are nicio modalitate de a măsura interacțiunile dintre caracteristici care pot crește relevanța. Acest lucru poate duce la performanțe slabe atunci când caracteristicile sunt inutile individual, dar sunt utile atunci când sunt combinate (un caz patologic se găsește atunci când clasa este o funcție de paritate a caracteristicilor). În general, algoritmul este mai eficient (în ceea ce privește cantitatea de date necesară) decât selecția teoretică optimă a dependenței maxime, totuși produce un set de caracteristici cu redundanță redusă în perechi.

RMN este o instanță a unei clase mari de metode de filtrare care se diferențiază între relevanță și redundanță în moduri diferite.

Selecția caracteristicilor de programare quadratică

RMN este un exemplu tipic de strategie lacomă incrementală pentru selectarea caracteristicilor: odată ce a fost selectată o caracteristică, aceasta nu poate fi deselectată într-o etapă ulterioară. În timp ce mRMR ar putea fi optimizat utilizând căutarea plutitoare pentru a reduce unele caracteristici, ar putea fi, de asemenea, reformulat ca o problemă globală de optimizare a programării pătratice după cum urmează:

{\ displaystyle \ mathrm {QPFS}: \ min _ {\ mathbf {x}} \ left \ {\ alpha \ mathbf {x} ^ {T} H \ mathbf {x} - \ mathbf {x} ^ {T} F \ right \} \ quad {\ mbox {st}} \ \ sum _ {i = 1} ^ {n} x_ {i} = 1, x_ {i} \ geq 0}

unde este vectorul de relevanță a caracteristicilor presupunând că există $n$ caracteristici în total, este matricea redundanței perechi de caracteristici și reprezintă greutăți relative ale caracteristicilor. QPFS este rezolvat prin programare pătratică. Este arătat recent că QFPS este părtinitoare față de caracteristici cu entropie mai mică, datorită plasării sale termenului redundanță caracteristica auto pe diagonala $H$ . ${\ displaystyle F_ {n \ times 1} = [I (f_ {1}; c), \ ldots, I (f_ {n}; c)] ^ {T}}$ ${\ displaystyle H_ {n \ times n} = [I (f_ {i}; f_ {j})] _ {i, j = 1 \ ldots n}}$ ${\ displaystyle \ mathbf {x} _ {n \ times 1}}$ ${\ displaystyle I (f_ {i}; f_ {i})}$

Informații reciproce condiționate

Un alt scor obținut pentru informațiile reciproce se bazează pe relevanța condiționată:

{\ displaystyle \ mathrm {SPEC_ {CMI}}: \ max _ {\ mathbf {x}} \ left \ {\ mathbf {x} ^ {T} Q \ mathbf {x} \ right \} \ quad {\ mbox {st}} \ \ | \ mathbf {x} \ | = 1, x_ {i} \ geq 0}

unde și . ${\ displaystyle Q_ {ii} = I (f_ {i}; c)}$ ${\ displaystyle Q_ {ij} = I (f_ {i}; c | f_ {j}), i \ neq j}$

Un avantaj al $SPEC CMI$ este că poate fi rezolvat pur și simplu prin găsirea vectorului propriu dominant al $Q$ , deci este foarte scalabil. $SPEC CMI$ gestionează, de asemenea, interacțiunea cu caracteristicile de ordinul doi.

Informații comune comune

Într-un studiu al diferitelor scoruri Brown și colab. a recomandat informațiile comune comune ca un scor bun pentru selectarea caracteristicilor. Scorul încearcă să găsească caracteristica, care adaugă cele mai noi informații la caracteristicile deja selectate, pentru a evita redundanța. Scorul este formulat după cum urmează:

{\ displaystyle {\ begin {align} JMI (f_ {i}) & = \ sum _ {f_ {j} \ în 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}}}

Scorul folosește informațiile reciproce condiționate și informațiile reciproce pentru a estima redundanța dintre caracteristicile deja selectate ( ) și caracteristica investigată ( ). ${\ displaystyle f_ {j} \ în S}$ ${\ displaystyle f_ {i}}$

Criteriul de independență Hilbert-Schmidt Selecția de caracteristici bazată pe lazo

Pentru date de probă de dimensiuni mari și mici (de exemplu, dimensionalitate> 10 ⁵ și numărul de probe <10 ³ ), este util Lasso de criteriu de independență Hilbert-Schmidt (HSIC Lasso). Problema de optimizare Lasso HSIC este dată ca

{\ displaystyle \ 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 {\ mbox {st}} \ x_ {1}, \ ldots, x_ {n} \ geq 0,}

în cazul în care este o măsură de independență bazată pe nucleu numit (empiric) Hilbert-Schmidt criteriul independenței (HSIC), denotă urme , este parametrul de regularizare, și sunt de intrare și de ieșire centrate matrici Gram , și sunt matrice Gram, și sunt funcții de kernel, este matricea de centrare, este matricea de identitate $m-$ dimensională ( $m$ : numărul de eșantioane), este vectorul $m-$ dimensional cu toate și este -norma. HSIC ia întotdeauna o valoare non-negativă și este zero dacă și numai dacă două variabile aleatorii sunt statistic independente atunci când se utilizează un nucleu universal de reproducere, cum ar fi nucleul Gaussian. ${\ displaystyle {\ mbox {HSIC}} (f_ {k}, c) = {\ mbox {tr}} ({\ bar {\ mathbf {K}}} ^ {(k)} {\ bar {\ mathbf {L}}})}$ ${\ displaystyle {\ mbox {tr}} (\ cdot)}$ ${\ displaystyle \ lambda}$ ${\ displaystyle {\ bar {\ mathbf {K}}} ^ {(k)} = \ mathbf {\ Gamma} \ mathbf {K} ^ {(k)} \ mathbf {\ Gamma}}$ ${\ displaystyle {\ bar {\ mathbf {L}}} = \ mathbf {\ Gamma} \ mathbf {L} \ mathbf {\ Gamma}}$ ${\ displaystyle K_ {i, j} ^ {(k)} = K (u_ {k, i}, u_ {k, j})}$ ${\ displaystyle L_ {i, j} = L (c_ {i}, c_ {j})}$ ${\ displaystyle K (u, u ')}$ ${\ displaystyle L (c, c ')}$ ${\ displaystyle \ mathbf {\ Gamma} = \ mathbf {I} _ {m} - {\ frac {1} {m}} \ mathbf {1} _ {m} \ mathbf {1} _ {m} ^ { T}}$ ${\ displaystyle \ mathbf {I} _ {m}}$ ${\ displaystyle \ mathbf {1} _ {m}}$ ${\ displaystyle \ | \ cdot \ | _ {1}}$ ${\ displaystyle \ ell _ {1}}$

HSIC Lasso poate fi scris ca

{\ displaystyle \ mathrm {HSIC_ {Lasso}}: \ min _ {\ mathbf {x}} {\ frac {1} {2}} \ left \ | {\ bar {\ mathbf {L}}} - \ sum _ {k = 1} ^ {n} x_ {k} {\ bar {\ mathbf {K}}} ^ {(k)} \ right \ | _ {F} ^ {2} + \ lambda \ | \ mathbf {x} \ | _ {1}, \ quad {\ mbox {st}} \ x_ {1}, \ ldots, x_ {n} \ geq 0,}

unde este norma Frobenius . Problema de optimizare este o problemă Lasso și, prin urmare, poate fi rezolvată eficient cu un rezolvator Lasso de ultimă generație, cum ar fi metoda Lagrangiană dublă augmentată . ${\ displaystyle \ | \ cdot \ | _ {F}}$

Selectarea funcției de corelare

Măsura de selectare a caracteristicilor de corelație (CFS) evaluează subseturile de caracteristici pe baza următoarei ipoteze: „Subseturile de caracteristici bune conțin caracteristici foarte corelate cu clasificarea, dar necorelate între ele”. Următoarea ecuație dă meritul unui subset de caracteristici S format din k caracteristici:

{\ displaystyle \ mathrm {Merit} _ {S_ {k}} = {\ frac {k {\ overline {r_ {cf}}}} {\ sqrt {k + k (k-1) {\ overline {r_ { ff}}}}}}.}

Aici este valoarea medie a tuturor corelațiilor de clasificare a caracteristicilor și este valoarea medie a tuturor corelațiilor caracteristică-caracteristică. Criteriul CFS este definit astfel: ${\ displaystyle {\ overline {r_ {cf}}}}$ ${\ displaystyle {\ overline {r_ {ff}}}}$

{\ displaystyle \ mathrm {CFS} = \ max _ {S_ {k}} \ left [{\ frac {r_ {cf_ {1}} + r_ {cf_ {2}} + \ cdots + r_ {cf_ {k} }} {\ sqrt {k + 2 (r_ {f_ {1} f_ {2}} + \ cdots + r_ {f_ {i} f_ {j}} + \ cdots + r_ {f_ {k} f_ {k- 1}})}}} \ dreapta].}

Și variabilele sunt denumite în continuare corelații, dar nu sunt neapărat coeficientul de corelație Pearson sau ρ Spearman . Disertația lui Hall nu folosește niciuna dintre acestea, ci folosește trei măsuri diferite de relaționare, lungimea descrierii minime (MDL), incertitudinea simetrică și relieful . ${\ displaystyle r_ {cf_ {i}}}$ ${\ displaystyle r_ {f_ {i} f_ {j}}}$

Fie x _i funcția indicatoare de membru setată pentru caracteristica f _i ; atunci cele de mai sus pot fi rescrise ca o problemă de optimizare:

{\ displaystyle \ mathrm {CFS} = \ max _ {x \ in \ {0,1 \} ^ {n}} \ left [{\ frac {(\ sum _ {i = 1} ^ {n} a_ { i} x_ {i}) ^ {2}} {\ sum _ {i = 1} ^ {n} x_ {i} + \ sum _ {i \ neq j} 2b_ {ij} x_ {i} x_ {j }}}\dreapta].}

Problemele combinatorii de mai sus sunt, de fapt, probleme mixte de programare liniară 0-1 care pot fi rezolvate folosind algoritmi ramificați și legați .

Arborii regularizați

Caracteristicile dintr-un arbore de decizie sau dintr-un ansamblu de arbori se arată că sunt redundante. O metodă recentă numită copac regularizat poate fi utilizată pentru selectarea subsetului de caracteristici. Arborii regularizați penalizează folosind o variabilă similară cu variabilele selectate la nodurile de arbore anterioare pentru împărțirea nodului curent. Arborii regularizați trebuie să construiască doar un model de arbore (sau un model de ansamblu de arbori) și, prin urmare, sunt eficienți din punct de vedere al calculului.

Arborii regularizați gestionează în mod natural trăsături numerice și categorice, interacțiuni și neliniarități. Acestea sunt invariante pentru a atribui scale (unități) și insensibile la valori anormale și, prin urmare, necesită o preprocesare redusă a datelor, cum ar fi normalizarea . Pădurea regularizată aleatorie (RRF) este un tip de copaci regularizați. RRF ghidat este un RRF îmbunătățit, care este ghidat de scorurile de importanță dintr-o pădure obișnuită obișnuită.

Prezentare generală asupra metodelor metaheuristice

O metaheuristică este o descriere generală a unui algoritm dedicat rezolvării problemelor dificile (de obicei problemă NP-hard ) de optimizare pentru care nu există metode de rezolvare clasice. În general, o metaheuristică este un algoritm stocastic care tinde să atingă un optim global. Există multe metaheuristici, de la o simplă căutare locală la un algoritm complex de căutare globală.

Principii principale

Metodele de selectare a caracteristicilor sunt prezentate în mod obișnuit în trei clase, pe baza modului în care combină algoritmul de selecție și construirea modelului.

Metoda filtrului

Metoda de filtrare pentru selectarea caracteristicilor

Metodele de tip filtrare selectează variabile indiferent de model. Ele se bazează doar pe caracteristici generale, cum ar fi corelația cu variabila de prezis. Metodele de filtrare suprimă cele mai puțin interesante variabile. Celelalte variabile vor face parte dintr-o clasificare sau un model de regresie utilizat pentru a clasifica sau a prezice date. Aceste metode sunt deosebit de eficiente în timp de calcul și sunt robuste la supra-montare.

Metodele de filtrare tind să selecteze variabile redundante atunci când nu iau în considerare relațiile dintre variabile. Cu toate acestea, caracteristici mai elaborate încearcă să minimizeze această problemă prin eliminarea variabilelor foarte corelate între ele, cum ar fi algoritmul Filtru bazat pe corelare rapidă (FCBF).

Metoda ambalajului

Metoda Wrapper pentru selectarea caracteristicilor

Metodele Wrapper evaluează subseturi de variabile care permit, spre deosebire de abordările de filtrare, să detecteze posibilele interacțiuni dintre variabile. Cele două dezavantaje principale ale acestor metode sunt:

Riscul crescut de supraagregare atunci când numărul de observații este insuficient.
Timpul de calcul semnificativ când numărul de variabile este mare.

Metoda încorporată

Metodă încorporată pentru selectarea funcției

S-au propus recent metode încorporate care încearcă să combine avantajele ambelor metode anterioare. Un algoritm de învățare profită de propriul proces de selecție variabilă și efectuează simultan selecția și clasificarea caracteristicilor, cum ar fi algoritmul FRMT.

Aplicarea metaheuristicii de selecție a caracteristicilor

Acesta este un studiu al aplicației metaheuristicii de selecție a caracteristicilor utilizate în ultima perioadă în literatură. Acest sondaj a fost realizat de J. Hammon în teza sa din 2013.

Cerere	Algoritm	Abordare	Clasificator	Funcția de evaluare	Referinţă
SNP-uri	Selectarea caracteristicilor folosind similaritatea caracteristicilor	Filtru		r ²	Phuong 2005
SNP-uri	Algoritm genetic	Înveliș	Arborele deciziei	Precizie de clasificare (de 10 ori)	Șah 2004
SNP-uri	Alpinism pe deal	Filtru + Wrapper	Naiv Bayesian	Suma reziduală estimată de pătrate	2007 lung
SNP-uri	Recuocare simulată		Bayesian naiv	Precizie de clasificare (de 5 ori)	Ustunkar 2011
Segmentează condiționat	Colonia de furnici	Înveliș	Retele neuronale artificiale	MSE	Al-ani 2005
Marketing	Recuocare simulată	Înveliș	Regresie	AIC , r ²	Meiri 2006
Economie	Recuocare simulată, algoritm genetic	Înveliș	Regresie	BIC	Kapetanios 2007
Masa spectrală	Algoritm genetic	Înveliș	Regresie liniară multiplă, pătrate minime parțiale	eroare de predicție rădăcină-medie-pătrat	Broadhurst și colab. 1997
Spam	Binar PSO + Mutație	Înveliș	Arborele deciziei	cost ponderat	Zhang 2014
Microarray	Căutare Tabu + PSO	Înveliș	Asistență Vector Machine , K Vecinii cei mai apropiați	Distanta euclidiana	Chuang 2009
Microarray	Algoritm genetic PSO +	Înveliș	Suport Machine Vector	Precizie de clasificare (de 10 ori)	Alba 2007
Microarray	Algoritm genetic + Căutare locală iterată	Încorporat	Suport Machine Vector	Precizie de clasificare (de 10 ori)	Duval 2009
Microarray	Căutare locală iterată	Înveliș	Regresie	Probabilitate posterioară	Hans 2007
Microarray	Algoritm genetic	Înveliș	K Vecinii mai apropiați	Acuratețea clasificării ( validare încrucișată exclusivă )	Jirapech-Umpai 2005
Microarray	Algoritm genetic hibrid	Înveliș	K Vecinii mai apropiați	Acuratețea clasificării (validare încrucișată exclusivă)	Oh 2004
Microarray	Algoritm genetic	Înveliș	Suport Machine Vector	Sensibilitate și specificitate	Xuan 2011
Microarray	Algoritm genetic	Înveliș	Toate aparatele de suport pentru perechi	Acuratețea clasificării (validare încrucișată exclusivă)	Peng 2003
Microarray	Algoritm genetic	Încorporat	Suport Machine Vector	Precizie de clasificare (de 10 ori)	Hernandez 2007
Microarray	Algoritm genetic	Hibrid	Suport Machine Vector	Acuratețea clasificării (validare încrucișată exclusivă)	Huerta 2006
Microarray	Algoritm genetic		Suport Machine Vector	Precizie de clasificare (de 10 ori)	Muni 2006
Microarray	Algoritm genetic	Înveliș	Suport Machine Vector	EH-DIALL, CLUMP	Jourdan 2005
Boala Alzheimer	T-testul lui Welch	Filtru	Suportă mașină vectorială	Precizie de clasificare (de 10 ori)	Zhang 2015
Viziunea computerizată	Selecție infinită de caracteristici	Filtru	Independent	Precizie medie , ROC AUC	Roffo 2015
Microarrays	Eigenvector Centrality FS	Filtru	Independent	Precizie medie, precizie, ASC ROC	Roffo & Melzi 2016
XML	Tau simetric (ST)	Filtru	Clasificare asociativă structurală	Precizie, acoperire	Shaharanee & Hadzic 2014

Selecția de caracteristici încorporată în algoritmi de învățare

Unii algoritmi de învățare efectuează selecția caracteristicilor ca parte a operației lor generale. Acestea includ:

${\ displaystyle l_ {1}}$ -tehnici de regularizare , cum ar fi regresia rar, LASSO și -SVM ${\ displaystyle l_ {1}}$
Arborii regularizați, de exemplu pădure aleatorie regularizată implementată în pachetul RRF
Arborele deciziei
Algoritm memetic
Logit multinomial aleatoriu (RMNL)
Rețele de codificare automată cu un strat de blocaj
Selectarea caracteristicilor submodulare
Selecție de caracteristici bazate pe învățarea locală. Comparativ cu metodele tradiționale, nu implică nici o căutare euristică, poate rezolva cu ușurință probleme cu mai multe clase și funcționează atât pentru probleme liniare, cât și pentru cele neliniare. De asemenea, este susținut de o bază teoretică puternică. Experimentele numerice au arătat că metoda poate realiza o soluție aproape de optimă chiar și atunci când datele conțin> 1M caracteristici irelevante.
Sistem de recomandare bazat pe selectarea caracteristicilor. Metodele de selectare a caracteristicilor sunt introduse în cercetarea sistemului de recomandare.

Vezi si

Referințe

Lecturi suplimentare

Guyon, Isabelle; Elisseeff, Andre (2003). „O introducere în selectarea variabilelor și a caracteristicilor” . Journal of Machine Learning Research . 3 : 1157-1182.
Harrell, F. (2001). Strategii de modelare prin regresie . Springer. ISBN 0-387-95232-2.
Liu, Huan; Motoda, Hiroshi (1998). Selecție de caracteristici pentru descoperirea cunoștințelor și extragerea datelor . Springer. ISBN 0-7923-8198-X.
Liu, Huan; Yu, Lei (2005). „Către integrarea algoritmilor de selecție a caracteristicilor pentru clasificare și clusterizare”. Tranzacții IEEE privind cunoașterea și ingineria datelor . 17 (4): 491-502. doi : 10.1109 / TKDE.2005.66 . S2CID 1607600 .

linkuri externe

Pachet de selecție a caracteristicilor, Universitatea de Stat din Arizona (Cod Matlab)
NIPS provocare 2003 (vezi și NIPS )
Implementare Naive Bayes cu selectarea caracteristicilor în Visual Basic (include codul executabil și sursa)
Programul de selecție a funcției minim-redundanță-maximă-relevanță (mRMR)
FEAST (algoritmi Open Source Feature Selection în C și MATLAB)

Languages

In other projects