Derivation of a scoring function for anomaly detection using eigen-decomposition
A computer program product and computer system configured to perform a method including: receiving input data including a multidimensional data point (MDDP), deriving a scoring function via data whitening by eigen-decomposition, and using the scoring function to provide a probability of whether the MDDP is normal or is an anomaly.
1 . A computer program product, comprising: a non-transitory tangible storage medium readable by a processing circuit and storing instructions for execution by the processing circuit for performing a method comprising:
receiving input data including a multidimensional data point (MDDP);
deriving a scoring function by performing data whitening that includes eigen-decomposition of a kernel matrix formed from the input data;
applying a transformation to the input data based on results of the eigen-decomposition to produce whitened data used for deriving the scoring function; and
using the scoring function to classify the MDDP as normal or as an anomaly.
2 . The computer program product of claim 1 , wherein the classification of the MDDP as an anomaly is indicative of detection of an unknown undesirable event, and, when the MDDP is classified as an anomaly, the method further comprises performing one or more of triggering an alarm, and/or sending a notification to a user or a data client system.
3 . The computer program product of claim 1 , wherein the deriving includes, training in a training phase that includes, for a training dataset T, forming an RBF kernel matrix G n×n for T with σ=J, forming a random matrix K (p+10)×n whose entries are Independent and Identically Distributed (i.i.d.) as a real Gaussian random variable of zero mean and unit variance, applying Rank Revealing QR (RRQR) to a matrix KG to get a set of p reference points R, and applying eigen decomposition to a reference submatrix {tilde over (G)} p×p to get Ũ p×p and {tilde over (S)} p×p , where {tilde over (G)} p×p is a submatrix of G n×n which is restricted only for the p reference points and where Ũ p×p and {tilde over (S)} p×p are orthogonal and diagonal matrices, respectively.
4 . The computer program product of claim 3 , wherein the training in the training phase further includes embedding T in : T n×p ={tilde over (h)}(T)=g σ (T, R)Ũ{tilde over (S)} −1/2 , post-embedding scaling by computing the columns means of T for embedding centralization and centralize it, applying SVD to T, to get
T
=
X
n
×
p
Λ
p
×
p
Y
p
×
p
T
,
setting
k
=
min
{
j
|
∑
i
=
1
j
λ
i
>
ρ
∑
i
=
1
p
λ
i
}
to form Λ k and Y k where Λ k is the upper left k×k submatrix of Λ and Y k is the k×p submatrix of Y which contains its k leftmost columns, and projecting centered embedded training data using a transformation
ψ
(
x
)
=
h
~
(
x
)
Y
k
Λ
k
-
1
2
,
x
∈
T
such that outputs of the training phase include reference set R, a pre-embedding scaler, a post-embedding scaler, Ũ, S, Λ k , Y k , and Ψ(T)={ψ(x)} x∈T .
5 . The computer program product of claim 4 , wherein inputs to the deriving and using the scoring function include an MDDP x∈ , outputs of the training phase, and l—number of nearest neighbors for scoring.
6 . The computer program product of claim 5 , wherein the deriving and using the scoring function includes applying a pre-embedding scaler to x, embedding x in : {tilde over (h)}(x)=g σ (x,R)Ũ{tilde over (S)} −1/2 , applying the post-embedding scaler to {tilde over (h)}(x), projecting
ψ
(
x
)
=
h
~
(
x
)
Y
k
Λ
k
-
1
2
,
computing the nearest neighbors of ψ(x), {y 1 , . . . , }⊂Ψ(T), and returning
s
(
x
)
=
∑
i
=
1
l
ψ
(
x
)
-
y
i
.
7 . The computer program product of claim 1 , wherein the deriving includes a training phase using a training dataset, wherein the computer program product is configured to reduce a computational cost by embedding the training dataset such that a number of principal component analysis computations is reduced from O(n 3 ) computations to O(n 2 p) computations, where n is a number of training datapoints and p is an embedding dimension, and wherein p<n.
8 . The computer program product of claim 1 , wherein the computer program product is configured to reduce a computational cost of using the scoring function by embedding datapoints to be scored such that a number of scoring computations is reduced from O(n 2 ) computations to O(p 2 ) computations for a single datapoint, where n is a number of datapoints and p is an embedding dimension, and wherein p<n.
9 . A computer system, comprising a hardware processor configurable to perform a method comprising:
receiving input data including a multidimensional data point (MDDP);
deriving a scoring function by performing data whitening that includes eigen-decomposition of a kernel matrix formed from the input data;
applying a transformation to the input data based on results of the eigen-decomposition to produced whitened data used for deriving the scoring function; and
using the scoring function to classify the MDDP as normal or as an anomaly.
10 . The computer system of claim 9 , wherein the classification of the MDDP as an anomaly is indicative of detection of an unknown undesirable event, and, when the MDDP is classified as an anomaly, the hardware processor is further configurable to perform one or more of triggering an alarm, and/or sending a notification to a user or a data client system.
11 . The computer system of claim 9 , wherein the deriving includes, training in a training phase that includes, for a training dataset T, forming an RBF kernel matrix G n×n for T with σ=J, forming a random matrix K (p+10)×n whose entries are Independent and Identically Distributed (i.i.d.) as a real Gaussian random variable of zero mean and unit variance, applying Rank Revealing QR (RRQR) to a matrix KG to get a set of p reference points R, and applying eigen decomposition to a reference submatrix {tilde over (G)} p×p , to get Ũ p×p and {tilde over (S)} p×p , where {tilde over (G)}p×p is a submatrix of G n×n which is restricted only for the p reference points and where {tilde over (Ũ)} p×p and {tilde over (S)} p×p are orthogonal and diagonal matrices, respectively.
12 . The computer system of claim 11 , wherein the training in the training phase further includes embedding T in : T n×p ={tilde over (h)}(T)=g σ (T, R)Ũ{tilde over (S)} −1/2 , post-embedding scaling by computing the columns means of T for embedding centralization and centralize it, applying SVD to T, to get
T
=
X
n
×
p
Λ
p
×
p
Y
p
×
p
T
,
setting
k
=
min
{
j
|
∑
i
=
1
j
λ
i
>
ρ
∑
i
=
1
p
λ
i
}
to form Λ k and Y k where Λ k is the upper left k×k submatrix of Λ and Y k is the k×p submatrix of Y which contains its k leftmost columns, and projecting centered embedded training data using a transformation
ψ
(
x
)
=
h
~
(
x
)
Y
k
Λ
k
-
1
2
,
x
∈
T
such that outputs of the training phase include reference set R, a pre-embedding scaler, a post-embedding scaler, Ũ, S, Λ k , Y k , and Ψ(T)={ψ(x)} x∈T .
13 . The computer system of claim 12 , wherein inputs to the deriving and using the scoring function include an MDDP x∈ , outputs of the training phase, and l—number of nearest neighbors for scoring.
14 . The computer system of claim 13 , wherein the deriving and using the scoring function includes applying a pre-embedding scaler to x, embedding x in : {tilde over (h)}(x)=g σ (x,R)Ũ{tilde over (S)} −1/2 , applying the post-embedding scaler to {tilde over (h)}(x), projecting
ψ
(
x
)
=
h
~
(
x
)
Y
k
Λ
k
-
1
2
,
computing the nearest neighbors of ψ(x), {y 1 , . . . , }⊂Ψ(T), and returning
s
(
x
)
=
∑
i
=
1
l
ψ
(
x
)
-
y
i
.
15 . The computer system of claim 9 , wherein the deriving includes a training phase using a training dataset, wherein the computer system is configured to reduce a computational cost by embedding the training dataset such that a number of principal component analysis computations is reduced from O(n 3 ) computations to O(n 2 p) computations, where n is a number of training datapoints and p is an embedding dimension, wherein p<n.
16 . The computer system of claim 9 , configured to reduce a computational cost of using the scoring function by embedding datapoints to be scored such that a number of scoring computations is reduced from O(n 2 ) computations to O(p 2 ) computations for a single datapoint, where n is a number of datapoints and p is an embedding dimension, wherein p<n.
17 . A method comprising:
receiving input data including a multidimensional data point (MDDP);
deriving a scoring function by performing data whitening that includes eigen-decomposition of a kernel matrix formed from the input data;
applying a transformation to the input data based on results of the eigen-decomposition to produced whitened data used for deriving the scoring function; and
using the scoring function to classify the MDDP as normal or as an anomaly.
18 . The method of claim 17 , wherein the classification of the MDDP as an anomaly is indicative of detection of an unknown undesirable event, and, when the MDDP is classified as an anomaly, the method further comprises performing one or more of triggering an alarm, and/or sending a notification to a user or a data client system.
19 . The method of claim 17 , wherein the deriving includes, training in a training phase that includes, for a training dataset T, forming an RBF kernel matrix G n×n for T with σ=J, forming a random matrix K (p+10)×n whose entries are Independent and Identically Distributed (i.i.d.) as a real Gaussian random variable of zero mean and unit variance, applying Rank Revealing QR (RRQR) to a matrix KG to get a set of p reference points R, and applying eigen decomposition to a reference submatrix {tilde over (G)} p×p to get Ũ p×p and {tilde over (S)} p×p , where {tilde over (G)} p×p is a submatrix of G n×n which is restricted only for the p reference points and where Ũ p×p and {tilde over (S)} p×p are orthogonal and diagonal matrices, respectively.
20 . The method of claim 19 , wherein the training in the training phase further includes embedding T in : T n×p ={tilde over (h)}(T)=g σ (T, R)Ũ{tilde over (S)} −1/2 , post-embedding scaling by computing the columns means of T for embedding centralization and centralize it, applying SVD to T, to get
T
=
X
n
×
p
Λ
p
×
p
Y
p
×
p
T
,
setting
k
=
min
{
j
|
∑
i
=
1
j
λ
i
>
ρ
∑
i
=
1
p
λ
i
}
to form Λ k and Y k where Λ k is the upper left k×k submatrix of Λ and Y k is the k×p submatrix of Y which contains its k leftmost columns, and projecting centered embedded training data using a transformation
ψ
(
x
)
=
h
~
(
x
)
Y
k
Λ
k
-
1
2
,
x
∈
T
such that outputs of the training phase include reference set R, a pre-embedding scaler, a post-embedding scaler, Ũ, S, Λ k′ , Y k , and Ψ(T)={ψ(x)} x∈T .
21 . The method of claim 20 , wherein inputs to the deriving and using the scoring function include an MDDP x∈ , outputs of the training phase, and l—number of nearest neighbors for scoring.
22 . The method of claim 21 , wherein the deriving and using the scoring function includes applying a pre-embedding scaler to x, embedding x in : {tilde over (h)}(x)=g σ (x, R)Ũ{tilde over (S)} −1/2 , applying the post-embedding scaler to {tilde over (h)}(x), projecting
ψ
(
x
)
=
h
~
(
x
)
Y
k
Λ
k
-
1
2
,
computing the nearest neighbors of
ψ
(
x
)
,
{
y
1
,
…
,
y
ℓ
}
⊂
Ψ
(
T
)
,
and
returning
s
(
x
)
=
∑
i
=
1
l
ψ
(
x
)
-
y
i
.
23 . The method of claim 17 , wherein the deriving includes a training phase using a training dataset, wherein the method provides a reduced computational cost by embedding the training dataset such that a number of principal component analysis computations is reduced from O(n 3 ) computations to O(n 2 p) computations, where n is a number of training datapoints and p is an embedding dimension, and wherein p<n.
24 . The method of claim 17 , wherein the method provides a reduced computational cost of using the scoring function by embedding datapoints to be scored such that a number of scoring computations is reduced from O(n 2 ) computations to O(p 2 ) computations for a single datapoint, where n is a number of datapoints and p is an embedding dimension, and wherein p<n.