Package elki.clustering.hierarchical
Class SLINK<O>
- java.lang.Object
-
- elki.clustering.hierarchical.SLINK<O>
-
- Type Parameters:
O
- the type of DatabaseObject the algorithm is applied on
- All Implemented Interfaces:
Algorithm
,HierarchicalClusteringAlgorithm
- Direct Known Subclasses:
CLINK
@Title("SLINK: Single Link Clustering") @Description("Hierarchical clustering algorithm based on single-link connectivity.") @Reference(authors="R. Sibson", title="SLINK: An optimally efficient algorithm for the single-link cluster method", booktitle="The Computer Journal 16 (1)", url="https://doi.org/10.1093/comjnl/16.1.30", bibkey="DBLP:journals/cj/Sibson73") @Alias({"single-link","single-linkage"}) @Priority(200) public class SLINK<O> extends java.lang.Object implements HierarchicalClusteringAlgorithm
Implementation of the efficient Single-Link Algorithm SLINK of R. Sibson.For ELKI 0.8.0, this was rewritten to no longer use the original "pointer" output format, but instead generate an easier to use merge history now.
This is probably the fastest exact single-link algorithm currently in use.
Reference:
R. Sibson
SLINK: An optimally efficient algorithm for the single-link cluster method
In: The Computer Journal 16 (1)- Since:
- 0.6.0
- Author:
- Elke Achtert, Erich Schubert
-
-
Nested Class Summary
Nested Classes Modifier and Type Class Description static class
SLINK.Par<O>
Parameterization class.-
Nested classes/interfaces inherited from interface elki.Algorithm
Algorithm.Utils
-
-
Method Summary
All Methods Static Methods Instance Methods Concrete Methods Modifier and Type Method Description protected static ClusterMergeHistoryBuilder
convertOutput(ClusterMergeHistoryBuilder builder, ArrayDBIDs oids, DBIDDataStore pi, DoubleDataStore lambda)
Convert a SLINK pointer representation to a cluster merge history.TypeInformation[]
getInputTypeRestriction()
Get the input type restriction used for negotiating the data query.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)
SLINK main loop.ClusterMergeHistory
run(Relation<O> relation)
Performs the SLINK algorithm on the given database.private void
slinkstep3(DBIDRef id, DBIDArrayIter it, int n, WritableDBIDDataStore pi, WritableDoubleDataStore lambda, WritableDoubleDataStore m)
Third step: Determine the values for P and Lprivate void
slinkstep4(DBIDRef id, DBIDArrayIter it, int n, WritableDBIDDataStore pi, WritableDoubleDataStore lambda)
Fourth step: Actualize the clusters if necessaryprivate void
step2(DBIDRef id, DBIDArrayIter it, int n, DistanceQuery<? super O> distQuery, WritableDoubleDataStore m)
Second step: Determine the pairwise distances from all objects in the pointer representation to the new object with the specified id.private void
step2primitive(DBIDRef id, DBIDArrayIter it, int n, Relation<? extends O> relation, PrimitiveDistance<? super O> distance, WritableDoubleDataStore m)
Second step: Determine the pairwise distances from all objects in the pointer representation to the new object with the specified id.-
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
-
-
-
-
Method Detail
-
getInputTypeRestriction
public TypeInformation[] getInputTypeRestriction()
Description copied from interface:Algorithm
Get the input type restriction used for negotiating the data query.- Specified by:
getInputTypeRestriction
in interfaceAlgorithm
- Returns:
- Type restriction
-
run
public ClusterMergeHistory run(Relation<O> relation)
Performs the SLINK algorithm on the given database.- Parameters:
relation
- Data relation to use
-
convertOutput
protected static ClusterMergeHistoryBuilder convertOutput(ClusterMergeHistoryBuilder builder, ArrayDBIDs oids, DBIDDataStore pi, DoubleDataStore lambda)
Convert a SLINK pointer representation to a cluster merge history.- Parameters:
builder
- Builderoids
- original DBIDspi
- Parent pointerlambda
- Parent distance- Returns:
- Builder
-
step2
private void step2(DBIDRef id, DBIDArrayIter it, int n, DistanceQuery<? super O> distQuery, WritableDoubleDataStore m)
Second step: Determine the pairwise distances from all objects in the pointer representation to the new object with the specified id.- Parameters:
id
- the id of the object to be inserted into the pointer representationit
- Array iteratorn
- Last objectdistQuery
- Distance querym
- Data store
-
step2primitive
private void step2primitive(DBIDRef id, DBIDArrayIter it, int n, Relation<? extends O> relation, PrimitiveDistance<? super O> distance, WritableDoubleDataStore m)
Second step: Determine the pairwise distances from all objects in the pointer representation to the new object with the specified id.- Parameters:
id
- the id of the object to be inserted into the pointer representationit
- Array iteratorn
- Last objectm
- Data storerelation
- Data relationdistance
- Distance function to use
-
process
protected void process(DBIDRef id, ArrayDBIDs ids, DBIDArrayIter it, int n, WritableDBIDDataStore pi, WritableDoubleDataStore lambda, WritableDoubleDataStore m)
SLINK main loop.- Parameters:
id
- Current objectids
- All objectsit
- Array iteratorn
- Last object to process at this runpi
- Parentlambda
- Heightm
- Distance
-
slinkstep3
private void slinkstep3(DBIDRef id, DBIDArrayIter it, int n, WritableDBIDDataStore pi, WritableDoubleDataStore lambda, WritableDoubleDataStore m)
Third step: Determine the values for P and L- Parameters:
id
- the id of the object to be inserted into the pointer representationit
- array iteratorn
- Last object to process at this runpi
- Pi data storelambda
- Lambda data storem
- Data store
-
slinkstep4
private void slinkstep4(DBIDRef id, DBIDArrayIter it, int n, WritableDBIDDataStore pi, WritableDoubleDataStore lambda)
Fourth step: Actualize the clusters if necessary- Parameters:
id
- the id of the current objectit
- array iteratorn
- Last object to process at this runpi
- Pi data storelambda
- Lambda data store
-
getLogger
protected Logging getLogger()
Get the (static) class logger.
-
-