孤立森林（Isolation Forest）算法簡(jiǎn)介

簡(jiǎn)介：

孤立森林算法是一種適用于連續(xù)數(shù)據(jù)的無(wú)監(jiān)督異常檢測(cè)方法，由南京大學(xué)周志華教授等人于2008年首次提出，之后又于2012年提出了改進(jìn)版本。與其他異常檢測(cè)算法通過(guò)距離，密度等量化指標(biāo)來(lái)刻畫(huà)樣本間的疏離程度不同，孤立森林算法通過(guò)對(duì)樣本點(diǎn)的孤立來(lái)檢測(cè)異常值。具體來(lái)說(shuō)，該算法利用一種名為孤立樹(shù)iTree的二叉搜索樹(shù)結(jié)構(gòu)來(lái)孤立樣本。由于異常值的數(shù)量較少且與大部分樣本的疏離性，因此，異常值會(huì)被更早的孤立出來(lái)，也即異常值會(huì)距離iTree的根節(jié)點(diǎn)更近，而正常值則會(huì)距離根節(jié)點(diǎn)有更遠(yuǎn)的距離。此外，相較于LOF，K-means等傳統(tǒng)算法，孤立森林算法對(duì)高緯數(shù)據(jù)有較好的魯棒性。

定義：

我們先給出孤立樹(shù)(Isolation Tree)和樣本點(diǎn)x在孤立樹(shù)中的路徑長(zhǎng)度h(x)的定義

孤立樹(shù)：若T為孤立樹(shù)的一個(gè)節(jié)點(diǎn)，T存在兩種情況：沒(méi)有子節(jié)點(diǎn)的外部節(jié)點(diǎn)，有兩個(gè)子節(jié)點(diǎn)\left ( T_{l},T_{r} \right )和一個(gè)test的內(nèi)部節(jié)點(diǎn)。在T的test由一個(gè)屬性q和一個(gè)分割點(diǎn)p組成，q < p的點(diǎn)屬于T_{l},反之屬于T_{r}。

樣本點(diǎn)x在孤立樹(shù)中的路徑長(zhǎng)度h(x):樣本點(diǎn)x從iTree的根節(jié)點(diǎn)到葉子節(jié)點(diǎn)經(jīng)過(guò)的邊的數(shù)量

基本思想：

從下圖我們可以直觀的看到，相對(duì)更異常的x_{o}只需要4次切割就從整體中被分離出來(lái)，而更加正常的x_{i}點(diǎn)經(jīng)過(guò)了11次分割才從整體中分離出來(lái)。這也體現(xiàn)了孤立森林算法的基本思想。(ps:圖片來(lái)自原論文)

Isolation_Forest_show.jpeg

算法介紹：

下面，我們來(lái)詳細(xì)介紹孤立森林算法。該算法大致可以分為兩個(gè)階段，第一個(gè)階段我們需要訓(xùn)練出t顆孤立樹(shù)，組成孤立森林。隨后我們將每個(gè)樣本點(diǎn)帶入森林中的每棵孤立樹(shù)，計(jì)算平均高度，之后再計(jì)算每個(gè)樣本點(diǎn)的異常值分?jǐn)?shù)。

Step1:X = \left \{ x_{1},...,x_{n} \right \} 為給定數(shù)據(jù)集, \forall x_{i} \in X, x_{i} = \left ( x_{i1},...,x_{id} \right ),從X中隨機(jī)抽取\psi個(gè)樣本點(diǎn)構(gòu)成X的子集X^{'}放入根節(jié)點(diǎn)。
Step2:從d個(gè)維度中隨機(jī)指定一個(gè)維度q，在當(dāng)前數(shù)據(jù)中隨機(jī)產(chǎn)生一個(gè)切割點(diǎn)p，min\left ( x_{ij}, j = q, x_{ij} \in X^{'} \right ) < p < max\left ( x_{ij}, j = q, x_{ij} \in X^{'} \right )。
Step3:此切割點(diǎn)p生成了一個(gè)超平面，將當(dāng)前數(shù)據(jù)空間劃分為兩個(gè)子空間：指定維度小于p的樣本點(diǎn)放入左子節(jié)點(diǎn)，大于或等于p的放入右子節(jié)點(diǎn)。
Step4:遞歸Step2和Step3，直至所有的葉子節(jié)點(diǎn)都只有一個(gè)樣本點(diǎn)或者孤立樹(shù) (iTree)已經(jīng)達(dá)到指定的高度。
Step5:循環(huán)Step1至Step4，直至生成t個(gè)孤立樹(shù)(iTree)

第二階段：
Step1: 對(duì)于每一個(gè)數(shù)據(jù)點(diǎn)x_{i},令其遍歷每一顆孤立樹(shù)(iTree),計(jì)算點(diǎn)x_{i}在森林中的平均高度h\left ( x_{i} \right ),對(duì)所有點(diǎn)的平均高度做歸一化處理。異常值分?jǐn)?shù)的計(jì)算公式如下所示：
s\left ( x,\psi \right ) = 2^{\frac{E\left ( h\left ( x \right ) \right )}{c\left ( \psi \right )}}
其中，c\left ( \psi \right ) = \left\{\begin{matrix} 2H\left ( \psi - 1 \right ) - 2 \left ( \psi - 1 \right )/\psi, \psi > 2\\ 1, \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \psi = 2\\ 0, \quad \quad \quad \quad \quad \quad \quad \quad otherwise \end{matrix}\right.

示例：

from sklearn.ensemble import IsolationForest  
from scipy import stats  
rng = np.random.RandomState(42)
X_train = data[:10000,:]
X_test = data
clf = IsolationForest(max_samples=256,random_state=rng)
clf.fit(X_train)
y_pred_test = clf.predict(X_test)

參考：https://dl.acm.org/citation.cfm?doid=2133360.2133363

最后編輯于 ：
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請(qǐng)聯(lián)系作者
【社區(qū)內(nèi)容提示】社區(qū)部分內(nèi)容疑似由AI輔助生成，瀏覽時(shí)請(qǐng)結(jié)合常識(shí)與多方信息審慎甄別。
平臺(tái)聲明：文章內(nèi)容（如有圖片或視頻亦包括在內(nèi)）由作者上傳并發(fā)布，文章內(nèi)容僅代表作者本人觀點(diǎn)，簡(jiǎn)書(shū)系信息發(fā)布平臺(tái)，僅提供信息存儲(chǔ)服務(wù)。

友情鏈接更多精彩內(nèi)容