test Browse by Author Names Browse by Titles of Works Browse by Subjects of Works Browse by Issue Dates of Works

Advanced Search
& Collections
Issue Date   
Sign on to:   
Receive email
My Account
authorized users
Edit Profile   
About T-Space   

T-Space at The University of Toronto Libraries >
School of Graduate Studies - Theses >
Doctoral >

Please use this identifier to cite or link to this item: http://hdl.handle.net/1807/17755

Title: Affinity Propagation: Clustering Data by Passing Messages
Authors: Dueck, Delbert
Advisor: Frey, Brendan J.
Department: Electrical and Computer Engineering
Keywords: Computer Science
Machine Learning
Exemplar-based clustering
Factor Graph
Belief Propagation
Issue Date: 24-Sep-2009
Abstract: Clustering data by identifying a subset of representative examples is important for detecting patterns in data and in processing sensory signals. Such "exemplars" can be found by randomly choosing an initial subset of data points as exemplars and then iteratively refining it, but this works well only if that initial choice is close to a good solution. This thesis describes a method called "affinity propagation" that simultaneously considers all data points as potential exemplars, exchanging real-valued messages between data points until a high-quality set of exemplars and corresponding clusters gradually emerges. Affinity propagation takes as input a set of pairwise similarities between data points and finds clusters on the basis of maximizing the total similarity between data points and their exemplars. Similarity can be simply defined as negative squared Euclidean distance for compatibility with other algorithms, or it can incorporate richer domain-specific models (e.g., translation-invariant distances for comparing images). Affinity propagation’s computational and memory requirements scale linearly with the number of similarities input; for non-sparse problems where all possible similarities are computed, these requirements scale quadratically with the number of data points. Affinity propagation is demonstrated on several applications from areas such as computer vision and bioinformatics, and it typically finds better clustering solutions than other methods in less time.
URI: http://hdl.handle.net/1807/17755
Appears in Collections:Doctoral
The Edward S. Rogers Sr. Department of Electrical & Computer Engineering - Doctoral theses

Files in This Item:

File Description SizeFormat
Dueck_Delbert_200906_PhD_thesis.pdf16.63 MBAdobe PDF

Items in T-Space are protected by copyright, with all rights reserved, unless otherwise indicated.