Are there any clustering algorithms that do not exclude/impute missing data?

Question

From my understanding, clustering algorithms require complete data. Based on this, if there are missing values in my dataset I have two options:

1. Impute missing information using some sort of imputation method

2. Get rid of observations that contain missing values

Sometimes I believe neither approach is appropriate, as ignoring observations can remove a lot of important information (sometimes all information, if there is always 1 missing value per obs for example) - and imputation methods are not 100% accurate.

As such, are there any clustering methods that do not require either of these options? In other words, algorithms that use the partial information from observations that don't have complete values, without discarding them? (looking at the information they do have in common)

This would allow me to assign these observations to clusters without applying any imputation methods to the data.

Answer 1

In k-means, you can ignore the missing attributes both when computing the cluster assignment and when recomputing the cluster averages. But of course it only works for continuous data.

In k-modes you could likely do the same - skip the missing value when finding the best assignment, as well as when finding the mode.

Implementing them with support for NAs is a mess, and will make the code much slower, so people didn't do it. You'll have to do it yourself. There are a number of ugly corner cases, too: what if all points assigned to a cluster have NA in the same attribute?

For many other methods you need to provide a distance function or matrix. So you "just" need to decide how to compute this. Beware that certain approaches (such as skipping attributes in the all-NA case) cause problematic points to become too central and violate the triangle inequality. Most clustering algorithms don't require the triangle inequality though. But imputation is an easy way that doesn't have this problem.

Last but not least, you could do uncertain clustering. For points with missing values, you assume some prior distribution over the possible values, then do several runs to find the most likely assignments. Similarly, you could model a distribution over the distances. But this is quite complicated. The easiest way is to perform some kind of "random imputation" many times and find the consensus clustering.

Answer 2

Some clustering algorithms rely on the Expectation-Maximisation (EM) algorithm and its variants, e.g. k-means (deterministic- partition clustering), Gaussian mixture models (probabilistic, model-based clustering), etc. In these, the cluster membership of the observations are regarded as the latent variable and a version of the EM algorithm is applied to find maximum likelihood or maximum a posteriori (MAP) estimates in the existence of these latent variables

There exist extensions of the EM algorithm that can cater for missing values. Have a look at this thesis for an example of such an extension.

As a final note, and as you allude to, it is crucial to examine the reason for the absent values before trying to address the missing data problem. In general we want to discover if the data is missing randomly Missing at Random, (MAR) or Missing Completely at Random, (MCAR), or if the absent values are related to the response data (Not Missing at Random, NMAR). For instance, deleting missing values may give biased results when the MCAR assumption is violated.

Answer 3

Say feature X1 may be missing. If X1 is categorical, you could add a missing level and proceed. If X1 is continuous, you could set it to the mean value of non-missing X1’s and create a categorical variable X1_missing that is True only when X1 is missing.

This assumes a clustering algorithm that can handle categorical variables.

Answer 4

Perhaps using binary trees (CART, C4.5, whatever version you prefer) might be of help here. You train the tree with complete data and then drop cases to be classified and label them according to the leaf where they end. Trees have their own rules when a variable is missing (stop at the current node, go with the majority, randomize, etc.); and it may well happen that a missing value is not needed anyway, because the splits only use observed values of the case to be classified.

You may find about trees in many monographies, including The Elements of Statistical Learning.