클러스터링(Clustering)이란? - 클러스터링 1

클러스터링 개념

주어진 데이터들을 비슷한 특성(유사성, 패턴)을 기반으로 분류해서 집단(클러스터)를 생성해주는 비지도 학습 기법

데이터에 존재하는 모든 특성들을 사용해서 분류, 군집 가능

 

클러스터링 목적

데이터 간의 유사성을 기준으로 내부적으로는 유사하고, 외부적으로는 서로 다른 집단(클러스터)을 형성하는 것

 

클러스터링 유형

• 데이터의 크기, 데이터의 차원, 클러스터 수 등에 따라서 적용하는 클러스터의 유형, 방식이 다양하다.
• 데이터의 종류에 따라서 적합한 클러스터링 알고리즘이 다르다.

 

다음은 기본적인 클러스터링의 다섯가지 방식이다. (평균 이동 클러스터링, 스펙트럼 클러스터링 제외)

 

중심점 기반 클러스터링

중심점(centroid)과 데이터 사이의 거리를 기반으로 데이터를 분할하는 클러스터링 유형

중심점(centroid) : 클러스터에 있는 모든 점(데이터)들의 평균, 중앙값

K-menas (K-평균) 알고리즘

중심점과의 거리를 기반으로 미리 지정한 K개의 클러스터로 데이터를 분할하는 알고리즘

중심점과 각각의 데이터들 사이의 거리를 반복적으로 계산해서 최적의 중심점, 클러스터를 찾는다.

 

과정

1. K 개의 중심점(centroid)을 가진 클러스터를 설정한다.
2. 데이터들을 가장 가까운 중심점의 클러스터에 할당한다.
3. 각 클러스터의 새로운 중심점을 계산한다.
4. 중심점이 더 이상 변하지 않을 때까지 2 ~ 3을 반복한다.

특징

• Hard Clustering 방식으로, 하나의 데이터가 정확히 하나의 군집에 할당된다.
• 클러스터들의 크기가 거의 동일하고 데이터 전체에 걸쳐 유의미한 이상값, 밀도 변화가 없을 때 잘 작동한다.
• 데이터가 고차원이거나 클러스터의 크기 또는 데이터 밀도 차이가 크면 분할이 잘 이루어 지지 않는다.
• 클러스터 내부의 모든 값의 평균값을 기반으로 중심값을 설정하기 때문에 이상값에 특히 민감하다.

 

계층적 클러스터링

데이터 속성의 근접성과 연결성을 기반으로 계층적 구조(트리 구조)로 데이터를 그룹화하는 클러스터링 유형

• 연결 기반 클러스터링이라고도 한다.
• 모든 차원에 걸쳐 데이터 포인트들이 서로에게 얼마나 근접해 있는지에 따라 클러스터를 결정한다.
  • 가까이 있는 객체일수록 멀리 있는 객체보다 더 밀접하게 관련되어 있다고 생각
• 클러스터 수를 지정할 필요 없이, 각 계층적 수준에서 자동적으로 클러스터의 그래프 네트워크 생성한다.
  • 계층적인 네트워크이기 때문에 부모노드는 하나뿐이지만, 자식 노드는 여러개 가능 (트리 구조)
• 중심점 기반 클러스터링과 다르게 클러스터 수(K)를 미리 지정하지 않고, 가까운 객체들과 서로 모여서 그룹화를 진행한다.

병합 클러스터링(상향식 접근)

작은 클러스터들을 큰 클러스터로 병합(집적)한다. (바텀업 방식)

• 각 데이터를 개별 클러스터로 시작해서, 가장 가까운 클러스터끼리 점점 합쳐가면서 하나의 클러스터로 만들어간다.
• 모든 클러스터와의 근접 행렬을 계산하고, 클러스터들을 연속적으로 병합하여 트리 형태의 구조를 생성한다.
• 모든 클러스터가 클러스터간의 유사성이 없거나, 낮은 상태의 클러스터 수준이 생성되면 종료한다.

특징

• 더 큰 클러스터 쪽으로 데이터, 클러스터들이 끌려들어가는 연쇄적 현상이 발생 가능하다.
  • 하나의 큰 클러스터로 편향된 결과 발생 가능성 높음
• 분할 방식에 비해서 속도가 훨씬 느리다.

분할 클러스터링(하향식 접근)

큰 클러스터를 작은 클러스터들로 분할한다. (탑다운 방식)

• 전체 데이터를 하나의 클러스터로 시작해서, 점점 나누어가며 여러개의 클러스터로 분리해간다.
• K-means 같은 평면 클러스터링 방법을 사용하여 데이터 세트를 먼저 분할하고, 오차제곱합(SSE)이 가장 큰 클러스터를 더 세분화해서 추가적으로 분할한다.
• 데이터 포인트를 트리형태의 구조로 연속적으로 분할한다.
• 트리의 계층 구조, 여러 클러스터의 균형 수준 측면에서 유연성을 높일 수 있다.

특징

• 개별 데이터 포인트까지 트리로 구성할 필요가 없는 데이터일 경우 병합 클러스터링 방식보다 속도가 더 빠르다.

 

분산(분포) 기반 클러스터링

클러스터 내부의 분산을 고려하여 분산이 가장 작아지도록 데이터를 분할하는 클러스터링 유형

• 확률적 클러스터링으로도 불린다.
• 클러스터 내부의 확률분포를 기반으로 데이터 요소들을 그룹화한다.
  • 중심점 기반 클러스터링 : 거리 매트릭(유클리드, 맨해튼 등) 기반

특징

• 군집 내 데이터가 서로 비슷하고, 클러스터 간에 뚜렷한 차이가 있도록 분할하는 데 중점을 둔다.
  • 응집도(cohesion)와 분리도(separation)가 크도록 분할을 진행
• 군집 내부 데이터들의 분산이 작을수록 좋은 클러스터로 판단한다.
• 최적의 클러스터 형성을 위해 각 차원에서 분포를 여러 번 적합시키기 때문에 연산 비용이 많이 들 수 있다.

GMM(Gaussian Mixture Model, 가우시안 혼합 모델)

데이터를 여러개의 가우시안 정규분포(Gaussian Distribution)의 혼합으로 모델링하고, 이를 활용해서 클러스터링을 진행하는 알고리즘

• 데이터가 매개변수를 가진 여러 가우시안 분포(정규분포)의 혼합으로 생성된다고 가정한다.
• 각 클러스터는 하나의 가우시안 분포(정규분포)로 표현되며 데이터는 각 클러스터에 속할 확률(probability)를 가진다.

과정

1. 가우시안의 개수(K)를 설정하고, 평균, 분산, 혼합 가중치 초기화
2. E-Step : 각 데이터가 각 클러스터에 속할 확률 계산
3. M-Step : 위 확률을 기반으로 모수(평균, 분산, 가중치) 업데이트
4. 수렴할 때까지 E-step 과 M-Step 반복

특징

• 클러스터가 타원형, 비대칭일 때도 잘 작동한다.
• Soft Clustering으로, 유연하게 값들을 분할 할 수 있다.
• 고차원 데이터, 복잡한 분포를 가지는 데이터, 비정규형 데이터에서는 부적합하다.

 

밀도 기반 클러스터링

데이터의 밀도(density)를 기준으로 분할하는 클러스터링 유형

• 데이터가 집중된 영역을 클러스터로 정의하고, 밀도가 낮은 영역을 경계(border), 이상치(outlier)로 정의한다.
• 유연하게 임의의 형태를 가진 클러스터를 탐지할 수 있다.
• 클러스터들이 특정 위치, 분포를 중심으로 정의되어 있지 않은 경우에 유용하다.
  • 다양한 형태, 크기, 밀도의 클러스터들을 발견 가능함
• 노이즈, 이상치가 있는 데이터를 사용할 때, 데이터 내의 클러스터 수에 대한 사전 지식이 없는 경우에 유용하다.

DBSCAN

데이터 포인트를 중심으로 전달된 반경 크기(ε) 안에 클러스터 구성 최소 데이터 개수(MinPts)보다 많은 데이터가 있으면 그 데이터 포인트를 공간 중심점(Core Point)으로 설정하고 클러스터를 생성하는 방법

과정

1. 임의의 점 선택, ε(eps) 반경 내 이웃 수 계산
2. 반경 내 이웃 수가 MinPts 이상이면 Core Point로 간주, 새 클러스터 생성
3. 해당 클러스터 안의 이웃 점이 또 다른 Core Point인지 확인하고 클러스터 추가 생성
4. 이웃 수가 MinPts 미만인 점은 Noise로 간주하거나, 다른 클러스터에 포함시킴
5. 모든 점이 클러스터가 정해지거나 Noise Point로 정해질 때까지 1 ~ 4 반복

특징

• 클러스터 개수(K)를 사전에 지정할 필요가 없다.
• 불규칙한 모양의 클러스터 탐지 가능하다.
• 고차원 데이터에서는 한계 존재가 존재한다.
• 매개변수에 대한 의존도가 높다.

개선사항

• 매개변수를 자동으로 지정해주는 HDBSCAN을 활용해서 더 유연한 밀도 기반 클러스터링 진행 가능하다.

 

격자 기반 클러스터링

고차원 데이터를 공간상에 격자(Grid)로 나눈 뒤 각 셀(shell)의 데이터 밀도를 기준으로 분할하는 클러스터링 유형

• 각 셀에 shell ID라는 고유 식별자를 할당하고, 셀 내의 모든 데이터 요소는 동일한 클러스터에 속한것으로 간주한다.
• 대부분의 클러스터링 방법에서 사용되는 인접 이웃 검색에 필요한 시간을 줄여준다.
  • 방대한 다차원 데이터 세트를 분석하는데 효율적
• 앞에 4가지 방식에 비해서 덜 사용되지만, 고차원 데이터 클러스터링에서 좋은 성능을 보일 수 있다.

STING (Statistical Information Grid, 통계정보 그리드)

데이터 공간을 계층적인 격자로 나누고, 각 셀(cell)의 통계 정보를 활용하여 클러스터링을 진행하는 방식

• 고해상도의 상위셀과 상위셀을 여러개로 나누어서 생성한 하위셀로 클러스터 연산 진행한다.

과정

1. 데이터를 포함하는 공간을 격자 형태의 셀들로 분할
2. 하위 셀들을 포함하는 상위셀을 생성해서 트리 구조 형태의 계층 구조 생성
3. 각 셀에 대한 데이터의 통계 정보 계산
4. 고밀도 영역 셀을 선택해 클러스터 형성
5. 필요에 맞게 셀을 더 세분화하거나 제외하면서 3 ~ 4 반복

특징

• 셀 단위 통계만 계산하면 되기 때문에 효율적이고 빠르다.
• 계층적 구조 덕분에 다양한 해상도로 클러스터링 가능하다.
• 격자 크기에 대해서 클러스터링 결과가 민감하다.
• 클러스터의 경계가 수평 또는 수직으로 정의되어야 하고, 직사각형의 클러스터 경계만 감지 가능하다.