You are viewing a plain text version of this content. The canonical link for it is here.
Posted to dev@mahout.apache.org by Andy Twigg <an...@gmail.com> on 2013/03/28 22:30:27 UTC

streaming k-means vs minibatch k-means

Dan/Ted:

I like that you are implementing streaming k-means.

Are there any results comparing it to mini batch k-means ([1] and the
paper cited therein) ?

In the distributed implementation, you independently compute a
O(k)-means clustering on each partition, then combine them into a
final k-means. Are there any guarantees/results about the accuracy of
this? Clearly this sort of design also favours a storm/spark
implementation - have you considered that?

-Andy



[1] http://scikit-learn.org/dev/modules/generated/sklearn.cluster.MiniBatchKMeans.html

Re: streaming k-means vs minibatch k-means

Posted by Ted Dunning <te...@gmail.com>.
I think (casually, informally) that the guarantees are preserved by simple
ordering arguments.  The argument goes that the threshold on partitions
will grow less than if the partitions were handled sequentially.  Thus the
partial sketches should have at least as much fidelity than if the same
segment were before other segments.  Secondly, the total number of sketch
clusters \kappa in M sketches across N points is

   \kappa > k log N for the sequential case

and

    \kappa > M ( k log N/M ) = M k log N - M k log M

But M << N so log N > log M. M >= 2 and M < sqrt(N) then

    \kappa > M ( k log N/M ) = M k log N - M k log M >= M/2 k log N > k log
N

if M = 1, the bound becomes equality (whew)

This is a pretty reasonable constraint (i.e use less than 1000 mappers on
1e6 points and less than 10,000 mappers on 1e9 points).

Thus the map-reduce sketch is commonly more detailed in both senses for
common cases (smaller threshold, more sketch centroids).  This should
result in as good or better theoretic results.


On Thu, Mar 28, 2013 at 10:30 PM, Andy Twigg <an...@gmail.com> wrote:

> Dan/Ted:
>
> I like that you are implementing streaming k-means.
>
> Are there any results comparing it to mini batch k-means ([1] and the
> paper cited therein) ?
>
> In the distributed implementation, you independently compute a
> O(k)-means clustering on each partition, then combine them into a
> final k-means. Are there any guarantees/results about the accuracy of
> this? Clearly this sort of design also favours a storm/spark
> implementation - have you considered that?
>
> -Andy
>
>
>
> [1]
> http://scikit-learn.org/dev/modules/generated/sklearn.cluster.MiniBatchKMeans.html
>

Re: streaming k-means vs minibatch k-means

Posted by Dan Filimon <da...@gmail.com>.
On Thu, Mar 28, 2013 at 11:30 PM, Andy Twigg <an...@gmail.com> wrote:

> Dan/Ted:
>
> I like that you are implementing streaming k-means.
>

Thanks!


>
> Are there any results comparing it to mini batch k-means ([1] and the
> paper cited therein) ?
>

I haven't read the mini batch k-means paper. It'll be nice to have as soon
the quirks are worked out. And there seem to be some left right now. I
think we should do definitely the comparison when it's done.


> In the distributed implementation, you independently compute a
> O(k)-means clustering on each partition, then combine them into a
> final k-means. Are there any guarantees/results about the accuracy of
> this? Clearly this sort of design also favours a storm/spark
> implementation - have you considered that?
>

So there's an O(k log n) clustering on each partition and that is supposed
to offer *some* guarantees. I don't fully understand the math behind it so
I can't comment further. Ted?

For now, I'd like to get the Hadoop version committed. I've heard really
positive things about Spark but haven't tried it.

The key constraint being that getting a high-quality implementation and
evaluating it doubles as my senior project. Depending on how much longer
this implementation takes, I'll say maybe to a Spark version. I think the
comparison would definitely be interesting. :)


> -Andy
>
>
>
> [1]
> http://scikit-learn.org/dev/modules/generated/sklearn.cluster.MiniBatchKMeans.html
>