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

1. 前言

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

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

isolation指將某個(gè)樣本點(diǎn)與其他樣本點(diǎn)區(qū)分開(kāi)。

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

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

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

其中，h(x)為樣本點(diǎn)x的路徑長(zhǎng)度，E(h(x))為iForest的多棵樹(shù)中樣本點(diǎn)x的路徑長(zhǎng)度的期望。特別地，

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

2. 詳解

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

停止分裂條件：

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

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

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

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