Ngoại lai dựa trên khoảng cách (Distance-based Outlier)

Định nghĩa

Đối tượng o trong tập dữ liệu S là ngoại lai dựa trên khoảng cách (Distance-based - DB outlier) với tham số p và d, ký hiệu DB(p, d), nếu ít nhất một phân số p của các đối tượng trong S nằm ở khoảng cách lớn hơn d từ o. Nói cách khác: thay vì dựa vào kiểm định thống kê, ngoại lai dựa trên khoảng cách là những đối tượng không có đủ láng giềng.

So sánh với phương pháp thống kê

Phát hiện ngoại lai dựa trên khoảng cách tổng quát/hợp nhất ý tưởng đằng sau kiểm định discordancy cho các phân phối chuẩn. Do đó ngoại lai dựa trên khoảng cách còn gọi là ngoại lai thống nhất (unified outlier - UO-outlier).

Ưu điểm: Tránh tính toán quá mức liên quan đến khớp phân phối quan sát vào phân phối chuẩn và chọn kiểm định discordancy. Nếu đối tượng o là outlier theo kiểm định discordancy cho trước, thì o cũng là DB(p, d) outlier với p, d phù hợp.

Ví dụ: Nếu đối tượng nằm ≥ 3 độ lệch chuẩn từ mean (phân phối chuẩn) coi là outlier → "thống nhất" bằng DB(0.9988, 0.13σ).

Các thuật toán hiệu quả khai thác ngoại lai dựa trên khoảng cách

1. Thuật toán dựa trên chỉ mục (Index-based algorithm)

Sử dụng cấu trúc chỉ mục đa chiều (R-trees, k-d trees) tìm láng giềng mỗi đối tượng o trong bán kính d. M = số đối tượng tối đa trong láng giềng d của outlier. Khi tìm thấy M+1 láng giềng → o không phải outlier. Độ phức tạp trường hợp xấu: O(k·n²), k=số chiều, n=số đối tượng.

2. Thuật toán lặp lồng (Nested-loop algorithm)

Độ phức tạp đánh giá giống index-based nhưng tránh xây dựng cấu trúc chỉ mục, cố gắng giảm I/O. Chia bộ đệm bộ nhớ thành 2 nửa, chia dữ liệu thành các khối logic.

3. Thuật toán dựa trên ô (Cell-based algorithm)

Tránh độ phức tạp O(n²), phát triển cho dữ liệu trong bộ nhớ. Độ phức tạp: O(cᵏ + n), c=hằng số dựa trên số ô, k=số chiều.

Không gian dữ liệu phân vùng thành ô cạnh dài = d/√k. Mỗi ô có 2 lớp bao quanh:

Lớp 1: dày 1 ô.
Lớp 2: dày √k ô (làm tròn lên).