회사에서 지도를 통해 구역을 분할하고, 분할한 구역을 일정 기준에 따라 묶어 사용자에게 보여주는 기능을 구상하고 있다.
그 기능을 구현하기 위해 필요한 기술 중 하나가 Marker Clustering이다.
이에 대해 공부하면서 내용을 짧게 메모하려고 한다.
What is Clustering?
Clustering은 '군집화'로 비슷한 특성을 가진 데이터끼리 묶어 나누는 과정을 의미한다.
클러스터링의 목표는 서로 다른 두 클러스터 사이는 서로 멀거나 비슷하지 않게 하고, 클러스터 내부의 데이터 사이는 서로 가깝거나 비슷하게 하는 것이다.
즉, 클러스터 사이의 거리는 최대화하고 클러스터 내 데이터 사이의 거리는 최소화하는 것이 클러스터링의 목표이다.
Clustering Algorithms
- Hierarchical clustering (계층적 군집)
- Point assignment clustering
Hierarchical clustering
- Divisicve (top to down)
: 하나의 클러스터로부터 시작해 모든 클러스터가 정확히 하나의 원소를 가질 때까지 계속 쪼개는 방식 - Agglomerative (bottom to up)
: 각각의 점을 원소로 가지는 클러스터로부터 전체 클러스터 하나를 만들 때까지 계속하여 두 개의 가까운 클러스터를 합치는 방식
Agglomerative
반복적으로 두 개의 '가까운' 클러스터를 찾는 것이 가장 중요하다.
거리 공간에서는 거리를 통해 가까운 클러스터를 찾는다.
원소가 하나일 때,
두 클러스터 내에 원소가 각 하나씩 있을 경우, 클러스터 사이의 거리는 간단하게 구할 수 있다.
원소가 두 개 이상일 때,
두 클러스터 내에 원소가 각 두 개 이상씩 있을 경우, 원소들 좌표값의 평균을 구해서 클러스터 사이의 거리를 계산해야 한다.
이 때 유클리드 공간에서는 주로 centroid라는 개념을 사용한다.
유클리드 공간: 수학 용어로, 평면과 공간을 일반화한 3차원 공간이다. 해당 공간에서는 다음의 유클리드 기하 5개의 공준이 성립한다.
1. 두 점을 잇는 직선은 유일하다.
2. 두 점을 잇는 선분은 직선인 채로 무한대로 늘릴 수 있다.
3. 임의의 한 점과 임의의 길이를 반지름으로 하는 원을 그릴 수 있다.
4. 직각은 모두 합동이다.
5. 직선 I와 그 직선 밖의 한 점 P가 있을 때, P를 지나면서 직선 I에 평행한 직선은 유일하다.
centroid: 도심. 어떤 임의 단면에서 직교 좌표축에 대한 단면 1차 모멘트가 0이 되는 점. 간단히 말해 면적의 중심점이다. 클러스터 내에 세 개의 점이 있고, 각각의 좌표가 (0, 0), (1, 2), (2, 1) 이라면 centroid의 좌표는 (1, 1) 이다.
이를 따라 두 클러스터 사이의 거리는 두 centroid 사이의 거리로 정의한다.
그러나 비유클리드 공간에서는 centroid를 명확히 정의할 수 없기 때문에, 다른 방법을 사용한다. 클러스터 내에서 한 점을 clustroid로 정하고, 두 클러스터 사이의 거리는 두 clustroid 사이의 거리로 정의한다.
가장 적합한 clustroid를 정하기 위해서는 각 점들 간 거리의 최댓값을 최소화하는 점을 찾거나, 각 점들 간 거리의 평균을 최소화하는 점을 찾아야 한다.
