개념적 클러스터링(conceptual clustering)은 머신러닝에서 사용되는 클러스터링 기법의 하나로, 레이블이 없는(unlabeled) 객체 집합이 주어졌을 때 이들 객체에 대한 분류 체계를 만들어내는 방식입니다.
일반적인 클러스터링이 유사한 객체들의 그룹을 식별하는 데 그치는 것과 달리, 개념적 클러스터링은 한 단계 더 나아가 각 그룹에 대한 특징적 정의까지 발견합니다. 즉, 각 그룹은 단순한 객체의 모음이 아니라 하나의 개념(concept) 또는 클래스(class)를 정의하게 됩니다.
개념적 클러스터링의 2단계 프로세스
개념적 클러스터링은 크게 두 단계로 이루어집니다. 먼저 클러스터링을 수행한 뒤, 이어서 특성화(characterization) 과정을 진행합니다. 따라서 클러스터링의 품질은 단일 객체만으로 판단되지 않으며, 전체 개념 구조의 관점에서 평가됩니다.
대부분의 개념적 클러스터링 기법은 확률 측정값을 활용하는 통계적 방법을 채택하여 개념이나 클러스터를 결정하며, 도출된 각 개념을 정의할 때 일반적으로 확률적 서술(probabilistic description)이 사용됩니다.
대표 알고리즘, COBWEB
COBWEB은 유명하고 간단한 점진적(incremental) 개념적 클러스터링 방법입니다. 입력 객체는 범주형 속성-값 쌍(categorical attribute-value pairs)으로 정의되며, COBWEB은 분류 트리(classification tree) 형태의 계층적 클러스터링을 수행합니다.
분류 트리와 결정 트리의 차이
분류 트리는 결정 트리(decision tree)와 다릅니다. 분류 트리의 각 노드는 하나의 개념을 정의하며, 해당 노드 아래로 분류된 객체들을 요약하는 개념의 확률적 서술을 포함합니다.
이 확률적 서술에는 개념의 확률과 함께 $P(A_{i}=v_{ij}|C_{k})$ 형태의 조건부 확률이 포함됩니다. 여기서 $A_{i}=v_{ij}$는 속성-값 쌍(i번째 속성이 j번째 가능한 값을 가짐)을 의미하고, $C_{k}$는 개념 클래스를 나타냅니다.
범주 유틸리티(Category Utility)
COBWEB은 범주 유틸리티(Category Utility, CU)라고 불리는 휴리스틱 평가 척도를 사용하여 트리 구축 과정을 안내합니다. 범주 유틸리티는 다음과 같이 정의됩니다.
$$\frac{\sum_{k=1}^{n}P(C_{k})\left [\sum_{i}\sum_{j}P(A_{i}=v_{ij}|C_{k})^{2}-\sum_{i}\sum_{j}P(A_{i}=v_{ij})^{2}\right ]}{n}$$
여기서 n은 트리의 특정 수준에서 분할(partition) {C1, C2, ..., Cn}을 이루는 노드, 개념 또는 '범주'의 개수입니다.
다시 말해, 범주 유틸리티는 어떤 분할이 주어졌을 때 완벽하게 맞힐 수 있는 속성값의 기대 개수($P(C_{k})\sum_{i}\sum_{j}P(A_{i}=v_{ij}|C_{k})^{2}$ 항에 해당)가, 그러한 지식이 없을 때의 올바른 추측 기대 개수($\sum_{i}\sum_{j}P(A_{i}=v_{ij})^{2}$ 항에 해당)보다 얼마나 증가하는지를 나타냅니다.
범주 유틸리티는 클래스 내 유사성과 클래스 간 비유사성에 보상을 부여하는 구조로 되어 있습니다.
클래스 내 유사성(Intraclass Similarity)
확률 $P(A_{i}=v_{ij}|C_{k})$에 해당합니다. 이 값이 높을수록 해당 속성-값 쌍을 공유하는 클래스 멤버의 비율이 높아지며, 이 쌍을 통해 클래스 멤버를 더욱 정확하게 예측할 수 있습니다.
클래스 간 비유사성(Interclass Dissimilarity)
확률 $P(C_{k}|A_{i}=v_{ij})$에 해당합니다. 이 값이 높을수록 대비되는 클래스에서 해당 속성-값 쌍을 공유하는 객체가 적어지며, 이 쌍이 특정 클래스를 예측하는 데 더욱 유용한 지표가 됩니다.
COBWEB의 트리 탐색 과정
COBWEB은 새로운 객체를 정의할 '최적 호스트(best host)', 즉 가장 적합한 노드를 찾기 위해 적절한 경로를 따라 트리를 내려가면서 도중에 카운트를 갱신합니다.
이때의 결정은 객체를 일시적으로 각 노드에 배치해 보고, 그 결과로 생성되는 분할의 범주 유틸리티를 평가하는 방식으로 이루어집니다. 최종적으로 가장 높은 범주 유틸리티를 산출하는 배치 위치가 해당 객체의 최적 호스트로 선택됩니다.