Clustering optimization problem for categorical data: How to solve?

Question

Problem

Say I have a data set of $n \in \mathbb N$ survey responses to $N \in \mathbb N$ categorically-valued multiple-choice questions, which we denote as $$ \mathbf X = \{ \mathbf x_j \}_{j = 1}^n \subset \mathcal X := \mathcal X_1 \times \dots \times \mathcal X_N \quad \text{with} \quad \mathbf x_j = \{ x_{j \ell } \}_{\ell = 1}^N. $$

I have an idea to perform a clustering analysis as follows:

Let $k \in \mathbb N$ be the pre-selected number of clusters and define the optimization problem: $$ P: \quad \min_{\mathcal S = \{S_1, \dots, S_k \} } \quad \sum_{i = 1}^k \sum_{\mathbf x \in S_i} \sum_{\ell = 1}^N - \log\left( \frac{1}{|S_i|} \sum_{ \tilde{\mathbf x} \in S_i} \mathbf 1\{ \tilde x_\ell = x_\ell \} \right) \quad \text{s.t.} \quad \bigsqcup \mathcal S = \mathbf X, $$ i.e. $\mathcal S$ is a partition of $\mathbf X$ into $k$ disjoint sets (clusters).

How could we go about solving this? (Or finding an approximate or local minimum?)

I'd be especially happy to hear about open source solvers that could help with this problem.

Motivation and thoughts

Let $\delta_{x}$ be the Dirac measure in the point $x$. Let $\hat Q_\ell(\bullet|S_i) = \frac{1}{|S_i|} \sum_{ \tilde{\mathbf x} \in S_i} \mathbf 1\{ \tilde x_\ell = \bullet \}$, i.e. the conditional empircal probability measure given the subset $S_i$. Then for $\mathbf x \in S_i$, we have the Kullback-Leibler divergence: $$ \begin{aligned} D_{\text{KL}}\left( \delta_{x_\ell} \, \middle\| \, \hat Q_\ell(\bullet|S_i) \right) = \sum_{y \in \mathcal X_\ell} \delta_{x_\ell}(y) \cdot \log \left( \frac{\delta_{x_\ell}(y)}{ \hat Q_\ell(y|S_i) } \right) &= - \log\left( \frac{1}{|S_i|} \sum_{ \tilde{\mathbf x} \in S_i} \mathbf 1\{ \tilde x_\ell = x_\ell \} \right) \\ &= \log|S_i| - \log \left|\{ \tilde{ \mathbf x } \in S_i : \tilde{x}_\ell = x_\ell \} \right|. \end{aligned} $$ So we're summing over the Kullback-Leibler divergences between the individual responses to question $\ell$ in cluster $S_i$ and conditional empirical distribution for question $\ell$ given $S_i$.

I'm not sure how to reformulate this into an analysis or solver-amenable problem. It seems like a pretty beastly combinatorial problem.

Answer 1

I tried a random key genetic algorithm (in R, using four parallel threads), both as a "standard GA" (single population) and as an "island" model (multiple populations, four in my tests, evolving separately and periodically using "migration" to pass "genetic material" to other populations). I used 100 responses to 30 questions with five clusters. Both methods hit a predefined limit of 500 generations in around three minutes on my PC (decent but no workstation), and appeared to still be improving when they hit that limit. I did not do many runs, nor did I experiment with the various parameters (mutation rates, elitism, migration rates) available.

The island model did a bit better than the standard model (which has me wondering if the standard model would benefit from a higher mutation rate or "immigration" of a few random solutions in each generation). Improvement over the initial random solution after three minutes was only about 2%, and I have no idea whether that is good or bad in this context.