A modified cross-entropy algorithm for multiple change-point detection

In a long data sequence, abrupt variations may occur at different locations, dividing the sequence to multiple smaller segments. These abrupt changes may represent the sudden changes in the underlying parameters of a statistical model of the sequence. The problem of detecting these events are typically known as a change-point problem. Change-point problems arise in many different fields including biology (e.g DNA segmentation), financial analysis (e.g stock volatility) and sensor data (e.g pedestrian foot traffic during different times of the year). One method to approach the change-point problem is to apply the Cross-Entropy algorithm, which is a model based evolutionary optimization algorithm. Commonly, the underlying (or sampling) distribution used for the Cross-Entropy algorithm is Gaussian distribution or Beta distribution, which draw samples from an approximate space of the change-point model. This thesis focuses on using the Dirichlet distribution as the underlying distribution, which samples from the exact space of the parameters of change-point model. We compare the accuracy of the proposed algorithm using artificially generated sequences and subsequently apply the method to a real pedestrian sensor data to illustrate the utility of this approach.