異常檢測——基于相似度的方法

基于距離的度量
基于密度的度量

1.概述

“異常”通常是一個(gè)主觀的判斷，什么樣的數(shù)據(jù)被認(rèn)為是“異?！钡模枰Y(jié)合業(yè)務(wù)背景和環(huán)境來具體分析確定。實(shí)際上，數(shù)據(jù)通常嵌入在大量的噪聲中，而我們所說的”異常值“通常指具有特定業(yè)務(wù)意義的那一類特殊的異常值。噪聲可以視作特性較弱的異常值，沒有被分析的價(jià)值。

在普通的數(shù)據(jù)處理中，我們通常保留正常的數(shù)據(jù)，而對噪聲和異常值的特性則基本忽略。但在異常檢測中，我們?nèi)趸恕霸肼暋焙汀罢?shù)據(jù)”之間的區(qū)別，專注于那些具有有價(jià)值特性的異常值。在基于相似度的方法中，主要思想是異常點(diǎn)與正常點(diǎn)不同。

2、基于距離的度量

基于距離的方法是一種常見的異常檢測算法，它基于最鄰距離來定義異常值。此類方法不僅適用于多維數(shù)值數(shù)據(jù)，在其他領(lǐng)域，例如分類數(shù)據(jù)，文本數(shù)據(jù)，時(shí)間序列數(shù)據(jù)序列數(shù)據(jù)也有廣泛的應(yīng)用。

基于距離的異常檢測有這樣一個(gè)前提假設(shè)，即異常點(diǎn)的 $k$ 近鄰距離要遠(yuǎn)大于正常點(diǎn)。解決問題的最簡單的方法是使用嵌套循環(huán)。第一層循環(huán)遍歷每個(gè)數(shù)據(jù)，第二層循環(huán)進(jìn)行異常判斷，需要計(jì)算當(dāng)前點(diǎn)與其他點(diǎn)的距離，一旦已識別出多余 $k$ 個(gè)數(shù)據(jù)點(diǎn)與當(dāng)前點(diǎn)的距離在 $D$ 之內(nèi)，則將該點(diǎn)自動標(biāo)記為非異常值。這樣計(jì)算的時(shí)間復(fù)雜度為 $O(N^{2})$ ,當(dāng)數(shù)據(jù)量較大時(shí)，這樣計(jì)算并不劃算。因此需要修剪方法以加快距離計(jì)算。

2.1基于單元的方法

在基于單元格的技術(shù)中，數(shù)據(jù)空間被劃分為單元格，單元格的寬度是閾值D和數(shù)據(jù)維度數(shù)的函數(shù)。具體地說，每個(gè)維度被劃分成寬度最多為 $\frac{D}{{2\cdot\sqrt d }}$ 單元格。在給定的單元以及相鄰的單元中存在的數(shù)據(jù)點(diǎn)滿足某些特性，這些特性可以讓數(shù)據(jù)被更有效的處理

以二維情況為例，此時(shí)網(wǎng)格間的距離為 $\frac{D}{{2\cdot\sqrt d}}$ ，需要記住的一點(diǎn)是，網(wǎng)格單元的數(shù)量基于數(shù)據(jù)空間的分區(qū)，并且與數(shù)據(jù)的數(shù)量點(diǎn)無關(guān)。這是決定該方法在低維數(shù)據(jù)上的效率的重要因素，在這種情況下，網(wǎng)格單元的數(shù)量可能不多。另一方面，此方法不適用于更高維的數(shù)據(jù)。對于給定的單元格，其 $L_{1}$ 鄰居被定義為通過最多1個(gè)單元間的邊界可從該單元到達(dá)的單元格的集合。請注意，在一個(gè)角上接觸的兩個(gè)單元格也是 $L_{1}$ 鄰居。 $L_{2}$ 鄰居是通過跨越2個(gè)或者3個(gè)邊界而獲得的那些單元格。上圖中顯示了標(biāo)記為 $X$ 的特定單元格及其 $L_{1}$ 和 $L_{2}$ 鄰居集。顯然，內(nèi)部單元具有8個(gè) $L_{1}$ 鄰居和40個(gè) $L_{2}$ 鄰居。然后，可以立即觀察到以下的幾種性質(zhì)：

單元格中兩點(diǎn)之間的距離最多為 $D/2$
一個(gè)點(diǎn)與 $L_{1}$ 鄰接點(diǎn)之間的距離最大為 $D$
一個(gè)點(diǎn)與它的 $Lr$ 鄰居（其中 $r$ >2）中的一個(gè)點(diǎn)之間的距離至少為 $D$

此過程的第一步是將部分?jǐn)?shù)據(jù)點(diǎn)直接標(biāo)記為非異常值（如果由于第一個(gè)規(guī)則而導(dǎo)致他們的單元格包含 $k$ 個(gè)點(diǎn)以上）。此外，此類單元格的所有相鄰單元格僅包含非異常值。為了充分利用第一條規(guī)則的修剪能力，確定每個(gè)單元格及其 $L_{1}$ 鄰居中點(diǎn)的總和。如果總數(shù)大于 $k$ ,則這些點(diǎn)也都標(biāo)記為非離群點(diǎn)。

接下來，利用第二條規(guī)則的修剪能力。對于包含至少一個(gè)數(shù)據(jù)點(diǎn)的每個(gè)單元格 $A$ ，計(jì)算其中的點(diǎn)數(shù)及其 $L_{1}$ 和 $L_{2}$ 鄰居的總和。如果該數(shù)字不超過 $k$ ，則將單元格 $A$ 中的所有點(diǎn)標(biāo)記為離群值。此時(shí)，許多單元可能被標(biāo)記為異常值或非異常值。

對于此時(shí)仍未標(biāo)記為異常值或非異常值的單元格中的數(shù)據(jù)點(diǎn)需要明確計(jì)算其 $k$ 最近鄰距離。即使對于這樣的數(shù)據(jù)點(diǎn)，通過使用單元格結(jié)構(gòu)也可以更快地計(jì)算出 $k$ 個(gè)最近鄰的距離?？紤]到目前為止尚未被標(biāo)記為異常值或非異常值的單元格 $A$ 。這樣的單元可能同時(shí)包含異常值和非異常值。單元格 $A$ 中數(shù)據(jù)點(diǎn)的不確定性主要存在于該單元格的 $L_{2}$ 鄰居中的點(diǎn)集。無法通過規(guī)則知道 $A$ 的 $L_{2}$ 鄰居中的點(diǎn)是否在閾值距離 $D$ 內(nèi)，為了確定單元 $A$ 中數(shù)據(jù)點(diǎn)與其 $L_{2}$ 鄰居中的點(diǎn)集在閾值距離 $D$ 內(nèi)的點(diǎn)數(shù)，需要進(jìn)行顯式距離計(jì)算。對于那些在 $L_{1}$ 和 $L_{2}$ 中不超過 $k$ 個(gè)且距離小于 $D$ 的數(shù)據(jù)點(diǎn)，則聲明為異常值。需要注意，僅需要對單元 $A$ 中的點(diǎn)到單元 $A$ 的 $L_{2}$ 鄰居中的點(diǎn)執(zhí)行顯式距離計(jì)算。這是因?yàn)橐阎? $L_{1}$ 鄰居中的所有點(diǎn)到 $A$ 中任何點(diǎn)的距離都小于 $D$ ，并且已知 $Lr$ 中 $(r> 2)$ 的所有點(diǎn)與 $A$ 上任何點(diǎn)的距離至少為 $D$ 。因此，可以在距離計(jì)算中實(shí)現(xiàn)額外的節(jié)省。

2.2基于索引的方法

對于一個(gè)給定數(shù)據(jù)集，基于索引的方法利用多維索引結(jié)構(gòu)(如 $\mathrm{R}$ 樹、 $k-d$ 樹)來搜索每個(gè)數(shù)據(jù)對象 $A$ 在半徑 $D$ 范圍內(nèi)的相鄰點(diǎn)。設(shè) $M$ 是一個(gè)異常值在其 $D$ -鄰域內(nèi)允許含有對象的最多個(gè)數(shù)，若發(fā)現(xiàn)某個(gè)數(shù)據(jù)對象 $A$ 的 $D$ -鄰域內(nèi)出現(xiàn) $M+1$ 甚至更多個(gè)相鄰點(diǎn)，則判定對象 $A$ 不是異常值。該算法時(shí)間復(fù)雜度在最壞情況下為 $O\left(k N^{2}\right),$ 其中 $k$ 是數(shù)據(jù)集維數(shù)， $N$ 是數(shù)據(jù)集包含對象的個(gè)數(shù)。該算法在數(shù)據(jù)集的維數(shù)增加時(shí)具有較好的擴(kuò)展性，但是時(shí)間復(fù)雜度的估算僅考慮了搜索時(shí)間，而構(gòu)造索引的任務(wù)本身就需要密集復(fù)雜的計(jì)算量。

2.3基于密度的方法

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

基于距離的檢測適用于各個(gè)集群的密度較為均勻的情況。在下圖中，離群點(diǎn)B容易被檢出，而若要檢測出較為接近集群的離群點(diǎn)A，則可能會將一些集群邊緣的點(diǎn)當(dāng)作離群點(diǎn)丟棄。而LOF等基于密度的算法則可以較好地適應(yīng)密度不同的集群情況。

那么，這個(gè)基于密度的度量值是怎么得來的呢？還是要從距離的計(jì)算開始。類似k近鄰的思路，首先我們也需要來定義一個(gè)“k-距離”。

3.1 k-距離(k-distance(p)):

對于數(shù)據(jù)集D中的某一個(gè)對象o，與其距離最近的k個(gè)相鄰點(diǎn)的最遠(yuǎn)距離表示為k-distance(p)，定義為給定點(diǎn)p和數(shù)據(jù)集D中對象o之間的距離d(p,o)，滿足：

在集合D中至少有k個(gè)點(diǎn) o'，其中 $o'∈D{p}$ ，滿足 $d(p,o')≤d(p,o)$
在集合D中最多有k-1個(gè)點(diǎn)o'，其中 $o'∈D{p}$ ，滿足 $d(p,o;)<d(p,o)$
??直觀一些理解，就是以對象o為中心，對數(shù)據(jù)集D中的所有點(diǎn)到o的距離進(jìn)行排序，距離對象o第k近的點(diǎn)p與o之間的距離就是k-距離。

3.2 k-領(lǐng)域（k-distance neighborhood）:

由k-距離，我們擴(kuò)展到一個(gè)點(diǎn)的集合——到對象o的距離小于等于k-距離的所有點(diǎn)的集合，我們稱之為k-鄰域： $N_{k ? d i s t a n c e ( p )}( P ) = { q ∈ D \backslash{ p } ∣ d ( p , q ) ≤ k ? d i s t a n c e ( p )}$ 。

在二維平面上展示出來的話，對象o的k-鄰域?qū)嶋H上就是以對象o為圓心、k-距離為半徑圍成的圓形區(qū)域。就是說，k-鄰域已經(jīng)從“距離”這個(gè)概念延伸到“空間”了。

3.3可達(dá)距離（reachablity distance）:

有了鄰域的概念，我們可以按照到對象o的距離遠(yuǎn)近，將數(shù)據(jù)集D內(nèi)的點(diǎn)按照到o的距離分為兩類：

若 $p_i$ 在對象o的k-鄰域內(nèi)，則可達(dá)距離就是給定點(diǎn)p關(guān)于對象o的k-距離；
若 $p_i$ 在對象o的k-鄰域外，則可達(dá)距離就是給定點(diǎn)p關(guān)于對象o的實(shí)際距離。

給定點(diǎn)p關(guān)于對象o的可達(dá)距離用數(shù)學(xué)公式可以表示為： $r e a c h?d i s t_ k ( p , o ) = m a x {k?distance( o ) , d ( p , o )}$ 。
這樣的分類處理可以簡化后續(xù)的計(jì)算，同時(shí)讓得到的數(shù)值區(qū)分度更高。

3.4局部可達(dá)密度（local reachability density）：

我們可以將“密度”直觀地理解為點(diǎn)的聚集程度，就是說，點(diǎn)與點(diǎn)之間距離越短，則密度越大。在這里，我們使用數(shù)據(jù)集D中給定點(diǎn)p與對象o的k-鄰域內(nèi)所有點(diǎn)的可達(dá)距離平均值的倒數(shù)（注意，不是導(dǎo)數(shù)）來定義局部可達(dá)密度。
??給定點(diǎn)p的局部可達(dá)密度計(jì)算公式為： $lrd_{MinPts}(p)=1/(\frac {\sum\limits_{o∈N_{MinPts}(p)} reach-dist_{MinPts}(p,o)} {\left\vert N_{MinPts}(p) \right\vert})$

由公式可以看出，這里是對給定點(diǎn)p進(jìn)行度量，計(jì)算其鄰域內(nèi)的所有對象o到給定點(diǎn)p的可達(dá)距離平均值。給定點(diǎn)p的局部可達(dá)密度越高，越可能與其鄰域內(nèi)的點(diǎn) 屬于同一簇；密度越低，越可能是離群點(diǎn)。

3.5 局部異常因子：

image.png

表示點(diǎn)p的鄰域 $N_k(p)$ 內(nèi)其他點(diǎn)的局部可達(dá)密度與點(diǎn)p的局部可達(dá)密度之比的平均數(shù)。如果這個(gè)比值越接近1，說明o的鄰域點(diǎn)密度差不多，o可能和鄰域同屬一簇；如果這個(gè)比值小于1，說明o的密度高于其鄰域點(diǎn)密度，o為密集點(diǎn)；如果這個(gè)比值大于1，說明o的密度小于其鄰域點(diǎn)密度，o可能是異常點(diǎn)。

最終得出的LOF數(shù)值，就是我們所需要的離群點(diǎn)分?jǐn)?shù)。在sklearn中有LocalOutlierFactor庫，可以直接調(diào)用。下面來直觀感受一下LOF的圖像呈現(xiàn)效果。

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

import numpy as np 
import panas as pd
import matplotlib.pyplot as plt
import seabron as sns
from sklearn.neighbors import LocalOutlierFactor

plt.rcParams['font.sans-serif'] = ['SimHei']
plt.rcParams['axes.unicode_minus']=False
pd.set_option('display.max_columns', None)
pd.set_option('display.max_rows', None)

首先構(gòu)造一個(gè)含有集群和離群點(diǎn)的數(shù)據(jù)集。該數(shù)據(jù)集包含兩個(gè)密度不同的正態(tài)分布集群和一些離群點(diǎn)。但是，這里我們手工對數(shù)據(jù)點(diǎn)的標(biāo)注其實(shí)是不準(zhǔn)確的，可能有一些隨機(jī)點(diǎn)會散落在集群內(nèi)部，而一些集群點(diǎn)由于正態(tài)分布的特性，會與其余點(diǎn)的距離相對遠(yuǎn)一些。在這里我們無法進(jìn)行區(qū)分，所以按照生成方式統(tǒng)一將它們標(biāo)記為“集群內(nèi)部的點(diǎn)”或者“離群點(diǎn)”。

np.random.seed(61)

# 構(gòu)造兩個(gè)數(shù)據(jù)點(diǎn)集群
X_inliers1 = 0.2 * np.random.randn(100, 2)
X_inliers2 = 0.5 * np.random.randn(100, 2)
X_inliers = np.r_[X_inliers1 + 2, X_inliers2 - 2]

# 構(gòu)造一些離群的點(diǎn)
X_outliers = np.random.uniform(low=-4, high=4, size=(20, 2))

# 拼成訓(xùn)練集
X = np.r_[X_inliers, X_outliers]

n_outliers = len(X_outliers)
ground_truth = np.ones(len(X), dtype=int)
# 打標(biāo)簽，群內(nèi)點(diǎn)構(gòu)造離群值為1，離群點(diǎn)構(gòu)造離群值為-1
ground_truth[-n_outliers:] = -1

plt.title('構(gòu)造數(shù)據(jù)集 (LOF)')
plt.scatter(X[:-n_outliers, 0], X[:-n_outliers, 1], color='b', s=5, label='集群點(diǎn)')
plt.scatter(X[-n_outliers:, 0], X[-n_outliers:, 1], color='orange', s=5, label='離群點(diǎn)')

plt.axis('tight')
plt.xlim((-5, 5))
plt.ylim((-5, 5))
legend = plt.legend(loc='upper left')
legend.legendHandles[0]._sizes = [10]
legend.legendHandles[1]._sizes = [20]
plt.show()

然后使用LocalOutlierFactor庫對構(gòu)造數(shù)據(jù)集進(jìn)行訓(xùn)練，得到訓(xùn)練的標(biāo)簽和訓(xùn)練分?jǐn)?shù)（局部離群值）。為了便于圖形化展示，這里對訓(xùn)練分?jǐn)?shù)進(jìn)行了一些轉(zhuǎn)換。

# 訓(xùn)練模型（找出每個(gè)數(shù)據(jù)的實(shí)際離群值）
clf = LocalOutlierFactor(n_neighbors=20, contamination=0.1)

# 對單個(gè)數(shù)據(jù)集進(jìn)行無監(jiān)督檢測時(shí)，以1和-1分別表示非離群點(diǎn)與離群點(diǎn)
y_pred = clf.fit_predict(X)

# 找出構(gòu)造離群值與實(shí)際離群值不同的點(diǎn)
n_errors = y_pred != ground_truth
X_pred = np.c_[X,n_errors]

X_scores = clf.negative_outlier_factor_
# 實(shí)際離群值有正有負(fù)，轉(zhuǎn)化為正數(shù)并保留其差異性（不是直接取絕對值）
X_scores_nor = (X_scores.max() - X_scores) / (X_scores.max() - X_scores.min())
X_pred = np.c_[X_pred,X_scores_nor]
X_pred = pd.DataFrame(X_pred,columns=['x','y','pred','scores'])

X_pred_same = X_pred[X_pred['pred'] == False]
X_pred_different = X_pred[X_pred['pred'] == True]

# 直觀地看一看數(shù)據(jù)
X_pred

plt.title('局部離群因子檢測 (LOF)')
plt.scatter(X[:-n_outliers, 0], X[:-n_outliers, 1], color='b', s=5, label='集群點(diǎn)')
plt.scatter(X[-n_outliers:, 0], X[-n_outliers:, 1], color='orange', s=5, label='離群點(diǎn)')

# 以標(biāo)準(zhǔn)化之后的局部離群值為半徑畫圓，以圓的大小直觀表示出每個(gè)數(shù)據(jù)點(diǎn)的離群程度
plt.scatter(X_pred_same.values[:,0], X_pred_same.values[:, 1], 
            s=1000 * X_pred_same.values[:, 3], edgecolors='c', 
            facecolors='none', label='標(biāo)簽一致')
plt.scatter(X_pred_different.values[:, 0], X_pred_different.values[:, 1], 
            s=1000 * X_pred_different.values[:, 3], edgecolors='violet', 
            facecolors='none', label='標(biāo)簽不同')

plt.axis('tight')
plt.xlim((-5, 5))
plt.ylim((-5, 5))

legend = plt.legend(loc='upper left')
legend.legendHandles[0]._sizes = [10]
legend.legendHandles[1]._sizes = [20]
plt.show()

可以看出，模型成功區(qū)分出了大部分的離群點(diǎn)，一些因?yàn)殡S機(jī)原因散落在集群內(nèi)部的“離群點(diǎn)”也被識別為集群內(nèi)部的點(diǎn)，但是一些與集群略為分散的“集群點(diǎn)”則被識別為離群點(diǎn)。
??同時(shí)可以看出，模型對于不同密度的集群有著較好的區(qū)分度，對于低密度集群與高密度集群使用了不同的密度閾值來區(qū)分是否離群點(diǎn)。
??因此，我們從直觀上可以得到一個(gè)印象，即基于LOF模型的離群點(diǎn)識別在某些情況下，可能比基于某種統(tǒng)計(jì)學(xué)分布規(guī)則的識別更加符合實(shí)際情況。

色偷偷精品伊人,欧洲久久精品,欧美综合婷婷骚逼,国产AV主播,国产最新探花在线,九色在线视频一区,伊人大交九欧美,1769亚洲,黄色成人av

異常檢測（四）——基于相似度的方法

異常檢測（四）——基于相似度的方法

異常檢測——基于相似度的方法

1.概述

2、基于距離的度量

2.1基于單元的方法

2.2基于索引的方法

2.3基于密度的方法

3.1 k-距離(k-distance(p)):

3.2 k-領(lǐng)域（k-distance neighborhood）:

3.3可達(dá)距離（reachablity distance）:

3.4局部可達(dá)密度（local reachability density）：

3.5 局部異常因子：

相關(guān)閱讀更多精彩內(nèi)容

友情鏈接更多精彩內(nèi)容

色偷偷精品伊人,欧洲久久精品,欧美综合婷婷骚逼,国产AV主播,国产最新探花在线,九色在线视频一区,伊人大交九 欧美,1769亚洲,黄色成人av

異常檢測（四）——基于相似度的方法

異常檢測——基于相似度的方法

1.概述

2、基于距離的度量

2.1基于單元的方法

2.2基于索引的方法

2.3基于密度的方法

3.1 k-距離(k-distance(p)):

3.2 k-領(lǐng)域（k-distance neighborhood）:

3.3可達(dá)距離（reachablity distance）:

3.4局部可達(dá)密度（local reachability density）：

3.5 局部異常因子：

相關(guān)閱讀更多精彩內(nèi)容

友情鏈接更多精彩內(nèi)容

色偷偷精品伊人,欧洲久久精品,欧美综合婷婷骚逼,国产AV主播,国产最新探花在线,九色在线视频一区,伊人大交九欧美,1769亚洲,黄色成人av