Suppose that I have a sequence of vectors $y_n \in \mathbb{R}^m$ for $n \in \{1, \dots, N\}$. My goal is to divide $y_n$ in $K$ clusters and want my clusters to satisfy the following conditions:

  1. Each $y_n$ belongs to exactly one cluster $x_n \in \{1, \dots, k\}$, which is unknown.
  2. The clusters form a Markov chain $p(x_n|x_1, \dots, x_{n-1}) = p(x_n|x_{n-1}),$ but we don't know the transition probabilities $p(x_n|x_{n-1})$.

The main difference between this clustering problem and conventional clustering problems is the Markov condition on the clusters that has to be satisfied. This problem also differs (and somewhat simpler) from hidden Markov model (HMM) formulation because we know that each $y_n$ exactly belongs to one cluster but in HMMs this is not true. We also don't have access to emission probabilities $p(y_n|x_n)$.

How is this problem solved? Can one extend for example k-means to this problem?



Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.