태그: 군집분석

Affinity Propagation # Affinity Propagation은 데이터 포인트들 간의 메시지 전달을 통해 클러스터의 중심(exemplar)을 자동으로 선택하는 클러스터링 알고리즘이다. 클러스터의 수를 미리 정하지 않고도 데이터의 구조에 따라 적절한 수의 클러스터를 자동으로 결정한다. 주요 개념 # Exemplar: 각 클러스터를 대표하는 실제 데이터 포인트이다. Responsibility: 데이터 포인트 i가 포인트 k를 exemplar로 선택하는 정도를 나타낸다. Availability: 포인트 k가 포인트 i의 exemplar가 되기에 적합한 정도를 나타낸다. Preference: 각 데이터 포인트가 exemplar가 될 가능성을 나타내는 값이다. 알고리즘 특징 # 실제 데이터 포인트를 클러스터의 중심으로 사용한다.

BIRCH (Balanced Iterative Reducing and Clustering using Hierarchies) # BIRCH는 대용량 데이터셋을 효율적으로 처리할 수 있는 계층적 클러스터링 알고리즘이다. 메모리 사용량을 최소화하면서 점진적으로 클러스터를 구성하며, CF(Clustering Feature) 트리 구조를 사용하여 데이터를 요약한다. 주요 개념 # CF (Clustering Feature): 클러스터의 요약 정보를 담고 있는 3개 값의 튜플 (N, LS, SS)이다. N: 클러스터 내 데이터 포인트의 수 LS: 데이터 포인트들의 선형 합 SS: 데이터 포인트들의 제곱 합 CF Tree: 클러스터링 특징들을 계층적으로 저장하는 균형 트리 구조이다.

DBSCAN (Density-Based Spatial Clustering of Applications with Noise) # DBSCAN은 밀도 기반 클러스터링 알고리즘이다. 데이터의 밀도에 따라 클러스터를 형성한다. 이 알고리즘은 군집의 형태가 불규칙하거나 크기가 다양할 때 효과적으로 동작하며, 노이즈 데이터(이상치)를 효과적으로 분리할 수 있다. 주요 개념 # 반경 (ε, Epsilon): 각 데이터 포인트 주변에서 이웃을 찾기 위한 최대 거리이다. 최소 샘플 수 (minPts): 클러스터를 형성하기 위해 필요한 최소 데이터 포인트 수이다. 핵심 포인트 (Core Point): 주변 반경 내에 최소 샘플 수 이상의 데이터 포인트가 존재하는 데이터 포인트이다.

Gaussian Mixture Model (GMM) # Gaussian Mixture Model (GMM)은 각 클러스터를 다변량 가우시안 분포로 모델링하는 확률적 클러스터링 기법이다. EM (Expectation-Maximization) 알고리즘을 사용하여 각 클러스터의 평균, 공분산, 혼합 계수를 추정하고, 데이터가 각 클러스터에 속할 확률을 계산한다. 특징 # 클러스터가 타원형인 경우에도 유연하게 모델링할 수 있다. 데이터에 대한 확률적 해석을 제공한다. 초기값 및 클러스터의 수 설정에 민감할 수 있다. GMM은 데이터의 분포를 확률적으로 모델링하여 복잡한 클러스터 구조를 파악하는 데 유용하다.

K중심값 (K-means) # K-means는 데이터마이닝과 기계학습에서 가장 널리 사용되는 클러스터링(군집화) 알고리즘 중 하나다. 영어 원어인 “K-means"는 한국어로 K중심값 또는 K평균 등으로 번역되기도 하지만, 현업에서는 주로 “케이민즈"라고 원어 그대로 부르는 경우가 많다. 본 문서에서도 혼동을 피하기 위해 K-means로 표기한다. 여기서 “K"는 사용자가 미리 정하는 군집(클러스터)의 개수를 의미하며, “means"는 각 군집의 중심값(평균값, 대푯값)을 의미한다. 다만, K-means에서의 “mean"은 통계적 의미의 평균이라기보다는, 각 군집을 대표하는 중심점(centroid)이라는 개념에 더 가깝다. K-means의 핵심은 데이터를 K개의 그룹으로 나누되, 각 그룹 내의 데이터들이 서로 최대한 비슷하도록(즉, 중심점과의 거리가 최소가 되도록) 군집을 형성하는 것이다.

Mean Shift # Mean Shift는 비모수적(non-parametric) 밀도 기반 클러스터링 알고리즘으로, 데이터의 확률 밀도 함수의 모드(mode)를 찾아 클러스터를 형성한다. 각 데이터 포인트를 확률 밀도가 가장 높은 지점으로 이동시켜 클러스터의 중심을 찾는다. 주요 개념 # 커널 밀도 추정: 각 데이터 포인트 주변의 확률 밀도를 추정한다. 그래디언트 상승: 밀도 함수의 그래디언트 방향으로 데이터 포인트를 이동시킨다. 모드 탐색: 확률 밀도 함수의 극값(모드)을 찾아 클러스터 중심으로 설정한다. 알고리즘 단계 # 각 데이터 포인트에서 시작한다. 주변 윈도우 내의 데이터 포인트들의 평균을 계산한다.

OPTICS (Ordering Points To Identify the Clustering Structure) # OPTICS는 DBSCAN의 확장된 형태로, 다양한 밀도를 가진 클러스터를 효과적으로 찾을 수 있는 밀도 기반 클러스터링 알고리즘이다. DBSCAN과 달리 고정된 ε 값 대신 클러스터링 순서(ordering)를 생성하여 다양한 밀도 수준에서 클러스터를 추출할 수 있다. 주요 개념 # 핵심 거리 (Core Distance): 특정 포인트가 핵심 포인트가 되기 위한 최소 반경이다. 도달 거리 (Reachability Distance): 한 포인트에서 다른 포인트로의 도달 가능성을 나타내는 거리이다. 클러스터링 순서: 데이터 포인트들의 처리 순서로, 도달 거리를 기준으로 정렬된다.

Ward 연결법 (Ward Linkage) # Ward 연결법은 계층적 클러스터링에서 사용되는 연결 기준(linkage criterion) 중 하나로, 클러스터 내 분산의 증가를 최소화하는 방향으로 클러스터를 병합하는 방법이다. 이 방법은 비교적 균등한 크기의 구형 클러스터를 생성하는 경향이 있다. 주요 개념 # 클러스터 내 제곱합 (Within-cluster Sum of Squares, WSS): 각 클러스터 내 데이터 포인트들과 클러스터 중심 간의 거리 제곱합이다. Ward 거리: 두 클러스터를 병합했을 때 증가하는 WSS의 양을 의미한다. 분산 최소화: 병합 시 전체 분산의 증가량을 최소화하는 것을 목표로 한다.

계층적 군집화 (Hierarchical Clustering) # 계층적 군집화는 데이터를 계층적인 트리 구조(dendrogram)로 표현하여 클러스터를 구성하는 방법이다. 주요 방식은 두 가지가 있다: 병합적 방법 (Agglomerative): 각 데이터 포인트를 개별 클러스터로 시작하여, 가장 유사한 클러스터들을 반복적으로 병합한다. 분할적 방법 (Divisive): 전체 데이터를 하나의 클러스터로 시작하여, 점진적으로 클러스터를 분할해 나간다. 알고리즘 작동 원리 # 병합적 방법 (Agglomerative) 단계 # 각 데이터 포인트를 개별 클러스터로 초기화 모든 클러스터 쌍 간의 거리를 계산 가장 가까운 두 클러스터를 병합 새로운 클러스터와 다른 클러스터 간의 거리를 다시 계산 모든 데이터가 하나의 클러스터가 될 때까지 2-4단계를 반복 거리 측정 방법 # 클러스터 간의 거리를 측정하는 다양한 방법이 있다:

스펙트럴 클러스터링 (Spectral Clustering) # 스펙트럴 클러스터링은 그래프 이론과 선형 대수학을 기반으로 하는 클러스터링 알고리즘이다. 데이터를 그래프로 표현하고, 그래프의 라플라시안 행렬의 고유벡터(eigenvector)를 사용하여 클러스터를 형성한다. 주요 개념 # 유사도 그래프: 데이터 포인트들을 노드로, 유사도를 엣지로 표현한 그래프이다. 라플라시안 행렬: 그래프의 구조적 특성을 나타내는 행렬이다. 고유벡터: 라플라시안 행렬의 고유벡터를 사용하여 차원을 축소한 후 클러스터링을 수행한다. 알고리즘 단계 # 데이터 포인트 간의 유사도를 계산하여 유사도 행렬을 구성한다. 유사도 행렬로부터 라플라시안 행렬을 계산한다.