Database Reference
In-Depth Information
•
Linear Interpolation:
Here the approximating line for the subsequence
T
[
a
b
t
a
and
t
b
. This can be obtained in
:
] is simply the line connecting
constant time.
•
Linear Regression:
Here the approximating line for the subsequence
T
[
] is taken to be the best fitting line in the least squares sense
[Shatkay (1995)]. This can be obtained in time linear in the length of
segment.
a
:
b
The two techniques are illustrated in Figure 2. Linear interpolation
tends to closely align the endpoint of consecutive segments, giving the piece-
wise approximation a “smooth” look. In contrast, piecewise linear regression
can produce a very disjointed look on some datasets. The aesthetic superi-
ority of linear interpolation, together with its low computational complex-
ity has made it the technique of choice in computer graphic applications
[Heckbert and Garland (1997)]. However, the quality of the approximating
line, in terms of Euclidean distance, is generally inferior to the regression
approach.
In this chapter, we deliberately keep our descriptions of algorithms at a
high level, so that either technique can be imagined as the approximation
technique. In particular, the pseudocode function
create segment(T)
can
be imagined as using interpolation, regression or any other technique.
All segmentation algorithms also need some method to evaluate the
quality of fit for a potential segment. A measure commonly used in conjunc-
tion with linear regression is the sum of squares, or the residual error. This is
calculated by taking all the vertical differences between the best-fit line and
the actual data points, squaring them and then summing them together.
Another commonly used measure of goodness of fit is the distance between
the best fit line and the data point furthest away in the vertical direction
Linear
Interpolation
Linear
Regression
Fig. 2. Two 10-segment approximations of electrocardiogram data. The approxima-
tion created using linear interpolation has a smooth aesthetically appealing appearance
because all the endpoints of the segments are aligned. Linear regression, in contrast, pro-
duces a slightly disjointed appearance but a tighter approximation in terms of residual
error.
