Class AGNES<O>
- java.lang.Object
-
- elki.clustering.hierarchical.AGNES<O>
-
- Type Parameters:
O
- Object type
- All Implemented Interfaces:
Algorithm
,HierarchicalClusteringAlgorithm
@Reference(authors="L. Kaufman, P. J. Rousseeuw",title="Agglomerative Nesting (Program AGNES)",booktitle="Finding Groups in Data: An Introduction to Cluster Analysis",url="https://doi.org/10.1002/9780470316801.ch5",bibkey="doi:10.1002/9780470316801.ch5") @Reference(authors="P. H. Sneath",title="The application of computers to taxonomy",booktitle="Journal of general microbiology, 17(1)",url="https://doi.org/10.1099/00221287-17-1-201",bibkey="doi:10.1099/00221287-17-1-201") @Reference(authors="R. M. Cormack",title="A Review of Classification",booktitle="Journal of the Royal Statistical Society. Series A, Vol. 134, No. 3",url="https://doi.org/10.2307/2344237",bibkey="doi:10.2307/2344237") @Alias({"HAC","SAHN"}) public class AGNES<O> extends java.lang.Object implements HierarchicalClusteringAlgorithm
Hierarchical Agglomerative Clustering (HAC) or Agglomerative Nesting (AGNES) is a classic hierarchical clustering algorithm. Initially, each element is its own cluster; the closest clusters are merged at every step, until all the data has become a single cluster.This is the naive O(n³) algorithm. See
SLINK
for a much faster algorithm (however, only for single-linkage).This implementation uses the pointer-based representation used by SLINK, so that the extraction algorithms we have can be used with either of them.
The algorithm is believed to be first published (for single-linkage) by:
P. H. Sneath
The application of computers to taxonomy
Journal of general microbiology, 17(1).This algorithm is also known as AGNES (Agglomerative Nesting), where the use of alternative linkage criterions is discussed:
L. Kaufman, P. J. Rousseeuw
Agglomerative Nesting (Program AGNES),
in Finding Groups in Data: An Introduction to Cluster AnalysisReference for the unified concept:
G. N. Lance, W. T. Williams
A general theory of classificatory sorting strategies 1. Hierarchical systems
The computer journal 9.4 (1967): 373-380.See also:
R. M. Cormack
A Review of Classification
Journal of the Royal Statistical Society. Series A, Vol. 134, No. 3- Since:
- 0.6.0
- Author:
- Erich Schubert
-
-
Nested Class Summary
Nested Classes Modifier and Type Class Description static class
AGNES.Instance
Main worker instance of AGNES.-
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 TypeInformation[]
getInputTypeRestriction()
Get the input type restriction used for negotiating the data query.protected static ClusterDistanceMatrix
initializeDistanceMatrix(ArrayDBIDs ids, DistanceQuery<?> dq, Linkage linkage)
Initialize a distance matrix.ClusterMergeHistory
run(Relation<O> relation)
Run the algorithm-
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
-
run
public ClusterMergeHistory run(Relation<O> relation)
Run the algorithm- Parameters:
relation
- Relation- Returns:
- Clustering hierarchy
-
initializeDistanceMatrix
protected static ClusterDistanceMatrix initializeDistanceMatrix(ArrayDBIDs ids, DistanceQuery<?> dq, Linkage linkage)
Initialize a distance matrix.- Parameters:
ids
- Object idsdq
- Distance querylinkage
- Linkage method- Returns:
- cluster distance matrix
-
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
-
-