5.5 군집분석

1. 군집분석이란?

 대상들의 유사성을 측정하여 유사성이 높은 집단을 분류하고, 서로 다른 군집에 속한 객체의 상이성을 규명하는 분석 방법으로, 대상을 여러개의 배타적인 집단으로 나누는 것으로 군집분석 방법에 따라 차이가 날 수 있다.
 대상들의 거리를 측정하여 군집을 나누게 된다.
 
 
 우리가 공부하면서 군집분석과 요인분석, 판별분석과 헷갈릴 수 있다! 어떤 차이점이 있을까?

• 요인분석은 유사한 변수들을 함께 묶어주는 것!
• 판별분석은 집단이 나누어진 상태에서 새로운 데이터가 있을 때, 기존에 나누어진 집단 중에 할당하는 것이 목적이다!

 
 

2. 거리

군집분석은 대상간에 거리를 측정하여 군집을 나눈다고 했는데, 거리를 측정하는 방법이 무엇이 있는지 살펴보자.
거리 측도는 데이터와 데이터간 유사성을 보는 군집분석 뿐만 아니라 변수와 변수간 관계를 보는 다변량 통계 분석에서도 기본기가 되는 중요한 내용이다.
 

연속형 변수간 거리 측정 방법

• 유클리디안 거리(Euclidean Distance) : 가장 많이 사용하는 거리이며, 통계적 개념이 내포되지 않아 변수들의 산포는 고려되지 않음. L2 거리라고도 함. 피타고라스 정리에 의해 구할 수 있다. 아래 그림에서 초록선을 의미함
  • $d(x,y) = \sqrt{(x_{1}-y_{1})^{2}+...+(x_{p}-y_{p})^{2}}$
• 표준화 거리(Statistical Distance) : 표준편차로 척도 변환 후, 유클리디안 거리 계산하여 분산의 차이로 인한 왜곡을 피할 수 있다.
  • $ d(x,y) = [(X_{r}-X{s})]^{T}D^{-1}(X_{r}-X{s})]^{1/2} , D = diag( s_{11} , ..., s_{pp} )$
• 마할라노비스 거리(Mahalanobis Distance) : 통계적 거리 개념이 포함되어 산포와 공분산(상관성) 구조를 함께 고려된 표준화 거리로 사전 지식 없이는 표본공분산 S를 사용할 수 없어 사용이 곤란
  • $ d(x,y) = [(X_{r}-X{s})]^{T}S^{-1}(X_{r}-X{s})]^{1/2} $
• 체비셰프 거리(Chebyshev Distance) : 두 벡터 x좌표 차이와 y좌표 차이 중 가장 큰 값을 갖는 거리
• 맨하탄 거리(Manhattan Distance) : 맨하탄 도시에서 건물에서 건물을 가기 위한 최단 거리를 구하기 위해 고안된 거리로 아래 그림에서 파란색,노란색,빨간색 선을 의미함
  • $d(x,y) = |x_{1}-y_{1}|+...+|x_{p}-y_{p}|$ 

    

• 캔버라 거리(Canberra Distance) : 두 벡터 사이의 차이에 대한 절대값을 두 벡터의 합으로 나눈 값을 모두 더하여 구하는 방식
• 민코우스키(Mindowsk Distance) : 맨하탄과 유클리디안 거리를 한번에 표현한 공식

  • 

 

범주형 변수간 거리 측정 방법

• 자카드 거리 = 1- 자카드 유사도(자카드 계수) 
  • 자카드 유사도 : 교집합을 합집합으로 나눈 개념
    • 예) A : 삼성전자, 테슬라, LG전자, 카카오, 펄어비스 / B : 삼성전자, 카카오, 넷마블, 현대자동차, 셀트리온
      • 교집합 = 2(삼성전자, 카카오) , 합집합 = 8 = 5+5-2
      • 자카드 유사도 = 2/8 = 0.25 

    • 

• 코사인 거리 : 문서 유사도를 기준으로 분류 혹은 그룹핑 할 때 사용
  • 코사인 유사도 : 두 벡터 내적의 코사인 값을 이용

  • 

 

3. 계층적 군집분석

위에서 살펴본 거리의 개념을 활용하여 개체간의 군집을 형성하는 방법들을 알아보고자 한다.
그 중에서 계층적 군집 방법은 Bottom up(합병형) 과 Top-Down(분리형) 방법이 있다.
 

0. 군집화 단계

1. 거리 행렬 기준으로 덴드로그램 그리기
2. 덴드로그램 최 상단부터 가로선 그어 군집 개수 선택
3. 적절한 군집수 선정

 

1. 최단연결법(Single Linkage)

n*n 거리 행렬에서 거리가 가장 가까운 데이터를 묶어서 군집 형성
군집과 군집 또는 데이터와의 거리를 계산할 때 최소거리(Min) 거리로 계산하여 거리행렬 수정
 

2. 최장연결법(Complete Linkage)

군집과 군집 또는 데이터와의 거리를 계산할 때 최장거리(Max)를 거리로 계산하여 거리행렬을 수정하는 방법
 

3. 평균연결법(Average Linkage)

군집과 군집 또는 데이터와의 거리를 계산할 때 평균을 거리로 계산하여 거리행렬 수정
 

4. 와드연결법(Ward Linkage)

군집내 편차들의 제곱함을 고려한 방법으로 군집 간 정보 손실을 최소화하기 위해 군집화 진행
 

 

4. 비계층적 군집분석

대표적인 비계층적 군집분석 방법으로는 K-Means 군집분석 방법이 있다.
 
K-means 군집분석은 주어진 데이터를 k개의 클러스터로 묶는 알고리즘으로 각 클러스터와 거리 차이의 분산을 최소화 하는 방식으로 동작됨
 

1. K-means 분석 방법 특징

• 연속형 변수에 활용 가능
• 초기값은 임의로 선택 가능하나 초기값에 따라 결과가 달라질 수 있음
• 안정된 군집은 보장하나 최적이란 보장은 없음
• 장점
  • 단순하고 빠르게 수행되며, 많은 양의 데이터를 다룰 수 있음
  • 사전정보가 없어도 의미있는 자료 구조를 찾을 수 있고, 다양한 형태의 데이터에 적용 가능
• 단점
  • 초기 군집수, 가중치와 거리 정의가 어려우며, 사전에 목적이 없으므로 결과 해석이 어려움
  • 이상값의 영향을 많이 받음

 

2. 분석 과정

1. 원하는 군집 갯수와 초기값(seed)를 정해 군집 형성
2. 각 데이터를 거리가 가장 가까운 초기값이 있는 군집으로 분류
3. 다시 seed 계산
4. 모든 개체가 군집으로 할당될 때까지 위 과정을 반복

 
 

5. 혼합 분포 군집 (Mixture Distribution Clustering)

 모형 기반의 군집 방법으로 데이터가 K개의 모수적 모형의 가중합으로 표현되는 모집단으로부터 나왔다는 가정하에 모수와 가중치를 자료로부터 추정하는 방법이다. K개는 군집을 의미하며, k개 모형 중 어떤 모형으로 나왔을지 확률이 높은 군집으로 분류가 이루어진다.
 모수와 가중치 추정에는 EM알고리즘이 사용된다.
 
특징으로는 아래와 같다.

• K-means와 절차는 유사하지만 확률분포를 도입하여 군집 수행
• EM 알고리즘을 이용한 모수 추정에서 데이터 커지면 수렴에 시간 걸릴 수 있음
• 이상치 자료에 민감

 
EM알고리즘

EM은 반복적인 방법을 사용하여 클러스터(분포)의 매개변수, 즉 평균, 분산/공분산 및 크기를 계산하고 재계산함

1. 모델은 임의적이거나 사용자가 지정할 수 있는 매개변수를 사용하여 클러스터 초기화함 (최종 결과가 매개변수에 민감하기 때문에 초기화에 주의해야함)
2. E-step 과 M-step에 대해서 수렴할 때까지 여러번 반복

 

예측(Expectation)과 최대화(Maximization) 2단계로 분류

1. 예측 (Expectation)
   • 처음에 각 정규분포에 데이터 포인트를 임의로 배정한 후, 개별 데이터 포인트가 각 정규 분포로부터 생성되었을 가능도(likelihood)를 계산하여 가장 높은 확률을 가진 정규 분포에 할당
   • 각 정규분포에 속할 확률은 계산한 후, 가장 큰 확률을 갖는 정규분포로 할당
2. 최대화  (Maximization)  
   • 1번 단계에서 개별 데이터 포인트를 모두 할당 후, 각 그룹의 데이터 포인트를 이용하여 MLE(Maximum Likelihood Estimation)으로 모분포, 모평균, 모분산 추정
   • 개별 데이터 포인트로 각 정규분포의 모수를 추정. 위 그림에서 정규 분포의 평균과 분산이 변경되었듯이 개별 데이터들의 클러스터와 정규 분포의 모수가 변하지 않을 때 까지 1,2 단계를 반복함

 

1. 초기화 단계 : 평균, 분산에 대해 임의값 설정하고, 사전 확률인 분포에 속할 확률(가중치)를 1/k로 초기화 함 (k : 전체 데이터를 설명하는 k개 분포)

      EM 알고리즘 활용

2. Expectation : 현재 parameter를 고정하고 X가 특정 분포에 속할 사후 확률을 계산함

3. Maximization : 사후 확률을 이용하여 parameter 추정

4. Stop : MLE를 통해 parameter 가 변하지 않고 수렴할 때까지 2~3단계를 반복함

 

6. SOM(Self Organizing Map)

 

구분	신경망 모형	SOM
학습방법	오차역전파법	경쟁학습방법
구성	입력층, 은닉층, 출력층	입력층, 2차원 격자 형태 경쟁층
기계학습 방법의 분류	지도학습	비지도학습

 

이전에 공부했던 내용이므로 아래 페이지 참고

https://based-infos.tistory.com/138 

05_01. 군집분석 S.O.M (self-organizing map)

 

 

7. 밀도기반 군집 분석

 어느 점을 기준으로 주어진 반경 내에 최소 개수 만큼의 데이터들은 가질 수 있도록 함으로써 특정 밀도함수 혹은 밀도에 의해 군집을 형성해나가는 기법이다.

• DBSCAN, OPTICS (순서를 생성하는 밀도 기반), DENCLUE(밀도 분포 함수에 기초한)

 

DBSCAN

• 밀도 기반 클러스터 알고리즘
• 동일한 클래스에 속하는 데이터는 서로 근접하게 분포할 것이다 라는 가정을 기반으로 동작함
• 임의로 선정한 하나의 데이터 포인트에서 지정 거리(eps) 안에 데이터가 최소 샘플 개수(min_samples)만큼 들어있으면 이 데이터 포인트를 핵심 샘플로 분류하여 클러스터 인식하는 방법
• 임의로 선정한 하나의 데이터 포인트에서부터 지정 거리 내 포인트 수가 최소 샘플 수보다 적으면 그 포인트는 Noise로 처리
• noise검출에 사용
• 이상 탐지, 과학 문헌 및 기타 응용 분야에서 널리 사용됩니다.

 

[장점]

• K-menas와 다르게 클러스터의 수를 지정할 필요가 없으며, 알고리즘이 자동으로 클러스터의 수를 찾음
• 밀도를 기반으로 클러스터가 형성되기 때문에 불특정한 기하학적 모양을 갖는 군집도 잘 구분함
• Noise Point 통한 Outlier 검출 가능 (clustering 되지 않은 데이터 발생). 따라서, Noise 데이터들이 군집에 영향을 주지 않음
• 계산량이 적어 빠름

🄀 임의의 모양의 클러스터를 결정할 수 있습니다.

1. 이상값에 대한 민감도가 낮습니다.

2. 이상치 탐지로 사용할 수 있습니다.

3. 모든 크기의 데이터 세트와 효과적으로 작동합니다.

 

[단점]

• quadratic time complexity 갖음
• 데이터가 입력되는 순서에 따라 클러스터링 결과가 변함
• 알고리즘이 이용하는 거리 측정 방법에 따라 클러스터링 결과가 변함 (차원의 저주 때문)
• 데이터 특성을 모를 경우 알고리즘의 적절한 hyper-parameter 설정이 어려움
• 다양한 밀도를 가지는 데이터의 분류에 부적합 (클러스터의 밀도가 다양할 때 다른 클러스터와 마찬가지로 잘 수행되지 않음)
• 고차원 데이터에 대해서 적절한 반경 (ε)을 찾기 어려움 -> t-SNE(시각화에만 유리할 수 있음), PCA, LDA 등 이용한 차원 축소 필요

🄀 고차원 데이터세트에는 잘 확장되지 않습니다.

1. 여러 하이퍼파라미터에 따라 다릅니다.

2. 다양한 밀도의 클러스터를 찾는 문제.

3. 숫자 데이터에서만 작동합니다.

 

 

[input/ hyper parameter]

• 반경 (ε, Eps)
• 반경 (ε) 내 최소 데이터 수 (n, MinPts)

https://rfriend.tistory.com/588

[R]  밀도 기반 군집분석 DBSCAN 의 입력 모수 Eps, MinPts 결정 방법 (Determining the Parameters Eps and MinPts)

 

[용어 정리]

• 이웃 벡터 : 한 데이터 벡터로부터 반경 (ε) 내 위치한 다른 데이터 벡터
• 핵심 벡터 (core points) : n개 이상의 이웃 벡터를 갖는 데이터 벡터
• 직접 접근 가능한 (directly density-reachable) : 핵심 벡터 p와  q의 한 이웃 벡터 q에 대해서 q는 p에 직접 접근 가능하다. 반면 q가 핵심 벡터가 아니라면 p는 q로 직접 접근 가능하지 않다.
• 접근 가능한 (density-reachable) : 데이터 벡터 p와 q에 대해서 직접 가능한 데이터 벡터 배열 {p = p1 -> p2,...,->q}가 있다면 p는 p로 부터 접근 가능
• 연결된(density-connected) : 데이터 벡터 p와 q에 대해서 p와 q에 접근 가능한 벡터 o가 존재한다면 p와 q는 연결되어 있음
• 군집 : 한 핵심 벡터 p에 대해서 접근 가능한 모든 데이터 벡터들의 집합. 한 군집 내 데이터 벡터들은 서로 연결 되어 있음
• 노이즈(Noise) : 어떤 군집에도 속하지 않은 데이터

1. core point : eps 반경 내에 minpts 이상 데이터 보유

2. border point : eps 반경 내에 minpts개의 데이터는 없지만, core point를 neighbor로 가진다.

3. noise point : eps 반경 내에 minpts개의 데이터도 없고, core point도 neighbor로 가지지 않는다

 

[알고리즘 과정]

1. minPts(클러스터 내  최소 데이터 수), eps(반경) 설정
2. 임의의 점 p 설정. p를 포함하여 주어진 반경 (ε) 안에 포함되어 있는 포인트 count
3. 해당 반경에 minPts개 이상이 포함되어 있으면, p를 core point로 간주하여 원 안에 포함된 점들을 하나의 클러스터로 묶음
4. 만약, 해당 반경에 minPts개 미만 점이 포함되면 pass
5. 모든 점에 대하여 돌아가면서 1~3 과정을 반복하고, 새로운 점 p가 core가 되고 이 점이 기존 클러스터에 속하면, 두 개의 클러스터는 연결되어 있다고 하며 하나의 클러스터로 묶음
6. 모든 점들에 대해서 클러스터링 과정을 끝냈으나 어디에도 속하지 못한 점이 있으면 noise point로 간주. 특정 군집에 속하지만 core point가 아닌 점들은 border point라 함

 

8. 군집분석 타당성 지표

실루엣 계수(silhouette score)

• 각 데이터 포인트와 주위 데이터 포인트들과의 거리 계산을 통해 값을 구하며, 군집 안에 있는 데이터들은 잘 모여있는지, 군집끼리는 서로 잘 구분되는지 클러스터링을 평가하는 척도로 활용
• 각 군집간 거리가 얼마나 효율적으로 분리되어 있는지 나타냄 ( 다른 군집과 거리가 떨어져 있고, 동일 군집 내 가까이 잘 뭉쳐짐을 의미)
• 군집 내 비유사성('within' dissimilarities)은 작고, 군집 간 비유사성('between' dissimilarities)은 커야 생성된 클러스터의 품질이 좋다
• 실루엣 계수의 평균값은 -1~1 사이 값을 가지며, 1에 가까울수록 군집화 잘됨
• 전체 실루엣 계수의 평균값과 더불어 개별 군집의 평균값의 편차가 작아야 함 (개별 군집의 실루엣 계수 평균값이 전체 실루엣 계수 평균값에서 크게 벗어나지 않아야 함)
• s(i)  1에 근사하고 a(i) < b(i) : 이웃 클러스터 보다 특정 데이터가 속한 군집에 훨씬 가까움을 의미

   

[장점]

• 클러스터링 알고리즘에 영향 받지 않음
• 적절한 클러스터 개수를 정하거나 클러스터링 기법 선택하는 기준으로 삼을 수 있음
• 클러스터링 결과 값을 시각화 할 수 있음

[단점]

• 데이터 양이 많아질수록 수행 시간 오래 걸림
• 전체 데이터 포인트의 실루엣 계수 평균값만으로 클러스터링 결과 판단할 수 없으며, 개별 클러스터 평균값도 함께 고려해야 함

 

Davies-Bouldin index

• 군집 내 거리와 군집 간 거리의 비율
• 해당 지표가 낮으면 클러스터링 알고리즘이 좋은 클러스터라고 평가함 -> 클러스터 간 거리가 멀고(클러스터 간 유사성 낮음), 클러스터 내 거리가 가까운(높은 클러스터 내 유사성) 클러스터는 낮은 수치를 가짐
• 실루엣 계수보다 계산량이 적고 간단함

 

Dunn index

• 밀도가 높고 잘 나뉜  즉, 군집 내 밀집 되고 군집 간 잘 나누어진 클러스터링을 목표로 함 -> 높은 클러스터 내 유사성과 낮은 클러스터 간 유사성
• 클러스터 간 최소 거리와 클러스터 내 최대 거리 비율로 정의
• 0에서 무한대 사이의 값으로 값이 클수록 군집이 잘 형성됨을 의미