Anomaly detection（異常檢測）

1、問題定義：假設(shè)數(shù)據(jù)集{x⁽¹⁾, x⁽²⁾, ..., x⁽³⁾}表示的數(shù)據(jù)都是正常的，則判斷x_test是否異常。

若概率值 p(x_test) <?ε，則表示異常；若 p(x_test) ≥ ε ，則表示正常。

?

2、Gaussian Distribution（高斯分布 / 正態(tài)分布）：

（1）分布：X ~ N(μ，σ2)? ?μ為均值，σ2為方差.

?

（2）Parameter estimation（參數(shù)估計）：

給定數(shù)據(jù)集，估算出 μ 和 σ 的值.?

?

3、應(yīng)用高斯分布實現(xiàn)異常檢測算法：

訓(xùn)練集：{x⁽¹⁾, x⁽²⁾, ..., x^(m)}，每一個數(shù)據(jù)都是 n 維向量.

建立模型：p(x) = p(x₁; μ₁, σ₁2) p(x₂; μ₂,?σ₂2)?p(x₃; μ₃,?σ₃2) ...?p(x_n; μ_n,?σ_n2)

算法流程：

?

4、開發(fā)異常檢測系統(tǒng)：

（1）使用帶標(biāo)簽的數(shù)據(jù)集，y = 0表示正常，y = 1表示異常，即：

（2）訓(xùn)練集表示所有正常的樣本集合（視為不帶標(biāo)簽），設(shè)置交叉驗證集和測試集：

舉例：如果一共10000個正常數(shù)據(jù)，20個異常數(shù)據(jù)：

可以通過交叉驗證集選擇較好的 ε 參數(shù). 選擇算法評估結(jié)果最好的（F₁-score最高）.

（3）算法評估：

由于異常的數(shù)據(jù)占極少數(shù)，因此是傾斜類的情況，不能僅僅通過計算預(yù)測的準(zhǔn)確率來評估系統(tǒng)。需要計算 precision、recall，并計算F₁-score.

?

5、異常檢測與監(jiān)督學(xué)習(xí)的區(qū)別：

既然異常檢測也帶有便簽，為什么不直接用邏輯回歸等方法進(jìn)行分類預(yù)測呢？

?

6、特征量的選擇：

（1）特征量的調(diào)整：

在對特征向量建模時，需要使得 x_i 服從正態(tài)分布，或者接近于正態(tài)分布，如下圖所示：

若不服從正態(tài)分布，則需要進(jìn)行修正，如下圖所示：

?

?

（2）誤差分析：

當(dāng)某一個數(shù)據(jù)處于異常，但是系統(tǒng)并沒有檢測出，即 p(x) 取值仍然較大，則可能原因是特征較少。

如下圖所示，當(dāng)只有一個特征量時，p(x) 值較高，但拓展特征量后，發(fā)現(xiàn)它處在了高斯分布的外圍區(qū)域.

?

7、Multivariate gaussian distribution（多元高斯分布）：

（1）問題背景：

在監(jiān)測數(shù)據(jù)中心的例子中，有兩個特征 x1 和 x2，當(dāng)出現(xiàn)一個異常的樣本，它有較低的CPU load和較高的Memory Use，在 x1 和 x2的正態(tài)分布圖中可以看出，該樣本含有較高的 p(x1) 和 p(x2)，也就是有較高的 p(x)，并不會被判定為異常.

原因分析：我們傾向于認(rèn)為兩個特征所構(gòu)成的區(qū)域具有較為均勻的概率分布.

?

（2）算法改進(jìn)：

X的協(xié)方差矩陣，第 i 行第 j 列表示 x_i 和 x_j 的協(xié)方差，

舉例：

?

（3）應(yīng)用多元高斯分布：

① 計算參數(shù)，擬合模型：

② 對于新樣本計算 p(x)：

?若 p(x) 小于閾值，則判定為異常點.

?

（4）多元高斯分布模型與常規(guī)高斯分布模型的聯(lián)系：

常規(guī)高斯分布模型對應(yīng)多元高斯分布模型的情況：Σ 非對角線元素全為0.

?對于誤差情況，一種方法是增加特征量（上文已闡述），另一種方法是使用多元高斯模型自動捕捉不同特征量之間的相關(guān)性.

?Σ 不可逆的兩種情況：① 不滿足 m > n； ② 有冗余的特征量.

?

Recommender systems（推薦系統(tǒng)）

1、以電影推薦系統(tǒng)舉例：一共編號1 2 3 4四個人，5部電影（前3部為愛情類，后2部為動作類），評分由0-5，可見編號1、2更喜歡愛情類電影，編號3、4更喜歡動作類電影。

符號定義：

n_u：用戶的數(shù)量；

n_m：電影的數(shù)量；

r(i, j)：如果用戶 j 已經(jīng)對電影 i 進(jìn)行評分，那么 r(i, j) = 1，否則 r(i, j) = 0；

y^{(i, j)}：用戶 j 對電影 i 的評分（僅對 r(i, j) = 1的定義）.

推薦系統(tǒng)的原理：根據(jù)已知的數(shù)據(jù)，預(yù)測出帶問號的空缺數(shù)據(jù)的可能值.

?

2、基于內(nèi)容的推薦系統(tǒng)：

（1）原理：

使用兩種特征量，x₁表示愛情電影的程度，x₂表示動作電影的程度.

設(shè) x₀ = 1，第 i 部電影設(shè)為 x⁽ⁱ⁾，例如 x⁽¹⁾ = [1? 0.9? 0]^T. 用 n 表示特征數(shù)量，即 n = 2. 第 j 個用戶評價過的電影數(shù)量為 m^(j).

若觀眾的打分預(yù)測是獨立的線性回歸問題，則每一個用戶 j 都有特征參數(shù) θ^(j)，其為 n 1 維向量. 對于電影 i 的打分為 (θ^(j))^Tx⁽ⁱ⁾.

現(xiàn)對第1個用戶的第3部電影的評分進(jìn)行預(yù)測：

x⁽³⁾ = [1? 0.99? 0]^T

θ⁽¹⁾ = [0? 5? 0]^T

value =?(θ⁽¹⁾)^Tx⁽³⁾?= 4.95

?

（2）參數(shù) θ 的訓(xùn)練：（本來求和公式前的常數(shù)是 1/(2m^(j))，但為了計算方面，將 m^(j) 去除，不影響結(jié)果）

?

3、Collaborative filtering（協(xié)同過濾）：

又名 Low rank matrix factorization （低秩矩陣分解）

（1）問題描述：

假設(shè)不知道電影的各個指數(shù)（如愛情電影指數(shù)、動作電影指數(shù)等），僅僅使用上述的方法，無法進(jìn)行預(yù)測. 但若已知用戶對各類電影的喜好程度，即已知 θ，則可以預(yù)測出各類電影的指數(shù).

?

（2）目標(biāo)描述：

即

利用 θ 和 x 的重復(fù)計算和迭代，收斂到一組合適的電影特征.?

簡化問題，可以定義新的代價函數(shù) J，將問題轉(zhuǎn)換為：

? ?

（3）算法流程：

① 初始化 x⁽¹⁾, ..., x^(n_m) 和 θ⁽¹⁾, ..., θ^(n_u)，初始值設(shè)置為一個較小的隨機(jī)數(shù)（類似于神經(jīng)網(wǎng)絡(luò)，使得各個參數(shù)初始化值不一樣）；

② 使用梯度下降法，最小化 J（這里沒有考慮 x₀、θ₀，即 k 從1開始）：

③ 若對一個用戶進(jìn)行預(yù)測，給出了參數(shù) θ 或者電影的指數(shù) x，則可以使用 θ^Tx 進(jìn)行預(yù)測評分.

?

（4）電影推薦的向量化實現(xiàn)：

① 將打分?jǐn)?shù)據(jù)轉(zhuǎn)為矩陣 Y：

一般化預(yù)測評分矩陣：

?

② 電影特征矩陣：x⁽ⁱ⁾ 表示第 i 部電影的特征向量，是一列，(x⁽ⁱ⁾)^T 將列向量轉(zhuǎn)為行向量.

X = [ (x⁽¹⁾)^T??(x⁽²⁾)^T? ...? (x^(n_m))^T]^T?

每一個用戶的參數(shù) θ 同理構(gòu)成矩陣 Θ，θ^(j) 表示第 j 個用戶，是一列，(θ^(j))^T?將列向量轉(zhuǎn)為行向量.

Θ = [(θ⁽¹⁾)^T??(θ⁽²⁾)^T? ...? (θ^(n_u))^T]^T? ?(結(jié)構(gòu)類似 X )

③ 在使用協(xié)同過濾算法求得 X 和 Θ 后，預(yù)測評分矩陣為 XΘ^T.

由于 XΘ^T?有低秩屬性，因此命名：低秩矩陣分解算法.

④ 尋找電影 i 的相關(guān)電影，即尋找若干個電影 j ，使得最小化

?

4、推薦系統(tǒng)的實現(xiàn)細(xì)節(jié)：均值歸一化：

（1）問題背景：當(dāng)?shù)谖鍌€用戶對于數(shù)據(jù)中的電影一部都沒看過，即下圖的情況：

那么當(dāng)計算 θ⁽⁵⁾ 時，根據(jù)目標(biāo)函數(shù)的定義：

目標(biāo)函數(shù)轉(zhuǎn)為最小化 λ/2 * [(θ₁⁽⁵⁾)2 (θ₂⁽⁵⁾)2]，

有此會得出解 θ⁽⁵⁾ = [0? 0]^T

最后的預(yù)測結(jié)果是把所有電影評分為 0.

?

（2）解決方法：均值歸一化

對于原矩陣 Y，減去均值 μ，將得到的新 Y 矩陣作為樣本數(shù)據(jù)進(jìn)行學(xué)習(xí)，得到 Θ 和 X，在進(jìn)行預(yù)測. 在預(yù)測結(jié)果加上μ，即 XΘ^T μ. 如下圖：

含義：一無所知的新用戶，把電影的平均評分作為預(yù)測評分進(jìn)行推薦.