STREAM 알고리즘이란?
STREAM은 데이터 스트림 환경에서 k-중심(k-medians) 문제를 해결하기 위해 고안된 단일 패스(one-pass), 상수 인자 근사 알고리즘입니다. 스트림 데이터는 전체를 저장해 두고 반복해서 처리할 수 없기 때문에, 제한된 자원 안에서도 고품질의 군집화 결과를 얻을 수 있도록 설계된 것이 특징입니다.
k-중심(k-medians) 문제의 정의
k-중심 문제는 N개의 데이터 포인트를 k개의 군집(cluster)으로 나누어, 각 포인트와 자신이 속한 군집의 중심 사이 제곱 오차 합(Sum of Squared Error, SSQ)이 최소화되도록 만드는 군집화 문제입니다. 핵심 아이디어는 서로 유사한 데이터 포인트들은 같은 군집에 배치하고, 다른 군집에 속한 포인트들과는 차별화하는 것입니다.
STREAM의 동작 방식
스트림 데이터 모델에서는 각 데이터 포인트를 한 번만 확인할 수 있으며, 메모리와 처리 시간도 제한적입니다. 이러한 제약 조건 속에서 고품질 군집화를 구현하기 위해 STREAM 알고리즘은 주메모리에 들어갈 수 있는 크기의 m개 포인트 단위 버킷(bucket, 배치)으로 데이터 스트림을 나누어 처리합니다.
각 버킷 bi에 대해 STREAM은 버킷 내부의 포인트들을 k개 군집으로 묶습니다. 이후 버킷 정보를 요약하여 k개 군집 중심에 관한 정보만 유지하는데, 이때 각 군집 중심에는 해당 군집에 할당된 포인트 수가 가중치로 부여됩니다.
그다음 STREAM은 원본 포인트들은 폐기하고 중심 정보만 남깁니다. 충분한 수의 중심이 누적되면, 가중치가 적용된 중심들을 대상으로 다시 군집화를 수행하여 새로운 O(k)개의 군집 중심을 생성합니다. 이 과정을 반복함으로써 매 단계마다 최대 m개의 포인트만 유지됩니다.
결과적으로 STREAM은 데이터 스트림 k-중심 문제에 대해 단일 패스, O(kN) 실행 시간, O(Nε) 공간(ε < 1인 상수), 그리고 상수 인자 근사를 보장하는 알고리즘이 됩니다.
STREAM의 한계
STREAM은 정해진 공간과 시간 안에서 품질 높은 k-중심 군집을 생성할 수 있지만, 데이터의 변화(evolution)와 시간 세분성(time granularity)은 고려하지 않습니다. 그 결과 스트림에서 오래되어 더 이상 유효하지 않은 데이터가 군집화 결과를 지배하게 될 수 있습니다.
또한 군집의 특성은 평가하는 시점과 측정하는 시간 범위(time horizon)에 따라 달라질 수 있습니다. 예를 들어 어떤 사용자는 지난주, 지난달, 또는 지난 1년간 형성된 군집을 각각 확인하고 싶어할 수 있는데, 이러한 결과들은 서로 다를 수 있습니다. 따라서 데이터 스트림 군집화 알고리즘은 사용자가 정의한 기간에 대해 대화형(interactive) 방식으로 군집을 계산할 수 있는 유연성까지 함께 지원해야 합니다.
CluStream: 진화하는 데이터 스트림의 군집화
CluStream은 사용자가 지정한 온라인 군집화 질의에 기반하여 진화하는 데이터 스트림을 군집화하기 위한 알고리즘입니다. CluStream은 군집화 과정을 온라인과 오프라인이라는 두 가지 구성 요소로 분리한다는 점이 핵심입니다.
온라인 컴포넌트는 마이크로 클러스터(micro-cluster)를 활용해 데이터 스트림에 대한 요약 통계량을 계산하고 저장하며, 마이크로 클러스터의 점진적인 온라인 계산과 유지보수를 담당합니다. 오프라인 컴포넌트는 저장된 요약 통계량을 바탕으로 매크로 클러스터링(macro-clustering)을 수행하고 다양한 사용자 질의에 응답하며, 이 과정은 기울어진 시간 프레임(tilted time frame) 모델에 의존합니다.
과거 데이터와 현재 스트림 데이터 정보를 모두 반영하여 진화하는 데이터 스트림을 군집화하기 위해, CluStream은 기울어진 시간 프레임 모델(예: 점진적 로그 모델)을 채택합니다. 이 모델은 데이터의 최근성(recency)에 따라 서로 다른 세분성 수준으로 마이크로 클러스터 집합의 스냅샷을 저장함으로써, 다양한 시간 범위의 군집 분석을 효율적으로 지원합니다.