機器學習_學習筆記系列(95)：孤立森林(Isolation Forest)
上一回我們介紹如何用One Class Support Vector Machine來做anomaly detection，而對於異常值檢測的演算法，我們依樣也可以用Decision Tree的架構來做，而這也是我們今天要來介紹的演算法「isolation forest」。
Isolation Forest
關於isolation forest其是由Fei Tony Liu、Kai Ming Ting和Zhi-Hua Zhou所提出，論文稱叫做
Isolation-based Anomaly Detection
對於isolation forest他的架構很有演算法的流程，跟我們之前所介紹的radom forest很像，會由多個tree的結構來構成。
而在資料當中，我們可以看到異常的點通常具備一個特點，就是他們很多特徵跟其他大部分的數據差非常多。所以說isolation forest做的事情就是把這些差距非常大的點分離出來。
而isolation的演算法如下
我們會透過執行迴圈，然後每次從資料集X取樣一些資料X’，帶入isolation tree演算法，並把我們的結果連集到isolation forest裡面。
而對於isolation tree的作法就是我們從取樣的資料集X’隨機挑一個feature，並從挑到的feature其所對應X’的最小值和最大值間，隨機挑一個值p，如果X’所對應這個被挑到的feature數值小於p就會被分到左邊，如果大於等於就會被分到右邊。
然後接下來的步驟就和decision tree做的事一樣，build up左右兩邊的subtree，然後繼續隨機挑一個feature並隨機設定一個值，再分成左右兩邊subtree，直到不能再分，也就是只剩下一筆資料為止。
而今天我們用這樣的方式分的話，我們可以發現，通常異常點在深度還很淺的時候，就會被分開了。所以我們可以透過執行以下演算法，找到tree某個leaf到root的距離
而最後我們得到多的isolation tree後，我們會給定深度限制，在這個限制深度以上的leaf就是我們isolation tree的異常值。所以最後我們再用ensemble learning的方式把多個isolation tree的結果合併起來，就是我們isolation預測異常值的結果。
接下來我們來看Isolation Forest的表現
我們可以看到，isolation forest可以將離群點標示出來達到我們anomaly detection的效果。
Python Sample Code:
Github:
Reference:
[1] Liu, F. T., Ting, K. M., & Zhou, Z. H. (2012). Isolation-based anomaly detection. ACM Transactions on Knowledge Discovery from Data (TKDD), 6(1), 1–39.
