Class 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
    • Field Detail

      • LOG

        private static final Logging LOG
        Class logger
      • 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