Isolation Forest és un algoritme per a la detecció d'anomalies de dades mitjançant arbres binaris. Va ser desenvolupat per Fei Tony Liu el 2008. Té una complexitat de temps lineal i un baix ús de memòria, cosa que funciona bé per a dades de gran volum. Es basa en la suposició que, com que les anomalies són poques i diferents d'altres dades, es poden aïllar mitjançant poques particions. Com els algoritmes d'arbre de decisió, no realitza una estimació de densitat. A diferència dels algoritmes d'arbre de decisió, només utilitza la longitud del camí per generar una puntuació d'anomalia i no utilitza estadístiques de node fulla de distribució de classes o valor objectiu.
Isolation Forest és ràpid perquè divideix l'espai de dades, seleccionant aleatòriament un atribut i un punt de divisió. La puntuació de l'anomalia està inversament relacionada amb la longitud de la ruta perquè les anomalies necessiten menys divisions per ser aïllades, ja que són poques i diferents.
Història L'algoritme Isolation Forest (iForest) va ser proposat inicialment per Fei Tony Liu, Kai Ming Ting i Zhi-Hua Zhou el 2008. El 2012, els mateixos autors van demostrar que iForest té complexitat de temps lineal, un petit requisit de memòria i és aplicable a dades d'alta dimensionalitat. El 2010, es va publicar una extensió de l'algoritme, SCiforest, per abordar anomalies agrupades i paral·leles a eixos.
Arbres d'aïllament miniatura|300x300px|Un exemple d'aïllament d'un punt no anòmal en una distribució gaussiana 2D. La premissa de l'algoritme Isolation Forest és que els punts de dades anòmals són més fàcils de separar de la resta de la mostra. Per tal d'aïllar un punt de dades, l'algoritme genera recursivament particions a la mostra seleccionant aleatòriament un atribut i després seleccionant aleatòriament un valor dividit entre els valors mínim i màxim permesos per a aquest atribut. alt=Isolating an Anomalous Point|miniatura|300x300px|Un exemple d'aïllament d'un punt anòmal en una distribució gaussiana 2D. Un exemple de partició aleatòria en un conjunt de dades 2D de punts amb distribució normal es mostra a la primera figura per a un punt no anòmal i a la segona per a un punt que és més probable que sigui una anomalia. A partir de les imatges, es pot veure com les anomalies requereixen menys particions aleatòries per aïllar-les, en comparació amb els punts normals.
El particionament recursiu es pot representar mitjançant una estructura d'arbre anomenada Arbre d'aïllament, mentre que el nombre de particions necessàries per aïllar un punt es pot interpretar com la longitud del camí, dins de l'arbre, per arribar a un node final començant des de l'arrel. Per exemple, la longitud del camí del punt a la primera figura és més gran que la longitud del camí de a la segona figura.
Sigui un conjunt de punts d-dimensionals i Un arbre d'aïllament (iTree) es defineix com una estructura de dades amb les propietats següents:
per a cada node a l'arbre, és o bé un node extern sense fill, o bé un node intern amb una "prova" i exactament dos nodes fills ( i ) una prova al node consisteix en un atribut i un valor dividit de manera que la prova determina el recorregut d'un punt de dades a qualsevol dels dos o .
Per construir un iTree, l'algoritme divideix recursivament seleccionant aleatòriament un atribut i un valor dividit , fins que qualsevol dels dos
el node només té una instància, o totes les dades del node tenen els mateixos valors.
Quan l'iTree està completament crescut, cada punt de està aïllat en un dels nodes externs. Intuïtivament, els punts anòmals són aquells (més fàcils d'aïllar, per tant) amb la longitud de camí més petita a l'arbre, on la longitud del camí de punt es defineix com el nombre d'arestes travessa des del node arrel per arribar a un node extern.
Una explicació probabilística d'iTree es proporciona a l'article original d'iForest.
Detecció d'anomalies La detecció d'anomalies amb Isolation Forest es fa de la següent manera:
Utilitzeu el conjunt de dades d'entrenament per construir un cert nombre d'iTrees Per a cada punt de dades del conjunt de proves: Passar-ho per tots els iTrees, comptant la longitud del camí per a cada arbre Assignar una "puntuació d'anomalia" a la instància Etiquetar el punt com a "anomalia" si la seva puntuació és superior a un llindar predefinit, que depèn del domini
Aplicació del bosc d'aïllament per a la detecció de fraus amb targetes de crèdit (anomalia) L'algoritme Isolation Forest ha demostrat la seva eficàcia en la detecció d'anomalies en conjunts de dades, com ara descobrir casos de frau amb targetes de crèdit entre transaccions, per part de titulars de targetes europees amb un conjunt de dades desequilibrat, on pot distingir les activitats fraudulentes de les legítimes identificant patrons poc freqüents que mostren diferències notables.
Propietats Submostreig: Com que iForest no necessita aïllar instàncies normals, sovint pot ignorar la major part del conjunt d'entrenament. Per tant, funciona molt bé quan la mida de mostreig es manté petita, a diferència de la majoria dels altres mètodes, que es beneficien d'una mida de mostra gran. Inundació: Quan les instàncies normals són massa a prop de les anomalies, el nombre de particions necessàries per separar les anomalies augmenta, un fenomen conegut com a inundació, que fa que sigui més difícil per a iForest discriminar entre anomalies i punts normals. Una de les principals raons per a l'inundació és la presència de massa dades; per tant, una possible solució és el submostreig. Com que iForest funciona bé amb submostreig, reduir el nombre de punts de la mostra també és una bona manera de reduir l'efecte de l'inundació. En entorns de temps real, s'ha demostrat que la combinació de petites finestres de dades seqüencials i submostreig millora el rendiment de detecció d'anomalies sense comprometre la precisió. Emmascarament: Quan hi ha moltes anomalies, algunes d'elles es poden agregar en un clúster dens i gran, cosa que fa que sigui més difícil separar les anomalies individuals i, per tant, identificar-les. Aquest fenomen s'anomena " emmascarament " i, com passa amb l'inundació, és més probable quan la mostra és gran i es pot pal·liar mitjançant un submostreig. Dades d'alta dimensionalitat: Una limitació principal dels mètodes estàndard basats en la distància és la seva ineficiència a l'hora de tractar dades d'alta dimensionalitat. La raó principal és que en un espai d'alta dimensionalitat, tots els punts són igualment dispersos, de manera que utilitzar una mesura de separació basada en la distància no és eficaç. Malauradament, les dades d'alta dimensionalitat també afecten el rendiment de detecció d'iForest, però el rendiment es pot millorar enormement mitjançant la selecció de característiques, com la curtosis, per reduir la dimensionalitat de la mostra. Només instàncies normals: Forest funciona bé fins i tot si el conjunt d'entrenament no conté punts anòmals. La raó és que iForest descriu distribucions de dades de manera que els camins d'arbre llargs corresponen a punts de dades normals. Per tant, la presència d'anomalies és irrellevant per al rendiment de la detecció.
Selecció de paràmetres miniatura|360x360px|El gràfic de barres mostra la sensibilitat del rendiment dels paràmetres clau d'Aïllament Bosc en diferents rangs de valors, basats en el conjunt de dades de Detecció de Fraud amb Targeta de Crèdit de Dal Pozzolo et al. (2014), que destaca la complexitat de l'ajust. El rendiment de l'algoritme Isolation Forest depèn en gran manera de la selecció dels seus paràmetres. Ajustar correctament aquests paràmetres pot millorar significativament la capacitat de l'algoritme per identificar anomalies amb precisió. Comprendre el paper i l'impacte de cada paràmetre és crucial per optimitzar el rendiment del model.
L'algoritme Isolation Forest implica diversos paràmetres clau que influeixen en el seu comportament i eficàcia. Aquests paràmetres controlen diversos aspectes del procés de construcció de l'arbre, la mida de les submostres i els llindars per identificar anomalies. Seleccionar els paràmetres adequats és la clau del rendiment de l'algoritme Isolation Forest. Cadascun dels paràmetres influeix en la detecció d'anomalies de manera diferent. Els paràmetres clau inclouen:
Nombre d'arbres: Aquest paràmetre determina el nombre d'arbres del Bosc d'Aïllament. Un nombre més elevat d'arbres millora la precisió de la detecció d'anomalies però augmenta els costos computacionals. El nombre òptim equilibra la disponibilitat de recursos amb les necessitats de rendiment. Per exemple, un conjunt de dades més petit pot requerir menys arbres per estalviar en càlcul, mentre que els conjunts de dades més grans es beneficien d'arbres addicionals per capturar més complexitat.
Mida de la submostra: La mida de la submostra dicta el nombre de punts de dades utilitzats per construir cada arbre. Les mides de submostra més petites redueixen la complexitat computacional però poden capturar menys variabilitat en les dades. Per exemple, s'utilitza habitualment una mida de submostra de 256, però el valor òptim depèn de les característiques del conjunt de dades.
Factor de contaminació: Aquest paràmetre estima la proporció de valors atípics en el conjunt de dades. Els valors de contaminació més alts marquen més punts de dades com a anomalies, cosa que pot conduir a falsos positius. Ajustar aquest paràmetre acuradament en funció del coneixement del domini o la validació creuada és fonamental per evitar biaixos o classificacions errònies.
Característiques màximes: aquest paràmetre especifica el nombre de característiques aleatòries a tenir en compte per a cada divisió de l'arbre. Limitar el nombre de característiques augmenta l'aleatorietat, fent que el model sigui més robust. Tanmateix, en conjunts de dades d'alta dimensionalitat, seleccionar només les característiques més informatives evita el sobreajustament i millora la generalització.
Profunditat de l'arbre: La profunditat de l'arbre determina el nombre màxim de divisions per a un arbre. Els arbres més profunds capturen millor la complexitat de les dades, però corren el risc de sobreajustament, especialment en conjunts de dades petits. Els arbres poc profunds, en canvi, milloren l'eficiència computacional.
Referències
Categoria:Aprenentatge automàtic