Một đối tượng o trong tập dữ liệu S là một ngoại lệ dựa trên khoảng cách (DB) với các tham số p và d, tức là, DB (p, d), nếu một phần nhỏ nhất p của các đối tượng trong S nằm ở khoảng cách cao hơn d so với o. Nói cách khác, thay vì phụ thuộc vào các bài kiểm tra thống kê, nó có thể coi các ngoại lệ dựa trên khoảng cách là những đối tượng không có đủ hàng xóm.
Các hàng xóm được biểu diễn dựa trên khoảng cách từ đối tượng nhất định. So với các phương pháp dựa trên thống kê, phát hiện ngoại lệ dựa trên khoảng cách khái quát hoặc kết hợp các ý tưởng đằng sau kiểm tra sự không phù hợp cho các phân phối chuẩn. Do đó, ngoại lệ dựa trên khoảng cách còn được gọi là ngoại lệ thống nhất hoặc ngoại lệ UO.
Việc phát hiện giá trị ngoại lệ dựa trên khoảng cách ngăn chặn việc tính toán quá mức có thể liên quan đến việc điều chỉnh phân phối quan sát được thành một số phân phối chuẩn và trong việc lựa chọn các thử nghiệm chênh lệch. Đối với một số bài kiểm tra Sự phù hợp, nó có thể được hiển thị rằng nếu một đối tượng o là một giá trị ngoại lệ theo thử nghiệm đã cho, thì o cũng là một ngoại lệ DB (p, d) đối với một số p và d được trình bày đúng.
Ví dụ:nếu các đối tượng nằm từ 3 độ lệch chuẩn trở lên so với giá trị trung bình được coi là ngoại lệ, được coi là phân phối chuẩn, thì biểu diễn này có thể được “thống nhất” bởi một ngoại lệ DB (0,9988, 0,13s). Có một số thuật toán hiệu quả để khai thác các ngoại lệ dựa trên khoảng cách đã được tạo ra như sau -
Thuật toán dựa trên chỉ mục - Cho một tập dữ liệu, thuật toán dựa trên chỉ mục tạo điều kiện cho các cấu trúc lập chỉ mục đa chiều, bao gồm cây R hoặc cây k-d, để tìm kiếm các lân cận của mỗi đối tượng o trong bán kính d xung quanh đối tượng đó. Gọi M là số đối tượng lớn nhất trong vùng lân cận d của một ngoại số. Do đó, một khi M + 1 lân cận của đối tượng o được phát hiện, có thể truy cập được rằng o không phải là đối tượng ngoại lai. Thuật toán này có độ phức tạp chữ thường thấp nhất là O (k * n2), trong đó k là số chiều và n là số đối tượng trong tập dữ liệu.
Thuật toán vòng lặp lồng nhau - Thuật toán vòng lặp lồng nhau có độ phức tạp đánh giá tương tự như thuật toán dựa trên chỉ mục nhưng tránh xây dựng cấu trúc chỉ mục và cố gắng giảm thiểu số lượng I / O’s. Nó chia vùng đệm bộ nhớ thành hai nửa và dữ liệu được đặt thành nhiều khối logic.
Thuật toán dựa trên ô - Nó có thể tránh được O (n 2 ) độ phức tạp tính toán, một thuật toán dựa trên ô được phát triển cho các tập dữ liệu thường trú trong bộ nhớ. Độ phức tạp của nó là O (e k + n), trong đó c là hằng số dựa trên số ô và k là thứ nguyên.
Trong phương pháp này, không gian dữ liệu được phân chia thành các ô có độ dài cạnh tương tự như $ \ frac {d} {\ sqrt [2] {k}} $. Mỗi ô có hai lớp bao quanh.
Lớp đầu tiên dày một ô, trong khi lớp thứ hai dày $ \ sqrt [2] {k} $ ô, được làm tròn đến số nguyên gần nhất. Thuật toán đếm các giá trị ngoại lệ trên từng ô thay vì từng đối tượng. Đối với một ô nhất định, nó tích lũy ba số đếm bao gồm số lượng đối tượng trong ô, trong ô và lớp đầu tiên cùng nhau và trong ô và cả hai lớp cùng nhau.