資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝學
法學什麼是基於距離的離群點？
如果資料集 S 中的一個物件 o 滿足引數 p 和 d，即 DB(p, d)，則它是一個基於距離的 (DB) 離群點，如果 S 中至少 p 比例的物件與 o 的距離大於 d。換句話說，它不依賴於統計檢驗，可以將基於距離的離群點視為那些沒有足夠鄰居的物件。
鄰居是根據與給定物件的距離來表示的。與基於統計的方法相比，基於距離的離群點檢測概括或合併了標準分佈離群值檢驗背後的思想。因此，基於距離的離群點也稱為統一離群點或 UO-離群點。
基於距離的離群點檢測避免了可能與將觀察到的分佈擬合到某些標準分佈以及選擇離群值檢驗相關的過度計算。對於某些離群值檢驗，可以證明，如果物件 o 根據給定檢驗是離群值，則 o 對於某些適當表示的 p 和 d 也是 DB(p, d) 離群值。
例如，如果將距均值 3 個或更多標準差的物件視為離群值（考慮正態分佈），則可以透過 DB(0.9988, 0.13s) 離群值來“統一”此表示。已經建立了幾種用於挖掘基於距離的離群點的有效演算法，如下所示：
**基於索引的演算法** - 給定一個數據集，基於索引的演算法利用多維索引結構（包括 R 樹或 k-d 樹）來搜尋物件 o 周圍半徑 d 內每個物件的鄰居。設 M 為離群點 d 鄰域內物件的最大數量。因此，一旦發現物件 o 的 M + 1 個鄰居，就可以確定 o 不是離群點。該演算法的最低情況複雜度為 O(k * n²)，其中 k 是維數，n 是資料集中物件的數目。
**巢狀迴圈演算法** - 巢狀迴圈演算法與基於索引的演算法具有相同的評估複雜度，但避免了索引結構的構建，並試圖最小化 I/O 次數。它將記憶體緩衝區劃分為兩半，並將資料分成多個邏輯塊。
**基於單元格的演算法** - 為了避免 O(n²) 的計算複雜度，開發了一種用於記憶體駐留資料集的基於單元格的演算法。其複雜度為 O(ck + n)，其中 c 是基於單元格數量的常數，k 是維數。
在這種方法中，資料空間被劃分為邊長類似於 $\frac{d}{\sqrt[2]{k}}$ 的單元格。每個單元格都有兩層圍繞著它。
第一層厚一個單元格，第二層厚 $\sqrt[2]{k}$ 個單元格（四捨五入到最接近的整數）。該演算法按單元格而非按物件逐個計算離群值。對於給定的單元格，它累積三個計數，包括單元格中的物件數量、單元格和第一層中的物件數量以及單元格和兩層中的物件數量。
2K+ 次瀏覽
