Introduction

Anomaly detection is a method used to recognize abnormal patterns that do not match expected behavior, called outliers. Nowadays, a massive amount of data and software available on social platforms are available to ensure service. This will be required to systematically monitor the data to detect an abnormal event such as Detection of abnormal health conditions, intrusion detection, and fraud detection.

Numerous types of algorithms have been developed for anomaly detection for twin academic research, commercial interest, and the use of all this to protect such a specific application or device.

In most kinds of records such as temperature, visits on a website, etc. there is usually a normal accepted behavior indicating that everything is working fine. It might be hard to determine an anomaly based on an instantaneous value of a waveform in some cases. Instead, it's better to consider the shape of the waveform as discussed in this paper.

A library of different waveforms is created, and with the use of k-means clustering, we can develop what constitutes the normal shape of a waveform. The dataset used is plotted to form a wave of a particular shape. The waveform using the waveform library is reconstructed. If there is any poor reconstruction, then the wave is certainly containing some abnormalities.

WCNC-2021: Workshop on Computer Networks & Communications, May 01, 2021, Chennai, India. EMAIL: avadhnareshkushwaha_2k19swe03@dtu.ac.in (Avadh Naresh Kushwaha) ORCID: 0000-0002-2346-484X (Avadh Naresh Kushwaha)

Related Work

Jianliang, Haikun, and Ling [1] performed Intrusion detection on networks using K-Means. The authors' evaluated their proposed model using "the KDD Cup 1992 data". The data provided a wide variation of instructions which were simulated over a military network. From the "100,000 labeled data items", 1,000 of them contained attack samples, while the other 99.999 were the normal samples free from attacks.

They perform data processing for more extensive features in two ways; first, they calculate the mean absolute deviation [10] and then calculate the standardized measurement [1]. New training datasets are then created based on the formulas above, and then the proposed algorithm is applied. The experiments performed showed that the K-means algorithm was the most suitable method for intrusion detection. [1].

Xinlong and Weishi [10] used an improved k-means clustering technique to perform anomaly detection on cloud computing. The method proposed by the authors finds the known attacks and anomaly attacks in the cloud computing environment. They use a distributed intrusion model of cloud computing to perform the detections [10]. The authors also made quantitative comparisons of the different intrusion detection methods used before based on their advantages and disadvantages.

K-Means Algorithm

Clustering is "the process that groups objects into subclasses so that those subclasses are entirely related or have some similarities and the different clusters are altogether dissimilar from each other" [1]. The clustering algorithm is divided into four different groups, i.e., Partitioning Clustering, hierarchical Algorithm, Density-based and Grid-based.

Partitioning Clustering

Partitioning clustering [6], the data objects are directly divided into clusters of a pre-defined number. "The checking for all possible clusters is computationally impractical; certain greedy heuristics are used in the form of iterative optimization of a cluster. The partitioning clustering consists of several approaches such as K-means Clustering, K-medoid Clustering, Relocation Algorithms, and Probabilistic Clustering." [4]

Hierarchical Algorithm

A hierarchical clustering [5] "creates a hierarchical decomposition of the given set of data objects. It builds a cluster hierarchy, known as a dendrogram. Disjoint groups of clusters are obtained by cutting the tree at the desired level. Hierarchical clustering is used to find data on different levels of dissimilarity." [4] 3.3.

Density-Based

Density-based algorithm [8] "can find a cluster of random shapes unexpectedly. To group objects, it uses the density objective function.in these method clusters will increase until the number of the article in the nearby growing some limitation." [4] 3.4.

Grid-Based

Grid-based clustering [8] "quantizes the object space into a finite number of cells that form a grid structure. After calculating density grid-based clustering, sort the cells according to their densities. Cluster centers are identified, and all neighbor cells are traversed." [4] Partitioning is done to divide a group of data into k-cluster [1]. K-mean constitutes a proper clustering technique by ambitious training

The Objective of Algorithm

Considering the d-dimension data set {𝑥 |𝑥 ∈ 𝑅 , 𝑖 = 1,2, … 𝑁} , the method to follow easy steps to classify given dataset, number of clusters 𝑤 , 𝑤 , … . 𝑤 to define K centroid 𝑐 = 𝑐 , 𝑐 , … . 𝑐 , one for each group,

𝑐 = ∑ 𝑥 ∈

Where 𝑛 Are several datasets in the cluster?

Select all points closest to a considering dataset and relate them to the nearest centroid. When a topic does not stand out, the first steps compete [1]. We need to the recalculated centroid of the cluster resulting from the previous actions.

A new obligate done between the current dataset and closest new centroid, an iterative loop has been generated due to this loop centroid change their location slowly until no change is done .lastly algorithm minimizing an objective function.

The objective function 𝐽 = ∑ ∑ 𝑑 𝑥 , 𝑐 where 𝑑 𝑥 , 𝑐 Distance between the data point 𝑥 and cluster center 𝑐 .

3.6.

Step

by Step Algorithm

Step1: (initialize) randomly choose K occurrence 𝑐 , 𝑐 , … . 𝑐 From the data set X and start cluster center of the clustering space.

Step2: (allotment) provide each occurrence to the nearest center: 𝑑 𝑋 , 𝐶 < 𝑑 (𝑋 , 𝐶 ) i.e.,

𝑗

Advantage(s):

K-mean algorithm is essential for a considerable large dataset [1], and its time complexity O (tkn), where t is the number of loops, k is the number of clusters, and n is the data point in the dataset

Disadvantage(s):

With the k-mean algorithm, the cluster number is required first, yet the number of clusters is usually determined later. It is sensitive to outliers [1] [2].

It is not easy to predict k-value, the k-mean algorithm with global cluster does not work well, and it does not perform well with a different group and size

Proposed Methodology

In our approach, we define an anomaly as a shape of the waveform that has not been experienced or seen last. The algorithm will build a normal shape library and reconstruct the waveform and determine its shape. The waveform is said to have an abnormal behavior if the reconstruction of the waveform by the library is inadequate.

Dataset

In this paper, the data used for the experiments is the EKG dataset publicly available at PhysioNet. This version of the data provides a regular waveform which provides a reasonable basis for exploring the proposed algorithm.

Clustering

To fully ascertain what constitutes a waveform's normal shape, we use k-means clustering to form different clusters to determine a normal cluster group. The clusters can be in separate n-dimensional space that's defined by n-features. In our case, the clusters are determined programmatically using the clustering algorithm.

Waveform Space

We shall consider a 32-dimensional waveform space to perform anomaly detection such that for every point within the space, it potentially represents a waveform segment. We cluster the segments that are similar to each other. "The middle of each cluster (the centroid) will measure the prototypical waveform pattern that all those segments are specific instances of". Still, where necessary, from all the waveforms, the average of them within a cluster will be considered as the centroid.

Since the center of the cluster is also a point that is part of the waveform space, this makes it also "waveform". This therefore means that, the centroids of the clusters will constitute a set of "normal waveform segments". Now using these normal segments, we try to reconstruct the dataset being tested. The reconstruction will be considered as good if the data is similar to the original. However, suppose there is some abnormal shape in the data. In that case, it won't be possible to reconstruct the waveform using the "normal" waveform library, which then results into a reconstruction error. This therefore indicates that there is some anomaly.

The algorithm is divided into two parts; -An abnormal shape is obtained if there is any reconstruction error on any segment.

Step by Step Algorithm

Step 1: Import the data Let FN be the filename of the data set. Let DS be the variable that holds the data after reading it using the ekg_data primitive function.

Step 2: Plot the data Using matplotlib.pyplot function and sample size of 300, plot the data. Label the x and y axes, then show the plotted graph.

Step 3: Split data into segments Let seg_len be the segment length of value 32, slide_len of value two, and an array named segments to store them. Loop through the DS dataset to split it into waveform segments.

Step 4: Cluster the segments Perform clustering of the segments in a 32-dimensional space using the k-means algorithm provided in python's library scikit-learn.

The different clusters created at this point then constitutes the normal waveform shapes of the library

Step 5: Reconstruct the waveform Try to reconstruct the data or the waveform, which will be tested using the learned library. The reconstruction process consists of four sub-steps which include; -First, the data is split into segments that are overlapping.

-Secondly, we determine the segment's cluster centroid by using the samples' average in a cluster. -Using the centroid from the above step, we reconstruct the segment.

-Finally, we join all the segments to form the waveform.

Step 6: Conclude on the anomaly We decide whether there is an anomaly or not based on the reconstruction error obtained. If there is a very high reconstruction error, then we conclude that there is an anomaly.

Result and Analysis

Using the EKG dataset, we performed clustering on the data and also try to reconstruct to find the error between the original plotted data and the newly revamped data.

The new shape formed indicates an anomaly detected after reconstruction of the data since there is a substantial visible error. The reconstruction error obtained was 23.8%.

The figure below shows the original data's waveform, the reconstructed information, and the error after reconstruction.

Conclusion

Anomaly detection is essential in everyday lives, and therefore it's vital to expand on the research continuously.

Every different kind of data consists of a regular pattern that depicts normal behavior. When the data are plotted to form a waveform, it can also be hard to determine an anomaly of a waveform based on its instantaneous value but by its shape.