COBWEB 알고리즘이란?
COBWEB은 개념 군집화(conceptual clustering)에 사용되는 대표적인 증분 학습(incremental learning) 알고리즘입니다. 이 알고리즘은 객체들을 하나씩 분류 트리(classification tree)에 점진적으로 삽입하면서 군집 구조를 형성합니다.
새로운 객체가 들어오면 COBWEB은 트리를 따라 내려가는 경로를 따라 이동하면서 지나가는 노드들의 카운트 값을 갱신하고, 해당 객체를 수용할 '최적 호스트(best host)', 즉 가장 적합한 노드를 탐색합니다.
최적 배치 위치를 결정하는 방법
최적 호스트를 찾는 과정은 다음과 같이 진행됩니다.
먼저 대상 객체를 각 노드에 임시로 배치해 보고, 그 결과로 만들어지는 분할(partition)의 범주 유틸리티(category utility)를 계산합니다. 그중 범주 유틸리티가 가장 높게 나타나는 배치가 해당 객체에게 가장 적합한 호스트가 됩니다.
또한 COBWEB은 기존 노드에 배치하는 경우뿐만 아니라, 객체를 위해 새로운 노드를 생성하는 경우의 범주 유틸리티도 함께 계산합니다. 그런 다음 기존 클래스에 배치했을 때와 새 클래스를 만들었을 때의 분할 결과를 비교하여, 범주 유틸리티 값이 가장 큰 쪽을 최종 선택합니다.
이러한 방식의 큰 장점 중 하나는 사용자가 군집의 개수를 직접 지정해 줄 필요가 없다는 점입니다. COBWEB은 스스로 파티션 내 클래스 수를 자동으로 조정할 수 있기 때문입니다.
병합(Merging)과 분할(Splitting) 연산자
COBWEB에는 입력 데이터의 순서에 덜 민감하게 만들어 주는 두 가지 핵심 연산자가 있습니다. 바로 병합(merging)과 분할(splitting)입니다.
객체가 삽입될 때, 두 개의 최적 호스트 후보가 있다면 이들을 하나의 클래스로 병합하는 것이 유리한지 평가합니다. 동시에, 최적 호스트의 자식 노드들을 현재의 여러 범주 사이에서 분할하는 것이 더 나은지도 고려합니다. 이러한 판단 역시 모두 범주 유틸리티를 기준으로 이루어집니다.
병합과 분할 연산자를 통해 COBWEB은 양방향 검색(bidirectional search)을 수행할 수 있습니다. 예를 들어, 이전에 수행된 분할을 병합이 되돌릴 수도 있습니다. 이 덕분에 입력 순서가 달라져도 보다 안정적인 군집 구조를 얻을 수 있습니다.
COBWEB의 한계점
COBWEB은 강력한 알고리즘이지만 몇 가지 명확한 한계를 가지고 있습니다.
1. 속성 간 통계적 독립 가정
COBWEB은 각 속성에 대한 확률 분포들이 서로 통계적으로 독립이라고 가정합니다. 그러나 실제 데이터에서는 속성들 간에 상관관계(correlation)가 존재하는 경우가 많으므로, 이 가정이 항상 성립하지는 않습니다.
2. 높은 갱신 및 저장 비용
각 군집을 확률 분포 형태로 기술하기 때문에 군집 정보를 갱신하고 저장하는 비용이 상당히 큽니다. 특히 속성이 가질 수 있는 값의 종류가 매우 많을 때 문제가 심해지는데, 시간 및 공간 복잡도가 속성의 개수뿐 아니라 각 속성이 가지는 값의 개수에도 의존하기 때문입니다.
3. 편향된 입력에 대한 트리 불균형
입력 레코드가 특정 방향으로 치우쳐(skewed) 있는 경우, 생성되는 분류 트리가 높이 균형(height-balanced)을 이루지 못할 수 있습니다. 이 경우 트리의 깊이가 깊어지면서 시간 및 공간 복잡도가 크게 악화될 수 있습니다.
연속 데이터를 위한 확장판: CLASSIT
CLASSIT은 COBWEB을 연속형(실수 값) 데이터의 증분 군집화로 확장한 알고리즘입니다. COBWEB이 이산형 속성을 대상으로 하는 것과 달리, CLASSIT은 각 노드의 모든 속성에 대해 연속 정규 분포(평균과 표준편차)를 저장합니다.
또한 범주 유틸리티 측정 방식도 수정되었습니다. COBWEB에서 이산형 속성들의 값을 합산(sum)하는 것과 달리, CLASSIT은 연속형 속성들에 대해 값을 적분(integral)하는 방식의 범주 유틸리티를 사용합니다.