News for hackers. Stuff that matters.
Re:Curse of dimensionality by pacala on Wednesday May 30, 2012 @10:24PM (#4045983)
Why not cluster one dimension at a time? K-means will meaningfully cluster for 2 of these dimensions and fail for the other 998. Measure how good the separation is and stick with the best X dimensions.
Re:Curse of dimensionality by mokus on Thursday May 31, 2012 @08:02AM (#4047554)
The problem is that in many dimensions that often just won't work. The cloud of points can be smeared in directions that don't line up with any axes, in such a way that no matter which 2 axes you choose the clusters will overlap (but choosing a plane that doesn't align with any axis will clearly separate them). Even in 3 dimensions, you can see this problem by considering your populations to lie on 2 parallel planes, x+y+z=1 and x+y+z=2. Looking at this in x-y, x-z, or y-z projections, the point clouds will often be inseparable. And yet if you know where to look, all it takes is a projection to one dimension (f(x,y,z) = x+y+z) to separate them cleanly.

The curse of dimensionality appears here in the fact that the "number" of possible ways of projecting the space increases dramatically with the dimension.

Re:Curse of dimensionality by pangram on Thursday May 31, 2012 @12:09AM (#4046318)
There are a variety of techniques to reduce the dimensionality of data (i.e., Principal Component Analysis, among other ways), and you can get better results sometimes by running K-means (or whatever) on the dimensionally-reduced data.
Re:Curse of dimensionality by arjunnarayan on Wednesday May 30, 2012 @11:27PM (#4046199)
Yes that will work. But, there are 1000C2 such combinations (that is, O(2^n)), and you have to try them all since you don't know which two dimensions are needed. And you cannot do each of the 100 separately in one-dimension and later hope to "combine" them together. In fact, you might not even know that it is 2 of the dimensions that are special. Maybe it is 7. So you have to try each of the 2^100 combinations separately. The algorithm you propose is not polynomial in the number of features.
Re:Curse of dimensionality by tveita on Thursday May 31, 2012 @06:09AM (#4047263)
I may be misunderstanding you, but the number of ways to pick 2 out of n dimensions is Θ(n²).

Even if we looked at up to d dimensions, (bruteforceable at Θ(n^d)), that doesn't imply we need to generalize to do all 1000.

The post you replied to actually suggested clustering just one dimension at a time. I think that's a reasonable solution given the situation you posited, where you have some dimensions that do cluster well, even individually, and some who are mostly noise.

I would say that the curse of dimensionality is more fundamental than the problem you describe. The problem doesn't lie just in separating noise from signal - in a truly high-dimensional space there may not be a "right angle" to see it from.

For a simple example, you may take randomly distributed points. Even at uniform random distribution, it is relatively easy to for instance index two dimensional points in such a way that you can later locate points that are close to any particular spot. For 20-dimensional points, this is very hard.