【알고리즘】 8강. 클러스터링 알고리즘

8강. 클러스터링 알고리즘(군집 모형, clustering algorithm)

 

추천글 : 【알고리즘】 알고리즘 목차

---

1. 개요 [본문]

2. 종류 1. unsupervised hierarchical clustering [본문]

3. 종류 2. K-means clustering [본문]

4. 종류 3. 밀도 기반 군집 [본문]

5. 종류 4. 혼합 분포 군집 [본문]

6. 종류 5. 그래프 기반 군집 [본문]

7. 기타 알고리즘 [본문]

---

 

1. 개요 [목차]

⑴ 클러스터링은 optimization problem

① variability

 

 

○ variability는 distance 혹은 distance²의 합이라고 할 수 있음

○ 거리 함수의 종류

○ 이유 : big and bad is worse than small and bad

② dissimilarity

 

 

○ 클러스터링은 dissimilarity에 대한 global minimum을 구하는 게 아님

○ 이유 1. global minimum은 샘플 개수만큼 클러스터가 존재하여 ^∀variability = 0인 자명해가 존재하기 때문

○ 이유 2. 큰 클러스터라고 무조건 패널티를 부과하는 것은 부당함 : big is not necessarily worse than small

○ 제약 조건이 필요함 : minimum distance between clusters, number of clusters 등

⑵ 클러스터링은 unsupervised algorithm

① 이로 인해, 클러스터링 알고리즘의 퍼포먼스를 평가하기는 어렵지만 다음과 같이 평가할 수 있음

② 방법 1. NMI(normalized mutual information)

③ 방법 2. ARI(adjusted rand index)

④ 방법 3. ASW(average silhouette width)

⑤ 방법 4. AMI

⑥ 방법 5. Homo

⑦ 방법 6. 클러스터 간 상대적 거리 

⑶ 클러스터링의 종류

① 종류 1. agglomerative : bottom-up approach. 더 큰 클러스터로 만들어가는 접근 방식

② 종류 2. divisive : top-down approach. 더 작은 클러스터로 만들어가는 접근 방식

③ practice에서만 agglomerative를 많이 씀

 

 

2. 종류 1. 계층적 군집 모형(unsupervised hierarchical clustering) [목차]

⑴ 개요

① 내적 행렬로부터 heatmap을 그릴 때 주로 사용 (예 : RStudio의 heatmap 함수)

② graph-based methood의 일종

③ 비계층적 군집 모형과 달리 계층적 군집은 군집의 개수를 미리 정하지 않음 

⑵ 종류 1. 분할분석법 

① 전체 집단으로부터 시작하여 유사성이 떨어지는 객체들을 분리하는 기법 

② 1단계 : 우선 N개의 원소 각각 1개의 클러스터씩, 총 N개의 클러스터를 할당

③ 2단계 : 가장 가까운 클러스터를 찾아 하나의 클러스터로 합침

④ 3단계 : 2단계를 클러스터의 개수 등의 제약조건을 만족할 때까지 반복

○ 이 경우 dendrogram 등을 이용함

⑶ 종류 2. 응집분석법(agglomerative hierarchical clustering )

① 정의 : 각 개체를 하나의 소집단으로 간주하고 단계적으로 유사한 소집단들을 합쳐 새로운 소집단을 구성해가는 기법 

⑷ linkage metric : 클러스터 간 거리를 정의

① 종류 1. 최단연결법(single-linkage) : 한 클러스터의 원소와 다른 클러스터의 원소 간 거리 중에서 가장 가까운 거리

② 종류 2. 최장연결법(complete-linkage) : 한 클러스터의 원소와 다른 클러스터의 원소 간 거리 중에서 가장 먼 거리

③ 종류 3. 평균연결법(average-linkage) : 한 클러스터의 중심과 다른 클러스터의 중심 간 거리

○ 한 클러스터의 원소와 다른 클러스터의 원소 간 거리의 평균을 의미하는 경우도 있음

④ 종류 4. 중심연결법 : 두 군집의 중심 간의 거리를 측정

⑤ 종류 5. 와드연결법(ward-linkage) : 군집 간의 거리를 측정하는 방법 중에서 군집 내의 오차 제곱합에 기초하여 군집을 수행

 

출처 : 이미지 클릭

Figure. 1. linkage metric에 따른 클러스터링 퍼포먼스^]

 

⑸ 특징

① K-means clustering과 함께 가장 자주 사용되는 클러스터링 알고리즘 중 하나

② 장점 1. 결정론적(deterministic) : 어떤 환경에서 실행해도 동일한 결론에 도달할 수 있음

③ 장점 2. 여러 linkage criteria를 시도해 볼 수 있음

④ 단점 1. 느린 naïve 알고리즘. 일반적으로 Ο(n³)의 시간복잡도가 소요됨

○ 이유 : 2단계를 수행하는 데 Ο(n²)가 소요되고 Ο(n)만큼 반복해야 함

○ 어떤 linkage criteria를 이용하는 경우 Ο(n²)의 시간복잡도가 소요되기도 함

⑹ 레퍼런스

Clustering(K-Mean and Hierarchical Cluster)

 

 

3. 종류 2. K-means clustering (K-평균 군집화) [목차]

⑴ 개요

① 이미지를 대상으로 하는 클러스터링 알고리즘에 많이 사용됨

⑵ 알고리즘

 

출처 : 이미지 클릭

Figure. 2. K-means clustering 작동 방식

 

① 1단계 : 랜덤하게 k개의 초기 centroid를 선택

② 2단계 : 각 원소가 어떤 centroid와 가까운지에 따라 클러스터를 할당

③ 3단계 : 각 클러스터의 중심을 계산하여 새로운 centroid를 정의

④ 4단계 : 더이상 centroid의 위치가 바뀌지 않으면 클러스터링은 종료됨

⑶ 특징

① 가장 많이 사용되는 클러스터링 알고리즘

② K-means clustering은 클러스터링을 위한 greedy 알고리즘 중 하나

③ K의 결정

○ 사전 배경지식

○ 예 : 바이오 멀티오믹스 데이터에서 암종과 비암종 데이터로 구분하는 경우

○ 엘보우 기법(elbow-)

○ 군집분석에서 군집 수를 결정하는 방법으로 군집 수에 따하 군집 내 총 제곱합을 플로팅하여 팔꿈치의 위치를 일반적으로 적절한 군집 수로 선택하는 방법

○ x축에 클러스터의 개수, y축에 SSE 값을 두었을 때 기울기가 완만한 팔꿈치 부분에 해당하는 클러스터를 선택

○ 실루엣 기법(silhouette-)

○ 실루엣 계수를 사용한 클러스터링의 품질을 정량적으로 계산 하는 방법

○ 각 군집 간의 거리가 얼마나 분리되어 있는지를 나타내는 기법 

○ 실루엣 계수가 1에 가까울수록 군집 간 거리가 멀어서 최적화가 잘 되어 있다고 할 수 있음

○ 실루엣계수가 0에 가까울수록 군집 간 거리가 가까워서 최적화가 잘 안 되어 있다고 할 수 있음 

○ 덴드로그램(dendrogram) : 계층적 군집 분석의 덴드로그램 시각화를 이용하여 군집의 개수를 결정

④ 장점 1. 속도가 빠름. 2단계를 수행하는 데 Ο(Kn)이 소요됨 (단, K는 클러스터의 개수, n은 데이터의 개수)

⑤ 장점 2. 매 반복마다 목적 함수가 감소하기 때문에 수학적으로 유한 번의 반복으로 수렴함

⑤ 단점 1. 잘못된 K를 선택하게 되면 잘못된 결과가 나올 수 있음

⑥ 단점 2. 초기 centroid 위치에 따라 결과가 달라지므로 deterministic하지 않음

⑷ 파이썬 코드

 

from sklearn.cluster import KMeans

X = [[1, 2, 3],[1, 2, 3.1],[2, 2, 4],[2, 2, 4.1]]
kmeans = KMeans(n_clusters=2, random_state=0)
kmeans.fit(X)
cluster_labels = kmeans.labels_

print(cluster_labels)
# [1 1 0 0]

 

⑸ unsupervised hierarchical clustering vs K-means clustering

 

	unsupervised hierarchical clustering	K-means clustering
시간 복잡도	O(n3)	O(kn) × iteration
무작위성	deterministic	random

Table. 1. unsupervised hierarchical clustering과 K-means clustering의 비교

 

⑹ K-NN vs K-means clustering

 

항목	K-NN	K-means clustering
유형	지도학습	비지도학습
k의 의미	근접한 이웃의 수	클러스터의 수
최적화 기법	cross validation, 혼동행렬	엘보우, 실루엣 기법
활용	분류	클러스터링

Table. 2. K-NN vs K-means clustering

 

⑺ 종류 2-1. K-medoid clustering

⑻ 종류 2-2. Lloyd's K-means clustering algorithm

 

 

4. 종류 3. 밀도 기반 군집(DBSCAN, density-based spatial clustering of applications with noise) [목차]

⑴ 개요 : K-means clustering처럼 비계층적 군집 분석 중 하나

① 개체들의 밀도 계산을 기반으로 밀접하게 분포된 개체들끼리 그룹핑하는 알고리즘

② 클러스터의 개수를 미리 지정할 필요가 없음

③ 군집 밀도에 따라서 군집을 서로 연결하기 때문에 기하학적인 모양의 군집 분석이 가능함

⑵ 구성 요소

① 중심점(core point)

○ 주변 반경(epsilon) 내에 최소 데이터 개수(min_samples) 이상의 다른 데이터를 가지고 있는 데이터

○ 반경 내에 존재해야 하는 최소 데이터 개수는 일종의 초매개변수로 설정

② 이웃점(neighbor point)

○ 특정 데이터 주변 반경 내에 존재하는 다른 데이터 

③ 경계점(border point)

○ 중심점은 아니지만, 중심점이 주변 반경 내에 존재하는 데이터

○ 중심점을 중심으로 하는 군집에는 포함되며, 주로 군집의 외곽을 이룸 

④ 잡음점(noise point)

○ 중심점도 아니고 경계점 조건도 만족하지 못하는 이웃점

○ 이상치라고도 함

⑶ 절차

① 단계 1. 일정 반경(epsilon) 내에 최소 데이터 개수(min_samples) 이상의 점이 포함되도록 중심점을 식별

② 단계 2. 모든 비 중심점을 무시하고 인접 그래프에서 중심점과 연결된 구성요소를 탐색

③ 단계 3. 중심점 외에 속하면 노이즈로 할당 : 파이썬 상으로 -1을 할당

⑷ 특징

① 장점 1. k-평균 군집과 같이 클러스터의 수를 정하지 않아도 됨

② 장점 2. 클러스터의 밀도에 따라서 클러스터를 서로 연결하기 때문에 기하학적인 모양을 갖는 군집도 잘 찾을 수 있음

③ 단점 1. 초매개변수를 결정하기 어렵고, 매개변수의 선택에 민감함

④ 단점 2. 클러스터들이 다양한 밀도를 가지거나, 차원이 크면 계산에 어려움이 있음 

⑸ 응용 : OPTICS, HDBSCAN, DBSCAN++

⑹ 파이썬 예제 

 

Figure. 3. DBSCAN 파이썬 예제

 

import pandas as pd
from sklearn.datasets import make_blobs
from sklearn.cluster import DBSCAN
import matplotlib.pyplot as plt

# Step 1: Generate sample data
X, _ = make_blobs(n_samples=300, centers=4, cluster_std=0.60, random_state=0)

# Step 2: Convert to DataFrame
df = pd.DataFrame(X, columns=['x', 'y'])

# DBSCAN parameters
epsilon = 0.5  
min_samples = 5 

# Step 3: Perform DBSCAN clustering
db = DBSCAN(eps=epsilon, min_samples=min_samples)
df['cluster_label'] = db.fit_predict(df[['x', 'y']])

# Step 4: Visualize the clustering results
plt.figure(figsize=(12, 8))
plt.scatter(df['x'], df['y'], c=df['cluster_label'], cmap='viridis', marker='o')
plt.title('DBSCAN Clustering')
plt.xlabel('X')
plt.ylabel('Y')
plt.show()

 

 

5. 종류 4. 혼합 분포 군집(mixture distribution clustering) [목차]

⑴ 혼합 분포 군집 : K-means clustering처럼 비계층적 군집 분석 중 하나 

① 데이터가 k개의 모수적 모형의 가중합으로 표현되는 모집단 모형으로부터 나왔다는 가정 하에 자료로부터 모수와 가중치를 추정

② k개의 각 모형은 군집을 의미하며, 각 데이터는 추정된 k개의 모형 중 어느 모형으로부터 나왔을 확률이 높은지에 따라 군집이 분류됨

③ 혼합 모형의 정의 : M개 분포(성분)의 가중합으로 표현되는 혼합 모형

 

p(x | θ) = Σ p(x | C_i, θ_i) p(C_i)

 

○ p(x | C_i, θ_i) : 혼합 모델을 이루는 단일 확률밀도 함수 

○ θ_i : i번째 분포의 모수 벡터

○ C_i : i번째 군집(클래스)

○ p(C_i) : i번째 군집이 혼합 모형에서 차지하는 중요도 또는 가중치(α_i)

④ 혼합 모형의 모수를 추정하는 경우 단일 모형과는 달리 표현식이 복잡하여 미분보다는 EM 알고리즘을 이용

⑤ 군집의 크기가 너무 작으면 추정의 정도가 떨어지거나 어려울 수 있음

⑥ 이상값에 민감하므로 이상값 제거 등의 사전 조치가 필요함

⑵ 가우시안 혼합 모델(GMM, gaussian mixture model) 

 

출처 : 이미지 클릭

Figure. 4. 가우시안 혼합 모델

 

① 전체 데이터의 확률분포가 k개의 가우시안 분포의 선형 결합으로 이뤄졌음을 가정

② 위 가정을 바탕으로 각 분포에 속할 확률인 높은 데이터 간의 군집을 형성하는 방법

③ GMM에서는 주어진 데이터 X = {x1, x2, ∙∙∙, xN}에 대하여 적절한 k개 가우시안 분포의 가중치, 평균, 공분산을 추정

④ 데이터들이 k개의 가우시안 분포 중에서 어디에 속하는 것이 최적인지 추정하기 위해 EM 알고리즘을 이용할 수 있음 

 

 

⑤ K means clustering과 Gaussian mixture model의 비교

 

Figure. 5. K means clustering과 Gaussian mixture model의 비교

 

 

6. 종류 5. 그래프 기반 군집(SOM, self-organizing maps) [목차]

⑴ 개요 : K-means clustering처럼 비계층적 군집 분석 중 하나 

① SOM은 코호넨에 의해 개발됐으며, 코호넨 맵(Kohonen maps)으로도 알려져 있음

② SOM은 대뇌피질과 시각피질의 학습 과정을 기반으로 모델링을 한 인공신경망

③ 자율 학습 방법에 의한 클러스터링

④ 고차원의 데이터를 이해하기 쉬운 저차원의 뉴런으로 정렬하여 지도의 형태로 형상화한 비지도 신경망 

⑤ 형상화는 입력변수의 위치 관계를 그대로 보존

⑥ 실제 공간의 입력변수가 가까이 있으면 지도상에는 가까운 위치에 있게 됨 

⑦ 단 하나의 전방 패스를 사용함으로써 속도가 매우 빠름 

⑵ SOM 구성

① 구성 1. 입력층(input layer)

○ 입력 벡터를 받는 층으로 입력변수의 개수와 동일하게 뉴런이 존재함

○  입력층의 자료는 학습을 통하여 경쟁층에 정렬되는데 이를 지도(map)라고 부름

○ 입력층에 있는 각각의 뉴런은 경쟁층에 있는 각각의 뉴런들과 완전 연결되어 있음

② 구성 2. 경쟁층(competitive layer)

○ 2차원 격자(grid)로 구성된 층으로 입력 벡터의 특성에 따라 벡터의 한점으로 클러스터링되는 층

○ SOM은 경쟁 학습으로 각각의 뉴런이 입력 벡터와 얼마나 가까운가를 계산하여 연결 강도를 반복적으로 재조정하여 학습

○ 학습 과정을 거치면서 연결 강도는 입력 패턴과 가장 유사한 경쟁층 뉴런이 승자가 됨

○ 승자 독식 구조로 인해 경쟁층에는 승자 뉴런만이 나타나며, 승자와 유사한 연결 강도를 갖는 입력 패턴이 동일한 경쟁 뉴런으로 배열

⑶ SOM 학습 알고리즘

① 단계 1. 초기화 : SOM 맵의 노드에 대한 연결 강도를 초기화 

② 단계 2. 입력 벡터 : 입력 벡터를 제시 

③ 단계 3. 유사도 계산 : 유클리드 거리를 사용하여 입력 벡터와 프로토타입 벡터 사이의 유사도를 계산 

④ 단계 4. 프로토타입 벡터 탐색 : 입력 벡터와 가장 거리가 짧은 프로토타입 벡터(BMU)를 탐색 

⑤ 단계 5. 강도 재조정 : BMU와 그 이웃들의 연결 강도를 재조정 

⑥ 단계 6. 반복 : 단계 2로 가서 반복 

 

 

7. 기타 클러스터링 알고리즘 [목차]

⑴ SNN(shared nearest neighbor) modularity optimization based clustering algorithm

① 1단계. K-nearest neighbor를 탐색

② 2단계. SNN 그래프를 구성

③ 3단계. 클러스터를 정의하기 위해 modularity function을 최적화

④ 참고 논문 : Waltman and van Eck (2013) The European Physical Journal B 

⑵ Leiden clustering 

① scanpy 파이프라인에서 사용하는 Leiden 알고리즘 예시

 

import scanpy as sc
import numpy as np

# Load your AnnData object
adata = sc.read_h5ad('my_h5ad.h5ad')

# Run PCA to reduce dimensionality
sc.pp.pca(adata, n_comps=20) 

# Compute the neighborhood graph
sc.pp.neighbors(adata)

# Run clustering using the Leiden algorithm (HERE!)
sc.tl.leiden(adata, resolution = 0.5)

# Optionally, compute UMAP for visualization
sc.tl.umap(adata)

# Plotting the results
sc.pl.umap(adata, color='leiden', title='Leiden Clustering')
sc.pl.spatial(adata, color = 'leiden')

 

⑶ 루베인 군집화(Louvain clustering)

① Louvain modularity optimization : graph-based methood의 일종

⑷ mean-shift clustering 

⑸ spectral clustering

⑹ NMF(non-negative matrix factorization)

① 알고 있는 A 행렬을 W 행렬과 H 행렬의 곱으로 분해하는 알고리즘 : A ~ W × H

○ A 행렬 : 샘플-특성을 나타내는 행렬. 샘플로부터 알 수 있음

○ H 행렬 : 변수-특성을 나타내는 행렬

○ 이를 통해 metagene을 뽑아낼 수 있음

○ K means clustering, PCA 알고리즘과 유사함

② 응용 1. cell type classification

○ 조직으로부터 얻은 scRNA-seq로부터 cell type proportion을 얻기 위한 목적

○ cell type heterogeneity에 의한 confounding effect를 줄이는 게 중요

○ 3-1. constrained linear regression

○ 3-2. reference-based approach

○ 3-2-1. CIBERSORT(cell-type identification by estimating relative subsets of RNA transcript) : 샘플별로 cell type proportion, p value를 확인할 수 있음

③ 응용 2. joint NMF : 멀티오믹스까지 확장하게 함

⑺ watershed algorithm 

① 특정 밝기 이상, 특정 밝기 이하 등의 역치값으로 이미지 상의 ROI를 알아내는 알고리즘

⑻ thresholding method

① 정의 : threshold 기반으로 binary image를 만드는 기법

② 예 : Otsu thresholding method 

⑼ MST(minimum spanning tree)

⑽ curve evolution

⑾ sparse neighboring graph : graph-based method의 일종

⑿ SC3

⒀ SIMLR

⒁ FICT

⒂ fuzzy clustering

⒃ C-means clustering 

⒄ Faiss : 2023년 Meta에서 개발한 유사도 기반 탐색 및 dense vector 클러스터링 알고리즘

⒅ mclust 

 

입력: 2021.11.16 13:17

수정: 2023.09.22 00:20