DevHwi

Hierarchical Clustering

Hierarchical Clustering은 사실, 데이터 분석 및 알고리즘에서 많이 사용해보지 않은 알고리즘이다. Hierarchical Clustering의 원리와 특징등을 조금 더 공부해보고 싶었다.

Hierarchical Clustering 이란?

• Hierarchical Clustering (계층적 군집화)는 데이터 포인트들을 거리나 유사도 기반으로 계층적으로 묶어나가는 군집화의 방법이다. 
• Hierarchical Clustering의 결과는 보통 Dendrogram 형태로 표현하여 쉽게 확인 가능하다.
• Hierarchical Clustering은 계층의 구조를 시각적으로 파악 가능하여, 크지 않은 데이터셋들의 구조 분석이나 증빙, 이상치를 정의하는 일등에 활용된다.  

Hierarchical Clustering의 특징

장점

1. Hierarchical Clustering에서의 Cluster의 개수는 계층 구조를 보고, 조정 가능하기 때문에, 유연성이 높다. (미리 Cluster 개수를 정해놓을 필요가 없음)
2. Hierarchical Clustering은 Clustering된 과정과 결과를 한눈에 확인 가능하기 때문에, 각 Cluster의 크기와 Cluster 간의 관계를 파악 가능하다. (Cluster 간 비교 분석에 용이)
3. Hierarchical Clustering 수행 시, 이상치는 다른 Cluster와 계층적으로 별도 분리되어 있을 가능성이 크기 때문에, 이상치 제거에 활용 가능하다.

단점

1. Hierarchical Clustering의 계산 복잡도가 큰 편이다. 특히, 모든 데이터셋 간의 거리를 비교해야하기 때문에, 데이터셋의 크기가 클수록 계산복잡도가 늘어난다. (일반적으로 O(N³))
2. Hierarchical Clustering은 데이터 포인트 전체를 고려하기 때문에, 데이터의 삭제나 추가, 변경에 대해 민감하다.

일반적으로, Hierarchical Clustering은 연산 시간이 크다는 단점을 가지고 있어서, 대용량 데이터의 분석에 그대로 적용하는데는 한계가 있다. 하지만, 계층 시각화 및 군집 간 관계 파악등이 가능하기 때문에, 초기 데이터 분석 시, 적은 양의 데이터로 사용하기 좋은 기법이다. 

Hierarchical Clustering 알고리즘

Hierarchical Clustering은 각 데이터 포인트 간의 거리나 유사도를 계산하여, 작은 단위부터의 Clustering을 진행하면서, 전체 데이터 포인트가 하나의 Cluster를 구성할 때까지 Clustering을 반복적으로 진행하는 방식을 사용한다.

1. 각 데이터 포인트를 개별 Cluster로 고려

• 총 데이터가 N개 존재한다고 할 때, 각 포인트 1개씩을 가지고 있는 N개 Cluster를 형성한다.

2. Cluster 간 Distance Matrix를 계산

• 각 Cluster 간 거리 or 유사도를 계산한다. Cluster 간의 거리나 유사도를 계산하는 방법은 많지만, 보통 Euclidean Distance를 사용한다.
• N개 Cluster가 서로 간의 Distaince를 계산하기 때문에, distance matrix를 구하기 위해 N(N-1)/2번 최소 연산이 필요하다.

3. 가장 비슷한 2개의 Cluster를 하나의 Cluster로 Merge

• 앞서 구한, Distance Matrix를 기반으로 가장 유사한 or 거리가 가까운 Cluster들을 하나의 Cluster로 연결한다. 즉, 가장 가까운 거리에 있는 두 데이터 포인트를 묶어서 Cluster를 형성한다.
• N개 Cluster에서 N-1개 Cluster가 된다. 

4. 변경된 Cluster를 고려한 Distance Matrix 재계산 

• 새로운 Cluster가 생성되었기 때문에, Distance Matrix의 업데이트가 필요하다.
• 새로 구성된 Cluster는 2개의 데이터 포인트를 가지고 있기 때문에,  Distance Matrix를 어떻게 구할 것인지 정의가 필요하다.
• Distance Matrix를 구하는 방법은 아래와 같다.
  •  Single Linkage : 새로운 Cluster와 나머지 Cluster 간 거리는 한 Cluster 내의 데이터 포인트 들과 다른 Cluster 내의 데이터 포인트 들 사이 거리 중 가장 가까운 거리로 정의
  • Complete Linkage : 새로운 Cluster와 나머지 Cluster 간 거리는 한 Cluster 내의 데이터 포인트 들과 다른 Cluster 내의 데이터 포인트 들 사이 거리 중 가장 먼 거리로 정의
  • Average Linkage : 새로운 Cluster와 나머지 Cluster 간 거리는 한 Cluster 내의 데이터 포인트 들과 다른 Cluster 내의 데이터 포인트 들 사이 거리들의 평균으로 정의
  • Ward's Method : Cluster 내 데이터 포인트의 평균으로 중심점을 구하고, 각 Cluster의 중심점 기준으로 distance를 구함. 두 Cluster를 합친 후, 새로운 Cluster 내의 SSW(Sum of Squares Within)가 최소화되도록, 거리를 계산함. (d_i, d_j : Cluster 중심 점과 각 데이터 포인트 간 거리의 합, n_i, n_j : Cluster 데이터 포인트 갯수, p: 전체 데이터 갯수, d_ij: Cluster i와 j 사이 거리)

5. 3~4 단계를 Cluster가 1개로 합쳐질 때까지 반복

• Cluster Merge와 distance matrix 계산을 N-1번 반복하면, Cluster는 1개만 남는다.

6. Dendrogram 시각화

•  각 Cluster Merge 단계들을 Dendrogram으로 나타내서, 계층 구조를 확인한다.

Hierarchical Clustering Python 구현

• 단순 Clustering 결과를 보기 위해서는 scikit-learn의 "AgglomerativeClustering"를 사용하면 쉽게 사용 가능하다.

from sklearn.cluster import AgglomerativeClustering
from sklearn.datasets import make_blobs

if __name__ == '__main__':
    X, y = make_blobs(n_samples=20, centers=2, random_state=10, cluster_std=2)

    model = AgglomerativeClustering(linkage='average')
    model.fit(X) # 데이터 Training
    model.fit_predict(X) # 데이터 Predict

    model.labels_ # Training sample 할당된 Cluster Label 표시
    model.n_leaves_ # 계층 Cluster leaf node 수

• AgglomerativeClustering의 매개변수는 다음과 같다.
  • n_clusters : cluster 갯수 지정, (미지정 시, 적당한 Cluster 개수로 나눠줌)
  • linkage : cluster 간 distance 연산에 사용하는 방법 ('ward', 'single', 'complete', 'average' 선택 가능, default는 'ward')
  • affinity :  cluster 간 distance 연산에 사용하는 식 ('euclidean','manhattan', 'cosine', 'precomputed' 선택 가능, default는 'euclidean')
• Dendrogram을 보기 위해서는 scikit-learn의 pdist와 linkage, dendrogram을 사용해야 한다.

from scipy.spatial.distance import pdist
from scipy.cluster.hierarchy import linkage, dendrogram

if __name__ == '__main__':
    X, y = make_blobs(n_samples=20, centers=2, random_state=10, cluster_std=2)
    distance_matrix = pdist(X) # distance matrix 계산
    linkage_matrix = linkage(distance_matrix, method='single') # linkage 단계를 matrix화 함

    dendrogram(linkage_matrix)

• pdist는 distance matrix를 1D 형식으로 구하는 함수로 자기 자신과 중복을 제거한 N(N-1)/2 개의 값이 나온다. (만약 matrix의 각 데이터 포인트 값을 알고 싶다면, cdist를 사용하면 된다. 다만, linkage 인자는 cdist를 넣어줘야 한다.)
• pidst 함수에서 'metric' 매개변수로 distance 계산 방식을 바꿔줄 수 있다.
• linkage 함수에서 'method' 매개변수로 cluster 간 거리 측정 방식을 바꿔줄 수 있다. ('single', 'complete', 'average', 'ward')
• likage matrix는 N X 4의 matrix로 표시되고, 각 칼럼은 다음과 같은 의미를 가지고 있다.
  • 1 열: 첫 번째 Cluster 번호 
  • 2 열: 두 번째 Cluster 번호 
  • 3 열: 두 Cluster 합쳤을 때의 거리 or 유사도
  • 4 열: 새로운 Cluster 구성하는 데이터 포인트의 개수

K-means Clustering

K-means Clustering은 비지도 학습 기반의 Clustering 기법으로, 데이터를 Clustering하는 문제가 있으면, 가장 쉽게 연상되는 알고리즘이다. 워낙 많이 사용되어, 많이들 알고 있겠지만, K-means Clustering의 특징과 단계를 조금 더 자세히 알아보기로 한다. 

K-means Clustering 이란?

• K-means Clustering은 데이터를 K개의 군집으로 나누기 위한, 거리 기반 Clustering 알고리즘이다.
• K-means Clustering은 같은 집단 내 데이터들은 비슷한 특징을 가지고 있고, 다른 집단의 데이터와는 데이터적으로 상반된 특징을 가지고 있다는 것을 가정한다. 즉, 동일 집단의 군집화를 고려하는 것 뿐만 아니라, 타집단과의 관계도 고려한다. 
• K-means Clustering은 간단하고, 빠르고, 성능도 좋은 편이기 때문에 비지도 학습 기반 이미지 분류나 데이터 마이닝, 이상점 탐지등에서도 자주 활용된다.

K-means Clustering의 특징

장점

1. 간단하고, 해석이 쉽다.

• K-means Clustering 알고리즘은 거리 기반 알고리즘이기 때문에, 복잡한 연산을 포함하지 않는다. 따라서, 구현도 매우 쉬운편이고, 수행 시간도 빠르다. 또한, 거리 기반 알고리즘이기 때문에, 해석이 매우 용이하다. (같은 Cluster면, 거리가 가깝고, 다른 Cluster면 거리가 멀다.)

2. 성능이 좋다.

• Clustering 문제에서 성능이 좋다라는 기준은 애매하지만, 일반적으로 좋은 성능을 보인다.

3. 연구가 많이 되었다.

• 쉽고, 해석력이 높은 알고리즘이기 때문에, 다양한 분야에서 많이 활용 및 연구되었고, 개선되었다. 분석하고자 하는 데이터의 특성을 당장 알 수 없을때, 비슷한 분야에서  K-means Clustering 알고리즘을 활용한 연구들을 참고하기 쉽다.(중심점을 어디에 찍어야할지, 군집은 몇개로 나눌지 등등)

단점

1. 초기 값 의존도가 높다.

• 초기 값(centroid)를 어떻게 설정하냐에 따라, Clustering 결과가 매우 다르다. 특히, 초기 값이 적절하게 설정되지 않으면, Local Optimum으로 수렴되어, 초기에 원하지 않는 Clustering 모양이 될 수 있다. 이러한 문제는 분류해야하는 Cluster의 대략적인 모습을 알 수 없을때는 치명적으로 작용한다. (Local Optimum을 Global Optimum으로 착각할 수 있어서)   

2. Cluster의 개수를 미리 알아야한다.

• K-means Clustering이 매우 좋은 알고리즘임에도 불구하고, 가장 큰 단점이 있다면, Cluster 개수를 미리 알아야한다는 것이라고 생각된다. 실제 데이터에서 Cluster 개수를 미리 알기 어렵기 때문에(아직 특징을 모르거나, 사전에 이론적으로 정의한 K개의 Cluster가 실제 데이터에 모두 포함되지 않을 가능성도 있기 때문에), k-mean clustering을 단독으로 사용하기 어려운 약점이 된다. 

3. Cluster의 형태가 arbitrary한 경우 Clustering이 어렵다.

• Distance 기반으로 Clustering하기 때문에, 일반적으로 구형의 모양이 된다. (Euclidean 거리 사용시)
• 아래와 같이, Clustering 하고자 하는 데이터 분포가 구형 모양이 아니면,  의도한 Clustering 결과와 다르게 분류가 될 수 있다. 

4. Outlier에 민감한 편이다.

• K-means Clustering은 Outlier에 민감한 편이다. 특히, Outlier가 centroid로 선택되면, 이상한 Clustering 결과가 될 수 있다. 

전체적으로, K-means Clustering은 간단하고, 좋은 해석력과 빠른 속도, 높은 성능등을 가지고 있지만, 몇가지의 단점이 존재하여, 단점들이 개선된 알고리즘이나, Outlier 제거 등의 다른 기법들과 함께 활용된다. 

K-means Clustering 알고리즘

K-means Clustering은 centroid를 설정하고, 데이터의 Cluster 할당 과정을 반복해가면서, Clustering을 수행한다.

1. 초기 centroid 설정

•  K-means Clustering에서 초기의 centroid를 잡는 것은 매우 중요하다. (잘못 설정 시, Local minimum에 빠질 수 있고, 수렴 속도도 느릴 수 있다.)
• K-means Clustering의 cetroid를 설정하는 방법은 크게 3가지 방법이있다.

1) Random : 데이터 포인트 중, K개를 뽑아서, centroid로 지정한다. 

2) Hierarchical clustering : Hierarchical clustering 같은 다른 clustering 방법을 사용하여, centroid에 대한 hint를 얻는다.

3) K-means++ : K-means Clustering의 초깃값을 더 효율적으로 찾기 위해, 몇가지 단계를 수행한다. (Sklean default 방법)

• 1개의 centroid를 무작위로 뽑는다.
• 데이터포인트들과 centroid 간의 거리를 계산한다.
• 각 데이터 포인트와 centroid 간 거리의 제곱을 확률로 하여, 다음 cluster의 centroid를 뽑는다. (거리가 멀수록, 다음 cluster로 뽑히는 확률이 높다는 의미)
• K개의 centroid가 만들어질때까지 반복한다.

→ 보통은 K-means++ 알고리즘을 많이 사용하지만, 계산 비용이 추가적으로 든다는 점과, 맨 처음 centroid가 이상치를 선택하게 되면, cluster 모양이 이상해진다는 점 등의 단점도 존재한다. 따라서, 데이터의 중심을 추정이 가능하다면, 직접 설정하는 것도 좋은 방법이다. 

2. 각 데이터 포인트와 centroid 거리 측정 & Cluster 할당

• K-means Clustering의 수식은 위와 같다. 즉, K개의 centroid 들 중, 현재 point와 거리가 가장 가까운 centroid가 형성하는 cluster에 데이터가 포함한다. 
• 거리를 구하는 방법은 지정하기 나름이지만, 보통 유클리디안 거리를 사용한다.

3. centroid 업데이트 

• 새로운 centroid로는 2번에서 할당한 cluster들의 평균 값을 활용한다. 
• 새로운 centroid는 2번에 할당된 cluster의 중간으로 이동할 것이다.

4. 2~3 단계를 반복

• 수렴할때까지, cluster 할당, centroid 업데이트를 반복한다.

K-means Clustering Python 구현

• scikit-learn의 KMeans를 사용하면 쉽게 사용 가능하다.

import numpy as np
from sklearn.cluster import KMeans
import matplotlib.pyplot as plt
from sklearn.datasets import make_blobs

if __name__ == '__main__':
    X, y = make_blobs(n_samples=1000, centers=5, random_state=10, cluster_std=2) # 데이터 생성

    kmeans = KMeans(n_clusters=5, init=rand_array, n_init=1, max_iter=100)
    kmeans.fit(X)

    kmeans.labels_ # 학습에 활용된 데이터의 cluster를 예측
    kmeans.predict(X) # 임의의 point가 어느 cluster에 포함되는지 예측
    kmenas.transform(X) # 임의의 point와 할당된 cluster의 centroid 간의 거리를 구함

• n_clusters : 클러스터 개수 (*hyper-parameter)
• init : 초깃값 설정 방법, 'k-means++', 'random', numpy_array(centroid를 직접 지정해줄 때) ,default는 k-means+
• max_iter : 2~3 단계 최대 반복 횟수 (default:300)
• random_state : k-means++ 등에서 무작위성을 제어하기 위한 시드 값, 재현을 위해 설정이 필요함
• algorithm : k-means clustering 데이터 계산 시, 어떤 알고리즘을 사용할 것인지, 'auto', 'full', 'elkan'이 있다. full은 모든 데이터를 2~3 단계에서 활용하는 것이고, elkan은 데이터 연산 부하를 줄이기 위해, 불필요한 연산을 줄이는 방법이다. auto는 데이터 크기와 특징에 따라, 자동으로 설정해줌
• metric : 거리 측정 방식, 'euclidean', 'manhattan', 'cosine', 'l1', 'l2', 'manhattan_l1', 'manhattan_l2' 등이 있음 (default : euclidean, 사용자 지정 함수도 활용 가능) 

GMM (Gaussian Mixture Model) Clustering

GMM Clustering은 Clustering 문제에서 각 Cluster에 포함될 확률이 포함될 때, 자주 사용하는 알고리즘이다. 대략적인 컨셉만 알고 쓰고 있지만, 조금 더 자세히 알아보고 싶었다.

GMM 이란?

• GMM(Gaussian Mixture Model) Clustering은 어떠한 데이터 분포가 여러 개의 Gaussian 분포 여러 개가 섞여서 만들어졌다고 생각하고, 해당 데이터 분포를 이루는 여러 개의 Gaussian 분포로 나타내는 확률적 생성 모델이다.
• GMM Clustering은 다른 Clustering 모델과 달리, 해당 Cluster에 속할 확률을 같이 나타내주기 때문에, Clustering 결과에 불확실성도 함께 고려할 수 있다.
• GMM Clustering은 확률을 포함한 Clustering이나, 데이터 생성, 이상치 탐지(다른 이상치 제거 알고리즘과 함께 사용되는 경우) 등에 유용하게 사용된다.

GMM Clustering, K-Means Clustering, DBSCAN과의 차이

• 보통 GMM Clustering을 단독으로 사용하지는 않지만, (초기값 설정에서 다른 Clustering 알고리즘의 도움을 많이 받음), 같은 Clustering 알고리즘이라는 점에서 DBSCAN과 K-means Clustering과 비교해 보기로 한다.

GMM Clustering 원리

• GMM Clustering 알고리즘은 데이터 분포를 여러개의 Gaussian 분포들의 합 들이 혼합된 상태로 구성되어 있다고 가정하기 때문에, 데이터는 아래 수식과 같이 모델링 된다.

- 𝑝(𝑥) : 데이터 포인트 x의 확률
- 𝜙𝑖 : i 번째 Gaussian 분포의 합의 weight (weight의 합은 1)
- N(𝑥|𝜇𝑖,Σ𝑖) : i번째 Gaussian 분포의 확률 밀도 함수
- 𝜇𝑖 : i번째 Gaussian 분포의 평균
- Σ𝑖 : i번째 Gaussian 분포의 공분산 행렬

• GMM Clustering 알고리즘은 결국 GMM 수식에서 𝜙𝑖(각 Gaussian 분포의 weight), 𝜇𝑖 (각 Gaussian 분포의 평균), Σ𝑖 (각 Gaussian 분포의 공분산 행렬)을 찾는 과정이다.
•  이를 위해, EM (Expectation & Maximization) 알고리즘을 사용한다. EM 알고리즘은 Expectation step과 Maximization Step으로 나뉜다.
  • E-step (Expectation step) :
    
    • 각 데이터 포인트가 어떤 Gaussian 분포에 속하는지에 대한 확률을 추정한다. 
  • M-step (Maximization step)
    • E-step에서 추정된 확률을 이용해서, Gaussian 분포의 Parameter(weight, 평균, 공분산 행렬)를 업데이트한다. 
    • 이때, 업데이트를 위한 목적함수는 log-likelihood 함수를 이용한다. 
    • log-likelihood 함수가 최대화하는 방향으로 Parameter를 업데이트한다. (어떠한 data point가 어떤 Gaussian 분포에 포함될 확률이 높도록 학습. 즉, 모든 데이터 포인트가 어떠한 Gaussian 분포에 포함될 확률이 높도록 parameter를 업데이트)

• 다만, GMM은 초기값 설정에 매우 민감하다. 만약 inital mean 값이 잘못 찍혔을 때, Clustering의 결과가 원하는 바와 다르게 나올 수 있다. 

• 따라서, GMM Clustering을 단독으로 사용하기 보다는 K-means Clustering 등을 이용하여, Initial 값들을 setting 한다. (scikit-learn의 GaussianMixture 함수도 초깃값의 default 설정이 k-means 방법을 통해 구하는 것으로 되어있다.)

GMM Clustering Python 구현

• scikit-learn의 GaussianMixture 함수를 사용하면 쉽게 사용 가능하다.

import numpy as np
from sklearn.datasets import make_blobs # Clustering 데이터 생성을 위해
from sklearn.mixture import GaussianMixture

if __name__ == '__main__':
    X, y = make_blobs(n_samples=1000, centers=5, random_state=1) # Sample 데이터 생성
    gmm = GaussianMixture(n_components=5, random_state=42, n_init=10)
    gmm.fit(X)

    gmm.means_ #gmm의 mean 값들을 확인 가능
    gmm.weights_ #gmm의 weight 값들을 확인 가능
    gmm.covariances_ #gmm의 공분산 행렬 확인 가능

    gmm.predict(X) #각 point가 어느 Cluster에 포함되는지 결과를 확인
    gmm.predict_proba(X) #각 point가 각 Cluster에 포함될 확률 (point 당 n_components개 만큼)

DBSCAN (Density-Based Spatial Clustering of Application with Noise)

포인트 데이터 분석에서 DBSCAN은 항상 빠지지 않고 등장한다. 항상 무의식적으로 사용했었는데, 조금 더 자세히 알아보고 싶었다.  

DBSCAN 이란?

• DBSCAN(Density-Based Spatial Clustering of Applications with Noise)은 머신 러닝에 주로 사용되는 클러스터링 알고리즘으로 Multi Dimension의 데이터를 밀도 기반으로 서로 가까운 데이터 포인트를 함께 그룹화하는 알고리즘이다.
• DBSCAN은 밀도가 다양하거나 모양이 불규칙한 클러스터가 있는 데이터와 같이 모양이 잘 정의되지 않은 데이터를 처리할 때 유용하게 사용 가능하다.

K-Means Clustering과의 차이

• 보통 Clustering 문제에서 K-Means Clustering을 우선 떠올리지만, DBSCAN이 필요한 경우도 있다.
• K-Means Clustering과 DBSCAN의 차이는 다음과 같다.

• DBSCAN과 K-means Clustering 사이에 어느 것이 좋다는 다루는 데이터에 따라 많이 달라진다.
• DBSCAN은 일반적으로 K-means Clustering에 비해 1) 불규칙 데이터를 다룰때, 2) Noise와 Outlier가 많을 것으로 예상될 때, 3) 데이터에 대한 사전 예측이 어려울때, 활용하는 것이 좋다.
• 하지만, DBSCAN은 K-means Clustering에 비해 1) Computational Cost가 많이 든다는 점, 2) 예측과 해석이 어렵다는 점의 단점이 있다.

DBSCAN 알고리즘

• DBSCAN도 2가지의 hyper parameter를 갖는다.

1. Epsilon : Cluster를 구성하는 최소의 거리
2. Min Points: Cluster를 구성 시, 필요한 최소 데이터 포인트 수

• DBSCAN의 동작 과정은 다음과 같다. 

1. 데이터 중, 임의의 포인트를 선택함.
2. 선택한 데이터와 Epsilon 거리 내에 있는 모든 데이터 포인트를 찾음.
3. 주변에 있는 데이터 포인트 갯수가 Min Points 이상이면, 해당 포인트를 중심으로 하는 Cluster를 생성한다.
4. 어떠한 포인트가 생성한 Cluster 안에 존재하는 다른 점 중, 다른 Cluster의 중심이 되는 데이터 포인트가 존재한다면 두 Cluster는 하나의 Cluster로 간주한다.
5. 1~4번을 모든 포인트에 대해서 반복한다.
6. 어느 Cluster에도 포함되지 않는 데이터 포인트는 이상치로 처리한다. 

DBSCAN Python 구현

from sklearn.datasets import make_moons
from sklearn.cluster import DBSCAN
import matplotlib.pyplot as plt

if __name__ == '__main__':
	N = 1000
    
    X, y = make_moons(n_samples=N, noise=0.05) # make_moons 함수를 사용

    dbscan = DBSCAN(eps=0.2, min_samples=5) # DBSCAN (eps : epsilon, min_samples : min point)
    dbscan.fit(X)

    plt.scatter(X[:, 0], X[:, 1], c=dbscan.labels_) # Clustering 결과 시각화 용도
    plt.show()