Wherein Spectral Clustering Is Presented as an Entry Point, Connections to Matrix Factorization Are Sketched, and Graph-Laplacian Embeddings for Network-Derived Similarities Are Described
Getting a bunch of data points and approximating them (in some sense) by their membership (possibly fuzzy) in some groups or regions of feature space. Quantization, in other words.
For certain definitions, this can be the same thing as non-negative and/or low-rank matrix factorizations if you use mixture models, and is only really different in emphasis from dimensionality reduction. If you start with a list of features and then think about “distances” between observations, you have just implicitly intuited a weighted graph from your hitherto non-graphy data and are now looking at a networks problem.
If you care about clustering as such, spectral clustering feels like a nice entry point, maybe via Chris Ding’s tutorial on spectral clustering.
MCL: Markov Cluster Algorithm, a fast and scalable unsupervised cluster algorithm for graphs (also known as networks) based on simulation of (stochastic) flow in graphs.
There are many useful tricks in here, e.g. Belkin and Niyogi (2003) shows how to use a graph Laplacian (possibly a contrived or arbitrary one) to construct “natural” Euclidean coordinates for your data, such that nodes that have much traffic between them in the Laplacian representation have a small Euclidean distance (The “Urban Traffic Planner Fantasy Transformation”) Quickly gives you a similarity measure on non-Euclidean data. Questions: Under which metrics is it equivalent to multidimensional scaling? Is it worthwhile going the other way and constructing density estimates from induced flow graphs?
1 Clustering as matrix factorization
If I know me, I might be looking at this page trying to remember which papers situate k-means-type clustering in matrix factorization literature.
The single-serve paper doing that is Bauckhage (2015), but there are broader versions (Singh and Gordon 2008; Türkmen 2015), some computer science connections in Mixon, Villar, and Ward (2016), and an older one in Zass and Shashua (2005).
Further things I might discuss here are the graph-flow/Laplacian notions of clustering and the density/centroids approach. I will discuss that under mixture models
He, and Niyogi. 2003. “Locality Preserving Projections.” In Proceedings of the 16th International Conference on Neural Information Processing Systems. NIPS’03.
Yan, Huang, and Jordan. 2009. “Fast Approximate Spectral Clustering.” In Proceedings of the 15th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. KDD ’09.