DBSCAN 군집화 알고리즘 완벽 정리: 밀도 기반 클러스터링으로 중첩 군집과 이상치 구분하기

핵심 메시지

• DBSCAN은 사람이 눈으로 군집을 알아보듯, 점들이 빽빽하게 모인 밀도를 기준으로 데이터를 묶는 비지도 학습 알고리즘이다.
• k-평균 군집화가 어려워하는 중첩된(서로 감싸는) 군집도 밀도 기준으로는 자연스럽게 구분할 수 있다.
• 핵심점(core point)은 사용자가 정한 반경 안에 최소 개수 이상의 이웃 점을 가진 점이며, 반경과 최소 이웃 수는 직접 조정하는 값이다.
• 핵심점은 가까운 핵심점을 끌어들여 군집을 확장하지만, 비핵심점은 군집에 합류만 할 뿐 군집을 더 넓히지 못한다.
• 어느 군집의 핵심점과도 가깝지 않은 점은 어떤 군집에도 속하지 않는 이상치(outlier)로 남는다.

쉽게 이해하기

키와 몸무게처럼 두 가지 특성을 가진 사람들을 2차원 그래프에 찍으면, 우리는 점들이 빽빽하게 모인 덩어리를 보고 눈으로 쉽게 군집을 구분한다. 그러나 한 군집이 다른 군집을 감싸는 중첩 구조이거나, 나이 같은 특성을 더해 4차원 이상이 되면 더 이상 눈으로 볼 수 없다. DBSCAN은 바로 이런 상황에서 사람이 밀도로 군집을 알아보는 방식을 그대로 흉내 내는 알고리즘이다.

DBSCAN의 출발점은 각 점 주위에 일정 반경의 원을 그려, 그 안에 들어오는 가까운 점이 몇 개인지 세는 것이다. 이때 정해 둔 기준(예: 최소 4개) 이상의 이웃을 가진 점을 핵심점이라 부른다. 반경의 크기와 핵심점이 되기 위한 최소 이웃 수는 모두 사용자가 정하는 값이라, 데이터에 맞게 이리저리 조정해 보아야 한다.

군집은 순차적으로 만들어진다. 먼저 핵심점 하나를 무작위로 골라 첫 군집을 시작하고, 그 군집에 가까운 핵심점들을 차례로 합류시키며 군집을 넓혀 간다. 핵심점이 더 이상 추가되지 않으면, 핵심점 근처에 있는 비핵심점들을 군집에 합류시킨다. 다만 비핵심점은 군집의 가장자리에 붙기만 할 뿐, 그 점을 발판 삼아 군집을 더 확장하지는 않는다.

첫 군집을 완성한 뒤 남은 핵심점들이 서로 가깝다면 같은 방식으로 두 번째 군집을 이룬다. 모든 핵심점이 어느 군집엔가 배정되고 나면, 어떤 군집의 핵심점과도 가깝지 않은 점들은 이상치로 따로 남는다. 군집이 순서대로 만들어지기 때문에, 두 군집 모두에 가까운 비핵심점은 먼저 만들어진 군집에 속하고 이후에는 다른 군집으로 옮겨 가지 않는다.

주요 인사이트

• 군집의 모양을 미리 가정하지 않고 밀도만으로 묶기 때문에, 원형이 아니거나 서로 감싸는 복잡한 형태의 군집도 찾아낼 수 있다.
• 눈으로 볼 수 없는 4차원 이상의 고차원 데이터에서도 같은 밀도 기준을 그대로 적용할 수 있다는 점이 DBSCAN의 큰 장점이다.
• 핵심점과 비핵심점을 구분하는 규칙 덕분에, 군집 가장자리의 점들과 외딴 이상치가 자연스럽게 분리된다.
• 반경과 최소 이웃 수라는 두 값이 결과를 좌우하므로, 좋은 군집을 얻으려면 이 두 매개변수를 데이터에 맞게 조정하는 과정이 필요하다.

자주 묻는 질문

관련 AI 소식