Why are mixed data a problem for euclidean-based clustering algorithms?

Question

Most classical clustering and dimensionality reduction algorithms (hierarchical clustering, principal component analysis, k-means, self-organizing maps...) are designed specifically for numeric data, and their input data are seen as points in a euclidean space.

This is a problem of course, as many real-world questions involve data that are mixed: for instance if we study buses, the height and length and motor size will be numbers, but we might also be interested in color (categorical variable: blue/red/green...) and capacity classes (ordered variable: small/medium/large capacity). Specifically, we might want to study these different types of variables simultaneously.

There are a number of methods to extend classical clustering algos to mixed data, for instance using a Gower dissimilarity to plug into hierarchical clustering or multidimensional scaling, or other methods that take a distance matrix as input. Or for instance this method, an extension of SOM to mixed data.

My question is: why can't we just use the euclidean distance on mixed variables? or why is it bad to do so? Why can't we just dummy-encode the categorical variables, normalize all variables so that they have a similar weight in the distance between observations, and run the usual algos on these matrices?

It's really easy, and never done, so I suppose it's very wrong, but can anyone tell me why? And/or give me some refs? Thanks

Answer 1

It's not about not being able to compute something.

Distances much be used to measure something meaningful. This will fail much earlier with categorial data. If it ever works with more than one variable, that is...

If you have the attributes shoe size and body mass, Euclidean distance doesn't make much sense either. It's good when x,y,z are distances. Then Euclidean distance is the line of sight distance between the points.

Now if you dummy-encode variables, what meaning does this yield?

Plus, Euclidean distance doesn't make sense when your data is discrete.

If there only exist integer x and y values, Euclidean distance will still yield non-integer distances. They don't map back to the data. Similarly, for dummy-encoded variables, the distance will not map back to a quantity of dummy variables...

When you then plan to use e.g. k-means clustering, it isn't just about distances, but about computing the mean. But there is no reasonable mean on dummy-encoded variables, is there?

Finally, there is the curse of dimensionality. Euclidean distance is known to degrade when you increase the number of variables. Adding dummy-encoded variables means you lose distance contrast quite fast. Everything is as similar as everything else, because a single dummy variable can make all the difference.

Answer 2

At the heart of these metric based clustering problems is the idea of interpolation.

Take whatever method you just cited, and let us consider a continuous variable such as weight. You have 100kg and you have 10kg in your data. When you see a new 99kg, the metric will enable you to approach 100kg --- even though you have never seen it. Unfortunately, there is no interpolation existing for discrete data.

Another argument for this question is there is no natural way to do so. You want to assign 3 values in R and make them equal-distance between each pair, this would be impossible. If you assign them into different categories and run let's say PCA, then you lose the information that they reflect in fact the same category.

Answer 3

A problem with unorder categorical values is that if you dummy encode them you force an ordering and thus a new meaning to the variables. E.g if you encode blue as 1 and orange as 2 and green 3 then you imply that a data pattern with orange value is closer to a pattern with green value than the one with the blue value.

One way to handle this is to make them new features (columns). For each distinct value you create a new binary feature and set it to true/false (in other words binary encode the values and make each bit a column). For each data pattern from this new set of features, only one feature will have the value 1 and all the others 0. But this usually doesn't stop the training algorithm to assign centroid values close to 1 to more than one features. This ofcourse might cause interpretation issues cause this doesn't make sense in the data domain.

You don't have the same problem with "capacity classes" namely ordered categories since in that case the numerical values assignment makes sence.

And ofcourse is you use features of different nature or measurement unit or different range of values then you should always normalize the values.

https://stackoverflow.com/questions/19507928/growing-self-organizing-map-for-mixed-type-data/19511894#19511894

https://stackoverflow.com/questions/13687256/is-it-right-to-normalize-data-and-or-weight-vectors-in-a-som/13693409#13693409

Answer 4

The answer is actually quite simple, we just need to understand what the information in a dummy variable really is. The idea of a dummy variable denotes the presence or absence of factor levels (discrete values of a categorical variable). It is meant to represent something non-measurable, non-quantifiable, by storing the information of whether it's there or not. This is why a dummy variable is expressed in binary digits, as many as the discrete values of the categorical variable it represents (or minus 1).

Representing factor levels as 0/1 values makes sense only in an analytical equation, such as a linear model (this is an easy concept for those who can interpret the coefficients of statistical models). In a dummy variable, the information of the underlying categorical variable is stored in the order of bits. When using those bits as the dimensions to map an input sample to a feature space (as in the case of a similarity/distance matrix), the information in the order of bits is completely lost.