[筆記] 機器學習 異常檢測 ( Anomaly detection )

• 主要用於非監督式學習
• 假設有一組資料 : {x⁽¹⁾，x⁽²⁾，…，x^(m)}

• 異常檢測用於檢查新的一筆資料 x_test 是否異常

  • p(x_test) < ε : 可能異常
  • p(x_test) ≥ ε : 正常

• 常見的應用

  • 欺詐檢測 ( Fraud detection ) :

    • 對不同的用戶計算特徵變量 : 登入頻率、訪問某頁面的次數、發文次數、打字速度…等
    • 根據這些資料建立一個模型 p(x)
    • 對 p(x) < ε 的可能異常用戶，進一步篩選或要求驗證身分

  • 工業生產領域 :

    • 檢查是否有異常飛機引擎…等

  • 數據中心的計算機監控 :

    • 用於管理多個計算機時，檢查計算機是否異常
    • 特徵量也許是 : 內存的消耗、記憶體的訪問、CPU 負載、CPU 負載與網路流量的比值…等

高斯分布 ( Gaussian distribution )

• 又稱常態分布 ( normal distribution )

• 代表 x 符合高斯分布 : x ~ N(μ, σ²) = $\dfrac{1}{\sqrt{2π}σ}exp(- \dfrac{(x - μ)^2}{2σ^2})$

  • μ 決定中心，μ = $\dfrac{1}{m}\sum_{i = 1}^{m}x^{(i)}$

  • σ 決定寬度，σ 越小 : 圖越細高，σ 越大 : 圖越寬矮，σ² = $\dfrac{1}{m}\sum_{i = 1}^{m}(x^{(i)} - μ)^2$

    • 計算 σ²，機器學習上習慣使用 $\dfrac{1}{m}$，而統計學上是使用 $\dfrac{1}{m - 1}$

• p(x; μ, σ²) 表示 x 的概率分布

演算法

• 假設有 m 筆資料 : {x⁽¹⁾，x⁽²⁾，…，x^(m)}

• 每筆資料有 n 個特徵值 : x₁、x₂、…、x_n

  • x₁ ~ N(μ₁, σ₁²)
  • x₂ ~ N(μ₂, σ₂²)
  • …
  • x_n ~ N(μ_n, σ_n²)

• p(x) = p(x₁; μ₁, σ₁²)p(x₂; μ₂, σ₂²)…p(x_n; μ_n, σ_n²) = $\prod_{j = 1}^{n}p(x_j; \mu_j, \sigma_j^2)$

步驟

1. 選擇特徵值 x_j，這些特徵值通常能夠看出異常

2. 算出 μ₁，…，μ_n，σ₁²，…，σ_n²

   • μ_j = $\dfrac{1}{m}\sum_{i = 1}^{m}x_j^{(i)}$

   • σ_j² = $\dfrac{1}{m}\sum_{i = 1}^{m}(x_j^{(i)} - μ_j)^2$

     function [mu sigma2] = estimateGaussian(X)
     
     [m, n] = size(X);
     
     mu = zeros(n, 1);
     sigma2 = zeros(n, 1);
     
     mu = sum(X) / m;
     sigma2 = sum((X - mu) .^ 2) / m
     
     end

   • 在 Octave 上算出 μ、σ² 的函式

3. 使用 p(x) 計算新的資料 x

   • p(x) = $\prod{j = 1}^{n}p(x_j; \mu_j, \sigma_j^2)$ = $\prod{j = 1}^{n}\dfrac{1}{\sqrt{2π}σ_j}exp(- \dfrac{(x_j - μ_j)^2}{2σ_j^2})$
   • 如果 p(x) < ε 則可能異常

建立異常檢測系統

開發與評估

• 當我們開發異常檢測系統時，必須要選出特徵值和選擇 ε，此時我們就需要評估算法來幫助我們選出合適的特徵值和 ε

1. 將資料分為訓練集、交叉驗證集、測試集 ( 這些資料是帶標籤的 )

   • 交叉驗證集、測試集包含有各半的異常數值，帶 y = 1 標籤的資料

2. 在使用訓練集訓練出來的的模型 p(x) 上預測交叉驗證集

   • if p(x) < ε，異常
   • if p(x) ≥ ε，正常

3. 評估預測結果

   • 算出查準率 ( Precision )
   • 算出召回率 ( Recall )

   • 最後使用 F₁ Score 選出最好的結果 ( 特徵值、ε )

     function [bestEpsilon bestF1] = selectThreshold(yval, pval)
     
     bestEpsilon = 0;
     bestF1 = 0;
     F1 = 0;
     
     stepsize = (max(pval) - min(pval)) / 1000;
     for epsilon = min(pval):stepsize:max(pval)
     
       % 算出是否異常的 1、0 向量
       predictions = (pval < epsilon);
     
       % 計算真陽性、假陽性、假陰性
       tp = sum((predictions == 1) & (yval == 1));
       fp = sum((predictions == 1) & (yval == 0));
       fn = sum((predictions == 0) & (yval == 1));
     
       % 計算查準率、召回率
       pre = tp / (tp + fp);
       rec = tp / (tp + fn);
     
       % 計算 F1
       F1 = 2 * (pre * rec) / (pre + rec);
     
       if F1 > bestF1
          bestF1 = F1;
          bestEpsilon = epsilon;
       end
     
     end
     
     end

   • 在 Octave 上選擇 ε 的函式

4. 使用測試集驗證最終模型

異常檢測與監督式學習

• 在評估時，既然我們都已經有了帶標籤的資料，那為何不使用監督式學習來預測呢?

• 適合使用異常檢測 :

  • 正樣本 ( y = 1 ) 資料量很少 ( EX : 0 ~ 50 )
  • 負樣本 ( y = 0 ) 資料較多
  • 正樣本較少時，要學習算法從中學習是非常困難的
  • 也許未來需要檢測一種全新沒看過的異常資料，這說明應該對負樣本建立高斯模型，而不是對正樣本建模
  • 例如 : 欺詐檢測、工業生產領域、數據中心的計算機監控…等 ( 這些應用在有較多資料時，就比較偏向使用監督式學習 )

• 適合使用監督式學習 :

  • 正樣本與負樣本資料量都很多
  • 擁有足夠多的正樣本使算法能夠感覺正樣本是什麼樣的
  • 假設未來的正樣本與訓練集中的相似，那就適合使用監督式學習
  • 例如 : 分類垃圾郵件、天氣預報、分類是否罹癌…等

挑選特徵值

• 通常在異常檢測前，會畫出數據 ( Octave 裡直方圖可以使用 hist )，確保數據是高斯分布
• 假如特徵值的資料沒有高斯分布，算法依然會正常運算，但是不優
• 所以假如沒有高斯分布，我們可以對資料做些轉換 ( 開根號、取對數… )，通常會進行對數轉換 : log(x)

• 誤差分析 :

  1. 完整的訓練出算法
  2. 在交叉驗證集運行算法，並找出預測出錯的樣本

  3. 看看是否能找出新的特徵值來幫助算法

     • 依照可能的出錯情況新增特徵值 :

       • 例如數據中心的計算機監控，某台異常的電腦可能執行較多工作，CPU 負載較大，網路流量正常，那 CPU 負載與網路流量的比值就會是很好的特徵值

多元高斯分布 ( multivariate Gaussian distribution )

• 當具有多個特徵值時，簡單的按照每一個特徵值概率相乘來檢測異常是不準確的，因此需要改良版的異常檢測算法，叫做多元高斯分布

演算法

• 假設有 m 筆資料 : {x⁽¹⁾，x⁽²⁾，…，x^(m)}
• 每筆資料有 n 個特徵值 : x₁、x₂、…、x_n

• 使用模型 p(x)

  • 這次不使用模型 p(x₁)、p(x₂)、…、p(x_n)

• 算出 μ 和 Σ ( n * n 矩陣 )

  • μ = $\dfrac{1}{m}\sum_{i = 1}^{m}x^{(i)}$
  • Σ 是協方差矩陣，Σ = $\dfrac{1}{m}\sum_{i = 1}^{m}(x^{(i)} - μ)(x^{(i)} - μ)^T$

• p(x; μ, Σ) = $\dfrac{1}{(2π)^{\frac{n}{2}}|\Sigma|^{\frac{1}{2}}}exp\Big(- \dfrac{1}{2}(x - μ)^T\Sigma^{-1}(x - μ)\Big)$

• 用 p(x) 計算新的資料 x

  • p(x) < ε 屬於異常

• 基本的 Σ

• Σ 對角數值增加

• Σ 對角單一數值增加

• Σ 反對角數值為正

• Σ 反對角數值為負

高斯分布與多元高斯分布的差別

• 高斯分布

  • 較常用
  • p(x) = $\prod{j = 1}^{n}p(x_j; \mu_j, \sigma_j^2)$ = $\prod{j = 1}^{n}\dfrac{1}{\sqrt{2π}σ_j}exp(- \dfrac{(x_j - μ_j)^2}{2σ_j^2})$
  • 只能做到單軸 ( x、y、z、… ) 的縮放，無法對特徵值之間的相關性建模
  • 若要對特徵值間的相關係建模，除了使用多元高斯分布，也可以新增一個特徵值，此特徵值為二到多個特徵值得相關，例如 : x_new = $\dfrac{x_1}{x_2}$
  • 運算量小，可以運算極多特徵值
  • 就算資料量小也能正常運行

• 多元高斯分布

  • 較不常使用
  • p(x) = $p(x; \mu, \Sigma)$ = $\dfrac{1}{(2π)^{\frac{n}{2}}|\Sigma|^{\frac{1}{2}}}exp\Big(- \dfrac{1}{2}(x - μ)^T\Sigma^{-1}(x - μ)\Big)$
  • 可以自動對特徵值之間的相關性建模，事實上 Σ 就是 $\begin{bmatrix} \sigma_1^2 & … & … & … \ … & \sigma_2^2 & … & … \ … & … & … & … \ … & … & … & \sigma_n^2 \end{bmatrix}$，若上三角與下三角皆為 0，那就等於是高斯分布的算法
  • 運算量大，不適合運算較多的特徵值
  • 資料量 m 必須大於特徵量 n，若 m ≤ n 則會造成 Σ 為不可逆矩陣，不能運算，通常用於 m 大於 n 非常多 ( 建議 10 倍 n 以上 )

  • 造成 Σ 為不可逆矩陣的情況 :

    • m ≤ n
    • 擁有冗餘的特徵值 ( 機率很低 )，例如 : x₁ = x₂、x₃ = x₄ + x₅…等

tags: 筆記 機器學習 異常檢測