클러스터링

클러스터링(군집 분석이라고도 함)은 분석가가 정의한 특정 유사도 또는 거리 측도에 따라 객체 집합을 그룹(클러스터)으로 분할하는 데이터 분석 기법으로, 같은 클러스터 내의 객체들은 다른 클러스터의 객체들보다 서로 더 유사하다. 이는 탐색적 데이터 분석의 주요 과업이자 통계적 데이터 분석의 일반적인 기법으로, 패턴 인식, 이미지 분석, 정보 검색, 생물정보학, 데이터 압축, 컴퓨터 그래픽스, 머신 러닝 등의 분야에서 사용된다. 비지도 학습 방법으로서 클러스터링은 레이블이 있는 데이터에 의존하지 않으며, 대신 클래스 레이블에 대한 사전 지식 없이 데이터에 내재된 구조와 그룹을 발견한다.

"클러스터링"이라는 용어는 단일한 특정 알고리즘이 아니라 일련의 알고리즘과 과업을 포괄한다. 알고리즘마다 클러스터가 무엇을 의미하는지, 그리고 클러스터를 효율적으로 식별하는 방법에 대한 이해가 크게 다르다. 널리 쓰이는 클러스터 개념으로는 구성원 간 거리가 작은 그룹, 데이터 공간의 밀집 영역, 구간, 특정 통계적 분포 등이 있다. 따라서 클러스터링은 다목적 최적화 문제로 공식화될 수 있으며, 적절한 알고리즘과 매개변수 설정(거리 함수, 밀도 임계값, 예상 클러스터 수 등)은 개별 데이터셋과 결과의 의도된 용도에 따라 달라진다. 클러스터 분석은 자동적인 작업이 아니라 지식 발견 또는 상호작용적 다목적 최적화의 반복적 과정으로, 원하는 속성을 가진 결과를 얻을 때까지 데이터 전처리와 모델 매개변수를 조정하는 시행착오가 자주 요구된다.

클러스터링이라는 용어 외에도 자동 분류, 수치 분류학, 보트리올로지(그리스어 βότρυς '포도'에서 유래), 유형론적 분석, 커뮤니티 탐지 등 여러 유사한 용어가 존재한다. 미묘한 차이는 주로 결과의 사용 방식에 있다. 데이터 마이닝에서는 결과로 얻은 그룹 자체가 관심 대상인 반면, 자동 분류에서는 결과의 판별력이 관심 대상이다.

역사

클러스터 분석은 1932년 Driver와 Kroeber의 연구로 인류학에서 시작되었다. 1938년 Joseph Zubin과 1939년 Robert Tryon에 의해 심리학에 도입되었으며, 1943년부터 Raymond Cattell이 성격 심리학의 특성 이론 분류에 유명하게 사용하였다. 그 이후 클러스터링은 수많은 과학 분야에서 기본 도구로 발전해 왔으며, 수십 년에 걸쳐 수백 개의 알고리즘이 발표되었다.

클러스터 모델

"클러스터"의 개념은 정확히 정의할 수 없으며, 이것이 클러스터링 알고리즘의 다양성을 설명하는 핵심 이유이다. 공통 분모는 데이터 객체의 그룹이라는 점이다. 그러나 연구자마다 서로 다른 클러스터 모델을 사용하며, 각 모델은 다양한 알고리즘으로 구현될 수 있다. 이러한 클러스터 모델을 이해하는 것은 알고리즘 간 차이를 이해하는 데 필수적이다. 대표적인 클러스터 모델은 다음과 같다.

• 연결성 모델: 계층적 클러스터링은 거리 연결성에 기반한 모델을 구축하며, 객체 간 근접성에 따라 객체를 연결하여 클러스터를 형성한다.
• 중심점 모델: k-평균 알고리즘은 각 클러스터를 단일 평균 벡터(중심점)로 표현하고 객체를 가장 가까운 중심점에 할당한다.
• 분포 모델: 클러스터는 통계적 분포를 사용하여 모델링되며, 기대값 최대화(EM) 알고리즘에서 사용되는 다변량 정규 분포가 그 예이다.
• 밀도 모델: DBSCAN, OPTICS, HDBSCAN과 같은 알고리즘은 클러스터를 데이터 공간에서 희소 영역으로 분리된 연결된 밀집 영역으로 정의한다.
• 부분공간 모델: 이중 클러스터링(공동 클러스터링 또는 이중 모드 클러스터링이라고도 함)에서 클러스터는 클러스터 구성원과 관련 속성 모두로 모델링되며, 클러스터가 데이터의 서로 다른 부분공간에 존재할 수 있게 한다.
• 그룹 모델: 일부 알고리즘은 결과에 대한 정교한 모델을 제공하지 않고 단순히 그룹 정보만 제공한다.
• 그래프 기반 모델: 그래프에서 모든 두 노드가 간선으로 연결된 노드의 부분집합인 클리크는 클러스터의 원형적 형태로 간주될 수 있다. 완전 연결 요구 조건을 완화한 준클리크는 HCS 클러스터링 알고리즘과 같은 알고리즘에서 사용된다.
• 부호 그래프 모델: 부호 그래프에서 모든 경로는 간선의 부호 곱으로부터 부호를 가진다. 균형 이론 가정 하에서 간선의 부호가 바뀔 수 있으며, 그 결과 이분된 그래프가 생성된다. 더 약한 "클러스터 가능성 공리"(어떤 순환도 정확히 하나의 음의 간선을 갖지 않음)는 둘 이상의 클러스터 또는 양의 간선만 있는 부분 그래프를 결과로 산출한다.
• 신경망 모델: 가장 잘 알려진 비지도 신경망은 자기 조직화 맵이며, 이러한 모델은 일반적으로 위 모델 중 하나 이상과 유사한 것으로 특징지을 수 있다. 신경망이 주성분 분석 또는 독립 성분 분석의 형태를 구현할 때 부분공간 모델도 포함된다.

클러스터링의 유형

"클러스터링"은 본질적으로 클러스터의 집합이며, 일반적으로 데이터셋의 모든 객체를 포함한다. 또한 클러스터 간의 관계(예: 서로 중첩된 클러스터의 계층 구조)를 명시할 수도 있다. 클러스터링은 대략 다음과 같이 구분될 수 있다.

• 하드 클러스터링: 각 객체는 클러스터에 속하거나 속하지 않는다.
• 소프트 클러스터링(퍼지 클러스터링이라고도 함): 각 객체는 소속 가능성과 같은 특정 정도로 각 클러스터에 속한다.

더 세부적인 구분은 다음과 같다.

• 엄격한 분할 클러스터링: 각 객체는 정확히 하나의 클러스터에 속한다.
• 이상치가 있는 엄격한 분할 클러스터링: 객체는 어떤 클러스터에도 속하지 않을 수 있으며, 이 경우 이상치로 간주된다.
• 중첩 클러스터링(대안 클러스터링, 다중 뷰 클러스터링이라고도 함): 객체는 둘 이상의 클러스터에 속할 수 있으며, 일반적으로 하드 클러스터를 포함한다.
• 계층적 클러스터링: 하위 클러스터에 속하는 객체는 상위 클러스터에도 속하며, 트리와 같은 구조를 만든다.
• 부분공간 클러스터링: 중첩 클러스터링이지만, 고유하게 정의된 부분공간 내에서 클러스터는 중첩되지 않을 것으로 기대된다.

알고리즘

클러스터링 알고리즘은 클러스터 모델에 따라 분류될 수 있다. 발표된 클러스터링 알고리즘은 100개가 넘을 수 있으며, 모든 알고리즘이 클러스터에 대한 모델을 제공하는 것은 아니므로 분류가 어렵다. 객관적으로 "올바른" 클러스터링 알고리즘은 존재하지 않는다. 언급되었듯이 "클러스터링은 보는 사람의 눈에 달려 있다." 실제로 공리적 접근법은 어떤 클러스터링 방법도 세 가지 기본 속성, 즉 규모 불변성(거리의 비례적 확장 하에서 결과가 변하지 않음), 풍부성(데이터의 모든 가능한 분할을 달성할 수 있음), 거리와 클러스터링 구조 간의 일관성을 동시에 충족할 수 없음을 보여준다. 특정 문제에 가장 적합한 알고리즘은 하나의 클러스터 모델을 다른 모델보다 선호할 수학적 이유가 없는 한 실험적으로 선택해야 하는 경우가 많다.

주요 클러스터링 알고리즘은 다음과 같다.

• K-평균: 클러스터 내 제곱합을 최소화하여 데이터를 k개의 클러스터로 분할하는 중심점 기반 알고리즘이다. 단순하고 효율적이지만 클러스터 수를 지정해야 하며 이상치에 민감하다.
• 계층적 클러스터링: 응집적(상향식) 또는 분할적(하향식) 방식으로 클러스터의 계층 구조를 구축한다. 사전 정의된 클러스터 수가 필요하지 않으며 덴드로그램을 생성한다.
• DBSCAN: 클러스터를 희소 영역으로 분리된 밀집 영역으로 식별하는 밀도 기반 알고리즘이다. 임의의 형태의 클러스터를 찾고 이상치를 처리할 수 있지만 엡실론과 최소 점수와 같은 매개변수 조정이 필요하다.
• 기대값 최대화(EM): 클러스터를 가우시안 분포로 모델링하고 우도를 최대화하기 위해 매개변수를 반복적으로 추정하는 분포 기반 알고리즘이다.
• OPTICS: DBSCAN의 확장으로 클러스터 순서를 생성하여 다양한 밀도에 더 강건하다.
• 자기 조직화 맵(SOM): 고차원 데이터를 저차원 격자에 매핑하여 위상적 관계를 보존하는 신경망 모델이다.

응용 분야

클러스터링은 다양한 영역에서 널리 사용된다. 패턴 인식에서는 분류 작업을 위해 데이터의 그룹을 식별하는 데 도움을 준다. 이미지 분석에서는 이미지 분할과 객체 탐지에 사용된다. 정보 검색에서는 검색과 추천을 위해 문서를 주제별로 구성한다. 생물정보학에서는 유사한 발현 패턴을 가진 유전자나 단백질을 그룹화한다. 데이터 압축에서는 그룹을 프로토타입으로 표현하여 데이터 크기를 줄인다. 컴퓨터 그래픽스에서는 색상 양자화와 메시 단순화에 기여한다. 인공 지능에서 클러스터링은 비지도 학습의 핵심 기법으로, 시스템이 레이블이 없는 예시 없이 패턴을 발견할 수 있게 한다.

과제와 고려 사항

클러스터링은 여러 과제를 제시한다. 최적의 클러스터 수를 결정하는 것은 종종 어려우며 도메인 지식이나 휴리스틱이 필요할 수 있다. 거리 측도의 선택은 결과에 큰 영향을 미치며, 일반적인 측도로는 유클리드 거리, 맨해튼 거리, 코사인 유사도가 있다. 고차원 데이터는 거리의 의미가 약해지는 차원의 저주를 겪을 수 있다. 클러스터링 결과는 초기화와 매개변수 설정에 민감하며 보편적인 해법은 없다. 또한 클러스터링의 반복적 특성상 결과는 실루엣 점수나 Rand 지수와 같은 내부 또는 외부 평가 지표를 사용하여 검증되어 원하는 속성을 충족하는지 확인해야 한다.

관련 개념

클러스터링은 차원 축소 및 이상 탐지와 같은 다른 비지도 학습 기법과 밀접하게 관련된다. 합성 샘플을 생성하기 위해 데이터 증강과 함께 사용되거나 지도 학습을 위한 전처리 단계에서 자주 사용된다. 딥 러닝의 맥락에서 클러스터링은 표현 학습을 위해 신경망 아키텍처에 통합될 수 있다. 클러스터링의 원리는 네트워크 분석의 커뮤니티 탐지와 마케팅의 시장 세분화의 기반이 되기도 한다.