Difference between PCA and spectral clustering for a small sample set of Boolean features

Question

I have a dataset of 50 samples. Each sample is composed of 11 (possibly correlated) Boolean features. I would like to some how visualize these samples on a 2D plot and examine if there are clusters/groupings among the 50 samples.

I've tried the following two approaches:

(a) Run PCA on the 50x11 matrix and pick the first two principal components. Project the data onto the 2D plot and run simple K-means to identify clusters.

(b) Construct a 50x50 (cosine) similarity matrix. Run spectral clustering for dimensionality reduction followed by K-means again.

What is the conceptual difference between doing direct PCA vs. using the eigenvalues of the similarity matrix? Is one better than the other?

Also, are there better ways to visualize such data in 2D? Since my sample size is always limited to 50 and my feature set is always in the 10-15 range, I'm willing to try multiple approaches on-the-fly and pick the best one.

Related question: Grouping samples by clustering or PCA

Answer 1

What is the conceptual difference between doing direct PCA vs. using the eigenvalues of the similarity matrix?

PCA is done on a covariance or correlation matrix, but spectral clustering can take any similarity matrix (e.g. built with cosine similarity) and find clusters there.

Second, spectral clustering algorithms are based on graph partitioning (usually it's about finding the best cuts of the graph), while PCA finds the directions that have most of the variance. Although in both cases we end up finding the eigenvectors, the conceptual approaches are different.

And finally, I see that PCA and spectral clustering serve different purposes: one is a dimensionality reduction technique and the other is more an approach to clustering (but it's done via dimensionality reduction)

Answer 2

For Boolean (i.e., categorical with two classes) features, a good alternative to using PCA consists in using Multiple Correspondence Analysis (MCA), which is simply the extension of PCA to categorical variables (see related thread). For some background about MCA, the papers are Husson et al. (2010), or Abdi and Valentin (2007). An excellent R package to perform MCA is FactoMineR. It provides you with tools to plot two-dimensional maps of the loadings of the observations on the principal components, which is very insightful.

Below are two map examples from one of my past research projects (plotted with ggplot2). I had only about 60 observations and it gave good results. The first map represents the observations in the space PC1-PC2, the second map in the space PC3-PC4... The variables are also represented in the map, which helps with interpreting the meaning of the dimensions. Collecting the insight from several of these maps can give you a pretty nice picture of what's happening in your data.

On the website linked above, you will also find information about a novel procedure, HCPC, which stands for Hierarchical Clustering on Principal Components, and which might be of interest to you. Basically, this method works as follows:

• perform a MCA,
• retain the first $k$ dimensions (where $k<p$, with $p$ your original number of features). This step is useful in that it removes some noise, and hence allows a more stable clustering,
• perform an agglomerative (bottom-up) hierarchical clustering in the space of the retained PCs. Since you use the coordinates of the projections of the observations in the PC space (real numbers), you can use the Euclidean distance, with Ward's criterion for the linkage (minimum increase in within-cluster variance). You can cut the dendogram at the height you like or let the R function cut if or you based on some heuristic,
• (optional) stabilize the clusters by performing a K-means clustering. The initial configuration is given by the centers of the clusters found at the previous step.

Then, you have lots of ways to investigate the clusters (most representative features, most representative individuals, etc.)