PCA before K-mean clustering

Question

If I applied PCA on feature vectors and then I do clustering, such like following:

reduced_data = PCA(n_components=2).fit_transform(data)
kmeans = KMeans(init='k-means++', n_clusters=n_digits, n_init=10)
kmeans.fit(reduced_data)

1. The reduced data will be the in terms of PCA components, so after clustering in kmean, you can get a label for each point (reduced_data), how to know which one from the origin data?

2. how to play with a number of PCA components regarding the number of clusters? Thanks.

Answer 1

1. PCA reduces dimensionality. It does not change the number of observations you have. Nor does it change the order of the data. The n-th observation in your original dataset will still be the n-th observation post-PCA.

2. Choosing the number of components in PCA and choosing the number of clusters in K-Means are independent of each other. Both K-Means and PCA seek to "simplify/summarize" the data, but their mechanisms are deeply different. PCA looks to find a low-dimensional representation of the observation that explains a good fraction of the variance. K-Means looks to find homogeneous subgroups among the observations.

   • For PCA, the optimal number of components is determined visually through the scree plot or mathematically using Kaiser's criterion (drop all components with eigenvalue <1). From my experience the two don't always give the same results, but the difference is negligible.

Screeplot (source) It does not make much sense to go beyond the 4th component. Law of diminishing marginal returns.

• For K-Means: Since increasing the number of clusters will always reduce the distance from centroid to data points, increasing K will always decrease this metric, to the extreme of reaching zero when K is the same as the number of data points. If we plot the average within cluster distance to centroids vs number of clusters, we will find the "elbow" to be a good place to stop.

source

Answer 2

PCA will not change the order of your points. The first point will still be the first point.

As for the second, this is too unclear to answer. There is no obvious relationship between the number of clusters and the number of PCs. If you use too few PCs, your data approximation is too crude. If you use too many, then you will be working with random deviations too much, and the results will usually be worse, independent of the number of clusters.

Answer 3

I haven't used sklearn but I'll try to answer the question to the best of my ability.

Assuming you have an $n \times f$ matrix (data), now reduced to $n\times d$ (reduced data). Say the 1st reduced data point was mapped to some cluster, wouldn't that correspond to the first data point in the reduced matrix being classified to that same cluster? (Each row denotes a data point) Basically, the ordering will not change.

Alternatively, if you want to look at it more mathematically, assume $W=(w1,w2...wd)$ form the basis vectors of the subspace you want to map your feature vectors to (the first d eigenvectors of your data covariance matrix).

Now every data point can be represented as a linear combination of these basis vectors: $x = \alpha1w1 + \alpha2w2 ... + \alpha dwd$

Here the vector $\alpha = (\alpha1, \alpha2..., \alpha d)$ is the representation of your data point in d dimensions, i.e. in the subspace, and your original data point is: $x = W^T\alpha$

I'm not so clear about what you are asking in part 2). You choose the number of components you want to keep in PCA depending on the amount of error you are willing to tolerate. Suppose you want the reduced data points to correspond to 95% of the variance, you select the first d eigenvectors such that their eigenvalues correspond to the above percentage of variance. $\frac {\sum\limits_{i=1}^d \lambda_i}{\sum\limits_{i=1}^n \lambda_i} \times 100 = 95\% $

Hope that helped!