데이터 세트 S의 객체 o는 매개변수 p와 d, 즉 DB(p, d)가 있는 거리 기반(DB) 이상값입니다. 영형. 즉, 통계적 테스트에 의존하는 대신 거리 기반 이상값을 이웃이 충분하지 않은 개체로 생각할 수 있습니다.
이웃은 주어진 객체로부터의 거리를 기반으로 표현됩니다. 통계 기반 방법과 비교하여 거리 기반 이상값 감지는 표준 분포에 대한 불일치 테스트 이면의 아이디어를 일반화하거나 병합합니다. 따라서 거리 기반 이상값은 통합 이상값 또는 UO 이상값이라고도 합니다.
거리 기반 이상값 감지는 관찰된 분포를 일부 표준 분포에 맞추고 불일치 테스트를 선택하는 것과 관련될 수 있는 과도한 계산을 방지합니다. 일부 불일치 테스트의 경우 개체 o가 주어진 테스트에 따라 이상값이면 o도 적절하게 표현된 p 및 d에 대한 DB(p, d) 이상값임을 표시할 수 있습니다.
예를 들어, 평균에서 3개 이상의 표준편차에 있는 개체를 이상값으로 취급하면 정규분포를 고려하여 이 표현을 DB(0.9988, 0.13s)-이상값으로 "통일"할 수 있습니다. 다음과 같이 생성된 거리 기반 이상값을 마이닝하기 위한 몇 가지 효율적인 알고리즘이 있습니다. -
색인 기반 알고리즘 − 주어진 데이터 세트에서 인덱스 기반 알고리즘은 R-트리 또는 k-d 트리를 포함한 다차원 인덱싱 구조를 촉진하여 해당 개체 주위의 반경 d 내에서 각 개체 o의 이웃을 검색합니다. M을 이상치의 d-이웃 내 최대 개체 수라고 합니다. 따라서 객체 o의 M + 1개의 이웃이 발견되면 o가 이상치가 아님을 알 수 있습니다. 이 알고리즘은 O(k * n2)의 가장 낮은 복잡도를 가지며 여기서 k는 차원이고 n은 데이터 세트의 개체 수입니다.
중첩 루프 알고리즘 − 중첩 루프 알고리즘은 인덱스 기반 알고리즘과 동일한 평가 복잡도를 갖지만 인덱스 구조 구성을 피하고 I/O 수를 최소화하려고 합니다. 메모리 버퍼 영역을 반으로 나누고 데이터를 여러 논리 블록으로 설정합니다.
셀 기반 알고리즘 − O(n 2 ) 계산 복잡성으로 인해 메모리 상주 데이터 세트를 위해 셀 기반 알고리즘이 개발되었습니다. 복잡성은 O(e k + n), 여기서 c는 셀 수를 기준으로 한 상수이고 k는 차원입니다.
이 방법에서 데이터 공간은 $\frac{d}{\sqrt[2]{k}}$와 유사한 측면 길이를 가진 셀로 분할됩니다. 각 셀은 두 개의 레이어를 둘러싸고 있습니다.
첫 번째 레이어는 한 셀 두께이고 두 번째 레이어는 $\sqrt[2]{k}$ 셀 두께이며 가장 가까운 정수로 반올림됩니다. 알고리즘은 개체 단위 대신 셀 단위로 이상값을 계산합니다. 주어진 셀에 대해 셀의 개체 수, 셀과 첫 번째 레이어를 함께, 셀과 두 레이어를 함께 포함하여 세 가지 카운트를 누적합니다.