# 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, 2023 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, 2023 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, 2023 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, 2023 at 5:34