공간 클러스터링: 종류와 사용

* 이 글은 아래 원문을 번역한 글임을 밝힙니다. 

https://towardsdatascience.com/geospatial-clustering-kinds-and-uses-9aef7601f386

Geospatial Clustering: Kinds and Uses

 

모든 종류의 공간 클러스터링 사례와 사용법을 자세하게 리뷰한다. 

 

Photo by Dennis Kummer on Unsplash

공간 분석은 공간적 객체 세트를 "군집(clusters)"으로 불리는 그룹으로 모으는 방법을 말한다. 군집 안의 객체는 서로 비슷한 특성을 가지는 반면 군집들은 매우 다른 특성을 보인다. 군집의 목적은 공간과 비공간 속성 사이의 관계를 드러내고 일반화하는 것이다. 

 

간단한 예를 통해 공간 군집을 이해해보자. 

 

"당신이 대도시(metro city)의 푸드 딜리버리 체인의 대표라고 가정해보자. 당신은 고객의 선호를 알아내어 사업의 규모를 확장하기 원할 것이다. 모든 고객의 세부사항을 보는 것은 불가능하므로 당신은 고객을 그룹으로 분리하고, 각 그룹/군집에 대한 사업 계획을 전략화한다."

 

공간 군집은 크게 다섯 가지 종류로 구분할 수 있다: 

 

1. Partition clustering

2. Hierarchical clustering

3. Fuzzy clustering

4. Density-based clustering

5. Model-based clustering

 

Locale(아마도 글 쓴이가 속한 회사를 지칭하는 듯)에서는 자산이 이동하는 모든 사업에서 위치 데이터에 접근할 수 있도록 최선을 다하고 있다. 지금부터 클러스터링의 유형을 자세히 알아보고 각각에 대해 이해해봅시다.

 

Partition Clustering

Partition clustering은 데이터 포인트를 겹치지 않는 하위 셋(subsets)로 나눈다. 각 데이터 포인트는 정확히 하나의 하위 셋에만 속한다. 다음의 두 가지 요건을 만족하도록 분류한다: 

 

1. 각 데이터 포인트는 단 하나의 군집에만 속한다. 

2. 각 군집은 적어도 하나의 데이터 포인트를 가진다. 

 

Partition clustering은 세 가지 유형으로 나뉜다: K-means 클러스터링, K-medoids clustering/PAM and CLARA (Classification Large Application)

 

1) K-means Clustering

K-means clustering은 분할 방법으로 데이터 셋을 속성에 따라 몇 개의 파티션 세트로 분해한다. 자세한 내용은 여기를 참고하라(here).

 

Source (https://towardsdatascience.com/k-means-data-clustering-bce3335d2203)

 

2) K-medoids Clustering/PAM

K-medoids 클러스터링은 K-means 클러스터링과 같은 분할 방법이다. medoid는 클러스터의 다른 모든 포인트와 가장 적은 유사성을 갖는 클러스터 지점이다. PAM에 대해 더 자세한 내용은 다음을 확인하세요(here). 

 

Source (https://www.mathworks.com/help/stats/kmedoids.html)

3) CLARA

CLARA는 대규모 데이터 셋에 대한 PAM 방법의 확장이다. 전체 데이터 셋에 대한 medoids를 찾는 대신 크기가 고정된 데이터의 작은 샘플을 고려하고 알고리즘ㅇ르 적용해 샘플에 대한 최적의 medoids 셋을 생성한다. 

Source (https://www.datanovia.com/en/lessons/clara-in-r-clustering-large-applications/)

 

사용 사례: 

일반적으로 파티션 기반 클러스터링은 데이터에 명시적으로 레이블이 지정되지 않은 그룹을 찾는 데 사용된다. 새로운 데이터 포인트를 올바른 군집에 할당하는 데 도움이 된다. 기업은 파티션 기반 클러스터링을 사용해 구매 내역을 세분화하고, 판매 활동별로 인벤토리를 그룹화하고, 헬스 모티터링에서 그룹을 식별하는 등의 작업을 수행한다. 

Uber using clustering for intent detection which they use for their one-click chat/suggested reply system. Source (https://syncedreview.com/2019/07/08/how-uber-lyft-use-ai-to-improve-ride-experience/)

 

Hierarchical Clustering 

계층적 클러스터링은 파티션 기반 클러스터링과 같은 군집 방법이지만 데이터 포인트를 분류하는 방식이 다르다. 먼저 각 데이터 포인트를 별도의 클러스터로 간주한다. 그런 다음 가까이 있는 가장 유사한 클러스터를 병합하고, 이를 모든 클러스터가 병합될 때까지 반복한다. 다음의 두 가지 유형이 있다. 

 

Agglomerative Hierarchical Clustering (응집 계층적 클러스터링)

이 작업은 포인트/클러스터의 근접 행렬이 계산되는 간단한 알고리즘과 함께 작동한다. 매 반복 작업 시 가장 가까운 포인트/클러스터가 병합되고 근접 행렬이 업데이트 된다. 이것은 하나의 클러스터 또는 k-클러스터가 형성될 때까지 계속된다. 이 방법은 "상향식(bottom-up)" 접근 방식으로 간주될 수 있다. 

Source (https://www.datanovia.com/en/lessons/agglomerative-hierarchical-clustering/)

Divisive Hierarchical Clustering (분할 계층적 클러스터링)

이 방법은 응집 클러스터링과 반대로 작동한다. 처음에 모든 데이터 포인트가 단일 클러스터에 속하게 되고, 반복하면서 유사하지 않은 데이터 포인트를 분리시킨다. 분리된 각 데이터 포인트는 개별 클러스터로 간주되며, k-클러스터가 생길 때까지 계속된다. 이는 "하향식(top-dow)" 방식으로 간주될 수 있다. 

Source (https://www.datanovia.com/en/lessons/divisive-hierarchical-clustering/)

사용 사례:

계층적 클러스터링은 계산 비용이 비싸지만(computationally expensive) 직관적인 결과를 생성한다. 계층적 클러스터링은 많은 가정을 필요로 하지 않기 때문에 현재 데이터에 대해 많이 알려지지 않은 경우에 유용하다(탐색적 연구?). 계층적 클러스터링이 광범위하게 사용되는 현실 시나리오 중 하나는 전염병 확산 중 바이러스 매핑과 은행 산업 또는 소매 산업의 고객 세분화이다. 

Using hierarchical clustering to cluster US Senators into their respective parties. Reds are Republicans, Blues are Democrats, Blacks are independent  [Source] (https://towardsdatascience.com/hierarchical-clustering-and-its-applications-41c1ad4441a6)

 

Fuzzy Clustering

퍼지 c-means 군집에서는 데이터 포인트의 중심을 찾은 다음 형성된 클러스터가 일정해질 때까지 주어진 중심에서 각 데이터 포인트의 거리를 계산한다. 데이터 포인트를 부분적으로 둘 이상의 클러스터로 분류할 수 있다는 점에서 파티션 기반 클러스터링과 차이가 있다. 

Fuzzy clustering of satellite imagery [ Source ] (https://www.researchgate.net/figure/Results-of-multi-spectral-satellite-images-clustering-FCM-a-FCoC-b-IVFCoC-c_fig5_303600590)

모든 데이터 포인트는 이론적으로 0과 1 사이의 membership function을 가진 모든 그룹에 속할 수 있따. 0은 데이터 포인트가 클러스터의 중심에서 가능한 가장 먼 지점에 있고 1은 데이터 포인트가 중심에서 가장 가까운 곳을 의미한다. 

 

사용 사례: 

퍼지 클러스터링은 이미지를 분할하거나 위성 이미지에서 물, 초목 및 암석 영역을 분할하는 것이 목표인 경우에 유용하다. 클러스터의 수를 선험적으로 결정할 수 없는 경우에 유용하다. 이 경우 경계가 약한 클러스터가 병합될 수 있다. 퍼지 클러스터링은 각 포인트에 대해 각 클러스터에 속하는 확률을 계산하기 때문에 K-means에 비해 computationally expensive하다. 

 

Density-based Clustering

밀도 기반 클러스터링은 밀도가 높은 영역을 그룹화하고 밀도가 낮은 영역과 분리하는 방식으로 작동한다. 가장 잘 알려진 밀도 기반 클러스터링 알고리즘은 DBSCAN 알고리즘(노이즈를 적용한 밀도 기반 공간 클러스터링)이다. 밀도는 다음과 같이 두 가지 매개변수를 사용하여 계산된다. 

 

1. EPS: 데이터 포인트 주변의 이웃을 정의한다. 즉, 두 포인트 사이의 거리가 eps 보다 작거나 같으면 이웃이라고 한다. 

2. MinPts: 이웃을 형성하는 데이터 포인트의 최소 갯수를 정의한다. 데이터 셋의 크기와 MinPts의 값은 정비례한다. 

 

DBSCAN 알고리즘은 모든 포인트를 방문하여 EPS 내에 MinPts가 포함되어 있으면 클러스터 형성이 시작된다. 다른 모든 점은 노이즈로 정의된다. 이 프로세스는 밀도 연결 클러스터가 형성될 때까지 계속되며, 이후 새로운 포인트에서 새로 시작된다. 

Left figure: Traditional clustering; Right figure: DBSCAN clustering (DBSCAN allows points to take up any shape or dimensionality to form clusters )

사용 사례:

DBSCAN은 주로 평면 공간에서 클러스터링에 사용된다. 자연 재해의 영향을 매핑하거나 도시의 기상 관측소 위치를 플로팅하는 데 사용하면 좋을 결과를 얻을 수 있다. 데이터가 비이산(non-discrete) 포인트로 구성되어 이상치(outliers)를 처리하는 데 좋은 경우에도 사용할 수 있다. 추천 엔진/시스템은 DBSCAN을 사용하여 고객에게 제품/쇼를 추천한다. 

 

Model-Based Clustering:

이 클러스터링 방법은 클러스터링을 위해 특정 모델을 사용하고, 데이터와 모델 간의 적합성을 최적화하려고 시도한다. 모델 기반 클러스터링 접근 방식에서 데이터는 각각 다른 클러스터를 나타내는 확률 분포가 혼합된 것으로 간주된다. 즉, 각 구성 요소가 서로 다른 클러스터를 나타내는 확률 분포가 혼합되어 데이터가 생성된다고 가정한다. 각 구성 요소(즉, 클러스터)는 정규 분포 또는 가우스 분포로 모델링된다. 

 

기대 최대화(expectation-maximization)는 잘 알려진 모델 기반 클러스터링 알고리즘이다. 특정 클러스터링 알고리즘은 데이터가 모델을 따를 때 잘 작동한다고 알려져 있다. 

 

사용 사례: 

클러스터의 경계가 약하고 데이터 포인트가 클러스터 간에 혼합 membership을 갖는 경우 유용하다. 또한 클러스터 공분산 측면에서 훨씬 더 유연하다. 이 경우 클러스터 할당에 매우 유연하며, 클러스터는 분포에 따라 어떤 모양이든 취할 수 있다.