Using the minimum description length to discover the intrinsic cardinality and dimensionality of time series

For concreteness, we present a simple scenario that shows the utility of understanding the intrinsic cardinality/dimensionality of data. Suppose we wish to build a time series classifier into a device with a limited memory footprint such as a cell phone, pacemaker or “smartshoe” (Vahdatpour and Sarrafzadeh 2010). Let us suppose we have only 20kB available for the classifier, and that (as is the case with the benchmark dataset, TwoPat Keogh et al. 2006) each time series exemplar has a dimensionality of 128 and takes 4 bytes per value.

One could choose decision trees or Bayesian classifiers because they are space efficient; however, recent evidence suggests that nearest neighbor classifiers can be difficult to beat for time series problems (Ding et al. 2008). If we had simply stored forty random samples in the memory for our nearest neighbor classifier, the average error rate over fifty runs would be a respectable 58.7 % for a four-class problem. However, we could also down-sample the dimensionality by a factor of two, either by skipping every second point, or by averaging pairs of points (as in SAX, Lin et al. 2007), and place eighty reduced-quality samples in memory. Or perhaps we could instead reduce the alphabet cardinality by reducing the precision of the original four bytes to just one byte, thus allowing 160 reduced-fidelity objects to be placed in memory. Many other combinations of dimensionality and cardinality reduction could be tested, which would trade reduced fidelity to the original data for more exemplars stored in memory. In this case, a dimensionality of 32 and a cardinality of 6 allow us to place 852 objects in memory and achieve an accuracy of about 90.75 %, a remarkable improvement in accuracy given the limited resources. As we shall see, this combination of parameters can be found using our MDL technique.

In general, testing all of the combinations of parameters is computationally infeasible. Furthermore, while in this case we have class labels to guide us through the search of parameter space, this would not be the case for other unsupervised data mining algorithms, such as clustering, motif discovery (Lin et al. 2002), outlier discovery (Chandola et al. 2009; Vereshchagin and Vitanyi 2010; Yankov et al. 2008), etc.

As we shall show, our MDL framework allows us to automatically discover the parameters that reflect the intrinsic model/cardinality/dimensionality of the data without requiring external information or expensive cross validation search.

For concreteness, we will consider a simple worked example comparing two possible dimensionalities of data. Note that here we are assuming a cardinality of 16, and a model of APCA. However, in general we do not need to make such assumptions. Let us consider a sample time series \(T\) of length 24:Figure 3 illustrates a plot of \(T\).

We attempt to model this data with a single constant line, a special case of APCA. We begin by finding the mean of all of the data, which (rounding in our integer space) is eight. We can create a hypothesis \(H_{1}\) to model this data, which is shown in Fig. 4. It is simply a constant line with a mean of eight. There are 16 possible values this model could have had. Thus, DL \((H_{1})\) = 4 bits.

Model \(H_{1}\) does not approximate \(T\) well, and we must account for the error.⁴ The errors \(e_{1}\), represented by the length of the vertical lines in Fig. 4, are:As noted in Definition 5, the cost to represent these errors is the correction cost; this is the number of bits encoding \(e_{1 }\)using Huffman coding, which is 82 bits. Thus, the overall cost to represent \(T \)with a one-dimensional model or its reduced description length is:We can now test to see if hypothesis \(H_{2}\), which models the data with two constant lines, could reduce the description length. Figure 5 shows the two segment approximation lines created by APCA.

As we expect, the error \(e_{2}\), shown as the vertical lines in Fig. 5, is smaller than the error \(e_{1}\). In particular, the error \(e_{2}\) is:The number of bits encoding \(e_{2}\) using Huffman coding or the correction cost to generate the time series \(T\) given the hypothesis \(H_{2}\), DL \((T\vert H_{2})\), is 65 bits. Although the correction cost is smaller than one-dimensional APCA, the model cost is larger. In order to store two constant lines, two constant numbers corresponding to the height of each line and a pointer indicating the end position of the first line are required. Thus, the reduced description length of model \(H_{2}\) is:Because we have \(DL\left( {T,H_2 } \right) < DL\left( {T,H_1} \right) \), we prefer \(H_{2}\) for our data.

We are not done yet: we should also test \(H_{3},\; H_{4},\; H_{5}\), etc., corresponding to 3, 4, 5, etc. piecewise constant segments. Additionally, we could also test alternative models corresponding to different DFT or PLA representations and test different cardinalities. For example, suppose we had been given \(T_{2}\) instead:Here, if we tested multiple hypotheses as to the cardinality of this data, we would hope to find that the hypothesis \(H_4^C \) that attempts to encode the data with a cardinality of just 4 would result in the smallest model.

A review of the following facts may help make our contributions more intuitive. The quality of an approximate representation of a time series is measured by the reconstruction error (Ding et al. 2008; Keogh and Kasetty 2003). This is simply the Euclidean distance between the model and the raw data. For example, in Fig. 4 we see the reconstruction error of the single segment model is 18.78, and the reconstruction error of the two segment model in Fig. 5 is just 8.42. This suggests a general truth; for the APCA, PLA, and DFT approximations of time series, it is always the case that the \(d\)-dimensional model has a greater or equal reconstruction error than \(d+1\) dimensional model (Ding et al. 2008; Palpanas et al. 2008). Note that this is only true on average for the DWT, SAX, IPLA, PAA approximations (Ding et al. 2008). However, even for these representations violations to this rule are very rare and minor.

The reader may have noted that in the example discussed, the range of the error vector (i.e. {max(\(e_{i})\)- min(\(e_{i})\)}) also decreased, from 12 (7 to \(-\)4) in the former case, to just 7 (3 to \(-\)3) in the latter. This is not necessarily the case; the relevant algorithms are minimizing the global error of the model, not the maximum error on any individual segment/coefficient, and one can certainly construct synthetic datasets for which this is not the case. However, it is almost always the case, and necessarily so. Recall that as \(d\) approaches \(m\), this range approaches zero. Further note that this range is an upper bound for the number of unique values that the compression algorithm must encode in the description length.

We note that this tight relationship between Euclidean distance and MDL has been observed/exploited before. In Fig. 12 of Rakthanmanon et al. (2012), Rakthanmanon et al. shows a scatterplot illustrating the extraordinary high correlation between the Euclidean distance of pair of subsequences, and the MDL description length when using one subsequence to encode the other (using essentially the same MDL formulation that we use here). Thus we can see the naturalness of using MDL to score our model choice, which is solely concerned with minimizing the Euclidean distance between the model and the original data.

We have just one more issue to address before moving on. We had glossed over this issue to enhance the flow of the presentation above. Consider Fig. 6 which contrasts the original single-segment approximation shown in Fig. 4 with an alternative single-segment approximation.

However, note that the sum of the magnitude of the residuals is much greater in for Fig. 6—right. This is true by definition, as using the mean minimizes this value. However, nothing in our model description length explicitly accounts for this. An obvious solution to this issue is to encode a term that accounts for the range of numbers required to be modeled in the description length, in addition to their entropy. This issue is unique to ordinal data, and does not occur with categorical data. For example, when dealing with categorical data, there is no cost difference between say \(s_{\mathrm{x}} = \mathbf{a \ a \ a \ b,}\) and \(s_{\mathrm{y}} = \mathbf{m\, m\, m\, n }\). However, in our domain there is a significant difference between say \(e_\mathrm{x} = \mathbf{1\, 1\, 1\, 2,}\) and \(e_\mathrm{y} = \mathbf{3\, 3\, 3\, 4,}\) because the latter condemns us to consider values in a \(\hbox {log}_{2}\)(4) range in the description length for the model, whereas the former allows us to only consider values in the smaller \(\hbox {log}_{2}\)(2) range.

In principle, this term is included in the size of \(|\textit{HuffmanTree}(T)|\), but as we noted above, we ignore this term in our model. The problem with Huffman coding is code words in Huffman coding can only have an integer number of bits. Thus the size of \(|\textit{HuffmanTree}(T)|\), does not distinguish between alternative models if we shift the mean up or down a few values. Arithmetic coding can be viewed as a generalization of Huffman coding, effectively allowing non-integer bit lengths. For this reason it tends to offer significantly better compression for small alphabet sizes, and we should expect a good hypothesis to have a small alphabet size by definition. In Fig. 7 we show the effect of considering fractional bits for this problem. Note that the factional bits have a narrow range of 3 to 4, and the Huffman encoding does not make any distinction here.

The reader can now appreciate our why “solution” to this issue was to simply ignore it. Because the underlying dimensionality reduction algorithms we are using (APCA, DFT, PLA) are attempting to minimize the residual error,⁵ they are also implicitly minimizing the range of residuals. As shown by Fig. 7, if we explicitly added a term for the range of residuals it would have no effect, as the dimensionality reduction algorithm has already minimized it.

We have shown a detailed example using APCA. However, essentially all of the time series representations can be encoded in a similar way. As shown with three representative examples in Fig. 8, essentially all of the time series models consist of a set of basic functions (i.e., coefficients) that are linearly combined to produce an approximation of the data.

As we apply our ideas to each representation, we must be careful to correctly “charge” each model for the number of parameters used in the model. For example, each APCA segment requires the mean value and length, whereas PLA segments require the mean value, segment length and slope. Each DFT coefficient can be represented by the amplitude and phase of each sine wave; however, because of the complex conjugate property, we get a “free” coefficient for each one we store (Camerra et al. 2010; Ding et al. 2008). In previous comparisons of the indexing performance of various time series representations, many authors have given an unfair advantage to one representation by counting the cost to represent an approximation incorrectly (Keogh and Pazzani 2000). The ideas in this work explicitly assume a fair comparison. Fortunately, the community seems to have become more aware of this issue in recent years (Camerra et al. 2010; Palpanas et al. 2008).

In the next section we give both the generic version of the MDL model discovery for time series algorithms and three concrete instantiations for DFT, APCA, and PLA.

In the previous section, we used a toy example to demonstrate how to compute the reduced description length of a time series with a competing hypothesis. In this section, we will show a detailed generic version of our algorithm, and then explain our algorithm in detail how we apply our algorithm to the three most commonly used time series representations.

Our algorithm not only discovers the intrinsic cardinality and dimensionality of an input time series, but it can also be used to find the right model or data representation for a given time series. Table 1 shows a high-level view of our algorithm for discovering the best model, cardinality, and dimensionality which will minimize the total number of bits required to store the input time series.

Because MDL is the core of our algorithm, the first step is to quantize a real-valued time series into a discrete-valued (but still fine-grained) time series, \(T\) (line 1). Next, we consider each model, cardinality, and dimensionality one by one (lines 3–5). Then, a hypothesis \(H\) is created based on the selected model and parameters (line 6). For example, a hypothesis \(H\), shown in Fig. 5, is created when the model \(M\) = APCA, cardinality c = 16, and dimensionality d = 2; note that, in that case, the length of the input time series was m = 24.

The reduced description length is finally calculated (line 7), and our algorithm returns the model and parameters that minimize the reduced description length for encoding \(T\) (lines 8–13).

For concreteness, we will now consider three specific versions of our generic algorithm.

As we have seen Sect. 3.1, an APCA model is simple; it contains only constant segments. The pseudo code for APCA, shown in Table 2, is very similar to the generic algorithm. First of all, we quantize the input time series (line 1). Then, we evaluate all cardinalities from 2 to 256 and dimensionalities from 2 to the maximum, which is half of the length of the input time series TS (lines 3–4). Value m denotes the length of the input time series.

Note that if the dimensionality were more than m/2, some segments would contain only one point. Then, a hypothesis \(H\) would be created using the values of cardinality c and dimensionality d, as shown in Fig. 5, where c = 16 and d = 2. The model contains \(d\) constant segments, so the model cost is the number of bits required for storing d constant numbers, and d - 1 pointers to indicate the offset of the end of each segment (line 6). The difference between \(T\) and \(H\) is also required to rebuild \(T\). The correction cost is computed; then the reduced description length is calculated from the combination of the model cost and the correction cost (line 7). Finally, the hypothesis that minimizes this value is returned as an output of the algorithm (lines 8–13).

An example of a PLA model is shown in Fig. 8—right. In contrast to APCA, a hypothesis using PLA is more complex because each segment contains a line of any slope, instead of a constant line in APCA. The algorithm used to discover the intrinsic cardinality and dimensionality for PLA is shown in Table 3, which is similar to the algorithm for APCA, except for the code in line 5 and 6.

A PLA hypothesis \(H\) is created from the external module PLA (line 5). To represent each segment in hypothesis \(H\), we record the starting value, ending value, and the ending offset (line 6). The slope is not kept because storing a real number is more expensive than log \(_{2}\) c.

The first two values are represented in cardinality c and thus log \(_{2}\) c bits are required for each of them. We also require log \(_{2}\) m bits to point to any arbitrary offset in \(T\). Thus, the model cost is shown in line 6. Finally, the reduced description length is calculated and the best choice is returned (lines 8–13).

A data representation in DFT space is simply a linear combination of sine waves, as shown in Fig. 8–left. Table 4 presents our algorithm specific to DFT. After we quantize the input time series to a discrete time series \(T\) (line 1), the external module DFT is called to return the list of sine wave coefficients that represent \(T\). The coefficients in DFT are a set of complex conjugates, so we store only half of all coefficients which contain complex numbers without their conjugate, called half_coef [line 5]. When half_coef is provided, it is trivial to compute their conjugates and obtain all original coefficients.

Instead of using all of half_coef to regenerate \(T\), we test using subsets of them as the hypothesis to approximately regenerate \(T\), incurring an approximation error. We first sort the coefficients by their absolute value (line 6). We use top-d coefficients as the hypothesis to regenerate \(T\) by using InverseDFT (line 8). For example, when d=1 we use only the single most important coefficient to rebuild \(T\), and when d=2 the combination of top-two sine waves are used as a hypothesis, etc. However, it is expensive to use 16 bits for each coefficient by keeping two complex numbers for its real part and imaginary part. Therefore, in line 7, we reduce those numbers to just c possible values (cardinality) by rounding the number to the nearest integer in a space of size c, and we also need a constant number of bits (32 bits) for the maximum and minimum value of both the real parts and the imaginary parts. Hence, the model contains top-d coefficients whose real (and imaginary) parts are in a space of size c. Thus, the model cost and the reduced description length are shown in lines 9 and 10.

For simplicity we placed the external modules APCA, PLA, and DFT inside two for-loops; however, to improve performance, they should be moved outside the loops.

For a given time series \(T\), we want to know the representation that can minimize the reduced description length for \(T\). We have shown how to achieve this goal by applying the MDL principle to three different models (APCA, PLA and DFT). However, for some complex time series, using only one of the above models may not be sufficient to achieve the most parsimonious representation, as measured by bit cost, or by our subjective understanding of the data (Lemire 2007; Palpanas et al. 2008). It has been shown that averaged over many highly diverse datasets; there is not much difference among the different representations (Palpanas et al. 2008). However, it is possible that within a single dataset, the specific model used could make a significant difference. For example, consider each of the two time series that form the trajectory of an automobile as it drives through Manhattan. These time series are comprised of a combination of straight lines and curves. We could choose just one of these possibilities, either representing the automobile’s turns with many piecewise linear segments, or representing the long straight sections with a degenerate “curve.” However, a mixed polynomial degree model is clearly more natural here.

For clarity, we show a toy example that can benefit from a mixed polynomial degree model in Fig. 9. It is easy to observe that there are constant, linear and quadratic patterns in this example. In Sects. 4.9 and 4.10, we further demonstrate the utility of our ideas on real datasets (Keogh et al. 2011; Lemire 2007; National Aeronautics and Space Administration 2011).

Several works propose that it may be fruitful to use a combination of different models within one time series (Keogh et al. 2011; Lemire 2007; Palpanas et al. 2008). For example, Lemire (2007) proposes a mixed model wherein the polynomial degree of each interval in one time series can vary. The polynomial degree can be zero, one, two or higher. The goal of Lemire (2007) is to minimize the Euclidean error between the model and the original data for a given number of segments. However, note that Lemire (2007) requires the user to state the desired dimensionality, something we obviously wish to avoid. Minimizing the Euclidean error between the model and the original data is a useful objective function for some tasks, but it is not necessarily the same as discovering the intrinsic dimensionality, which is our stated goal. In the following, we show that our proposed algorithm returns the intrinsic model by minimizing the reduced description length using MDL. Moreover, our algorithm is essentially parameter-free.

We propose a mixed model framework using MDL that optimizes a mixture of constant, linear and quadratic representations for different local regions of a single time series. In this case, the operator space of the segmentation algorithm (Table 6) becomes larger. Table 5 shows a high-level view of the algorithm. Lines 1–4 are similar to the algorithm for APCA and PLA. The function in line 5 is the return for the \(d\) segments with the hypothesis H, the model cost and the starting point of each segment. Table 6 illustrates how the bottom-up mixed polynomial degree algorithm works in detail. Each segment is represented by a different polynomial degree to minimize the reduced description length. The model costs for constant, linear and quadratic representations are log\(_{2}\) c bits, 2*log\(_{2}\) c bits and 3*log\(_{2}\) c bits, respectively. For example, if \(c\) is 256, the model costs for the above three representations are 8 bits, 16 bits and 24 bits, respectively. In line 7, In addition to the total model cost of all of the segments, the model cost of the whole time series needs to use extra bits to store the starting point of each segment. Observe that the model cost for a segment is independent of the length of the segment. More specifically, the model cost for each segment is only determined by the polynomial degree of the representation and the cardinality c.

Table 6 shows the bottom-up mixed polynomial degree model algorithm. By choosing the minimum description costs as the objection function, the algorithm shown in Table 6 is a generalization of the bottom-up algorithm for generating the PLA introduced in Keogh et al. (2011). There are two main differences between our bottom-up mixed model algorithm and the bottom-up algorithm described in Keogh et al. (2011). The first is a minor pragmatic point: instead of using two points in the finest possible approximation, the algorithm shown in Table 6 uses three points. This is because when the polynomial degree of the representation is two, the number of points by using this approximation must be at least three. Second, instead of using Euclidean distance as the objective function, the algorithm in Table 6 uses MDL cost. The algorithm calculates the MDL costs for three degrees of polynomial degree representations for a segment. The polynomial degrees are zero, one and two, respectively. Next, it chooses the one that can minimize the cost (the description length). The algorithm begins by creating the finest possible approximation of the input time series. So for a length of n time series, there are n/3 segments after this step, as shown in Table 6, lines 2–4. Then the cost of merging each pair of adjacent segments is calculated, as shown in lines 5–7. To minimize the merging cost for the two inputsegments, this calculate_MDL_cost function calculates the MDL costs for three kinds of polynomial degree representations, and then chooses the minimum one as the merging cost (line 6). After this step, the algorithm iteratively merges the lowest cost pair until a stopping criterion is met. In this scenario, the stopping criterion is the input number of segments. This means that the algorithm will not terminate as long as the current number of segments is larger than the input number of segments.

It is important to note that, similar to the algorithm (Keogh et al. 2011), our algorithm is greedy in the sense that once two regions have been joined together in a single segment, they will remain together in that segment (which may get larger as it is iteratively joined with other segments). There are only join operators; there are no split operators. However, if a region in our algorithm is initially assigned to a polynomial of a particular degree, this does not mean it cannot later be subsumed into a larger segment of a different degree. In other words, a tiny region that locally may consider itself, say, linear has the ability to later become part of a constant or quadratic segment as it obtains a more “global” view.

We start with a simple sanity check on the classic problem specifying the correct time series model, cardinality and dimensionality, given an observation of a corrupted version of it. While this problem has received significant attention in the literature (Donoho and Johnstone 1994; Salvador and Chan 2004; Sarle 1999), our MDL method has two significant advantages over existing works. First, there is no explicit parameter to set, whereas most other methods require several parameters to be set. Second, MDL helps to specify the model, cardinality and dimensionality, whereas other methods typically only consider the model and/or dimensionality.

To eliminate the possibility of data bias (Keogh and Kasetty 2003) we consider a ten-year-old instantiation (Sarle 1999) of a classic benchmark problem (Donoho and Johnstone 1994). In Fig. 10 we show the classic Donoho–Johnstone block benchmark. The underlying model used to produce it consists of 12 piecewise constant sections with Gaussian noise added.

The task is challenging because some of the piecewise constant sections are very short and thus easily dismissed during a model search. Dozens of algorithms have been tested on this time series (indeed, on this exact instance of data) in the last decade: which should we compare to? Most of these methods have several parameters, in some cases as many as six (Firoiu and Cohen 2002; García-López and Acosta-Mesa 2009). We argue that comparisons to such methods are inappropriate, since our explicit aim is to introduce a parameter-free method. The most cited parameter-free method addressing this problem is the L-Method (Salvador and Chan 2004). In essence, the L-Method is a “knee-finding” algorithm. It attempts to explain the residual error vs. size-of-model curve using all possible pairs of two regression lines. Figure 11—top shows one such pair of lines, from one to ten and from eleven to the end. The location that produces the minimum sum of the residual errors of these two curves, R, is offered as the optimal model. As we can see in Fig. 11—bottom, this occurs at location ten, a reasonable estimate of the true value of 12.

We also tested several other methods, including a recently-proposed Bayesian Information Criterion-based method that we found predicted a too coarse four-segment model (Zhao et al. 2008). No other parameter-free or parameter-lite method we found produced intuitive (much less correct) results. We therefore omit further comparisons in this paper (however, many additional experiments are available at www.​cs.​ucr.​edu/​~bhu002/​MDL/​MDL.​html).

We solve this problem with our MDL approach. Figure 12 shows that of the 64 different piecewise constant models it evaluated, MDL selected the 12-segment model, which is the correct answer.

The figure above uses a cardinality of 256, but the same answer is returned for (at least) every cardinality from 8 to 256.

Beyond outperforming other techniques at the task of finding the correct dimensionality of a model, MDL can also find the intrinsic cardinality of a dataset, something for which methods (Salvador and Chan 2004; Zhao et al. 2008) are not even defined. In Fig. 13 we have repeated the previous experiment, but this time fixing the dimensionality to 12 as suggested above, and testing all possible cardinality values from 2 to 256.

Here MDL indicates a cardinality of ten, which is the correct answer (Sarle 1999). We also re-implemented the most referenced recent paper on time series discretization (García-López and Acosta-Mesa 2009). The algorithm is stochastic, and requires the setting of five parameters. In one hundred runs over multiple parameters we found it consistently underestimated the cardinality of the data (the mean cardinality was 7.2).

Before leaving this example, we show one further significant advantage of MDL over existing techniques. Both Salvador and Chan (2004) and Zhao et al. (2008) try to find the optimal dimensionality, assuming the underlying model is known. However, in many circumstances we may not know the underlying model. As we show in Fig. 14, with MDL we can relax even this assumption. If our MDL scoring scheme is allowed to choose over the cross product of model = {APCA, PLA, DFT}, dimensionality = {1 to 512} and cardinality = {2 to 256}, it correctly chooses the right model, dimensionality and cardinality.

The Muscle dataset studied by Mörchen and Ultsch (2005) describes the muscle activation of a professional inline speed skater. The authors calculated the muscle activation from the original EMG (electromyography) measurements by taking the logarithm of the energy derived from a wavelet analysis. Figure 15—top shows an excerpt. At first glance it seems to have two states, which correspond to our (perhaps) naive intuitions about skating and muscle physiology.

We test this binary assumption by using MDL to find the model, dimensionality and cardinality. The results for the model and dimensionality are objectively correct, as we might have expected given the results in the previous section, but the results for cardinality, shown in Fig. 16—left, are worth examining.

Our MDL method suggests a cardinality of three. Glancing back at Fig. 15—bottom shows why. At the end of the stroke there is an additional level corresponding to an additional push-off by the athlete. This feature was noted by physiologists who worked with Mörchen and Ultsch (2005). However, their algorithm weakly predicts a value of four.⁶ Here, once again we find the MDL can outperform this latter approach, even though Mörchen and Ultsch (2005) acknowledges that their reported result is the best obtained after some parameter tuning using additional data from the same domain.

In this section (and the one following) we consider the possible utility of MDL scoring as an anomaly detector. Building an anomaly detector using MDL is very simple. We can simply record the best model, dimensionality and/or cardinality predicted for the training data, and then test on future observations that have significantly different learned parameters. We can illustrate this idea with an example in astronomy. We begin by noting that we are merely demonstrating an additional possible application of our ideas. We are only showing that we can reproduce the utility of existing works. However note that our technique is at least as fast as existing methods (Protopapas et al. 2006; Rebbapragada et al. 2009), and does not require any training data or parameter tuning, an important advantage for exploratory data mining.

Globally there are hundreds of telescopes covering the sky and constantly recording massive amounts of astronomical data (Protopapas et al. 2006). Moreover, there is a worldwide effort to digitize tens of millions of observations recorded on formats ranging from paper/pencil to punch cards over the last hundred years. Having humans manually inspect all such observations is clearly impossible (Malatesta et al. 2005). Therefore, outlier detection can be useful to catch anomalous data, which may indicate an exciting new discovery or just a pedestrian error. We took a collection of 1,000 hand-annotated RRL variable stars (Protopapas et al. 2006; Rebbapragada et al. 2009), and measured the mean and standard deviation of the DFT dimensionality, which turned out to be 22.52 and 2.12, respectively. As shown in Fig. 17—top, the distribution is Gaussian.

We then took a test set of 8,124 objects, known to contain at least one anomaly, and measured the intrinsic DFT dimensionality of all of its members, and discovered that one had a value of 31. As shown in Fig. 17—bottom, the offending curve looks different from the other data, and is labeled RRL_OGLE053803.42-695656.4.I.folded ANOM. This curve is a previously known anomaly. In this case, we are simply able to reproduce the anomaly finding ability of previous work (Protopapas et al. 2006; Rebbapragada et al. 2009). However, we achieved this result without extensive parameter tuning, and we can do so very efficiently.

In this section we show how MDL can be used to mine ECG data. Our intention is not to produce a definitive method for this domain, but simply to demonstrate the utility and generality of MDL. We conducted an experiment that is similar in spirit to the previous section. We learned the mean and standard deviation of the DFT dimensionality on 200 normal heartbeats, finding them to be 20.82 and 1.70, respectively. As shown in Fig. 18—top, the distribution is clearly Gaussian. We used these learned values to monitor the rest of the data, flagging any heartbeats that had a dimensionality that was more than three standard deviations from the mean. Figure 18—bottom shows a heartbeat that was flagged by this technique.

Once again, here we are simply reproducing a result that could be produced by other methods (Yankov et al. 2008). However, we reiterate that we are doing so without any parameter tuning. Moreover, it is interesting to note when our algorithm does not flag innocuous data (i.e., produces false positives). Consider the two adjacent heartbeats labeled A and B in Fig. 18—bottom. It happens that the completely normal heartbeat B has significantly more noise than heartbeat A. Such non-stationary noise presents great difficulties for distance-based and density-based outlier detection methods (Yankov et al. 2008), but MDL is essentially invariant to it. Likewise, the significant wandering baseline (not illustrated) in parts of this dataset has no medical significance and is ignored by MDL, but it is the bane of many EEG anomaly detection methods (Chandola et al. 2009).

Global-scale Earth observation satellites such as the Defense Meteorological Satellite Program (DMSP) Special Sensor Microwave/Imager (SSM/I) have provided temporally detailed information about the Earth’s surface since 1978, and the National Snow and Ice Data Center (NSIDC) in Boulder, Colorado makes this data available in real time. Such archives are a critical resource for scientists studying climate change (Picard et al. 2007). In Fig. 19, we show a brightness temperature time series from a region in Antarctica, using SSM/I daily observations over the 2001–2002 austral summer.

We used MDL to search this archive for low complexity annual data, reasoning that low complexity data might be amenable to explanation. Because there is no natural starting point for a year, for each time series we tested every possible day as the starting point. The simplest time series we discovered required a piecewise constant dimensionality of two with a cardinality of two, suggesting that a very simple process created the data. Furthermore, the model discovered (piecewise constant) is somewhat surprising, since virtually all climate data is sinusoidal, reflecting annual periodicity; thus, we were intrigued to find an explanation for the data.

In this section we show two applications of our algorithm in hydrological and environmental domains.

The first application is the hydrology data studied by Kehagias (2004) describing the annual discharge rate of the Senegal River. This data was measured at Bakel station from the year 1903 to 1988 (Kehagias 2004), as shown in Fig. 20.

The authors of Kehagias (2004) reported the optimal segmentation occurs when the number of segments is five using a Hidden Markov Model (HMM)-based segmentation algorithm, as shown in Fig. 21—top.

As illustrated in Fig. 21—bottom, we get a similar plot by hard coding the number of segments to five, using the MDL-based APCA algorithm shown in Table 2. However, as shown in Fig. 22, our MDL algorithm actually predicts two as its intrinsic dimensionality of data in Fig. 20. Note that there is no ground truth for this problem.⁷ Nevertheless, for the Donoho–Johnstone block benchmark dataset that has ground truth in Sect. 4.1, we have correctly predicted its intrinsic dimensionality, and we would argue that the two-segment solution shown in Fig. 22 is at least subjectively as plausible as the five segment solution.

Below we consider an application of our algorithm in a similar domain in environmental data. The data we consider is the time series of the annual global temperature change from the year 1700 to 1981 (Kehagias 2004), as shown in Fig. 23.

In Kehagias (2004) the authors suggest that the optimal segmentation occurs when the number of segments is four, as shown in Fig. 24—top.

As illustrated in Fig. 24—bottom, using the algorithm in Table 2, we obtain a very similar plot by hard coding the number of segments to four. As before there is no external ground truth explanation as to why the optimal segmentation of this global annual mean temperature time series should be four. However, as shown in Fig. 25, our MDL algorithm predicts that the intrinsic dimensionality of the global temperature change data is two. Here, there is at least some tentative evidence to support our two segment model. Research done by Linacre and Geerts (2011), National Aeronautics and Space Administration (2011) and US Environmental Protection Agency (2011) suggests that there was a global temperature rise between 1910 and 1940. To be more precise, this period of rapid warming was from 1915 to 1942 (Linacre and Geerts 2011; US Environmental Protection Agency 2011). Moreover, there were no significant temperature changes after 1700 other than during this rapid warming period.

In Bronson et al. (2009), the authors also proposed an HMM-based approach (distinct from, but similar in spirit to that described in Kehagias (2004) and discussed in the previous section) to segment the time series from single-molecule Förster resonance energy transfer (smFRET) experiments. Figure 26 shows a time series from the smFRET experiment (Bronson et al. 2009; vbFRET Toolbox 2012).

The authors in Bronson et al. (2009) noted that there are biophysical reasons to think that the data is intrinsically piecewise constant, but the number of states is unknown. Their method suggests that there are three states in the above time series, as shown in Fig. 27—top). We obtain the same results, as our algorithm finds that the intrinsic cardinality for the data in Fig. 26 is also three using the algorithm in Table 2. Figure 27—bottom illustrates our approach. However, there are several parameters in the HMM-based approach used by Bronson et al. (2009). Moreover, their approach iteratively finds the number of states with the maximum likelihood, which results in a very slow algorithm. In contrast, our algorithm is parameter-free and significantly faster. Note that we do not even have to have the assumption (made by Bronson et al. 2009) that the data is piecewise constant. The mixed polynomial algorithm introduced in Sect. 3.6 considered and discounted a linear, quadratic or mixed polynomial model to produce the model shown in Fig. 27—bottom.

In this section, we demonstrate our framework’s ability to aid in clustering problems.

Recently, the field of prognostics for engineering systems has attracted a huge amount of attention due to its ability to provide an early warning for system failures, forecast maintenance as needed, and estimate the remaining useful life of a system (Goebel et al. 2008; Prognostics Center of Excellence, National Aeronautics and Space Administration (NASA) 2012; Vachtsevanos et al. 2006; Wang et al. 2008; Wang and Lee 2006). Data-driven prognostics are more useful than model-driven prognostics, since a model-driven prognostic requires incorporating a physical understanding of the systems (Goebel et al. 2008). This is especially true when we have access to large amounts of data, a situation that is becoming more and more common.

There may be thousands of sensors in a single engineering system. Consider, for example, a typical oil-drilling platform that can have 20,000–40,000 sensors on board (IBM 2012). All of these sensors stream data about the health of the system (IBM 2012). Among the huge number of variables, there are some variables called operational sensors that have a substantial effect on system performance. In order to do a prognostic analysis, first the operational variables should be filtered from the non-operational variables that are just responding to the operational ones (Wang et al. 2008).

We analyzed the Prognostics and Health Management Challenge (PHM08) dataset which contains data from 233 different engines (PHM Data Challenge Competition 2008; Prognostics Center of Excellence, National Aeronautics and Space Administration (NASA) 2012). Each engine has data from around 900 engine cycles for one aircraft. Each engine cycle represents one aircraft flying from one destination to another. Figure 28 implies that the data from the operational variable and the non-operational variable are visually very similar.

The defined task here is to cluster the operational variables and non-operational variables into two groups. For ease of exposition, we only consider one variable in each group. Nevertheless, our framework can be easily extended to multivariate problems. We calculate the intrinsic cardinality and the reduced description length for one operational variable and one non-operational variable from all of the 233 engines. One marker in Fig. 29 represents one variable from one engine.

Although data from the two kinds of variables look very similar (Fig. 28), our results in Fig. 29 show that there is a significant difference between them: the operational variables lie in the lower left corner of Fig. 29 with low cardinalities and small reduced description lengths. In contrast, the non-operational variables lie in the upper right corner of Fig. 29 with high cardinalities and large reduced description lengths. This implies that the data from the operational variables is relatively ‘simple’ compared to the data from the non-operational variables, since the intrinsic cardinalities and reduced description lengths of the data from the operational variables are relatively small. This result was confirmed by a Prognostics expert: the hypothesis for filtering out the operational variables is that data from operational variables tends to have simpler behavior, since there are only several crucial states for the engines (Heimes and BAE Systems 2008; PHM Data Challenge Competition 2008; Prognostics Center of Excellence, National Aeronautics and Space Administration (NASA) 2012; Wang et al. 2008; Wang and Lee 2006). Note that in our experiment we did not need to tune any parameters, while most of the related literature for this dataset use multi-layer perceptron neural networks (Heimes and BAE Systems 2008; Wang et al. 2008; Wang and Lee 2006), which have the overhead of parameter tuning and are prone to overfitting.

In Sect. 3.6 we introduced an algorithm for finding mixed polynomial degree models for a time series. In this section, we demonstrate the application of our proposed algorithm to the synthetic time series shown in Fig. 9. As shown in Fig. 30, we calculated its intrinsic dimensionality using the algorithms in Tables 5 and 6. The minimum cost occurs when the dimensionality is eight.

Figure 31 shows the data and its intrinsic mixed polynomial degree representations. In Fig. 31—bottom, we observed that there are four constant segments, two linear segments and two quadratic segments, which correctly reflects how we constructed this toy data.

Having demonstrated the mixed polynomial degree model on a toy problem, we are now ready to consider a real-world dataset. The Space Shuttle dataset contains time series produced by the inertial navigation system error correction system, as shown in Fig. 32.

Using only one approximation to represent the time series like the ones in Fig. 32 does not achieve a natural segmentation, since the data itself is intrinsically composed of more than one state. We applied the mixed polynomial degree algorithm in Tables 5 and 6 to the data shown in Fig. 32. The algorithm returns different polynomial degrees for different segments, as demonstrated in Fig. 33. We observe that there are three different states in both of the two time series shown in Fig. 32. An understanding of the processes that produced this data seems to support this result (Keogh et al. 2006).

We conclude this section with a set of quantifiable experiments that explicitly allow us to demonstrate the robustness of our algorithm to various factors that can cause it to fail. In every case, we push our algorithm passed its failure point, and by archiving all data (www.​cs.​ucr.​edu/​~bhu002/​MDL/​MDL.​html) we establish baselines for researchers to improve on our results. We are particularly interested in measuring our algorithms sensitivity to:To test these issues we created modifications of the Donoho–Johnstone block benchmark (Sarle 1999). Our version is essentially identical to the version shown in Fig. 10, except it initially has no noise. We call this initial prototype signal \(P\). After adding various distortions/modifications to the data, we can measure the success of our algorithm in three ways:As shown in Fig. 34 our strategy is to begin with an easy case for our algorithm and progressively add more distortion until both the cardinality and dimensionality predictions fail. Concretely:

The results in Fig. 34 suggest our algorithm is quiet robust to these various distortions. To give the reader a better appreciation of when our algorithm fails, in Fig. 35 we show the most corrupted version of the signals for which our algorithm correctly predicted either the cardinality or the dimensionality.

It is important to reiterate that the experiment that added a linear trend to the data but only considered a constant model was deliberately testing the mismatch between assumptions and reality. In particular if we repeat the technique shown in Fig. 14, of testing over all models spaces in {DFT, APCA, PLA}, our algorithm does correctly predict the data in Fig. 35c as consisting of piecewise linear segments, and still correctly predicts the cardinality and the dimensionality.