Computing exact clustering posteriors with subset convolution

DOI10.1080/03610926.2014.894070MaRDI QIDQ2815984zbMATH OpenOpenAlexFDO

Authors Jukka Kohonen, Jukka Corander

Publication date 30 June 2016

Published in Communications in Statistics. Theory and Methods (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1310.1034

zbMATH Keywords

clusteringexact algorithmssubset convolution

Mathematics Subject Classification ID

Bayesian inference (62F15) Classification and discrimination; cluster analysis (statistical aspects) (62H30)

Abstract: An exponential-time exact algorithm is provided for the task of clustering n items of data into k clusters. Instead of seeking one partition, posterior probabilities are computed for summary statistics: the number of clusters, and pairwise co-occurrence. The method is based on subset convolution, and yields the posterior distribution for the number of clusters in O(n * 3^n) operations, or O(n^3 * 2^n) using fast subset convolution. Pairwise co-occurrence probabilities are then obtained in O(n^3 * 2^n) operations. This is considerably faster than exhaustive enumeration of all partitions.

Recommendations

• Modal clustering in a class of product partition models
• Dynamic programming and convex clustering
• Improved criteria for clustering based on the posterior similarity matrix
• Sublinear time approximate clustering
• scientific article; zbMATH DE number 1163449

Cites work

• A Dynamic Programming Algorithm for Cluster Analysis
• Bayesian Clustering and Product Partition Models
• Bayesian Detection of Clusters and Discontinuities in Disease Maps
• Bayesian unsupervised classification framework based on stochastic partitions of data and a parallel search strategy
• Combinatorial data analysis. Optimization by dynamic programming
• Dealing With Label Switching in Mixture Models
• Exact exponential algorithms.
• scientific article; zbMATH DE number 3357742 (Why is no real title available?)
• Improving dynamic programming strategies for partitioning
• Modal clustering in a class of product partition models
• Product partition models for change point problems

This page was built for publication: Computing exact clustering posteriors with subset convolution

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2815984)