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?

  • 1
    $\begingroup$ Cool question! You could perhaps use an existing clustering algorithm with a tweak: the distance between the categorical features should be treated as the negative thereof; distance(cat,dog) will be low but distance(cat,cat) or distance(dog,dog) will be high. The idea is that you only need a custom distance metric and then can use a traditional clustering algorithm. $\endgroup$ – Richard Hardy Jan 29 at 10:16

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.

  • 1
    $\begingroup$ Practical consideration: add an alpha parameter in the pseudodistance - it will allow to control diversity. Regrading distance on categorical features: encode them e.g. with one-hot encoding and use PCA. $\endgroup$ – hans Feb 2 at 22:51
  • $\begingroup$ @hans, thanks, good idea. $\endgroup$ – Richard Hardy Feb 3 at 6:14
  • $\begingroup$ @hans how would you include $\alpha$? For example, how would you modify the above formulas for of $L_1$ and $L_2$ pseudodistances? $\endgroup$ – DeltaIV Feb 4 at 22:18
  • 2
    $\begingroup$ @DeltaIV, I suppose premultiply the distance component corresponding to a particular coordinate, e.g. use $\alpha(y_i-y_j)^2$ instead of $(y_i-y_j)^2$ inside of $d'_E$ and similarly in $d'_M$. This is the same as to scale some dimensions (variables, features) before calculating the distance. $\endgroup$ – Richard Hardy Feb 5 at 7:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.