Early Classification of Time Series. Cost-based Optimization Criterion
  and Algorithms
  An increasing number of applications require to recognize the class of an
incoming time series as quickly as possible without unduly compromising the
accuracy of the prediction. In this paper, we put forward a new optimization
criterion which takes into account both the cost of misclassification and the
cost of delaying the decision. Based on this optimization criterion, we derived
a family of non-myopic algorithms which try to anticipate the expected future
gain in information in balance with the cost of waiting. In one class of
algorithms, unsupervised-based, the expectations use the clustering of time
series, while in a second class, supervised-based, time series are grouped
according to the confidence level of the classifier used to label them.
Extensive experiments carried out on real data sets using a large range of
delay cost functions show that the presented algorithms are able to
satisfactorily solving the earliness vs. accuracy trade-off, with the
supervised-based approaches faring better than the unsupervised-based ones. In
addition, all these methods perform better in a wide variety of conditions than
a state of the art method based on a myopic strategy which is recognized as
very competitive.
