LSROM: Learning Self-Refined Organizing Map for Fast Imbalanced Streaming Data Clustering (2024)

II-A Streaming Clustering

Data stream clustering involves categorizing data chunks into a finite set of clusters, which differs from static clustering and places higher demands on memory and time due to continuously varying chunks entering the stream. This necessitates fast incremental data processing to produce timely results. Modern data stream clustering algorithms strive to balance high accuracy with compressed time complexity.

Many of these algorithms are variations of traditional clustering methods like $k$-means (e.g., [16], [17], [13]), DBSCAN (e.g., [18], [19]), and hierarchical clustering [20]. While these adaptations enable efficient processing, they introduce specific hyper-parameters. To circumvent the non-trivial setting of hyper-parameters, Zhang et al. propose the Davies-Bouldin Index Evolving Clustering Method (DBIECM) [21] for streaming data clustering. However, this concept cannot be directly extended to the online setting since streaming algorithms do not retain data or maintain a partition of it, both of which are needed by batch cluster validity indices. Moshtaghi et al. develop two incremental versions of the Xie-Beni and Davies-Bouldin validity indices and employ them to monitor and control two streaming clustering algorithms, such as sk-means and online ellipsoidal clustering [22]. The above methods are limited to single-view, and a multiview support vector domain description (MVSVDD) model [23] is proposed to capture cluster evolution and discover arbitrarily shaped clusters with limited computing resources. In this context, these new incremental validity indices serve as performance monitoring functions. Nevertheless, handling non-stationary data distributions remains a challenge as most algorithms struggle to maintain accuracy and robustness.

II-B Imbalanced Clustering

Imbalanced clustering, where the number of samples varies in different clusters, has emerged from many real data mining applications [24]. Using prototypes is one of the effective approaches to tackle this issue (e.g., in [25], [26], [7]). Each cluster can be represented by multiple prototype points, reducing uniform effect [27] between subclusters. However, the above methods typically use a pre-defined number of prototypes. The issue with this strategy is that if the given number of prototypes is too small, the uniform effect may still occur between minority and majority clusters. Conversely, if the number of prototypes is too large, prototype points may also reside in overlapping regions between clusters, and noise and outliers could be treated as subclusters. Furthermore, if the number of prototypes is less than the number of clusters, the clustering result will never be correct. Hence, various methods have sought adaptive improvements in the pre-defined number of prototype points.

SMCL [8] achieves this by gradually adding seed points until a seed point is driven by a competitive punishment mechanism. The introduced competitive punishment mechanism effectively prevents the issue of dead units. In the case of using $k$-means as the clustering algorithm during learning, if no seed point is driven, a new seed point will be reintroduced. However, this approach lacks effectiveness in distinguishing small clusters from noise points. To address this, LDPI [12] designs an initial subcluster generation scheme, improving the clustering method of DPC by automatically identifying noise points and initial subcluster centers. According to the nearest-neighbor principle, the remaining points are classified as subcluster centers to generate subclusters. MCNS [28] introduces a measure based on the reconstruction rate to select the appropriate number of clusters, enhancing convergence speed while ensuring accuracy. All of these methods seek the optimal solution through iterations, resulting in time complexity exceeding quadratic levels.

II-C SOM-Based Clustering

Clustering algorithms based on SOM [29] have garnered significant attention and research in recent years. The two-dimensional mapping produced by SOM is a highly suitable method for representing the inherent relationships within data. It makes it easy to explore the intrinsic clustering structures. As a result, many improvements and extensions have been developed in this regard. Given that traditional SOM requires an initial number of neurons, leading to non-adaptive clustering precision, Raube et al. construct a hierarchical structure (GHSOM) [30] by recursively growing and splitting neurons, partitioning the data space into finer-grained regions, and gradually refining the clustering results. In order to go beyond the constraints of traditional numerical features, FMSOM [31] has devised a method that extends neural prototypes with category frequency tables to handle heterogeneous feature data without the need for binary transformation.

Olszewski et al. address data asymmetry by introducing additional asymmetric connection weights (ASOM) [32], which makes the topological structure more adaptable and reduces the topological distortion caused by random initialization. A. Ali Hameed et al. introduce a new intelligent adaptive learning SOM [33]. In this approach, they derive a new variable learning rate that adaptively achieves optimal weights, resulting in winning neurons with a shorter learning process time compared to traditional SOM. The authors aim to simultaneously achieve low quantization error in SOM and fast high convergence of the SOM algorithm, thereby overcoming the main drawbacks of classical SOM. Zhang et al. design a clustering method (SOFM) [34] where the learning rate and neighborhood function are adaptively adjusted based on data distribution and changes in the feature space. Later, a self-supervised self-organizing clustering network ($\text{S}^{3}$OCNet) [35] is proposed to jointly learn feature extraction and feature clustering to achieve a single-stage clustering method.

IV-A IP: Intensive Partition based on Trained Topology

In order to expedite the rapid construction of micro-clusters, we employ reclustering, which consists of two clustering steps. In the initial clustering step, we adopt an advanced SOM architecture named Randomized Self-Organizing Map (RSOM) [37].We assume that the mapping grid comprises $Q\times Q$ neurons, while the input imbalanced data chunk $\mathbf{X}^{i}\in\mathbb{R}^{n\times f}$ is used as the dataset. In this context, $\mathbf{x}_{j}^{i}\in R^{f}$ represents the $j$-th data object within $\mathbf{X}^{i}$. $\mathbf{z}_{q}\in R^{f}$ represents each neuron in the topology, to consider the random placement of neurons with a specific spectral distribution, a method employing rapid Poisson disk sampling for neurons of any dimension [38] is utilized. The Poisson disk sampling ensures that neurons are not placed too close to each other. Subsequently, through 10 iterations of the Lloyd relaxation scheme [39], the initial placements are further rearranged to achieve nearly centroidal Voronoi tessellation.Furthermore, neighbors of $\mathbf{z}_{q}$ at step $t$ can be defined as $\varOmega\left(\mathbf{z}_{q},t\right)$, representing a group of neurons close to $\mathbf{z}_{q}$ on the grid. Throughout the entire training process, the neighborhood variation follows a nearest-neighbor winner-takes-all rule (shrinking over time).

Since the data characteristics in the data chunk may be high-dimensional and diverse, the topological structure obtained through RSOM exhibits controlled randomness and discontinuities, enhancing readability in high-dimensional spaces. As neural network training tends to converge, it eventually yields trained neurons, represented as $Z=\left\{\mathbf{z}_{1},\mathbf{z}_{2},\ldots,\mathbf{z}_{Q^{2}}\right\}$. The SOM topological map, denoted as $G_{\text{SOM}}=\left\{Z,\mathbf{A}\right\}$, constitutes an undirected weighted graph. The adjacency matrix of connections between neurons, $\mathbf{A}=\left[a_{ij}\right]\in\mathbb{R}^{Q^{2}\times Q^{2}}$, the formation formula is as follows:

When $a_{ij}=1$, there exists a connecting edge between $\mathbf{z}_{i}$ and $\mathbf{z}_{j}$. In contrast, when $a_{ij}=0$, there is no connecting edge between $\mathbf{z}_{i}$ and $\mathbf{z}_{j}$.

Repeating the above steps for a finite number of iterations will inevitably converge to a minimum solution of $P$ [41]. Since the neurons after fine-tuning are already reasonably representative of the data objects, we define them as micro-cluster centers $M=\{\mathbf{m}_{1},\mathbf{m}_{2},\ldots,\mathbf{m}_{Q^{2}}\}$. Thus, the reclustering process composed of RSOM and $k$-means is completed.

IV-B RP: Refining Partition by Bridge Nodes

After obtaining micro-cluster centers, an excessive quantity of them may result in the dispersion of micro-clusters within the overlapping regions among the true clusters.

Because BN acts like a bridge connecting the two micro-clusters that should be separated during the merge phase, which results in degraded performance. Specifically, the distribution of micro-cluster centers reflects the data objects, making these centers the primary reference for the merging process. If we do not eliminate BNs, there is a risk of merging two true clusters into one, resulting in a deviation from the expected final number of clusters.

The generated topology map of Section IV-A, as shown in Fig. 3(a), exhibits high-density data objects that are also mapped in places with high local density of micro-cluster centers. BNs exist in the blank area between every two true clusters because the SOM-based construction of the topology map forms a neural network-like structure, and during the learning and updating process, neurons need to be driven based on data objects, and their driving ability is limited in low-density data areas, causing them to be trapped.

IV-C MMC: Merging Micro-Clusters based on Refined Topology

In this stage, micro-clusters will be merged to automatically obtain the final clustering result. Our merge process utilizes two metrics, namely compactness and separability. We will use separation to find the most suitable micro-clusters for merging, because the smaller the separation, the more similar the two micro-clusters are and are more likely to come from the same true cluster. The separation is calculated by using a 1-D Gaussian mixture probability density function.

In order to estimate the minimum discrete probability of $u$ within $S(u)$, we will use a step size of 0.01 to traverse the interval from -0.5 to 0.5, denoted as $U=\{-0.5,-0.49,\ldots,0.5\}$. When the separation between two micro-clusters is large, $\min_{u\in U}S(u)$ approaches 0, and $s_{ij}$ becomes large. Suppose the current unmerged clustering result state is $\varPhi(k)$, which indicates that the current data chunk is split by $k$ micro-clusters. The following equation calculates the micro-clusters that should be merged and the global compactness of the clustering result for $\varPhi(k)$:

Iterate through all possible values of $K$ to find the optimal combination state for $com$ and $sep$. To normalize the global compactness and global separability, we divide their maximum values into equal ranges. Finally, we select the minimum value from the sum of global separability and global compactness to guide the selection of the clustering result.

IV-D Overall Algorithm and Complexity Analysis

The summary of LSROM is presented in Algorithm 1. In the initial stage, we utilize RSOM and apply reclustering with $k$-means to generate micro-cluster centers distributed across the imbalanced dataset. We employ the topological map to guide the subsequent processes. In the second stage, we compute the local topological radius ratio for each micro-cluster center and use this ratio to remove BNs. In the third stage, the updated micro-clusters are adaptively merged using two metrics: separability and compactness. We quickly determine the final, suitable number of clusters using the topological map.

V-A Experimental Settings

Ten datasets including four synthetic and six real datasets with varying sizes, dimensions, and distribution types. Their statistical details are provided in TableI. For the synthetic datasets, banana and Lithuanian are generated using PRTools[43]with thickness parameter set at $0.4$ and choose ”non-spherical clusters”. ids2 and gaussian [7] are synthesized by applying a mixture of bivariate Gaussian density functions with custom scales in the order of one million, resulting in spherical clustering. All real datasets are found in the UCI Machine Learning Repository¹¹1https://archive.ics.uci.edu. Min-max normalization is adopted to pre-process each feature to be with the identical value domain $[0,1]$.

We have designed a data generation method to validate the ISDC problem, which can comprehensively generate imbalanced data chunks. A selected dataset serves as the basis for generating data chunks using a Two-Layer Random Sampling method (TLRS), where the two layers involve random sampling for the number of clusters and the Imbalanced Ratio. The specific algorithmic procedure is described in Algorithm2. By repeating this algorithm $t$ times, we obtain a total of $t$ data chunks. Generating data chunks in this manner ensures the rationality of data distribution while attempting to include the imbalanced states of all streaming data as comprehensively as possible. This approach enhances the diversity of experimental data, allowing a better evaluation of algorithm performance under various imbalanced scenarios.

We compare LSROM with seven other methods: the traditional partitional clustering approach ($k$-means [4]), advanced algorithms designed for streaming data (StreamKM++ [13], BIRCH [16], AMD-DPC [15]), and state-of-the-art methods suitable for static imbalanced data (SMCL [8], MC-MNN [44], LDPI [12]).For $k$-means, StreamKM++, BIRCH, and AMD-DPC, the number of clusters needs to be specified in advance. In contrast, SMCL, MC-MNN, LDPI, and our method can adaptively determine the number of clusters without prior specification. The specific experimental parameters of our method are set as follows: the initial number of neurons $Q^{2}=100$, and the number of nearest neighbors $\kappa=10$. In the following Section V-E, we conduct a comprehensive parameter sensitivity verification. Since $\kappa$ and $Q$ are not too sensitive, the rationality of our settings is confirmed. The other parameters for all the compared methods are set following the recommendations in the source literature.

Two metrics, i.e., Normalized Mutual Information (NMI) [45] and Difference of CV (DCV) [8] index are utilized for performance evaluation. NMI is an external metric reflecting the correlation between the clustering results and the given labels from the perspective of information theory. Its value range is $[0,1]$, and the larger the better. DCV is an internal metric that is specifically designed for evaluating the clustering performance of imbalanced data. It calculates the effectiveness of clustering based on the similarity between clusters and the compactness within clusters. A lower index value indicates better clustering results, with greater differences between clusters and higher compactness within clusters. All the reported NMI and DCV performances are averaged over 10 runs with random initialization of seeds.

V-B Efficiency Evaluation

The impact of data size on the runtime of clustering methods is studied by plotting their runtime-data size curves on the six large-scale datasets in Fig. 4. Each point in the figure reflects the execution time (y-axis) of a method under the amount of data (x-axis). We categorize the compared methods into three groups, i.e., 1) the proposed LSROM (in purple), 2) SMCL (in orange), MC-MNN (in green), LDPI (in blue), and 3) existing fast streaming data clustering methods that do not dedicate to consider the imbalanced issue (in gray). Please note that we visualize the y-axis on a logarithmic scale because the running times of different methods vary widely.

It can be seen that the proposed LSROM has a similar running time as that of the $k$-means, StreamKM++, BIRCH, and AMD-DPC thanks to their linear or$O(n\log n)$ level complexity, while the group of SMCL, MC-MNN, and LDPI is with heavy computational cost due to their polynomial time complexity. Moreover, due to the excessive computational resource requirements, these algorithms encounter ”out of memory” situations when dealing with larger datasets.

V-C Clustering Accuracy Evaluation

Two sub-experiments have been conducted. We first compare the clustering performance of different clustering methods on each whole dataset in Table II to evaluate the clustering accuracy of methods on static datasets, where the best- and second-best-performing method on each dataset is highlighted in boldface and underlined, respectively. Then we generate imbalanced streaming data chunks based on the six large-scale datasets to specifically evaluate the capability of methods in ISDC as shown in Fig. 5 and Fig. 6. For each of the six large-scale datasets, we generate 50 chunks by using TLRS and let them flow in one by one per the time-stamp. The data volume of each chunk is determined based on the maximum data capacity that can be processed by SMCL. Since SMCL takes the longest time to run among all methods as shown in Fig.4, we hope that all methods can run and get accurate results. Specifically, it is determined as follows: $chunk_{ids2}=chunk_{gaussian}=8\times 10^{4}$, $chunk_{Forest}=chunk_{Bitcoin}=chunk_{SEER}=5\times 10^{4}$ and $chunk_{IOT}=4\times 10^{4}$.

From TableII, it can be seen that the proposed LSROM performs best in general, winning in 16 out of 20 comparisons. In comparison with the fast clustering methods, i.e., $k$-means, StreamKM++, BIRCH, and AMD-DPC, LSROM demonstrates its superiority as it is competent in detecting imbalanced clusters, while the four fast methods do not adopt a mechanism to specially take the imbalanced issue into account. AMD-DPC performs the second-best in general as it adopts a density-based principle, which can somewhat distinguish imbalanced clusters as discussed in SectionI. In comparison with SMCL, MC-MNN, and LDPI that are proposed for imbalanced data, LSROM still performs the best in general, as SMCL, MC-MNN, and LDPI are unavailable due to the ”out of memory” on the six large-scale datasets, while LSROM remains competitive on the four smaller datasets. The reason would be that LSROM inherits most merits of SMCL and further appropriately considers the global distribution information in doing the intensive data partition with the help of the trained SOM-topology and the partition refinement (i.e. SectionIV).

It can be observed from Fig. 5 and Fig. 6 that in ISDC tasks, LSROM still significantly outperforms the other four fast clustering methods, i.e., $k$-means, StreamKM++, BIRCH, and AMD-DPC, which conforms with the observations of TableII. Since SMCL, MC-MNN, and LDPI are executable on each chunk generated from the large-scale datasets, their ISDC performance is reported, showing that LSROM is still very competitive in comparison with them. In summary, the proposed LSROM is superior in both accuracy and scalability in handling imbalanced streaming data with different scales.

V-D Ablation Study

To further validate the effectiveness of LSROM, we conduct ablation experiments. Since LSROM consists of three components, we perform ablations on each module individually to obtain their NMI, DCV scores, and Runtime. For the IP ablation, we directly obtain neurons by training RSOM without the $k$-means fine-tuning step. For the RP ablation, we omit the step of removing BNs, thus directly merging the micro-clusters obtained by the IP. For the MMC ablation, we use the merge method named SGMS of SMCL, instead of MMC. The specific precision results are shown in TableIII.We find that for the standard LSROM workflow, ablation of any module leads to a certain decrease in clustering performance, demonstrating that each module contributes to achieving good clustering performance. Among these ablations, the IP ablation has the smallest impact, while the ablations of RP and MMC result in more significant differences in precision. When processing large-scale data, SGMS requires quadratic running time, so it causes ”out of memory”. In this study, the LSROM algorithm consistently produces the best clustering results among all ablation settings, further confirming its effectiveness.

V-E Parameter Sensitivity Evaluation

In the proposed LSROM framework, there are two parameters, namely the number of neurons $Q^{2}$ and the neighbor count $\kappa$. Different values of these parameters can potentially affect the clustering performance in various ways. Here is an explanation of these parameters.

For the parameter $Q^{2}$, it directly determines the initial number of neurons. A value of $Q^{2}$ that is too large can lead to an excessive number of micro-clusters, resulting in significant overlap between final clusters. During the merging process, micro-clusters representing low-density data may be incorrectly identified as belonging to the same true cluster. Additionally, an excessive number of micro-clusters can result in high computational costs. On the other hand, a too small value of $Q^{2}$ can lead to significant differences in the data sizes contained within micro-clusters, which can still be influenced by the uniform effect, directly affecting the quality of the LSROM framework.Regarding the parameter $\kappa$, which is used in the approximate $\kappa$-neighbor algorithm in MMC, it calculates the global separability values for specific clusters. When $\kappa$ is too big, it can lead to increased computational overhead. Conversely, when $\kappa$ is too small, it can result in global separability values being meaningless.

We conduct experiments on ten datasets by varying the values of $Q$ and $\kappa$, recording the obtained NMI and DCV scores, as shown in Fig. 7. $Q$ values are traversed from 3 to 12 with a step size of 1, while $\kappa$ values range from 3 to 21 with a step size of 2. Based on the results shown in Fig. 7, it can be concluded that the clustering quality, as measured by NMI and DCV, remains robust for different parameter value combinations. Particularly, $Q$ performs well and is stable between 8 and 12, and $\kappa$ performs well and is stable between 7 and 15. Different $Q$ values produce larger accuracy changes than $\kappa$. In general, the LSROM framework demonstrates low sensitivity to parameter changes.