6
$\begingroup$

Many clustering algorithms can be used with big data, eg. versions of KMeans, DBSCAN based on Hadoop, etc. But, with k means we will get k centroids for k clusters and we can map them to the space and somehow understand the results. But what about density based algorithms like DBSCAN? In DBSCAN we'll get m clusters containing millions and billions of data points in case of big-data.

How do we try to understand the results of such clusterings?

Clustering more data is costly and also meaningless if we don't understand each cluster.

$\endgroup$

2 Answers 2

3
$\begingroup$

Are you sure that clustering big data is actually used anywhere?

As far as I can tell, it is not used. Everybody uses classification, nobody uses clustering. Because the clustering problem is much harder, and will require manual analysis of the results.

K-means: the usual Lloyd algorithm is naive parallel, and thus trivial to implement on Hadoop. But at the same time, it does not make sense to use k-means on big data. The reason is simple: there is no dense vector big data. K-means works well for say up to 10 dimensions. With double precision, I need 80 bytes per record then. A modest computer with 1 GB of RAM can then already fit some 13 million vectors into main memory. I have machines with 128 GB of RAM...

So you will have a hard time coming up with a real data set where:

  • I run out of memory on a single computer.
  • k-means produces notable results. (On high dimensional data, k-means is usually only as effective as random voronoi partitions!)
  • the result improves over a sample.

The last point is important: k-means computes means. The quality of a mean does not infinitely improve when you add more data. You only get marginal changes (if the result is stable, i.e. k-means worked). Most likely, your distributed computation already lost more precision on the way than you gain in the end...

Now for DBSCAN: I'm not aware of a popular distributed implementation. Every now and then a new parallel DBSCAN is proposed, usually using grids, but I've never seen one being used in practise or publicly available. Again, there are problems with the availability of interesting data where it would make sense to use DBSCAN.

  • For big data, how do you set the minPts and epsilon parameters? If you get this wrong, you won't have any clusters; or everything will be a single large custer.
  • If your data is low-dimensional, see above for k-means. Using techniques such as R*-trees and grids, a single computer can already cluster low-dimensional data with billions of points using DBSCAN.
  • If you have complex data, where indexing no longer works, DBSCAN will scale quadratically and thus be an inappropriate choice for big data.

Many platforms/companies like to pretend they can reasonably run k-means on their cluster. But fact is, it does not make sense this way, and its just maketing and tech demo. That is why they usually use random data to show off, or the dreaded broken KDDCup1999 data set (which I still can cluster faster on a single computer than on any Hadoop cluster!).

So what is really done in practise

  • The Hadoop cluster is your data warehouse (rebranded as fancy new big data).
  • You run distributed preprocessing on your raw data, to massage it into shape.
  • The preprocessed data is small enough to be clustered on a single computer, with more advanced algorithms (that may even scale quadratic, and do not have to be naive parallel)
  • You sell it to your marketing department
  • Your marketing department sells it to the CSomethingO.
  • Everybody is happy, because they are now big data experts.
$\endgroup$
7
  • $\begingroup$ You do understand that not every clustering algorithm is k-means, right? Also, what you mean by "there is no dense vector big data"? You can easily have a huge collection of dense vectors! $\endgroup$
    – iliasfl
    Feb 6, 2014 at 9:20
  • $\begingroup$ Well, I wonder how do you want to get enough data to train a classifier and then classify big data. Besides, what you told about minPts and epsilon actually exist in every context of AI. Whatever you want to use has its own parameters. To gain big data is not a problem. I strongly believe if there was no use for clustering in big data, Mahout won't come up with a clustering library. You are just cleaning the question itself. I'm exactly looking for the Manual Analysis part of the clustering. $\endgroup$
    – Mehraban
    Feb 6, 2014 at 9:23
  • $\begingroup$ @SAM Well, in machine learning, you do have training data to perform a grid search for these parameters. You cannot do this in cluster analysis... but yes, for learning you need training data. If you don't have big training data, you cannot do big data machine learning, but only learn on small data. But if you consider typical recommender systems or computer vision, you do have big labeled training data there, actually. $\endgroup$ Feb 6, 2014 at 9:44
  • $\begingroup$ @iliasfl prove me wrong. Where is big dense non-random numerical data? Show me the applications that really use clustering on dense big data and do not follow the pattern I outlined at the bottom. News aggregation is IMHO something different, and clearly not dense. $\endgroup$ Feb 6, 2014 at 9:46
  • $\begingroup$ @Anony-Mousse What you told about recommender systsms or computer vision is not general. Also recommender systems are not supervised necessarily. $\endgroup$
    – Mehraban
    Feb 6, 2014 at 9:54
2
$\begingroup$

It is not true that we need to understand the clusters in every application. Actually if you have few well established clusters, probably you will soon end up doing some supervised learning rather than clustering: do the clustering of choice, check results, assign labels to cluster members, train using a supervised method based on the assigned labels.

I can give you a simple example where number of clusters can be huge and still useful: Grouping of similar news stories or tweets. For example, in a web site we want to provide links from a news story to other similar stories. This requires finding similar news, i.e. the cluster where each news story belongs, without necessarily needing to assign "labels" to each cluster.

$\endgroup$
5
  • $\begingroup$ Your recommender system example is very good. But it doesn't fit for every problem. My question is, in case we need to understand what is representing a cluster, what should we do? $\endgroup$
    – Mehraban
    Feb 6, 2014 at 7:37
  • $\begingroup$ You can't really understand what's inside each cluster, by just examining them. What you expect is that every cluster will have "similar" samples. Similar as defined by the similarity/distance metric you use. $\endgroup$
    – iliasfl
    Feb 6, 2014 at 9:12
  • $\begingroup$ Similarity measure is somehow meaningless for reachable or connected points of data. The border elements could be far away and see them together (just them and nothing else) doesn't make much sense. $\endgroup$
    – Mehraban
    Feb 6, 2014 at 9:26
  • $\begingroup$ Hehe, I think you need first to understand that clustering itself is ill-defined altogether. I suggest reading the work of Prof. Shai Ben-David on the theoretical foundation of clustering. $\endgroup$
    – iliasfl
    Feb 6, 2014 at 9:35
  • $\begingroup$ You mean this? $\endgroup$
    – Mehraban
    Feb 6, 2014 at 9:45

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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