# Isolation forest
> 過去參與的研究與專案很常使用到此方法，但都一知半解，import以後就直接開始用...，面試直接被問爆，為了記起來，因此建立此筆記進行紀錄

### Isolation forest 介紹
如同字面上意義，"Isolation" 孤立，主要就是要找出資料中的孤立樣本，孤立樣本通常會距離高密度的群體中較遠，且分布稀疏，以統計學角度來看，正常資料通常落在這些分布稀疏的點所落在的區域機率很低，因此這些零散的點可以被視為異常點。

我們可以發現到，上述所探討的異常點是基於資料的分布來決定是否為異常，因此也可以得知出此方法是屬於非監督式學習，不需要標籤。因此對於一些異常資料很難蒐集到的應用場景e.g.信用卡詐欺檢測...等等非常有用，我們只需要準備資料即可。

### Isolation forest 算法原理
#### 初步介紹
為了方便後續簡介不用打這麼多字Isolation Forest會簡稱為iForest，當中的樹則稱為iTree。

iForest主要由大量二元樹所構成，主要構建過程是完全隨機

在介紹中有提到，正常樣本分布會聚集在一起，異常樣本分布零散而且跟正常樣本分布較遠，所以我們可以使用此特性進行切分，如果是異常樣本因為是稀疏的所以切分前期就會被分離出來，而正常的樣本需要切分很多次。

更完善的解釋：假設我們今天有N筆資料，會隨機從中拿出n筆，作為建立iTree的樣本，並於這些樣本中隨便挑選出一個特徵，並在特徵值的範圍(最大＆最小值)隨機選取一個值，我們每次會使用一個==隨機超平面==對數據空間進行切分，切一次會生成兩個子空間，以此循環，直到每個子空間裡面只有包含一個數據點或是達到樹的限定高度。

但一個iTree是不可信的，我們需要透過ensemble的方法，反覆從頭開始切，然後平均每次切的結果這樣才能得到收斂值(蒙地卡羅方法)

#### 演算法詳細介紹

##### iTree建立過程
iTree是一二元樹，也就是每個節點要不有兩個子節點，要不然就是葉節點。
依照原始論所敘述之演算法如下
1. 從樣本中可用特徵 $Q$ 隨機選擇一個attributes(特徵) $q$
2. 隨機從特徵值最大與小間的均勻分佈中取值當作截斷值 $p$
3. 根據特徵進行分類，把拿到樣本小於 $p$ 的放在左子樹，大於則放在右子樹
- 特徵值 $< p$ ➔ 左子樹($X_l$)
- 特徵值 $\geq p$ ➔ 右子樹($X_r$)
4. 持續遞迴建立子樹，直到滿足兩點其一
- 1.樹的高度達到限制(如果達到限制，就把剩下資料全部放入葉節點中)
- 2.節點資料量剩下一筆或更少


建立好iTree可以使用這棵樹進行預測，來判斷新輸入的資料經過計算後是依據異常分樹來確認是否為異常。

這邊先定義 $h(x)$ 是根節點走到葉節點的的數量，也就是樹的"深度"

我們已經知道異常樣本的特性很容易前期就被切出來，不過我們究竟如何判斷深淺？(深度4對100筆資料很深，但對1000筆資料很淺)，因此需要進行正規化，得出一個對比例。

依照BST(binary search tree)的理論，我們知道 $h(x)$ 最小值是 $log(n)$ (最優)，最大值是 $n-1$ (最差)，如果直接使用使用這兩個值會造成分數每次計算出來都不一樣，且沒有一個通用的threshhold來判斷到底甚麼樣的分數為正常或異常。

基於上述理由，作者引入一個參考值的方法，加入 $c(n)$
$c(n)$ 代表給定n個樣本，BST的平均路徑長度
其數學式：$c(n)=2H(n-1) - \cfrac{2(n-1)}{n}$
> $c(n)$ 補充：
> $2H(n-1)$ 當中$H(n-1)$代表著隨機樣本數建立樹時的趨勢，乘上2則是依據理論，完美平衡二元樹平均高度大約是$log_2n$，而隨機生成出來的樹經證明大約是$2\ln n$，因此這邊的乘2由此而來。
>
> $\cfrac{2(n-1)}{n}$ 由於樹只有幾個節點的話，可能會遠離正常的對數曲線，這邊的功用是用來對於邊界的補償，將其平滑，確保小樣本依然精確
>
> 另外，$H(n)$代表著每個節點是成為其它節點的祖先期望程度(也代表著期望深度)，經推導後會是一個調和常數$\cfrac{1}{2}+\cfrac{1}{3}+\cfrac{1}{4}+...+\cfrac{1}{n}$
> 因此 $H(i)$ 中的$i$很大時可以利用自然對數來取近似值 $H(i) \approx ln(i)+0.5772156649...(歐拉常數)，以此加快運算速度$

我們就有以下狀況進行判斷
- 路徑長度$h(x) \approx c(n)$，代表正常
- 路徑長度$h(x) << c(n)$，代表著比平均更容易被孤立(很淺)，很有可能是異常

進一步整理，依據原始論文，就能得出：
$s(x,n)=2^{-\cfrac{E(h(x))}{c(n)}}$
> 補充：$E(h(x))$是代表著多棵數的期望值(平均)

$s(x,n)$代表著x在n個樣本所構建iTree異常指數，其範圍為$[0,1]$
會有三個狀況
1. 如果分數非常接近1，代表其樣本非常高機率為異常
2. 如果分數遠小於0.5，可以將其視為正常樣本
3. 如果幾乎整個樣本每個幾乎$\approx0.5$，那可以說這群資料沒有異常值

##### iForest
由於我們在一群資料中隨機選擇資料來建立iTree，如果只有建立一顆勢必不能當作檢測依據，這樣變異數太大，所以需要建立森林進行全面性的評斷。

依據原始論文iForest建構如下：
- X:原始輸入數據集(Input data)
- t:樹的樹量
- $\psi$:子抽樣大小(Sub-sanpling size)
1. 先初始化集和(森林)來存放後續生成的樹
2. 設定樹的高度限制($l$):計算單棵樹允許生長的最大高度34
計算公式為：$l=ceiling(log_2\psi)$，也就是與子抽樣大小有關，如果$\psi=256$，那樹高度限制就是8
3. 執行建樹迴圈(t次)
1.隨機抽樣：從原始資料隨機抽取 $\psi$ 筆資料，形成子集$X^{'}$
2.建立iTree:使用前面提到iTree的演算法來建立樹(輸入步驟1採集到的子集$X^{'}$、設定當前的高度是由0開始、數高度限制為$l$)
3.將建立好的一棵iTree放入一開始所初始化的iFoest中
4. 建立好由t棵iTree所形成的iForest的後回傳
> $ceiling(x)$ 代表無條件進位到最接近的整數


> [!Tip] iForest 參數設定與其意義
> (1)子抽樣大小通常會設為256，這與其他演算法資料越多越好反而相反，論文指出兩個原因，其一為正常樣本如果過多，可能讓異常樣本被正常樣本包圍，導致切分的時候次數過多而被誤認為正常樣本，其二為異常很多時會群聚在一起，小量抽樣能夠減少這狀況發生。
> (2)整個演算法核心-異常樣本很早就被切出，故不需要完整的建立一整棵iTree，並需要對其限制高度$l$。
>
> 從以上兩點也可以發現到，這是讓Isolation Forest速度較快之重要原因

##### iTree之路徑長度
介紹iTree中我們已經有$s(x,n)=2^{-\cfrac{E(h(x))}{c(n)}}$，$h(x)$代表著樣本$x$輸入iTree後之路徑長度，在此小節中就是要來介紹$h(x)$是要如何算出路徑。

主要演算法如下：
會有幾個主要參數
- $x$：要檢測之樣本
- $T$：以建立好之一棵iTree
- $e$：當前目前累積之路徑長度(初始會設置為0)

接著
1. 檢查是否為葉節點
2. 若為葉節點，則回傳$h(x)=e+c(T.size)$，當中$T.size$為葉節點中剩餘的訓練資料數量，並且利用$c$來估算剩下資料會形成的樹深度
3. 若不是葉節點，就進行一般二元樹搜尋，如果比節點小往左子樹走，反之則往右子樹走，隨著每遍歷一個節點就需+1長度路徑。