You are viewing a plain text version of this content. The canonical link for it is here.
Posted to reviews@spark.apache.org by srowen <gi...@git.apache.org> on 2016/09/04 11:50:43 UTC
[GitHub] spark pull request #14956: [SPARK-17389] [ML] [MLLIB] KMeans speedup with be...
GitHub user srowen opened a pull request:
https://github.com/apache/spark/pull/14956
[SPARK-17389] [ML] [MLLIB] KMeans speedup with better choice of k-means|| init steps = 2
## What changes were proposed in this pull request?
Reduce default k-means|| init steps to 2 from 5. See JIRA for discussion.
## How was this patch tested?
Existing tests.
You can merge this pull request into a Git repository by running:
$ git pull https://github.com/srowen/spark SPARK-17389.2
Alternatively you can review and apply these changes as the patch at:
https://github.com/apache/spark/pull/14956.patch
To close this pull request, make a commit to your master/trunk branch
with (at least) the following in the commit message:
This closes #14956
----
commit 014f26ad71f04caa9049f49a39d4dd169290b6df
Author: Sean Owen <so...@cloudera.com>
Date: 2016-09-04T11:49:58Z
Reduce default k-means|| init steps to 2 from 5 (see SPARK-17389 for discussion)
----
---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. If your project does not have this feature
enabled and wishes so, or if the feature is enabled but not working, please
contact infrastructure at infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
[GitHub] spark issue #14956: [SPARK-17389] [ML] [MLLIB] KMeans speedup with better ch...
Posted by SparkQA <gi...@git.apache.org>.
Github user SparkQA commented on the issue:
https://github.com/apache/spark/pull/14956
**[Test build #65210 has finished](https://amplab.cs.berkeley.edu/jenkins/job/SparkPullRequestBuilder/65210/consoleFull)** for PR 14956 at commit [`b5aaec9`](https://github.com/apache/spark/commit/b5aaec9a398fc4ac0754efb1e14345c3464acd49).
* This patch passes all tests.
* This patch merges cleanly.
* This patch adds no public classes.
---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. If your project does not have this feature
enabled and wishes so, or if the feature is enabled but not working, please
contact infrastructure at infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
[GitHub] spark issue #14956: [SPARK-17389] [ML] [MLLIB] KMeans speedup with better ch...
Posted by mateiz <gi...@git.apache.org>.
Github user mateiz commented on the issue:
https://github.com/apache/spark/pull/14956
Cool, then it does make sense to change it.
---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. If your project does not have this feature
enabled and wishes so, or if the feature is enabled but not working, please
contact infrastructure at infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
[GitHub] spark issue #14956: [SPARK-17389] [ML] [MLLIB] KMeans speedup with better ch...
Posted by SparkQA <gi...@git.apache.org>.
Github user SparkQA commented on the issue:
https://github.com/apache/spark/pull/14956
**[Test build #65210 has started](https://amplab.cs.berkeley.edu/jenkins/job/SparkPullRequestBuilder/65210/consoleFull)** for PR 14956 at commit [`b5aaec9`](https://github.com/apache/spark/commit/b5aaec9a398fc4ac0754efb1e14345c3464acd49).
---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. If your project does not have this feature
enabled and wishes so, or if the feature is enabled but not working, please
contact infrastructure at infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
[GitHub] spark issue #14956: [SPARK-17389] [ML] [MLLIB] KMeans speedup with better ch...
Posted by srowen <gi...@git.apache.org>.
Github user srowen commented on the issue:
https://github.com/apache/spark/pull/14956
@mateiz pardon for the ping but I think you authored the line / comment I'm changing here. See my note at https://github.com/apache/spark/pull/14948#issuecomment-244597251 -- does that logic make sense to you regarding R=2 steps instead of 5?
---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. If your project does not have this feature
enabled and wishes so, or if the feature is enabled but not working, please
contact infrastructure at infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
[GitHub] spark pull request #14956: [SPARK-17389] [ML] [MLLIB] KMeans speedup with be...
Posted by srowen <gi...@git.apache.org>.
Github user srowen closed the pull request at:
https://github.com/apache/spark/pull/14956
---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. If your project does not have this feature
enabled and wishes so, or if the feature is enabled but not working, please
contact infrastructure at infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
[GitHub] spark issue #14956: [SPARK-17389] [ML] [MLLIB] KMeans speedup with better ch...
Posted by SparkQA <gi...@git.apache.org>.
Github user SparkQA commented on the issue:
https://github.com/apache/spark/pull/14956
**[Test build #64923 has started](https://amplab.cs.berkeley.edu/jenkins/job/SparkPullRequestBuilder/64923/consoleFull)** for PR 14956 at commit [`014f26a`](https://github.com/apache/spark/commit/014f26ad71f04caa9049f49a39d4dd169290b6df).
---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. If your project does not have this feature
enabled and wishes so, or if the feature is enabled but not working, please
contact infrastructure at infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
[GitHub] spark issue #14956: [SPARK-17389] [ML] [MLLIB] KMeans speedup with better ch...
Posted by AmplabJenkins <gi...@git.apache.org>.
Github user AmplabJenkins commented on the issue:
https://github.com/apache/spark/pull/14956
Merged build finished. Test PASSed.
---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. If your project does not have this feature
enabled and wishes so, or if the feature is enabled but not working, please
contact infrastructure at infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
[GitHub] spark pull request #14956: [SPARK-17389] [ML] [MLLIB] KMeans speedup with be...
Posted by srowen <gi...@git.apache.org>.
Github user srowen commented on a diff in the pull request:
https://github.com/apache/spark/pull/14956#discussion_r78277099
--- Diff: mllib/src/main/scala/org/apache/spark/mllib/clustering/PowerIterationClustering.scala ---
@@ -395,7 +395,7 @@ object PowerIterationClustering extends Logging {
val points = v.mapValues(x => Vectors.dense(x)).cache()
val model = new KMeans()
.setK(k)
- .setSeed(0L)
+ .setSeed(5L)
--- End diff --
Sorry Matei I kind of missed your point. Yes it's a bit more strange to be changing a seed in a non-test file. Same reasoning, but I agree. There's a seed here to begin with for determinism but probably shouldn't matter.
I think I understand the problem, and I think it's the test. k-means is used to cluster 1D data. The test case generates two concentric circles of points of radius 1 and 4, which are intended to form k=2 separate clusters in the derived values that are clustered by k-means internally. That's even clear from looking at the similarities plotted:
While it's clear what the clustering is supposed to be, it's not actually the lowest-cost k-means clustering. Many clusterings do find the 'wrong' better clustering which is one that would include a few of the leftmost elements of the right group into the left one. Many other clusterings get the 'right' answer which is a big local minimum but not optimal. In fact, k-means|| init seems to do worse than random here exactly because it's less likely to find the local minimum.
I don't think the choice of radii matters here, since the resulting values above are basically invariant.
I'm going to have to read the paper more to understand what the difference is here. It's not quite the k-means change here, and, we can make this test pass easily by either
- Set seed back to 0 and fix init steps = 5 for this use of k-means, because that happens to work. Then this implementation doesn't change at all. It means it does more work just to make the test pass.
- Set seed to, say, 5 to get this to pass, on the theory that the choice of seed still doesn't seem to matter per se, and 5 is no worse than 0.
Obviously I want to understand a little more about how this is ever supposed to work in PIC, though it ends up being a slightly different issue.
---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. If your project does not have this feature
enabled and wishes so, or if the feature is enabled but not working, please
contact infrastructure at infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
[GitHub] spark issue #14956: [SPARK-17389] [ML] [MLLIB] KMeans speedup with better ch...
Posted by AmplabJenkins <gi...@git.apache.org>.
Github user AmplabJenkins commented on the issue:
https://github.com/apache/spark/pull/14956
Test PASSed.
Refer to this link for build results (access rights to CI server needed):
https://amplab.cs.berkeley.edu/jenkins//job/SparkPullRequestBuilder/65210/
Test PASSed.
---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. If your project does not have this feature
enabled and wishes so, or if the feature is enabled but not working, please
contact infrastructure at infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
[GitHub] spark issue #14956: [SPARK-17389] [ML] [MLLIB] KMeans speedup with better ch...
Posted by AmplabJenkins <gi...@git.apache.org>.
Github user AmplabJenkins commented on the issue:
https://github.com/apache/spark/pull/14956
Test PASSed.
Refer to this link for build results (access rights to CI server needed):
https://amplab.cs.berkeley.edu/jenkins//job/SparkPullRequestBuilder/64924/
Test PASSed.
---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. If your project does not have this feature
enabled and wishes so, or if the feature is enabled but not working, please
contact infrastructure at infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
[GitHub] spark issue #14956: [SPARK-17389] [ML] [MLLIB] KMeans speedup with better ch...
Posted by SparkQA <gi...@git.apache.org>.
Github user SparkQA commented on the issue:
https://github.com/apache/spark/pull/14956
**[Test build #64923 has finished](https://amplab.cs.berkeley.edu/jenkins/job/SparkPullRequestBuilder/64923/consoleFull)** for PR 14956 at commit [`014f26a`](https://github.com/apache/spark/commit/014f26ad71f04caa9049f49a39d4dd169290b6df).
* This patch **fails Spark unit tests**.
* This patch merges cleanly.
* This patch adds no public classes.
---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. If your project does not have this feature
enabled and wishes so, or if the feature is enabled but not working, please
contact infrastructure at infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
[GitHub] spark issue #14956: [SPARK-17389] [ML] [MLLIB] KMeans speedup with better ch...
Posted by AmplabJenkins <gi...@git.apache.org>.
Github user AmplabJenkins commented on the issue:
https://github.com/apache/spark/pull/14956
Merged build finished. Test FAILed.
---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. If your project does not have this feature
enabled and wishes so, or if the feature is enabled but not working, please
contact infrastructure at infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
[GitHub] spark issue #14956: [SPARK-17389] [ML] [MLLIB] KMeans speedup with better ch...
Posted by SparkQA <gi...@git.apache.org>.
Github user SparkQA commented on the issue:
https://github.com/apache/spark/pull/14956
**[Test build #64924 has finished](https://amplab.cs.berkeley.edu/jenkins/job/SparkPullRequestBuilder/64924/consoleFull)** for PR 14956 at commit [`3343acc`](https://github.com/apache/spark/commit/3343accdcf450ad1fa4f48f7d624b051c2113170).
* This patch passes all tests.
* This patch merges cleanly.
* This patch adds no public classes.
---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. If your project does not have this feature
enabled and wishes so, or if the feature is enabled but not working, please
contact infrastructure at infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
[GitHub] spark issue #14956: [SPARK-17389] [ML] [MLLIB] KMeans speedup with better ch...
Posted by AmplabJenkins <gi...@git.apache.org>.
Github user AmplabJenkins commented on the issue:
https://github.com/apache/spark/pull/14956
Test FAILed.
Refer to this link for build results (access rights to CI server needed):
https://amplab.cs.berkeley.edu/jenkins//job/SparkPullRequestBuilder/64923/
Test FAILed.
---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. If your project does not have this feature
enabled and wishes so, or if the feature is enabled but not working, please
contact infrastructure at infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
[GitHub] spark pull request #14956: [SPARK-17389] [ML] [MLLIB] KMeans speedup with be...
Posted by srowen <gi...@git.apache.org>.
Github user srowen commented on a diff in the pull request:
https://github.com/apache/spark/pull/14956#discussion_r77880357
--- Diff: mllib/src/main/scala/org/apache/spark/mllib/clustering/PowerIterationClustering.scala ---
@@ -395,7 +395,7 @@ object PowerIterationClustering extends Logging {
val points = v.mapValues(x => Vectors.dense(x)).cache()
val model = new KMeans()
.setK(k)
- .setSeed(0L)
+ .setSeed(5L)
--- End diff --
The desired test result here depends on the seed, since some random initializations don't happen to produce the clustering that the test has in mind. 0 no longer worked after the change above but 5 did. This does indicate the clustering is different. Yes that sounds like a good quick science experiment, to verify more empirically that the clustering results here match what the paper advertises.
---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. If your project does not have this feature
enabled and wishes so, or if the feature is enabled but not working, please
contact infrastructure at infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
[GitHub] spark issue #14956: [SPARK-17389] [ML] [MLLIB] KMeans speedup with better ch...
Posted by SparkQA <gi...@git.apache.org>.
Github user SparkQA commented on the issue:
https://github.com/apache/spark/pull/14956
**[Test build #64924 has started](https://amplab.cs.berkeley.edu/jenkins/job/SparkPullRequestBuilder/64924/consoleFull)** for PR 14956 at commit [`3343acc`](https://github.com/apache/spark/commit/3343accdcf450ad1fa4f48f7d624b051c2113170).
---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. If your project does not have this feature
enabled and wishes so, or if the feature is enabled but not working, please
contact infrastructure at infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
[GitHub] spark pull request #14956: [SPARK-17389] [ML] [MLLIB] KMeans speedup with be...
Posted by mateiz <gi...@git.apache.org>.
Github user mateiz commented on a diff in the pull request:
https://github.com/apache/spark/pull/14956#discussion_r78270573
--- Diff: mllib/src/main/scala/org/apache/spark/mllib/clustering/PowerIterationClustering.scala ---
@@ -395,7 +395,7 @@ object PowerIterationClustering extends Logging {
val points = v.mapValues(x => Vectors.dense(x)).cache()
val model = new KMeans()
.setK(k)
- .setSeed(0L)
+ .setSeed(5L)
--- End diff --
Wait, but I don't get it, is this a test? This seems to be changing the main Power Iteration Clustering file. For the tests, we usually created data with very obvious clusterings where nearly any initialization would find the right thing. You should look over whichever test is failing without this change.
---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. If your project does not have this feature
enabled and wishes so, or if the feature is enabled but not working, please
contact infrastructure at infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
[GitHub] spark pull request #14956: [SPARK-17389] [ML] [MLLIB] KMeans speedup with be...
Posted by mateiz <gi...@git.apache.org>.
Github user mateiz commented on a diff in the pull request:
https://github.com/apache/spark/pull/14956#discussion_r77874667
--- Diff: mllib/src/main/scala/org/apache/spark/mllib/clustering/PowerIterationClustering.scala ---
@@ -395,7 +395,7 @@ object PowerIterationClustering extends Logging {
val points = v.mapValues(x => Vectors.dense(x)).cache()
val model = new KMeans()
.setK(k)
- .setSeed(0L)
+ .setSeed(5L)
--- End diff --
Why change this?
---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. If your project does not have this feature
enabled and wishes so, or if the feature is enabled but not working, please
contact infrastructure at infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
[GitHub] spark issue #14956: [SPARK-17389] [ML] [MLLIB] KMeans speedup with better ch...
Posted by AmplabJenkins <gi...@git.apache.org>.
Github user AmplabJenkins commented on the issue:
https://github.com/apache/spark/pull/14956
Merged build finished. Test PASSed.
---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. If your project does not have this feature
enabled and wishes so, or if the feature is enabled but not working, please
contact infrastructure at infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
[GitHub] spark pull request #14956: [SPARK-17389] [ML] [MLLIB] KMeans speedup with be...
Posted by srowen <gi...@git.apache.org>.
Github user srowen commented on a diff in the pull request:
https://github.com/apache/spark/pull/14956#discussion_r78273585
--- Diff: mllib/src/main/scala/org/apache/spark/mllib/clustering/PowerIterationClustering.scala ---
@@ -395,7 +395,7 @@ object PowerIterationClustering extends Logging {
val points = v.mapValues(x => Vectors.dense(x)).cache()
val model = new KMeans()
.setK(k)
- .setSeed(0L)
+ .setSeed(5L)
--- End diff --
Power iteration clustering uses k-means as an internal step, which is why the change affects PIC and its test. You're right, really a test should assert something that is true no matter how the implementation behaves. It'll probably never work for 100% of seeds though I agree, it should work for most. It worked for, I think, the third seed I tried. Maybe those odds are too low. Let me look into what goes wrong with seed 0 and see if it implies that something should be improved about the test or impl.
---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. If your project does not have this feature
enabled and wishes so, or if the feature is enabled but not working, please
contact infrastructure at infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
[GitHub] spark issue #14956: [SPARK-17389] [ML] [MLLIB] KMeans speedup with better ch...
Posted by mateiz <gi...@git.apache.org>.
Github user mateiz commented on the issue:
https://github.com/apache/spark/pull/14956
I think the number 5 is indeed from that paper (I think from figure 5.1 actually), but have you tested the effect of using R=2 empirically? It would be good to check that they match what's in the paper.
---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. If your project does not have this feature
enabled and wishes so, or if the feature is enabled but not working, please
contact infrastructure at infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
[GitHub] spark issue #14956: [SPARK-17389] [ML] [MLLIB] KMeans speedup with better ch...
Posted by mateiz <gi...@git.apache.org>.
Github user mateiz commented on the issue:
https://github.com/apache/spark/pull/14956
Cool, thanks for improving the PIC test.
---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. If your project does not have this feature
enabled and wishes so, or if the feature is enabled but not working, please
contact infrastructure at infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
[GitHub] spark issue #14956: [SPARK-17389] [ML] [MLLIB] KMeans speedup with better ch...
Posted by srowen <gi...@git.apache.org>.
Github user srowen commented on the issue:
https://github.com/apache/spark/pull/14956
Merged to master
---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. If your project does not have this feature
enabled and wishes so, or if the feature is enabled but not working, please
contact infrastructure at infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
[GitHub] spark pull request #14956: [SPARK-17389] [ML] [MLLIB] KMeans speedup with be...
Posted by srowen <gi...@git.apache.org>.
Github user srowen commented on a diff in the pull request:
https://github.com/apache/spark/pull/14956#discussion_r78277526
--- Diff: mllib/src/main/scala/org/apache/spark/mllib/clustering/PowerIterationClustering.scala ---
@@ -395,7 +395,7 @@ object PowerIterationClustering extends Logging {
val points = v.mapValues(x => Vectors.dense(x)).cache()
val model = new KMeans()
.setK(k)
- .setSeed(0L)
+ .setSeed(5L)
--- End diff --
I got the tests to pass reliably by simply making the two sets of points generated in this test both contain 10 points, not 10 and 40. Balancing them made the issue go away.
As to why the paper 'works', I'm actually not clear it does. It does not actually just k-means cluster the values. They say they run 100 clusterings and take the most common cluster assignment. It's a little ambiguous what this means, but may be the source of difference. AFAICT the current PIC test does present a situation that PIC clustering won't get right, often, if it uses straight k-means internally.
---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. If your project does not have this feature
enabled and wishes so, or if the feature is enabled but not working, please
contact infrastructure at infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
[GitHub] spark issue #14956: [SPARK-17389] [ML] [MLLIB] KMeans speedup with better ch...
Posted by srowen <gi...@git.apache.org>.
Github user srowen commented on the issue:
https://github.com/apache/spark/pull/14956
@mateiz I was able to reproduce the result in Figure 5.3 very closely (Spambase data set) and the result in Figure 5.2 pretty closely (mixture of Gaussians). In each case it seems like the final cost doesn't change much after 2 init steps. I didn't find as much of a jump in cost for 1 init step in mixture of Gaussians, but otherwise it matched well in terms of the log10 of sum of squares cost reported in the paper vs the implementation. (I have code if anyone cares.)
For example here's number of steps vs log10 of cost for...
k=20
1 7.344
2 7.404
3 7.401
4 7.389
5 7.396
6 7.423
7 7.374
8 7.442
9 7.402
10 7.345
k=50
1 6.940
2 6.817
3 6.831
4 6.798
5 6.888
6 6.803
7 6.838
8 6.815
9 6.818
10 6.804
k=100
1 6.663
2 6.359
3 6.400
4 6.345
5 6.397
6 6.407
7 6.367
8 6.452
9 6.368
10 6.413
---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. If your project does not have this feature
enabled and wishes so, or if the feature is enabled but not working, please
contact infrastructure at infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org