# Streaming-Based Anomaly Detection in ITS Messages
## 1 Introduction
If a score exceeds three times the standard deviation, it can be deemed an anomaly. Another method is to order the scores so that a top_k algorithm provides the \(k\) most anomalous observations. Anomalies can be identified by assuming that the data follow a specific probability distribution and categorising data points with a low probability density as anomalous. In an elliptical distribution, the Mahalanobis distance between each point and the mean is calculated, with points exceeding a predetermined threshold being categorised as anomalies. Due to its ability to resist outlier observations, the minimum covariance determinant (MCD) [13] serves as a highly dependable means for identifying anomalies in multivariate contexts. Given a dataset presented as an \(n\times p\) matrix, where \(n\) refers to the number of occurrences and \(p\) relates to the number of features. The initial stage in obtaining the MCD estimator involves calculating the covariance matrix's determinant. A smaller set of observations (consisting of \(h\) data points, wherein \(n/2\leq h\leq n\)) is selected from a larger sample of \(n\) data points. This selection is made in a way that minimises the generalised variance of the subset \(h\). The MCD estimator defines the following location and scatter estimates [14]:  
1. [i0, the mean of the \(h\) observations with the least possible determinant of the sample covariance matrix. 2. \(\hat{\Sigma}_{0}\) is the associated covariance matrix multiplied by a consistency factor \(c_{0}\). The mean and the covariance matrix are used to calculate the robust distance for a point \(x\) defined as [14]  
\[RD(x)=d(x,\hat{u}_{\text{MCD}},\hat{\Sigma}_{\text{MCD}}) \tag{2}\]  
where \(\hat{u}_{\text{MCD}}\) is the MCD estimate of location, and \(\hat{\Sigma}_{\text{MCD}}\) is the MCD covariance estimate. MCD selects the section of the data with the closest distribution to eliminate anomalies, as they tend to be far from the bulk of the data. This minimises the masking effect caused by atypical observations [15]. The isolation forest (IForest) [16] algorithm is utilised to uncover anomalies in data that have a high number of dimensions.It is a non-parametric method that demonstrates favourable results when applied to normally distributed, unbiased data that contain minimal noise [4]. Its suitability for anomaly detection in C-ITS data lies in the fact that the data lack prior distribution and remain unlabeled. The IForest model is composed of a collection of unique, random isolation trees _itrees_ that are divided into nodes through recursive partitioning. IForest's scoring stage computes an anomaly score for each data observation within the dataset. The outlier score is calculated based on the distance between the leaf and the root. The ultimate outcome is obtained by taking the mean of the distances from the individual data points to the different _itrees_ within the isolation forest. Given an instance \(x\), the anomaly score is defined as  
\[c(n)=2H(n-1)-(2(n-1)/n) \tag{3}\]  
\[E(h(x))=\sum_{i=1}^{t}h_{i}(x) \tag{4}\]  
\[s(x,n)=2^{\frac{E(h(x))}{c(n)}} \tag{5}\]  
where \(E(h(x))\) is the average path length of sample \(x\) over \(t\)_itrees_, \(c(n)\) is the average path length of the unsuccessful search in the binary search tree, and \(H(i)\)= ln(\(i\)) + \(\gamma\) (\(\gamma\) is Euler's constant). Based on the anomaly score \(s\), the following conclusions can be made [17]:  
1. If instances return \(s(x,\)\(n)\) extremely close to 1, then they are anomalies;
2. If instances have an \(s(x,\)\(n)\) less than 0.5, then they are deemed normal instances;
3. If all the instances return an \(s(x,\)\(n)\) of 0.5, then there is no differentiation between normal and anomalous instances. Robust random cut forest (RRCF) [18], a variation of isolation forest designed for streaming data, incorporates concept drift and tree evolution to generate a measure of the isolation score. The tree structure is impacted by the degree to which a new point alters the anomaly score.