# [筆記] 機器學習 異常檢測 ( 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: `筆記` `機器學習` `異常檢測`