clustering with particle filters

Question

Suppose we want to cluster a data stream of unknown number of clusters, and estimate them using particle filters. With particle filters, we need to know $P(x_t | x_{t-1})$ and $P(z_t | x_t)$ (where z refer to the data (reports), and x refer to the estimated states (hypothesis)).

Then my question is: how can we define $P(x_t | x_{t-1})$ (transition probability) and $P(z_t | x_t)$ (observation/likelihood probability) in this context (online clustering) ?

Answer 1

Preliminaries

From §3 (Bayesian Sequential Clustering):

Let the stochastic variable $X_k = [I_1, \dots, I_k]$ denote the state at step $k$, and $x_k = [i_1,\dots, i_k]$ a certain value of $X_k$, i.e., a certain state. Thus, at step $k$ we have received $k$ observations and all elements of the state-space $x_k$ are of length $k$, where $i_k$ is a target number of an observation $z_k$ according to hypothesis $x_k$.

The number of objects according to the hypothesis $x_k$ can be obtained as $n_k = \max(x_k) = \max([i_1, \dots, i_k])$.

State space

The structure of the state space is depicted in fig.1 (pg.1):

At the arrival of the first report, the state-space has only two states, [0] and [1]. We let the value “0” mean clutter, and let the value “1” mean a target given a target number of “1”.

Since the number of possible states grows somewhat faster than simple exponentially, we must perform some hard pruning.

This is facilitated through the particle filter (pg.2):

At each time-step, we will only propagate those states which have posterior probability higher than a certain threshold. All other states are assigned zero probability and are eliminated. This is achieved indirectly by using a fixed number of particles. Whatever remains are the active hypotheses maintained in the analysis. As many states with a small likelihood are not sampled with the Monte Carlo algorithm we avoid a combinatorial explosion.

Transition probability

This is the subject of §3.1. The state is updated by concatenating the target number $i_k$ with the previous state (see previous section). Three cases are identified (no cluster, new cluster, existing cluster), and associated transition probabilities given in (2-6).

Observation likelihood

This is the subject of §3.2. The standard Gaussian error model is used if observations are available, otherwise the uniform distribution is used to indicate that all observations are equally probable. Also:

Denote the number of clusters according to hypothesis $x_k$, $n_k$. From $x_k$, $n_k$ cluster means can be computed, as the Euclidean mean position of all observations clustered in the same cluster. These cluster means are the estimated positions of the $n_k$ objects that generated the observations $[z_1,\dots,z_k]$.

p.s. Have you tried running a particle filter demo under whatever language you happen to be using? Studying a few examples will make learning easier.