It is not easy to apply standard Machine Learning methods to time-series classi cation because of the nature of the data. k-Nearest Neighbour (k-NN) can be applied because e ective distance measures for time-series are available (e.g. Dynamic Time Warping (DTW)). However, these e ective measures are inclined to be quite computationally expensive { DTW is O(t2) in the length of the time-series. This is a problem because the resultant retrieval time is O(nt2) when n is the number of training samples. Methods to improve k-NN retrieval performance exist, but some constraints apply. Some methods require that the distance measure is a proper metric; others are only e ective in low dimension spaces. In this paper, we evaluate the e ectiveness of Navigable Small Worlds (NSW) for time-series classi cation using k-NN. NSW organises training samples into a small-world network for e cient retrieval. We show that this strategy can signi cantly speed up time-series classi cation at the cost of some loss of accuracy.
Time-series classi cation is a particular challenge for supervised machine
learning because the data is not in a feature vector format. A comprehensive
evaluation of ML methods for time-series classi cation [
In this paper, we assess the potential of using Navigable Small Worlds for k-NN in time-series classi cation. With NSW, the data is organised into a smallworld graph that facilitates e cient retrieval. Small-world networks have the special characteristic that any pair of nodes is likely to be linked by a small number of hops. This property is due to the presence of hubs in the network. Hubs are high-degree nodes that serve as a routing backbone that delivers short shortest path distances. With NSW this small-world characteristic arises naturally from the way the network is constructed (see details in section 4.1).
So NSW can be used as a data-structure to provide approximate k-NN
retrieval (see Figure 3). While most of the research on NSW for approximate
nearest neighbour retrieval is based on proper metrics, the authors do claim
that it might also be e ective for non-metric spaces [
In the next section, we provide an overview of k-NN and time-series classi cation illustrating the computational challenges. In section 3, we review relevant research on k-NN speedup. In section 4, we introduce NSW and show how it can be used for k-NN retrieval. Our results on using NSW to speed up k-NN time-series classi cation are presented in section 5. 2
k-NN and Time-Series Classi cation k-NN works by nding the nearest neighbours for a query q in training set D and then a class is assigned to q using these neighbours, typically by majority voting. If the data is numeric, D is made up of samples of the form x = fx1; :::; xj ; :::; xmg. For each x 2 D the Euclidean distance between q and x is:
vu m d(q; x) = tuX(qi i=1 xi)2
If two time-series are the same length, then Euclidean distance can be used
as a distance measure. However, as we see in Figure 1, if the two time-series are
a little out of phase, then the Euclidean distance can be misleading. The vertical
lines in the plot on the left indicate this. So there has been extensive research
on similarity/distance measures for time-series [
(1)
In our research, we are particularly interested in the use of time-series classi
cation for process monitoring in manufacturing. We are concerned with the use
of time-series classi cation to detect processing anomalies in metal 3D printing
[
The details of the two datasets are summarised in Table 1. Each data sample is a time-series of melt-pool temperature recorded by a pyrometer. The classi cation task is to detect pores in the part being manufactured. These pores would be rare but would typically show up as dips in the temperature time-series. The longest time-series in both datasets contain 300 time points and the shortest 101. When calculating distance the shorter series is post-padded with zeroes to bring it to the length of the longer one. A trailing zero is added to the longer series to allow matching with this padding.
To compare the time complexity of the three distance measures, we computed the average retrieval time of 10 random queries in a k-NN environment using
the PLarge dataset. The average retrieval time for each measure (given best parameters) per query are as follows: { Euclidean2: 0.02 s { DTW3: 1.46 s { TWED4: 10.16 s
As expected, Euclidean distance is the fastest by two orders of magnitude, DTW the second, and TWED the slowest of them all. 3
k-NN Speedup Strategies These baseline calculations illustrate the run-time problems with k-NN. The performance with Euclidean distance might be acceptable, but the DTW and TWED gures are not adequate for real-time analysis. This is a recognised problem with k-NN and has been the subject of extensive research. This research can be categorised under exact methods and approximate methods. Exact methods will guarantee that the neighbours retrieved by brute force search will be precise. Approximate methods don't meet this requirement.
Exact Methods The two most popular alternatives to brute force search for
exact k-NN are Ball Trees and Kd-Trees [
Network
k-NN
NSW
{ Neighbourhood-Based Methods index the data by building a proximity
graph where data points are linked to their neighbours. Retrieval entails
navigating this proximity graph to nd nearest neighbours for a query. NSW
is such a method but with the special characteristic that the graph is a
smallworld graph (see section 4). A recent evaluation by Li et al. [
NSW
& k-NN NSW is a neighbourhood-based method for ANN that constructs a proximity graph that has small-world characteristics. This is illustrated in Figure 2 and Table 2. We compare an NSW graph with a standard k-NN graph. The k-NN graph is constructed by connecting each node to its f = 233 nearest neighbours (parameter setting details are in section 4.2). The NSW graph is constructed using the strategy detailed in section 4.1. The statistics in Table 2 show that the NSW graph is more compact than the k-NN graph; this is due to the high-degree hub nodes on the right in Figure 2(a). 4.1
NSW uses a small-world network that can be represented by a graph G(V; E),
where vertices from set V are the stored elements, and edges from set E are
connections linking them with other vertices. The NSW structure is constructed
by inserting elements into the network consecutively[
Algorithm 1 Insertion Algorithm procedure NN Insert(element; f; m) . m multi-searches to nd f neighbours to connect with element neighbours N N Search(element; f; m) for neighbour in neighbours do element:connect(neighbour) neighbour:connect(element)
Store the new and updated elements in the network
NSW employs a variant of the greedy search algorithm as its core k-NN search to fetch approximate neighbours of the object. At rst, a random node is selected from the network as an entry point (see Figure 3), and then search progress by traversing the network from one element to its unvisited nearest neighbouring element. The exploration continues within the neighbourhood of the nearest objects in a greedy style until it no longer improves the already known k nearest neighbours (stop condition) or has an unvisited object left to explore (see Algorithm 2). On identifying a set of neighbours, the algorithm inserts the element into the network by connecting it to its neighbours and vice versa. This incremental strategy has the important side-e ect that long-distance links are created early on in the construction process because true nearest neighbours are not present. This results in small-world characteristics.
We used ValueSortedDict from the sortedcollections5package in the PyPI repository, as the data-structure for our implementation of NSW for storage and retrieval of neighbours. This signi cantly improves performance because there is a lot of sorting required for network traversal.
procedure NN Search(query; k; m) . m searches to nd k neighbours of a query Set visited set . maintains list of visited nodes ValueSortedDict candidates; result for iteration m do v ep random entry point . Fetch a random node from the network visited set; candidates v ep ValueSortedDict temp result while True do candidate nearest candidate(candidates) . from candidates pool if stop condition = F alse and candidate has neighbours then for neighbour in candidate:neighbours do if neighbour not in visited set then cost distance(query; neighbour) visited set; candidates; temp result neighbour else
break while loop result temp result Return k nearest neighbours from result . result is updated with temp result
Two parameters f and m dictate the performance of the NSW algorithm. f determines the maximum number of \friends" or neighbours, a vertex can have in the network, and m dictates multi-search. m is directly proportional to the recall of the system, where a high enough m results in the perfect recall; however, it is then similar to an exhaustive search. Hence, there is a trade-o between classi cation accuracy and the speed-up accomplished by the model, governed by its parameters. 4.2
Before applying NSW to time-series data, we present a baseline analysis on feature vector data. For this, we have selected six public datasets from the KEEL6 repository for classi cation tasks. As previously mentioned, selecting optimal values for f and m is essential, owing to the trade-o between accuracy and time complexity of the NSW model. The idea is to obtain a high accuracy while keeping f and m small for a quicker retrieval time. This is achieved through a grid-search, as shown in Figure 4. When supplied with a pair of values, the models undergo 5 5-fold cross-validation over the train set of a dataset, with accuracy as its scoring method. The heatmap generated illustrates the e ect of
6 https://sci2s.ugr.es/keel/datasets.php (a) Parameter heatmap of NSW over newthyroid dataset. (b) Parameter heatmap of NSW over pima dataset. f and m on the accuracy of the model. Fig. 4 show heatmaps for two datasets. It is clear that higher values of f and m give better accuracy, but it is possible to nd lower values that achieve high accuracy while achieving signi cant speedup.
The feature selection process is mostly automated, with these heatmaps allowing the user to select an optimal pair of parameter values for the dataset. The nal evaluation of the model is over the held-out test set of the dataset provided with the selected pair as its parametric values. The evaluation results on the six non-time-series datasets are shown in Figure 5. Over the six datasets, the processing time is reduced to 42% on average. There is no reduction in classi cation accuracy for three of the datasets. The average reduction in accuracy is 1:3%. The result illustrates NSW to be a promising strategy to achieve accuracy of full k-NN comparably and much quicker.
NSW in TS Classi cation Building upon our preliminary analysis discussed in 4.2, we extend the evaluation of k-NN and NSW models to classi cation tasks on time-series datasets (PLarge and PSmall). The nal results reported in Figure 6 are on hold-out test sets as described in Table 1. The f and m parameters were tuned using 5 5-fold cross-validation on the training set. The value of k for exact k-NN was set in the same manner. The same k value was used with NSW.
(a) Model evaluation over Plarge dataset.
(b) Model evaluation over Psmall dataset.
1. Even if TWED is a proper metric, DTW is still the clear winner by achieving the highest accuracy for both exact k-NN and using NSW. 2. Using NSW, the processing time is reduced to 23.5% for Plarge and 35% for Psmall of that of exact k-NN-DTW. The speedup is more signi cant for the larger dataset. 3. NSW achieves accuracy comparable to that of exact k-NN. The drop in accuracy using NSW with DTW measure is 2.7% on Plarge and 4.2% for Psmall.
In summary, the speedup is signi cant { it seems reasonable to expect better than a four-fold speedup on large datasets. However, the impact on accuracy would probably not be acceptable in many situations. 6
Conclusions & Future Work In this paper, we address the challenge of improving the run-time performance of time-series classi cation using k-NN. Because e ective distance measures for time-series are computationally expensive, we explore the potential of NSW for speeding up k-NN using DTW and TWED. TWED is included because it is a proper metric, whereas DTW is not. Despite its lack of metric pedigree, DTW performs best. NSW delivers signi cant speedup but at the cost of classi cation accuracy.
So it seems that NSW does not allow us to avoid the curse of dimensionality. We cannot speed up retrieval without paying the price in terms of accuracy.
In future work, we will explore measures to quantify the intrinsic dimension of time-series data to see if speedup strategies might work for datasets that have a lower intrinsic dimension. Furthermore, these methods need to be evaluated in a realistic context where time-series containing pores would be very rare. Acknowledgements This publication has resulted from research supported in part by a grant from Science Foundation Ireland (SFI) under Grant Number 16/RC/3872 and is cofunded under the European Regional Development Fund.