I have n vectors with m features and also a weight vector with n elements. I'd like to reduce the number of n vectors in a way that the probability distributions of the m (weighted) features (across the n vectors) are maintained (or "least" affected).

2 Vectors can be collapsed into 1 by weight averaging their m features with each of the vector's weights (the resulting weight is the sum of the two vector's weights).

m is in the range of 2..5, n can be up to 500. The distributions of the features are unknown and different for each feature.

I would require a distance measure for two probability distributions (not sure if some combination of variance and mean is sufficient) and a smart way of selecting the two candidate vectors to merge.

At the moment I am using a Euclidian distance measure and merge the smallest weight's vector with the closest (wrt. distance measure) other vector. There is no check of whether or not the distributions are maintained (just followed intuition).

Are there any established methods to do what I describe or any keywords I could follow up on? Any help or comments are appreciated.


I may have found ways to measure the distance between two probability distributions (the original distribution and the distribution from reducing the data points).

I am unsure of which one to choose though.

  • $\begingroup$ What's wrong with weighted random sampling, besides merging similar objects? Also 500 is tiny. $\endgroup$ Apr 28 '16 at 7:04
  • $\begingroup$ All objects are used in the end. Sampling doesn't work as it would potentially sample the same object twice (which wouldn't be allowed). Essentially the weighted average of m and the sum of weights has to be preserved by whatever data reduction transformation is applied. $\endgroup$
    – orange
    Apr 28 '16 at 8:24
  • $\begingroup$ I'm glad to hear that 500 is tiny ;-) $\endgroup$
    – orange
    Apr 28 '16 at 8:25
  • $\begingroup$ Well, you could sample without replacement (but that still won't have your other criterions). Try to be explicit about your requirements. Preserving the global weighted averages exactly is a restriction. Also, apparently your vectors are probability distributions, i.e. every vector has a sum of 1? $\endgroup$ Apr 28 '16 at 9:14
  • $\begingroup$ Across all vectors n, for each feature dimension in m you can plot a distribution in a histogram, but the values don't sum to 1 (neither do the n weights for each vector). $\endgroup$
    – orange
    Apr 28 '16 at 9:48

Treat it as an optimization problem.

What do you want to optimize? You want to merge objects by taking the weighted average, i.e. $z_i=(w_{xi}\cdot x_i+w_{yi}\cdot y_i)/(w_{xi}+w_{yi})$; and $w_{zi}=w_{xi}+w_{yi}$ I assume? Because that will preserve the global averages and weight sum (see comments on the question).

So define a criterion on what is a good merge. Absolute error? Squared error?

The absolute error is probably smallest by weighted Manhattan distance. The squared error is probably smallest by weighted Euclidean distance. So if you write down your objective, you may directly end up with a distance measure to use. Then you can repeatedly perform the best merge (= single-linkage hierarchical clustering) until the desired number of vectors remain.

  • $\begingroup$ Good recommendation re optimisation problem (you're spot on with your assumptions). However, what's the error/distance here? Any merge would result in a larger "error". I could express the max. error as a constraint of this problem, but still it's unclear what the actual error is. $\endgroup$
    – orange
    Apr 28 '16 at 9:54
  • $\begingroup$ Ideally, I would find a solution with the lowest error, given a maximal | n |, i.e. specifying the allowed number object (or the "degree of merging") $\endgroup$
    – orange
    Apr 28 '16 at 9:56
  • 1
    $\begingroup$ This is related to William Dumouchel's "Data Squashing" algorithm. $\endgroup$ Apr 28 '16 at 11:38
  • $\begingroup$ @orange that depends on your problem. It could be e.g. the relative error in each bin (i.e. average deviation from the original to the aggregated value) or the square of that value. Of course weighted. But there is no general rule on which is better or "correct"; it is use case dependent. $\endgroup$ Apr 28 '16 at 11:55

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.