Object o ใน Data Set S เป็น Distance-based (DB) Outlier ด้วย Parameters p และ d คือ DB(p, d) หากอย่างน้อย Fraction p ของ Objects ใน S อยู่ที่ Distance มากกว่า d จาก o กล่าวคือ แทนที่จะ Depend on Statistical Tests สามารถคิดว่า Distance-based Outliers คือ Objects ที่ไม่มี Neighbors เพียงพอ
Neighbors กำหนดโดย Distance จาก Given Object ในการเปรียบเทียบกับ Statistical-based Methods Distance-based Outlier Detection Generalizes หรือ Merges Ideas เบื้องหลัง Discordancy Testing สำหรับ Standard Distributions ดังนั้น Distance-based Outlier เรียกอีกอย่างว่า Unified Outlier หรือ UO-outlier
Distance-based Outlier Detection ป้องกัน Excessive Computation ที่เกี่ยวข้องกับ Fitting Observed Distribution เข้า Standard Distribution และเลือก Discordancy Tests สำหรับบาง Discordancy Tests สามารถแสดงได้ว่า ถ้า Object o เป็น Outlier ตาม Given Test แล้ว o ยังเป็น DB(p, d) Outlier สำหรับ Properly Defined p และ d
ตัวอย่าง: ถ้า Objects ที่อยู่ 3 หรือมากกว่า Standard Deviations จาก Mean ถือว่า Outliers ภายใต้ Normal Distribution Representation นี้สามารถ "Unified" ได้โดย DB(0.9988, 0.13s)-outlier มี Efficient Algorithms สำหรับ Mining Distance-based Outliers ที่พัฒนาขึ้น ดังนี้:
1. Index-based Algorithm
กำหนด Data Set Index-based Algorithm ใช้ Multidimensional Indexing Structures รวม R-trees หรือ k-d Trees เพื่อ Search Neighbors ของแต่ละ Object o ภายใน Radius d รอบ Object นั้น ให้ M เป็น Maximum Number of Objects ภายใน d-neighborhood ของ Outlier ดังนั้น เมื่อพบ M + 1 Neighbors ของ Object o แล้ว เข้าถึงได้ว่า o ไม่ใช่ Outlier Algorithm นี้มี Worst-case Complexity O(k × n²) โดย k = Dimensionality, n = จำนวน Objects ใน Data Set
2. Nested-loop Algorithm
Nested-loop Algorithm มี Evaluation Complexity เหมือน Index-based Algorithm แต่ Avoid Index Structure Construction และ Try Minimize Number of I/O's แบ่ง Memory Buffer Areas เป็น 2 Halves และ Data Set เป็น Several Logical Blocks
3. Cell-based Algorithm
เพื่อ Avoid O(n²) Computational Complexity Cell-based Algorithm พัฒนาสำหรับ Memory-resident Data Sets Complexity คือ O(cᵏ + n) โดย c = Constant based on Number of Cells, k = Dimensionality
ใน Method นี้ Data Space ถูก Partition เป็น Cells ด้วย Side Length เทียบเท่า d/√k แต่ละ Cell มี 2 Layers รอบๆ
Layer แรกหนา 1 Cell ในขณะที่ Layer ที่สองหนา √k Cells ปัดขึ้นเป็น Integer ใกล้ที่สุด Algorithm นับ Outliers บน Cell-by-cell Basis แทน Object-by-object สำหรับ Given Cell สะสม 3 Counts: จำนวน Objects ใน Cell, ใน Cell + First Layer, และใน Cell + Both Layers
