CluStream 알고리즘 개요
CluStream은 사용자가 지정한 온라인 클러스터링 질의에 기반하여 끊임없이 변화하는(진화하는) 데이터 스트림을 클러스터링하기 위한 알고리즘입니다. 이 알고리즘의 핵심 아이디어는 전체 클러스터링 프로세스를 온라인(online) 단계와 오프라인(offline) 단계로 분리하는 것입니다.
온라인 구성 요소와 오프라인 구성 요소
온라인 구성 요소는 마이크로 클러스터(micro-cluster)를 활용해 데이터 스트림에 대한 요약 통계를 실시간으로 계산하고 저장하며, 이를 점진적으로(incrementally) 갱신하고 유지 관리합니다.
오프라인 구성 요소는 저장된 요약 통계를 바탕으로 매크로 클러스터링(macro-clustering)을 수행하고, 사용자가 제기하는 다양한 질문과 분석 요청에 답변합니다. 이때 활용되는 요약 통계는 기울어진 시간 프레임 모델(tilted time frame model)에 기반합니다.
기울어진 시간 프레임 모델(Tilted Time Frame Model)
CluStream은 과거 스트림 데이터와 현재 스트림 데이터 정보를 모두 반영하여 클러스터를 형성합니다. 이를 위해 최근성(recency)에 따라 서로 다른 세분화 수준으로 마이크로 클러스터 집합의 스냅샷(snapshot)을 저장하는 기울어진 시간 프레임 모델(예: 점진적 로그 모델)을 채택했습니다.
그 직관적인 배경은 다음과 같습니다. 오래된 사건보다 최근에 발생한 사건에 대해서는 더 많은 정보가 필요하다는 것입니다. 이렇게 저장된 정보는 시간 이력과 관련된 사용자 맞춤형 클러스터링 질의를 처리하는 데 활용될 수 있습니다.
마이크로 클러스터의 정의: 클러스터링 피처(Clustering Feature)
CluStream에서 마이크로 클러스터는 하나의 클러스터링 피처(clustering feature)로 정의됩니다. 즉, CluStream은 BIRCH에서 개발된 클러스터링 피처 개념을 시간(temporal) 영역까지 확장한 것입니다.
타임스탬프 T1, ..., Tn을 가진 d차원 포인트 X1, ..., Xn의 집합에 대한 마이크로 클러스터는 (2d + 3)개의 튜플 (CF2x, CF1x, CF2t, CF1t, n)로 정의됩니다. 여기서 CF2x와 CF1x는 d차원 벡터이고, CF2t, CF1t, n은 스칼라 값입니다.
- CF2x: 차원별 데이터 값의 제곱합, 즉 ∑i=1nXi2를 유지합니다. 통계학적으로 데이터의 2차 모멘트(second-order moment)에 해당합니다.
- CF1x: 차원별 데이터 값의 합을 유지합니다. 데이터의 1차 모멘트(first-order moment)를 나타냅니다.
- CF2t: 타임스탬프의 제곱합을 유지합니다.
- CF1t: 타임스탬프의 합을 유지합니다.
- n: 해당 마이크로 클러스터에 속한 데이터 포인트의 개수를 유지합니다.
클러스터링 피처의 가감(Additive/Subtractive) 특성
클러스터링 피처는 덧셈과 뺄셈 연산에 대해 닫혀 있는 성질을 가지며, 이는 데이터 스트림 클러스터 분석에서 매우 유용하게 활용됩니다. 예를 들어 두 마이크로 클러스터를 병합할 때는 각각의 클러스터링 피처를 단순히 더해주기만 하면 됩니다. 또한 이러한 구조 덕분에 많은 메모리를 소모하지 않고도 대량의 마이크로 클러스터를 유지할 수 있습니다. 이렇게 유지되는 마이크로 클러스터들의 스냅샷은 기울어진 시간 프레임에 따라 주요 시점에 저장됩니다.
온라인 마이크로 클러스터 처리 과정
온라인 마이크로 클러스터 처리는 크게 두 단계로 나뉩니다.
1단계 — 통계 데이터 수집: 총 q개의 마이크로 클러스터 M1, ..., Mq를 유지 관리합니다. 여기서 q는 일반적으로 자연스러운(natural) 클러스터 수보다 상당히 큰 값으로 설정되며, 사용 가능한 메모리 용량에 따라 결정됩니다.
2단계 — 마이크로 클러스터 갱신: 새로 도착하는 각 데이터 포인트는 기존 클러스터에 추가되거나 새로운 클러스터를 생성하여 할당됩니다. 새로운 클러스터가 필요한지 여부를 판단하기 위해 각 클러스터에는 최대 경계(maximum boundary)가 정의되어 있으며, 이 경계를 기준으로 신규 클러스터 생성 여부를 결정합니다.
정리
CluStream은 온라인·오프라인 분리 구조, 마이크로 클러스터 기반 요약 통계, 그리고 기울어진 시간 프레임 모델을 결합하여 빠르게 변화하는 데이터 스트림 환경에서도 효율적이면서도 유연한 클러스터링을 가능하게 하는 대표적인 데이터 스트림 클러스터링 알고리즘입니다.