[
https://issues.apache.org/jira/browse/MATH-1371?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=15307424#comment-15307424
]
Artem Barger commented on MATH-1371:
------------------------------------
Here results of benchmarking using PerfTestUtils:
kmeans comparison (calls per timed block: 100, timed blocks: 100, time unit: ms)
|| name || time/call || std dev || total time || ratio ||
cv || difference ||
|elkan kmeans++, k=20, d=5 | 1.506e+03 | 5.3e+02 | 1.3551e+04 | 1.000 | 0.35 |
0.0000e+00 |
|elkan kmeans++, k=20, d=10| 7.130e+03 | 1.7e+03 | 6.4169e+04 | 4.735 | 0.23 |
5.0618e+04 |
|elkan kmeans++, k=20, d=20 | 1.546e+04 | 5.2e+02 | 1.3915e+05 | 10.269 | 0.03
| 1.2560e+05 |
|kmeans++, k=20, d=5 | 3.784e+03 | 2.1e+02 | 3.4054e+04 | 2.513 | 0.06 |
2.0503e+04 |
|kmeans++, k=20, d=10 | 2.212e+04 | 8.1e+03 | 1.9910e+05 | 14.692 | 0.37
| 1.8555e+05 |
|kmeans++, k=20, d=20 | 3.682e+04 | 1.7e+04 | 3.3142e+05 | 24.457 | 0.46
| 3.1787e+05 |
> Provide accelerated kmeans++ implementation
> -------------------------------------------
>
> Key: MATH-1371
> URL: https://issues.apache.org/jira/browse/MATH-1371
> Project: Commons Math
> Issue Type: Improvement
> Reporter: Artem Barger
> Assignee: Artem Barger
> Attachments: ElkanKmeansPlusPlusClusterer.java
>
>
> There is an updated version of kmeans++ algorithm available, which is
> published in: Elkan, Charles. "Using the triangle inequality to accelerate
> k-means." ICML. Vol. 3. 2003. paper.
> The main essence is to boost the kmeans iterations by avoiding computation of
> distances between centers and points when there is no need for that. For
> example after the update cluster center haven't moved too far from the point
> therefore no change in point assignment. The accelerated algorithm avoids
> unnecessary distance calculations by applying the triangle inequality in two
> different ways, and by keeping track of lower and upper bounds for distances
> between points and centers.
> Algorithm description is available in the paper.
--
This message was sent by Atlassian JIRA
(v6.3.4#6332)
