一、解決的問題

• 數據是實時產生的，對數據進行批處理所花費的成本太高了，數據產生的價值被低估

• 在高維數據下，如何能發現異常的維度？

If my time-series data with 30 features yields an unusually high anomaly score. How do I explain why this particular point in the time-series is unusual?
Ideally I'm looking for some way to visualize "feature importance" for a specific data point.

二、業內的解決方案

1、Numenta公司提出的HTM算法模型

• 背景：在大多數情況下，傳感器流的數量很大，人類很少有機會，更不用說專家干預了。 因此，以無人監督的自動方式（例如，無需手動參數調整）操作通常是必要的。 底層系統通常是非平穩的，探測器必須不斷學習和適應不斷變化的統計數據，同時進行預測。 Hierarchical Temporal Memory （HTM）網絡以有原則的方式在各種條件下穩健地檢測異常。
• 生產系統應該是高效的，非常容忍噪聲數據，不斷使用數據統計的變化，并檢測非常微妙的異常，同時最大限度地減少誤報。該算法在實時金融異常檢測中表現較好，切已經得到商業化部署。HTM與序列預測中的一些現有算法相比是有利的，特別是復雜的非馬爾可夫序列，HTM不斷學習系統，自動適應不斷變化的統計數據，這是一種與流分析特別相關的屬性。
• 該公司開發的Grok系統，目前服務在AWS，針對物理機器進行異常檢測。The Leading AIOPS Platform For Intelligent Incident Prediction And Self-Healing Operations In IT Service Assurance

2、Amazon Kinesis

2.1 應用場景

• AWS Metering
• Amazon S3 events
• Amazon Cloud Watch Logs
• http://Amazon.com online catalog
• Amazon Go Video analysis

2.2 Kinesis - RRCF調用方式

-- creates a temporary stream. CREATE OR REPLACE STREAM "TEMP_STREAM" ("passengers" INTEGER,"distance" DOUBLE,"ANOMALY_SCORE" DOUBLE);-- creates another stream for application output. CREATE OR REPLACE STREAM "DESTINATION_SQL_STREAM" ("passengers" INTEGER,"distance" DOUBLE,"ANOMALY_SCORE" DOUBLE);-- Compute an anomaly score for each record in the input stream -- using Random Cut Forest CREATE OR REPLACE PUMP "STREAM_PUMP" ASINSERT INTO "TEMP STREAM"SELECT STREAM "passengers", "distance", ANOMALY_SCOREFROM TABLE (RANDOM_CUT_FOREST (CURSOR(SELECT STREAM * FROM "SOURCE_SQL_STREAM")))-- Sort records by descending anomaly score, insert into output stream CREATE OR REPLACE PUMP "OUTPUT_PUMP" ASINSERT INTO "DESTINATION_SQL_STREAM"SELECT STREAM * FROM "TEMP_STREAM"ORDER BY FLOOR("TEMP_STREAM".ROWTIME TO SECOND), ANOMALY_SCORE DESC;

3、Azure IoT Edge, Azure Stream Analytic

• 下面的示例查詢假設在2分鐘的滑動窗口中以每秒120個事件的歷史記錄來統一輸入每秒事件的速率。 最終的SELECT語句提取并輸出得分和異常狀態，置信度為95％。

WITH AnomalyDetectionStep AS (SELECTEVENTENQUEUEDUTCTIME AS time,CAST(temperature AS float) AS temp,AnomalyDetection_SpikeAndDip(CAST(temperature AS float), 95, 120, 'spikesanddips')OVER(LIMIT DURATION(second, 120)) AS SpikeAndDipScoresFROM input ) SELECTtime,temp,CAST(GetRecordPropertyValue(SpikeAndDipScores, 'Score') AS float) ASSpikeAndDipScore,CAST(GetRecordPropertyValue(SpikeAndDipScores, 'IsAnomaly') AS bigint) ASIsSpikeAndDipAnomaly INTO output FROM AnomalyDetectionStep

4、SLS @ Alibaba Cloud

• 阿里云日志服務功能介紹

三、算法原理

3.0、無監督樹形異常檢測算法發展歷程

• 2008 - Isolation Forest Published
• 2013 - Survey on outlier detection
• 2016 - RRCF published in JMLR
• 2016 - RRCF available on Amazon Kinesis
• 2018 - RCCF available on Hydroserving

3.1 2008年Isolate Forest原理

1. 單棵樹的構建過程

iTree是一種隨機二叉樹，每個節點要么有兩個孩子，要么就是葉子節點，每個節點包含一個屬性q和一個劃分值p。

具體的構建過程如下：

從原始訓練集合X種無放回的抽取樣本子集

劃分樣本子集，每次劃分都從樣本中隨機選擇一個屬性q，再從該屬性中隨機選擇一個劃分的值p，該p值介于屬性q的最大與最小值之間

根據2中的屬性q與值p，劃分當前樣本子集，小于值p的樣本作為當前節點的左孩子，大于p值的樣本作為當前的右孩子

重復上述2，3步驟，遞歸構建每個節點的左、右孩子節點，知道滿足終止條件為止，通常終止條件為所有節點均只包含一個樣本或者多個相同的樣本，或者樹的深度達到了限定的高度

2. 構建參數的說明

有兩個參數控制著模型的復雜度：

• 每棵樹的樣本子集大小，它控制著訓練數據的大小，論文中的實驗發現，當該值增加到一定程度后，IForest的辨識能力會變得可靠，但沒有必要繼續增加下去，因為這并不會帶來準確率的提升，反而會影響計算時間和內存容量，論文實現發現該參數取256對于很多數據集已經足夠；
• 集成的樹的數量，也可以理解為對原始數據的采樣的次數，它控制著模型的集成度，論文中描述取值100就可以了；

3. 如何衡量樣本的異常值

計算樣本的異常值的過程如下：將測試數據在iTree樹上沿著對應的條件分支往下走，直到達到葉子節點，并記錄這過程中經過的路徑長度h(x)，利用如下公式進行異常分數的計算：

其中，

是二叉搜索樹的平均路徑長度，用來對結果進行歸一化處理，其中的 來估計，其中 是歐拉常數，其值大約為0.5772156649。

4. 一些缺點

• Contains all points
• Every leaf contains one distinct point
• Each node separates bounding box of it's points in two halves

3.2 2016年RRCF原理

0. 為何會引入RRCF算法？

• 數據是持續產生的，數據中的時間戳是一個重要因素，而這個維度卻經常被大家忽略
• 數據的結構和形態是未知的，需要設計一個魯棒性的算法來應對各種復雜的場景需求
• iTree是針對候選數據，進行N次無放回的采樣，通過對靜態數據集進行劃分而得到。若針對流式數據，每次都要針對最新的數據進行采樣，再去構造數據集，運行算法，得到相應的結果；
• 在針對流式數據的異常檢測場景中，缺少對序列中時序的關系的考慮，算法僅僅把當前的點當做孤立的點進行建模；

1. 針對數據流進行采樣建模

針對第一個上述的第一個問題：

• 可以采用一些采樣策略（蓄水池采樣）能準確的當前的數據點是否參與異常建模；
• 同時指定一個時間窗口長度，當建模的數據過期后，應該從模型中剔除掉；

2. 算法中核心的幾個操作

• 構造Robust Random Cut Tree操作

• 從一個Tree中刪除某個樣本

• 插入一個新的樣本到樹結構中

3. 如何衡量樣本的異常值

• 引用論文中的一段話

Let 0 be a left decision and 1 be a right decision. Thus, for x ∈ S, we can write its path as a binary string in the same manner of the isolation forest, m(x). We can repeat this for all x ∈ S and arrive at a complete model description: M(S) = ⊕x∈Sm(x), the appending of all our m(x) together. We will consider the anomaly score of a point x to be the degree to which including it causes our model description to change if we include it or not,

• 形象化的描述如下所示：

上圖左側表示構造出來的樹的結構，其中x是我們待處理的樣本點，有圖表示將該樣本點刪除后，動態調整樹結構的形態。其中q_0,...,q_r表示從樹的根節點編碼到

節點的描述串。

• 每個樣本的異常分數的含義：將點x的異常得分視為包含或不包含該點，而導致模型的描述發生改變的程度

論文中通過對上式的變換，得到對應的公式：

• 利用上述公式的描述，可以得到具體的衡量分數，但是如果將上述分數直接轉換為異常值，還需要算法同學根據自己的場景進行合理的轉換

3.3 流式改造 - 蓄水池采樣算法

• 算法大致描述：給定一個數據流，數據流長度N很大，且N直到處理完所有數據之前都不可知，請問如何在只遍歷一遍數據（O(N)）的情況下，能夠隨機選取出m個不重復的數據。
• 具體的偽代碼描述

int[] reservoir = new int[m];// init for (int i = 0; i < reservoir.length; i++) {reservoir[i] = dataStream[i]; }for (int i = m; i < dataStream.length; i++) {// 隨機獲得一個[0, i]內的隨機整數int d = rand.nextInt(i + 1);// 如果隨機整數落在[0, m-1]范圍內，則替換蓄水池中的元素if (d < m){reservoir[d] = dataStream[i];} }

通過對數據流進行采樣，可以較好的從數據流中等概率的進行采樣，通過RRCF中提供的DELETE方法，可以將置換出模型的數據動態的刪除掉，將新選擇的樣本數據動態的加入到已經有的樹中去，進而得到對應的CODISP值。

3.4 并行調用的改造

該算法同Isolation Forest算法一樣，非常適合并行構建，在此不做太多的贅述，推薦讀者使用Python一個并行的軟件包Joblib，能非常方便的幫助用戶開發。

傳送門：Joblib: running Python functions as pipeline jobs

四、算法實驗結果

4.1 多維度的流量場景實驗

• 實驗數據說明：（時間戳，流量，平均請求延遲，訪問次數），數據每5秒聚合一個點
• 該實驗結果是使用全量的數據進行RRCF樹的構造，在對結果中的全部葉子節點去獲取對應的CODISP值，可視化如下結果，其中第一條曲線表示：網站每5秒的請求流量情況；第二條曲線表示：網站每5秒的平均請求延遲情況；第三條曲線表示：網站每5秒的訪問次數情況；第四條曲線表示：每個點的CODISP值的大小；
• 在實際場景中，可以通過對CODISP值的判別來判定具體點是否是異常；

• 使用數據的前1024個點做為基礎模型的數據，去構造100棵樹；針對余下的數據點逐點輸入算法中去，采用蓄水池采樣的策略，動態的對樹內部的有效點進行增刪，實時得到最新點的CODISP值，繪制結果如下圖所示；

4.2 如何將CODISP分數轉換成異常值

• 理解下算法的本質：某個點的刪除，導致整體樹結構發生變化的程度（目前使用受影響程度正比于樹種點的數量），對于一個確定容量的樹來說，可以通過設置具體的閾值，來判別異常
• 可以針對CODISP使用K-Sigma算法，得到具體的上界異常值

4.3 如何對檢測到的異常進行可解釋性描述

• 該部分比較復雜，請等下一篇文章的分享

參考文獻

• Sudipto Guha, Nina Mishra, Gourav Roy, and Okke Schrijvers. "Robust random cut forest based anomaly detection on streams." In International Conference on Machine Learning, pp. 2712-2721. 2016.
• Byung-Hoon Park, George Ostrouchov, Nagiza F. Samatova, and Al Geist. "Reservoir-based random sampling with replacement from data stream." In Proceedings of the 2004 SIAM International Conference on Data Mining, pp. 492-496. Society for Industrial and Applied Mathematics, 2004.
• http://proceedings.mlr.press/v48/guha16-supp.pdf
• Implementation of the Robust Random Cut Forest Algorithm for anomaly detection on streams. https://klabum.github.io/rrcf/scoring-rctree.html
• 亞馬遜中關于該算法的參數說明 https://docs.aws.amazon.com/zh_cn/kinesisanalytics/latest/sqlref/sqlrf-random-cut-forest-with-explanation.html
• 亞馬遜中關于該算法的具體例子說明 https://docs.aws.amazon.com/zh_cn/kinesisanalytics/latest/dev/app-anomaly-detection.html

總結

以上是生活随笔為你收集整理的剔除异常值栅格计算器_基于数据流的异常检测： Random Cut Forest的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。