Mailing-List: contact dev-help@mahout.apache.org; run by ezmlm
Precedence: bulk
Reply-To: dev@mahout.apache.org
Received-SPF: pass (athena.apache.org: domain of ted.dunning@gmail.com
 designates 209.85.210.182 as permitted sender)
MIME-Version: 1.0
In-Reply-To: 
 <CAJQdJb1-Re4mL4d8tS6xu4D=M6rNTBzS7-7yiS2_8LcPVyf4Xg@mail.gmail.com>
References: 
 <CAJQdJb1-Re4mL4d8tS6xu4D=M6rNTBzS7-7yiS2_8LcPVyf4Xg@mail.gmail.com>
From: Ted Dunning <ted.dunning@gmail.com>
Date: Fri, 29 Mar 2013 03:29:53 +0100
Message-ID: 
 <CAJwFCa1qJY3yTk75FbCR4nAKOR32M7T9zQ20dj3ZsFAuFLa+_A@mail.gmail.com>
Subject: Re: streaming k-means vs minibatch k-means
To: dev@mahout.apache.org
Content-Type: multipart/alternative; boundary=14dae934036fa5635f04d9070d70

--14dae934036fa5635f04d9070d70
Content-Type: text/plain; charset=UTF-8

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 <andy.twigg@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
>

--14dae934036fa5635f04d9070d70--