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

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.

• What do you expect an algorithm to do when it sees a missing value? if you can explain that, then you might do the same beforehand. May 29 '19 at 17:39
• @NickCox I guess I want the algorithm to compute the distances based on the data points two observations do have in common. For example, (1,2,3,NA,5) and (1,2,3,4,5) would have a distance of 0, even though the first observation has a missing value May 29 '19 at 17:44
• Then NA, 2, 3, 4, 5 and 1, 2, NA, 4, 5 and some others are all equivalent. I doubt that you can make that consistent. Do you also want NA, NA, NA, NA, NA and 1, 2, 3, 4, 5 to be equivalent? May 29 '19 at 17:48
• @NickCox I agree that the first two would be equivalent, since the pairwise comparisons are equivalent (2, 4 and 5). However, I don't want NA, NA, NA, NA, NA to be equivalent to 1, 2, 3, 4, 5. Does this make sense? May 29 '19 at 17:50
• I don't know if it makes sense. I just gather that you have specific rules for NA so that you will tolerate one NA value but not five (in this example). Where do you draw the line and why? If you try this even on a simple toy example I have to guess that it will lead to contradiction. It's also hard to find out if someone has already coded up your rules unless you know exactly what they all are. May 29 '19 at 17:53

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.

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.

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.

• But that causes missing values to be highly similar. There is usually little reason to assume they are all similar. So you'd probably need to make them all unique levels. IMHO this causes more trouble than it helps. May 30 '19 at 6:17
• They would be overly similar on N features that were missing + 1, which is sub-optimal, but anything that tries to assign non-similar values would essentially be equivalent to imputation, which the OP ruled out. May 30 '19 at 18:54

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.