Mailing-List: contact user-help@hadoop.apache.org; run by ezmlm
Precedence: bulk
Reply-To: user@hadoop.apache.org
Received-SPF: pass (nike.apache.org: domain of josh.wills@gmail.com designates
 209.85.215.48 as permitted sender)
MIME-Version: 1.0
In-Reply-To: <22C27BA5-A2E2-43BF-B1F9-6ED942A4C6CE@gmail.com>
References: 
 <CAKj4Onyp7HmYAB_S2J+Debpsr8cU9KcYhnpSP=YFRhhVjcRjgg@mail.gmail.com>
 <CAOcnVr0b6ZKQpsegPLatjBiG97Kp=zOUWfVz=PniP6SfRGbPpQ@mail.gmail.com>
 <CAND0qzs9=s_F=Z16pUv8yj6Eo4LcVKshdsQCt3v2fqNLG0e6xg@mail.gmail.com>
 <22C27BA5-A2E2-43BF-B1F9-6ED942A4C6CE@gmail.com>
From: Josh Wills <josh.wills@gmail.com>
Date: Tue, 2 Apr 2013 18:03:40 -0700
Message-ID: 
 <CANb5z2L2v2W0f9xxmq6aGg1XR2vWA_=qERwPTcJ-OhFC__x7YA@mail.gmail.com>
Subject: =?ISO-8859-1?Q?Re=3A_Na=EFve_k=2Dmeans_using_hadoop?=
To: user@hadoop.apache.org
Content-Type: multipart/alternative; boundary=14dae94732cbf2703004d96a6d1d

--14dae94732cbf2703004d96a6d1d
Content-Type: text/plain; charset=ISO-8859-1

A couple of folks pointed me to this thread to ask if I had lifted the
k-means algorithm in ML from Mahout's implementation. For the record, I did
not; the implementation in ML is based on the iterative k-means|| algorithm
described in Bahmani et al. (2012):

http://arxiv.org/abs/1203.6402

whereas the Mahout impl (MAHOUT-1154) is based on the single-pass algorithm
described in Shindler et al. (2011):

http://books.nips.cc/papers/files/nips24/NIPS2011_1271.pdf

For what it's worth, I point this out in the original blog post:

http://blog.cloudera.com/blog/2013/03/cloudera_ml_data_science_tools/

Also for what it's worth, I'm eager to try out the single-pass k-means
algorithm as soon as it's actually committed to Mahout and the 0.8 release
comes out; my primary interest is in helping people choose good values of K
building on the kind of data sketching techniques outlined in these
algorithms.

Submitting ML to Mahout didn't seem like a great idea, given that it would
have added a dependency on Crunch from Mahout. The Crunch project spends a
fair amount of time doing battle with dependency conflicts, and I wouldn't
want to make that situation any worse for another project, esp. by doing it
via an unsolicited and massive patch.

J


On Wed, Mar 27, 2013 at 10:37 AM, Mark Miller <markrmiller@gmail.com> wrote:

>
> On Mar 27, 2013, at 12:47 PM, Ted Dunning <tdunning@maprtech.com> wrote:
>
> > And, of course, due credit should be given here.  The advanced
> clustering algorithms in Crunch were lifted from the new stuff in Mahout
> pretty much step for step.
> >
> > The Mahout group would have loved to have contributions from the
> Cloudera guys instead of re-implementation, but you can't legislate taste.
> >
>
> LOL - that's so ironic that I had to check my Calendar. Nope, not quite
> April 1st yet ;)
>
> Made my day.
>
> - Mark

--14dae94732cbf2703004d96a6d1d
Content-Type: text/html; charset=ISO-8859-1
Content-Transfer-Encoding: quoted-printable

<div dir=3D"ltr">A couple of folks pointed me to this thread to ask if I ha=
d lifted the k-means algorithm in ML from Mahout&#39;s implementation. For =
the record, I did not; the implementation in ML is based on the iterative k=
-means|| algorithm described in Bahmani et al. (2012):<div>

<br><div><a href=3D"http://arxiv.org/abs/1203.6402">http://arxiv.org/abs/12=
03.6402</a><br></div><div><br><div>whereas the Mahout impl (MAHOUT-1154) is=
 based on the single-pass algorithm described in Shindler et al. (2011):</d=
iv>

<div><br></div><div><a href=3D"http://books.nips.cc/papers/files/nips24/NIP=
S2011_1271.pdf">http://books.nips.cc/papers/files/nips24/NIPS2011_1271.pdf<=
/a><br></div><div><br></div><div>For what it&#39;s worth, I point this out =
in the original blog post:</div>

<div><br></div><div><a href=3D"http://blog.cloudera.com/blog/2013/03/cloude=
ra_ml_data_science_tools/">http://blog.cloudera.com/blog/2013/03/cloudera_m=
l_data_science_tools/</a><br></div></div></div><div><br></div><div>Also for=
 what it&#39;s worth, I&#39;m eager to try out the single-pass k-means algo=
rithm as soon as it&#39;s actually committed to Mahout and the 0.8 release =
comes out; my primary interest is in helping people choose good values of K=
 building on the kind of data sketching techniques outlined in these algori=
thms.</div>

<div><br></div><div>Submitting ML to Mahout didn&#39;t seem like a great id=
ea, given that it would have added a dependency on Crunch from Mahout. The =
Crunch project spends a fair amount of time doing battle with dependency co=
nflicts, and I wouldn&#39;t want to make that situation any worse for anoth=
er project, esp. by doing it via an unsolicited and massive patch.</div>

<div><br></div><div>J</div></div><div class=3D"gmail_extra"><br><br><div cl=
ass=3D"gmail_quote">On Wed, Mar 27, 2013 at 10:37 AM, Mark Miller <span dir=
=3D"ltr">&lt;<a href=3D"mailto:markrmiller@gmail.com" target=3D"_blank">mar=
krmiller@gmail.com</a>&gt;</span> wrote:<br>

<blockquote class=3D"gmail_quote" style=3D"margin:0 0 0 .8ex;border-left:1p=
x #ccc solid;padding-left:1ex"><div class=3D"im"><br>
On Mar 27, 2013, at 12:47 PM, Ted Dunning &lt;<a href=3D"mailto:tdunning@ma=
prtech.com">tdunning@maprtech.com</a>&gt; wrote:<br>
<br>
&gt; And, of course, due credit should be given here. =A0The advanced clust=
ering algorithms in Crunch were lifted from the new stuff in Mahout pretty =
much step for step.<br>
&gt;<br>
&gt; The Mahout group would have loved to have contributions from the Cloud=
era guys instead of re-implementation, but you can&#39;t legislate taste.<b=
r>
&gt;<br>
<br>
</div>LOL - that&#39;s so ironic that I had to check my Calendar. Nope, not=
 quite April 1st yet ;)<br>
<br>
Made my day.<br>
<span class=3D"HOEnZb"><font color=3D"#888888"><br>
- Mark</font></span></blockquote></div><br></div>

--14dae94732cbf2703004d96a6d1d--