58
$\begingroup$

It is a common practice to apply PCA (principal component analysis) before a clustering algorithm (such as k-means). It is believed that it improves the clustering results in practice (noise reduction).

However I am interested in a comparative and in-depth study of the relationship between PCA and k-means. For example, Chris Ding and Xiaofeng He, 2004, K-means Clustering via Principal Component Analysis showed that "principal components are the continuous solutions to the discrete cluster membership indicators for K-means clustering". However, I have hard time understanding this paper, and Wikipedia actually claims that it is wrong.

Also, the results of the two methods are somewhat different in the sense that PCA helps to reduce the number of "features" while preserving the variance, whereas clustering reduces the number of "data-points" by summarizing several points by their expectations/means (in the case of k-means). So if the dataset consists in $N$ points with $T$ features each, PCA aims at compressing the $T$ features whereas clustering aims at compressing the $N$ data-points.

I am looking for a layman explanation of the relations between these two techniques + some more technical papers relating the two techniques.

$\endgroup$
  • 2
    $\begingroup$ Clustering can also be considered as feature reduction. Where you express each sample by its cluster assignment, or sparse encode them (therefore reduce $T$ to $k$). Both of these approaches keep the number of data points constant, while reducing the "feature" dimensions. $\endgroup$ – jeff Nov 24 '15 at 1:38
72
+50
$\begingroup$

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.

What Ding & He paper does, it to make 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.

PCA vs K-means

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 - \boldsymbol \mu_k)^2$ (that K-means algorithm minimizes) 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^\top \mathbf X_c$, 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    
$\endgroup$
  • 2
    $\begingroup$ I've just glanced inside the Ding & He paper. In theorem 2.2 they state that if you do k-means (with k=2) of some p-dimensional data cloud and also perform PCA (based on covariances) of the data, then all points belonging to cluster A will be negative and all points belonging to cluster B will be positive, on PC1 scores. Interesting statement, - it should be tested in simulations. The problem, however is that it assumes globally optimal K-means solution, I think; but how do we know if the achieved clustering was optimal? $\endgroup$ – ttnphns Dec 16 '15 at 20:20
  • 1
    $\begingroup$ @ttnphns, I have updated my simulation and figure to test this claim more explicitly. If projections on PC1 should be positive and negative for classes A and B, it means that PC2 axis should serve as a boundary between them. This is very close to being the case in my 4 toy simulations, but in examples 2 and 3 there is a couple of points on the wrong side of PC2. Regarding convergence, I ran kmeans function with 100 replications: it chooses a different random initialization each time and then selects the best solution, so it should hopefully ensure that the global optimum is achieved. $\endgroup$ – amoeba Dec 16 '15 at 21:22
  • 1
    $\begingroup$ @ttnphns: I think I figured out what is going on, please see my update. $\endgroup$ – amoeba Dec 17 '15 at 15:11
  • $\begingroup$ amoeba, thank you for digesting the being discussed article to us all and for delivering your conclusions (+2); and for letting me personally know! I'll come back hopefully in a couple of days to read and investigate your answer. But appreciating it already now. $\endgroup$ – ttnphns Dec 17 '15 at 18:49
  • $\begingroup$ Outstanding post. Is there a reason why you used Matlab and not R? Just curious because I am taking the ML Coursera course and Andrew Ng also uses Matlab, as opposed to R or Python. Is it a general ML choice? $\endgroup$ – Antoni Parellada Jun 16 '16 at 20:21
10
$\begingroup$

PCA and K-means do different things.

PCA is used for dimensionality reduction / feature selection / representation learning e.g. when the feature space contains too many irrelevant or redundant features. The aim is to find the intrinsic dimensionality of the data.

Here's a two dimensional example that can be generalized to higher dimensional spaces. The dataset has two features, $x$ and $y$, every circle is a data point.

enter image description here

In the image $v1$ has a larger magnitude than $v2$. These are the Eigenvectors. The dimension of the data is reduced from two dimensions to one dimension (not much choice in this case) and this is done by projecting on the direction of the $v2$ vector (after a rotation where $v2$ becomes parallel or perpendicular to one of the axes). This is because $v2$ is orthogonal to the direction of largest variance. One way to think of it, is minimal loss of information. (There is still a loss since one coordinate axis is lost).

K-means is a clustering algorithm that returns the natural grouping of data points, based on their similarity. It's a special case of Gaussian Mixture Models.

In the image below the dataset has three dimensions. It can be seen from the 3D plot on the left that the $X$ dimension can be 'dropped' without losing much information. PCA is used to project the data onto two dimensions. In the figure to the left, the projection plane is also shown. Then, K-means can be used on the projected data to label the different groups, in the figure on the right, coded with different colors.

enter image description here

PCA or other dimensionality reduction techniques are used before both unsupervised or supervised methods in machine learning. In addition to the reasons outlined by you and the ones I mentioned above, it is also used for visualization purposes (projection to 2D or 3D from higher dimensions).

As to the article, I don't believe there is any connection, PCA has no information regarding the natural grouping of data and operates on the entire data, not subsets (groups). If some groups might be explained by one eigenvector ( just because that particular cluster is spread along that direction ) is just a coincidence and shouldn't be taken as a general rule.

"PCA aims at compressing the T features whereas clustering aims at compressing the N data-points."

Indeed, compression is an intuitive way to think about PCA. However, in K-means, to describe each point relative to it's cluster you still need at least the same amount of information (e.g. dimensions) $x_i = d( \mu_i, \delta_i) $, where $d$ is the distance and $\delta_i$ is stored instead of $x_i$. And you also need to store the $\mu_i$ to know what the delta is relative to. You can of course store $d$ and $i$ however you will be unable to retrieve the actual information in the data.

Clustering adds information really. I think of it as splitting the data into natural groups (that don't have to necessarily be disjoint) without knowing what the label for each group means (well, until you look at the data within the groups).

$\endgroup$
  • 3
    $\begingroup$ The way your PCs are labeled in the plot seems inconsistent w/ the corresponding discussion in the text. Note that, although PCA is typically applied to columns, & k-means to rows, both could be applied to either. I haven't read the paper, but I bet that's what they're talking about. $\endgroup$ – gung Dec 15 '15 at 2:56
  • $\begingroup$ Sorry, I meant the top figure: viz., the v1 & v2 labels for the PCs. $\endgroup$ – gung Dec 15 '15 at 3:08
  • $\begingroup$ Good point, it might be useful (can't figure out what for) to compress groups of data points. Find groups using k-means, compress records into fewer using pca. As to the grouping of features, that might be actually useful. $\endgroup$ – shuriken x blue Dec 15 '15 at 3:09
  • 2
    $\begingroup$ So are you essentially saying that the paper is wrong? It explicitly states (see 3rd and 4th sentences in the abstract) and claims to have proven mathematically that there is a specific connection, whereas you say that there is no connection. $\endgroup$ – amoeba Dec 15 '15 at 15:26
  • $\begingroup$ What I got from it: PCA improves K-means clustering solutions. The connection is that the cluster structure are embedded in the first K − 1 principal components. This is is the contribution. $\endgroup$ – shuriken x blue Dec 16 '15 at 3:24
7
$\begingroup$

It is common to whiten data before using k-means. The reason is that k-means is extremely sensitive to scale, and when you have mixed attributes there is no "true" scale anymore. Then you have to normalize, standardize, or whiten your data. None is perfect, but whitening will remove global correlation which can sometimes give better results. PCA/whitening is $O(n\cdot d^2 + d^3)$ since you operate on the covariance matrix.

To my understanding, the relationship of k-means to PCA is not on the original data. It is to using PCA on the distance matrix (which has $n^2$ entries, and doing full PCA thus is $O(n^2\cdot d+n^3)$ - i.e. prohibitively expensive, in particular compared to k-means which is $O(k\cdot n \cdot i\cdot d)$ where $n$ is the only large term), and maybe only for $k=2$. K-means is a least-squares optimization problem, so is PCA. k-means tries to find the least-squares partition of the data. PCA finds the least-squares cluster membership vector.

The first Eigenvector has the largest variance, therefore splitting on this vector (which resembles cluster membership, not input data coordinates!) means maximizing between cluster variance. By maximizing between cluster variance, you minimize within-cluster variance, too.

But for real problems, this is useless. It is only of theoretical interest.

$\endgroup$
  • 2
    $\begingroup$ It would be great to see some more specific explanation/overview of the Ding & He paper (that OP linked to). I am not familiar with it myself (yet), but have seen it mentioned enough times to be quite curious. $\endgroup$ – amoeba Nov 25 '15 at 23:28
  • 3
    $\begingroup$ You mean this? Yes, I have come across it too; I think it only adds to my confusion. I was hoping that this will be the thread that could clarify it for me... Now that I think about it, perhaps I should put a bounty on it. I don't think I will have time in the next days to study this topic myself. $\endgroup$ – amoeba Nov 25 '15 at 23:45
  • 3
    $\begingroup$ This wiki paragraph is very weird. It says that Ding & He (2001/2004) was both wrong and not a new result! To demonstrate that it was not new it cites a 2004 paper (?!). To demonstrate that it was wrong it cites a newer 2014 paper that does not even cite Ding & He. Fishy. $\endgroup$ – amoeba Nov 26 '15 at 0:07
  • 3
    $\begingroup$ Maybe citation spam again. Wikipedia is full of self-promotion. $\endgroup$ – Anony-Mousse Nov 26 '15 at 0:19
  • 1
    $\begingroup$ I think I figured out what is going in Ding & He, please see my answer. Apart from that, your argument about algorithmic complexity is not entirely correct, because you compare full eigenvector decomposition of $n\times n$ matrix with extracting only $k$ K-means "components". That's not a fair comparison. If you use some iterative algorithm for PCA and only extract $k$ components, then I would expect it to work as fast as K-means. So I am not sure it's correct to say that it's useless for real problems and only of theoretical interest. $\endgroup$ – amoeba Dec 17 '15 at 15:17
4
$\begingroup$

Solving the k-means on its O(k/epsilon) low-rank approximation (i.e., projecting on the span of the first largest singular vectors as in PCA) would yield a (1+epsilon) approximation in term of multiplicative error.

Particularly, Projecting on the k-largest vector would yield 2-approximation.

In fact, the sum of squared distances for ANY set of k centers can be approximated by this projection. Then we can compute coreset on the reduced data to reduce the input to poly(k/eps) points that approximates this sum.

See: Dan Feldman, Melanie Schmidt, Christian Sohler: Turning big data into tiny data: Constant-size coresets for k-means, PCA and projective clustering. SODA 2013: 1434-1453

$\endgroup$
3
$\begingroup$

Intuitive relationship of PCA and KMeans

  1. Theoretically PCA dimensional analysis (the first K dimension retaining say the 90% of variance...does not need to have direct relationship with K Means cluster), however the value of using PCA came from a) practical consideration given the nature of objects that we analyse tends to naturally cluster around/evolve from ( a certain segment of) their principal components (age, gender..) b) PCA eliminates those low variance dimension (noise), so itself adds value (and form a sense similar to clustering) by focusing on those key dimension In simple terms, it is just like X-Y axis is what help us master any abstract mathematical concept but in a more advance manner.

  2. K Means try to minimize overall distance within a cluster for a given K

  3. For a set of objects with N dimension parameters, by default similar objects Will have MOST parameters “similar” except a few key difference (eg a group of young IT students, young dancers, humans… will have some highly similar features (low variance) but a few key features still quite diverse and capturing those "key Principal Componenents" essentially capture the majority of variance, eg. color, area of residence.... Hence low distortion if we neglect those features of minor differences, or the conversion to lower PCs will not loss much information
  4. It is thus “very likely” and “very natural” that grouping them together to look at the differences (variations) make sense for data evaluation (eg. if you make 1,000 surveys in a week in the main street, clustering them based on ethnic, age, or educational background as PC make sense) Under K Means’ mission, we try to establish a fair number of K so that those group elements (in a cluster) would have overall smallest distance (minimized) between Centroid and whilst the cost to establish and running the K clusters is optimal (each members as a cluster does not make sense as that is too costly to maintain and no value)
  5. K Means grouping could be easily “visually inspected” to be optimal, if such K is along the Principal Components (eg. if for people in different age, ethnic / regious clusters they tend to express similar opinions so if you cluster those surveys based on those PCs, then that achieve the minization goal (ref. 1) Also those PCs (ethnic, age, religion..) quite often are orthogonal, hence visually distinct by viewing the PCA
  6. However this intuitive deduction lead to a sufficient but not a necessary condition. (Ref 2: However, that PCA is a useful relaxation of k-means clustering was not a new result (see, for example,[35]), and it is straightforward to uncover counterexamples to the statement that the cluster centroid subspace is spanned by the principal directions.[36])

Choosing clusters based on / along the CPs may comfortably lead to comfortable allocation mechanism

This one could be an example if x is the first PC along X axis: (...........CC1...............CC2............CC3 X axis) where the X axis say capture over 9X% of variance and say is the only PC

6.Finally PCA is also used to visualize after K Means is done (Ref 4)

If the PCA display* our K clustering result to be orthogonal or close to, then it is a sign that our clustering is sound , each of which exhibit unique characteristics

(*since by definition PCA find out / display those major dimensions (1D to 3D) such that say K (PCA) will capture probably over a vast majority of the variance.

So PCA is both useful in visualize and confirmation of a good clustering, as well as an intrinsically useful element in determining K Means clustering - to be used prior to after the K Means.

Reference:

  1. https://msdn.microsoft.com/en-us/library/azure/dn905944.aspx
  2. https://en.wikipedia.org/wiki/Principal_component_analysis
  3. CLUSTERING USING PRINCIPAL COMPONENT ANALYSIS: APPLICATION OF ELDERLY PEOPLE AUTONOMY-DISABILIT (Combes & Azema)
  4. http://cs229.stanford.edu/notes/cs229-notes10.pdf Andrew Ng
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.