Package elki.clustering.kmedoids
Class FastPAM1<O>
- java.lang.Object
-
- elki.clustering.kmedoids.PAM<O>
-
- elki.clustering.kmedoids.FastPAM1<O>
-
- Type Parameters:
O
- vector datatype
- All Implemented Interfaces:
Algorithm
,ClusteringAlgorithm<Clustering<MedoidModel>>
,KMedoidsClustering<O>
- Direct Known Subclasses:
FastPAM
@Reference(authors="Erich Schubert, Peter J. Rousseeuw", title="Faster k-Medoids Clustering: Improving the PAM, CLARA, and CLARANS Algorithms", booktitle="Proc. 12th Int. Conf. Similarity Search and Applications (SISAP\'2019)", url="https://doi.org/10.1007/978-3-030-32047-8_16", bibkey="DBLP:conf/sisap/SchubertR19") @Priority(-100) public class FastPAM1<O> extends PAM<O>
FastPAM1: A version of PAM that is O(k) times faster, i.e., now in O((n-k)²). The change here feels pretty small - we handle all k medoids in parallel using an array. But this means the innermost loop only gets executed in O(1/k) of all iterations, and thus we benefit on average.This acceleration gives exactly (assuming perfect numerical accuracy) the same results as the original PAM. For further improvements that can affect the result, see also
FastPAM
, which is recommended for usage in practice.Reference:
Erich Schubert, Peter J. Rousseeuw
Faster k-Medoids Clustering: Improving the PAM, CLARA, and CLARANS Algorithms
Proc. 12th Int. Conf. Similarity Search and Applications (SISAP'2019)- Since:
- 0.7.5
- Author:
- Erich Schubert
-
-
Nested Class Summary
Nested Classes Modifier and Type Class Description protected static class
FastPAM1.Instance
Instance for a single dataset.static class
FastPAM1.Par<V>
Parameterization class.-
Nested classes/interfaces inherited from interface elki.Algorithm
Algorithm.Utils
-
-
Constructor Summary
Constructors Constructor Description FastPAM1(Distance<? super O> distance, int k, int maxiter, KMedoidsInitialization<O> initializer)
Constructor.
-
Method Summary
All Methods Instance Methods Concrete Methods Modifier and Type Method Description protected Logging
getLogger()
Get the static class logger.Clustering<MedoidModel>
run(Relation<O> relation, int k, DistanceQuery<? super O> distQ)
Run k-medoids clustering with a given distance query.
Not a very elegant API, but needed for some types of nested k-medoids.-
Methods inherited from class elki.clustering.kmedoids.PAM
getInputTypeRestriction, initialMedoids, run, wrapResult
-
Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
-
Methods inherited from interface elki.clustering.ClusteringAlgorithm
autorun
-
-
-
-
Field Detail
-
LOG
private static final Logging LOG
The logger for this class.
-
KEY
private static final java.lang.String KEY
Key for statistics logging.
-
-
Constructor Detail
-
FastPAM1
public FastPAM1(Distance<? super O> distance, int k, int maxiter, KMedoidsInitialization<O> initializer)
Constructor.- Parameters:
distance
- distance functionk
- k parametermaxiter
- Maxiter parameterinitializer
- Function to generate the initial means
-
-
Method Detail
-
run
public Clustering<MedoidModel> run(Relation<O> relation, int k, DistanceQuery<? super O> distQ)
Description copied from interface:KMedoidsClustering
Run k-medoids clustering with a given distance query.
Not a very elegant API, but needed for some types of nested k-medoids.
-
-