Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

in the area of image processing, I'm trying out different dimensionality reduction techniques. I use these to reduce intensity images/bitmaps (sliced as a vector, i.e. such a vector has a high dimensionality, e.g. 6400 for a 80x80 image) to a lower, k-dimensional space (e.g. k=12). One of these techniques is PCA, and as you know, there are many others.

Given:

  • N point clouds (i.e. a set of k-dimensional real-valued coordinates, refered to as "point")
  • Each point cloud has some number of points (e.g. n_i)
  • No knowledge about the distribution of the points for each point cloud shall be assumed (although it's probably somehow Gaussian-like distributed, but not uni-variate)

Needed: the amount of overlap of these point clouds. Or, in other words, how separable the data is. I really have no clue how intensive of a problem this is. Visually, I conceive the solution like building the k-dimensional convex hull for every point cloud, calculating the volume of total overlap.

If the distribution was just "spherical" (i.e. uni-variate Gaussian) it would be trivial, I could simply divide 'no of points that are further away from their own cloud center than 0.5*distanceToCenterOfOtherClosestPointCloud' by 'total no of points'

I'm also sorry if I should have made use of the wrong tags. I'm by no means a mathematician.

share|improve this question
    
The question is rather vague (and even your "trivial" case is not so). Some issues: the "overlap volume" of a pair of "clouds" might no be representative (the concentration of points does not matter? what if class A has a high overlap voulmen with class B, but only because of a few points?). Are we interested in pair-overlapping only? (assume class A overlaps 50% of its cloud with class B, and 50% with class C; does it matter whether it's the same half?) Here's a little paper: prasa.org/proceedings/2004/prasa04-12.pdf –  leonbloy Jul 2 '12 at 17:18
    
You're totally right, I was not clear with my question. The paper you provide is a very good start, thanks! Class separability measures being the keyword here. –  NameZero912 Jul 2 '12 at 21:30

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.