iForest （Isolation Forest）是由Liu et al. [1] 提出來的基于二叉樹的ensemble異常檢測算法，具有效果好、訓(xùn)練快（線性復(fù)雜度）等特點。

1. 前言

iForest為聚類算法，不需要標(biāo)記數(shù)據(jù)訓(xùn)練。首先給出幾個定義：

劃分（partition）指樣本空間一分為二，相當(dāng)于決策樹中節(jié)點分裂；

isolation指將某個樣本點與其他樣本點區(qū)分開。

iForest的基本思想非常簡單：完成異常點的isolation所需的劃分?jǐn)?shù)大于正常樣本點（非異常）。如下圖所示：

xi 樣本點的isolation需要大概12次劃分，而異常點x0指需要4次左右。因此，我們可以根據(jù)劃分次數(shù)來區(qū)分是否為異常點。但是，如何建模呢？我們?nèi)菀紫氲剑簞澐謱?yīng)于決策樹中節(jié)點分裂，那么劃分次數(shù)即為從決策樹的根節(jié)點到葉子節(jié)點所經(jīng)歷的邊數(shù)，稱之為路徑長度（path length）。假設(shè)樣本集合共有n個樣本點，對于二叉查找樹（Binary Search Tree, BST），則查找失敗的平均路徑長度為

其中，H(i)為harmonic number，可估計為ln(i)+0.5772156649。那么，可建模anomaly score：

其中，h(x)為樣本點x的路徑長度，E(h(x))為iForest的多棵樹中樣本點x的路徑長度的期望。特別地，

當(dāng)s值越高（接近于1），則表明該點越可能為異常點。若所有的樣本點的s值都在0.5左右，則說明該樣本集合沒有異常點。

2. 詳解

iForest采用二叉決策樹來劃分樣本空間，每一次劃分都是隨機(jī)選取一個屬性值來做，具體流程如下：

停止分裂條件：

樹達(dá)到了最大高度；

落在孩子節(jié)點的樣本數(shù)只有一個，或者所有樣本點的值均相同；

為了避免錯檢（swamping）與漏檢（masking），在訓(xùn)練每棵樹的時候，為了更好地區(qū)分，不會拿全量樣本，而會sub-sampling樣本集合。iForest的訓(xùn)練流程如下：

sklearn給出了iForest與其他異常檢測算法的比較。