속성 그래프에서의 강한 연결성과 적합한 서브스페이스에 기반한 아웃라이어 검출 방법

Abstract

본 연구는 그래프의 각 오브젝트에 다수의 속성값을 갖는 속성 그래프에서 아웃라이어를 검출하는 문제를 해결하고자 한다. 이를 위해 벡터 데이터와 그래프 밀도를 고려하여 클러스터링을 수행하고, 획득한 클러스터를 통해 각 오브젝트의 outlierness를 구해 그 값이 큰 오브젝트를 아웃라이어로 정의한다. 제안하는 알고리즘은 클러스터링과 아웃라이어 검출을 하는 2단계 알고리즘을 수행한다. 클러스터링 단계에서는 그래프 내 엣지의 밀도가 높은 서브그래프를 코어 클러스터로 하여 클러스터 내 오브젝트들의 속성 간 연관성이 높은 서브스페이스를 선정하고 서브스페이스 상에서 유사한 값을 가지면서 그래프의 밀도가 높은 클러스터로 점진적으로 확장해 나간다. 아웃라이어 검출 단계에서는 도출된 클러스터를 이용하여 각 오브젝트의 아웃라이어 스코어를 계산하고 아웃라이어 검출을 수행한다. 제안하는 방법은 속성 그래프에서 아웃라이어어를 검출하기 위한 클러스터링 방법과 각 클러스터의 quality measure 그리고, 각 오브젝트의 아웃라이어 스코어를 고안하였으며, 실험을 통해 그 효율성을 입증하였다.