用機器學習檢測異常點擊流

本文內容是我學習ML時做的一個練手項目，描述應用機器學習的一般步驟。該項目的目標是從點擊流數據中找出惡意用戶的請求。點擊流數據長下圖這樣子，包括請求時間、IP、平臺等特征：

該項目從開始做到階段性完成，大致可分為兩個階段：算法選擇和工程優化。算法選擇階段挑選合適的ML模型，嘗試了神經網絡、高斯分布、Isolation Forest等三個模型。由于點擊流數據本身的特性，導致神經網絡和高斯分布并不適用于該場景，最終選擇了Isolation Forest。工程優化階段，最初使用單機訓練模型和預測結果，但隨著數據量的增加，最初的單機系統出現了性能瓶頸；然后開始優化性能，嘗試了分布化訓練，最終通過單機異步化達到了性能要求。

1 算法選擇

1.1 神經網絡

剛開始沒經驗，受TensorFlow熱潮影響，先嘗試了神經網絡。選用的神經網絡是MLP（Multilayer Perceptron，多層感知器），一種全連接的多層網絡。MLP是有監督學習，需要帶標簽的樣本，這里“帶標簽”的意思是樣本數據標注了哪些用戶請求是惡意的、哪些是正常的。但后臺并沒有現成帶標簽的惡意用戶樣本數據。后來通過安全側的一些數據“間接”給用戶請求打上了標簽，然后選擇IP、平臺、版本號、操作碼等數據作為MLP的輸入數據。結果當然是失敗，想了下原因有兩個：

1， 樣本的標簽質量非常差，用這些樣本訓練出來的模型性能當然也很差；

2， 輸入的特征不足以刻畫惡意用戶。

數據的質量問題目前很難解決，所以只能棄用MLP。

1.2 高斯分布

然后嘗試其他模型。通過搜索發現，有一類ML模型專門用于異常檢測，找到了Andrew Ng介紹的基于高斯分布的異常檢測算法：高斯分布如下圖所示：

這個算法的思想比較簡單：與大部分樣本不一致的樣本就是異常；通過概率密度量化“不一致”。具體做法是：選擇符合高斯分布或能轉換為高斯分布的特征，利用收集到的數據對高斯分布做參數估計，把概率密度函數值小于某個閾值的點判定為異常。

所謂的參數估計是指，給定分布數據，求分布的參數。對高斯分布來說，就是求μ和σ。用極大似然估計可以得到高斯分布參數的解析解：

得到高斯分布參數后，用下式計算概率密度：

X表示一個特征輸入。若有多個特征x0、x1、…、xn，一種簡單的處理方法是將其結果連乘起來即可：f(x) = f(x0)f(x1)…f(xn)。

然后選定一個閾值ε，把f(x) < ε的樣本判定為異常。ε值需根據實際情況動態調整，默認可設定ε = f(μ- 3σ)。

把這個模型初步應用于點擊流異常檢測時，效果還不錯，但在進一步實施過程中碰到一個棘手問題：樣本中最重要的一個特征是操作碼，當前操作碼在微信后臺的取值范圍是[101, 1000]，每個操作碼的請求次數是模型的基礎輸入，對900個特征計算概率密度再相乘，非常容易導致結果下溢出，以致無法計算出精度合適的概率密度值。這個現象被稱為維度災難（Dimension Disaster）。

解決維度災難的一個常見做法是降維，降維的手段有多種，這里不展開討論了。在點擊流分析的實踐中，降維的效果并不好，主要原因有兩個：

1， 正常用戶和惡意用戶的訪問模式并不固定，導致很難分解出有效的特征矩陣或特征向量；

2， 降維的本質是有損壓縮，有損壓縮必定導致信息丟失。但在本例中每一維的信息都是關鍵信息，有損壓縮會極大破壞樣本的有效性。

高斯分布模型的維度災難在本例中較難解決，只能再嘗試其他模型了

1.3 Isolation Forest

Isolation Forest，可翻譯為孤異森林，該算法的基本思想是：隨機選擇樣本的一個特征，再隨機選擇該特征取值范圍中的一個值，對樣本集做拆分，迭代該過程，生成一顆Isolation Tree；樹上葉子節點離根節點越近，其異常值越高。迭代生成多顆Isolation Tree，生成Isolation Forest，預測時，融合多顆樹的結果形成最終預測結果。Isolation Forest的基礎結構有點類似經典的隨機森林（Random Forest）。

這個異常檢測模型有效利用了異常樣本“量少”和“與正常樣本表現不一樣”的兩個特點，不依賴概率密度因此不會導致高維輸入的下溢出問題。提取少量點擊流樣本測試，它在900維輸入的情況下也表現良好，最終選擇它作為系統的模型。

2 工程優化

工程實現經歷了單機訓練、分布式訓練、單機異步化訓練3個方案，下面內容介紹實現過程中碰到的問題和解決方法。

2.1 單機訓練

整個系統主要包括收集數據、訓練模型、預測異常、上報結果四個部分。

2.1.1 收集數據

剛開始嘗試該模型時，是通過手工方式從mmstreamstorage獲取樣本的：

1，通過logid 11357，得到手工登錄成功用戶的uin和登錄時間；

2，利用mmstreamstorage提供的接口，得到用戶登錄后10分鐘的點擊流；

但這樣做有兩個缺點：

1，上述步驟1是離線手工操作的，需要做成自動化；

2，mmstreamstorage的接口性能較差，只能提供2萬/min的查詢性能，上海IDC登錄的峰值有9萬/min。

改進辦法是復用點擊流上報模塊mmstreamstorage，增加一個旁路數據的邏輯：

1，手工登錄時在presence中記錄手工登錄時間，mmstreamstorage基于該時間旁路一份數據給mmguardstore。由于mmstreamstorage每次只能提供單挑點擊流數據，所以需要在mmguardstore中緩存；

2，mmguardstore做完數據清洗和特征提取，然后把樣本數據落地，最后利用crontab定期將該數據同步到Hadoop集群中。

最終的數據收集模塊結構圖如下所示：

點擊流數據提供了IP、平臺、版本號、操作碼等特征，經過多次試驗，選定用戶手工登錄后一段時間內操作碼的訪問次數作為模型的輸入。

上面我們提到過點擊流的操作碼有900個有效取值，所以一個顯然的處理方法是，在mmguardstore中把用戶的點擊流數據轉化為一個900維的向量，key是cgi id，value是對應cgi的訪問次數。該向量刻畫了用戶的行為，可稱為行為特征向量。

2.1.2 訓練模型

初起為了控制不確定性，只輸入1萬/分鐘的樣本給模型訓練和預測。系統的工作流程是先從Hadoop加載上一分鐘的樣本數據，然后用數據訓練Isolation Forest模型，最后用訓練好的模型做異常檢測，并將檢測結果同步到tdw。

在1萬/分鐘輸入下取得較好的檢測結果后，開始導入全量數據，全量數據數據的峰值為20萬/分鐘左右。出現的第一個問題是，一分鐘內無法完成加載數據、訓練模型、預測結果，單加載數據就耗時10分鐘左右。這里先解釋下為什么有“一分鐘”的時間周期限制，主要原因有兩個：

1， 想盡快獲取檢測結果；

2， 由于點擊流異常檢測場景的特殊性，模型性能有時效性，需要經常用最新數據訓練新的模型。

解決性能問題的第一步是要知道性能瓶頸在哪里，抽樣發現主要是加載數據和訓練模型耗時較多，預測異常和上報結果的耗時并沒有隨數據量的增加而快速上漲。

加載數據的耗時主要消耗在網絡通信上：樣本文件太大了，導致系統從Hadoop同步樣本數據時碰到網絡帶寬瓶頸。但由于樣本是文本類數據，對數據先壓縮再傳輸可極大減少通信量，這里的耗時比較容易優化。

訓練模型的耗時增加源于輸入數據量的增加。下圖是1萬樣本/min的輸入下，系統個階段的耗時：

其中：
加載程序： 2s
加載數據： 6s
訓練模型：11s
分類異常： 2s
保存結果： 4s
單輪總耗時：25s
需處理全量數據時，按線性關系換算，“訓練模型”耗時為：11s * 24 = 264s，約為4.4分鐘，單機下無法在1分鐘內完成計算。
最先想到的優化訓練模型耗時的辦法是分布式訓練。

2.2 分布式訓練

由于scikit-learn只提供單機版的Isolation Forest實現，所以只能自己實現它的分布式版本。了解了下目前最常用的分布式訓練方法是參數服務器（Parameter Server，PS）模式，其想法比較簡單：訓練模型并行跑在多機上，訓練結果在PS合并。示意圖如下所示：

分布式訓練對算法有一定要求，而Isolation Forest正好適用于分布式訓練。

然后嘗試在TensorFlow上實現Isolation Forest的分布式訓練版本。選擇TensorFlow的原因有主要兩個：

1， TensorFlow已經實現了一個分布式訓練框架；

2， TensorFlow的tf.contrib.learn包已經實現的Random Forest可作參考（Isolation Forest在結構上與Random Forest類似），只需對Isolation Forest定制一個Operation即可。

寫完代碼測試時，發現了個巨坑的問題：TenforFlow內部的序列化操作非常頻繁、性能十分差。構造了110個測試樣本，scikit-learn耗時只有0.340秒，29萬次函數調用；而TensorFlow耗時達207.831秒，有2.48億次函數調用。

TensorFlow性能抽樣：

Scikit-learn性能抽樣：

從TensorFlow的性能抽樣數據可以看到，耗時排前排的函數都不是實現Isolation Forest算法的函數，其原因應該與TensorFlow基于Graph、Session的實現方式有關。感覺這里坑比較深，遂放棄填坑。

也了解了下基于Spark的spark-sklearn，該項目暫時還未支持Isolation Forest，也因為坑太深，一時半會搞不定而放棄了。

2.3 單機異步化訓練

沒搞定分布式訓練，只能回到單機場景再想辦法。單機優化有兩個著力點：優化算法實現和優化系統結構。

首先看了下scikit-learn中Isoaltion Forest的實現，底層專門用Cython優化了，再加上Joblib庫的多CPU并行，算法實現上的優化空間已經很小了，只能從系統結構上想辦法。

系統結構上的優化有兩個利器：并行化和異步化。之前的單機模型，加載數據、訓練模型、預測異常、上報結果在單進程中串行執行，由此想到的辦法是啟動4個工作進程分別處理相應的四個任務：異步訓練模型、預測異常和上報結果，并行加載數據。工作進程之間用隊列通信，隊列的一個優勢是容易實現流量控制。

寫完代碼測試，卻發現YARD環境中的Python HDFS庫在多進程并發下直接拋異常。嘗試多個方法發現這個問題較難解決，暫時只能想辦法規避。經測試發現，直接從Hadoop同步所有壓縮過的樣本數據只需2秒左右，由此想到規避方法是：先單進程同步所有樣本數據，再多進程并發解壓、加載和預測。

按上述想法修改代碼測試，效果較好，處理所有樣本只需20秒左右，達到了1分鐘處理完所有樣本的要求。然后提交YARD作業線上跑，處理所有樣本耗時卻達到200～400秒：

咨詢YARD側同學，得知YARD對提交的離線作業有CPU配額的硬限制，分時段配額如下表：

00:00~09:00 80%
09:00~19:00 50%
19:00~23:00 15%
23:00~24:00 50%

晚高峰時段的配額只有15%。

與YARD側同學溝通，他們答應后續會支持scikit-learn庫的在線服務。目前通過手工方式在一臺有scikit-learn的mmguardstore機器上運行在線服務，晚高峰時段處理全量數據耗時為20秒左右。

最終的系統結構圖如下圖所示：

模型訓練進程定期訓練最新的模型，并把模型通過隊列傳給預測進程。預測進程每分鐘運行一次，檢查模型隊列上是否有新模型可使用，然后加載數據、檢測異常，將檢測結果通過上報隊列傳給上報進程。上報進程block在上報隊列上，一旦發現有新數據，就根據數據類型執行上報監控、上報tdw等操作。

2.4 評估性能

安全側將異常用戶分為以下幾類：盜號、LBS/加好友、養號、欺詐、外掛/多開等。由于這些分類的異常打擊是由不同同學負責，不便于對Isolation Forest的分類結果做評估，因此需要在Isolation Forest的基礎上，再加一個分類器，標記“異常樣本”的小類。利用操作碼實現了該分類器。

接入全量數據后，每天準實時分析1億量級的樣本，檢測出500萬左右的異常，精確分類出15萬左右的惡意請求。惡意請求的uin、類型、發生時間通過tdw中轉給安全側。安全側通過線下人工分析和線上打擊，從結果看檢測效果較好。

2.5 持續優化

再回過頭觀察點擊流數據，我們使用的Isolation Forest模型只利用了操作碼的統計數據?？梢悦黠@看到，點擊流是一個具備時間序列信息的時序數據。而自然語言處理（Natural Language Processing，NLP）領域已經積累了非常多的處理時序數據的理論和實戰經驗，如LSTM、word2vec等模型。后續期望能引入NLP的相關工具挖掘出更多惡意用戶。