1 Introduction↩︎

Clustering remains a core task in unsupervised learning, with applications spanning pattern discovery, compression, anomaly detection, and post-processing [1]–[6]. Among modern clustering approaches, centroid neural network (CentNN) [3] is a prototype-based algorithm that follows a competitive-learning paradigm, where centroid vectors are updated online through winner-loser dynamics. This design is well suited to incremental data processing, memory-constrained environments, and adaptive model growth, placing CentNN within the broader family of competitive and self-organizing neural models [7], [8]. Unlike batch clustering methods, CentNN updates centroids one sample at a time and expands model capacity through centroid splitting.

Despite these advantages, standard CentNN suffers from a practical inefficiency: before each split event, it may spend many epochs in a low-activity regime where centroid movement is minimal, yet splitting is delayed until strict local stabilization, as illustrated in Fig. 1. These “flat” phases increase runtime without corresponding structural progress. To address this limitation, this report proposes FastCentNN, a more efficient variant that treats global centroid movement per epoch as an entropy proxy for clustering uncertainty and initiates splitting once movement remains below a threshold for a patience window. FastCentNN converts split timing from a strict convergence event into an adaptive early-trigger decision while preserving the original winner-loser learning dynamics. It supports both absolute and stage-relative thresholds, enabling consistent behavior across datasets and training stages. Although the asymptotic computational complexity remains unchanged, FastCentNN improves practical efficiency by reducing unnecessary low-information epochs between split operations.

2 FastCentNN↩︎

2.1 Problem Setup↩︎

Let \(\mathcal{X}=\{x_i\}_{i=1}^n\), with \(x_i\in\mathbb{R}^d\), and let \(K\) be the target number of clusters. CentNN represents clusters by centroids \(\{w_j\}_{j=1}^{k_t}\) at epoch \(t\), where \(k_t\) grows over time via split operations. For each sample \(x\), the winner index is defined as: \[j^\star(x)=\arg\min_{j\in\{1,\dots,k_t\}} \|x-w_j\|_2.\] Each sample also stores its previous assignment \(a_i^{(t-1)}\) from the previous epoch.

2.2 Winner-Loser Updates↩︎

If sample \(x_i\) changes assignment at epoch \(t\) from previous cluster \(p=a_i^{(t-1)}\) to current winner \(c=j^\star(x_i)\), the centroids are updated by: \[\begin{align} w_c &\leftarrow w_c + \frac{1}{N_c+1}(x_i-w_c), \\ w_p &\leftarrow w_p - \frac{1}{N_p-1}(x_i-w_p), \end{align}\] where \(N_c,N_p\) are current member counts before reassignment. The loser update is applied only when \(N_p>1\) to avoid division by zero and unstable singleton collapse.

2.3 Split Operation↩︎

CentNN starts from two centroids near the global mean: \[w_1=\bar{x}+\epsilon,\quad w_2=\bar{x}-\epsilon,\quad \bar{x}=\frac{1}{n}\sum_{i=1}^n x_i,\] where \(\epsilon\) is a small perturbation. The centroids are updated iteratively until local stabilization is reached. If \(k_t<K\), the split candidate is selected based on the maximum within-cluster error: \[s=\arg\max_j E_j,\quad E_j=\sum_{x_i:a_i=j}\|x_i-w_j\|_2.\] Then a symmetric split is applied: \[w_s^- = w_s-\delta_s,\qquad w_s^+ = w_s+\delta_s,\] where \(\delta_s\) is a small perturbation (magnitude controlled by \(\epsilon\)), typically aligned with the largest-variance feature within cluster \(s\).

2.4 Early Split in FastCentNN↩︎

Standard CentNN often spends many epochs in a low-activity regime with minimal centroid movement before satisfying the splitting criterion. FastCentNN addresses this inefficiency by replacing strict stabilization with an early splitting criterion based on the total centroid movement: \[M_t=\sum_{j=1}^{k_t}\|w_j^{(t)}-w_j^{(t-1)}\|_2,\] where \(M_t\) is the global centroid movement (entropy proxy) at epoch \(t\). A split is triggered when \(M_t\) remains below a threshold for a predefined patience window: \[M_t \le \tau_t \text{ for } P \text{ consecutive epochs},\] where \(\tau_t\) is the movement threshold and \(P\) is the patience parameter. The threshold can be configured in two modes. In the absolute mode, \(\tau_t=\tau\), whereas in the stage-relative mode, \(\tau_t=\tau B_r\), where \(B_r\) is the baseline movement measured immediately after the latest split stage \(r\). Following each split, the stage state is reset as: \[B_{r+1}\leftarrow \max(M_t,\varepsilon_0),\qquad \text{streak}\leftarrow 0,\] where \(\varepsilon_0>0\) is a small constant for numerical stability. The full FastCentNN procedure is summarized in Algorithm 2.

3 Experiments↩︎

3.1 Experimental Setup↩︎

FastCentNN is evaluated against the original CentNN under identical parameter settings on two clustering tasks: (i) synthetic 2D datasets and (ii) high-dimensional datasets. Since the primary objective is to improve computational efficiency while preserving clustering quality, the relative difference in mean squared error (MSE) is reported as: \[\Delta\mathrm{MSE}(\%) = \frac{\mathrm{MSE}_{\text{FastCentNN}} - \mathrm{MSE}_{\text{CentNN}}}{\mathrm{MSE}_{\text{CentNN}}} \times 100. \label{eq:delta95mse}\tag{1}\] In addition, efficiency is assessed using the total runtime and the number of training epochs required for convergence.

3.2 Test on Synthetic 2D Data↩︎

FastCentNN was evaluated against the original CentNN on six widely used synthetic clustering benchmark datasets: A1, A2, S1, S2, R15, and Aggregation [9]. Each dataset consists of 2D data points with a predefined number of clusters. Table 1 summarizes the results. Compared with the original CentNN, FastCentNN consistently reduces both runtime and the number of training epochs while producing nearly identical clustering quality. Across all six datasets, FastCentNN achieves an average runtime reduction of approximately \(9.6\%\), with the largest speed-up of \(16.72\%\) on A1 and the smallest of \(4.18\%\) on R15. The \(\Delta\mathrm{MSE}\) measures are negligible for all datasets, remaining close to zero even on the most challenging cases. These results indicate that the proposed early splitting strategy effectively eliminates unnecessary low-movement epochs, improving computational efficiency without degrading clustering performance. Visual results are shown in Fig. 3.

3.3 Test on High-dimensional Data↩︎

FastCentNN was also evaluated on two high-dimensional image datasets, MNIST and Fashion-MNIST, each configured with 10 target clusters. Table 2 summarizes the results. FastCentNN consistently reduces both runtime and the number of training epochs while preserving clustering quality. On MNIST, the runtime is improved from 8.344 s to 7.924 s, corresponding to a speed-up of 5.03%, while the number of training epochs is decreased from 141 to 132. Similarly, on Fashion-MNIST, FastCentNN reduces the runtime from 8.220 s to 7.775 s (5.41% speed-up) and the number of training epochs from 127 to 119.

The \(\Delta\mathrm{MSE}\) values are negligible on both datasets, remaining within \(10^{-5}\%\) compared to the original CentNN. These results demonstrate that the proposed early splitting strategy remains effective on high-dimensional datasets, reducing computational cost while maintaining overall clustering accuracy.

4 Conclusion↩︎

This report proposes FastCentNN, an accelerated variant of CentNN that introduces an early splitting strategy based on total centroid movement. By triggering centroid splits before strict local stabilization, FastCentNN reduces unnecessary low-movement epochs while preserving the original winner-loser learning dynamics. Experimental results on synthetic 2D datasets, MNIST, and Fashion-MNIST demonstrate consistent reductions in runtime and training epochs with negligible differences in clustering quality.

Acknowledgment↩︎

The author would like to thank Prof. Dong-Chul Park, the inventor of the original CentNN algorithm, whose insights inspired the development of this approach.

References↩︎