Relief (funktionsval)

Relief är en algoritm som utvecklades av Kira och Rendell 1992 och som använder en filtermetod för val av funktioner som är särskilt känslig för interaktioner med funktioner. Det designades ursprungligen för tillämpning på binära klassificeringsproblem med diskreta eller numeriska funktioner. Relief beräknar en funktionspoäng för varje funktion som sedan kan användas för att rangordna och välja topppoängfunktioner för funktionsval. Alternativt kan dessa poäng användas som funktionsvikter för att styra nedströms modellering. Relieffunktionspoängning baseras på identifieringen av funktionsvärdesskillnader mellan närmaste granninstanspar. Om en funktionsvärdesskillnad observeras i ett angränsande instanspar med samma klass (en "träff"), minskar egenskapspoängen. Alternativt, om en funktionsvärdesskillnad observeras i ett angränsande instanspar med olika klassvärden (en "miss"), ökar egenskapspoängen. Den ursprungliga Relief-algoritmen har sedan dess inspirerat en familj av Relief-baserade funktionsvalsalgoritmer (RBA), inklusive ReliefF-algoritmen. Utöver den ursprungliga Relief-algoritmen har RBA:er anpassats för att (1) fungera mer tillförlitligt i bullriga problem, (2) generalisera till problem med flera klasser (3) generalisera till numeriska resultat (dvs. regression) problem och (4) för att göra dem robust för ofullständiga (dvs. saknade) data.

Hittills har utvecklingen av RBA-varianter och -tillägg fokuserat på fyra områden; (1) förbättra prestandan för "core" Relief-algoritmen, dvs. undersöka strategier för grannval och instansviktning, (2) förbättra skalbarheten för "core" Relief-algoritmen till större funktionsutrymmen genom iterativa tillvägagångssätt, (3) metoder för flexibel anpassning Relief till olika datatyper, och (4) förbättring av Reliefkörningens effektivitet.

Deras styrkor är att de inte är beroende av heuristik, de körs i lågordet polynomtid, och de är brustoleranta och robusta för att presentera interaktioner, samt att de är tillämpliga för binära eller kontinuerliga data; den gör dock ingen skillnad mellan redundanta funktioner och ett lågt antal träningstillfällen lurar algoritmen.

Lättnadsalgoritm: Val av närmaste träff och närmaste missförekomst grannar innan poäng.

Lättnadsalgoritm

Ta en datamängd med n instanser av p funktioner, som tillhör två kända klasser. Inom datamängden ska varje funktion skalas till intervallet [0 1] (binära data ska förbli som 0 och 1). Algoritmen kommer att upprepas m gånger. Börja med en p -lång viktvektor (W) med nollor.

Vid varje iteration, ta särdragsvektorn (X) som tillhör en slumpmässig instans, och särdragsvektorerna för instansen närmast X (med euklidiskt avstånd) från varje klass. Den närmaste instansen av samma klass kallas 'nära-träff', och den närmaste instansen av olika klass kallas 'nära-miss'. Uppdatera viktvektorn så att

Sålunda minskar vikten av en given egenskap om den skiljer sig från den egenskapen i närliggande instanser av samma klass mer än närliggande instanser av den andra klassen, och ökar i omvänt fall.

Efter m iterationer, dividera varje element i viktvektorn med m . Detta blir relevansvektorn. Funktioner väljs om deras relevans är större än ett tröskelvärde τ .

Kira och Rendells experiment visade en tydlig kontrast mellan relevanta och irrelevanta egenskaper, vilket gjorde att τ kunde bestämmas genom inspektion. Det kan dock också bestämmas av Chebyshevs olikhet för en given konfidensnivå ( α ) att en τ på 1/sqrt(α*m) är tillräckligt bra för att göra sannolikheten för ett typ I-fel mindre än α , även om det anges att τ kan vara mycket mindre än så.

Relief beskrevs också som generaliserbar till multinomial klassificering genom nedbrytning i ett antal binära problem.

ReliefF Algoritm

Kononenko et al. föreslå ett antal uppdateringar av Relief. För det första hittar de nästan-träff- och nästan-miss-instanserna genom att använda Manhattan (L1)-normen snarare än den euklidiska (L2)-normen , även om motiveringen inte är specificerad. Dessutom fann de att det var tillräckligt att ta de absoluta skillnaderna mellan x i och nära-träff i , och x i och nästan-miss i för att uppdatera viktvektorn (snarare än kvadraten på dessa skillnader).

Tillförlitlig sannolikhetsuppskattning

Istället för att upprepa algoritmen m gånger, implementera den uttömmande (dvs. n gånger, en gång för varje instans) för relativt litet n (upp till tusen). Dessutom, snarare än att hitta den enstaka närmaste träffen och enstaka närmaste miss, vilket kan orsaka att redundanta och bullriga attribut påverkar valet av de närmaste grannarna, söker ReliefF efter k närmaste träffar och missar och beräknar ett genomsnitt av deras bidrag till vikten av varje funktion. k kan ställas in för alla individuella problem.

Ofullständiga uppgifter

I ReliefF bestäms bidraget av saknade värden till egenskapsvikten med hjälp av den villkorade sannolikheten att två värden ska vara lika eller olika, approximerade med relativa frekvenser från datamängden. Detta kan beräknas om en eller båda funktionerna saknas.

Flerklassiga problem

Istället för att använda Kira och Rendells föreslagna nedbrytning av en multinomial klassificering i ett antal binomialproblem, söker ReliefF efter k nästan misstag från varje klass och sätter ett genomsnitt av deras bidrag för att uppdatera W, viktat med den tidigare sannolikheten för varje klass.

Andra lättnadsbaserade algoritmtillägg/derivat

Följande RBA är ordnade kronologiskt från äldsta till senaste. De inkluderar metoder för att förbättra (1) kärnan i Relief-algoritmen, (2) iterativa metoder för skalbarhet, (3) anpassningar till olika datatyper, (4) strategier för beräkningseffektivitet eller (5) någon kombination av dessa mål. För mer om RBA, se dessa bokkapitel eller detta senaste recensionsdokument.

RRELIEFF

Robnik-Šikonja och Kononenko föreslår ytterligare uppdateringar av ReliefF, vilket gör det lämpligt för regression.

Lättad-F

Introducerat deterministisk grannvalsmetod och en ny metod för ofullständig datahantering.

Iterativ lättnad

Implementerad metod för att ta itu med bias mot icke-monotona egenskaper. Introducerade den första iterativa hjälpmetoden. För första gången bestämdes grannar unikt av en radietröskel och instanser viktades med deras avstånd från målinstansen.

I-RELIEF

Introducerad sigmoidal viktning baserad på avstånd från målinstans. Alla instanspar (inte bara en definierad delmängd av grannar) bidrog till poänguppdateringar. Föreslog en online-inlärningsvariant av Relief. Utökade det iterativa reliefkonceptet. Introducerade lokala inlärningsuppdateringar mellan iterationerna för förbättrad konvergens.

TuRF (aka Tuned ReliefF)

Specifikt försökt ta itu med brus i stora funktionsutrymmen genom rekursiv eliminering av funktioner och iterativ tillämpning av ReliefF.

Evaporativ kyllättnadF

Försöker på liknande sätt att ta itu med buller i stora utrymmen. Använde ett iterativt "evaporativt" avlägsnande av funktioner med lägsta kvalitet med hjälp av ReliefF-poäng i samband med ömsesidig information.

EReliefF (aka Extended ReliefF)

Ta itu med problem relaterade till ofullständig och multiklassdata.

VLSReliefF (aka Very Large Scale ReliefF)

Förbättrar dramatiskt effektiviteten för att upptäcka 2-vägs funktionsinteraktioner i mycket stora funktionsutrymmen genom att poängsätta slumpmässiga funktionsunderuppsättningar snarare än hela funktionsutrymmet.

ReliefMSS

Introducerad beräkning av egenskapsvikter i förhållande till genomsnittlig funktionsskillnad mellan instanspar.

SURFA

SURF identifierar närmaste grannar (både träffar och missar) baserat på en avståndströskel från målinstansen definierad av det genomsnittliga avståndet mellan alla par av instanser i träningsdatan. Resultaten tyder på förbättrad kraft för att upptäcka 2-vägs epistatiska interaktioner över ReliefF.

SURF* (alias SURFStar)

SURF* utökar SURF-algoritmen till att inte bara använda "nära" grannar i poänguppdateringar, utan även "fjärr"-instanser, utan använder inverterade poänguppdateringar för "fjärrinstanspar". Resultaten tyder på förbättrad förmåga att upptäcka 2-vägs epistatiska interaktioner över SURF, men en oförmåga att upptäcka enkla huvudeffekter (dvs univariata associationer).

SWRF*

SWRF* utökar SURF*-algoritmen och använder sigmoidviktning för att ta hänsyn till avståndet från tröskeln. Införde också ett modulärt ramverk för att vidareutveckla RBA:er som kallas MoRF.

MultiSURF* (alias MultiSURFStar)

MultiSURF* utökar SURF*-algoritmen och anpassar grannskapsgränserna nära/fjärrt baserat på medel- och standardavvikelsen för avstånden från målinstansen till alla andra. MultiSURF* använder standardavvikelsen för att definiera en dödbandszon där "mellandistans"-instanser inte bidrar till poängsättning. Bevis tyder på att MultiSURF* presterar bäst när det gäller att upptäcka rena 2-vägs funktionsinteraktioner.

ReliefSeq

Introducerar en funktionsmässigt adaptiv k-parameter för att mer flexibelt detektera univariata effekter och interaktionseffekter.

MultiSURF

MultiSURF förenklar MultiSURF*-algoritmen genom att bevara dödbandszonen och målinstans-centrerad grannskapsbestämning, men eliminera "långt"-poängen. Bevis tyder på att MultiSURF är ett väl avrundat alternativ, som kan upptäcka 2-vägs och 3-vägs interaktioner, såväl som enkla univariata associationer. Introducerade även RBA-programvarupaketet som heter ReBATE som inkluderar implementeringar av (Relief, ReliefF, SURF, SURF*, MultiSURF*, MultiSURF och TuRF).

VISPA

STIR omformulerar och justerar den ursprungliga lättnadsformeln något genom att inkludera provvariansen för de närmaste grannavstånden i uppskattningen av attributets betydelse. Denna varians tillåter beräkning av statistisk signifikans av funktioner och justering för flera tester av lättnadsbaserade poäng. För närvarande stöder STIR binär utfallsvariabel men kommer snart att utökas till multi-state och kontinuerligt utfall.

RBA-applikationer

Olika RBA har använts för val av funktioner i en mängd olika problemdomäner.

Se även

  1. ^ Kira, Kenji och Rendell, Larry (1992). Funktionsvalsproblemet: traditionella metoder och en ny algoritm . AAAI-92 Proceeds.
  2. ^ a b Kira, Kenji och Rendell, Larry (1992) A Practical Approach to Feature Selection , Proceedings of the Ninth International Workshop on Machine Learning, p249-256
  3. ^ a b Kononenko, Igor et al. Att övervinna närsyntheten av induktiva inlärningsalgoritmer med RELIEFF (1997), Applied Intelligence, 7(1), s39-55
  4. ^ a b c    Kononenko, Igor (1994-04-06). "Uppskattning av attribut: Analys och förlängningar av RELIEF". Maskininlärning: ECML-94 . Föreläsningsanteckningar i datavetenskap. Vol. 784. Springer, Berlin, Heidelberg. s. 171–182. doi : 10.1007/3-540-57868-4_57 . ISBN 978-3540578680 . S2CID 8190856 . {{ citera bok }} : Saknas eller tom |title= ( hjälp )
  5. ^ a b Robnik-Šikonja, Marko och Kononenko, Igor (1997). En anpassning av Relief för attributuppskattning vid regression. Machine Learning: Proceedings of the Fourteenth International Conference (ICML'97) (p296-304)
  6. ^ a b c    Urbanowicz, Ryan J.; Meeker, Melissa; LaCava, William; Olson, Randal S.; Moore, Jason H. (2018). "Reliefbaserat funktionsval: Introduktion och recension" . Journal of Biomedical Informatics . 85 : 189–203. arXiv : 1711.08421 . Bibcode : 2017arXiv171108421U . doi : 10.1016/j.jbi.2018.07.014 . PMC 6299836 . PMID 30031057 .
  7. ^   Kononenko, Igor, Robnik-Sikonja, Marko (2007-10-29). Utvärdering av icke-närsynt funktionskvalitet med (R)ReliefF . Chapman och Hall/CRC. s. 169–192. doi : 10.1201/9781584888796-9 . ISBN 9780429150418 .
  8. ^    Moore, Jason H. (2015). "Epistasanalys med hjälp av ReliefF". Epistasis . Metoder i molekylärbiologi. Vol. 1253. Humana Press, New York, NY. s. 315–325. doi : 10.1007/978-1-4939-2155-3_17 . ISBN 9781493921546 . PMID 25403540 .
  9. ^   Todorov, Alexandre (2016-07-08). En översikt över RELIEF-algoritmen och framsteg . MIT Press. ISBN 9780262034685 .
  10. ^   Kohavi, Ron; John, George H (1997-12-01). "Wrappers för val av funktionsdelmängder". Artificiell intelligens . 97 (1–2): 273–324. doi : 10.1016/S0004-3702(97)00043-X . ISSN 0004-3702 .
  11. ^   Draper, B.; Kaito, C.; Bins, J. (juni 2003). "Iterativ lättnad". 2003 konferens om datorseende och mönsterigenkänning Workshop . 6 : 62. doi : 10.1109/CVPRW.2003.10065 . S2CID 17599624 .
  12. ^     Sun, Yijun; Li, Jian (2006-06-25). "Iterativ RELIEF för funktionsviktning". Handlingar från den 23:e internationella konferensen om maskininlärning - ICML '06 . ACM. s. 913–920. CiteSeerX 10.1.1.387.7424 . doi : 10.1145/1143844.1143959 . ISBN 978-1595933836 . S2CID 1102692 .
  13. ^     Sun, Y. (juni 2007). "Iterativ RELIEF för funktionsviktning: Algoritmer, teorier och tillämpningar". IEEE-transaktioner på mönsteranalys och maskinintelligens . 29 (6): 1035-1051. doi : 10.1109/TPAMI.2007.1093 . ISSN 0162-8828 . PMID 17431301 . S2CID 14087053 .
  14. ^     Sun, Y.; Todorovic, S.; Goodison, S. (september 2010). "Lokalt inlärningsbaserat funktionsval för högdimensionell dataanalys" . IEEE-transaktioner på mönsteranalys och maskinintelligens . 32 (9): 1610–1626. doi : 10.1109/TPAMI.2009.190 . ISSN 0162-8828 . PMC 3445441 . PMID 20634556 .
  15. ^   Moore, Jason H.; White, Bill C. (2007-04-11). Tuning ReliefF för genomomfattande genetisk analys . Evolutionär beräkning, maskininlärning och datautvinning inom bioinformatik . Föreläsningsanteckningar i datavetenskap. Vol. 4447. Springer, Berlin, Heidelberg. s. 166–175. doi : 10.1007/978-3-540-71783-6_16 . ISBN 9783540717829 .
  16. ^     McKinney, BA; Reif, DM; Vit, BC; Crowe, JE; Moore, JH (2007-08-15). "Val av evaporativ kylfunktion för genotypdata som involverar interaktioner" . Bioinformatik . 23 (16): 2113–2120. doi : 10.1093/bioinformatics/btm317 . ISSN 1367-4803 . PMC 3988427 . PMID 17586549 .
  17. ^    Park, H.; Kwon, HC (augusti 2007). Utökade lättnadsalgoritmer i instansbaserad funktionsfiltrering . Sjätte internationella konferensen om avancerad språkbehandling och webbinformationsteknik (ALPIT 2007) . s. 123–128. doi : 10.1109/ALPIT.2007.16 . ISBN 978-0-7695-2930-1 . S2CID 15296546 .
  18. ^    Eppstein, MJ; Haake, P. (september 2008). Mycket storskalig ReliefF för genomomfattande associationsanalys . 2008 IEEE Symposium on Computational Intelligence in Bioinformatics and Computational Biology . s. 112–119. doi : 10.1109/CIBCB.2008.4675767 . ISBN 978-1-4244-1778-0 . S2CID 9296768 .
  19. ^   Chikhi, Salim; Benhammada, Sadek (2009-11-04). "ReliefMSS: en variant på en ReliefF-algoritm för funktionsrankning" . International Journal of Business Intelligence and Data Mining . 4 (3/4): 375. doi : 10.1504/ijbidm.2009.029085 . S2CID 15242788 .
  20. ^ a b     Greene, Casey S.; Penrod, Nadia M.; Kiralis, Jeff; Moore, Jason H. (2009-09-22). "Spatially Uniform ReliefF (SURF) för beräkningseffektiv filtrering av gen-geninteraktioner" . BioData Mining . 2 (1): 5. doi : 10.1186/1756-0381-2-5 . ISSN 1756-0381 . PMC 2761303 . PMID 19772641 .
  21. ^ a b   Greene, Casey S.; Himmelstein, Daniel S.; Kiralis, Jeff; Moore, Jason H. (2010-04-07). De informativa ytterligheterna: Att använda både närmaste och längst borta individer kan förbättra lindringsalgoritmer inom området mänsklig genetik . Evolutionär beräkning, maskininlärning och datautvinning inom bioinformatik . Föreläsningsanteckningar i datavetenskap. Vol. 6023. Springer, Berlin, Heidelberg. s. 182–193. doi : 10.1007/978-3-642-12211-8_16 . ISBN 9783642122101 .
  22. ^ a b c d   Urbanowicz, Ryan J.; Olson, Randal S.; Schmitt, Peter; Meeker, Melissa; Moore, Jason H. (2017-11-22). "Benchmarking Relief-Based Feature Selection Methods for Bioinformatics Data Mining". arXiv : 1711.08477 . Bibcode : 2017arXiv171108477U . PMID 30030120 .
  23. ^     Stokes, Matthew E.; Visweswaran, Shyam (2012-12-03). "Tillämpning av en rumsligt viktad lättnadsalgoritm för att rangordna genetiska prediktorer för sjukdom" . BioData Mining . 5 (1): 20. doi : 10.1186/1756-0381-5-20 . ISSN 1756-0381 . PMC 3554553 . PMID 23198930 .
  24. ^ a b   Granizo-Mackenzie, Delaney; Moore, Jason H. (2013-04-03). Flera trösklar rumsligt enhetlig lättnadF för genetisk analys av komplexa mänskliga sjukdomar . Evolutionär beräkning, maskininlärning och datautvinning inom bioinformatik . Föreläsningsanteckningar i datavetenskap. Vol. 7833. Springer, Berlin, Heidelberg. s. 1–10. doi : 10.1007/978-3-642-37189-9_1 . ISBN 9783642371882 .
  25. ^     McKinney, Brett A.; White, Bill C.; Grill, Diane E.; Li, Peter W.; Kennedy, Richard B.; Polen, Gregory A.; Oberg, Ann L. (2013-12-10). "ReliefSeq: A Gene-Wise Adaptive-K Nearest-Neighbor Feature Selection Tool för att hitta gen-geninteraktioner och huvudeffekter i mRNA-Seq genuttrycksdata" . PLOS ETT . 8 (12): e81527. Bibcode : 2013PLoSO...881527M . doi : 10.1371/journal.pone.0081527 . ISSN 1932-6203 . PMC 3858248 . PMID 24339943 .
  26. ^    Le, Trang; Urbanowicz, Ryan; Moore, Jason; McKinney, Brett (18 september 2018). "Val av STIR-funktioner för statistisk slutledning" . Bioinformatik . 35 (8): 1358–1365. doi : 10.1093/bioinformatics/bty788 . PMC 6477983 . PMID 30239600 .
  27. ^ Le, Trang (1 november 2018). "STIR Poster" . Figshare . doi : 10.6084/m9.figshare.7241417 . Hämtad 24 januari 2019 .
Hämtad från " https://en.wikipedia.org/w/index.php?title=Relief_(feature_selection)&oldid=1121144461 "