3 ms·

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

by pacala 14y ago

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.

arjunnarayan 14y ago
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.
- tveita 14y ago
  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.
pangram 14y ago
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.
mokus 14y ago
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.

by pacala 14y ago

arjunnarayan 14y ago

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.

tveita 14y ago
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.

pangram 14y ago

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.

mokus 14y ago

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.