High dimensional clustering *in*the*general* case is severely hexed by this problem of orthogonality.
Many important datasets, however, contain data that does not really fill the feature space, but is instead nearly constrained to a much lower dimensional manifold. As such, clustering can be useful for these datasets. The important problem becomes how to expose the (relatively) low dimensionality of the data. Some of the approaches include spectral techniques, locally linear embedding and probabilistic modeling. Some of the high dimensional data sets that can be usefully clustered using these techniques include images, transaction histories and event logs. It is also true that for a fixed, small number of clusters you can get by very with a first pass of random sampling followed by another pass for assigning points to clusters. For non-parametric clustering such as the DP based stuff I have been talking about lately, increasing the number of data points implies an increasing and conceptually unbounded number of clusters. IF you want to learn about you data in deep detail, then these non-parametric techniques will need to look at more of the data. The beneficial effects of sampling are used in data-mining extensively. In fraud detection, for example, it is an absolutely standard first step to down-sample the non-frauds so that you have a decent sized data set. It is important, however, to not just do blind sampling but rather to stratify your sampling so that you keep a sufficient number of the rare kinds of events to characterize them. Doing that kind of sampling well inherently involves multiple passes over the data which should be very much helped by something like Mahout. On Fri, May 23, 2008 at 1:23 PM, Jeff Eastman < [EMAIL PROTECTED]> wrote: > This is an interesting point that actually came up in my data mining talk > at Yahoo! a couple of weeks back. At the time, I did not completely get the > impact of his question, but now I do. One of their senior statisticians (the > only other person in the room with any gray hair<grin>), posed this > conundrum for Mahout clustering: > > 1. Beyond 20 or so dimensions in the dataset, the "curse of dimensionality" > limits what can be reasonably gained from clustering because the data points > become so far apart in n-space. This limits the value of wide dataset > handling in Mahout. > 2. Since very large datasets can be effectively clustered using sampling > techniques (as in the above) to determine the clusters, the benefit of using > all the points for deep dataset cluster determination is also limited. > > I still do not know how to respond to it, but offer it to the list for > discussion. Of course, once the cluster centers are known, Mahout offers a > faster way to actually cluster all of the points, if this is needed for the > application. > > Jeff > -- ted
