STREAM은 k-중앙값 문제에 대해 생성된 개별 통과, 상수 요소 근사 알고리즘입니다. k-중앙값 문제는 N 데이터 포인트를 k 클러스터 또는 그룹으로 클러스터링하여 포인트와 포인트가 할당된 클러스터 중심 사이의 제곱합 오차(SSQ)가 최소화되도록 하는 것입니다. 아이디어는 유사한 포인트를 동일한 클러스터에 할당하는 것입니다. 여기서 이러한 포인트는 다른 클러스터의 포인트와 다릅니다.
스트림 데이터 모델에서 데이터 포인트는 한 번만 볼 수 있으며 메모리와 시간이 제한됩니다. 고품질 클러스터링을 구현할 수 있고 STREAM 알고리즘은 m 포인트의 버킷(또는 배치)에서 데이터 스트림을 처리하며 각 버킷은 메인 메모리에 맞습니다.
각 버킷에 대해 bi , STREAM은 버킷의 포인트를 k개의 클러스터로 클러스터링합니다. 그런 다음 k개의 센터에 관한 정보만 유지하여 버킷 정보를 요약하고 각 클러스터 센터는 해당 클러스터에 할당된 포인트 수로 가중치를 부여합니다.
그런 다음 STREAM은 포인트를 버리고 중앙 정보만 유지합니다. 충분한 중심이 수집되었으므로 가중치 중심을 군집하여 O(k) 군집 중심의 또 다른 그룹을 만듭니다. 이것은 모든 레벨에서 최대 m개의 포인트가 유지되도록 반복됩니다. 이 접근 방식은 1회 통과, O(kN)-시간, O(N ε )-공간(일부 상수 ε <1), 데이터 스트림 k-중앙값에 대한 상수 인자 근사 알고리즘.
STREAM은 명확한 영역과 시간으로 품질 k-중앙값 클러스터를 변경합니다. 그러나 기록의 발전이나 시간 세분성을 다루지 않았습니다. 클러스터링은 스트림의 오래된 오래된 데이터에 의해 지배될 수 있습니다. 클러스터의 기능은 클러스터가 평가되는 순간과 측정되는 시간 범위에 따라 달라질 수 있습니다.
예를 들어, 사용자는 지난 주, 지난 달 또는 작년에 나타난 클러스터를 테스트해야 할 수 있습니다. 이것들은 다를 수 있습니다. 따라서 데이터 스트림 클러스터링 알고리즘은 대화형 방식으로 사용자 정의 기간 동안 클러스터를 계산할 수 있는 유연성도 지원해야 합니다.
CluStream은 사용자 지정 온라인 클러스터링 쿼리를 기반으로 진화하는 데이터 스트림의 클러스터링을 위한 알고리즘입니다. 클러스터링 프로세스를 온라인 및 오프라인 구성 요소로 나눕니다.
온라인 구성 요소는 마이크로 클러스터를 사용하여 데이터 스트림에 대한 요약 통계를 계산 및 저장하고 마이크로 클러스터의 증분 온라인 계산 및 유지 관리를 수행합니다. 오프라인 구성 요소는 매크로 클러스터링을 수행하고 기울어진 시간 프레임 모델에 따라 달라지는 저장된 요약 통계를 사용하여 여러 사용자 질문을 해결합니다.
과거 및 현재 스트림 데이터 정보를 기반으로 하는 클러스터 진화 데이터 스트림은 최근에 따라 다른 수준의 세분성에서 마이크로클러스터 세트의 스냅샷을 저장하는 기울어진 시간 프레임 모델(예:점진적 로그 모델)이 채택됩니다.