de.lmu.ifi.dbs.elki.algorithm.clustering.hierarchical

Class MiniMax<O>

java.lang.Object

de.lmu.ifi.dbs.elki.algorithm.AbstractAlgorithm<R>

de.lmu.ifi.dbs.elki.algorithm.AbstractDistanceBasedAlgorithm<O,PointerPrototypeHierarchyRepresentationResult>

de.lmu.ifi.dbs.elki.algorithm.clustering.hierarchical.MiniMax<O>

Type Parameters:

O - Object type

All Implemented Interfaces:

Algorithm, HierarchicalClusteringAlgorithm, DistanceBasedAlgorithm<O>

@Reference(authors="S. I. Ao, K. Yip, M. Ng, D. Cheung, P.-Y. Fong, I. Melhado, P. C. Sham",title="CLUSTAG: hierarchical clustering and graph methods for selecting tag SNPs",booktitle="Bioinformatics, 21 (8)",url="https://doi.org/10.1093/bioinformatics/bti201",bibkey="DBLP:journals/bioinformatics/AoYNCFMS05") @Reference(authors="J. Bien, R. Tibshirani",title="Hierarchical Clustering with Prototypes via Minimax Linkage",booktitle="Journal of the American Statistical Association 106(495)",url="https://doi.org/10.1198/jasa.2011.tm10183",bibkey="doi:10.1198/jasa.2011.tm10183")
public class MiniMax<O>
extends AbstractDistanceBasedAlgorithm<O,PointerPrototypeHierarchyRepresentationResult>
implements HierarchicalClusteringAlgorithm

Minimax Linkage clustering.

Reference:

S. I. Ao, K. Yip, M. Ng, D. Cheung, P.-Y. Fong, I. Melhado, P. C. Sham
CLUSTAG: hierarchical clustering and graph methods for selecting tag SNPs
Bioinformatics, 21 (8)

J. Bien and R. Tibshirani
Hierarchical Clustering with Prototypes via Minimax Linkage
Journal of the American Statistical Association 106(495)

Since:

0.7.5

Author:

Julian Erhard, Erich Schubert

Nested Class Summary

Nested Classes

Modifier and Type	Class and Description
static class	MiniMax.Parameterizer<O> Parameterization class.

Field Summary

Fields

Modifier and Type	Field and Description
private static Logging	LOG Class Logger.

Fields inherited from class de.lmu.ifi.dbs.elki.algorithm.AbstractAlgorithm

ALGORITHM_ID

Fields inherited from interface de.lmu.ifi.dbs.elki.algorithm.DistanceBasedAlgorithm

DISTANCE_FUNCTION_ID

Constructor Summary

Constructors

Constructor and Description
MiniMax(DistanceFunction<? super O> distanceFunction) Constructor.

Method Summary

Modifier and Type	Method and Description
private static double	findMax(DistanceQuery<?> dq, DBIDIter i, DBIDs cy, double maxDist, double minMaxDist) Find the maximum distance of one object to a set.
protected static int	findMerge(int end, MatrixParadigm mat, DBIDArrayMIter prots, PointerHierarchyRepresentationBuilder builder, it.unimi.dsi.fastutil.ints.Int2ObjectOpenHashMap<ModifiableDBIDs> clusters, DistanceQuery<?> dq) Find the best merge.
private static double	findPrototype(DistanceQuery<?> dq, DBIDs cx, DBIDs cy, DBIDVar prototype, double minMaxDist) Find the prototypes.
private static double	findPrototypeSingleton(DistanceQuery<?> dq, DBIDs cx, DBIDRef cy, DBIDVar prototype) Find the prototypes.
TypeInformation[]	getInputTypeRestriction() Get the input type restriction used for negotiating the data query.
protected Logging	getLogger() Get the (STATIC) logger for this class.
protected static <O> void	initializeMatrices(MatrixParadigm mat, ArrayModifiableDBIDs prots, DistanceQuery<O> dq) Initializes the inter-cluster distance matrix of possible merges
protected static void	merge(int size, MatrixParadigm mat, DBIDArrayMIter prots, PointerHierarchyRepresentationBuilder builder, it.unimi.dsi.fastutil.ints.Int2ObjectOpenHashMap<ModifiableDBIDs> clusters, DistanceQuery<?> dq, int x, int y) Merges two clusters given by x, y, their points with smallest IDs, and y to keep
PointerPrototypeHierarchyRepresentationResult	run(Database db, Relation<O> relation) Run the algorithm on a database.
protected static void	updateEntry(MatrixParadigm mat, DBIDArrayMIter prots, it.unimi.dsi.fastutil.ints.Int2ObjectOpenHashMap<ModifiableDBIDs> clusters, DistanceQuery<?> dq, int x, int y) Update entry at x,y for distance matrix distances
protected static <O> void	updateMatrices(int size, MatrixParadigm mat, DBIDArrayMIter prots, PointerHierarchyRepresentationBuilder builder, it.unimi.dsi.fastutil.ints.Int2ObjectOpenHashMap<ModifiableDBIDs> clusters, DistanceQuery<O> dq, int c) Update the entries of the matrices that contain a distance to c, the newly merged cluster.

Methods inherited from class de.lmu.ifi.dbs.elki.algorithm.AbstractDistanceBasedAlgorithm

getDistanceFunction

Methods inherited from class de.lmu.ifi.dbs.elki.algorithm.AbstractAlgorithm

run

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Methods inherited from interface de.lmu.ifi.dbs.elki.algorithm.clustering.hierarchical.HierarchicalClusteringAlgorithm

run

Field Detail

LOG

private static final Logging LOG

Class Logger.

Constructor Detail

MiniMax

public MiniMax(DistanceFunction<? super O> distanceFunction)

Constructor.

Parameters:

distanceFunction - Distance function to use.

Method Detail

run

public PointerPrototypeHierarchyRepresentationResult run(Database db,
                                                         Relation<O> relation)

Run the algorithm on a database.

Parameters:

db - Database

relation - Relation to process.

Returns:

Hierarchical result

initializeMatrices

protected static <O> void initializeMatrices(MatrixParadigm mat,
                                             ArrayModifiableDBIDs prots,
                                             DistanceQuery<O> dq)

Initializes the inter-cluster distance matrix of possible merges

Parameters:

mat - Matrix

dq - The distance query

findMerge

protected static int findMerge(int end,
                               MatrixParadigm mat,
                               DBIDArrayMIter prots,
                               PointerHierarchyRepresentationBuilder builder,
                               it.unimi.dsi.fastutil.ints.Int2ObjectOpenHashMap<ModifiableDBIDs> clusters,
                               DistanceQuery<?> dq)

Find the best merge.

Parameters:

mat - Matrix view

prots - Prototypes

builder - Result builder

clusters - Current clusters

dq - Distance query

Returns:

x, for shrinking the working set.

merge

protected static void merge(int size,
                            MatrixParadigm mat,
                            DBIDArrayMIter prots,
                            PointerHierarchyRepresentationBuilder builder,
                            it.unimi.dsi.fastutil.ints.Int2ObjectOpenHashMap<ModifiableDBIDs> clusters,
                            DistanceQuery<?> dq,
                            int x,
                            int y)

Merges two clusters given by x, y, their points with smallest IDs, and y to keep

Parameters:

size - number of ids in the data set

mat - distance matrix

prots - calculated prototypes

builder - Result builder

clusters - the clusters

dq - distance query of the data set

x - first cluster to merge

y - second cluster to merge

updateMatrices

protected static <O> void updateMatrices(int size,
                                         MatrixParadigm mat,
                                         DBIDArrayMIter prots,
                                         PointerHierarchyRepresentationBuilder builder,
                                         it.unimi.dsi.fastutil.ints.Int2ObjectOpenHashMap<ModifiableDBIDs> clusters,
                                         DistanceQuery<O> dq,
                                         int c)

Update the entries of the matrices that contain a distance to c, the newly merged cluster.

Parameters:

size - number of ids in the data set

mat - matrix paradigm

prots - calculated prototypes

builder - Result builder

clusters - the clusters

dq - distance query of the data set

c - the cluster to update distances to

updateEntry

protected static void updateEntry(MatrixParadigm mat,
                                  DBIDArrayMIter prots,
                                  it.unimi.dsi.fastutil.ints.Int2ObjectOpenHashMap<ModifiableDBIDs> clusters,
                                  DistanceQuery<?> dq,
                                  int x,
                                  int y)

Update entry at x,y for distance matrix distances

Parameters:

mat - distance matrix

prots - calculated prototypes

clusters - the clusters

dq - distance query on the data set

x - index of cluster, x > y

y - index of cluster, y < x

findPrototype

private static double findPrototype(DistanceQuery<?> dq,
                                    DBIDs cx,
                                    DBIDs cy,
                                    DBIDVar prototype,
                                    double minMaxDist)

Find the prototypes.

Parameters:

dq - Distance query

cx - First set

cy - Second set

prototype - Prototype output variable

minMaxDist - Previously best distance.

Returns:

New best distance

findPrototypeSingleton

private static double findPrototypeSingleton(DistanceQuery<?> dq,
                                             DBIDs cx,
                                             DBIDRef cy,
                                             DBIDVar prototype)

Find the prototypes.

Parameters:

dq - Distance query

cx - First set

cy - Singleton object

prototype - Prototype output variable

Returns:

New best distance

findMax

private static double findMax(DistanceQuery<?> dq,
                              DBIDIter i,
                              DBIDs cy,
                              double maxDist,
                              double minMaxDist)

Find the maximum distance of one object to a set.

Parameters:

dq - Distance query

i - Current object

cy - Set of candidates

maxDist - Known maximum to others

minMaxDist - Early stopping threshold

Returns:

Maximum distance

getInputTypeRestriction

public TypeInformation[] getInputTypeRestriction()

Description copied from class: AbstractAlgorithm

Get the input type restriction used for negotiating the data query.

Specified by:

getInputTypeRestriction in interface Algorithm

Specified by:

getInputTypeRestriction in class AbstractAlgorithm<PointerPrototypeHierarchyRepresentationResult>

Returns:

Type restriction

getLogger

protected Logging getLogger()

Description copied from class: AbstractAlgorithm

Get the (STATIC) logger for this class.

Specified by:

getLogger in class AbstractAlgorithm<PointerPrototypeHierarchyRepresentationResult>

Returns:

the static logger