Finding most informative feature subsets given dataset, clustering algorithm and gold standard partition

Question

I have an $n \times m$ matrix of data $\mathbf{D}$ as well as a $k$-partition $P$ of $n$ indices each representing a row in $\mathbf{D}$. Assuming an arbitrary clustering algorithm $A$, I would like to find a subset $F$ of $\{1,\ldots, m\}$, representing indices of the columns of $\mathbf{D}$, such that applying $A$ to only the columns indexed by $F$, an $n \times |F|$ matrix, minimizes the average variation of information (VI) between $P$ and the output of $A$. Another way of saying this is that I would like to be able to find the subspace on which $\mathbf{D}$ is most informative about $P$.

(That the metric is VI or that the statistic taken over multiple runs is an average is not necessarily important. I'm looking for a general solution, but if a solution that specifies either the metric or the clustering algorithm exists, I'd be interested.)

Attempting to build the distribution of (normalized) variation of information values by brute force is not practical since the number of possible subsets of $\{1,\ldots, m\}$ is the Stirling number (of the second kind) $S(m, 2)$, which obviously gets monstrous as $m$ gets to any interesting size.

Answer 1

If you objective is purely optimization of VI then without a lot of knowledge on the structure of your data you can't expect to do much better than what standard combinatorial algorithms offer. You can try things like simulated annealing to move across the feature space "intelligently", perhaps.

Typically however you want a statistical method to determine which subset of features yield the most informative clustering. The terminology for this problem is unsupervised feature selection. Some popular methods include:

1. Regularization on parameters Zhou, Pan and Shen (2009), which assumes a Gaussian mixture model.

2. Regularization on feature weights Witten and Tibshirani (2010), which express clustering criteria as additive in features then regularize the weights assigned to each summand.

If your clustering algorithm in already known (and/or the number of clusters) then I worked on a method that is based on Prediction Strength. The idea is to split your data into two halves by rows (observations), call them $X$ (training data) and $Y$ (test data).

Then calculate $A^X_{i} = \{x:C_X(x) = i\}$ and $B_{ij} = A^X_i \cap A^Y_j, \: i,j = 1,\ldots,k$, where $C_X(x)$ is the cluster index the algorithm would assign to a data point $x$ when fit on the data-set $X$.

The $A_i^X$ represent how the training data partitions the feature space space. Therefore $B_{ij}$ represents how much overlap there is between the training set and a test set clustering. If the clustering is extremely stable the overlap will be large, so you search for features that maximize the statistic

$\begin{align*} ps(K) &= \mathbf{P}(x_1, x_2 \: \text{in same training cluster} \: | \: x_1,x_2 \:\text{in same test cluster}) \\ &=\frac{1}{K}\sum_{i=1}^K\frac{\sum_{j=1}^K |B_{ij}|\left(|B_{ij}| - 1\right)}{|A_i^X|\left(|A_i^X| - 1\right)} + o_p(1) \end{align*}$

given the number of clusters $K$.

In practice I sample feature subsets randomly then average to see which features yield the best prediction strength.

Answer 2

This is not exactly a reply to your question, but starts a step earlier:

Have you looked into what the various subspace clustering algorithms do?

There is a survey article on subspace methods (which also covers correlation methods):

• Clustering high-dimensional data: A survey on subspace clustering, pattern-based clustering, and correlation clustering
  Hans-Peter Kriegel, Peer Kröger, Arthur Zimek
  https://dl.acm.org/citation.cfm?id=1497578

I can imagine that some of the algorithms will try to measure what you are looking for.