주요 클러스터링 알고리즘 4가지 쉽게 이해하기

  공학자들은 수많은 데이터들을 처리하는 것에 익숙하다. 다양한 센서들 혹은 시뮬레이션 등의 도구(Tool)로 부터 입력받는 데이터들을 실시간으로 처리하거나 방대한 데이터들을 쌓아두었다가 한번에 처리하는 등의 상황에 여러차례 놓이곤 한다. 본 클러스터링은 이렇게 데이터를 처리하는 하나의 방법이라고 볼 수 있다. 

 

  이번 시간에는 다양한 데이터들을 알아서 특징점을 찾아주어 비슷한 내용의 데이터들을 하나의 군집으로 나누어 주는 알고리즘인 Clustering Algorithm 에 대해 알아보도록 하겠다. 

 

  본 글은 'The 5 Clustering Algorithms Data Scientists Need to Know'의 글을 해석하며 정리하는 과정을 통해 쓰여짐을 미리 밝힌다. towardsdatascience.com/the-5-clustering-algorithms-data-scientists-need-to-know-a36d136ef68

The 5 Clustering Algorithms Data Scientists Need to Know

 

 

---

 

주요 클러스터링 알고리즘 4가지 쉽게 이해하기

 

Easy Understanding of The Main 7 Clustering Algorithms

 

---

 

1. K-Means Clustering 알고리즘 (K평균 알고리즘)

 

  Kmeans 알고리즘은 가장 잘 알려진 클러스터링 알고리즘이다. 코드의 이해와 구현이 비교적 쉽다는 특징이 있다. 

K-means 알고리즘의 시각화[1] 

알고리즘의 순서

ⓐ 군집의 개수를 선정하고 랜덤하게 초기 중심점을 잡고 시작한다. 초기 입력변수인 군집의 개수를 알아내기 위해서는 데이터를 간단하게 살펴보고 군집을 알아내는 과정을 거치는것이 좋다. 

 

ⓑ 각각의 데이터 포인트들은 각각의 군집 중심점들과의 거리(유클리드거리)를 계산함으로써 분류된다. 그리고 나서 포인트가 어느 그룹의 중심에 가깝게 있는지를 가려낸다.

 

ⓒ 분류된 포인트들에 기반하여, 그룹의 벡터들에서 평균을 계산함으로써 군집의 주임을 다시 계산한다.

 

ⓓ ⓐⓑⓒ의 과정을 반복과정에 의해서 변화가 크지 않아질때까지 계속 반복한다. (랜덤하게 군집의 중심을 초기화하는 과정을 통해 세밀한 조정도 가능하다.)

 

알고리즘의 장단점

  꽤나 빠르다는 장점이 있다. 포인트와 그룹간의 거리계산만을 하고 있는것이기 때문에 꽤나 적은 계산량을 가진다고 할 수 있다. 그러므로 선형적인 복잡도 즉 O(n)의 계산복잡도를 가진다.

 

  반면에, K-Means알고리즘은 두가지 정도의 단점을 가진다. 첫째로, 군집의 개수를 정해주어야 한다는 점이다. 항상 데이터들에서 군집의 개수를 대강이라도 판별할 수 있는것이 아니다. 때문에 알고리즘의 사용자가 통찰력을 갖고 군집의 개수를 정해주어야 하는 단점이 있다. 둘째로, 랜덤하게 정해진 초기 중심점때문에 결과가 매번 달라질 수 있다. 다른 클러스터링 결과는 반복적이지 않고 일관성에서 부족함을 보인다.

 

---

2. K-Medians Clustering 알고리즘 (K중앙값 알고리즘)

 

  K-Medians 알고리즘은 K-Means 알고리즘과 비슷하지만 한가지 과정에서 차이를 보이는 또 다른 클러스터링 알고리즘이다. Kmeans 알고리즘이 군집의 중심점(도심)을 평균으로 구하는것과 다르게  K-Median 알고리즘은 중앙값을 이용한다는 특징을 가진다. 

 

*평균값과 중앙값의 차이

 

---

3. Mean-Shift Clustering 알고리즘 (평균 이동 군집화 알고리즘)

 

  Mean shift 클러스터링은 미끄러지는 창을 기반으로 하여 데이터 포인트들의 밀집 지역을 찾기를 시도하는 알고리즘이다. 본 알고리즘은 도심 기반의 알고리즘이다. 본 알고리즘의 목표는 각각의 군집의 도심점들을 위치시키는 것이다. 본 목표는 도심점의 후보군들을 계속 업데이트하면서 도심점이 미끄러지는 창 안의 포인트들의 평균이 되도록 하는 것이다. 그런 다음 이러한 후보 창을 후처리 단계에서 필터링하여 거의 중복된 후보들을 제거하여 중앙점과 해당 그룹의 최종 집합을 형성한다.

Mean-shift Clustering 알고리즘의 시각화[1]

알고리즘의 순서

ⓐ 평균 이동을 설명하기 위해 위의 그림처럼 2차원 공간의 점 집합에 대해 알아보자. 본 알고리즘은 임의적으로 선택된 C 지점에서 일정 반지름을 가지는 원형 슬라이딩 창과 그 중심인 중요 포인트로 시작한다. 평균 이동이 수렴될 때까지 각 단계에서 이 중요 포인트를 고밀도 영역으로 반복적으로 이동하는 것을 포함하는 알고리즘이다.

 

ⓑ 매번 반복할 때마다 미끄러지는 창은 중앙점을 창 내의 포인트들의 평균으로 이동시킴으로써 더 높은 밀도의 영역으로 이동된다. 미끄러지는 창 내의 밀도는 미끄러지는 창 내의 포인트 수에 비례한다. 결과적으로 창의 점의 평균으로 이동함으로써 점 밀도가 더 높은 영역으로 점차 이동하게 된다.

 

ⓒ 우리는 각각의 반복과정이 가져오는 변화가 중 내부의 더 많은 포인트를 수용할 수 있는 방향이 없을 때까지 평균에 따라 슬라이딩 윈도우를 계속 이동한다. 더 이상 밀도(창 내의 포인트 수)를 증가시키지 않을 때까지 원을 계속 이동시킨다.

 

ⓓ ⓐ,ⓑ,ⓒ의 과정을 창 내의 밀도가 가장 많아질때까지 여러개의 미끄럼 창이 각각 가장 높은 밀도를 가질때까지 반복한다. 결과적으로 미끄럼 창이 위치한 곳에서 점들간 군집을 형성함을 확인하게 된다.

 

Mean-shift Clustering 전체 실행 과정 (여러개의 군집)[1]

 

알고리즘의 장단점

  K-Means 알고리즘과 대조되게, 군집의 개수를 지정해 줄 필요가 없고 평균이동 알고리즘이 알아서 군집의 개수를 알아낸다. 본 특징은 아주 큰 장점이다. 군집이 최대의 밀도에서 수렴한다는 사실이 굉장히 매력적이다. 데이터가 어떻게 형성되는지의 과정이 꽤나 이해하기 직관적이고 잘 맞는다. 본 알고리즘의 단점은 창의크기 즉 반지름의 결정이 중요하게 다뤄지지 않는다는 점이다.

---

4. DBSCAN (Density-Based Spatial Clustering of Applications with Noise)

 

  DBSCAN은 평균 이동과 유사하지만 몇 가지 주목할 만한 장점이 있는 밀도 기반 클러스터 알고리즘이다. 

알고리즘의 순서

ⓐ DBSCAN은 방문하지 않은 임의의 포인트에서 시작한다. 거리 앱실론을 통해서 이웃하는 점을 추출해나간다. 

 

ⓑ 충분한 숫자의 점들이 이웃으로 위치하고 있다면, 군집화 프로세스는 현재 데이터 포인트가 새로운 클러스터의 첫 지점이 되도록 한다. 충분하지 않은 숫자의 이웃점이 위치한다면 노이즈로 분류될 것이다. 이 모든 두 과정에서 본 점들은 방문된 점으로 분류된다.

 

ⓒ 새 군집의 첫번째 점에서 거리 앱실론 내 지점도 동일한 군집의 일부가 된다. 근방의 모든 지점의 포인트를 동일 군집으로 속하도록 하는 이 과정은 그룹에 추가된 모든 새 지점에서도 동일한 과정을 거치게 되며 반복된다.

 

ⓓ 이 ⓑⓒ의 과정을  군집내의 모든 포인트가 결정될때까지 라벨되어질때까지 반복한다.

 

ⓔ 현재 군집에 관한 분류가 끝났을때, 앱실론 거리 내의 새로운 방문되지 않은 포인트가 모두 처리되면, 클러스터 혹은 노이즈로 분류 처리가 된다. 모든 점들이 방문되어 질때까지 이 과정이 반복되고 마지막 방문으로 처리될때엔 각각의 포인트는 클러스터 혹은 노이즈로 분류되게 될 것이다.

 

알고리즘의 장단점

  DBSCAN은 다른 알고리즘에 비해 큰 강점을 보인다. 첫째로, 미리 정해진 개수의 군집을 아예 필요로 하지 않고 노이즈를 검출해 내며 Mean-Shift(평균이동) 과 다르게 데이터 점이 아주 어려울때에도 군집에 훌륭하게 포함시킨다. 추가적으로 제멋대로인 사이즈와 모양도 꽤 훌륭하게 군집화를 이뤄낸다.

 

  DBSCAN의 주요 단점은 클러스터가 큰 밀도를 가지고 있을때 좋은 성능을 발휘하지 못한다는 것이다. 그 이유는 밀도가 변동될 때 인접 지점을 식별하기 위한 거리 임계값 앱실론 및 최소 점간 거리의 설정이 클러스터마다 다르기 때문이다. 이 단점은 매우 높은 차원의 데이터에도 적용되는데, 거리 임계값 앱실론이 측정하기 어렵게 되기 때문이다.

 

DBSCAN 전체 실행 과정[1]

 

 

---

출처

[1] George Seif, The 5 Clustering Algorithms Data Scientists Need to Know, towardsdatascience.com/the-5-clustering-algorithms-data-scientists-need-to-know-a36d136ef68 (2021.01.21)

 

프랑스 트루아 지역의 한 술 가게