I wish to know about the operation of minibatch KMeans through a very simple algorithm. The aim of this post is to know how should one update centers in minibatch KMeans. I intend to integrate minibatch in my self written KMeans code in C++ once I get the implementation clarified.
I am referring to this paper for minibatch KMeans. Following is a picture of the algorithm.
My KMeans algorithm already gives me cluster centroids and all points corresponding to a given centroid once I give it data.
I will try to explain my present understanding of minibatch KMeans clustering algorithm through a very simple example. Lets say that there are 15 data points in total. Following are the data points:
X = [[1.0, 10.0], [1.5, 15.0], [2.0, 20.0], [2.5, 25.0], [8.0, 80.0], [8.5, 85.0], [9.0, 95.0], [10.0, 100.0], [30.0, 60.0], [31.0, 62.0], [32.0, 64.0], [33.0, 66.0], [34.0, 68.0], [35.0, 70.0], [36.0, 72.0]]
This is how I have interpreted the algorithm:
Step 1. Choose number of number of centers n = 3; minibatch (M) size b = 10; iterations t = 3.
Step 2. Start iteration = 0.
Step 3. Randomly choose minibatch M = [[1.0, 10.0], [1.5, 15.0], [2.5, 25.0], [8.0, 80.0], [8.5, 85.0], [9.0, 95.0], [31.0, 62.0], [33.0, 66.0], [34.0, 68.0], [35.0, 70.0]]
Step 4. Randomly choose three centroids, c1, c2, c3 from M. Say c1 = [1.5, 15.0], c2=[8.5, 85.0], c3=[34.0, 68.0]. Lets say that the clusters corresponing to the three centroids are, cluster1 = [[1.0, 10.0], [1.5, 15.0], [2.5, 25.0]], cluster2 = [[8.0, 80.0], [8.5, 85.0], [9.0, 95.0]] and cluster3 = [[31.0, 62.0], [33.0, 66.0], [34.0, 68.0], [35.0, 70.0]].
Step 5. Get number of points (cardinality) in each cluster. The cardinalities of clusters corresponding to centroids, c1, c2, c3 are 3, 3, 4 respectively.
Step 6. Get learning rates as reciprocal of cardinalities. The learning rates corresponding to centroids, c1, c2, c3 are 1/3, 1/3, 1/4 respectively.
Step 7. Iterate over points in minibatch M to get new centroids, i.e.
c1_new = (1-1/3)*[1.5, 15.0] + (1/3) * ([1.0, 10.0] + [1.5, 15.0] + [2.5, 25.0]) = [ 2.66666667, 26.66666667]
c2_new = (1-1/3)*[8.5, 85.0] + (1/3) * ([8.0, 80.0] + [8.5, 85.0] + [9.0, 95.0]) = [ 14.16666667, 143.33333333]
c3_new = (1-1/4)*[34.0, 68.0] + (1/4) * ([31.0, 62.0] + [33.0, 66.0] + [34.0, 68.0] + [35.0, 70.0]) = [ 58.75, 117.5 ]
Step 8. Choose new minibatch M_new. Say, M_new = [[1.0, 10.0], [2.0, 20.0], [2.5, 25.0], [8.0, 80.0], [8.5, 85.0], [10.0, 100.0], [30.0, 60.0], [33.0, 66.0], [34.0, 68.0], [36.0, 72.0]].
Step 9. Find closest points from c1_new, c2_new, c3_new (from Step 7) to M_new. That is [ 2.5, 25. ], [ 10., 100.] and [ 36., 72. ] as new centers respectively.
Step 10. Repeat steps 2, 5, 6, 8, 9 till maximum iteration = 3 is reached.
I am majorly concerned if I am doing Step 7., that is update of centroids correctly. Something in Step 7 does not seem to be correct in my implementation. The new centroids in the given example in Step 7 seem to be very big and out of the center.
In the above mentioned paper (refer to the picture for algorithm), the per center counts are initialized and set to 0 in line index = 3 which is before the for loop for iterations. It seems that the per center counts, which are updated in line index = 11, will only but keep increasing with each iteration. That would not seem right. Also, in line indices = 11, 12, it seems that the per center counts and learning rate are being done for specific points and not for specific clusters. That would not seem right either. Or, perhaps, I am not understanding the algorithm correctly.
How should I update the centers and find the new centers? Can you please explain with reference to the small example data which I have given here? Thanks in advance.
