Package elki.clustering.hierarchical
Class CLINK<O>
- java.lang.Object
-
- elki.clustering.hierarchical.SLINK<O>
-
- elki.clustering.hierarchical.CLINK<O>
-
- Type Parameters:
O
- the type of DatabaseObject the algorithm is applied on
- All Implemented Interfaces:
Algorithm
,HierarchicalClusteringAlgorithm
@Reference(authors="D. Defays", title="An Efficient Algorithm for the Complete Link Cluster Method", booktitle="The Computer Journal 20.4", url="https://doi.org/10.1093/comjnl/20.4.364", bibkey="DBLP:journals/cj/Defays77") @Alias("Defays") public class CLINK<O> extends SLINK<O>
CLINK algorithm for complete linkage.This algorithm runs in O(n²) time, and needs only O(n) memory. The results can differ from the standard algorithm in unfavorable ways, and are order-dependent (Defays: "Modifications of the labeling permit us to obtain different minimal superior ultrametric dissimilarities"). Unfortunately, the results are usually perceived to be substantially worse than the more expensive algorithms for complete linkage clustering. This arises from the fact that this algorithm has to add the new object to the existing tree in every step, instead of being able to always do the globally best merge.
Reference:
D. Defays
An Efficient Algorithm for the Complete Link Cluster Method
In: The Computer Journal 20.4- Since:
- 0.7.0
- Author:
- Erich Schubert
-
-
Nested Class Summary
Nested Classes Modifier and Type Class Description static class
CLINK.Par<O>
Parameterization class.-
Nested classes/interfaces inherited from interface elki.Algorithm
Algorithm.Utils
-
-
Method Summary
All Methods Instance Methods Concrete Methods Modifier and Type Method Description private void
clinkstep3(DBIDArrayIter i, int n, WritableDBIDDataStore pi, WritableDoubleDataStore lambda, WritableDoubleDataStore m)
Third step: Determine the values for P and Lprivate void
clinkstep4567(DBIDRef id, ArrayDBIDs ids, DBIDArrayIter it, int n, WritableDBIDDataStore pi, WritableDoubleDataStore lambda, WritableDoubleDataStore m)
Fourth to seventh step of CLINK: find best insertionprivate void
clinkstep8(DBIDRef id, DBIDArrayIter it, int n, WritableDBIDDataStore pi, WritableDoubleDataStore lambda)
Update hierarchy.protected Logging
getLogger()
Get the (static) class logger.protected void
process(DBIDRef id, ArrayDBIDs ids, DBIDArrayIter it, int n, WritableDBIDDataStore pi, WritableDoubleDataStore lambda, WritableDoubleDataStore m)
CLINK main loop, based on the SLINK main loop.-
Methods inherited from class elki.clustering.hierarchical.SLINK
convertOutput, getInputTypeRestriction, run
-
Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
-
Methods inherited from interface elki.clustering.hierarchical.HierarchicalClusteringAlgorithm
autorun
-
-
-
-
Field Detail
-
LOG
private static final Logging LOG
The logger for this class.
-
-
Method Detail
-
process
protected void process(DBIDRef id, ArrayDBIDs ids, DBIDArrayIter it, int n, WritableDBIDDataStore pi, WritableDoubleDataStore lambda, WritableDoubleDataStore m)
CLINK main loop, based on the SLINK main loop.
-
clinkstep3
private void clinkstep3(DBIDArrayIter i, int n, WritableDBIDDataStore pi, WritableDoubleDataStore lambda, WritableDoubleDataStore m)
Third step: Determine the values for P and L- Parameters:
i
- Iteratorn
- Stopping positionpi
- Pi data storelambda
- Lambda data storem
- Distance data store
-
clinkstep4567
private void clinkstep4567(DBIDRef id, ArrayDBIDs ids, DBIDArrayIter it, int n, WritableDBIDDataStore pi, WritableDoubleDataStore lambda, WritableDoubleDataStore m)
Fourth to seventh step of CLINK: find best insertion- Parameters:
id
- Current objctids
- All objectsit
- Iteratorn
- Index thresholdpi
- Parent data storelambda
- Height data storem
- Distance data store
-
clinkstep8
private void clinkstep8(DBIDRef id, DBIDArrayIter it, int n, WritableDBIDDataStore pi, WritableDoubleDataStore lambda)
Update hierarchy.- Parameters:
id
- Current objectit
- Iteratorn
- Last object to processpi
- Parent data storelambda
- Height data store
-
-