python package for Sparse Affinity Propagation (SAP) Clustering method. 
Affinity propagation (AP) is a relatively new clustering algorithm that has been introduced by Brendan J. Frey and Delbert Dueck. Compared with classical clustering methods such as k-means, AP has several advantages such as a lower clustering error, automatic determination of number of clusters, identification of exemplars (cluster centers), support of similarities that are not symmetric and deterministic clustering result (k-means clustering result depends on initialization, and hence requires multiple runs to achieves global optimization). Instead of full similarity matrix, pySAPC can take scipy sparse matrix(affinity/similarity matrix). pySAPC will be useful in case when full similarity matrix can not fit in memory. Speed and memory optimized with cython.

Python 3 supported.

Installation:

Install from source:
Download and unzip source files and install as:
python setup.py install


To test installation, in python shell, run:
from pysapc import tests
tests.testDense()
tests.testSparse()

Quick Start:

Use pysapc to cluster sparse similarity matrix (scipy sparse matrix):
from pysapc import SAP
sap=SAP(preference,convergence_iter=convergence_iter,max_iter=max_iter,damping=damping,verboseIter=100)
sap_exemplars=sap.fit_predict(X) # X should be a scipy sparse similarity matrix


Parameters:
----------------------
X: precomputed sparse affinity/similarity matrix in scipy coo_matrix,csr_matrix or lil_matrix format
    (affinity/similarity could be cosine, pearson, euclidean distance, or others).
    Please note that affinity/similarity matrix doesn't need to be symmetric, s(A,B) can be different from s(B,A).
    In fact it could be that s(A,B) exist while s(B,A) not exist in the sparse affinity/similarity matrix

preference: a numeric scalar(float), or a str of 'min'/'median', or a list/numpy 1D array(length of samples)
    the preference of a datapoint K, p(K), which will set to the affinity/similarity matrix s(K,K), is the 
    priori suitability of datapoint K to serve as an exemplar (cluster center), Higher values of preference will lead to more exemplars (cluster centers).
    A good initial choice is minimum('min') or median('median') of the full dense affinity/similarity matrix.
    Plsease note that minimum('min') or median('median') of sparse affinity/similarity matrix is not recommended.

convergence_iter: int, optional, default: 15. Number of iterations with no change or change less than 1.0-convergence_percentage 
    in exemplars (cluster centers) label of datapoint.

convergence_percentage: float, optional, default: 0.999999, 
    This parameter is used to define convergence condition. If set as 0.999999, then one or less out of 1 million datapoints does not change their exemplars (cluster centers) will be considered as convergence.
    This parameter is added because pySAPC is designed to deal with large data.

max_iter: int, optional, default: 2000
    Maximum number of iterations. Try to increase max_iter if pySAPC is not convergence yet at max_iter.

damping: float, optional, default: 0.9.
    Damping factor, should between 0.5 and 1.

verboseIter: int or None, default: 100
    The level of verbose. if set to 0 or None, no verbose output; 
    If set to 1, print the status for each interation.
    If set to 100, for each 100 iterations, print current status
    
parallel: boolean, default: True
    Turn on cython multiprocessing or not. It is recommended to set it True for speed up.

Attributes
----------------
exemplars_: the cluster centers for each datapoint, same length of samples.
    The index(row index of matrix) of examplers(cluster centers) for each datapoint 

Notes
---------------
To prepare sparse matrix, either use a single cutoff for all samples (for example keep top 20 percent of full matrix) or use different cutoff values for each samples so that each samples have K nearest neighbors. Users are recommended to try several sparse matrix and compare their clustering result to determine when the clustering result reach plateau (when including more data do not change clustering result significantly) 


References
----------------
Brendan J. Frey and Delbert Dueck, "Clustering by Passing Messages Between Data Points", Science Feb. 2007