Research On Affinity Propagation And Its Application In Image Clustering

Clustering or discovering meaning partitions of data is a fundamental problem of data mining, maching learning and pattern recognition. This thesis is dedicated to one symbolic method of exemplar based clustering:Affinity Propagation. Published on Science at 2007, it achieved outstanding results and has been used as an analysis tool to tackle a wide array of problems in different research areas. In Affinity Progation, data is characterized by a measure of pairwise similairities, thus emancipated from the restrication of vector space. And clusters are instead be represented by exemplar data, while simultaneously considering all data points as potential exemplars. By viewing each data point in a network, it recursively transmits messages along edges of the network until a good set of exemplars and corresponding clusters emerge.The fact of the algorithm's effectiveness results in the desire to further extend it. The focus of chapter three is on integrating supervised information with the original method using SSAP(semi-supervised affinity propagation) model and metric learning approach. To relax the hard constaints introduced by the SSAP model, new parameters controlling the intensity of the constrainsts are introduced. Tests on the synthetic datasets demonstrate good performances.To apply the algorithm in the field of image clustering, chapter four conducted experiments on real image datasets. In core computer vision research, features play significant role. Different feature extraction methods may lead to different similarity computation strategies, whereupon chapter four gives a comprehensive discussion. Meanwhile, squre time complexity is alleviated by sparse similarity.Further on, Chapter five shows a practical way to implement affinity propagation on Spark. After belief introduction to Spark, it gives details about the parallel logics and data structures. Experiment results indicate its potential in extention to big datasets.