Mini-batch K-Means++ Clustering Initialization

Fast algorithms for clustering large and ultra-large volumes of data are in demand in various fields, for example, vector databases. The k-means algorithm remains the most popular, however, it is extremely dependent on the initialization method. K-means++ is a well-established procedure for selecting initial cluster centers (centroids) for the k-means algorithm. In this work, we present a new algorithm capable of solving the k-means++ initialization problem for obtaining a good initial solution. The well-known k-means++ algorithm works well for data sets of N data vectors in a d-dimensional space when performing a single pass through the input data in O(k) iterations, and each iteration is characterized by complexity O(Ndk), where k is the number of centroids (clusters). So, the total execution time is \(O(Ndk^2)\) . Since k-means++ requires k passes through the data to initialize, it does not scale well to large data sets. We propose the Mini-batch K-means++ algorithm with a single pass through the data and a total expected execution time of \(O(dk(b+\log B))\) , where B is the number of batches of data, and b is the number of data vectors in one batch, \(N \le Bb\) . The higher comparative efficiency of the new Mini-batch K-means++ algorithm for big data is shown by the experiment. The minimum amount of memory resources for the algorithm to run is expected at \(B=n^{1/2}\) with a non-optimal execution time of \(O(dk(b+\log B))\) . In the optimal scenario for running a new algorithm, for \(2^w\) data vectors, the expected time expenditure is O(dkw). It is shown that the quality of solutions is not inferior to the classical k-means++.