데이터 마이닝에서 장애물(obstacle)이 존재하는 공간에서의 클러스터링은 흔히 간과되지만 매우 중요한 문제입니다. 예를 들어 도시 시설 입지를 분석할 때 강이나 호수 같은 지리적 장애물을 고려하지 않으면 현실성 없는 결과가 나올 수 있습니다. 이 글에서는 장애물이 있는 클러스터링 문제를 효율적으로 해결하는 접근 방식을 살펴봅니다.
왜 k-medoids 방법인가?
분할 기반 클러스터링(partitioning clustering) 방법은 데이터 집합과 클러스터 중심 간의 거리를 최소화하기 때문에 바람직한 선택입니다. 그러나 k-평균(k-means) 방법을 사용하면 장애물이 존재할 경우 클러스터 중심을 적절히 설정할 수 없다는 문제가 있습니다.
예를 들어, 계산된 클러스터 중심이 호수 한가운데에 위치하게 될 수 있습니다. 반면 k-중심점(k-medoids) 방법은 클러스터 내부에 실제로 존재하는 객체를 중심으로 선택하기 때문에 이러한 비현실적인 상황이 발생하지 않도록 보장합니다.
다만 새로운 중심점(medoid)이 선택될 때마다 각 객체와 새로 선정된 클러스터 중심 사이의 거리를 다시 계산해야 합니다. 두 객체 사이에 장애물이 있을 수 있으므로, 객체 간 거리는 삼각측량(triangulation)과 같은 기하학적 계산을 통해 구해야 하며, 객체와 장애물의 수가 많아지면 계산 비용이 크게 증가한다는 한계가 있습니다.
가시성 그래프를 이용한 문제 정의
장애물을 고려한 클러스터링(clustering with obstacles) 문제는 그래프 이론을 통해 명확하게 정의할 수 있습니다.
먼저 영역 R에서 점 p가 다른 점 q로부터 가시적(visible)이라는 것은, p와 q를 연결하는 직선이 어떠한 장애물과도 교차하지 않는 경우를 의미합니다.
가시성 그래프(visibility graph) VG = (V, E)는 장애물의 각 꼭짓점(vertex)이 V의 노드에 대응되며, V의 두 노드 v1과 v2가 E의 간선으로 연결되는 조건은 해당 꼭짓점들이 서로 가시적인 경우와 정확히 일치하는 그래프입니다.
여기서 VG에 두 개의 추가 점 p와 q를 삽입하여 생성된 가시성 그래프를 VG’ = (V’, E’)라고 하면, E’는 V’의 두 점이 서로 가시적일 때 해당 두 점을 연결하는 간선을 포함합니다.
계산 비용을 줄이는 전처리 및 최적화 기법
임의의 두 객체 또는 점 집합 간의 거리 계산 비용을 줄이기 위해 여러 가지 전처리 및 최적화 기법을 활용할 수 있습니다.
1. 마이크로클러스터링(Microclustering)
그중 하나는 서로 가까운 점들을 마이크로클러스터(microcluster)로 묶는 방법입니다. 이는 먼저 영역 R을 삼각형으로 분할한 후, 같은 삼각형 안에 속한 인접한 점들을 BIRCH나 DBSCAN과 유사한 기법으로 마이크로클러스터로 통합하는 방식으로 수행됩니다. 개별 점 대신 마이크로클러스터 단위로 처리하면 전체 계산량이 크게 줄어듭니다.
2. 조인 인덱스 사전 계산(Precomputation)
이후 최단 경로 계산에 기반하여 두 가지 유형의 조인 인덱스(join index)를 미리 구축할 수 있습니다.
VV 인덱스: 장애물 꼭짓점 쌍(pair of obstacle vertices)에 대한 인덱스
MV 인덱스: 마이크로클러스터와 장애물 꼭짓점 쌍에 대한 인덱스 — 이러한 인덱스를 활용하면 전체 성능을 더욱 최적화할 수 있습니다.
결론: 대규모 데이터셋에서도 고품질 클러스터링 가능
이러한 사전 계산과 최적화를 통해 임의의 두 점(마이크로클러스터 단위의 세밀도) 간의 거리를 효율적으로 계산할 수 있습니다. 따라서 클러스터링 과정은 CLARANS와 같은 일반적인 고효율 k-medoids 알고리즘과 유사한 방식으로 구현할 수 있으며, 대규모 데이터셋에서도 우수한 클러스터링 품질을 달성할 수 있습니다.