Clustering on n features while maximizing the heterogeneity on m remaining features

Question

We have a random vector $X\sim p(X)$, and a set of realizations of the random vector $S=\{X_i\}_{i=1}^N$. The random vector has $n$ continuous and $m$ categorical features. I want to cluster $S$ so that datapoints with similar values of the continuous features end up in the same cluster, but at the same time I want to maximize the heterogeneity of the categorical features in each cluster. Example with $n=2, m=1, N=4$:

$$ S=\{(0.2, 0.4, \text{dog}),(-0.2, -0.4, \text{cat}),(-0.2, 0.4, \text{dog}),(0.2, -0.4, \text{cat})\}$$

If we didn't have the categorical variable, $\{X_1,X_3\}$ and $\{X_2,X_4\}$ would be "natural" clusters because they're the closest pairs. However, since we also want "diverse" clusters in terms of the categorical variable, we settle for $\{X_1,X_4\}$ and $\{X_2,X_3\}$. $\{X_1,X_2\}$ and $\{X_3,X_4\}$ would also be "diverse" clusters, but the points would be farther apart, so they seem to me a worse choice. Of course, this is just a toy example: a clustering task with 4 points and 2 clusters doesn't make a lot of sense.

Which algorithms could I use?

Answer 1

I will offer a simple example for numerical data. The idea behind it can be extended to the case of categorical data without major conceptual difficulty (as far as I can see).

Suppose you have two variables, $X$ and $Y$. You want to cluster data so that points with similar $X$ values and dissimilar $Y$ values end up in the same cluster while points with dissimilar $X$ values and similar $Y$ values end up in different clusters. If you only cared about $X$, you would use some traditional clustering algorithm. However, you have the problem of $Y$ which is the opposite to traditional clustering.

Note that a clever definition of distance* can fix this. If you define the distance so that dissimilar $Y$s get a low score but similar $Y$s get a high score, you are back to traditional clustering. One way of doing that is to reverse the sign of the $Y$ coordinate in some traditional distance metric. E.g. the traditional Manhattan distance between points $(i,j)$ is $$ d_M(i,j)=\mid x_i-x_j \mid + \mid y_i-y_j \mid $$ but the modified one would be $$ d_M'(i,j)=\mid x_i-x_j \mid - \mid y_i-y_j \mid. $$ If you base clustering on the latter, you get the desired result.

Another example: Euclidean distance. The traditional one is $$ d_E(i,j)=\sqrt{ (x_i-x_j)^2 + (y_i-y_j)^2 } $$ but the modified one would be $$ d_E'(i,j)=\text{sign}\left((x_i-x_j)^2 - (y_i-y_j)^2\right) \sqrt{\mid (x_i-x_j)^2 - (y_i-y_j)^2\mid }. $$

This idea should be possible to extend to distance measures for categorical variables by taking the negative of the distance for the $Y$ coordinate where needed.

---

*The cleverly defined distance should probably not be called distance anymore as it violates some conditions and is not intuitively a distance. But it will be used in place of distance in a clustering algorithm, so I have kept the term.