Outlier Detection of Functional Data Using Reproducing Kernel Hilbert Space

The work proposed a novel technique for outlier detection during the analysis of functional data. Outlier detection is performed to find any deviation in normal behavior. An observation that diverges from all other in a sample of pattern on data is termed as Outlier. Since the outliers bias any statistical analysis, outlier detection is important in exploratory analysis process. In the analysis of functional data, outlying properties can be exhibited. Some of the observations have most extreme maximum or minimum values. This may be obtained due to the variability in data measurement or in errors in experimental data. Outlier normally falls under two classes, namely Univariate and Multivariate. Univariate outlier is the one in which the values are distributed over the single feature space. In Multivariate, distribution of values is happened through n-features space. In most of the applications, outliers shown in Figure 1 can be considered as noise otherwise exceptions that should be excluded. In some of the disciplines like physics, economy, machine learning and cyber security etc. detecting outliers is acquiring major importance. The predictions or accuracy of the training model is affected by the outliers due to the occurrence of drastic change in estimation of fitness [1]. It is up to the analyst to make decision about the necessity of including outlier consideration in their context. The process of detecting and analysis of outlier data is termed as outlier mining.

Generally, outliers are defined as, “Given D dimensional Feature space with a set of N data objects, then the expected number of outliers (ω) is found out by considering the top ω data objects that has dissimilarity with respect to the remaining data objects” [2-4]. The outliers are classified into three categories namely, Global outlier, a data object deviates from real data set, Contextual outlier, a data object deviate from the context it is specified, and Collective outlier, a subset of the data objects deviates from the whole data set. Supervised learning and Unsupervised learning are the two basic methodologies used for mining the outliers. Supervised learning is the one in which the outlier detection is implemented based on the labeled example, while in unsupervised learning the labeling is not necessary. Unsupervised Learning based outlier detection mechanisms falls under various categories such as statistical based approach, distance-based approach, deviation based approach and density based approach.

1.png

Figure 1. Outliers in datasets

Distance based outlier getting importance when compared to other detection technique since it has dealt mainly based on the non-parametric machine learning approaches. A point outlier in distance based approaches are defined as “A point x is said to be outlier if no more points $\alpha$ in the data sets are at a distance of d or less distance from x”. Detection of the point outliers has implemented as polynomial algorithm or exponential algorithm. But these algorithms have restrictions in terms of two parameters a and d. To overcome these issues, a new definition based on the distance D_k(p) in k-nearest neighbor is defined as, “Given k and n number of data objects, a point x is said to be outlier if no more n-1 points are having maximum distance D_k than p”.

Univariate Outlier detection methodology is inadequate for functional data because the curve values are non-outlying at each time points of observations even though the curve is functional outlier. Multivariate outlier detection methods have some drawbacks due to the following reason. The plotting methods suitable only up to three dimensions [4, 5]. The methods are not robust methods. The procedure is restricted for normal or elliptical samples. To overcome these issues, an approach based on the functional depth is proposed. There are several strategies evolved to find the functional depth of the curve. This paper proposed a novel multivariate methodology which is based on reproducing kernel Hilbert spatial curve for outlier detection of functional data. The proposed methodology decreases the high dimensionality in a large dataset without loss of useful information.

The next section discusses the survey of the Literature and section three discusses the mathematical model of the Reproducing Kernel Hilbert Space (RKHS) curve. The section 4 elaborates the concepts of RKHS by conducting numerical experiments and section 5 concludes.

3.1 Reproducing Hilbert spaces

A continuous function whose range lies either in two dimensional planar curve or three dimensional space curve on the closed interval [0, 1] in the Euclidean distance space. The Euclidean distance (s) between real valued function is calculated based on the metric space $s: X \times X \rightarrow R$ and the points $x, y, z \in X$ as follows

1. The distance (s) is real valued, finite and non negative.
2. $s(x, y)=0$ iff $x=y$.
3. $s$ is symmetry that is $s(x, y)=s(y, x)$.
4. $s$ has triangle inequality property, $s(x, z) \leq s(x, y)+$ $s(y, z)$.

The function $F$ is said to be continuous one that mapping $f:(X, s) \rightarrow(Y, s)$ at $x_0$, where $x_0 \in X$ for every $\partial>0$ and $\exists \delta>$ 0 , then $s(x, y)<\partial \rightarrow s(F x, F y)<\delta$. A space that is linear which is closed under addition of vector and scalar multiplication is called as vector space $H$.

• If x, y, z $\in$ H, then vector space closed under addition is represented as

$x+y=y+z \in H($ commutative property $)$

$x+(y+z)=(x+y)+z \in H($ Associative property $)$

• If If $c$ is scalar, then $c x \in H$

A vector space H is said to be normed space with the norm $\|x\|$ where $x \in H$ is defined on as

$\|x\|=\sqrt{<x-x\rangle}$

An inner product on $H$ over complex field $C$ is a function $<., .>: H \times H \rightarrow C$ with the property of

1.  $\langle u, v\rangle=\langle v, u\rangle$, for $u, v \in H$
2.  $\langle\alpha u+\beta v, h\rangle=\alpha \cdot\langle u, h\rangle+\beta<v, h\rangle$ and $<$ $u, \alpha v+\beta h\rangle=\bar{\alpha}\langle u, v\rangle+\bar{\beta}<u, h\rangle$ where $\alpha, \beta \in C$ and $u, v, h \in H$
3.  $\langle u, u \geq 0$ for $u \in H$ and $\langle u, u>=0 \Leftrightarrow u=0$

A Hilbert space is a vector space H with the inner product $\langle u, v\rangle$ defined with norm $\|x\|$ on it is defined by

$|x|=\sqrt{\langle x-x\rangle}$       (2)

that turns H into a complete metric space. Hilbert spaces in finite dimensional space is specified as Real numbers $\mathrm{R}^{\mathrm{n}}$ and Complex number $\mathrm{C}^{\mathrm{n}}$. In infinite dimensional space, Hilbert space is defined as

$\langle u \cdot v\rangle=\int_{-\infty}^{\infty} u(x) \cdot v(x) d x$       (3)

An evaluation function over the Hilbert space functions (F) is represented as a linear function as follows

$L_x: F \rightarrow R$ such that $L_x(f)=f(x), \forall \mathrm{f} \in \mathrm{F}$        (4)

where, $f$ is a bounded linear functional in which $f(x)=<$ $x, m>$ in which $\mathrm{m}$ is defined by $\mathrm{f}$ and has norm $\|\mathrm{f}\|=\|\mathrm{m}\|$. 

Reproducing Kernel Hilbert spaces (RKHS).

If a set Y in which all the point evaluations are considered as bounded linear functional in a Hilbert space of Functions, then the space is termed as Reproducing Kernel Hilbert Space (RKHS).

For each $y_i \in Y, Y \in R^n$, the function $L_{y_i}: F \rightarrow R$ such that $L_{y_i}(f)=f\left(y_i\right), \forall \mathrm{f} \in \mathrm{F}$, then according to the definition of RKHS, the function $\left\{L_{y_i}\right\}_{y_i \in Y}$ is said to be bounded. According to Reisz theorem, the set of functions $\left\{k_{y_i}\right\} \subseteq F$ is defined in a way that

$L_{y_i} f=<f, k_{y_i}>, \forall f \in F$       (5)

The function $\mathrm{k}$ is called as reproducing kernel function which is defined over the feature map function $\emptyset: Y \rightarrow F$ such that $\emptyset(x) \rightarrow k_y$ and $k: Y \times Y \rightarrow R$ as

$k(u, v)=<k_u, k_v>=(\emptyset(u), \emptyset(v))$        (6)

where, k_y is called the representer of evaluation at y. A space filing curve is the one that performs mapping of N- dimensional space into one dimensional space. It is the curve that proposed as a linear order of pixels by visiting each pixel only once in a multidimensional space.

3.2 Functional data outlier

The multivariate outlier can be detected by estimating the central tendency of the curve. Generally, the multivariate functional median is identified based on the depth and then the deviation of the curve from the center point is calculated by measuring the distance deviated from the curve. Various depth functions are used for identifying the center point of the curve. Sampling is the concept associated with the evaluation. Whenever the point evaluations are continuous, then sampling in functional spaces is essential to ensure the stability of the functional data. 

According to Reisz’s lemma, the function has the ability to reproduce the functional values by means of inner product termed as RKHS [13]. The main issue lies in reproducing the functional values. In earlier, Shannon’s theorem proposed a sine function with inner product of L2 as reproducing kernel in RKHS. The functional space is taken as $[-\pi, \pi]$. Nowadays the reproducing is generalized through semi-inner products for Banach spaces. The accurate reconstruction is possible only when sampled data is available. The minimum norm interpolation technique is proposed for RHKS with the benefit of over-sampling that reduces the approximation errors exponentially. Optimal Finite sampling points could be found based on the concept of fixed reproducing kernel [14-20].

The optimal approximation of the linear functions f is produced from a RHKS by considering a class of linear functional. The optimal approximation based on linear function is studied and the function is approximated by finding the n^th minimal errors of class of functions characterized by the eigen values.

Let $\delta_x$ is a point evaluation functional that has a unique kernel function $k: Y \times Y \rightarrow R$ defined over $f \in H$ and $x \in$ $Y, K(x,.) \in H$ and we get

$f(x)=\left(f, K\left(x_1, X_2 \ldots X_i\right)\right)_H$        (7)

The above equation states that the functional values of the function f in H can be reproduced using the kernel function. The characteristics of reproducing kernels to be considered are

1. RKHS is called as positive-definite function on, that is for all the points $\left(x_1, x_2 \ldots \ldots x_m\right) \in Y$, the matrix $\left[K\left(x_u, x_y\right)\right]_{\text {m,and } u, v=1}$ is hermitian one and semi-positive.
2. K is called as RKHS on Y if and only if there exists a mapping of $\emptyset: Y \rightarrow H$ where $H$ is a Hilbert space such that

$K(u, v)=(\emptyset(u), \emptyset(v))_{H, \text { and u, v $\in$ Y}}$

Two classes of functional data classes such as polynomial and exponential RKHS are proposed. The polynomial classes is specified through the equation

$K(u, v)=\sum_{m=0}^{m=\infty} a_m(u . v)^m, \quad u, v \in R^d$         (8)

where, $\left\{a_m\right\}$ denotes a sequence of non negative number of the kernel series of polynomial class. The series of the numbers that converges for all the functional values $u, v \in R^d$.

Procedure Outlier_ detection

1. Select a functional space for sampling is RKHS. Optimal sampling points are obtained by applying the following procedure

1. Obtain m sampling points $S=\left\{y_n, 1 \leq n \leq m\right\} \in Y$  
2. Generate m space-filling curve by using Hilbert curve families
3. Construct a subspace and approximate the subspace by finding the eigenvectors of a compact operator by a kernel space.
4. The optimal method of reconstructing function $\tilde{\mathrm{f}}$ for the given function $f \in H_k$ from sampled data points $f(x)$

$\overline{f(x)}=\sum_{\mathrm{j}=1}^{\mathrm{m}} \alpha_{\mathrm{j}} \mathrm{k}\left(\mathrm{x}_{\mathrm{j}}, \mathrm{x}\right), \mathrm{x} \in \mathrm{Y}$

where the coefficients $\alpha_j, 1 \leq j \leq m$, are the solutions of

$\sum_{\mathrm{j}=1}^{\mathrm{m}} \alpha_{\mathrm{j}} \mathrm{k}\left(\mathrm{x}_{\mathrm{j}}, \mathrm{x}_{\mathrm{k}}\right)=\mathrm{f}\left(\mathrm{x}_{\mathrm{k}}\right)$

5. Optimal sampling points in Karhunen–Loève subspace is designed by kernel space and approximate the best one.
6. The n^th minimal reconstruction error of linear transformation is found out.

2. The error estimates using the function

0000.png

3. Obtain optimized sample points $S_{o p t}$ and compare it with the equalized sample points $S_{e q u}$     

4. Distance of each point from the optimized sample point of the curve is measured. If there are more deviations then that point is considered to be outlier.

5. Stop

3.3 Procedure for Outlier detection

The steps shown above describes the procedure for Generally, Outliers occur at the low probability region of the stochastic model, inliers occur at the high probability region. The number of sampling points m is fixed. The reconstruction RKHS and the approximation error measurement are the two factors that constitute the mechanisms of selecting the sampling points. According to the Gaussian Reconstruction kernel

$k_\sigma(u, v)=\exp \left(\frac{\|u-v\|^2}{\sigma}\right), u, v \in R^d$          (9)

where, $\sigma>0$ and $\|$.$\|$ denotes a standard Euclidean norm on higher dimensional space. The general form of reconstruction error is constructed as minimization problem as follows

$\min \int_\omega^u \operatorname{distance}{ }^2(K(u, .), \delta) d \mu(u)$

where, $\delta$ refers to subspace in n-dimensional space and $\mu$. Is variation on measurement space. The procedure for outlier detection is shown in Figure 2.

2.png

Figure 2. Three heat sources