This paper is devoted to the problem of detecting and classifying anomalies for time series data. Some of the important applications of time series anomaly detection are healthcare, fraud detection, and system failure recognition. Despite scientists extensive experience in detecting anomalies in time series, most methods look for individual objects that differ from ordinary objects, but do not take into account the specifics of the data sequence [1]. In this paper, a method for detecting anomalies and clastering time series based on neuroevolutionary approaches is proposed. Prediction-based methods are used to detect anomalies: statistical and deep neural networks are used. Classical clustering methods that accept statistical parameters of series were used for clustering.
Prescriptive (decision support) Predictive (forecast, predictive)
Diagnostic
Descriptive
Complexity of the
model
Human participation
rate
collection, processing, and preliminary analysis. The listed types of analytics differ both in the
complexity of the models used and in the degree of human participation [
There are a lot of areas of application of analytics tools-information security, banking sector,
public administration, medicine and many other subject areas. Often, the same method works
effectively for different subject areas, so developers of analytics systems create universal modules
containing different algorithms [
For many technological systems, monitoring results can be represented as time series. The
properties of the time series are [
Time series can describe more than just numerically measurable processes. The use of various
methods and model architectures, including deep neural networks, allows you to work with data from
natural language processing, computer vision tasks, etc. For example, a chat message can be
converted into numeric vectors (embedding) that appear sequentially at a certain time, and the video is
nothing more than a matrix of numbers that changes over time [
So, time series are very useful for describing the operation of complex devices and are often used
for typical tasks: modeling, forecasting, feature selection, classification, clustering, pattern search,
anomaly search [
Time series have typical characteristics that accurately describe the nature of the time series [
Time series may contain anomalies. An anomaly is a deviation in the standard behavior of a
process. The method of machine search for anomalies uses data about the operation of the process
(data sets) [
N1
O3
O1
O2
N2
x
c)
Figure 3: Examples of various anomalies in time series: a) point O1 and O2 and collective O3
1. Point anomalies. They occur in situations where a single instance of data can be considered as
absolutely abnormal in relation to others [
An individual instance may not be a deviation, but the joint appearance of such instances will be a collective anomaly. 1.1.
Detecting point anomalies often requires some kind of system model. If the system does not have a
deterministic mathematical model or such a model is too difficult to build, then a statistical model
must be available. Depending on the method of constructing a statistical model, the following
approaches are distinguished [
1. Recognize anomalies in case supervised learning. This technique requires a full-fledged training sample, including enough representatives of the normal and abnormal classes of values.
The technique is applied in 2 stages: first, training takes place on data that manually indicates
normal and abnormal points. Then recognition occurs when new data is classified based on the
constructed model [
It is usually assumed that the statistical properties of the model do not change over time, and such a change often requires repeated training.
The main difficulty of such methods is the formation of data for training. In addition to the
obvious labor costs, often the abnormal class is also worse represented than the normal one, which
can lead to inaccuracies in the resulting model [
2. Recognition of anomalies partially supervised learning. Similar to the previous one, but the
training data represents only a normal class. A system trained in a normal class can determine
whether data belongs to it, thus identifying abnormal data by exclusion.
3. Recognition in case unsupervised learning. In the absence of a priori information, this is the
only possible option. Recognition in unsupervised learning: free mode is based on the assumption
that abnormal data is quite rare. Therefore, only those that are farthest from the average values are
indicated as anomalous [
Classification. This method is based on the fact that the normal behavior of a system can be
determined by one or more classes. Then an instance that does not belong to any of the classes is
anomalous. This method usually uses the “partially supervised learning” approach. Basic
mechanisms: neural networks, Bayesian networks, rule-based reference vector method [
Clustering. This method is based on grouping similar values into clusters, and does not require
knowledge of the properties of possible deviations. Anomaly detection is based on the following
assumptions [
Statistical analysis. Using this approach, a statistical model of the process is constructed, which is
then compared with the actual behavior. If the actual behavior differs from the model by more than a
certain threshold, it is concluded that there are anomalies. Statistical analysis methods are divided into
two groups [
Nearest neighbor method. When using this technique, a metric is introduced (a measure of
similarity between objects). Then two approaches are possible [
Spectral methods. Based on the spectral (frequency) characteristics of the data, a model is constructed that is designed to take into account most of the variability in the data.
Let's compare the existing methods and present the results as a table.
No No No
In general, from the comparison of methods, we can conclude that there is an insufficient qualitative level of existing methods, because most methods are not able to use all strategies (approaches) to machine learning, and also from the results they do not provide an unambiguous answer about the assessment of detected anomalies. Moreover, most papers note an insufficient level of accuracy when using cool methods with newer model topologies. That is why the task of developing new approaches and methods for detecting anomalies in time series remains an urgent task.
Point anomalies are most easily recognized-these are individual points where the behavior of the
process differs dramatically from other points. For example, you can observe a sharp deviation of
parameter values at a particular point [
Such values are called “outliers”, they strongly influence the statistical indicators of the process and are easily detected by setting thresholds for the observed value.
It is more difficult to detect an anomaly in a situation where the process behaves “normally” at
each point, but collectively the values at several points behave “strangely”. Such abnormal behavior
can include, for example, a change in the waveform, a change in statistical indicators (mean, mode,
median, variance), the appearance of a mutual correlation between two parameters, small or
shortterm abnormal changes in the amplitude, and so on. And in this case, the task is to recognize
abnormal behavior of parameters that cannot be detected by conventional statistical methods [
Finding anomalies is very important. In one situation, data should be cleared of anomalies in order to get a more realistic picture, while in another situation, anomalies should be carefully examined, as they may indicate a possible rapid transition of the device to emergency mode.
Finding anomalies in time series is not easy (unclear definition of anomalies, lack of markup,
nonobvious correlation). So far, the Self Organizing Tree Algorithm (SOTA-algorithms) for searching for
anomalies in time series has a high level of False Positive [
Only a small number of anomalies, mostly point-based, can be detected manually if good data
visualization is available. Group anomalies are harder to detect manually, especially when it comes to
large amounts of data and analyzing information about multiple devices. Also difficult to detect is the
case of an “anomaly in time”, when a normal signal appears at the “wrong” time. Therefore, when
searching for anomalies in time series, it is advisable to use automation methods [
A big problem in finding anomalies on real data is that the data is usually not marked up, so initially it is not strictly defined what an anomaly is, there are no rules for searching. In such situations, it is necessary to apply methods of teaching without a teacher (unsupported learning), while models independently determine the relationships and characteristic laws in the data.
The methods used to search for anomalies in time series are usually divided into groups [
Proximity-based methods are focused on finding values that significantly deviate from the
behavior of all other points. The simplest and most obvious example of implementing this method is
monitoring whether a given threshold of values is exceeded [
In prediction-based methods, the main task is to build a qualitative process model in order to
simulate the signal and compare the obtained simulated values with the original (true) ones. If the
predicted and true signal are close, then the behavior is considered “normal”, and if the values in the
model are very different from the true ones, then the behavior of the system in this area is declared
abnormal [
The most common time series modeling methods are SARIMA [
The original approach is used in reconstruction-based models - first, the model is taught to encode
and decode signals from an existing sample, while the encoded signal has a much smaller dimension
than the original one, so the model has to learn to “compress” information. An example of such
compression for 32-by-32-pixel images is given in [
After training, the models give input signals that are segments of the time series under study, and if encoding and decoding is successful, then the behavior of the process is considered “normal”, otherwise the behavior is declared abnormal.
One of the newly developed reconstruction-based methods that show good results in detecting
anomalies is TadGAN [
The network acts as an encoder that translates time series segments x into hidden space vectors
z, and is a decoder that recovers time series segments from the hidden z representation. Cx is the
critic who evaluates the recovery quality of x, and Cz is the critic who evaluates the similarity
of the hidden representation of z x to white noise. In addition, there is a control of the
“similarity” of the original and restored samples using the L2 measure according to the “Cycle
consistency loss” ideology (which ensures the overall similarity of the generated samples to the
original samples in GAN) [
To create and train a neural network, you can use various standard packages (for example,
TensorFlow or PyTorch) that have a high-level API. An example of implementing a TadGAN-like
architecture using the TensorFlow package for weight training can be found in the repository [
After training the model, individual segments of the time series under study are reconstructed and
the original and reconstructed series are compared, which can be performed using one of the
following methods [
Quality is evaluated using the f1 metric for the binary classification problem, “positive” (null hypothesis): there is an anomaly, “negative” (alternative hypothesis): no anomaly.
FP predicted an anomaly where it doesn't exist
absence of an anomaly
FN there is an anomaly, but it was not found
TN there is no anomaly and the model does not see it 2
2
To demonstrate the operation of the method, we use a synthetic (artificially generated) series without anomalies, which is the sum of two sinusoids, the values of which vary in the range from -1 to 1: yx 1 sinx 1 sin0.8x .
It can be seen that the model has quite accurately learned to predict the main patterns in the data.
Let's try adding various anomalies to the data and then detect them using the tadgan model. First, let's
add a few point anomalies [
The graph of the original and predicted signals shows that the model cannot restore the “peaks” of
anomalous values, which can be used with high accuracy to determine point anomalies. However, in
such a situation, the crust of the complex TadGAN model is not obvious-such anomalies can also be
detected by estimating the excess of thresholds [
Now consider a signal with a different type of anomaly: a periodic signal with an abnormal
frequency change. In this case, there is no excess of the threshold: from the point of view of
amplitude, all elements of the series are “normal” values, and the anomaly is detected only in the
group behavior of several points. In this case, TadGAN also cannot restore the signal (as can be seen
in the figure) and can be used as a sign of the presence of a group anomaly [
These two examples illustrate the work of the method. The reader can also try to create their own data sets and test the model's capabilities in various situations.
More complex examples of datasets can be found in the article by the authors of the TadGAN
Method [
However, most scientists agree that each case requires its own method of signal reconstruction and a conductive method of training the model, which significantly slows down the practical implementation.
The prototype of our solution is shown in Fig. 7, consists of two separate groups of the same population. The first is a set of models, and the second is a set of data individuals.
Each model is a sequence of encoder and decoder levels that describe the input multidimensional signal [16]. The framework allows you to create an ensemble model using an approach similar to the method based on packaging in packages. A whole ensemble model is a set of sub-models that work with subgroups of input signals. Ensemble models form a set.
The work of the solution begins with generating initial groups of input signals using correlation; the system then updates the models and groups using a genetic algorithm [17-19]. In parallel, genetic operators optimize individual models in each subgroup by making changes to the topology of neural models (for example, model length and layer parameters) [17-19]. The end result of these actions is an ensemble model optimized for anomaly detection. The ensemble model is defined as follows.
A number of papers note that despite different models, it is noticeable that almost all models show a similar set of anomalies, despite changes in their hyperparameters [16]. Of course, the results differed depending on the hyperparameters, but none of the changes significantly affected detection. Because of this, an ensemble model is proposed, based on the simultaneous division of the search space into subgroups and the evolution of models for such subgroups. As a result, the models were able to identify more specific dependencies and relationships between signals [20-22].
Models within each subgroup are optimized by changing their internal structure. The evolution of a single model is carried out in five main stages: 1. clustering the search space [23-25];
crossing, mutating, and selecting the best models for individual clusters; syncing solutions; multi-parent crossover [17-19]; evaluation of the ensemble solution.
For the experimental research of proposed method was be used the following as the training and testing data: The Secure Water Treatment (SWaT) Dataset [26], [16]. This dataset contains data gathered from a scaled-down version of a real water treatment plant. The data were collected for 11 d in two modes – 7 d of normal operation of the plant and 4 d during which there were cyber and physical attacks executed; The Water Distribution (WADI) Dataset [27], [16]. This dataset contains data from a scaleddown version of a water distribution network in a city. The collected data contain 14 d of normal operation and 2 d during which there were 15 attacks executed.
The general information about datasets present in Table 3.
The meta-parameters for neuroevolution synthesis of models demonstrate at Table 4.
The results of the work present at Table 5.
Value 100 5% hyperbolic tangent
25% uniform deleting an interneuronal connection removing a neuron adding interneuronal connection adding a neuron changing the activation function k‐nearest neighbors 7
Recall, % 55.35 70.64 71.47 f1, % 0.74 0.82 0.83
The experimental results demonstrate that parallel clustering of data and synthesis of a model based on the processed data using an ensemble system can significantly increase the efficiency of the anomaly detection process. The process of neuroevolution helps to synthesize models and develop them in stages based on updated information about input data, without separating the process of data preprocessing. Tests based on samples of WADI and SWAT data. In both cases, the results of anomaly detection demonstrated satisfactory values, raising the qualitative level of detection. The improvements in the WADI dataset were more significant than in the SWAT dataset because there are more sensors and samples in the WADI dataset than in the SWAT dataset.
The article proved that the neuroevolution approach can have a positive impact on the results. Our future work will focus on further improvements to the method. A combination of different solution topologies can significantly improve the results of the work.
At the paper a research and comparative analysis of existing strategies and methods solving the problem of detecting and classifying anomalies were carried out, and a detection method based on neuroevolutionary methods was also proposed. As can be seen from the results of the study, the method of detecting anomalies based on neuroevolution has shown much greater effectiveness. The proposed method has shown itself to be viable and can be improved.
The result of the work is not only a comprehensive study and theoretical justification of the theory associated with the analysis of time series, but also the proposed solution. His work consists of two stages: the separation of the search space and the synthesis of models. At the training stage, the method processes and separates data about the behavior of the system. In the synthesis mode, the method gradually adjusts the models in order to get the final solution from them in the future. The resulting model is synthesized using uniform crossing, which makes it possible to increase the size of the parent pool from two individuals to a much larger number.
The work was carried out with the support of the state budget research projects of the state budget of the National University "Zaporozhzhia Polytechnic" “Development of methods and tools for analysis and prediction of dynamic behavior of nonlinear objects” (state registration number 0121U107499) and “Intelligent methods and tools for diagnosing and predicting the state of complex objects” (state registration number 0122U000972). 8. References [15] Examples. TadGAN, 2022. URL: https://github.com/CyberLympha/Examples/tree/main/%D0%A0%D0%B0%D0%B7%D0%B1% D0%BE%D1%80%20%D1%81%D1%82%D0%B0%D1%82%D0%B5%D0%B9/TadGAN [16] K. Faber, M. Pietron, D. Zurek, Ensemble Neuroevolution-Based Approach for Multivariate
Time Series Anomaly Detection, Entropy, 23 (2021). doi: 10.3390/e23111466. [17] S. Leoshchenko, S. Subbotin, A. Oliinyk, V. Lytvyn, M. Ilyashenko, Smart crossover mechanism for parallel neuroevolution method of medical diagnostic models synthesis, in: Proceedings of the Third International Workshop on Computer Modeling and Intelligent Systems, CMIS-2020, CEUR-WS, Zaporizhzhia, 2020, pp. 57-69. [18] S. Leoshchenko, A. Oliinyk, S. Subbotin, Adaptive Mechanisms for Parallelization of the Genetic Method of Neural Network Synthesis, in: Proceedings of the 10th International Conference on Advanced Computer Information Technologies, ACIT 2020, Deggendorf, Ternopil, IEEE, 2020, oo. 446-450. doi: 10.1109/ACIT49673.2020.9208905. [19] S. Leoshchenko, A. Oliinyk, S. Subbotin, T. Zaiko, S. Shylo, V. Lytvyn, Sequencing for encoding in neuroevolutionary synthesis of neural network models for medical diagnosis , in: Proceedings of the 3rd International Conference on Informatics & Data-Driven Medicine, IDDM 2020, Växjö, Lviv, CEUR-WS, 2020, pp. 62-71. [20] J.A.J. Alsayaydeh, Irianto, M. Zainon, H. Baskaran, S. G. Herawan, Intelligent Interfaces for Assisting Blind People using Object Recognition Methods, International Journal of Advanced Computer Science and Applications(IJACSA), 13(5) (2022) 734-741. doi: 10.14569/IJACSA.2022.0130584. [21] J.A.J. Alsayaydeh, Irianto, A. Aziz, C.K. Xin, A. K. M. Zakir Hossain, S.G. Herawan, Face Recognition System Design and Implementation using Neural Networks, International Journal of Advanced Computer Science and Applications(IJACSA), 13(6) (2022) 519-526. doi: 10.14569/IJACSA.2022.0130663. [22] V. Shkarupylo, I. Blinov, A. Chemeris, J.A.J. Alsayaydeh, A. Oliinyk, Iterative approach to TLC model checker application, in: Proceedings of the 2nd KhPI Week on Advanced Technology, KhPI Week 2021, IEEE, Kyiv, 2021, pp. 283-287. doi: 10.1109/KhPIWeek53812.2021.9570055. [23] R. Pawar, k-NN based Time Series Classification, 2021. URL: https://towardsdatascience.com/knn-based-time-series-classification-e5d761d01ea2 [24] S. Tajmouati, B. Wahbi, A. Bedoui, A. Abarda, M. Dakkon, Applying k-nearest neighbors to time series forecasting : two new approaches, 2021. URL: https://arxiv.org/abs/2103.14200 [25] F. Martínez, M.P. Frías, M. Pérez, A. J. Rivera Rivas, A methodology for applying k-nearest neighbor to time series forecasting, Artificial Intelligence Review, 52 (2019) 2019–2037. doi: 10.1007/s10462-017-9593-z. [26] A. P. Mathur, N. O. Tippenhauer, SWaT: a water treatment testbed for research and training on ICS security, in: Proceedings of the International Workshop on Cyber-physical Systems for Smart Water Networks, CySWater, Vienna, IEEE, 2016, pp. 31-36, doi: 10.1109/CySWater.2016.7469060. [27] C. M. Ahmed, V. R. Palleti, A. P. Mathur, WADI: a water distribution testbed for research in the design of secure cyber physical systems, in: Proceedings of the 3rd International Workshop on Cyber-Physical Systems for Smart Water Networks, CySWATER '17, Pittsburgh, PA, ACM, 2017, pp. 25-28. doi: 10.1145/3055366.3055375.