용어 목록 > 밀도기반 군집분석(DBSCAN) (DBSCAN)

밀도기반 군집분석(DBSCAN) (DBSCAN)

쉽게 풀면

밤하늘에서 별을 관찰한다고 생각해봅시다. 별들이 촘촘하게 모여 있는 곳은 하나의 "성단"으로 보이고, 주변에 외따로 떨어진 별 하나는 그냥 배경의 잡음처럼 느껴집니다. DBSCAN은 정확히 이런 방식으로 작동합니다.

한 점 주위 일정 반경 안에 이웃 점이 충분히 많으면 "밀집 지역"으로 보고 계속 이어 붙여 하나의 군집을 만들고, 이웃이 거의 없는 외딴 점은 어느 군집에도 넣지 않고 "노이즈(이상치)"로 분류합니다.

k-means처럼 처음부터 "몇 개의 그룹으로 나눌지"를 미리 정할 필요가 없고, 동그란 모양이 아닌 구불구불한 형태의 군집도 잘 찾아낸다는 장점이 있습니다.

왜 중요한가

실제 데이터는 미리 몇 개의 그룹으로 나뉘는지 알기 어렵고, 군집의 모양도 원형이 아닌 경우가 많습니다.

DBSCAN은 군집 개수를 사전에 지정하지 않고도 임의 형태의 군집을 찾아내며, 동시에 이상치를 자연스럽게 걸러낼 수 있어 이상 탐지, 공간 데이터 분석, 탐색적 데이터 분석(EDA)처럼 "정상 패턴과 예외를 함께 봐야 하는" 연구에서 폭넓게 쓰입니다.

이런 특성 때문에 논문에서는 k-means 등 다른 군집화 기법과 비교 대상으로도 자주 등장합니다.

언제 쓰나

군집이 둥글지 않은 모양(초승달, 고리 등)이거나, 자료에 이상치(잡음)가 섞여 있고 군집 수를 미리 모를 때 씁니다. 공간 자료(위치 좌표), 이상 탐지에 많이 쓰입니다.

• 두 개의 매개변수를 정해야 합니다: 반경 ε(eps)과 최소 이웃 수 minPts. 이웃 수에는 점 자신도 포함하는 것이 원 논문과 많은 구현의 방식입니다.
• 거리 계산이 필요하므로 변수 단위가 다르면 표준화합니다.
• 군집마다 밀도가 크게 다르면 하나의 ε으로는 맞추기 어렵습니다(HDBSCAN 등이 이 한계를 다룸).

결과는 이렇게 읽는다

모든 점이 세 종류 중 하나로 분류됩니다(Ester 외, 1996).

• 핵심점: 반경 ε 안에 minPts개 이상의 점(자신 포함)이 있는 점.
• 경계점: 핵심점의 이웃이지만 자신은 핵심점이 아닌 점. 군집의 가장자리입니다.
• 잡음점: 어느 쪽도 아닌 점. 군집에 넣지 않고 −1 같은 꼬리표를 줍니다.
• 핵심점끼리 ε 이내로 이어지면 같은 군집이 됩니다(밀도 연결).
• 매개변수 고르기: minPts는 보통 차원 수 + 1 이상으로, 경험적으로 2 × 차원 수를 많이 씁니다(Schubert 외, 2017). ε은 각 점의 k번째 이웃까지의 거리(k는 minPts 근처)를 정렬해 그린 k-거리 그래프의 꺾이는 지점을 봅니다.

(가상의 예, 직접 계산) 2차원 점 13개(밀집한 5개 점 두 묶음, 가장자리 가까운 점 2개, 외톨이 2개)에 DBSCAN을 적용했습니다.

ε = 1.0에서는 두 군집이 잘 나뉘고 외톨이 2개가 잡음으로 남습니다. ε을 0.6으로 줄이면 13개 중 9개가 잡음이 되고, 5.0으로 키우면 가장 멀리 떨어진 외톨이 하나만 빼고 모든 점이 한 군집으로 합쳐집니다. 매개변수에 결과가 크게 좌우된다는 점을 보여 줍니다.

논문에는 이렇게 보고한다

ε과 minPts의 값과 선택 근거(k-거리 그래프 등), 거리 척도, 표준화 여부, 군집 수, 잡음점의 수를 적습니다. (아래 문장은 형식을 보여 주는 가상의 예입니다.)

DBSCAN(ε = 0.35, minPts = 8, 유클리드 거리, 표준화 후)을 적용하여 4개 군집과 잡음 31건(3.1%)을 얻었다. ε은 k-거리 그래프의 꺾임 지점에서 정하였다.

• 잡음점을 “이상치”로 단정하지 말고, 매개변수에 따라 달라질 수 있음을 논의합니다.
• 내부 평가지표(실루엣 계수 등)는 잡음점 처리 방법에 따라 달라지므로, 잡음을 제외했는지 밝힙니다.
• 정답 레이블이 있으면 ARI 같은 외부 지표를 함께 제시합니다.

논문에서는 이렇게 쓰입니다

실제 논문에서

이 용어를 직접 쓴 국내 논문 문장을 아직 수집하지 못했습니다. 수집되는 대로 출처와 함께 싣겠습니다.

예시 문장

아래는 용어의 쓰임을 보여 주려고 만든 예시로, 실제 논문에서 가져온 문장이 아닙니다.

이 문장은 "정상 거래는 밀집된 군집으로 묶이고, 패턴이 다른 이상 거래는 어느 군집에도 속하지 않는 점(노이즈)으로 구분되었다"는 뜻입니다. 이상치 탐지가 필요한 연구에서 DBSCAN이 특히 자주 쓰이는 이유입니다.

도로나 GPS 좌표처럼 정형화되지 않은 공간 데이터에서는 군집이 원형이 아닌 경우가 흔합니다. 이 문장은 DBSCAN이 그런 불규칙한 형태의 밀집 구역(예: 정차가 잦은 골목이나 교차로)을 별도의 모양 가정 없이 찾아냈다는 의미입니다.

텍스트를 벡터로 표현한 뒤 군집화하는 자연어처리 연구에서도 DBSCAN이 활용됩니다. 이 문장은 의미가 비슷한 문서끼리는 군집으로 묶고, 어느 주제 군집에도 속하지 않는 문서는 노이즈로 분리해 후속 분석에서 따로 다루었다는 뜻입니다.

조금 더 깊게 보면

DBSCAN에서 각 점은 크게 세 종류로 나뉩니다. 반경(epsilon) 안에 이웃이 minPts개 이상인 "핵심점(core point)", 핵심점의 이웃이지만 그 자체로는 이웃 수가 부족한 "경계점(border point)", 그리고 어느 군집에도 속하지 않는 "노이즈점"입니다.

논문에서 결과를 평가할 때는 실루엣 계수 같은 내부 평가지표나, 정답 레이블이 있는 경우 ARI(Adjusted Rand Index) 같은 외부 평가지표를 함께 보고하는 경우가 많습니다.

또한 데이터 밀도가 지역마다 크게 다른 경우를 다루기 위해 계층적 밀도 개념을 도입한 HDBSCAN 같은 변형 기법이 후속 연구로 자주 언급됩니다.

주의할 점

DBSCAN은 군집 개수를 미리 정하지 않아도 되지만, 대신 "반경(epsilon)"과 "최소 이웃 수(minPts)"라는 두 매개변수를 직접 정해야 하며 이 값에 따라 결과가 크게 달라질 수 있습니다. 또한 k-평균 군집화와 달리 군집마다 밀도가 크게 다른 데이터에는 잘 맞지 않을 수 있습니다.

헷갈리기 쉬운 용어

군집분석 방법들은 군집을 정의하는 방식이 다릅니다.

참고 문헌

1. Ester, M., Kriegel, H.-P., Sander, J., & Xu, X. (1996). A density-based algorithm for discovering clusters in large spatial databases with noise. In Proceedings of the 2nd International Conference on Knowledge Discovery and Data Mining (KDD-96) (pp. 226–231). AAAI Press.
2. Schubert, E., Sander, J., Ester, M., Kriegel, H.-P., & Xu, X. (2017). DBSCAN revisited, revisited: Why and how you should (still) use DBSCAN. ACM Transactions on Database Systems, 42(3), Article 19.
3. Campello, R. J. G. B., Moulavi, D., & Sander, J. (2013). Density-based clustering based on hierarchical density estimates. In Advances in Knowledge Discovery and Data Mining (PAKDD 2013), Lecture Notes in Computer Science, 7819, 160–172. Springer.

표의 기준값은 위 문헌에 근거한 관례이며, 분야·학술지마다 다른 기준을 쓸 수 있습니다.

관련 용어