Clustering uncertain data with independent uncertainty per dimension

Question

I have $n$ objects located in a $d$ dimensional space, however I do not know their exact coordinates. For each object and each dimension, I have a set of noisy measurements of the coordinate.

I would like to cluster this data in the

For example, with $n = 3$ and $d = 2$, I could have access to the following data:

• object $a$, dim 1: 0.8 0.7 0.6
• object $a$, dim 2: 1.0 1.0 1.0 0.9
• object $b$, dim 1: 0.4 0.3
• object $b$, dim 2: 0.2 0.1
• object $c$, dim 1: 0.9 0.6
• object $c$, dim 2: $\emptyset$

In my current approach, I take the for each (object, dimension) pair that has data the average value, and I imput the average value of the dimension for the missing data.

So I would get

• $a$ [0.7 0.975]
• $b$ [0.35 0.15]
• $c$ [0.75 0.6] (where $0.6 = \frac{1+1+1+0.9+0.2+0.1}{6}$)

Then I use the scikit-learn python library to run the mean-shift algorithm and obtain clusters.

I am not completely satisfied with this methods for two main reasons (maybe they're the same):

1. an (object, dimension) pair with a single observation is treated as as reliable as one with numerous observations
2. there is a discontinuity between how a pair with zero observations and a pair with some observations are treated. In the second case, the value of the other objects does not influence the attribute at all.

My questions are: What would be a more principled approach to this problem? If I need to use another algorithm, are there open source decent quality libraries available that would implement it?

I currently use $d = 256$ and $n = 10$ for my testing, but I aim to use $d = 16000$ and $n = 1000$ (but maybe a smaller $n$ if it's unrealistic) in my target application.

Answer 1

Model the measurement process

For each dimension you could attempt to model the distribution of the measurement process variance. Perhaps every dimension has the same measurement process or perhaps it is distinct. Combine all measurements from all dimensions if the process is the same.

If you have enough data then you can build an empirical model of the distribution of errors using perhaps a kernel based estimator.

Otherwise you might choose to use a Gaussian distribution formed from the mean value of each measurement and an overall measure of the variance of the measurement process. Then you replace observations you have with a sample drawn from a distribution with the observation mean and overall measurement process variance.

Answer 2

There are two separate issues and you should be able to combine the two following ideas to solve your problem.

Multiple measurements

What if you treat all the measurements as separate data points during the clustering and just cluster all the data together. Run your favorite clustering algorithm. Then, if one of your objects has measurements that get clustered in different clusters that will provide you with a measure of the fuzziness of the object. Assign the object to the cluster with the most measurements assigned to it.

Incomplete measurements

This one is trickier. You don't just have missing data points, but you have missing dimensions. Here is a dissertation that starts to address some of these issues. The literature review may point you in the right direction.

My initial idea would be to cluster the data sequentially in order of subspace rank. That is, first cluster all data points with similar rank d together, then use those cluster labels as the initial clustering to rank those with rank d-1, then rank d-2, etc.

Answer 3

With (d=256, n=10) as well as with (d=16000, n=1000) you are under the curse of dimensionality. The essence of the curse (quoted from Wikipedia)

nearly all of the high-dimensional space is "far away" from the centre. To put it another way, the high-dimensional unit hypercube can be said to consist almost entirely of the "corners" of the hypercube, with almost no "middle".

For an intuitive explanation I also found this

IMHO, for your problem with n=10 you can use d<=2, for n=1000 d=3 (maybe 4, at most 5). Why d=3 for n=1000? Roughly speaking this would correspond to 10 points along each dimension (10^3=1000), which is reasonable to fill the 3D space. For d=5 it is like 4 points in each dimension, which is not so good but not a disaster.

IMHO, you should try to reformulate your problem and significantly reduce dimensionality (maybe try to use SVD or PCA). This may automatically solve your problem of noisy data.