Hierarchical Density-Based Clustering for Data Stream over Sliding Window

Abstract

데이터 스트림은 응용 프로그램이 급격히 증가함에 따라 최근 몇 년 동안 뜨거운 관심 주제가 되었다. 또한, 전자 기기 및 네트워크의 과도한 사용으로 인해 데이터 스트림이 지속적으로 생성되고 있다. 따라서 데이터 스트림은 빠른 데이터 포인트 생성과 같은 정적 데이터와 다른 고유한 특성을 가지며 시간이 지남에 따라 무한한 크기에 도달할 수 있다. 위에서 언급한 데이터 스트림의 고유한 특성으로 인해 데이터 스트림 클러스터링 알고리즘에 대한 요구 사항은 점점 더 복잡해지고 있다. 정적 데이터에 대한 클러스터링 알고리즘의 기본 요구 사항은 데이터 내에서 임의의 모양과 클러스터 수를 추출할 수 있어야 한다. 또한 스트림 클러스터링 알고리즘은 시간과 공간의 제약으로 인해 들어오는 데이터를 빠르고 효율적으로 처리하는 것이 중요하다. 기존의 밀도 기반 알고리즘은 들어오는 스트림 내에서 임의의 모양과 숫자의 클러스터를 성공적으로 찾았지만 밀도(ε)가 클러스터당 최소 포인트(minPts)와 함께 사용자 고정 매개변수인 경우가 많기 때문에 밀도 변화를 발견할 때는 여전히 부족하다. 본 논문에서는 데이터 스트림 내에서 밀도가 다른 클러스터를 감지할 수 있는 계층적 밀도 기반 클러스터링 알고리즘을 기반으로 하는 StreamHD 라는 스트림 클러스터링 알고리즘을 제안한다. 제안된 알고리즘은 사용자 개입을 최소화하면서 클러스터의 밀도 임계 값을 독립적으로 감지합니다. 또한 StreamHD 는 코어 밀도를 계산할 때 고려하고 최소 클러스터 크기도 결정하는 주어진 지점의 인접 지점 수를 결정하는 minPts 와 윈도우 크기의 두 가지 사용자 매개변수만 필요하다. StreamHD 는 스트림 클러스터링 알고리즘 중 사용자 개입이 가장 적다고 할 수 있다. 또한 실제 데이터셋과 합성 데이터셋에 대한 실험 결과 우리가 제안한 알고리즘이 각 윈도우 처리 시간과 클러스터 품질 측면에서 비교 알고리즘 중 가장 우수한 성능을 보였다.

Data stream has become a hot topic of interest in recent years as its applications are increasing drastically. In addition, data streams are being continuously generated as a result of excessive usage of electronic devices and network. Thus, data streams have these unique characteristics differing to the static data such as speedy data point generation and possibly get to an unbounded size over time. Due to the distinctive nature of data stream as mentioned above, requirements for the data stream clustering algorithms are becoming more and more complex. The basic requirements for clustering algorithms for static data are being able to extract arbitrary shape and numbers of clusters within the data. In addition, it is crucial for stream clustering algorithms to process incoming data fast and efficiently due to the time and space limitation. Although existing density-based stream clustering algorithms successfully find clusters of arbitrary shape and numbers within incoming stream, it has two user parameters density (ε) and minimum points per cluster(minPts) that has to be tuned carefully to obtain the desired clustering outcome. In this paper, we propose a stream clustering algorithm called StreamHD, which is based on a hierarchical density-based clustering algorithm that can detect clusters ii of arbitrary shapes within the data stream. The proposed algorithm independently detects density thresholds of the clusters without much user intervention. In addition, StreamHD requires only two user parameters, window size and minPts which determines the number of neighboring points of the given point to consider when calculating core density and also determines the minimum cluster size. It can be said that StreamHD has the least user intervention among the stream clustering algorithms. Furthermore, experiment results on real and synthetic datasets have shown that our proposed algorithm performs the best among the comparison algorithms in terms of window processing time and cluster quality.