Cross Validated is a question and answer site for people interested in statistics, machine learning, data analysis, data mining, and data visualization. It only takes a minute to sign up.
Sign up to join this community
I have a complex data set with various features, some of them are not normally distributed (e.g. very skewed to the left). Is it genereally advisable to make these variables normal distributed (Gaussian) before applying k-means clustering to get more reasonable clusters?
If not, why?
The k-means algorithm minimizes the following objective function
$\displaystyle\sum_{i=1}^n\left\|x_i-\mu_i\right\|^2=\sum_{i=1}^n\sum_{j=1}^p\left(x_i^{(j)}-\mu_i^{(j)}\right)^2=\sum_{j=1}^p\sum_{i=1}^n\left(x_i^{(j)}-\mu_i^{(j)}\right)^2$
where $\mu_i$ is the mean of the cluster associated with observation $i$ and $x_i^{(j)}$ denotes the $j$th coordinate of observation $x_i$. Notice that this is a sort of generalization of the variance.
The last sum can be expressed as an estimate of the variance of each of the clusters with respect to each of the variables.
So standardizing the variables to have equal variance is important because it means they get weighted equally with respect to each other. It's reasonable to weight the variables the same if you have no reason to think one is more important than the others.
Note that that has nothing to do with whether the variables belong to some known distribution such as the normal distribution.
Further note that the most popular algorithm for k-means (Lloyd's algorithm) always takes steps that decrease the variance. So, you will always get a local optimum in a finite number of steps. It is always advisable to run the algorithm multiple times to make sure that you are close to the global optimum.
A full answer to your question hinges on the term 'reasonable'. Given that I've covered that you will get an answer and how the answer might depend on the variables, a question you might ask is whether that answer is stable.
The solution might indeed be more stable with Gaussian distributed variables because the variance is sensitive to outliers. So outliers could certainly be driving the solutions you arrive at. For instance, consider a single outlier: if it's large enough it could force a center to be allocated to it in order to reduce its contribution to the objective function.
It would help if you were to provide information regarding the magnitude of the noise or overdispersion in these features. This can be as simple as providing means, medians and std deviations in a tabular format.
My experience is that K-means, as with many traditional methods, is fairly robust to violations of normality when the magnitude of the noise is not large. In this sense, K-means differs significantly from, e.g., OLS regression assumptions that the errors be normally distributed (not the inputs). K-means does not have similar assumptions. In fact and for the most part, assumptions wrt K-means are rules of thumb, conventions and heuristics that vary from discipline to discipline as well as varying as a function of highly subjective decisions made by the analyst. For you this means that there is no 'cookbook of rules' in existence wrt K-means which stipulates what you, the analyst, should or should not do in driving to a solution. This suggests additional K-means limitations:
It's not recommended for use with longitudinal information (time series)
Solutions are sensitive to dependence among features
The number of clusters has to be pre-specified and, given that number, K-means always finds a solution. This solution may or may not accurately represent the behavior of the data
Solutions are always spherical around the cluster centroids. If the 'real' clusters in the data are differently shaped, K-means will not capture patterning other than spherical
It does not return reasonable results with noncontinuous features or mixtures of continuous and discrete information
If the seeds used in forming the clusters are automatically created from random data draws, extreme values in the features can cause sparsity and nonrepresentative distortion in the results
As aksakal notes, k-medians is one workaround to the issue you've raised. Assuming the ready availability of that routine, its results should be compared with solutions using k-means.
Wrt rules of thumb, a common prescription in marketing is first, standardize the features to a mean of 0 and std dev of 1 then, second, reduce the dimensionality of the data using PCA (or similar methods). In part, this helps mitigate feature dependence. This also smoothes 'lumpiness' that can result from using the full or unreduced matrix of features. Finally and for your purposes dimension reduction could also help blunt the impact of extreme or overdispersed information. I've found such pre-clustering, dimension reduction methods helpful, that is when they work -- which is most of the time.
However, what does one do in the case of large magnitude noise? To facilitate a deeper understanding of the issues that raises, Xie and Xing's paper Cauchy Principal Component Analysis (ungated here ... http://www.cs.cmu.edu/~pengtaox/papers/cpca.pdf) presents a typology of data matrices as a function of sparsity and noise. Despite its focus on PCA, their discussion is informative as it can be generalized to K-means.
If Xie and Xing's discussion is too technical, there are many simpler transformations that can be applied to the extreme features. For positive valued features, the natural log transformation compresses heavy tails. Other possibilities include the Box-Cox transformation, the inverse hyperbolic sine, Lambert's W, and so on. Formulas for all of these are readily obtainable online.
The bottom line is that there is no 'one size fits all' answer to your question.
