Affinity Propagation (sklearn) - strange behavior Trying to use affinity propagation for a simple clustering task:
from sklearn.cluster import AffinityPropagation
c = [[0], [0], [0], [0], [0], [0], [0], [0]]
af = AffinityPropagation (affinity = 'euclidean').fit (c)
print (af.labels_)

I get this strange result: [0 1 0 1 2 1 1 0]
I would expect to have all samples in the same cluster, like in this case:
c = [[0], [0], [0]]
af = AffinityPropagation (affinity = 'euclidean').fit (c)
print (af.labels_)

which indeed puts all samples in the same cluster: [0 0 0]
What am I missing?
Thanks
 A: The way that Affinity Propagation works is that it sends messages back and forth between 'nodes' comparing them. The comparisons between elements of your data set will all result in equality, so you will achieve a sort of equilibrium where clusters can't choose what their exemplar should be. (I mean, evidently this is what is happening, I didn't know this could happen until I saw this question)
To fix this, you can increase the damping factor. Default damping is 0.5, which means 50% of the calculation for new cluster with each iteration is based on information, and 50% of the calculation is based on current cluster. If we raise damping, then the info from the other cluster is weighted more heavily, and thus the algorithm will recognize the equality and quickly merge to a single exemplar/cluster:
>>> from sklearn.cluster import AffinityPropagation
>>> c = [[0], [0], [0], [0], [0], [0], [0], [0]]
>>> af = AffinityPropagation (damping = 0.5,affinity = 'euclidean').fit (c)
>>> print (af.labels_)
[0 1 0 1 2 1 1 0]

>>> from sklearn.cluster import AffinityPropagation
>>> c = [[0], [0], [0], [0], [0], [0], [0], [0]]
>>> af = AffinityPropagation (damping = 0.9,affinity = 'euclidean').fit (c)
>>> print (af.labels_)
[0 1 0 0 1 1 1 0]

>>> from sklearn.cluster import AffinityPropagation
>>> c = [[0], [0], [0], [0], [0], [0], [0], [0]]
>>> af = AffinityPropagation (damping = 0.99,affinity = 'euclidean').fit (c)
>>> print (af.labels_)
[0 0 0 0 0 0 0 0]

A: Change of behaviour
Note that the behaviour reported in the question has changed since sklearn version 0.20 [1]. Now the answers to a clustering of same samples will be to give back one cluster per sample. A warning will be also delivered.
Example:
from sklearn.cluster import AffinityPropagation
c = [[0], [0], [0], [0], [0], [0], [0], [0]]
af = AffinityPropagation (affinity = 'euclidean').fit (c)
print (af.labels_)

output:
P:\Development\Anaconda3\lib\site-packages\sklearn\cluster\affinity_propagation_.py:125:
UserWarning: All samples have mutually equal similarities. Returning arbitrary cluster center(s).                                                        warnings.warn("All samples have mutually equal similarities. "
[0 1 2 3 4 5 6 7] 

Explanation of Affinity Propagation
Affinity Propagation tries to maximize the total similarity [2]. It does so through a message passing algorithm, but it is not necessary to understand the algorithm to understand the results.
What is this total similarity and how does it depend on the possible different results of clustering?
similarity between two sample points
Given two sample points the default similarity of Affinity Propagation is to take minus the squared euclidean distance. The more two points are distant, the less they are similar.
exemplars
Affinity Propagation iteratively tries to find the best set of exemplars (to maximize similarity). Exemplars are sample points which will be used to separate all other points in clusters (every exemplar gives a cluster and a point belongs to the cluster of the closest - actually most similar - exemplar). Exemplars are different than centroids of K-Means since they actually have to be one of the sample points (while in K-means the centroid is a barycenter of the points in a cluster).
preferences
Every point will be assigned not only a similarity against each other point, but also a self-similiarity with itself, called preference. This is a crucial input of Affinity Propagation and depending on its value the number of output clusters can vary wildly. Note that in principle every point can have a different preference from other points, but the more common case is for all points to have the same preference. By default this preference is the median value of all input similiarities.
total similarity
The total similarity given a set of exemplars is the sum of preferences of exemplars and the sum of similarities of the other points with respect to the cluster they are associated.
Let $s_{i, j}$ be the similarity of point $i$ with point $j$ (so that $s_{i,i}$ is the preference of point $i$), and let $c(i) = j$ be the mapping that asociates to point $i$ the cluster of exemplar $j$ (we will have that for an exemplar $k$ $c(k) = k$).
Then the total similarity is:
$\Sigma_{i} s_{i, c(i)}$
relationship between preference and number of clusters
If points like themselves a lot (i.e. they have a high preference) they will tend to make their own cluster (they can only be attracted from a point more similar than their preference). In particular if the preference of all points is higher than all input similarities, we will get a cluster for each point. If instead the points have preferences always smaller than the input similarities we will have a single cluster.
In general, higher preferences -> more cluster, lower preferences -> less clusters.
Conclusions
In the example above where the sample points are all the same, the input similiarities are all 0 (default to negative squared distance) and the preference is also 0. In this degenerate condition the total similarity is the same whatever the cluster output is. The default in sklearn is currently to put each sample point in a single cluster (debatable but that is the current default). If you override the prefence with a negative value instead you will obtain a single cluster:
c = [[0], [0], [0], [0], [0], [0], [0], [0]]
af = AffinityPropagation (affinity = 'euclidean', preference=-1e09).fit (c)
print (af.labels_)

output:
[0 0 0 0 0 0 0 0]

why the old behaviour?
In the past there was no check that input similarities and preferences were all equal. So the next step of AffinityPropagation is to add a small random noise to the similarity matrix. This makes the resulting clustering actually depending on this random noise instead of the input and makes also the damping impact the type of results that we obtain.
References
[1] Since this pull request: https://github.com/scikit-learn/scikit-learn/pull/9635
[2] http://www.cs.columbia.edu/~delbert/docs/DDueck-thesis_small.pdf
