Adjusted k-nearest neighbor algorithm: Application on forecasting the ship accident in South Korea

2.1 Nearest-Neighbor Approaches

Of the popular nearest neighbor approaches, kNN is used in the field of machine learning, and rolling window is used in the field of time series analysis.

Most studies have mainly addressed the kNN algorithm in classification or fitting, while some have adopted it for forecasting. For example, the kNN algorithm has been used to forecast future traffic flow, and the method based on the kNN algorithm gave more improved forecasting accuracy than one that was not [8]. In another study, the kNN algorithm has been combined with an SVM according to the distance from a separating hyperplane for solar flare forecasting [9]. There are also some studies using kNN on time series prediction; for example, the kNN algorithm has been applied to forecasting short-term electric energy demand and compared with a conventional dynamic regression technique [10]. An interesting approach has also been proposed to find an optimal size of nearest neighbor for time-series prediction by using multiple nearest neighbors to same data [11]. Thus, there have been many studies combining kNN algorithm with other machine learning techniques or applying it to practical areas, however it seems that there are not many studies addressing the shortcoming of it, which is caused by using only a small part of the entire sample.

In moving average methods, a rolling window refers to the size of the most recent data to forecast future values. It is similar to kNN in that it uses neighboring points, but it only considers the distance in the space of a predictor. In a moving average method, consider the time series sequence { y_t }_{t =1,…} , and when forecasting a value at t = T with rolling window n, then the moving average is

Based on the similarity of the nearest observations, a better forecast can be obtained than one from using a whole data set according to n, although only considering the n data may lead to a large variance. Therefore, selecting the optimal window size is a critical issue for accurate forecasting, and in many applications, it is experimentally obtained from past data. Rolling windows of different sizes were used, and the results from them were compared using an autoregressive model for forecasting the consumer price index and industry production [12], and a specific rolling window of size 68 selected out of 60-82 was used when forecasting inflation indices across five countries [13]. There have also been researchers who have tried an analytical approach on how to determine the window size. The study in [14] focused on estimating the windows size when structural breaks existed in a given stochastic process because these affected changes in the parameters to be estimated. Approaches based on geometrical characteristics to find the optimal window size have also been attempted [15]. Unlike the studies using kNN algorithm, many studies using a rolling window seem to have mainly focused on forecasting in practical areas, and so the optimal window sizes widely vary depending on the given data.

2.2 Combination for Forecasting

Test error is typically higher than training error obtained from a given data set [7]. Therefore, among forecasting-oriented studies, alleviating over-fitting plays a major role in getting an accurate forecast. Shrinkage or regularization methods in the field of machine learning such as ridge regression, lasso, etc. have been introduced to deal with the over-fitting problem. When considering the shrinkage of estimated coefficients to avoid being overly biased against one forecasting model, a combination of several forecasts can be an alternative. Consider forecasts f₁, . . ., f_M from M models and suppose that their variances σ₁, . . ., σ_M are uncorrelated, then combination of forecasts f_c is

where $$ {\omega }_i=\frac{{\sigma }_i^{-2}}{{\sum }_{j=1}^M{\sigma }_j^{-2}}$$ and $$ {\sum }_{i=1}^M{\omega }_i=1$$. Note that the weight is inversely proportional to the forecast’s variance [16]. A combination of forecasts still yields an accurate forecast even in cases where the variances of the forecasts are correlated [17]. Furthermore, analogous to shrinkage or regularization, a unique approach was suggested to shrink f_c into λ_c, λ < 1, giving up the sum of a combination of weights to be one for better accuracy [18]. The idea of combining forecasts is based on Jensen’s inequality [16] as long as a loss function is convex. Meanwhile, questions remain on how many forecasting methods to use and which ones work well together. We also found a different type of combination under structural change [19]. In this study, rather than combining forecasts from different models, the method here was to combine the estimated coefficients of rolling and expanding (or recursive) windows in the same forecasting model. Let $$ {\widehat{\beta }}_R$$ and $$ {\widehat{\beta }}_E$$ be the estimated coefficients in rolling and expanding window forecasts, respectively, then the combination coefficient is

where α is an optimal weight of less than 1. This approach has the advantage of not considering the choice among the forecasting models unlike the previous forecasting combination, but it is still a linear combination of already estimated parameters bounded by $$ {\widehat{\beta }}_R$$ and $$ {\widehat{\beta }}_E$$, similar to the previously reported forecasting combination methods.

2.3 Least Squares Adjusted With Pseudo Data (LSPD) for Forecasting

Let us consider a data set {y_t}_t=1,…,T and suppose that we want to forecast y_T+1. In most cases, we use estimated parameters obtained from using the T data set to forecast a future value at T+1. Unfortunately, the over-fitting problem is likely to occur in this case unless the stochastic process is a martingale, i.e., E(y_T+1|y_T,…, y₁) = y_T. If we set a pseudo value close to the future value at T+1, we can construct a loss function including the (T+1) data set rather than the T data set and obtain a better forecast using this transformation [5][6]. Hence, test error obtained from the (T+1) data set including a pseudo data point are less than test error from using the T data set,

where $$ {\tilde{y}}_{T+1}$$ is a pseudo data point constructed from using the T data set. We can consider many candidates for this pseudo data point but in practice, the sample mean is the most appropriate based on the central limit theorem. This method provides better forecasting by just adding the pseudo data point, but its degree of improvement decreases as the data size increases.

2.4 AkNN for Forecasting

Nearest neighbor approaches can give a good approximation of a forecast but easily lead to a large variance due to using a small sample. From the forecast combination, we can obtain better forecasting accuracy by the regularization effect. Here, we propose a new forecasting method that blends subsample use and entire sample use, which is also associated with LSPD to forecast more accurately. By combining subsample use and entire sample use, we can avoid the large variance problem unlike the nearest neighbor approaches and the decrease of forecasting improvement of LSPD.

Let X and y be random variables on probability spaces ( Ω_X, Σ_X, μ_X) and ( Ω_y, Σ_y, μ_y) , respectively, and consider a stochastic process (X_t, y_t), for t = 1,…, T+1. Suppose that we want to forecast a future value at T+1. First, we try to find a nearest neighbor of the most recent cases to forecast this future value. Since the most recently estimated nearest neighbor varies depending on the forecasting location, its direct use or the average of the nearest neighbors over some interval may not give a stable result. To obtain a robust estimate of the nearest neighbor on a random basis, we construct bootstrap samples by b iterations and attach a pseudo value at T+1 to each sample for using LSPD. Subsequently, we obtain bootstrap samples {(X_j,t, y_j,t)}, for j = 1,…, b, t = 1,…, T+1, and for T+1, a pseudo value $$ {\tilde{y}}_{j,T+1}$$ (sample mean up to T) is used instead of the actual y_T+1.

Denote the size of the nearest neighbor as k_j and obtain its estimate for a forecast at t (k_j < t ≤ T + 1) by minimizing test error using LSPD:

where X_j,‖t-kj‖ is a ‘k_j ’th nearest point to X_j,t . Let k_j,o be the corresponding nearest neighbor for d’ by linearly combining d and L = ‖ X_j,T+1 − X_j,1 ‖, which acquires more stability than a simple nearest neighbor. Thus,

where α_j is a new parameter that is a nonnegative weight of less than or equal to one.

We can obtain an optimal $$ {\widehat{\alpha }}_j$$ by

Since $$ {\widehat{\alpha }}_j$$ is optimal for each bootstrap sample, we average over b, and then we obtain the bagged estimate

and by estimating $$ \widehat{k}$$ (corresponding metric: d^o) of the original T data set, we obtain k^* for the forecast at T+1 from its corresponding metric d^*:

By using $$ {\widehat{k}}^{*}$$ as AkNN we can expect less variance than that from a simple nearest neighbor approach and overcome a drawback of LSPD. We summarize the above procedure in the following algorithmic form.

3.1 Simulation Testing

We used three functions to examine the generalization of our method; a linear function as the basic model, a polynomial function for the sensitivity to the curve, and sine and logarithm functions as the complicated data generating process

Model 1 $$ y_i=1+2x_i+e_i$$

Model 2 $$ y_i=3+x_i-x_i^2+e_i$$

Model 3 $$ y_i=3+\sin \left(5x_i\right)+\log \left(\text{abs}\left(x_i\right)\right)+e_i$$

where x_i is a random variable in [0,1] and is used for considering the distance in the kNN algorithm [20], and e_i is an independent and identically distributed random variable orthogonal to x_i and normally distributed with zero mean and unit variance.

Samples of 100 and 300 were used for each simulation test, the number of Monte Carlo iterations was 100, and the number of bootstrap subsamples was 50 (of course, the forecast accuracy increased as the number of bootstraps increased).

Table 1 shows a test error comparison for the proposed method and some previously reported methods. In general, we can see that test errors were mainly large in the order of ordinary least squares OLS, LSPD, and AkNN (the proposed method), and the results of kNN and AkNN improved when the simulation function model was more curved (non-linear). Conversely, with Model 1, their improvements were slight since the linear form was the true model. kNN did not show low test error with any of the models and obtained the highest test error in the linear case (Model 1) and the lowest in the nonlinear case (Model 3), which is as expected considering the property of kNN using only a small portion of the data. LSPD consistently outperformed OLS but its improvement became smaller as the sample size increased. We can also see that the degree of reduced test error percentage compared with OLS decreased in the LSPD case but increased in the AkNN case as the sample size increased. Note that AkNN outperformed the results of ACT (residuals from fitting when the actual value at T+1 assumed to be known) for Models 2 and 3.

Table 1:

Test error comparison

Figure 2 shows test error comparisons of AkNN with the other methods over 20 arbitrary trials. From Model 1 to Model 3, the performance of AkNN was better than its counterpart in each case although it seemed to fluctuate, which implies that kNN’s influence increased as the simulation function became more curved. A similar phenomenon is evident in the middle charts of kNN vs. AkNN, reflecting a large variance caused by kNN.

Figure 2:

Test error comparison

Figure 3 shows the histograms of α in Equation (8) over 100 trials. Overall, they show a bell-shaped distribution, which implies that α can be used as a parameter in each particular data generating process. From Equation (9), we can see that the greater α is, the more $$ {\widehat{k}}^{*}$$ depends on the nearest neighbor $$ \widehat{k}$$. From Models 1-3 shown in Table 2, α becomes greater, reflecting that kNN’s influence increased.

Figure 3:

Histogram of alpha (N = 300)

Table 2:

Mean of Alpha

Figure 4 shows estimated lines from OLS and AkNN when both were compared with the original simulation function (y–e: noisefiltered y). We can see that AkNN uses a subsample on all the models and also that the end point, i.e. the forecast, of AkNN is closer to the end point of the original function than OLS in every case.

Figure 4:

Comparison of estimated lines (N = 100): (a) Model 1, (b) Model 2, and (c) Model 3

3.2 Empirical Study

Ship accident is considered as a serious event because the emergency process is not quickly taken. Overall, the number of the ship accident is gradually increasing as shown Figure 5. There are some papers [21][22][23] studying the human factor of the ship accident, but there does not seem to be many studies on the forecasting the ship accident from a statistical point of view. Considering this point, we forecast the number of the onestep ahead ship accident based on our proposed method (AkNN), and since the number of ship accident is varied according to the ship weight, we forecasted the number of the ship accident by each weight.

Figure 5:

Monthly data on the ship accident by the ship weight

We collected the 96 monthly data on the ship accident for each weight between Jan. 2000 and Dec. 2014 in South Korean waters, and the test errors from the last 40 observations were obtained and compared across the methods. The trends in Figure 5 seem to be moderate, but the degree of noise is quite high, and thus a nearest-neighbor approach will promise desirable forecasting performance.

In Table 3, the test errors of AkNN were mainly less than the rival methods, OLS, kNN, and LSPD, and in some cases, it was less than the residuals obtained from ACT in some cases. kNN showed good forecasting performances compared to OLS in some cases, but in other cases its forecasting accuracy was very low, which reflects the high variance of the subsample use and affects its high standard deviation in the table.

Table 3:

Test error comparison

Histograms of α in the ship accident data is shown in Figure 6. Not as close to a bell shape as the simulation case, it shows a peak around the mean. The mean of alpha was 0.5820 and its standard deviation 0.1702.

Figure 6:

Histogram of alpha