[
https://issues.apache.org/jira/browse/SPARK-5056?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=14272458#comment-14272458
]
Tomislav Milinovic commented on SPARK-5056:
-------------------------------------------
Partitioning Around Medoids (PAM) complexity of each iteration is O(k(n-k)2)
For large values of n and k, such computation becomes very costly.
Clustering Large Applications (CLARA) is fully described in chapter 3 of
Kaufman, L. and Rousseeuw, P.J. (1990) Finding Groups in Data: An Introduction
to Cluster Analysis.Wiley, New York.
Compared to other partitioning methods such as PAM, it can deal with much
larger datasets. Internally, this is achieved by considering sub-datasets of
fixed size (sampsize) such that the time and storage requirements become linear
in n rather than quadratic.
CLARA complexity of each Iteration is: O(ks2 + k(n-k))
s: the size of the sample
k: number of clusters
n: number of objects
> Implementing Clara k-medoids clustering algorithm for large datasets
> --------------------------------------------------------------------
>
> Key: SPARK-5056
> URL: https://issues.apache.org/jira/browse/SPARK-5056
> Project: Spark
> Issue Type: Improvement
> Components: MLlib
> Reporter: Tomislav Milinovic
> Priority: Minor
> Labels: features
>
> There is a specific k-medoids clustering algorithm for large datasets. The
> algorithm is called Clara in R, and is fully described in chapter 3 of
> Finding Groups in Data: An Introduction to Cluster Analysis. by Kaufman, L
> and Rousseeuw, PJ (1990).
> The algorithm considers sub-datasets of fixed size (sampsize) such that the
> time and storage requirements become linear in n rather than quadratic. Each
> sub-dataset is partitioned into k clusters using the same algorithm as in
> Partinioning around Medoids (PAM).
--
This message was sent by Atlassian JIRA
(v6.3.4#6332)
---------------------------------------------------------------------
To unsubscribe, e-mail: [email protected]
For additional commands, e-mail: [email protected]
