Limitation of Previous Models

• Data compactness 중심의 한계: 기존의 K-Means와 Mixture models(GMM)는 주어진 데이터가 둥글게 뭉쳐 있는 형태(Compactness)를 띠어야만 군집화가 정상적으로 작동함
• 나선형(Concentric circles)이나 알파벳 궤적 등 복잡하게 얽혀 있는 강한 데이터 연결성(Strong data connectivity) 을 가지는 기하학적 분포에서는 기존 모델들의 군집화가 완벽히 실패함
• 이를 극복하고 데이터 간의 구조적 연결성을 보존하며 군집을 나누기 위해 Spectral (Graph) Clustering 기법이 도입됨

Spectral Clustering: Preliminaries

Eigenvectors and Eigenvalues

• 정방 행렬 A에 대해 Av = lambda v를 만족하는 영벡터가 아닌 v를 Eigenvector(고유벡터), lambda를 **Eigenvalue(고윳값)**라 함
• 동일한 Eigenvalue를 가지는 여러 개의 Eigenvector v_1, v_2, ..., v_k가 존재할 수 있으며, 이때 해당 Eigenvalue는 k의 대수적 중복도(Algebraic multiplicity)를 가짐
• 일반적인 N x N 크기의 행렬은 중복도를 포함하여 총 N개의 Eigenvector와 Eigenvalue 쌍을 지님
• Symmetric matrix (대칭 행렬) 의 고유 특성: 도출되는 모든 Eigenvalue가 허수가 아닌 실수(Real-valued)이며, 각 Eigenvector들은 서로 완벽하게 직교(Orthogonal)함
• Positive semi-definite (PSD) 행렬의 고유 특성: 임의의 실수 벡터 x에 대해 x^T A x >= 0을 만족하며, 이로 인해 도출되는 모든 Eigenvalue가 0 이상의 양수(Non-negative) 값만을 가짐

Graph Representations