# Clustering optimization problem for categorical data: How to solve?

#### 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.

• I don't really understand what your problem formulation is. But if it's a sum of Kullback-Leibler divergence:s, with some (or all) variables being integer,, and some linear constraints, as I think it might be, then you can straightforwardly formulate (using provided function for KL Divergence) it in a convex optimization tool, such as CVX, YALMIP, CVXPY, or CVXR (all freely available) and use Mosek as solver. Mosek is not open source (but has free license for academics). Whether it is solvable within a useful time frame is another matter. Jun 30 at 14:12
• A possibly lower performing alternative using only free solvers would be to use YALMIP, with BNB as solver, and ECOS or SCS as upper solver. Jun 30 at 14:18
• What dimensions are you looking at ($n,$ $N,$ $k$ and the typical number of choices for a question)? Also, are you looking for exactly, at least or at most $k$ clusters?
– prubin
Jun 30 at 19:34
• @prubin: Nothing crazy big: $n \approx 100$, $N \approx 30$. I was planning on running the opimization separately for $2 \leq k \leq 5$. Jul 4 at 5:34

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.