Isolation forest

Isolation Forest (en espanyol Bosc d'aïllament) és un algoritme per a la detecció d'anomalies en les senyes desenrollat inicialment per Fei Tony Liu en 2008. Isolation Forest detecta anomalies utilisant arbres binarios. L'algoritme té una complexitat temporal llineal i requerix poca memòria, per lo que funciona be en grans volums de senyes. En essència, l'algoritme es basa en les característiques de les anomalies, és dir, que siguen poques i diferents, per a detectar-les. En l'algoritme no es realisa cap estimació de la densitat. L'algoritme es diferencia dels algoritmes d'arbre de decisió en que només s'utilisa la mida o aproximació de la llongitut del camí per a generar la puntuació de l'anomalia, no es necessiten estadístiques dels nodos full sobre la distribució de classes o el valor objectiu.

El bosc d'aïllament és ràpit perque dividix l'espai de senyes de forma aleatòria, utilisant un atribut seleccionat a l'encert i un punt de divisió seleccionat a l'encert. La puntuació de l'anomalia està inversamente associada a la llongitut del camí, ya que les anomalies necessiten menys divisions per a ser aïllades, degut a que són poques i diferents.

Història

L'algoritme Isolation Forest (iForest) va ser propost inicialment per Fei Tony Liu, Kai Ming Ting i Zhi-Hua Zhou en 2008. En 2010, es va desenrollar una extensió de l'algoritme - SCiforest per a abordar anomalies agrupades i paraleles a eixos. En 2012 els mateixos autors varen demostrar que iForest té una complexitat temporal llineal, un chicotet requeriment de memòria i és aplicable a senyes d'alta dimensió.

Algoritme

Archiu:Isolating a Non-Anomalous Point.png

Fig. 2 - Eixemple 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 senyes anómales són més fàcils de separar del restant de la mostra. Per a aïllar un punt de senyes, l'algoritme genera recursivamente particions en la mostra seleccionant aleatoriamente un atribut i, a continuació, seleccionant aleatoriamente un valor de partició entre els valors mínim i màxim permesos per a eixe atribut.

En la figura 2 es mostra un eixemple de partició aleatòria en un conjunt de senyes 2D de punts distribuïts normalment per a un punt no anómal i en la figura 3 per a un punt que té més provabilitats de ser una anomalia. En les imàgens s'aprecia cóm les anomalies requerixen menys particions aleatòries per a ser aïllades, en comparació als punts normals.

La partició recursiva pot representar-se per mig d'una estructura d'arbre denominada Arbre d'aïllament, mentres que el número de particions necessàries per a aïllar un punt pot interpretar-se com la llongitut del camí, dins de l'arbre, per a aplegar a un nodo terminal partint de la raïl. Per eixemple, la llongitut de la trayectòria del punt $x_i$ en la figura 2 és major que la llongitut del recorregut de $x_j$ en la figura 3.

Archiu:Isolating an Anomalous Point.png

Fig. 3 - Eixemple d'aïllament d'un punt anómal en una distribució gaussiana 2D.

$X=\{x_1,\dots ,x_n\}$ serà un conjunt de punts d-dimensionals i $X^{\prime }\subset X$. Un arbre d'aïllament (iTree) es definix com una estructura de senyes en les següents propietats:

1. per a cada nodo $T$ en l'arbre, $T$ és un nodo extern sense cap fill, o un nodo intern en un «test» i exactament dos nodos fills ($T_l$ i $T_r$)
2. una prova en el nodo $T$ consistix en un atribut $q$ i un valor dividit $p$ de manera que la prova $q<p$ determina el recorregut d'un punt de senyes a $T_l$ o $T_r$.

Per a construir un iTree, l'algoritme dividix recursivamente $X^{\prime }$ seleccionant aleatoriamente un atribut $q$ i un valor dividit $p$, fins que:

1. el nodo només té una instància, o
2. totes les senyes del nodo tenen els mateixos valors.

Quan el iTree està completament desenrollat, cada punt de $X$ s'aïlla en un dels nodos externs. Intuitivamente, els punts anómals són aquells (més fàcils d'aïllar, per tant) en la menor llongitut de camí en l'arbre, a on la llongitut de camí $h(x_i)$ del punt $x_i\in X$ es definix com el número d'arestes $x_i$ que travessen des del nodo raïl per a aplegar a un nodo extern.

En el document original de iForest s'oferix una explicació provabilística de iTree.

Vore també

• Detecció d'anomalies