{"id":16954,"date":"2019-01-26T09:59:30","date_gmt":"2019-01-26T08:59:30","guid":{"rendered":"https:\/\/thingsolver.com\/blog\/friday-talks-the-dark-horse-of-isolation-forest\/"},"modified":"2024-11-29T13:58:33","modified_gmt":"2024-11-29T12:58:33","slug":"razgovori-petkom-crni-konj-algoritma-isolation-forest","status":"publish","type":"post","link":"https:\/\/thingsolver.com\/sr\/blog\/razgovori-petkom-crni-konj-algoritma-isolation-forest\/","title":{"rendered":"Razgovori petkom: &#8222;Crni konj&#8220; algoritma Isolation Forest"},"content":{"rendered":"<p>Kada se bavimo anomalijama u podacima, postoji mnogo izazova koje treba re\u0161iti. Vec\u0301 smo imali nekoliko \u010dlanaka na ovu temu, a ako ih vec\u0301 niste pro\u010ditali, predla\u017eem vam da pogledate<a href=\"https:\/\/thingsolver.com\/anomaly-detection\/\"> ovaj<\/a>, i <a href=\"https:\/\/thingsolver.com\/time-series-anomaly-detection-using-a-variational-autoencoder-vae\/\">ovaj<\/a>, od mog kolege Milo\u0161a. U ovom postu c\u0301u govoriti o jednom od mojih najvec\u0301ih favorita me\u0111u algoritmima za otkrivanje anomalija. Jednostavan je, superbrz i efikasan, sa malim zahtevima za memorijom i linearnom vremenskom slo\u017eeno\u0161c\u0301u. Nec\u0301u da pri\u010dam o upotrebi, po\u0161to sam nai\u0161ao na odli\u010dan \u010dlanak o <a href=\"https:\/\/towardsdatascience.com\/\" target=\"_blank\" rel=\"noopener\">Kretanju ka nauci podataka <\/a>(pogledajte: <a href=\"https:\/\/towardsdatascience.com\/outlier-detection-with-isolation-forest-3d190448d45e\" target=\"_blank\" rel=\"noopener\">Detekcija odstupanja sa algoritmom Isolation Forest<\/a>). Ideja je da podelim svoje utiske, i da vas inspiri\u0161em da ga isprobate, i da mi date svoje mi\u0161ljenje o tome.<\/p>\n<div id=\"ez-toc-container\" class=\"ez-toc-v2_0_72 counter-hierarchy ez-toc-counter ez-toc-grey ez-toc-container-direction\">\n<div class=\"ez-toc-title-container\">\n<p class=\"ez-toc-title\" style=\"cursor:inherit\">Sadr\u017eaj<\/p>\n<span class=\"ez-toc-title-toggle\"><a href=\"#\" class=\"ez-toc-pull-right ez-toc-btn ez-toc-btn-xs ez-toc-btn-default ez-toc-toggle\" aria-label=\"Toggle Table of Content\"><span class=\"ez-toc-js-icon-con\"><span class=\"\"><span class=\"eztoc-hide\" style=\"display:none;\">Toggle<\/span><span class=\"ez-toc-icon-toggle-span\"><svg style=\"fill: #999;color:#999\" xmlns=\"http:\/\/www.w3.org\/2000\/svg\" class=\"list-377408\" width=\"20px\" height=\"20px\" viewBox=\"0 0 24 24\" fill=\"none\"><path d=\"M6 6H4v2h2V6zm14 0H8v2h12V6zM4 11h2v2H4v-2zm16 0H8v2h12v-2zM4 16h2v2H4v-2zm16 0H8v2h12v-2z\" fill=\"currentColor\"><\/path><\/svg><svg style=\"fill: #999;color:#999\" class=\"arrow-unsorted-368013\" xmlns=\"http:\/\/www.w3.org\/2000\/svg\" width=\"10px\" height=\"10px\" viewBox=\"0 0 24 24\" version=\"1.2\" baseProfile=\"tiny\"><path d=\"M18.2 9.3l-6.2-6.3-6.2 6.3c-.2.2-.3.4-.3.7s.1.5.3.7c.2.2.4.3.7.3h11c.3 0 .5-.1.7-.3.2-.2.3-.5.3-.7s-.1-.5-.3-.7zM5.8 14.7l6.2 6.3 6.2-6.3c.2-.2.3-.5.3-.7s-.1-.5-.3-.7c-.2-.2-.4-.3-.7-.3h-11c-.3 0-.5.1-.7.3-.2.2-.3.5-.3.7s.1.5.3.7z\"\/><\/svg><\/span><\/span><\/span><\/a><\/span><\/div>\n<nav><ul class='ez-toc-list ez-toc-list-level-1 ' ><li class='ez-toc-page-1 ez-toc-heading-level-2'><a class=\"ez-toc-link ez-toc-heading-1\" href=\"https:\/\/thingsolver.com\/sr\/blog\/razgovori-petkom-crni-konj-algoritma-isolation-forest\/#Forest_kazes\" title=\"Forest, ka\u017ee\u0161?\">Forest, ka\u017ee\u0161?<\/a><\/li><li class='ez-toc-page-1 ez-toc-heading-level-2'><a class=\"ez-toc-link ez-toc-heading-2\" href=\"https:\/\/thingsolver.com\/sr\/blog\/razgovori-petkom-crni-konj-algoritma-isolation-forest\/#Skriveni_heroj%E2%80%A6\" title=\"Skriveni heroj\u2026\">Skriveni heroj\u2026<\/a><\/li><li class='ez-toc-page-1 ez-toc-heading-level-2'><a class=\"ez-toc-link ez-toc-heading-3\" href=\"https:\/\/thingsolver.com\/sr\/blog\/razgovori-petkom-crni-konj-algoritma-isolation-forest\/#Uvodjenje_malo_postenja_u_ovaj_post%E2%80%A6\" title=\"Uvo\u0111enje malo po\u0161tenja u ovaj post\u2026\">Uvo\u0111enje malo po\u0161tenja u ovaj post\u2026<\/a><\/li><\/ul><\/nav><\/div>\n<h2><span class=\"ez-toc-section\" id=\"Forest_kazes\"><\/span>Forest, ka\u017ee\u0161?<span class=\"ez-toc-section-end\"><\/span><\/h2>\n<p>Kao \u0161to mo\u017eete pretpostaviti, Isolation Forest je metoda zasnovana na sastavljanju. A ako ste upoznati sa na\u010dinom na koji radi Random Forest (znam da jeste, svi ga volimo!), nema sumnje da c\u0301ete brzo savladati algoritam Forest algorithm. Pa, kako to funkcioni\u0161e?<\/p>\n<p>Jedna stvar koju treba razjasniti pre obja\u0161njenja algoritma je koncept \u201eizolacije instance\u201c. Dok vec\u0301ina drugih algoritama poku\u0161ava da modelira normalno pona\u0161anje, da bi nau\u010dio obrasce profila, ovaj algoritam poku\u0161ava da odvoji anomalnu instancu od ostatka podataka (odatle pojam \u201eizolacija\u201c). \u0160to je lak\u0161e izolovati instancu, vec\u0301e su \u0161anse da je anomalna. Kao \u0161to autori <a href=\"https:\/\/cs.nju.edu.cn\/zhouzh\/zhouzh.files\/publication\/icdm08b.pdf\" target=\"_blank\" rel=\"noopener\">\u00a0ovog rada<\/a> sugeri\u0161u, vec\u0301ina postojec\u0301ih pristupa detektovanju anomalija zasnovanih na modelu konstrui\u0161e profil normalnih instanci, a zatim identifikuje instance koje nisu u skladu sa normalnim profilom kao anomalije. \u0160ta je problem u vezi sa tim? Pa, definisanje normalnog pona\u0161anja. Granice normalnog pona\u0161anja. U vec\u0301ini slu\u010dajeva, ozna\u010davanje podataka i dobijanje informacija o normalnom i anomalnom pona\u0161anju je preskupo i dugotrajno. I tada kreativnost iskora\u010di i ispoljava se na sceni. Kreirati jednostavno ali re\u0161enje koje se grani\u010di sa genijalno\u0161\u0107u (u redu, ovde sam malo pristrasan :D).<\/p>\n<p>Dakle, u osnovi, Isolation Forest (iForest) funkcioni\u0161e tako \u0161to gradi ansambl &#8222;drvec\u0301a&#8220;, nazvanog Izolaciona stabla (iTrees), za dati skup podataka. Odre\u0111eno iTree je izgra\u0111eno na funkciji, izvo\u0111enjem particionisanja. Ako imamo funkciju sa datim opsegom podataka, prvi korak algoritma je da nasumi\u010dno izabere podeljenu vrednost iz dostupnog opsega vrednosti. Kada se odabere podeljena vrednost, po\u010dinje particioniranje \u2013 svaka instanca sa vredno\u0161c\u0301u obele\u017eja ni\u017eom od vrednosti podele se rutira na jednu stranu stabla, dok se svaka instanca sa vredno\u0161c\u0301u obele\u017eja vec\u0301om ili jednakom od vrednosti podele rutira u suprotnoj strani drveta. U drugom koraku, bira se druga nasumi\u010dna podeljena vrednost, van dostupnog opsega vrednosti za svaku stranu stabla. Ovo se radi rekurzivno sve dok se sve instance ne stave u terminalne \u010dvorove (li\u0161c\u0301e) ili dok se ne ispune neki od kriterijuma postavljenih u ulaznim parametrima. Pojednostavljeni proces izgradnje stabla je prikazan ispod.<\/p>\n<p><img decoding=\"async\" class=\" wp-image-11662 aligncenter\" src=\"https:\/\/thingsolver.com\/wp-content\/uploads\/isolation-forest-1.png\" alt=\"Isolation Forest\" width=\"529\" height=\"296\" title=\"\" srcset=\"https:\/\/thingsolver.com\/wp-content\/uploads\/isolation-forest-1.png 1150w, https:\/\/thingsolver.com\/wp-content\/uploads\/isolation-forest-1-768x430.png 768w\" sizes=\"(max-width: 529px) 100vw, 529px\" \/><\/p>\n<p>&nbsp;<\/p>\n<p>Ideja je jednostavna \u2013 ako se instanca lako izoluje (\u0161to zna\u010di da je preduzeto manje koraka da bi se smestila u terminalni \u010dvor), ima vec\u0301e \u0161anse da bude anomalija. Sa slike koja sledi, mo\u017ee se primetiti da je Xi instanca iz gustog podru\u010dja zahtevala mnogo koraka da bi bila izolovana, dok je usamljena Xo instanca zahtevala mnogo manje.<\/p>\n<p><img decoding=\"async\" class=\" wp-image-11661 aligncenter\" src=\"https:\/\/thingsolver.com\/wp-content\/uploads\/isolation-forest-2.png\" alt=\"Isolation Forest\" width=\"568\" height=\"318\" title=\"\" srcset=\"https:\/\/thingsolver.com\/wp-content\/uploads\/isolation-forest-2.png 1150w, https:\/\/thingsolver.com\/wp-content\/uploads\/isolation-forest-2-768x430.png 768w\" sizes=\"(max-width: 568px) 100vw, 568px\" \/><\/p>\n<p>Dakle, u algoritmu iForest, rezultat anomalije je odre\u0111en du\u017einom putanje od korenskog \u010dvora do lista u kojem je instanca sme\u0161tena. Po\u0161to je to ansambl, uzima se prosek svih du\u017eina putanja za datu instancu. Mo\u017ee se indukovati da su prose\u010dna du\u017eina putanje i rezultat anomalije obrnuto proporcionalni \u2013 \u0161to je put krac\u0301i, to je vec\u0301i skor anomalije.\u00a0 U slu\u010daju da sam bio potpuno konfuzan, ostavic\u0301u samo zvani\u010dnu dokumentaciju <a href=\"https:\/\/cs.nju.edu.cn\/zhouzh\/zhouzh.files\/publication\/icdm08b.pdf\" target=\"_blank\" rel=\"noopener\">ovde<\/a>.<\/p>\n<p>Postoje dva glavna parametra \u2013 broj stabala i veli\u010dina poduzorkovanja. Veli\u010dina poduzorkovanja kontroli\u0161e veli\u010dinu uzorka koji c\u0301e se koristiti iz obuke modela, kada se izvr\u0161i particioniranje. U zvani\u010dnoj dokumentaciji, autori sugeri\u0161u da su empirijski utvrdili da su optimalne vrednosti za ove parametre 100 i 256, za broj stabala, odnosno veli\u010dinu poduzorka.<\/p>\n<h2><span class=\"ez-toc-section\" id=\"Skriveni_heroj%E2%80%A6\"><\/span><strong>Skriveni heroj\u2026<\/strong><span class=\"ez-toc-section-end\"><\/span><\/h2>\n<p>Sada, postoje dva glavna problema na koja se mo\u017ee nai\u0107i kada se radi o otkrivanju anomalija: zatamnjenje i maskiranje. Swamping je situacija pogre\u0161nog identifikovanja normalnih instanci kao anomalnih, \u0161to se mo\u017ee desiti kada su normalne i anomalne instance blizu jedna drugoj. Maskiranje je situacija pogre\u0161nog identifikovanja anomalnih instanci kao normalnih, \u0161to se \u010desto de\u0161ava kada se zajedno nalaze u gustom podru\u010dju, tako da \u201eprikrivaju\u201c svoje prisustvo. Poduzorkovanje u algoritmu iForest-u omoguc\u0301ava mu da napravi delimi\u010dan model koji je otporan na ova dva efekta. Sledec\u0301a slika pokazuje kako poduzorkovanje mo\u017ee lako da re\u0161i oba problema. Mo\u017ee se primetiti da je poduzorkovanje o\u010distilo normalne instance oko klastera anomalija i smanjilo veli\u010dinu anomalnih klastera, \u0161to bi moglo dovesti do zahteva vi\u0161e koraka za izolaciju.<\/p>\n<p><img decoding=\"async\" class=\" wp-image-11660 aligncenter\" src=\"https:\/\/thingsolver.com\/wp-content\/uploads\/isolation-forest-3.png\" alt=\"Isolation Forest\" width=\"640\" height=\"334\" title=\"\" srcset=\"https:\/\/thingsolver.com\/wp-content\/uploads\/isolation-forest-3.png 1446w, https:\/\/thingsolver.com\/wp-content\/uploads\/isolation-forest-3-768x402.png 768w\" sizes=\"(max-width: 640px) 100vw, 640px\" \/><\/p>\n<p><a href=\"https:\/\/scikit-learn.org\/stable\/modules\/generated\/sklearn.ensemble.IsolationForest.html\" target=\"_blank\" rel=\"noopener\">Scikit-learn implementacija<\/a> ima neke dodatne parametre poput maksimalnog broja funkcija za razmatranje i kontaminaciju \u2013 procenat anomalija koje treba identifikovati, \u0161to je veoma lepo. U osnovi funkcioni\u0161e na takav na\u010din da se odre\u0111eni procenat slu\u010dajeva sa najvec\u0301im rezultatom anomalije ozna\u010di kao anomalan. Ima funkciju_odlu\u010divanja () koja izra\u010dunava prose\u010dnu ocenu anomalije i funkcije za prilago\u0111avanje i predvi\u0111anje. I jo\u0161 nismo stigli do najvec\u0301e prednosti algoritma! Mo\u017ee da radi i u nadziranom i u nenadziranom re\u017eimu, \u0161to ga \u010dini zaista skrivenim herojem oblasti ma\u0161inskog u\u010denja. Dakle, mo\u017eete ga hraniti ili sa ulaznim podacima i oznakama, ili samo sa ulaznim podacima, on c\u0301e ga &#8222;zgnje\u010diti&#8220; i vratiti izlaznu vrednost.<\/p>\n<h2><span class=\"ez-toc-section\" id=\"Uvodjenje_malo_postenja_u_ovaj_post%E2%80%A6\"><\/span><strong>Uvo\u0111enje malo po\u0161tenja u ovaj post\u2026<\/strong><span class=\"ez-toc-section-end\"><\/span><\/h2>\n<p>Da bismo smanjili pristrasnost, hajde da pri\u010damo o nedostacima, jer su prisutni. Prvo i najva\u017enije \u2013 ne mo\u017ee da radi sa multivarijantnim vremenskim serijama, \u0161to je jedan od najvec\u0301ih problema sa kojima se suo\u010davamo u praksi. \u0160to se ti\u010de scikit-learn implementacije, jedna stvar koja me stvarno mu\u010di je to \u0161to nije moguc\u0301e dobiti posebnu odluku za svako iTree. Osim toga, tako\u0111e je nemoguc\u0301e vizuelizovati drvec\u0301e, a, budimo iskreni \u2013 ljudi vole da vide sliku. Ni\u0161ta im se ne dopada vi\u0161e od savr\u0161eno prikazanog algoritma koji mogu sami da protuma\u010de. Moglo bi biti zaista korisno videti koja karakteristika je izazvala anomaliju i kojeg intenziteta. Druga stvar koja me ovde brine je \u2013 kako c\u0301e se pona\u0161ati sa karakteristikama koje su blago devijantne? Bojim se da to mo\u017ee dovesti do sli\u010dnih du\u017eina putanje i do problema sa maskiranjem (ispravite me ako gre\u0161im). Kona\u010dno, nisam ga stvarno testirao sa kategori\u010dkim podacima, ali ako neko ima iskustva sa tim, molim vas da mi ka\u017eete.<\/p>\n<p>\u0160to se ti\u010de njegove prirode, Isolation Forest pokazuje zavidne performanse kada radi sa visokodimenzionalnim ili suvi\u0161nim podacima. Prili\u010dno je moc\u0301an kada je postavljen na odgovarajuc\u0301i na\u010din i za probleme koji ne zahtevaju otkrivanje kontekstualnih anomalija (kao \u0161to su vremenske serije ili prostorna analiza). A po\u0161to je superbrz, stvarno volim da ga koristim. Isprobao sam ga na maloprodaji i na telekomunikacionim podacima, i rezultati su bili prili\u010dno zadovoljavajuc\u0301i.<\/p>\n<p>Otkrivanje anomalija je i dalje jedan od najvec\u0301ih problema sa kojima se analiti\u010dari susrec\u0301u kada rade sa podacima. Nema sumnje da c\u0301e biti vi\u0161e algoritama za otkrivanje anomalija u podacima, sa mnogo pobolj\u0161anja i moguc\u0301nosti. Ali najva\u017enije je da se ne zanemari zna\u010daj i uticaj anomalija na rezultate i dono\u0161enje odluka, jer one predstavljaju veoma osetljiv problem i njima treba pa\u017eljivo pristupiti i analizirati ih. Imajte to na umu. Hvala vam! [nz_icons icon=\u201dicon-wink\u201d animate=\u201dfalse\u201d size=\u201dsmall\u201d type=\u201dcircle\u201d icon_color=\u201d\u201d background_color=\u201d\u201d border_color=\u201d\u201d \/]<\/p>\n","protected":false},"excerpt":{"rendered":"<p>Kada se bavimo anomalijama u podacima, postoji mnogo izazova koje treba re\u0161iti. Vec\u0301 smo imali nekoliko \u010dlanaka na ovu temu, a ako ih vec\u0301 niste pro\u010ditali, predla\u017eem vam da pogledate ovaj, i ovaj, od mog kolege Milo\u0161a. U ovom postu &#8230; <\/p>\n<p class=\"read-more\"><a class=\"btn small\" href=\"https:\/\/thingsolver.com\/sr\/blog\/razgovori-petkom-crni-konj-algoritma-isolation-forest\/\">Pro\u010ditaj vi\u0161e<\/a><\/p>\n","protected":false},"author":3,"featured_media":16955,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"_acf_changed":false,"footnotes":""},"categories":[189],"tags":[246,251,252,253],"acf":[],"_links":{"self":[{"href":"https:\/\/thingsolver.com\/sr\/wp-json\/wp\/v2\/posts\/16954"}],"collection":[{"href":"https:\/\/thingsolver.com\/sr\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/thingsolver.com\/sr\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/thingsolver.com\/sr\/wp-json\/wp\/v2\/users\/3"}],"replies":[{"embeddable":true,"href":"https:\/\/thingsolver.com\/sr\/wp-json\/wp\/v2\/comments?post=16954"}],"version-history":[{"count":3,"href":"https:\/\/thingsolver.com\/sr\/wp-json\/wp\/v2\/posts\/16954\/revisions"}],"predecessor-version":[{"id":16958,"href":"https:\/\/thingsolver.com\/sr\/wp-json\/wp\/v2\/posts\/16954\/revisions\/16958"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/thingsolver.com\/sr\/wp-json\/wp\/v2\/media\/16955"}],"wp:attachment":[{"href":"https:\/\/thingsolver.com\/sr\/wp-json\/wp\/v2\/media?parent=16954"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/thingsolver.com\/sr\/wp-json\/wp\/v2\/categories?post=16954"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/thingsolver.com\/sr\/wp-json\/wp\/v2\/tags?post=16954"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}