# Clustering categorical variable values based on continuous target values

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)?

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.