Affinity propagation

In statistics and data mining, affinity propagation (AP) is a clustering algorithm based on the concept of 'message passing' between data points.Unlike clustering algorithms such as k-means or k-medoids, affinity propagation does not require the number of clusters to be determined or estimated before running the algorithm. Similar to k-medoids, affinity propagation finds 'exemplars', members of the input set that are representative of clusters. In statistics and data mining, affinity propagation (AP) is a clustering algorithm based on the concept of 'message passing' between data points.Unlike clustering algorithms such as k-means or k-medoids, affinity propagation does not require the number of clusters to be determined or estimated before running the algorithm. Similar to k-medoids, affinity propagation finds 'exemplars', members of the input set that are representative of clusters. Let x1 through xn be a set of data points, with no assumptions made about their internal structure, and let s be a function that quantifies the similarity between any two points, such that s(xi, xj) > s(xi, xk) iff xi is more similar to xj than to xk. For this example, the negative squared distance of two data points was used i.e. for points xi and xk, s ( i , k ) = − ‖ x i − x k ‖ 2 {displaystyle s(i,k)=-left|x_{i}-x_{k} ight|^{2}} The diagonal of s (i.e. s ( i , i ) {displaystyle s(i,i)} ) is particularly important, as it represents the input preference, meaning how likely a particular input is to become an exemplar. When it is set to the same value for all inputs, it controls how many classes the algorithm produces. A value close to the minimum possible similarity produces fewer classes, while a value close to or larger than the maximum possible similarity, produces many classes. It is typically initialized to the median similarity of all pairs of inputs. The algorithm proceeds by alternating two message passing steps, to update two matrices: Both matrices are initialized to all zeroes, and can be viewed as log-probability tables. The algorithm then performs the following updates iteratively: The iterations are performed until either the cluster boundaries remain unchanged over a number of iterations, or after some predetermined number of iterations. The exemplars are extracted from the final matrices as those whose 'responsibility + availability' for themselves is positive (i.e. ( r ( i , i ) + a ( i , i ) ) > 0 {displaystyle (r(i,i)+a(i,i))>0} ). The inventors of affinity propagation showed it is better for certain computer vision and computational biology tasks, e.g. clustering of pictures of human faces and identifying regulated transcripts, than k-means, even when k-means was allowed many random restarts and initialized using PCA.A study comparing affinity propagation and Markov clustering on protein interaction graph partitioning found Markov clustering to work better for that problem. A semi-supervised variant has been proposed for text mining applications.