There are many excellent conversations on CV about the curse of dimensionality when applied to methods like k-means. The answer in the same post and other research (e.g., the paper titled "When Is ‘Nearest Neighbor’ Meaningful: A Converse Theorem and Implications") point that if the "intrinsic" domensionality of the data is lower then the curse does not apply.
However, I am coming from the angle of practical application, which seems to be not clearly answered.
Let's say we want to do k-means clustering in high dimensions. The data consists of $n$ rows and $d$ features. To make the conversation simpler, we can assume that the $d$ features are not independent and the intrinsic dimensionality of the data is actually $m$ such that $m<d$. To further simplify and for illustrative purposes, we can imagine two cases where the intrinsic dimensionality is the same but the correlation structure between the features is different:
- All of the $m$ features are duplicated multiple times to create the data with $d$ features. For example, all the features are duplicated once and we get $d = 2m$.
- Some of the $m$ features are duplicated to make up the $d$ features. For example, only the first feature is duplicated.
Now if PCA is run on this data then in both cases it will correctly say that the data is actually $m$ dimensional as 100% variance will be explained by the $m$ eigenvalues. Thus, one can conclude that the curse of dimensionality does not apply in either case and use all $d$ features to calculate distances between the points. However, the Euclidean distances in the two cases will be very different. Specifically, in the first case it will be the same as the $m$ dimensional data, while in the second case it will be biased.
Question: As we do not know the correlation structure of the data, should all analysis (e.g. k-means) be run on the $m$ PCA scores instead of the $d$ dimensional data?
EDIT: I am adding some R code and the resulting plot to show that the k-means results actually differ. The data x is available here. The data x1 simply duplicates the features of x and the data x2 duplicates only the first feature of x. PCA on both x1 and x2 show that first two components retain ~100% of cumulative variance. So I expect that all the plots on the right hand column to show similar clustering.
set.seed(1) x <- matrix(rnorm(100*2), nrow=100) x <- scale(x, scale=FALSE) x1 <- cbind(x, x) x2 <- cbind(x, x[,1]) k <- kmeans(x, 2, iter.max=100, nstart=10) k1 <- kmeans(x1, 2, iter.max=100, nstart=10) k2 <- kmeans(x2, 2, iter.max=100, nstart=10) p1 <- prcomp(x1) p2 <- prcomp(x2) kp1 <- kmeans(p1$x[,1:2], 2, iter.max=100, nstart=10) kp2 <- kmeans(p2$x[,1:2], 2, iter.max=100, nstart=10) par(mfrow=c(3,2)) plot(x[,1], x[,2], main="Original data x") plot(x[,1], x[,2], col=k$cluster, main="Cluster x") plot(x[,1], x[,2], col=k1$cluster, main="Cluster x1") plot(x[,1], x[,2], col=kp1$cluster, main="Cluster x1 PCA") plot(x[,1], x[,2], col=k2$cluster, main="Cluster x2") plot(x[,1], x[,2], col=kp2$cluster, main="Cluster x2 PCA")