Anomaly Detection
異常檢測算法經(jīng)常用于非監(jiān)督學(xué)習(xí)問題中升敲，有點類似于logistic regression.
examples
如上圖所示,紅色的樣本都是經(jīng)過測試被證明是質(zhì)量合格的引擎,如果有一個新的引擎稱作與質(zhì)量合格的樣本位置接近那么大概率也質(zhì)量合格,反之此樣本可能需要作更進(jìn)一步的安全測試.
量化來說就是如果就被認(rèn)為是異常樣本,反之正常.調(diào)節(jié)
的值類似調(diào)節(jié)logistic regression中的Threshold值.
Anomaly Detection還用于欺詐行為識別和manufacturing
Gaussian((Normal) distribution
正態(tài)分布
如果隨機(jī)變量X服從正態(tài)分布,記作X~,則其密度函數(shù)為:
其中
被稱為數(shù)學(xué)期望/期望值,被稱為方差,被稱為標(biāo)準(zhǔn)差
Anomaly detection algorithm
1.選擇你認(rèn)為可能會表明樣本是一個異常樣本的特征,用來篩選異常樣本候選者.
2.構(gòu)造{}樣本集合用來訓(xùn)練,上圖中的公式向量化可以寫作,類似
3.給定新樣本x,計算p(x)
符號表示乘積.,即
如果則x被認(rèn)為是異常樣本,值的選取下文會提到.
p(x)的函數(shù)圖類似于上圖中的3D圖片(特征值n=2).
Developing and evaluating an anomaly detection system
數(shù)據(jù)準(zhǔn)備階段,如下圖,需要
1.Training Set, unlabeled,由正常樣本構(gòu)成
2.Cross validation set, labeled,由正常樣本和異常樣本混合而成.
3.Test set, labeled,由正常樣本和異常樣本混合而成.
舉個例子,如下圖,不推薦粉色的樣本分組方法.一般來說Training/CV/Test分組的樣本最好不要重合,避免影響對算法的性能評估.
評估一個Anomaly detection algorithm算法的步驟如下:
1.使用training set的樣本數(shù)據(jù)訓(xùn)練出
2.對CV set的樣本進(jìn)行預(yù)測,選擇Fscore最高時對應(yīng)的
3.將以及用于Test set觀察算法表現(xiàn).
Anomaly detection vs. supervised learning
Anomaly detection算法實際上也是預(yù)測樣本的分類,飛機(jī)引擎是好的還是壞的;這筆交易是否有欺詐嫌疑等等.那既然如此為什么不使用logistic regression呢?
因為這兩個算法針對的場景有細(xì)微的差別,如下圖所示:
- Anomaly detection算法適用于異常樣本很少的情況下(通常是0-20),并且有大量的正常樣本(因為訓(xùn)練p(x)需要的是正常樣本).換句話說就是異常樣本太少以至于使用監(jiān)督學(xué)習(xí)算法無法很好的識別異常樣本的特征,但是因為有大量的正常樣本反而能很好的訓(xùn)練p(x),所以這種場景使用Anomaly detection更好.
-
Supervised learning適用于無論正常樣本還是異常樣本都很多的情況.
example
Choosing what features to use
如何為Anomaly Detection 算法選擇特征使得算法的性能更好呢?
需要思考以下兩個方面:
1.選擇的特征盡量滿足Gaussian distribution.
在octave中我們可以使用hist函數(shù)打印特征值的圖形,如果特征值的圖形不符合Gaussian distribution我們可以使用如下手段:
注意:我們可以對每個特征使用不同的方式變形.
2.選擇的特征需要盡可能可以區(qū)分正常/異常樣本.
一般來說我們會選擇特征值要么非常大要么非常小的特征去用于Anomaly Detection算法,更通常的做法是,選擇一些特征看看能不能很好的區(qū)分,如果不行,觀察本該是異常的樣本,在挑選新的特征加入算法.但是有時候根據(jù)現(xiàn)有的特征無法還是不能夠區(qū)分出異常樣本.
舉個例子,如下圖所示,你想找出在數(shù)據(jù)中心中出現(xiàn)特定錯誤的機(jī)器(cpu空轉(zhuǎn),死循環(huán)導(dǎo)致),依靠現(xiàn)有的4個特征值很難將異常機(jī)器和正常機(jī)器區(qū)分開(有可能真的是在執(zhí)行很耗cpu的任務(wù)),此時我們創(chuàng)建一個新特征值,這樣就能很明顯區(qū)分出正常機(jī)器和異常機(jī)器了.
Multivariate Gaussian Distribution
之前p(x)的計算方式(分別計算)沒法很好的區(qū)分CPU低Memory Use高,CPU高M(jìn)emory Use高兩個樣本,所以這里需要使用Multivariate Gaussian Distribution,新的p(x)如下:
以下是一些例子:
如果使用example4中間的例子可以區(qū)分CPU低Memory Use高,CPU高M(jìn)emory Use高兩種情況.
Anomaly detection using the multivariate Gaussian distribution
Gaussian distribution的p(x)是multivariate Gaussian distribution 的特例(是一個n*n的矩陣當(dāng)滿足除對角線之外的元素都為0的時候).
另一個發(fā)現(xiàn)是original model的輪廓圖始終是與坐標(biāo)軸對齊的.
- Original model
需要創(chuàng)建新的特征(現(xiàn)有特征值的組合)來更好的識別異常值.
計算成本低(適用于大規(guī)模輸入,like n=10000)
training size很小也ok - Multivariate Gaussian
無需考慮新建特征值
計算成本高,求的inverse
必須滿足m>n,否則
Recommender System
Content-based recommender systems
基于內(nèi)容的推薦系統(tǒng),以推薦電影為例,根據(jù)用戶的打分?jǐn)?shù)據(jù)和這些分?jǐn)?shù)對應(yīng)的電影特征去構(gòu)造hypothesis去預(yù)測該用戶對沒打過分?jǐn)?shù)的電影的打分,然后可以根據(jù)分高的推薦.
上圖中的可以理解為用戶的對不同類型電影的喜好.
,這其實是一個linear regression,帶入linear regression的cost function可得recommender system用戶j的cost function如上.
Collaborative filtering
協(xié)同過濾的動機(jī)在于(還是拿預(yù)測電影評分舉例子):電影太多了,如果需要工作人員一個一個去看完然后給出每個電影的特征值太慢而且不現(xiàn)實.所以我們這樣想,如果我們已知用戶對于電影的喜好(),并且知道用戶對于電影的評分(y(i,j)),那么我們可以根據(jù)這些來倒推電影的特征(
).
如上圖所示求出最優(yōu)的X.
Collaborative filtering的思想就是隨機(jī)初始化用戶的偏好,根據(jù)用戶評分去估算電影特征X,再根據(jù)X和評分去優(yōu)化,如此往復(fù),雖然沒給出證明,但是這樣做最后和X都會收斂.
Collaborative filtering algorithm
前一節(jié)中的先優(yōu)化再優(yōu)化X的反復(fù)的過程可以合并在一起同時進(jìn)行,cost fucntion 如上.
完整的Collaborative filtering algorithm步驟如上.
注意,這里不需要
Vectorization:Low rank matrix factorization
X是的矩陣,可以看成是影片的樣本,每一行代表一部電影,每一列代表電影的特征,是的矩陣,可以看作用戶的樣本,每一行代表一個用戶,每一列代表用戶對電影特征的愛好程度.
有時候我們要根據(jù)用戶喜愛的電影類型推薦相似的電影給他,當(dāng)計算出用戶喜歡的電影的特征值時,遍歷所有電影,當(dāng)最小時對應(yīng)的電影j就是和i最類似的電影.
Implementational detail:Mean normalization
對于從來沒有打?qū)﹄娪按蜻^分的用戶,在使用Collaborative filtering algorithm時,cost function的第一項永遠(yuǎn)為0,那么在梯度下降算法執(zhí)行的過程中對于上圖中的Eve用戶來說,傾向于把偏好都設(shè)置為0,如果使用去預(yù)測Eve的評分那將全部是0,我們沒法給Eve做推薦,為了解決這種問題,我們需要使用Mean normalization,如下圖所示,對于Y的每一行求平均值構(gòu)成向量,再做類似于的操作,此時對于用戶j在電影i上的打分則是 ,換句話說就是對于沒有做過任何評分的用戶,將他對電影的評分設(shè)置為該電影的平均分.
