Package elki.clustering.affinitypropagation

Class AffinityPropagation<O>

java.lang.Object

elki.clustering.affinitypropagation.AffinityPropagation<O>

Type Parameters:

O - object type

All Implemented Interfaces:

Algorithm, ClusteringAlgorithm<Clustering<MedoidModel>>

@Title("Affinity Propagation: Clustering by Passing Messages Between Data Points")
@Reference(title="Clustering by Passing Messages Between Data Points",
           authors="B. J. Frey, D. Dueck",
           booktitle="Science Vol 315",
           url="https://doi.org/10.1126/science.1136800",
           bibkey="doi:10.1126/science.1136800")
public class AffinityPropagation<O>
extends java.lang.Object
implements ClusteringAlgorithm<Clustering<MedoidModel>>

Cluster analysis by affinity propagation.

Reference:

B. J. Frey, D. Dueck
Clustering by Passing Messages Between Data Points
Science Vol 315

Since:

0.6.0

Author:

Erich Schubert

Nested Class Summary

Nested classes/interfaces inherited from interface elki.Algorithm

Algorithm.Utils

Field Summary

Fields

Modifier and Type	Field	Description
(package private) int	convergence	Terminate after 10 iterations with no changes.
(package private) AffinityPropagationInitialization<O>	initialization	Similarity initialization
(package private) double	lambda	Damping factor lambda.
private static Logging	LOG	Class logger
(package private) int	maxiter	Maximum number of iterations.

Constructor Summary

Constructors

Constructor	Description
AffinityPropagation(AffinityPropagationInitialization<O> initialization, double lambda, int convergence, int maxiter)	Constructor.

Method Summary

Modifier and Type	Method	Description
private Clustering<MedoidModel>	buildResult(ArrayDBIDs ids, int[] assignment)	Build the clustering result.
TypeInformation[]	getInputTypeRestriction()	Get the input type restriction used for negotiating the data query.
private it.unimi.dsi.fastutil.ints.Int2ObjectOpenHashMap<ModifiableDBIDs>	makeClusterMap(ArrayDBIDs ids, int[] assignment)	Build an int to DBIDs lookup for the clusters.
Clustering<MedoidModel>	run(Relation<O> relation)	Perform affinity propagation clustering.
private int	updateAssignment(double[][] r, double[][] a, int[] assignment)	Update the cluster assignment.
private void	updateAvailabilities(double[][] r, double[][] a)	Update availability matrix
private void	updateResponsibilities(double[][] s, double[][] a, double[][] r)	Update the responsibility matrix

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

Class logger

initialization

AffinityPropagationInitialization<O> initialization

Similarity initialization

lambda

double lambda

Damping factor lambda.

convergence

int convergence

Terminate after 10 iterations with no changes.

maxiter

int maxiter

Maximum number of iterations.

Constructor Detail

AffinityPropagation

public AffinityPropagation(AffinityPropagationInitialization<O> initialization,
                           double lambda,
                           int convergence,
                           int maxiter)

Constructor.

Parameters:

initialization - Similarity initialization

lambda - Damping factor

convergence - Termination threshold (Number of stable iterations)

maxiter - Maximum number of iterations

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 interface Algorithm

Returns:

Type restriction

run

public Clustering<MedoidModel> run(Relation<O> relation)

Perform affinity propagation clustering.

Parameters:

relation - Relation

Returns:

Clustering result

updateResponsibilities

private void updateResponsibilities(double[][] s,
                                    double[][] a,
                                    double[][] r)

Update the responsibility matrix

Parameters:

s - Similarities

a - Availability

r - Responsibilities

updateAvailabilities

private void updateAvailabilities(double[][] r,
                                  double[][] a)

Update availability matrix

Parameters:

r - Responsibilities

a - Availability

updateAssignment

private int updateAssignment(double[][] r,
                             double[][] a,
                             int[] assignment)

Update the cluster assignment.

Parameters:

r - Responsibilities

a - Affinities

assignment - Assignment storage

Returns:

Number of changed entries

makeClusterMap

private it.unimi.dsi.fastutil.ints.Int2ObjectOpenHashMap<ModifiableDBIDs> makeClusterMap(ArrayDBIDs ids,
                                                                                         int[] assignment)

Build an int to DBIDs lookup for the clusters.

Parameters:

ids - DBIDs

assignment - Cluster assignment

Returns:

Index

buildResult

private Clustering<MedoidModel> buildResult(ArrayDBIDs ids,
                                            int[] assignment)

Build the clustering result.

Parameters:

ids - DBIDs

assignment - Assignment index

Returns:

Clustering