Unsupervised Learning on Stream Data: Clusterability Analysis in a Joint Perspective Under Incremental and Parallel Constraints

Unsupervised learning is one of the fundamental machine learning methods. Clustering is a vital unsupervised learning task and can significantly contribute to the detection of hidden structures in unknown datasets. Clusterability is an important concept due to the fact that it can theoretically portray the extent to which a clustering algorithm can recover a benchmark clustering, with the absence of excessive experimental validations. Moreover, conventional batch-mode-clustering-oriented clusterability analysis should be extended to the incremental setting when the clustering algorithm is required to handle stream data. However, such clusterability analysis is facing two barriers. First, the incremental clustering algorithm proceeds in a step-wise manner and can merely access the newly arrived data of the current step. This extremely fragmentary view of the entire input data stream inevitably results in a biased perception of the underlying benchmark clustering. Second, incremental clustering is conventionally applied to real-time or massive-data scenarios. Such application scenarios typically require the computational power of mainstream SIMD (Single Instruction Multiple Data) hardware accelerators. However, strong data dependency inherently exists between two successive steps of an incremental clustering algorithm, which dramatically impairs data parallelism. In view of these constraints, we propose our roadmap to theoretically analyze and ensure the clusterability under an incremental setting in terms of a general clusterability metric: niceness (higher intra-cluster similarity than inter-cluster similarity). In our work, a nice-k clustering (a clustering that has k clusters and satisfies the niceness metric) is supposed to exist in the input data stream. Meanwhile, the input data stream is supposed to be divided into a series of micro-clusters, and the micro-clusters are incrementally clustered into clusters. In addition, we rely on an assumption (homogeneity assumption) that every micro-cluster merely contains homogenous data. First, we point out that a vital reason for the induction of heterogeneous clusters is the lack of representative micro-clusters. We propose Theorem 1 to iteratively identify a set of 2[Formula: see text] representative micro-clusters that can cover all k benchmark clusters. Therefore, we can trade the number of clusters for homogeneity and thus assure clusterability. Second, we demonstrate that evolution in the granularity of a micro-cluster can prompt SIMD-parallelism more than in the granularity of a single data point. Consequently, the clusterability-assured method of Theorem 1 is furthermore parallel-friendly. In all, we depict a roadmap to assure clusterability under both incremental and SIMD-friendly constraints.