Let's say I have $n$ data points with just one categorical feature $x$ and a continuous target variable $y$. I want to divide the possible values of $x$ into subsets such that the value of $y$ doesn't vary much within a subset.

As an example, suppose $x$ takes $5$ possible unique values: $x_1,\ldots,x_5$. We observe that the values of $y$ don't vary much across $x_1$ and $x_2$. $y$ doesn't vary much across $x_3$ and $x_5$, but is different from the typical $y$ value for $x_1$ and $x_2$. For $x_4$, $y$ values are quite different from the above groups. So we can say that $(x_1,x_2), (x_3,x_5)$ and $(x_4)$ can be considered as "clusters".

Now what's a concrete way of saying that $y$ doesn't "vary much across $x_1$ and $x_2$"? One natural way to define that is for $y$ to have the same distribution for $x_1$ and $x_2$, i.e. the same mean and standard deviation of $y$ values for both $x_1$ and $x_2$.

  • Is there a better way to characterize the fact that $y$ doesn't "vary much across $x_1$ and $x_2$? Maybe the way I defined it above is too idealistic and I need a criterion more suited to a real-life dataset?

  • Are there any popular existing methods or library functions to solve such kind of a problem (i.e. clustering categorical feature values on the basis of continuous target values)?


1 Answer 1


The problem can be reframed as clustering individual data points according to their $y$ values, while requiring that all points with the same $x$ value are assigned to the same cluster. This is a constrained clustering problem, where the $y$ values determine distance/similarity, and the $x$ values determine a set of must-link constraints. A must-link constraint declares that two specified points must be assigned to the same cluster.

Since you indicated that $y$ values should vary as little as possible within a cluster, minimizing the within-cluster variance is a natural approach. This is a constrained k-means problem, and can be solved using the COP-KMEANS algorithm (Wagstaff et al. 2001). It's a simple modification of Lloyd's algorithm, which is the typical algorithm for solving the regular (unconstrained) k-means problem. The only change is that, when assigning points to the nearest centroid, we avoid making assignments that violate the constraints.


Wagstaff, K., Cardie, C., Rogers, S., & Schrödl, S. (2001, June). Constrained k-means clustering with background knowledge. In Icml (Vol. 1, pp. 577-584).


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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