The outlier detection is a very important problem in the field of data mining that aims to detect objects having high deviation from other data. Most of the algorithms with regarding to outlier detection are only based on the vector data or the graph data respectively in this field. But there are a lot of data that combine both the graph property and the features of each entity such as social networking graphs and co-purchased graphs of ecommerce market. In this paper, we propose an efficient method to detect outliers from data that has both properties of graph and features called attributed graph. The method processes a two-phase algo-rithm that is clustering and outlier detection. In the clustering phase, it finds densely connected subgraph called core clusters and discovers contributed features among the data in each core cluster, then it expands all core clusters with their neighbors which have similar values with respect to contributed features and keep a densely connected graph. In the outlier detection phase, it scores for all objects using the generated clusters then finds outliers. Our experiments show that our proposed approach is more efficient than existing algo-rithms with real world data and synthetic data.
본 연구는 그래프의 각 오브젝트에 다수의 속성값을 갖는 속성 그래프에서 아웃라이어를 검출하는 문제를 해결하고자 한다. 이를 위해 벡터 데이터와 그래프 밀도를 고려하여 클러스터링을 수행하고, 획득한 클러스터를 통해 각 오브젝트의 outlierness를 구해 그 값이 큰 오브젝트를 아웃라이어로 정의한다. 제안하는 알고리즘은 클러스터링과 아웃라이어 검출을 하는 2단계 알고리즘을 수행한다. 클러스터링 단계에서는 그래프 내 엣지의 밀도가 높은 서브그래프를 코어 클러스터로 하여 클러스터 내 오브젝트들의 속성 간 연관성이 높은 서브스페이스를 선정하고 서브스페이스 상에서 유사한 값을 가지면서 그래프의 밀도가 높은 클러스터로 점진적으로 확장해 나간다. 아웃라이어 검출 단계에서는 도출된 클러스터를 이용하여 각 오브젝트의 아웃라이어 스코어를 계산하고 아웃라이어 검출을 수행한다. 제안하는 방법은 속성 그래프에서 아웃라이어어를 검출하기 위한 클러스터링 방법과 각 클러스터의 quality measure 그리고, 각 오브젝트의 아웃라이어 스코어를 고안하였으며, 실험을 통해 그 효율성을 입증하였다.
