一種基於自動編碼機的分布式離群點檢測方法及系統的製作方法
2023-05-27 16:42:06 1
一種基於自動編碼機的分布式離群點檢測方法及系統的製作方法
【專利摘要】本發明涉及一種基於自動編碼機的分布式離群點檢測方法及系統，包括定義訓練數據集和測試數據集；將訓練集的訓練數據隨機分配給若干個計算單元；所有計算單元並行執行，每個計算單元求解編碼與解碼參數；匯總每個計算單元的編碼與解碼參數得到最終編碼與解碼參數，構建一個自複製模型；將自複製模型應用到測試數據集上，並行計算每條測試數據的重建誤差；按照重建誤差降序排列測試數據，重建誤差大於預定閾值的測試數據為離群點；本發明所述方法處理需要的總時間與處理的樣本個數之間是獨立的，僅僅取決於參數求解需要達到的精度；本發明非常適合基於MapReduce框架來處理大規模數據集上的離群點檢測，具有良好的伸縮性與擴展性。
【專利說明】一種基於自動編碼機的分布式離群點檢測方法及系統
【技術領域】
[0001]本發明涉及信息安全領域，尤其涉及一種基於自動編碼機的分布式離群點檢測方法及系統。
【背景技術】
[0002]在數據挖掘與統計學裡，離群點指觀察值或者樣本點顯著地偏離其它數據。在很多數據挖掘應用中，離群點被過濾和丟棄，然而從知識發現的角度來看，罕見事件常常比平常事件更有價值，因而離群點是一個有著很高的應用價值的研究領域，例如在欺詐檢測、網絡入侵檢測等領域。目前國內外基於計算機的離群點檢測方法可以分為四大類:基於統計分布、基於深度、基於距離以及基於密度的局部離群點檢測方法。
[0003]自動編碼機(Auto-Encoders)是一種特殊類型的神經網絡。自動編碼機包括編碼與解碼過程，首先用編碼機將輸入數據映射到一個隱層表示(編碼過程)，然後利用相似的變換將隱層重新映射回與輸入數據相同形狀的重建數據(解碼過程)。通過最優化重建誤差來學習編碼，常用來做特徵提取。圖1是一個包含一個隱含層的三層架構的自動編碼機示例。基本的自動編碼機也可以看做是一種自複製模型，對不包含離群點的訓練數據編碼學習自複製模型，然後通過計算測試數據的重建誤差可檢測離群點。
[0004]隨著網絡的普及，特別是物聯網和社交網絡的發展，各類感知終端產生海量的、形式多樣的半結構化或非結構化數據，形成大數據問題。我們需要在有限資源、有限時間內檢測出大規模數據集中的離群點，諸多傳統的檢測算法往往基於內存計算或者串行執行，只能處理小規模數據。基於自動編碼機的離群點檢測算法通常使用隨機梯度下降方法來求解編碼與解碼參數，求解速度慢，數據全局依賴性高，難以處理比內存大得多的大規模數據。
【發明內容】
[0005]本發明所要解決的技術問題是針對現有技術的不足，提供一種基於自動編碼機的分布式離群點檢測方法及系統，實現大規模數據集上的離群點高效準確檢測。
[0006]本發明解決上述技術問題的技術方案如下:一種基於自動編碼機的分布式離群點檢測方法，包括如下步驟:
[0007]步驟1:定義訓練數據集和測試數據集；
[0008]步驟2:將訓練集的訓練數據隨機分配給若干個計算單元；
[0009]步驟3:所有計算單元並行執行，在每個計算單元內使用隨機梯度下降算法求解編碼與解碼參數；
[0010]步驟4:匯總每個計算單元的編碼與解碼參數得到最終編碼與解碼參數，構建一個自複製模型；
[0011]步驟5:將自複製模型應用到測試數據集上，並行計算每條測試數據的重建誤差；
[0012]步驟6:按照重建誤差降序排列測試數據，重建誤差大於預定閾值的測試數據為離群點。[0013]本發明的有益效果是:本發明通過將訓練數據隨機分配到不同的計算單元，從而可以通過在並行地每一個計算單元內使用隨機梯度下降算法來求解編解碼參數，這一過程可以並行執行，從而可以通過增加計算單元來減少每個計算單元內部的計算時間，最終大大減少訓練時間；本發明所述方法處理需要的總時間與處理的樣本個數之間是獨立的，僅僅取決於參數求解需要達到的精度；本發明非常適合基於MapReduce框架來處理大規模數據集上的離群點檢測，具有良好的伸縮性與擴展性。
[0014]在上述技術方案的基礎上，本發明還可以做如下改進。
[0015]進一步，步驟I中所述訓練數據集和測試數據集分別如下式:
[0016]訓練數據集IxiIxi e Rd, I = I,…，N}用來學習自動編碼機的編碼與解碼參數；
[0017]測試數據集{V Jxi J e Rd, j = I,…，N' }，為待檢測離群點的數據集。
[0018]進一步，步驟2的具體實現為:
[0019]步驟2.1:定義每個計算單元的計算樣本個數:T = floor (N/K)；
[0020]其中，N為訓練數據集中訓練數據的條數，K為計算單元的個數；
[0021]步驟2.2:隨機劃分訓練數據集，給每個計算單元分配T個訓練樣本。
[0022]進一步，步驟3的具體實現為:
[0023]步驟3.1:所有計算單元並行執行，對於計算單元k e {1,2,…，K}，對分配的訓練數據隨機排序；
[0024]步驟3.2:初始化計算單元k的編碼參數劣與解碼參數P
[0025]步驟3.3:依次讀取單元k上的第t個樣本xf，t e {1，…，T}，T為每個計算單元計算樣本個數，依照下式更新編碼參數與解碼參數，
[0026]更新編碼參數
【權利要求】
1.一種基於自動編碼機的分布式離群點檢測方法，其特徵在於，包括如下步驟: 步驟1:定義訓練數據集和測試數據集； 步驟2:將訓練集的訓練數據隨機分配給若干個計算單元； 步驟3:所有計算單元並行執行，在每個計算單元內使用隨機梯度下降算法求解編碼與解碼參數； 步驟4:匯總每個計算單元的編碼與解碼參數得到最終編碼與解碼參數，構建一個自複製模型； 步驟5:將自複製模型應用到測試數據集上，並行計算每條測試數據的重建誤差，輸出以重建誤差為key的鍵值對； 步驟6:按照重建誤差降序排列測試數據，重建誤差大於預定閾值的測試數據為離群點。
2.根據權利要求1所述一種基於自動編碼機的分布式離群點檢測方法，其特徵在於，步驟I中所述訓練數據集和測試數據集分別如下式: 訓練數據集IxiIxi e Rd, i = l,…，N}用來學習自動編碼機的編碼與解碼參數； 測試數據集IVj e Rd, j = 1，…，N' }為待檢測離群點的數據集。 D為數據的緯度，即屬性個數。
3.根據權利要求1所述一種基於自動編碼機的分布式離群點檢測方法，其特徵在於，步驟2的具體實現為: 步驟2.1:定義每個計算單元的計算樣本個數:T = floor (N/K)； 其中，N為訓練數據集中訓練數據的條數，K為計算單元的個數； 步驟2.2:隨機劃分訓練數據集，給每個計算單元分配T個訓練樣本。
4.根據權利要求1所述一種基於自動編碼機的分布式離群點檢測方法，其特徵在於，步驟3的具體實現為: 步驟3.1:所有計算單元並行執行，對於計算單元k e {1,2,…，K}，對分配的訓練數據隨機排序； 步驟3.2:初始化計算單元k的編碼參數< 與解碼參數0^ ； 步驟3.3:依次讀取單元k上的第t個樣本Xi t e {I,…，T}, T為每個計算單元計算樣本個數，依照下式更新編碼參數與解碼參數， 更新編碼參~" 更新解碼參數^ 其中Θ1 (化丨―)表示第t輪迭代單元k上的編碼(解碼)參數；α為學習速率，▽e (Vr)表示以θ (Θ』)為參數的梯度，表示第t輪迭代單元k上的編碼(解碼)損失函數，損失函數可選擇/(屹;xf) = |.<-/(^;xf)|2，/(也;xf)表示輸入樣本<、參數為貧—i的網絡輸出，損失函數為輸入與輸出的L2範式。
5.根據權利要求1所述一種基於自動編碼機的分布式離群點檢測方法，其特徵在於，所述步驟4的具體實現為:聚集所有計算單元的編碼參數與解碼參數，計算最終編碼與解碼參數，計算公式如下式
6.根據權利要求1所述一種基於自動編碼機的分布式離群點檢測方法，其特徵在於，步驟5的具體實現為，針對測試數據集{Vj∈RD，j = l，一，N' }進行如下操作: 步驟5.1:對於測試數據X』 j並行執行，計算測試輸出xj=f(θlxj') 其中，f(9 ；x' j)表示輸入為χ』」，編碼參數為Θ的網絡輸出； 步驟5.2:根據下式計算重建誤差
7.根據權利要求1所述一種基於自動編碼機的分布式離群點檢測方法，其特徵在於，步驟3中每個計算單元之間是相互獨立的，當數據量增加時，可通過增加計算單元個數來減少每個計算單元的計算量。
8.一種實現權利要求1-7中任一項所述基於自動編碼機的分布式離群點檢測方法的系統，其特徵在於，包括數據集定義模塊、數據分配模塊、編解碼參數計算模塊、編解碼參數匯總模塊、重建誤差計算模塊和離群點篩選模塊； 所述數據集定義模塊，其用於定義訓練數據集和測試數據集； 所述數據分配模塊，其用於將訓練集的訓練數據隨機分配給若干個計算單元； 所述編解碼參數計算模塊，其用於並行計算每個計算單元的編解碼參數，每個計算單元使用隨機梯度下降算法求解編碼與解碼參數； 編解碼參數匯總模塊，其用於匯總每個計算單元的編碼與解碼參數得到最終編碼與解碼參數，構建一個自複製模型； 重建誤差計算模塊，其用於將自複製模型應用到測試數據集上，並行計算每條測試數據的重建誤差； 離群點篩選模塊，其用於按照重建誤差降序排列測試數據，重建誤差大於預定閾值的測試數據為離群點。
【文檔編號】G06N3/08GK104008420SQ201410225026
【公開日】2014年8月27日 申請日期:2014年5月26日 優先權日:2014年5月26日
【發明者】馬雲龍, 張鵬, 曹亞男, 翟立東, 杜躍進 申請人:中國科學院信息工程研究所