# Clustering categorical features based on fit

I have a set of data. For our purpose lets simplify it to one independent numerical variable,$x$, and dependent numerical variable, $y$. The goal is to train on the data to determine the parameters in the model, for simplicity assume $y=mx+b$. I could then predict new $y$ values when new $x$ values are given. Pretty standard fitting.

The tricky part is that I have another feature dimension in my data set which is categorical with many possible values. I could do one fit per unique categorical value or fit all values together but I have reason to believe it is best to do some clustering and do one fit per cluster. There is a clear trade-off since every cluster adds more parameters but reduces the data per fit.

If we simplify to trying to find two Clusters. If I could hypothesize two clusters which would each fit to their own line. To restate, $y_1=m_1*x_1+b_1$ and $y_2=m_2*x_2+b_2$ where the data is split into two groups based on clustering the categorical variable might fit the data "better" than $y=m*x+b$ when all the data is fit together. The problem is that even if I knew the clusters I would not know what metric to use for "better". RMSE should always decrease for as the number of clusters increase.

Similarly $R^2$ would always decrease because I am adding parameters so this would lead to overfitting. Should I use $\frac{\chi^2}{ndf}$? I feel like this is something that must be well understood and I am just missing something on how to balance the number of clusters/models and find them in the first place.

A very similar question was asked and partially answered years ago Clustering as a means of splitting up data for logistic regression

There are a lot of performance measures which penalise for eating up extra degree of freedom like AIC, BIC or Adjusted R-square. You can use one of them. And if you are concerned with overfitting then you could try test and train validation and there you can simply use performance measures like MAPE or RMSE. Compared to your older method, if MAPE is decreasing on test data as well then there is no overfitting.

I am not sure if I am miss understanding something in your question, else these performance measures should work just fine.

• You understand the issue and I have been doing as you suggest. Guess my clusters then use RMSE to see if it improved the overall model. I want to remove this iterative guesswork. I am thinking about some sort of Agglomerative Hierarchical clustering based on which categorical values are fit well together. I have a maximum number of clusters for technical reasons so a hierarchical clustering dendrogram would be a valuable output. I am tempered to brute force it combinatorially but I think the computing time would explode – Keith Mar 22 '17 at 18:15
• Are you trying to group observations into clusters and then run some models on these clusters? – saurav shekhar Mar 23 '17 at 17:28
• Essentially yes. There is nothing to cluster on except possibly the performance measure of the models so that was the plan. I want to find the k clusters that minimize the combined RMSE. There would be one model per cluster but the issue is that RMSE decreases with increased k and would eventually over-fit. I need a natural balance. – Keith Mar 23 '17 at 18:33
• Have you tried splines? – saurav shekhar Mar 23 '17 at 19:16
• Splines are just peicewise functions. I do not want to cluster (or make peicewise) my independent numerical variable. I want to cluster in terms of another independent categorical variable. Or did I miss something? I am giving you the bounty since you have helped. – Keith Mar 23 '17 at 21:35

Mixed models is probably what you are looking for. They are extensions of linear models when you have fixed effects(in your case, the set of independent variables) and random effects (the clusters your data belongs to) which seem to be the case from your description.

Here's a useful reference: Random-Effects Regression Models for Clustered Data With an Example from Smoking Prevention Research

• This is useful knowledge but I have not sorted out if it can be applied to my specific case yet. I think I am required to know the hierarchy (ie clustering) before hand. – Keith Mar 23 '17 at 22:31
• In your description, you are building separate regressions for each cluster right? – Arun Jose Mar 27 '17 at 10:58
• Yes. The problem is that the clustering would be to optimize the total RMSE across all regressions so you don't have it at the time of clustering. – Keith Mar 27 '17 at 16:14