이상 점/분리 점 검출 알고리즘―LOF 분석

부분 이상 인자 알고리즘-Local Outlier Factor(LOF)
        데이터 발굴 에 있어 특징 공정 과 모델 훈련 을 하기 전에 데 이 터 를 세척 하고 잘못된 데이터 와 이상 데 이 터 를 제거 해 야 한다.이상 검출 도 데이터 발굴 의 한 방향 으로 반 부정행위,위조 기지 국,금융 사기 등 분야 에 사용 된다.
이상 검출 방법 은 서로 다른 데이터 형식 에 대해 서로 다른 실현 방법 이 있다.자주 사용 하 는 것 은 분포 에 기초 한 방법 이 있 는데,위,아래 에 있다.α비트 점 이외 의 값 은 이상 값(예 를 들 어 그림 1)이 라 고 생각 하고 속성 값 에 대해 자주 사용 합 니 다.거 리 를 바탕 으로 하 는 방법 은 2 차원 또는 고 차원 좌표 체계 내 이상 점 의 판별 에 적용 된다.예 를 들 어 2 차원 평면 좌표 나 경위도 공간 좌표 에서 이상 점 을 식별 할 수 있 고 이런 방법 을 사용 할 수 있다.

        이번 에는 거리 기반 의 이상 검출 알고리즘 인 국부 이상 인자 LOF 알고리즘(Local Outlier Factor)을 소개 한다.
시각 적 으로 직관 적 으로 느껴 보 자.그림 2 와 같이 C1 집합 점 에 대해 전체적인 간격,밀도,분산 상황 이 비교적 고 르 게 일치 하고 같은 무리 라 고 볼 수 있다.C2 집합 점 에 대해 서도 마찬가지 로 한 무더기 라 고 볼 수 있다.o1,o2 점 이 상대 적 으로 고립 되 어 이상 점 이나 이산 점 이 라 고 볼 수 있다.문 제 는 알고리즘 의 유 니 버 설 성 을 어떻게 실현 하 느 냐 하 는 것 이다.C1 과 C2 라 는 밀도 분산 상황 이 현저히 다른 집합 이상 점 인식 을 만족 시 킬 수 있다 는 것 이다.LOF 는 우리 의 목 표를 실현 할 수 있다.

LOF 알고리즘 에 대한 정 의 를 소개 합 니 다.
        1)d(p,o):두 점 p 와 o 사이 의 거리;
2)k-distance:k 거리
               점 p 의 제 k 거리 dk(p)에 대한 정 의 는 다음 과 같 습 니 다. 
               dk(p)=d(p,o),그리고 만족:
                      a)집합 중 적어도 p 를 포함 하지 않 은 k 개 점 o,8712°C{x≠p},만족 d(p,o,)≤d(p,o); 
                      b)집합 중 p 를 포함 하지 않 은 k-1 개의 점 o,8712°C{x≠p}이 가장 많 고 d(p,o,)        p 의 제 k 거리,즉 p 제 k 에서 먼 점 의 거 리 는 p 를 포함 하지 않 습 니 다.그림 3 참조.

        3)k-distance neighborhood of p:k 번 째 인접 지역
점 p 의 제 k 거 리 는 인접 지역 Nk(p)이 고 p 의 제 k 거리 즉 이내 의 모든 점 이 며 k 거 리 를 포함한다.
따라서 p 의 제 k 인접 점 의 개수|Nk(p)|≥k.
4)reach-distance:도달 거리
점 o 에서 점 p 까지 의 제 k 가 달 거 리 는 다음 과 같이 정의 합 니 다.
reach−distancek(p,o)=max{k−distance(o),d(p,o)}
즉,점 o 에서 점 p 까지 의 제 k 는 거리 에 도달 할 수 있 고 적어도 o 의 제 k 거리 또는 o,p 간 의 진실 거리 이다.
이것 은 또한 점 o 에서 가장 가 까 운 k 개 점,o 에서 그들의 도달 거리 가 같다 고 여 겨 지고 모두 dk(o)와 같다 는 것 을 의미한다.
그림 4 에서 o 1 에서 p 까지 의 5 번 째 거 리 는 d(p,o 1)이 고 o 2 에서 p 까지 의 5 번 째 거 리 는 d5(o 2)이다.

        5)local reachability density:국부 도달 밀도
점 p 의 부분 적 인 접근 밀 도 는 다음 과 같다.

                점 p 의 제 k 인접 도 메 인 에서 p 까지 의 평균 거 리 를 나타 내 는 역수 입 니 다.
주의 하 세 요.p 의 인접 점 Nk(p)에서 p 까지 의 접근 거리 입 니 다.p 에서 Nk(p)까지 의 접근 거리 가 아니 라 관 계 를 분명히 해 야 합 니 다.또한 중복 점 이 있 으 면 분모 의 도달 거리 와 0 이 될 수 있 으 며,lrd 가 무한대 로 변 할 수 있 으 며,다음 에 도 이 점 을 계속 언급 할 것 이다.
이 값 의 의 미 는 이렇게 이해 할 수 있다.우선 이것 은 하나의 밀 도 를 대표 하고 밀도 가 높 을 수록 우 리 는 같은 무리 에 속 할 수 있 고 밀도 가 낮 을 수록 분리 점 일 수 있다 고 생각한다.만약 에 p 와 주변 인접 지역 점 이 같은 떨 기 라면 도달 거리 가 비교적 작은 dk(o)일 수 있 고 도달 거리 가 비교적 작고 밀도 가 비교적 높다.만약 에 p 와 주변 이웃 점 이 비교적 멀 면 도달 할 수 있 는 거 리 는 비교적 큰 값 d(p,o)를 취하 여 밀도 가 비교적 적 고 분리 점 일 수 있다.
        6)local outlier factor:국부 분리 인자
점 p 의 국부 분리 인 자 는 다음 과 같다.

                점 p 의 인접 점 Nk(p)의 국부 적 밀도 와 점 p 의 국부 적 밀도 비례 를 나타 내 는 평균 수.
만약 에 이 비율 이 1 에 가 까 울 수록 p 의 이웃 점 밀도 차이 가 많 지 않 고 p 는 이웃 지역 과 같은 무리 에 속 할 수 있 음 을 나타 낸다.만약 에 이 비율 이 1 보다 작 을 수록 p 의 밀 도 는 이웃 점 의 밀도 보다 높 고 p 는 밀집 점 임 을 나타 낸다.만약 에 이 비율 이 1 보다 클 수록 p 의 밀 도 는 이웃 점 의 밀도 보다 적 고 p 는 이상 점 일 수 있다 는 것 을 의미한다.
현재 개념 정 의 는 이미 소개 되 었 습 니 다.지금 다시 돌 이 켜 보면 lof 의 사상 은 주로 각 점 p 와 그 인접 점 의 밀 도 를 비교 하여 이 점 이 이상 점 인지 아 닌 지 를 판단 하 는 것 입 니 다.만약 에 점 p 의 밀도 가 낮 을 수록 이상 점 으로 인 정 될 수 있 습 니 다.밀 도 는 점 간 의 거 리 를 통 해 계산 되 는데 점 간 의 거리 가 멀 수록 밀도 가 낮 고 거리 가 가 까 울 수록 밀도 가 높 아 우리 의 이해 에 완전히 부합된다.그리고 lof 는 밀 도 를 점 의 k 인접 도 메 인 을 통 해 계산 하기 때문에 전체 계산 이 아니 라'부분'이상 인자 라 고 불 린 다.그러면 그림 1 의 두 가지 데이터 세트 인 C1 과 C2 에 대해 lof 는 데이터 밀도 분산 상황 이 다 르 기 때문에 정상 점 을 이상 점 으로 잘못 판단 하지 않 고 정확하게 처리 할 수 있다.
알고리즘 사상 은 이미 다 말 했 으 니,지금 은 건어물 부분 에 들 어가 코드 를 밝 혔 다.
python 에서 실 현 된 lof 알고리즘:
https://github.com/damjankuznar/pylof
포크 다음 코드 좀 더 주세요.
https://github.com/wangyibo360/pylof
차이 점:
위 에서 언급 한 바 와 같이 중복 점 국부 가 달 밀도 가 무한대 로 변 할 수 있 는 문제 에 대해 제 가 고 친 코드 는 이 문 제 를 처 리 했 습 니 다.만약 에 중복 점 방면 의 장면 이 있 으 면 제 코드 를 사용 할 수 있 습 니 다.소스 코드 는 bug 가 있 고 fix 가 없 으 며 코드 주인 이 자 취 를 감 춘 것 같 습 니 다.제 pull 도 아무 도 관여 하지 않 습 니 다.
이상 점/이 군 점 검출 알고리즘-LOF 해석 에 관 한 이 글 은 여기까지 소개 되 었 습 니 다.더 많은 이상 점/이 군 점 검출 알고리즘-LOF 내용 은 우리 의 이전 글 을 검색 하거나 아래 의 관련 글 을 계속 찾 아 보 세 요.앞으로 많은 응원 바 랍 니 다!