Solved – How to determine the best batch-size value for Mini Batch K-means algorithm

clusteringk-means

I am working on a project where I apply k-means on severals datasets. These datasets may include up to several billion points. I would like to use mini batch k-means to save time. However, the mini batch k-means requires a value for the batch size argument (I am using sklearn). What is the best way to choose a good batch size?

Best Answer

It is true that minibatch would be better to avoid the outlier. If you believe there is no outlier, then Kmeans should be better.

Related Solutions

K-means Clustering and PCA – Understanding Their Relationship

It is true that K-means clustering and PCA appear to have very different goals and at first sight do not seem to be related. However, as explained in the Ding & He 2004 paper K-means Clustering via Principal Component Analysis, there is a deep connection between them.

The intuition is that PCA seeks to represent all $n$ data vectors as linear combinations of a small number of eigenvectors, and does it to minimize the mean-squared reconstruction error. In contrast, K-means seeks to represent all $n$ data vectors via small number of cluster centroids, i.e. to represent them as linear combinations of a small number of cluster centroid vectors where linear combination weights must be all zero except for the single $1$. This is also done to minimize the mean-squared reconstruction error.

So K-means can be seen as a super-sparse PCA.

Ding & He paper makes this connection more precise.

Unfortunately, the Ding & He paper contains some sloppy formulations (at best) and can easily be misunderstood. E.g. it might seem that Ding & He claim to have proved that cluster centroids of K-means clustering solution lie in the $(K-1)$-dimensional PCA subspace:

Theorem 3.3. Cluster centroid subspace is spanned by the first $K-1$ principal directions [...].

For $K=2$ this would imply that projections on PC1 axis will necessarily be negative for one cluster and positive for another cluster, i.e. PC2 axis will separate clusters perfectly.

This is either a mistake or some sloppy writing; in any case, taken literally, this particular claim is false.

Let's start with looking at some toy examples in 2D for $K=2$. I generated some samples from the two normal distributions with the same covariance matrix but varying means. I then ran both K-means and PCA. The following figure shows the scatter plot of the data above, and the same data colored according to the K-means solution below. I also show the first principal direction as a black line and class centroids found by K-means with black crosses. PC2 axis is shown with the dashed black line. K-means was repeated $100$ times with random seeds to ensure convergence to the global optimum.

One can clearly see that even though the class centroids tend to be pretty close to the first PC direction, they do not fall on it exactly. Moreover, even though PC2 axis separates clusters perfectly in subplots 1 and 4, there is a couple of points on the wrong side of it in subplots 2 and 3.

So the agreement between K-means and PCA is quite good, but it is not exact.

So what did Ding & He prove? For simplicity, I will consider only $K=2$ case. Let the number of points assigned to each cluster be $n_1$ and $n_2$ and the total number of points $n=n_1+n_2$. Following Ding & He, let's define cluster indicator vector $\mathbf q\in\mathbb R^n$ as follows: $q_i = \sqrt{n_2/nn_1}$ if $i$-th points belongs to cluster 1 and $q_i = -\sqrt{n_1/nn_2}$ if it belongs to cluster 2. Cluster indicator vector has unit length $\|\mathbf q\| = 1$ and is "centered", i.e. its elements sum to zero $\sum q_i = 0$.

Ding & He show that K-means loss function $\sum_k \sum_i (\mathbf x_i^{(k)} - \boldsymbol \mu_k)^2$ (that K-means algorithm minimizes), where $x_i^{(k)}$ is the $i$-th element in cluster $k$, can be equivalently rewritten as $-\mathbf q^\top \mathbf G \mathbf q$, where $\mathbf G$ is the $n\times n$ Gram matrix of scalar products between all points: $\mathbf G = \mathbf X_c \mathbf X_c^\top$, where $\mathbf X$ is the $n\times 2$ data matrix and $\mathbf X_c$ is the centered data matrix.

(Note: I am using notation and terminology that slightly differs from their paper but that I find clearer).

So the K-means solution $\mathbf q$ is a centered unit vector maximizing $\mathbf q^\top \mathbf G \mathbf q$. It is easy to show that the first principal component (when normalized to have unit sum of squares) is the leading eigenvector of the Gram matrix, i.e. it is also a centered unit vector $\mathbf p$ maximizing $\mathbf p^\top \mathbf G \mathbf p$. The only difference is that $\mathbf q$ is additionally constrained to have only two different values whereas $\mathbf p$ does not have this constraint.

In other words, K-means and PCA maximize the same objective function, with the only difference being that K-means has additional "categorical" constraint.

It stands to reason that most of the times the K-means (constrained) and PCA (unconstrained) solutions will be pretty to close to each other, as we saw above in the simulation, but one should not expect them to be identical. Taking $\mathbf p$ and setting all its negative elements to be equal to $-\sqrt{n_1/nn_2}$ and all its positive elements to $\sqrt{n_2/nn_1}$ will generally not give exactly $\mathbf q$.

Ding & He seem to understand this well because they formulate their theorem as follows:

Theorem 2.2. For K-means clustering where $K= 2$, the continuous solution of the cluster indicator vector is the [first] principal component

Note that words "continuous solution". After proving this theorem they additionally comment that PCA can be used to initialize K-means iterations which makes total sense given that we expect $\mathbf q$ to be close to $\mathbf p$. But one still needs to perform the iterations, because they are not identical.

However, Ding & He then go on to develop a more general treatment for $K>2$ and end up formulating Theorem 3.3 as

Theorem 3.3. Cluster centroid subspace is spanned by the first $K-1$ principal directions [...].

I did not go through the math of Section 3, but I believe that this theorem in fact also refers to the "continuous solution" of K-means, i.e. its statement should read "cluster centroid space of the continuous solution of K-means is spanned [...]".

Ding & He, however, do not make this important qualification, and moreover write in their abstract that

Here we prove that principal components are the continuous solutions to the discrete cluster membership indicators for K-means clustering. Equivalently, we show that the subspace spanned by the cluster centroids are given by spectral expansion of the data covariance matrix truncated at $K-1$ terms.

The first sentence is absolutely correct, but the second one is not. It is not clear to me if this is a (very) sloppy writing or a genuine mistake. I have very politely emailed both authors asking for clarification. (Update two months later: I have never heard back from them.)

Matlab simulation code

figure('Position', [100 100 1200 600])

n = 50;
Sigma = [2 1.8; 1.8 2];

for i=1:4
    means = [0 0; i*2 0];
    
    rng(42)
    X = [bsxfun(@plus, means(1,:), randn(n,2) * chol(Sigma)); ...
         bsxfun(@plus, means(2,:), randn(n,2) * chol(Sigma))];
    X = bsxfun(@minus, X, mean(X));
    [U,S,V] = svd(X,0);
    [ind, centroids] = kmeans(X,2, 'Replicates', 100);
    
    subplot(2,4,i)
    scatter(X(:,1), X(:,2), [], [0 0 0])

    subplot(2,4,i+4)
    hold on
    scatter(X(ind==1,1), X(ind==1,2), [], [1 0 0])
    scatter(X(ind==2,1), X(ind==2,2), [], [0 0 1])
    plot([-1 1]*10*V(1,1), [-1 1]*10*V(2,1), 'k', 'LineWidth', 2)
    plot(centroids(1,1), centroids(1,2), 'w+', 'MarkerSize', 15, 'LineWidth', 4)
    plot(centroids(1,1), centroids(1,2), 'k+', 'MarkerSize', 10, 'LineWidth', 2)
    plot(centroids(2,1), centroids(2,2), 'w+', 'MarkerSize', 15, 'LineWidth', 4)
    plot(centroids(2,1), centroids(2,2), 'k+', 'MarkerSize', 10, 'LineWidth', 2)
    
    plot([-1 1]*5*V(1,2), [-1 1]*5*V(2,2), 'k--')
end

for i=1:8
    subplot(2,4,i)
    axis([-8 8 -8 8])
    axis square
    set(gca,'xtick',[],'ytick',[])
end

Solved – Why not terminating the k-means clustering algorithm after one iteration

What you are discussing sounds more like nearest neighbor classification to me, i.e. assign every point to the nearest "training" object. Essentially, you are describing classification, not clustering.

You appear to be doing only "half an iteration". A full iteration would also update the cluster centroids. The task of clustering is to discover structure in the data - in the case of k-means the structure are the centroids. In other algorithms it is usually the set of points that makes up the cluster.

Now to the "helipad" example. K-means does not minimize average distances. It minimizes the average squared distance. For a purely cost-driven approach that is worse, centroid-linkage is maybe better. For the helipad emergency it's better to have fewer extreme distance; but one may want to optimize the maximum instead. That is easier to formuate with hierarchial clustering, e.g. using minimax linkage. Furthermore, k-means may be placing the centers in the ocean, or in a lake... (this does not happen with minimax) if you had to connect all point with a point-to-point radio network, single-linkage is meaningful, because it is the minimum spanning tree. And Ward linkage optimizes squared deviations, just like k-means. This shows a key benefit of hierarchical clustering: it's flexibility. It allows both different objectives (linkages) and arbitrary distance functions (e.g. haversine distance). K-means does neither.

Best Answer

Related Solutions

K-means Clustering and PCA – Understanding Their Relationship

Matlab simulation code

Solved – Why not terminating the k-means clustering algorithm after one iteration

Related Question