1宪萄、概述

“異常”通常是一個主觀的判斷榨惰，什么樣的數據被認為是“異嘲萦ⅲ”的，需要結合業(yè)務背景和環(huán)境來具體分析確定琅催。 ??實際上居凶，數據通常嵌入在大量的噪聲中，而我們所說的“異常值”通常指具有特定業(yè)務意義的那一類特殊的異常值藤抡。噪聲可以視作特性較弱的異常值侠碧，沒有被分析的價值。噪聲和異常之間杰捂、正常數據和噪聲之間的邊界都是模糊的舆床。異常值通常具有更高的離群程度分數值，同時也更具有可解釋性嫁佳。
??在普通的數據處理中挨队，我們常常需要保留正常數據，而對噪聲和異常值的特性則基本忽略蒿往。但在異常檢測中盛垦，我們弱化了“噪聲”和“正常數據”之間的區(qū)別，專注于那些具有有價值特性的異常值瓤漏。在基于相似度的方法中腾夯，主要思想是異常點的表示與正常點不同

2、基于距離的度量

基于距離的方法是一種常見的適用于各種數據域的異常檢測算法蔬充，它基于最近鄰距離來定義異常值蝶俱。 此類方法不僅適用于多維數值數據，在其他許多領域饥漫，例如分類數據榨呆，文本數據，時間序列數據和序列數據等方面也有廣泛的應用庸队。 ??基于距離的異常檢測有這樣一個前提假設积蜻，即異常點的 近鄰距離要遠大于正常點闯割。解決問題的最簡單方法是使用嵌套循環(huán)。 第一層循環(huán)遍歷每個數據竿拆，第二層循環(huán)進行異常判斷宙拉，需要計算當前點與其他點的距離，一旦已識別出多于 個數據點與當前點的距離在 之內丙笋，則將該點自動標記為非異常值谢澈。 這樣計算的時間復雜度為，當數據量比較大時不见，這樣計算是及不劃算的澳化。 因此，需要修剪方法以加快距離計算稳吮。

2.1 基于單元的方法

在基于單元格的技術中，數據空間被劃分為單元格井濒，單元格的寬度是閾值D和數據維數的函數灶似。具體地說，每個維度被劃分成寬度最多為 單元格瑞你。在給定的單元以及相鄰的單元中存在的數據點滿足某些特性酪惭，這些特性可以讓數據被更有效的處理。

image.png

以二維情況為例者甲，此時網格間的距離為 春感，需要記住的一點是，網格單元的數量基于數據空間的分區(qū)虏缸，并且與數據點的數量無關鲫懒。這是決定該方法在低維數據上的效率的重要因素，在這種情況下刽辙，網格單元的數量可能不多窥岩。 另一方面，此方法不適用于更高維度的數據宰缤。對于給定的單元格颂翼，其 鄰居被定義為通過最多1個單元間的邊界可從該單元到達的單元格的集合。請注意慨灭，在一個角上接觸的兩個單元格也是 鄰居朦乏。 鄰居是通過跨越2個或3個邊界而獲得的那些單元格。 上圖中顯示了標記為 的特定單元格及其 和 鄰居集氧骤。 顯然呻疹，內部單元具有8個 鄰居和40個 鄰居。 然后语淘，可以立即觀察到以下性質：

• 單元格中兩點之間的距離最多為 诲宇。
• 一個點與 鄰接點之間的距離最大為 际歼。
• 一個點與它的 鄰居(其中 > 2)中的一個點之間的距離至少為。

唯一無法直接得出結論的是 中的單元格姑蓝。 這表示特定單元中數據點的不確定性區(qū)域鹅心。 對于這些情況，需要明確執(zhí)行距離計算纺荧。 同時旭愧，可以定義許多規(guī)則，以便立即將部分數據點確定為異常值或非異常值宙暇。 規(guī)則如下：

• 如果一個單元格中包含超過 個數據點及其 鄰居输枯，那么這些數據點都不是異常值。
• 如果單元 及其相鄰 和 中包含少于 個數據點占贫，則單元A中的所有點都是異常值桃熄。

此過程的第一步是將部分數據點直接標記為非異常值（如果由于第一個規(guī)則而導致它們的單元格包含 個點以上）。 此外型奥，此類單元格的所有相鄰單元格僅包含非異常值瞳收。 為了充分利用第一條規(guī)則的修剪能力，確定每個單元格及其 鄰居中點的總和厢汹。 如果總數大于 螟深，則所有這些點也都標記為非離群值。

接下來烫葬，利用第二條規(guī)則的修剪能力界弧。 對于包含至少一個數據點的每個單元格 ，計算其中的點數及其 和 鄰居的總和搭综。 如果該數字不超過 垢箕，則將單元格 中的所有點標記為離群值。 此時设凹，許多單元可能被標記為異常值或非異常值舰讹。

對于此時仍未標記為異常值或非異常值的單元格中的數據點需要明確計算其 最近鄰距離。即使對于這樣的數據點闪朱，通過使用單元格結構也可以更快地計算出 個最近鄰的距離月匣。考慮到目前為止尚未被標記為異常值或非異常值的單元格奋姿。這樣的單元可能同時包含異常值和非異常值锄开。單元格 中數據點的不確定性主要存在于該單元格的 鄰居中的點集。無法通過規(guī)則知道 的 鄰居中的點是否在閾值距離 內称诗，為了確定單元 中數據點與其 鄰居中的點集在閾值距離 內的點數萍悴，需要進行顯式距離計算。對于那些在 和 中不超過 個且距離小于 的數據點，則聲明為異常值癣诱。需要注意计维，僅需要對單元 中的點到單元的鄰居中的點執(zhí)行顯式距離計算。這是因為已知 鄰居中的所有點到 中任何點的距離都小于 撕予，并且已知 中 的所有點與 上任何點的距離至少為 鲫惶。因此，可以在距離計算中實現額外的節(jié)省实抡。

2.2 基于索引的方法

對于一個給定數據集欠母，基于索引的方法利用多維索引結構(如 樹、 樹)來搜索每個數據對象 在半徑 范圍 內的相鄰點吆寨。設 是一個異常值在其 -鄰域內允許含有對象的最多個數赏淌，若發(fā)現某個數據對象 的 -鄰域內出現 甚至更多個相鄰點， 則判定對象 不是異常值啄清。該算法時間復雜度在最壞情況下為 其中 是數據集維數六水， 是數據集包含對象的個數。該算法在數據集的維數增加時具有較好的擴展性辣卒，但是時間復雜度的估算僅考慮了搜索時間缩擂，而構造索引的任務本身就需要密集復雜的計算量。

3添寺、基于密度的度量

基于密度的算法主要有局部離群因子(LocalOutlierFactor,LOF)，以及LOCI懈费、CLOF等基于LOF的改進算法计露。下面我們以LOF為例來進行詳細的介紹和實踐。

基于距離的檢測適用于各個集群的密度較為均勻的情況憎乙。在下圖中票罐，離群點B容易被檢出，而若要檢測出較為接近集群的離群點A泞边，則可能會將一些集群邊緣的點當作離群點丟棄该押。而LOF等基于密度的算法則可以較好地適應密度不同的集群情況。

image.png

那么阵谚，這個基于密度的度量值是怎么得來的呢蚕礼？還是要從距離的計算開始。類似k近鄰的思路梢什，首先我們也需要來定義一個“k-距離”奠蹬。

3.1 k-距離（k-distance(p)）：

對于數據集D中的某一個對象o，與其距離最近的k個相鄰點的最遠距離表示為k-distance(p)嗡午，定義為給定點p和數據集D中對象o之間的距離d(p,o)囤躁，滿足：

• 在集合D中至少有k個點 o'，其中，滿足
• 在集合D中最多有k-1個點o'狸演，其中言蛇，滿足

直觀一些理解，就是以對象o為中心宵距，對數據集D中的所有點到o的距離進行排序腊尚，距離對象o第k近的點p與o之間的距離就是k-距離。

image.png

3.2 k-鄰域（k-distance neighborhood）：

由k-距離消玄，我們擴展到一個點的集合——到對象o的距離小于等于k-距離的所有點的集合跟伏，我們稱之為k-鄰域：。

在二維平面上展示出來的話翩瓜，對象o的k-鄰域實際上就是以對象o為圓心受扳、k-距離為半徑圍成的圓形區(qū)域。就是說兔跌，k-鄰域已經從“距離”這個概念延伸到“空間”了勘高。

3.3 可達距離（reachability distance）：

有了鄰域的概念，我們可以按照到對象o的距離遠近坟桅，將數據集D內的點按照到o的距離分為兩類：

• 若在對象o的k-鄰域內华望，則可達距離就是給定點p關于對象o的k-距離；
• 若在對象o的k-鄰域外仅乓，則可達距離就是給定點p關于對象o的實際距離赖舟。

給定點p關于對象o的可達距離用數學公式可以表示為： 。
??這樣的分類處理可以簡化后續(xù)的計算夸楣，同時讓得到的數值區(qū)分度更高宾抓。

3.4 局部可達密度（local reachability density）：

我們可以將“密度”直觀地理解為點的聚集程度，就是說豫喧，點與點之間距離越短石洗，則密度越大。在這里紧显，我們使用數據集D中給定點p與對象o的k-鄰域內所有點的可達距離平均值的倒數（注意讲衫，不是導數）來定義局部可達密度。
??給定點p的局部可達密度計算公式為：

由公式可以看出孵班，這里是對給定點p進行度量涉兽，計算其鄰域內的所有對象o到給定點p的可達距離平均值。給定點p的局部可達密度越高重父，越可能與其鄰域內的點 屬于同一簇花椭；密度越低，越可能是離群點。

3.5 局部異常因子：

image.png

表示點p的鄰域內其他點的局部可達密度與點p的局部可達密度之比的平均數。如果這個比值越接近1，說明o的鄰域點密度差不多携茂，o可能和鄰域同屬一簇袋倔；如果這個比值小于1雕蔽，說明o的密度高于其鄰域點密度，o為密集點宾娜；如果這個比值大于1批狐，說明o的密度小于其鄰域點密度，o可能是異常點前塔。

最終得出的LOF數值嚣艇，就是我們所需要的離群點分數。在sklearn中有LocalOutlierFactor庫华弓，可以直接調用食零。下面來直觀感受一下LOF的圖像呈現效果。

LocalOutlierFactor庫可以用于對單個數據集進行無監(jiān)督的離群檢測寂屏，也可以基于已有的正常數據集對新數據集進行新穎性檢測贰谣。在這里我們進行單個數據集的無監(jiān)督離群檢測。

例：

Outlier detection

Outlier detection：當訓練數據中包含離群點迁霎，模型訓練時要匹配訓練數據的中心樣本吱抚，忽視訓練樣本的其他異常點

The Local Outlier Factor（LOF） algorithm is an unsupervised anomaly detection method which computes the local density deviation of a given data point with respect to its neighbors. It considers as outliers the samples that have a substantially lower density than their neighbors.

This example shows how to use LOF for outlier detection which is the default use case of this estimator in sklearn。Note that when LOF is used for outlier detection it has no predict, decision_function and score_samples methods.

The number of neighbors considered（parameter n_neighbors）is typically set 1) greater than the minimum number of samples a cluster has to contain, so that other samples can be local outliers relative to this cluster , and 2) smaller than the maximum number of close by samples that can potentially be local outliers. In practice, such informations are generally not available and taking n_neighbors=20 appears to work well in general.

鄰居的數量考慮（參數 n_neighbors通常設置為：

1） 大于一個集群包含最小數量的樣本考廉，以便其他樣本可以局部離群
2） 小于附加的最大數量樣本秘豹，可以局部離群值
　　在實踐中，這種信息一般是不可用的昌粤，n_neighbors=20 似乎實踐很好憋肖。

代碼：

#_*_coding:utf-8_*_
import numpy as np
from sklearn.neighbors import LocalOutlierFactor as LOF
import matplotlib.pyplot as plt
 
# generate train data
X_inliers = 0.3 * np.random.randn(100, 2)
X_inliers = np.r_[X_inliers + 2, X_inliers - 2]
 
 
# generate some outliers
X_outliers = np.random.uniform(low=-4, high=4, size=(20, 2))
X = np.r_[X_inliers, X_outliers]
 
n_outliers = len(X_outliers)  # 20
ground_truth = np.ones(len(X), dtype=int)
ground_truth[-n_outliers:] = -1
 
# fit the model for outlier detection
clf = LOF(n_neighbors=20, contamination=0.1)
 
# use fit_predict to compute the predicted labels of the training samples
y_pred = clf.fit_predict(X)
n_errors = (y_pred != ground_truth).sum()
X_scores = clf.negative_outlier_factor_
 
 
plt.title('Locla Outlier Factor (LOF)')
plt.scatter(X[:, 0], X[:, 1], color='k', s=3., label='Data points')
# plot circles with radius proportional to thr outlier scores
radius = (X_scores.max() - X_scores) / (X_scores.max() - X_scores.min())
plt.scatter(X[:, 0], X[:, 1], s=1000*radius, edgecolors='r',
    facecolors='none', label='Outlier scores')
plt.axis('tight')
plt.xlim((-5, 5))
plt.ylim((-5, 5))
plt.xlabel("prediction errors: %d"%(n_errors))
legend = plt.legend(loc='upper left')
legend.legendHandles[0]._sizes = [10]
legend.legendHandles[1]._sizes = [20]
plt.show()

image.png

更詳細的代碼及結果可以參考：https://www.cnblogs.com/wj-1314/p/14049195.html