1. 군집분석이란?

사전에 정의된 클래스가 없는 비지도학습의 종류 중 하나로, 관측된 여러 개의 변수 값에서 유사성에만 기초하여 n개의 군집으로 집단화한 뒤, 그 군집의 특성을 분석하는 다변량 분석 기법이다.

군집 : 유사한 데이터 개체들의 집합체
군집화 : 군집으로 묶는 행위

1.1 주요 목적

• 주로 데이터 분포에 대한 인사이트를 얻기 위해 사용
• 다른 데이터마이닝 알고리즘 작업을 위한 사전 작업 단계

1.2 좋은 군집의 조건

💡좋은 군집이란?
= 유사성에 따라 데이터가 잘 분류된 상태
군집 내의 데이터 간의 유사도는 높고, 군집 간의 유사도는 낮을 때

• 군집 내 데이터 간 유사도 높음 = 비슷한 개체끼리 잘 모여있다
• 군집 간의 유사도가 낮다 = 군집 간 거리가 멀다

따라서 군집 간의 거리가 멀수록 군집화가 잘 된 것이다.
여기서 유사도는 거리를 의미한다.

---

2. 유사도(=거리) 측정

2.1 군집 간 거리 계산

연속형 : 유클리드, 맨하탄, 민코프스키 등을 사용
명목형 : 전체 속성 중 일치하는 속성의 비율, 자카드 계수 이용
순서형 : 값에 순위를 매겨 순위에 대해 상관 계수를 구함

• 유클리드 거리
  

• 맨하탄 거리
  

• 민코프스키
  

  $[(x_if-x_jf)^m]^{1/m}$

  m차원 민코프스키 공간에서의 거리
  m=1 일 때, 맨하탄 거리와 동일
  m=2 일 때, 유클리드 거리와 동일

2.2.2 명목형 변수의 유사도 측정

• 단순 매칭
  유사도 = $sim(i,j) = 1-d(i,j)= (p-m)/p$
  m = 두 객체 간의 매칭 수
  p = 객체 전체 속성 수

• 자카드(Jarcad) 계수
  
  두 집합 사이의 유사도를 측정하는 방법 중 하나로, 0과 1 사이의 값을 가지며 두 집합이 같의면 1의 값, 공통의 원소가 없으면 0의 값을 가진다.
  위의 그림에서 집합 A는 4개의 원소, 집합 B는 5개의 원소를 가진다.

두 집합의 합집합 원소 개수는 7개이고, 두 집합에 동일하게 포함된 원소는 2개이다.
자카드 계수는 교집합 / 합집합 으로 $2 / 7 = 0.286$ 의 유사도를 가진다.

2.2.3 서열형 변수의 유사도 측정

속성값이 순서를 가질 뿐 연속하는 값 간의 차이를 알 수 없다.
→ 1단계 : 속성 순서를 숫자 속성으로 변경해야한다.
예를 들어 만족도 조사에서 매우 불만족, 불만족, 보통, 만족, 매우 만족 → 1,2,3,4,5로 변경

2단계 : 각 값들을 [0,1] 범위로 min-max 정규화시킨다.
3단계 : 정규화한 값을 연속형 변수의 거리 측정 방법을 사용하여 유사도를 구한다.

---

3. 군집분석의 종류

3.1 K-means

k=3으로 설정하여 3개의 군집으로 나눈 후 군집마다 최적의 중심을 찾기 위해 평균 거리 d를 구하고 c1, c2, c3의 위치를 반복해서 조정한다.

3.1.1 개념

• k는 군집 수, means는 평균
  말 그대로 각 군집의 평균(mean)을 활용하여 K개의 군집으로 묶는다는 의미다.
• 초기 값으로 k개의 군집을 지정하고 각 개체를 가까운 초기 값에 할당하여 군집을 형성
• 각 군집의 평균을 재계산하여 초기값을 갱신하는 과정을 반복하여 k개의 최종 군집 형성

3.1.2 군집화 과정

① 군집의 수 k 결정
② 데이터를 가장 가까운 군집 임의의 중심에 할당
여기서 중심은 각 학습 데이터가 자신이 속한 클러스터를 결정하는데 기준점이 된다.
③ 각 클러스터 마다 자료들의 평균을 계산하여 군집의 초기 중심 결정
④ 학습이 진행되면서 각 클러스터마다 최적의 중심으로 이동
⑤ 군집 중심이 변화가 거의 없을 때까지 (=재배치 하지 않을 때까지) 2~4번 단계를 반복 수행

⭐여기서 군집의 최적의 중심을 찾는게 K-means의 핵심 !⭐

3.1.2 K값 설정

K = '내가 몇 개의 그룹을 만들 것인가?'를 지정
K-means에서 다루는 레이블이 없는 데이터에서는 몇 개의 클러스터가 존재하는지 모르기 때문에 분류한 클러스터의 수를 미리 정한다.
k값을 조금씩 늘려가며, 특정 k 이후에 cost가 변하지 않는 구간이 존재하는 경우, 그 때의 k를 최적의 k값으로 선정한다.

3.1.3 엘보(Elbow) 차트

적절한 군집 수를 결정하기 위해서는 k의 개수를 변경해가면서 오차제곱합(SSE)을 Elbow 차트로 시각화한 후 SSE가 급격히 감소하다 완만해지는 시점에서의 k값을 적정 군집 수로 판단한다.
K값을 조금씩 늘려가며 즉, 군집의 수가 늘어날수록 SSE는 당연히 낮아질 수 밖에 없기 때문에 무조건 SSE가 작다고 좋은 것은 아니다. K-means의 목표는 가장 작은 k로 SSE를 최소화하는 것이다.

3.1.4 장단점

장점

• 명확하고 직관적이다.
• 학습 데이터 계산이 빠르다.

단점

• 오목한 형태의 군집 모델은 특성을 구별해내는데 어려움을 보인다.
  중심으로부터 거리를 기반으로 군집화하기 때문에 구형으로 뭉쳐져 있는 볼록한 데이터셋에는 비교적 잘 적용되는 편이다.
• 이상치와 노이즈에 매우 민감하게 반응한다.
• 사전에 클러스터 개수를 정하는 것이 초기 중심을 어떻게 선택하느냐에 따라 분류에 큰 영향을 미치기 때문에 단점이라 할 수 있다.

3.2 DBSCAN (Destiny Based Spatial Clustering Of Application with Noise)

3.2.1 개념

K-means와 같이 비지도학습 모델이며, 노이즈 및 아웃라이어 데이터 식별에 강한 군집 모델이다. DBSCAN 모델도 계층적 군집처럼 초기에 클러스터 개수를 정하지 않는다.
DBSCAN이 제안하는 새로운 군집화 개념에 의하면 '밀도있게 연결돼 있는' 데이터 집합은 동일한 클러스터라고 판단한다. 여기서 '밀도있게 연결돼 있다'가 DBSCAND의 핵심이다.

여기서 밀도는 무엇을 나타낼까?

• 자기를 중심으로 반지름 R안에 있는 다른 좌표점의 개수이다. 예를 들면 데이터 포인트 A 중심으로 반지름 R안에 A 제외 3개의 좌표점이 있다면 밀도는 3이다.
• 어떤 좌표점의 밀도가 최소 좌표점의 개수(=Minpts) 이상이면 이 좌표는 클러스터를 형성할 수 있다.

밀도있게 연결돼 있다?

• DBSCAN은 일정한 밀도를 가지는 데이터의 무리가 마치 체인처럼 연결돼 있으면 거리의 개념과 관계없이 같은 클러스터로 판단한다.

3.2.2 DBSCAN의 데이터 형태

DBSCAN은 데이터 형태로 코어(Core), 경계(Border), 노이즈(Noise) 3가지를 가진다.

학습 데이터의 전체 집합인 X가 있다. 여러 개의 데이터 포인트 중 좌표점 A의 밀도가 Mintus 이상이면 클러스터를 형성할 수 있고 A를 코어라고 한다.
만약 좌표점 B가 A의 군집 영역 내에 존재하고, B의 중심으로부터 반지름 내에 Minpts(A의 Minpts는 4) 만큼의 점이 존재하지 않으면 B는 A의 경계가 된다.
만약 좌표점 C가 코어 A의 영역 내에 존재하지 않으며, C를 중심으로 반지름 내에 Minpts만큼의 점이 존재하지 않으면 노이즈라고 정의한다.

3.2.3 군집화 과정

DBSCAN에서 군집화 과정은 코어가 중심이 된다.
쉽게 말하면 코어 → 코어 → 코어 → ... →경계 로 가는 방향성을 띈다 (경계에서 코어로 가지는 않는다!)

① 코어 정의 & 주변의 이웃 데이터와 함께 하나의 레이블을 가지는 클러스터 구성
② 이후 반지름 내에 있는 이웃 점들이 코어인지 아닌지 판단
③ 코어이면 반복, 경계이면 진행 중단
④ 모든 점들을 다 판단했다면 중단하고 확보된 클러스터를 결과로 반환

이렇게 진행되는 기준을 '밀도 접근성'이라 한다.
= 코어의 기준을 만족할 때만 그 이웃 점으로 확장하여 계속하여 군집화를 진행해가는 방법

3.2.4 장단점

K-mean와 비교했을 때, 데이터가 동심원 혹은 반달 모양으로 모여있는 경우에 k-means는 클러스터 중심으로부터 거리를 비교하기 때문에 클러스터의 특성을 잘 반영하지 못하여 분류 성능이 떨어지지만 DBSCAN은 데이터들이 밀도 있게 연결돼 있으면 동일한 클러스터로판단하기 때문에 분류 성능이 더 좋다.
하지만 밀도 반지름과 최소 이웃 수 (Minpts)가 문제의 특성에 따라 민감하게 작용하여 분류에 영향을 미친다는 단점을 가진다.

3.3 계층적 군집분석 (Hierarchical clustering)

3.3.1 개념

유사한 특성을 지닌 데이터를 군집화하며 이진 트리 형태로 만들어가는 방법이다. 이를 통해 완성된 이진 트리를 계통수라고 하며, K-means와 달리 초기에 클러스터의 개수를 미리 정할 필요가 없다.

3.3.2 형성 방법

💡 병합적 군집 (agglomerative)

• 작은 군집으로 시작하여 군집을 병합시키는 상향식 방법
• 처음에 데이터셋의 모든 점을 군집의 원점으로 시작해 유사한 클러스터끼리 합쳐 나가면서 원하는 클러스터 개수가 될 때까지 진행
  즉, 최초에는 자기 자신이 유일한 구성 요소인 클러스터인 상태에서 시작한다.

💡 분할적 군집 (divise)

• 큰 군집에서 시작하여 군집을 분리해 나가는 하향식 방법
• 병합적 방법과 반대로 가장 관련성이 없는 관계를 분리하는 작업을 반복
• 모든 클러스터의 크기가 1이되면, 즉 클러스터가 단일 데이터값을 가지게 되면 군집을 완료한다.
• 상위 클러스터에서 잘못된 결정이 하위 클러스터로 파급되는 정도가 크다는 단점을 가진다.

3.3.3 군집 간 거리 측정 방법

군집 간의 연결 방법에 따라 군집의 결과가 달라진다.

연결법	설명
최단연결법	각 군집의 최솟값을 기준으로 두 군집의 최단 거리를 이용
최장연결법	각 군집의 최댓값을 기준으로 두 군집의 최장 거리를 이용
중심연결법	두 군집의 중심 간의 거리 측정
평균연결법	모든 항목에 대한 거리 평균 이용
와드연결법	군집 내의 오차 제곱합에 기초 (거리 이용x)

3.3.4 계통도 (Dendrogram)

군집의 결과를 보여주는 그림으로, 각 개체는 단 하나의 군집에만 속한다. 이는 항목 간, 군집 간의 거리를 알 수 있고, 유사도를 파악하여 군집의 견고성을 해석할 수 있다.