Clustering uncertain data with independent uncertainty per dimension 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):


an (object, dimension) pair with a single observation is treated as as reliable as one with numerous observations
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.
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.