This is a pre-production deployment of Warehouse. Changes made here affect the production instance of PyPI (
Help us improve Python packaging - Donate today!

Sparse Affinity Propagation Clustering

Project Description
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.


Install from source:
Download and unzip source files and install as:
python install

Install from pip:
pip install pysapc

Install from Conda:
conda install -c pysapc

To test installation, in python shell, run:
from pysapc import tests

Quick Start:

Use pysapc to cluster sparse similarity matrix (scipy sparse matrix):
from pysapc import SAP
sap_exemplars=sap.fit_predict(X) # X should be a scipy sparse similarity matrix

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.

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

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)

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

Release History

This version
History Node


Download Files

Download Files

Download the file for your platform. If you're not sure which to choose, learn more about installing packages.

File Name & Checksum SHA256 Checksum Help Version File Type Upload Date
pysapc-1.1.0.tar.gz (4.7 MB) Copy SHA256 Checksum SHA256 Source Jun 3, 2016

Supported By

WebFaction WebFaction Technical Writing Elastic Elastic Search Pingdom Pingdom Monitoring Dyn Dyn DNS Sentry Sentry Error Logging CloudAMQP CloudAMQP RabbitMQ Heroku Heroku PaaS Kabu Creative Kabu Creative UX & Design Fastly Fastly CDN DigiCert DigiCert EV Certificate Rackspace Rackspace Cloud Servers DreamHost DreamHost Log Hosting