關注並標星索信達
每天打卡閱讀
更快走進金融人工智能世界
━━━━━━
我們是索信達集團旗下的金融人工智能實驗室團隊，微信公眾號（datamargin)將不定期推送原創AI科學文章。我們的作品都是由實戰經驗豐富的AI科學技術人員或資深顧問精心準備，志在分享結合實際業務的理論應用和心得體會。
文 | 索 信 達 楊 健 穎
本文主要介紹異常值檢測領域一種高效的非監督算法——孤立森林。該算法構建多棵孤立樹將每個樣本單獨分成一類，通過衡量分類時各樣本點被區分開的難易程度來尋找異常值。以往異常值檢測方法多用有監督模型，需要使用歷史數據對交易行為進行分類，所以這些模型只能識別歷史數據中已有的詐騙手段，新的欺詐方式卻難以識別。而孤立森林非監督的檢測原理可以很好的克服這一問題，而且該算法還擁有高精度和線性時間複雜度的特點，非常適用於金融行業的反欺詐領域。
一、引言
孤立森林（Isolation Forest,簡稱iForest）是劉飛博士在莫納什大學就讀期間在陳開明教授和周志華教授的指導下發表的一種高效的無監督異常值檢測方法，具有線性時間複雜度和高精準度，適用於金融交易欺詐檢測。
該方法主要思想就是對數據集建立很多棵分類樹將數據集中的樣本點分開，由於異常點在數據集中佔比比較少，且在一些特徵上與正常點有差異，所以將樣本點進行分類時異常點更容易被區分開。而正常樣本點由於佔比較大且彼此之間特徵差異很小故很難區分開。iForest就是通過衡量分類時各樣本點被區分開的難易程度來尋找異常值的，這一難易程度主要通過分類樹中分類樣本時所需的路徑長度來衡量的，路徑越長說明越難分開。這裡舉一個簡單的例子說明這一原理：
特徵1
特徵2
特徵3
特徵4
特徵5
正常點1
1 100021
3正常點2
110051.9
14正常點3
19982.21
2.9
異常點
0
110.03-1
100
假設有4個樣本，其中1個異常點，另外三個是正常點，每個樣本有5個特徵，且異常點在這些特徵上都明顯與正常點不一樣。現在我們要構造一個分類樹將這些樣本分開，保證每個樣本被單獨分成一類（即一個葉節點只有一個樣本）：任選一個特徵，如特徵2,特徵2取值區間為[11,1005]；再從特徵2的取值區間內任選一個分割點，此時選取的分割點有極大的可能會來自區間[11,998]，而不太可能來自[998,1005]，所以這一特徵的分割結果就是將異常點單獨分為一類，3個正常點分成一類；再繼續選擇特徵和分割點進行切分，直至每個樣本被單獨分成一類。我們可以看到在這個例子中，由於異常點在各個特徵上與正常點明顯不一樣，所以只需要任選一個特徵（即在分類樹中用一個節點進行切分）就可以和正常點分開。但正常點之間的特徵很相似，需要多次切分才能被單獨分開。iForest就是通過衡量分類時各樣本點被區分開的難易程度來尋找異常值。下面我們將介iForest的理論模型。
二、《數據結構》中的"樹"
滿二叉樹:在正式介紹iForest的模型之前需要先簡單介紹《數據結構》中的“滿二叉樹”的相關知識。在《數據結構》中“樹”是數據的一種結構，從圖像上看類似於機器學習中的“決策樹”，它是由
個有限結點組成一個具有層次關係的集合。例如，圖1就是《數據結構》中某種樹的結構。
《數據結構》中“樹”的類型有多種，其中有一種被稱為滿二叉樹的結構，這裡採用國外的定義，滿二叉樹被定義為樹中的所有節點都有2個子節點或沒有子節點，如圖2所示就是滿二叉樹。若滿二叉樹的最後一層有
個節點，則其餘層節點共有
個，整棵樹總共有
個節點。我們稱二叉樹最開始的那個節點為根節點，最後一層沒有子節點的節點為葉節點。
二叉搜索樹:二叉搜索樹也是《數據結構》中“樹”的一種，它或者是一棵空樹，或者是具有下列性質的二叉樹：若它的左子樹不空，則左子樹上所有結點的值均小於它的根結點的值；若它的右子樹不空，則右子樹上所有結點的值均大於它的根結點的值；它的左、右子樹也分別為二叉排序樹。例如，圖3就是《數據結構》中二叉搜索樹的結構。
其實可以把二叉搜索樹理解為一種存儲數據的方式，可以通過二叉搜索樹來查找存儲在其中的數據，這樣也就對應了查找數據所需要的次數。例如，我們想通過圖3的二叉搜索樹查找13，第一步發現8比13小，則往8的右邊搜索；第二步發現10比13小，則往10的右邊搜索；第三步發現14比13大，則往14的左邊搜索，從而找到了13。這時搜索是成功的，需要3步。再例如，我們想通過圖3的二叉搜索樹查找15，第一步發現8比15小，則往8的右邊搜索；第二步發現10比15小，則往10的右邊搜索；第三步發現14比15小，則往14的右邊搜索，但14的右邊為空，這時將在14的右邊插入15這個值。這時搜索是不成功的，也需要3步。
從而我們可以發現，二叉搜索樹中查找數據時有成功和不成功兩種結果，若成功則返回對應的值，若不成功則在相應位置插入我們所查找的值作為新值。成功或不成功都有查找次數這個值。
三、孤立樹
算法思路:孤立森林是由很多棵孤立樹（Isolation Tree,簡稱iTree）組成的一種集成的模型，每棵iTree都是一棵滿二叉樹，樹中的所有節點都有2個子節點或沒有子節點。每棵iTree的建立過程如下：
給定含
個樣本的集合
通過隨機選擇數據集的特徵
和隨機選擇特徵的分裂值
來遞歸樣本集
，從而建立iTree。遞歸過程直到滿足以下三個條件之一才停止：①iTree的深度達到限定的最大值；②某次遞歸後iTree的節點只有一個樣本；③某次遞歸後iTree的節點所包含的數據都有相同的值。在假定樣本集
中所有點都不同的情況下，當iTree充分生長時，樣本集中的每個樣本
都會是iTree的葉節點。iTree的算法思路如下所示：
Algotithm：iTree
Inputs:
- input data,
– current tree height,
- height limit Output: an iTree
1: if
or
then
2: return
3: else
4: let
be a list of attributes in
5: randomly select an attribute
6: randomly select a split point
from
and
values of attribute
in
7:
8：
9: return
10:
11:
12:
13: end if
iTree 中的評價指標
（1）路徑長度
這裡定義 iTree 中節點
的路徑長度
為從根節點貫穿到
所在的葉節點的邊的數量。
( 2）路徑長度平均值
iTree 中葉節點的平均路徑長度
與二叉搜索樹不成功查找時所需的路徑長度相同(這裡的證明來自參考文獻[4])，所以這裡借用二叉搜索樹的相關知識來定義 iTree 中葉節點的平均路徑長度
的平均值。給定一個含
個樣本的數據集，二叉搜索樹中不成功查找的平均路徑長度為：
其中，
是調和級數，
（ 歐拉常數 ）。
也正是給定
個樣本時，一棵iTree路徑長度
的平均值。在樣本量固定
時，不同iTree的
其實是相同的。
四、孤立森林
算法思路: iForest 就是由多棵 iTree 組成的一種集成模型。根據劉飛博士等的研究表明，與傳統的機器學習算法要求大樣本相比， iForest 在小樣本時的表現更好。所以根據他們的建議，在使用 iForest 檢測異常值時，先對較大的原始樣本量進行多次抽樣（設
次），每次隨機抽出一部分數據（設
個數據）建立一棵iTree，多次抽樣可以建立多棵iTree（
棵）組合成iForest。 iForest 的算法思路如下所示：
Algotithm:iForest
Input:
-input data,
-number of trees,
-smapling size
Output:a set of
iTrees
1: Initialize Forest
2: set height limit
3: for
to
do
4:
5:
6: end for
7: return Forest
評價指標--異常值得分
異常值得分
定義為：
其中，iForest中有很多棵iTree，對於某個樣本
而言，每棵iTree的葉節點
都有一個路徑長度
，
是
這個樣本在iForest的不同iTree中路徑長度的平均值。這裡容易混淆的是
和
的結構：
是給定
個樣本時，一棵iTree的平均路徑長度，
只與
有關，在一個iForest中，每棵iTree的
是一個固定不變的常數。
是
這個樣本在iForest的不同iTree中路徑長度
的平均值。從異常值得分
的定義可知，
是一個關於
的單調函數，
，且
越大則對應的樣本點x越有可能是異常點。當 iForest 模型建立好之後，通過再計算各個樣本點的異常值得分來判斷該樣本點是否為異常值，得分越高越有可能是異常值。
現在Python的sklearn庫裡已經集成了iForest的算法，其主要調用方法如下：
五、應用總結
金融領域的欺詐行為往往在某些地方與正常行為不一樣，這些欺詐行為可以被認為是數據中的異常值，以往的檢測方法一般是構建有監督的分類模型來進行分析：一次交易或一個客戶是一個樣本，有風險是一類，無風險是另一類，交易行為的一些信息是樣本的特徵，通過構建分類模型來識別這次交易（或這個客戶）是否欺詐。這些模型的數據來自已有的數據，這導致這些模型只能識別歷史數據中已經存在的詐騙手段，而新的欺詐方式由於不在歷史數據中故難以識別，這極大的制約了金融交易欺詐檢測領域數據挖掘模型的應用。而iForest是一種無監督的方法，只需要知道樣本點的特徵即可，無需確定樣本點的所屬類別，這樣一來傳統有監督的金融反欺詐模型只能識別歷史已有的欺詐模式這一侷限性就大大減小了，這特別適用於金融領域的欺詐識別。而且iForest在保證高精度的同時還只具有線性的時間複雜度，模型的計算量也較小。
參考資料：
[1] Aggarwal, Charu C. Outlier Analysis, 2nd ed[M]. Berlin, Germany:Springer. 2016.
[2]Liu F T , Ting K M , Zhou Z H . Isolation Forest[C]// Data Mining, 2008. ICDM '08. Eighth IEEE International Conference on. IEEE, 2009.
[3]Liu F T , Ting K M , Zhou Z H . Isolation-Based Anomaly Detection[J]. ACM Transactions on Knowledge Discovery from Data, 2012, 6(1):1-39.
[4]B. R. Preiss. Data Structures and Algorithms with ObjectOriented Design Patterns in Java. Wiley, 1999.
