1
$\begingroup$

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 a dataset. Assuming an arbitrary clustering algorithm $A$, I would like to find a subset $F$ of $\{1,\ldots, m\}$, representing indices of the columns of $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.

$\endgroup$
1
1
$\begingroup$

This problem is called subset selection and is nowadays usually solved by appropriate nonsmooth convex optimization techniques.

Two recent papers describing subset selection methods are
http://users.cms.caltech.edu/~jtropp/reports/Tro04-Just-Relax-TR.pdf
http://automatica.dei.unipd.it/public/Schenato/PSC/2010_2011/gruppo4-Building_termo_identification/Bibliografia%20Casuale/Sensor%20Selection%20via%20Convex%20Optimization.pdf
but this is just the tip of an iceberg.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.