Bayesian blocks in two or more dimensions: Image segmentation and cluster analysis
Jeffrey D. Scargle · AIP conference proceedings · 2002
I describe an extension, to higher dimensions, of the Bayesian Blocks algorithm for estimating signals in noisy time series data [17,18]. We seek the partition of the data space with the maximum posterior for a model consisting of a homogeneous Poisson process in each partition element. Model Mn, attributing the data within region n of the data space to a Poisson process with a fixed event rate λn, has a global posterior depending on only N, the number of data points in the region, and V, its volume: P(Mn)=Φ(N,V)=Γ(N+1)Γ(V−N+1)/Γ(V+2)=N!(V−N)!/(V+1)!. (1) Note that λn does not appear, since it has been marginalized, using a flat, improper prior. Other priors yield similar formulas. This expression is valid for a data space of any dimension. Suppose two regions, described by N1, V1 and N2, V2, are candidates for being merged into one. The Bayes merge factor, giving the posterior ratio for merged and not merged, respectively, is: P=Φ(N1+N2,V1+V2)/Φ(N1,V1)Φ(N2,V2). (2) Then collect data points into blocks with this cell coalescence algorithm: (1) Identify each cell of the Voronoi tessellation of the data as a block (2) Iteratively merge the pair of blocks with the largest merge factor (3) Halt when the maximum merge factor falls below 1 In many applications it convenient to restrict mergers to neighboring blocks. This algorithm partitions the space into a set of relatively few blocks, each having a density equal to the number of its data points divided by its volume. Adjacent high-density blocks can be collected into clusters. This method allows detection of clusters in high-dimensional data spaces, with the following properties: • The number of clusters is determined, not assumed • Clusters can have any shape: - Avoid the conventional Gaussian assumption - Shapes can include both concavities and convexities - Blocks and clusters do not even have to be simply connected • Cluster density profiles are estimated, not just the boundaries • Any slowly varying background is automatically identified • No binning of the raw data is necessary