異常值檢測(cè)（也稱為異常檢測(cè)）是機(jī)器學(xué)習(xí)中查找具有與期望非常不同的行為的數(shù)據(jù)對(duì)象的過(guò)程。這些對(duì)象稱為離群值或異常。

最有趣的對(duì)象是那些與普通對(duì)象明顯不同的對(duì)象。離群值不是由與其他數(shù)據(jù)相同的機(jī)制生成的。

異常檢測(cè)在許多應(yīng)用中很重要，例如：

•  財(cái)務(wù)數(shù)據(jù)欺詐
•  通信網(wǎng)絡(luò)中的入侵
•  假新聞和錯(cuò)誤信息
•  醫(yī)療分析
•  行業(yè)損壞檢測(cè)
•  安全和監(jiān)視
•  等等

離群值檢測(cè)和聚類(lèi)分析是兩個(gè)高度相關(guān)的任務(wù)。聚類(lèi)在機(jī)器學(xué)習(xí)數(shù)據(jù)集中查找多數(shù)模式并相應(yīng)地組織數(shù)據(jù)，而離群值檢測(cè)嘗試捕獲那些與多數(shù)模式大不相同的異常情況。

在本文中，我將介紹異常值檢測(cè)的基本方法，并重點(diǎn)介紹一類(lèi)Proximity-based算法方法。我還將提供LOF算法的代碼實(shí)現(xiàn)。

[[243914]]

異常值和噪聲數(shù)據(jù)

首先在機(jī)器學(xué)習(xí)中，您需要將離群值與噪聲數(shù)據(jù)區(qū)分開(kāi)來(lái)。

應(yīng)用離群檢測(cè)時(shí)應(yīng)去除噪音。它可能會(huì)扭曲正常對(duì)象并模糊正常對(duì)象和離群值之間的區(qū)別。它可能有助于隱藏離群值并降低離群值檢測(cè)的有效性。例如，如果用戶考慮購(gòu)買(mǎi)他過(guò)去經(jīng)常購(gòu)買(mǎi)的更昂貴的午餐，則應(yīng)將此行為視為“噪音交易”，如“random errors”或“variance”。

異常值的類(lèi)型

通常，異常值可以分為三類(lèi)，即全局異常值，上下文（或條件）異常值和集體異常值。

•  全局異常值 - 對(duì)象顯著偏離數(shù)機(jī)器學(xué)習(xí)據(jù)集的其余部分
•  上下文異常值 - 對(duì)象根據(jù)選定的上下文顯著偏離。例如，28⁰C是莫斯科冬季的異常值，但在另一個(gè)背景下不是異常值，28⁰C不是莫斯科夏季的異常值。
•  集合異常值 - 即使單個(gè)數(shù)據(jù)對(duì)象可能不是異常值，數(shù)據(jù)對(duì)象的子集也會(huì)顯著偏離整個(gè)機(jī)器學(xué)習(xí)數(shù)據(jù)集。例如，短期內(nèi)小方的同一股票的大量交易可以被視為市場(chǎng)操縱的證據(jù)。

集合異常值

通常，數(shù)據(jù)集可以包含不同類(lèi)型的異常值，并且同時(shí)可以屬于不止一種類(lèi)型的異常值。

異常值檢測(cè)方法

文獻(xiàn)中涵蓋了許多異常值檢測(cè)方法，并在實(shí)踐中使用。首先，異常值檢測(cè)方法根據(jù)用于分析的數(shù)據(jù)樣本是否與領(lǐng)域?qū)＜姨峁┑臉?biāo)簽一起給出，該標(biāo)簽可用于構(gòu)建異常值檢測(cè)模型。其次，可以根據(jù)關(guān)于正常對(duì)象與異常值的假設(shè)將方法分成組。

如果可以獲得正常和/或異常對(duì)象的專(zhuān)家標(biāo)記示例，則可以使用它們來(lái)構(gòu)建異常值檢測(cè)模型。使用的方法可以分為監(jiān)督方法，半監(jiān)督方法和無(wú)監(jiān)督方法。

監(jiān)督方法

我們將離群值檢測(cè)建模為分類(lèi)問(wèn)題。由領(lǐng)域?qū)＜覚z查的樣本用于訓(xùn)練和測(cè)試。

挑戰(zhàn)：

•  類(lèi)不平衡。也就是說(shuō)，異常值的數(shù)量通常遠(yuǎn)小于普通對(duì)象的數(shù)量?？梢允褂锰幚聿黄胶忸?lèi)的方法，例如過(guò)采樣。
•  捕獲盡可能多的異常值，即，召回比準(zhǔn)確性更重要（即，不將正常對(duì)象誤標(biāo)記為異常值）

無(wú)監(jiān)督的方法

在某些應(yīng)用程序方案中，標(biāo)記為“正常”或“異常”的對(duì)象不可用。因此，必須使用無(wú)監(jiān)督學(xué)習(xí)方法。無(wú)監(jiān)督異常值檢測(cè)方法做出了一個(gè)隱含的假設(shè)：正常對(duì)象在某種程度上是“聚類(lèi)的”。換句話說(shuō)，無(wú)監(jiān)督異常值檢測(cè)方法期望正常對(duì)象比異常值更頻繁地遵循模式。

挑戰(zhàn)：

•     普通對(duì)象可能不共享任何強(qiáng)模式，但是集合異常值可能在小區(qū)域中具有高相似性
•     如果正?；顒?dòng)是多樣的并且不屬于高質(zhì)量聚類(lèi)，則無(wú)監(jiān)督方法可能具有高誤報(bào)率并且可能使許多實(shí)際異常值不受影響。

最新的無(wú)監(jiān)督方法開(kāi)發(fā)了智能想法，直接解決異常值而無(wú)需明確檢測(cè)聚類(lèi)。

半監(jiān)督方法

在許多應(yīng)用中，雖然獲得一些標(biāo)記的示例是可行的，但是這種標(biāo)記的示例的數(shù)量通常很小。如果有一些標(biāo)記的普通對(duì)象可用：

•  使用帶標(biāo)簽的示例和鄰近的未標(biāo)記對(duì)象來(lái)訓(xùn)練普通對(duì)象的模型
•  那些不適合普通對(duì)象模型的對(duì)象被檢測(cè)為異常值
•  如果只有一些標(biāo)記的異常值可用，則少量標(biāo)記的異常值可能無(wú)法很好地覆蓋可能的異常值。

統(tǒng)計(jì)方法

統(tǒng)計(jì)方法（也稱為基于模型的方法）假設(shè)正常數(shù)據(jù)遵循一些統(tǒng)計(jì)模型（隨機(jī)模型）。我們的想法是學(xué)習(xí)適合給定數(shù)據(jù)集的生成模型，然后將模型的低概率區(qū)域中的對(duì)象識(shí)別為異常值。

參數(shù)方法

參數(shù)方法假設(shè)通過(guò)參數(shù)θ的參數(shù)分布生成正常數(shù)據(jù)對(duì)象。參數(shù)分布f（x， θ ）的概率密度函數(shù)給出了通過(guò)分布生成對(duì)象x的概率。該值越小，x越可能是異常值。

正常對(duì)象出現(xiàn)在隨機(jī)模型的高概率區(qū)域中，而低概率區(qū)域中的對(duì)象是異常值。

統(tǒng)計(jì)方法的有效性在很大程度上取決于分配的假設(shè)。

例如，考慮具有正態(tài)分布的單變量數(shù)據(jù)。我們將使用最大似然法檢測(cè)異常值。

估計(jì)參數(shù)μ和σ的最大似然法

取μ和σ²的導(dǎo)數(shù)并求解所得的一階條件系統(tǒng)導(dǎo)致以下最大似然估計(jì)

μ和σ²的最大似然估計(jì)

看下Python示例:

 

import numpy as np  
avg_temp = np.array([24.0, 28.9, 28.9, 29.0, 29.1, 29.1, 29.2, 29.2, 29.3, 29.4])  mean = avg_temp.mean() 
 
std = avg_temp.std()  
sigma = std^2  
print (mean, std, sigma) //28.61 1.54431214461 2.3849 

最偏離的值是24⁰，遠(yuǎn)離平均值4.61。我們知道μ+/-3σ區(qū)域在正態(tài)分布假設(shè)下包含97％的數(shù)據(jù)。因?yàn)?.61 / 1.54> 3我們認(rèn)為24⁰是異常值。

我們還可以使用另一種統(tǒng)計(jì)方法，稱為Gribbs測(cè)試并計(jì)算z得分。

s - 標(biāo)準(zhǔn)偏差

但是我們很少使用只有一個(gè)屬性的數(shù)據(jù)。涉及兩個(gè)或多個(gè)屬性的數(shù)據(jù)稱為多變量。這些方法的核心思想是將多變量數(shù)據(jù)轉(zhuǎn)換為單變量異常值檢測(cè)問(wèn)題。

流行的方法之一是 ² -statistics。

Oi - 第i維度中O的值。Ei - 所有對(duì)象中第i維的平均值，n維度。

如果χ²-大，則對(duì)象是異常值。

參數(shù)模型的主要缺點(diǎn)是在許多情況下，數(shù)據(jù)分布可能是未知的。

例如，如果我們有兩個(gè)大的集合，那么關(guān)于正態(tài)分布的假設(shè)就不會(huì)很好。

相反，我們假設(shè)正常數(shù)據(jù)對(duì)象由多個(gè)正態(tài)分布Θ（μ1，σ1）和Θ（μ2，σ2）生成，并且對(duì)于數(shù)據(jù)集中的每個(gè)對(duì)象o，我們計(jì)算由分布的混合生成的概率。

Pr（o |Θ1，Θ2）=fΘ1（o）+fΘ2（o）

其中fΘ1（o） - Θ1和Θ2的概率密度函數(shù)。要學(xué)習(xí)參數(shù)μ和σ，我們可以使用EM算法。

非參數(shù)方法

在用于離群值檢測(cè)的非參數(shù)方法中，從輸入數(shù)據(jù)中學(xué)習(xí)“正常數(shù)據(jù)”模型，而不是先驗(yàn)地假設(shè)。非參數(shù)方法通常對(duì)數(shù)據(jù)做出較少的假設(shè)，因此可適用于更多場(chǎng)景。作為一個(gè)例子，我們可以使用直方圖。

在最簡(jiǎn)單的方法中，如果對(duì)象在一個(gè)直方圖箱中失敗，則認(rèn)為是正常的。缺點(diǎn) - 很難選擇垃圾箱尺寸。

Proximity-based算法

給定特征空間中的一組對(duì)象，可以使用距離度量來(lái)量化對(duì)象之間的相似性。直覺(jué)上，遠(yuǎn)離其他對(duì)象的對(duì)象可被視為異常值。Proximity-based方法假設(shè)異常值對(duì)象與其最近鄰居的接近度明顯偏離對(duì)象與數(shù)據(jù)集中的大多數(shù)其他對(duì)象的接近度。

Proximity-based算法可以分為基于距離（如果對(duì)象是沒(méi)有足夠的點(diǎn)，則對(duì)象是異常值）和基于密度的方法（如果對(duì)象的密度相對(duì)遠(yuǎn)低于其鄰居，則對(duì)象是異常值）

基于密度

基于距離的離群值檢測(cè)方法參考對(duì)象的鄰域，該對(duì)象由給定半徑定義。如果對(duì)象的鄰域沒(méi)有足夠的其他點(diǎn)，則該對(duì)象被視為異常值。

閾值的距離，可以定義為對(duì)象的合理鄰域。對(duì)于每個(gè)對(duì)象，我們可以找到對(duì)象的合理neighbours數(shù)量。

令r（r> 0）為距離閾值，π （0 <π<1）為分?jǐn)?shù)閾值。對(duì)象o是DB（r， π ）

DIST -距離測(cè)量

需要O(n²)時(shí)間。

挖掘基于距離的異常值的算法：

•  基于索引的算法
•  嵌套循環(huán)算法
•  基于單元的算法

基于密度的方法

基于密度的離群點(diǎn)檢測(cè)方法研究對(duì)象的密度及其相鄰對(duì)象的密度。在這里，如果一個(gè)對(duì)象的密度相對(duì)于其相鄰對(duì)象的密度要低得多，那么這個(gè)對(duì)象就是一個(gè)離群值。

許多真實(shí)世界的數(shù)據(jù)集展示了一個(gè)更復(fù)雜的結(jié)構(gòu)，其中對(duì)象可能被視為與其局部neighbours相關(guān)的離群值，而不是與全局?jǐn)?shù)據(jù)分布相關(guān)的離群值。

考慮上面的例子，基于距離的方法能夠檢測(cè)到o3，但是對(duì)于o1和o2，它并不那么明顯。

基于密度的想法是我們需要將對(duì)象周?chē)拿芏扰c其局部neighbours周?chē)拿芏冗M(jìn)行比較?；诿芏鹊碾x群值檢測(cè)方法的基本假設(shè)是，非離群對(duì)象周?chē)拿芏阮?lèi)似于其neighbours周?chē)拿芏?，而離群對(duì)象周?chē)拿芏扰c其鄰近對(duì)象周?chē)拿芏让黠@不同。

dist_k(o)——對(duì)象o與k近鄰之間的距離。o的k-distance鄰域包含所有到o的距離不大于o的k-th距離dist_k(o)

我們可以用Nk(o)到o的平均距離作為o的局部密度的度量，如果o有非常接近的鄰域o'，使得dist(o,o')非常小，那么距離度量的統(tǒng)計(jì)波動(dòng)可能會(huì)非常高。為了克服這個(gè)問(wèn)題，我們可以通過(guò)添加平滑效果切換到以下可達(dá)距離測(cè)量。

k是用戶指定的參數(shù)，用于控制平滑效果。基本上，k指定要檢查的最小鄰域以確定對(duì)象的局部密度?？蛇_(dá)距離是不對(duì)稱的。

對(duì)象o的局部可達(dá)性密度是

我們計(jì)算對(duì)象的局部可達(dá)性密度，并將其與其相鄰的可比性密度進(jìn)行比較，以量化對(duì)象被視為異常值的程度。

局部異常因子是o的局部可達(dá)性密度與o的 k近鄰的比率的平均值。o的局部可達(dá)性密度越低，k的最近鄰點(diǎn)的局部可達(dá)性密度越高，LOF值越高。這恰好捕獲了局部密度相對(duì)較低的局部密度相對(duì)較低的局部異常值。它的k近鄰。

LOF算法

基于data.csv中的點(diǎn)擊流事件頻率模式，我們將應(yīng)用LOF算法來(lái)計(jì)算每個(gè)點(diǎn)的LOF，并具有以下初始設(shè)置：

•  k = 2并使用曼哈頓距離。
•  k = 3并使用歐幾里德距離。

結(jié)果，我們將找到5個(gè)異常值及其LOF_k（o）

可以從github 存儲(chǔ)庫(kù)下載數(shù)據(jù)（https://github.com/zkid18/Machine-Learning-Algorithms）

Python實(shí)現(xiàn)如下： 

import pandas as pd  
import seaborn as sns  
from scipy.spatial.distance import pdist, squareform   
data_input = pd.read_csv('../../data/clikstream_data.csv')   
#Reachdist function  
def reachdist(distance_df, observation, index):  
 return distance_df[observation][index]   
 #LOF algorithm implementation from scratch  
def LOF_algorithm(data_input, distance_metric = "cityblock", p = 5):  
 distances = pdist(data_input.values, metric=distance_metric)  
 dist_matrix = squareform(distances)  
 distance_df = pd.DataFrame(dist_matrix)   
 k = 2 if distance_metric == "cityblock" else 3   
 observations = distance_df.columns  
 lrd_dict = {}  
 n_dist_index = {}  
 reach_array_dict = {}   
 for observation in observations:  
 dist = distance_df[observation].nsmallest(k+1).iloc[k]  
 indexes = distance_df[distance_df[observation] <= dist].drop(observation).index  
 n_dist_index[observation] = indexes   
 reach_dist_array = []  
 for index in indexes:  
 #make a function reachdist(observation, index)  
 dist_between_observation_and_index = reachdist(distance_df, observation, index)  
 dist_index = distance_df[index].nsmallest(k+1).iloc[k]  
 reach_dist = max(dist_index, dist_between_observation_and_index)  
 reach_dist_array.append(reach_dist)  
 lrd_observation = len(indexes)/sum(reach_dist_array)  
 reach_array_dict[observation] = reach_dist_array  
 lrd_dict[observation] = lrd_observation   
 #Calculate LOF  
 LOF_dict = {}  
 for observation in observations:  
 lrd_array = []  
 for index in n_dist_index[observation]:  
 lrd_array.append(lrd_dict[index])  
 LOF = sum(lrd_array)*sum(reach_array_dict[observation])/np.square(len(n_dist_index[observation]))  
 LOF_dict[observation] = LOF   
 return sorted(LOF_dict.items(), key=lambda x: x[1], reverse=True)[:p]   
LOF_algorithm(data_input, p = 5)  
# [(19, 11.07),  
# (525, 8.8672286617492091),  
# (66, 5.0267857142857144),  
# (638, 4.3347272196829723),  
# (177, 3.6292633292633294)]   
LOF_algorithm(data_input, p = 5, distance_metric = 'euclidean')  
# [(638, 3.0800716645705695),  
# (525, 3.0103162562616288),  
# (19, 2.8402916620868903),  
# (66, 2.8014102661691211),  
# (65, 2.6456528412196416)]