반지도(semi-supervised) 클러스터링은 도메인 지식을 활용하여 레이블이 없는 데이터를 군집화하는 방법입니다. 도메인 지식은 일반적으로 인스턴스 간의 쌍별 제약 조건(pairwise constraints) 형태로 표현되거나, 추가로 제공되는 레이블이 지정된 인스턴스 집합의 형태로 표현됩니다.
반지도 클러스터링의 핵심 개념
비지도(unsupervised) 클러스터링만으로는 데이터의 숨겨진 구조를 완벽하게 파악하기 어려운 경우가 많습니다. 하지만 약한 형태의 감독 정보, 예컨대 동일한 클러스터에 속한다 또는 서로 다른 클러스터에 속한다고 레이블된 객체 쌍(pairwise constraints)을 활용하면 클러스터링의 품질을 획기적으로 향상시킬 수 있습니다.
이처럼 사용자의 피드백이나 안내 제약 조건(guidance constraints)에 의존하여 군집화를 수행하는 절차를 반지도 클러스터링이라고 부릅니다.
반지도 클러스터링의 두 가지 주요 접근 방식
반지도 클러스터링 기법은 크게 두 가지 클래스로 나눌 수 있습니다.
1. 제약 기반(Constraint-based) 반지도 클러스터링
사용자가 제공한 레이블이나 제약 조건을 활용하여 알고리즘이 더 적절한 데이터 분할에 도달하도록 유도하는 방식입니다. 구체적으로는 다음과 같은 방법이 포함됩니다.
- 제약 조건을 반영하도록 목적 함수(objective function)를 수정하는 방법
- 레이블이 지정된 객체를 기준으로 클러스터링 과정을 초기화하거나 제한하는 방법
2. 거리 기반(Distance-based) 반지도 클러스터링
감독 데이터의 레이블이나 제약 조건을 만족하도록 학습된 적응형 거리 측도(adaptive distance measure)를 활용하는 방식입니다. 실제로 다양한 적응형 거리 측도가 사용되어 왔습니다.
- EM(Expectation-Maximization) 알고리즘으로 학습된 문자열 편집 거리(string-edit distance)
- 최단 거리 알고리즘으로 조정된 유클리드 거리(Euclidean distance)
CLTree: 의사결정 트리 기반 클러스터링
CLTree(CLustering based on decision TREEs)는 비지도 클러스터링과 지도 분류(supervised classification)의 개념을 통합한 흥미로운 클러스터링 기법으로, 제약 기반 반지도 클러스터링의 대표적인 사례입니다.
CLTree의 핵심 아이디어는 클러스터링 문제를 분류 문제로 변환하는 것입니다. 구체적인 과정은 다음과 같습니다.
- 클러스터링 대상인 점들의 집합을 하나의 클래스에 속하는 것으로 간주하고 "Y"로 레이블합니다.
- 데이터 공간 전체에 걸쳐 상대적으로 균일하게 분포된 "존재하지 않는 점(nonexistence points)"들을 별도의 클래스 "N"으로 삽입합니다.
이렇게 하면 데이터 영역을 밀집(dense) 영역과 공백(sparse) 영역으로 나누는 원래의 클러스터링 문제가, "Y" 점과 "N" 점을 구별해내는 분류(classification) 문제로 바뀌게 됩니다.
변환된 문제는 의사결정 트리(decision tree) 유도 방식을 통해 해결할 수 있습니다. 예를 들어 2차원 공간에서 의사결정 트리가 "Y"와 "N"을 구분하는 경계를 학습하면, 결과적으로 두 개의 클러스터가 "Y" 점들만으로 자연스럽게 식별됩니다.
CLTree의 한계점
CLTree 방식은 직관적이지만 몇 가지 단점이 존재합니다.
- 계산 오버헤드: 원본 데이터에 대량의 "N" 점을 삽입해야 하므로 불필요한 계산 비용이 발생할 수 있습니다.
- 고차원 공간의 문제: 매우 높은 차원의 공간에서 점들이 진정으로 균일하게 분포하도록 만들기는 사실상 불가능합니다. 균일한 커버리지를 위해서는 지수적으로 많은 수의 점이 필요하기 때문입니다.
따라서 CLTree를 실무에 적용할 때는 데이터의 차원과 규모를 고려하여 "N" 점의 삽입 전략을 신중하게 설계해야 합니다.