We adapt a classic online clustering algorithm called Balanced Iterative Reducing and Clustering using Hierarchies (BIRCH), to incrementally cluster large datasets of features commonly used in multimedia and computer vision. We call the adapted version modified-BIRCH (m-BIRCH). The algorithm uses only a fraction of the dataset memory to perform clustering, and updates the clustering decisions when new data comes in. Modifications made in m-BIRCH enable data driven parameter selection and effectively handle varying density regions in the feature space. Data driven parameter selection automatically controls the level of coarseness of the data summarization. Effective handling of varying density regions is necessary to well represent the different density regions in data summarization. We use m-BIRCH to cluster 840K color SIFT descriptors, and 60K outlier corrupted grayscale patches. We use the algorithm to cluster datasets consisting of challenging non-convex clustering patterns. Our implementation of the algorithm provides an useful clustering tool and is made publicly available.

Date Published: 6 March 2015
PDF: 17 pages
Proc. SPIE 9408, Imaging and Multimedia Analytics in a Web and Mobile World 2015, 940808 (6 March 2015); doi: 10.1117/12.2078264

Published in SPIE Proceedings Vol. 9408:
Imaging and Multimedia Analytics in a Web and Mobile World 2015
Qian Lin; Jan P. Allebach; Zhigang Fan, Editor(s)