Segmentation

LA home
Computing
 Algorithms
 Bioinformatics
 FP,  λ
 Logic,  π
 MML
 Prog.Langs

FP
 II
  Ver.1.1
   Seg

DPA

Given a series of data, [d0, d1, ..., dn-1], does it consist of one, two [[d0, ..., di], [di+1, ..., dn-1]], or more segments, where each segment is homogeneous in some way? This problem is a special case of unsupervised classification because here the members of a segment ("class") must be contiguous. The number of segments and their boundaries must be learned.

Given an estimator, est, we can estimate a model for each (hypothetical) segment, calculate the message-length of each segment and its model, include the encoding of the segment "cut-points", and thus cost a segmentation. The best segmentation is the one having the shortest total message length.

W.D.Fisher (1958) gave an O(K.n2)-time algorithm to find the best segmentation having exactly K segments, but gave no "stopping criterion" to determine the best K.

If we can break the total segmentation cost into the sum of the cost of each segment, [di+1, ..., dj] where j>i, we can use the 1-dimensional [dynamic programming algorithm] (DPA). Such a break-down requires stating: the length of each segment, the parameters of each segment (to appropriate precision), and the segment's members (the data) given those parameter estimates. This break-down is an approximation to the true cost of the segmentation because it omits the number of segments (small), and states the lengths of all segments which is redundant if the length of the series is common knowledge[*]. However these discrepancies are small. (And they can be removed by using Fisher's algorithm with our costs but then we have to try K=1, 2, ..., Kmax.)

edgeCost est dataSet =
 let n = length dataSet
     lrCosts = ...
      ... cost = nlPr wallaceIntModel (r-l) + msg segModel seg
      ...                    -- NB seg is elts l..r of dataSet
 in \i -> \j -> lrCosts !! (i+1) !! (j-i-1)

segment est dataSet =
 let ...
     (path,c) = dpa1D (-1) (length dataSet - 1) (edgeCost est dataSet)
     bounds   = zip (map ((+)1) path) (drop 1 path)
     segments = map (\(l,r) -> take (r-l+1) (drop l dataSet)) bounds
 ...
7/12/2005

The natural null-hypothesis is to apply the estimator to fit a single model to all of the data in the whole series.

The segmentation algorithm can be applied to any type of data -- univariate, multivariate, discrete, continuous, mixed, correlated or not -- provided only that the estimator, est, and the dataSet agree about that type.

The DPA takes O(n2)-time if the cost of each segment can be calculated in constant time.

Also see


[*] A way to "balance the books" is for the null-hypothesis to include the cost of stating the length of the series.
window on the wide world:

Computer Science Education Week

Linux
 Ubuntu
free op. sys.
OpenOffice
free office suite,
ver 3.4+

The GIMP
~ free photoshop
Firefox
web browser
FlashBlock
like it says!

© L. Allison   http://www.allisons.org/ll/   (or as otherwise indicated),
Faculty of Information Technology (Clayton), Monash University, Australia 3800 (6/'05 was School of Computer Science and Software Engineering, Fac. Info. Tech., Monash University,
was Department of Computer Science, Fac. Comp. & Info. Tech., '89 was Department of Computer Science, Fac. Sci., '68-'71 was Department of Information Science, Fac. Sci.)
Created with "vi (Linux + Solaris)",  charset=iso-8859-1,  fetched Saturday, 23-Aug-2014 15:32:04 EST.