Abstract

Clustering observations described by both numerical and categorical variables is routine in survey, marketing and biomedical data. Gower-based hierarchical clustering lacks a global objective, K-prototypes inherits the nonconvexity and initialization sensitivity of K-means, and model-based clustering relies on EM algorithms prone to local optima.

We introduce Mixed Data Convex Clustering (MIDACC), a convex clustering framework that treats both variable types within a single penalized likelihood. Each observation receives its own centroid. A Gaussian loss for the numerical variables and a multinomial logit loss for the categorical ones are coupled through an l2 fusion penalty on sparse kernel weights, so that centroids fuse progressively along a regularization path. Categorical differences are measured in a metric that makes the objective invariant to the choice of reference category. Each loss is normalised by its value at the single-cluster fit, and a mixing parameter sets the relative weight of the two variable types in both the loss and the penalty. A ridge term on the categorical centroids makes the objective uniformly strongly convex, so a unique minimizer exists over the whole path, including its unpenalized endpoint.

We derive a majorization-minimization algorithm based on Bohning's bound for the multinomial loss and a quadratic surrogate for the fusion penalty. A diagonal majorization step and a centroid-assignment decomposition give closed-form updates whose cost per iteration is linear in the number of observations.

We establish invariance to category relabelling, the behaviour of the path at both extremes, and monotone descent of the algorithm. We give a deterministic, finite-sample window for the regularization parameter inside which the minimizer recovers a prescribed partition exactly. Both thresholds are computable from the data and the fusion graph, through a flow constant measuring how well the within-cluster graph absorbs the pull of the other clusters. A corollary shows that clusters indistinguishable on the numerical variables remain separated through their categorical profiles alone. Since fusions along the computed path are irreversible, we also give an a posteriori certificate of global optimality for the returned solution, whose exact form is a second-order cone program. The mixing parameter is selected by comparing the normalised losses of refitted partitions at a common resolution, and the number of clusters by a BIC evaluated at the unpenalized refit.

The talk presents the method and its guarantees, simulation studies against K-prototypes, Gower-based hierarchical clustering and KAMILA, and an empirical application.