CluStream은 사용자 지정 온라인 클러스터링 쿼리를 기반으로 진화하는 데이터 스트림의 클러스터링을 위한 알고리즘입니다. 클러스터링 프로세스를 온라인 및 오프라인 구성 요소로 나눕니다.
온라인 구성 요소는 마이크로 클러스터를 사용하여 데이터 스트림에 대한 요약 통계를 계산 및 저장하고 마이크로 클러스터의 증분 온라인 계산 및 유지 관리를 수행합니다. 오프라인 구성 요소는 기울어진 시간 프레임 모델을 기반으로 하는 저장된 요약 통계를 사용하여 매크로 클러스터링을 수행하고 다양한 사용자 질문에 답변합니다.
클러스터는 과거 및 현재 스트림 데이터 정보를 기반으로 하는 데이터 스트림을 발전시키며, 기울기에 따라 서로 다른 수준의 세분성에서 마이크로클러스터 세트의 스냅샷을 저장하는 기울어진 시간 프레임 모델(예:점진적 로그 모델)이 채택됩니다. 최근에.
여기서 직관은 더 오래된 이벤트와 반대로 더 최근의 이벤트에 대해 더 많은 정보가 필요하다는 것입니다. 저장된 정보는 기록 관련 사용자별 클러스터링 쿼리를 처리하는 데 사용할 수 있습니다. CluStream의 마이크로 클러스터는 클러스터링 기능으로 정의됩니다.
CluStream은 시간 영역을 포함하도록 BIRCH에서 개발된 클러스터링 기능의 개념을 확장합니다. 클러스터링 기능의 시간적 확장으로서, d차원 포인트 세트에 대한 미세다발,X1 , . . . , Xn , 타임스탬프 포함, T1 ,...,Tn , (2d +3) 튜플(CF2 x ,CF1 x ,CF2 t , CF1 t , n), 여기서 CF2 x 및 CF1 x CF2 t 인 동안 d차원 벡터 , CF1 t , n은 스칼라입니다. CF2 x 차원당 데이터 값의 제곱합, 즉 $\sum_{i=1}^{n}{X_{i}}^{2}$
를 유지합니다.마찬가지로 각 차원에 대해 데이터 값의 합계가 CF1 x 에서 유지됩니다. . 통계적 관점에서 CF2 x 및 CF1 x 데이터의 2차 및 1차 모멘트를 각각 나타냅니다. 타임스탬프의 제곱합은 CF2 t 에서 유지됩니다. . 타임스탬프의 합계는 CF1 t 에서 유지됩니다. . 마지막으로 마이크로클러스터의 데이터 포인트 수는 n으로 유지됩니다.
클러스터링 기능에는 데이터 스트림 클러스터 분석에 매우 유용한 가산 및 감산 속성이 있습니다. 예를 들어, 두 개의 마이크로클러스터는 각각의 클러스터링 기능을 추가하여 병합할 수 있습니다. 또한 많은 메모리를 사용하지 않고도 많은 수의 마이크로 클러스터를 유지 관리할 수 있습니다. 이러한 미세다발의 스냅샷은 기울어진 시간대를 기준으로 주요 시점에 저장됩니다.
온라인 마이크로 클러스터 처리는 통계 데이터 수집 및 마이크로 클러스터 업데이트와 같은 두 단계로 나뉩니다. 첫 번째 단계에서 총 q개의 마이크로클러스터,M1 ,..., Mq , 유지되며, 여기서 q는 일반적으로 자연 클러스터의 수보다 훨씬 크며 사용 가능한 메모리 양에 의해 결정됩니다.
두 번째 단계에서는 마이크로 클러스터가 업데이트됩니다. 각각의 새 데이터 포인트는 기존 클러스터나 새 클러스터에 추가됩니다. 새로운 클러스터가 필요한지 여부를 결정할 수 있으며 각 클러스터에 대한 최대 경계가 정의됩니다.