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)?
 A: 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.
References
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).
