US10509847B1ActiveUtility
Local outlier factor hyperparameter tuning for data outlier detection
Est. expiryFeb 11, 2039(~12.6 yrs left)· nominal 20-yr term from priority
G06F 17/18G06F 17/16
91
PatentIndex Score
23
Cited by
8
References
30
Claims
Abstract
A computing device determines hyperparameter values for outlier detection. An LOF score is computed for observation vectors using a neighborhood size value. Outlier observation vectors are selected from the observation vectors. Outlier mean and outlier variance values are computed of the LOF scores of the outlier observation vectors. Inlier observation vectors are selected from the observation vectors that have highest computed LOF scores of the observation vectors that are not included in the outlier observation vectors. Inlier mean and inlier variance values are computed of the LOF scores of the inlier observation vectors. A difference value is computed using the outlier mean and variance values and the inlier mean and variance values. The process is repeated with each neighborhood size value of a plurality of neighborhood size values. A tuned neighborhood size value is selected as the neighborhood size value associated with an extremum value of the difference value.
Claims
exact text as granted — not AI-modifiedWhat is claimed is:
1. A non-transitory computer-readable medium having stored thereon computer-readable instructions that when executed by a computing device cause the computing device to:
(A) define a contamination value;
(B) select a neighborhood size value from a plurality of neighborhood size values;
(C) compute a local outlier factor (LOF) score for each observation vector of a plurality of observation vectors using the selected neighborhood size value, wherein each observation vector of the plurality of observation vectors includes a variable value for each variable of a plurality of variables;
(D) select a number of outlier observation vectors from the plurality of observation vectors to define an outlier set of observation vectors, wherein the number of outlier observation vectors is the defined contamination value, wherein the outlier set of observation vectors have highest computed LOF scores of the plurality of observation vectors;
(E) compute an outlier mean value of the LOF scores computed for the outlier set of observation vectors;
(F) compute an outlier variance value of the LOF scores computed for the outlier set of observation vectors;
(G) select a number of inlier observation vectors from the plurality of observation vectors to define an inlier set of observation vectors, wherein the number of inlier observation vectors is the defined contamination value, wherein the inlier set of observation vectors have highest computed LOF scores of the plurality of observation vectors that are not included in the outlier set of observation vectors;
(H) compute an inlier mean value of the LOF scores computed for the inlier set of observation vectors;
(I) compute an inlier variance value of the LOF scores computed for the inlier set of observation vectors;
(J) compute a difference value using the computed outlier mean value, the computed outlier variance value, the computed inlier mean value, and the computed inlier variance value;
(K) repeat (B) to (J) with each remaining neighborhood size value of the plurality of neighborhood size values as the selected neighborhood size value;
(L) select a tuned neighborhood size value as the neighborhood size value associated with an extremum value of the difference value computed for each neighborhood size value of the plurality of neighborhood size values; and
(M) output the selected, tuned neighborhood size value, an outlier threshold that is a lowest LOF score of the LOF scores computed for the outlier set of observation vectors, and the defined contamination value for determining if a new observation vector is an outlier observation vector using a trained LOF model that includes the selected, tuned neighborhood size value, the outlier threshold, and the defined contamination value.
2. The non-transitory computer-readable medium of claim 1 , wherein the outlier mean value, the outlier variance value, the inlier mean value, and the inlier variance value are computed for the logarithm of the LOF scores in (E), (F), (H), and (I), respectively.
3. The non-transitory computer-readable medium of claim 1 , wherein, after (K) and before (L), the computer-readable instructions further cause the computing device to:
(AA) compute a grid outlier mean value from the outlier mean value computed for each neighborhood size value of the plurality of neighborhood size values;
(AB) compute a grid outlier variance value from the outlier mean value computed for each neighborhood size value of the plurality of neighborhood size values;
(AC) compute a grid inlier mean value from the inlier mean value computed for each neighborhood size value of the plurality of neighborhood size values;
(AD) compute a grid inlier variance value from the inlier mean value computed for each neighborhood size value of the plurality of neighborhood size values;
(AE) compute a non-centrality parameter value using the computed grid outlier mean value, the computed grid outlier variance value, the grid computed inlier mean value, and the computed grid inlier variance value;
(AF) compute a degrees of freedom value using the defined contamination value; and
(AG) repeat (A) to (K) and (AA) to (AF) with each remaining contamination value of a plurality of contamination values as the defined contamination value;
wherein, after (AG) and before (L), the computer-readable instructions further cause the computing device to
(AH) compute a probability value for each contamination value of the plurality of contamination values using the difference value computed for each selected, tuned neighborhood size value, the non-centrality parameter value, and the degrees of freedom value computed for each contamination value of the plurality of contamination values; and
(AI) select a tuned contamination value as the contamination value associated with a second extremum value of the probability value computed for each contamination value of the plurality of contamination values,
wherein the defined contamination value output in (M) is the selected, tuned contamination value.
4. The non-transitory computer-readable medium of claim 3 , wherein, after (AI) and before (M), the computer-readable instructions further cause the computing device to:
select a second tuned neighborhood size value as the neighborhood size value associated with the selected, tuned contamination value,
wherein the selected, tuned neighborhood size value output in (M) is the selected, second tuned neighborhood size value.
5. The non-transitory computer-readable medium of claim 4 , wherein, after selecting the second tuned neighborhood size value, the computer-readable instructions further cause the computing device to:
receive the new observation vector;
determine a plurality of nearest neighbors to the received new observation vector from the plurality of observation vectors, wherein a number of the plurality of nearest neighbors is the selected, second tuned neighborhood size value, wherein the plurality of nearest neighbors have minimum distances to the new observation vector;
compute a second LOF score for the received new observation vector using the determined plurality of nearest neighbors; and
when the computed second LOF score is greater than the outlier threshold, identify the received new observation vector as an outlier.
6. The non-transitory computer-readable medium of claim 5 , wherein when the received new observation vector is identified as an outlier, output an indicator of detection of an anomaly.
7. The non-transitory computer-readable medium of claim 3 , wherein the probability value is computed using a non-central t distribution.
8. The non-transitory computer-readable medium of claim 3 , wherein the non-centrality parameter value is computed using
p
c
n
=
M
c
n
,
out
-
M
c
n
,
in
1
c
n
(
V
c
n
,
out
+
V
c
n
,
in
)
,
where M c n ,out is the computed grid outlier mean value, V c n ,out is the computed grid outlier variance value, M c n ,in is the grid computed inlier mean value, V c n ,in is the computed grid inlier variance value, and c n is the defined contamination value.
9. The non-transitory computer-readable medium of claim 3 , wherein the degrees of freedom value is computed using f c n =2c n −2 where c n is the defined contamination value.
10. The non-transitory computer-readable medium of claim 1 , wherein the difference value is computed using T c n ,k n
T
c
n
,
k
n
=
μ
c
n
,
k
n
,
out
-
μ
c
n
,
k
n
,
in
1
c
n
(
v
c
n
,
k
n
,
out
+
v
c
n
,
k
n
,
in
)
,
where μ c n ,k n ,out is the computed outlier mean value, v c n ,k n ,out is the computed outlier variance value, μ c n ,k n ,in is the computed inlier mean value, v c n ,k n ,in is the computed inlier variance value, and c n is the defined contamination value.
11. The non-transitory computer-readable medium of claim 10 , wherein the outlier mean value is computed using
μ
c
n
,
k
n
,
out
=
∑
i
=
1
c
n
ln
LOF
i
c
n
,
where LOF i is the computed LOF score of an i th selected outlier observation vector of the outlier set of observation vectors, and ln LOF i is a natural logarithm of LOF i .
12. The non-transitory computer-readable medium of claim 10 , wherein the outlier variance value is computed using
v
c
n
,
k
n
,
out
=
∑
i
=
1
c
n
(
ln
(
LOF
i
)
-
μ
c
n
,
k
n
,
out
)
2
c
n
,
where LOF i is the computed LOF score of an i th selected outlier observation vector of the outlier set of observation vectors, and ln LOF i is a natural logarithm of LOF i .
13. The non-transitory computer-readable medium of claim 10 , wherein the inlier mean value is computed using
μ
c
n
,
k
n
,
in
=
∑
i
=
1
c
n
ln
LOF
i
c
n
,
where LOF i is the computed LOF score of an i th selected inlier observation vector of the inlier set of observation vectors, and ln LOF i is a natural logarithm of LOF i .
14. The non-transitory computer-readable medium of claim 10 , wherein the inlier variance value is computed using
v
c
n
,
k
n
,
in
=
∑
i
=
1
c
n
(
ln
(
LOF
i
)
-
μ
c
n
,
k
n
,
in
)
2
c
n
,
where LOF i is the computed LOF score of an i th selected inlier observation vector of the inlier set of observation vectors, and ln LOF i is a natural logarithm of LOF i .
15. The non-transitory computer-readable medium of claim 1 , wherein, before (C), the computer-readable instructions further cause the computing device to:
apply a dimension reduction method to each observation vector of the plurality of observation vectors to define principal components; and
project each observation vector of the plurality of observation vectors into a space defined by the principal components,
wherein each observation vector of the plurality of observation vectors in (C) is the projected observation vector.
16. The non-transitory computer-readable medium of claim 1 , wherein, after (M), the computer-readable instructions further cause the computing device to:
receive the new observation vector;
determine a plurality of nearest neighbors to the received new observation vector from the plurality of observation vectors, wherein a number of the plurality of nearest neighbors is the selected, tuned neighborhood size value, wherein the plurality of nearest neighbors have minimum distances to the new observation vector;
compute a second LOF score for the received new observation vector using the determined plurality of nearest neighbors; and
when the computed second LOF score is greater than the outlier threshold, identify the received new observation vector as an outlier.
17. The non-transitory computer-readable medium of claim 16 , wherein when the received new observation vector is identified as an outlier, output an indicator of detection of an anomaly.
18. The non-transitory computer-readable medium of claim 16 , wherein after (L), the plurality of observation vectors is output to determine the plurality of nearest neighbors to the received new observation vector.
19. A computing device comprising:
a processor; and
a non-transitory computer-readable medium operably coupled to the processor, the computer-readable medium having computer-readable instructions stored thereon that, when executed by the processor, cause the computing device to
(A) define a contamination value;
(B) select a neighborhood size value from a plurality of neighborhood size values;
(C) compute a local outlier factor (LOF) score for each observation vector of a plurality of observation vectors using the selected neighborhood size value, wherein each observation vector of the plurality of observation vectors includes a variable value for each variable of a plurality of variables;
(D) select a number of outlier observation vectors from the plurality of observation vectors to define an outlier set of observation vectors, wherein the number of outlier observation vectors is the defined contamination value, wherein the outlier set of observation vectors have highest computed LOF scores of the plurality of observation vectors;
(E) compute an outlier mean value of the LOF scores computed for the outlier set of observation vectors;
(F) compute an outlier variance value of the LOF scores computed for the outlier set of observation vectors;
(G) select a number of inlier observation vectors from the plurality of observation vectors to define an inlier set of observation vectors, wherein the number of inlier observation vectors is the defined contamination value, wherein the inlier set of observation vectors have highest computed LOF scores of the plurality of observation vectors that are not included in the outlier set of observation vectors;
(H) compute an inlier mean value of the LOF scores computed for the inlier set of observation vectors;
(I) compute an inlier variance value of the LOF scores computed for the inlier set of observation vectors;
(J) compute a difference value using the computed outlier mean value, the computed outlier variance value, the computed inlier mean value, and the computed inlier variance value;
(K) repeat (B) to (J) with each remaining neighborhood size value of the plurality of neighborhood size values as the selected neighborhood size value;
(L) select a tuned neighborhood size value as the neighborhood size value associated with an extremum value of the difference value computed for each neighborhood size value of the plurality of neighborhood size values; and
(M) output the selected, tuned neighborhood size value, an outlier threshold that is a lowest LOF score of the LOF scores computed for the outlier set of observation vectors, and the defined contamination value for determining if a new observation vector is an outlier observation vector using a trained LOF model that includes the selected, tuned neighborhood size value, the outlier threshold, and the defined contamination value.
20. A method of determining hyperparameter values for a local outlier factor outlier detection, the method comprising:
(A) defining, by a computing device, a contamination value;
(B) selecting, by the computing device, a neighborhood size value from a plurality of neighborhood size values;
(C) computing, by the computing device, a local outlier factor (LOF) score for each observation vector of a plurality of observation vectors using the selected neighborhood size value, wherein each observation vector of the plurality of observation vectors includes a variable value for each variable of a plurality of variables;
(D) selecting, by the computing device, a number of outlier observation vectors from the plurality of observation vectors to define an outlier set of observation vectors, wherein the number of outlier observation vectors is the defined contamination value, wherein the outlier set of observation vectors have highest computed LOF scores of the plurality of observation vectors;
(E) computing, by the computing device, an outlier mean value of the LOF scores computed for the outlier set of observation vectors;
(F) computing, by the computing device, an outlier variance value of the LOF scores computed for the outlier set of observation vectors;
(G) selecting, by the computing device, a number of inlier observation vectors from the plurality of observation vectors to define an inlier set of observation vectors, wherein the number of inlier observation vectors is the defined contamination value, wherein the inlier set of observation vectors have highest computed LOF scores of the plurality of observation vectors that are not included in the outlier set of observation vectors;
(H) computing, by the computing device, an inlier mean value of the LOF scores computed for the inlier set of observation vectors;
(I) computing, by the computing device, an inlier variance value of the LOF scores computed for the inlier set of observation vectors;
(J) computing, by the computing device, a difference value using the computed outlier mean value, the computed outlier variance value, the computed inlier mean value, and the computed inlier variance value;
(K) repeating, by the computing device, (B) to (J) with each remaining neighborhood size value of the plurality of neighborhood size values as the selected neighborhood size value;
(L) selecting, by the computing device, a tuned neighborhood size value as the neighborhood size value associated with an extremum value of the difference value computed for each neighborhood size value of the plurality of neighborhood size values; and
(M) outputting, by the computing device, the selected, tuned neighborhood size value, an outlier threshold that is a lowest LOF score of the LOF scores computed for the outlier set of observation vectors, and the defined contamination value for determining if a new observation vector is an outlier observation vector using a trained LOF model that includes the selected, tuned neighborhood size value, the outlier threshold, and the defined contamination value.
21. The method of claim 20 , wherein the outlier mean value, the outlier variance value, the inlier mean value, and the inlier variance value are computed for the logarithm of the LOF scores in (E), (F), (H), and (I), respectively.
22. The method of claim 20 , wherein, after (K) and before (L), further comprising:
(AA) computing, by the computing device, a grid outlier mean value from the outlier mean value computed for each neighborhood size value of the plurality of neighborhood size values;
(AB) computing, by the computing device, a grid outlier variance value from the outlier mean value computed for each neighborhood size value of the plurality of neighborhood size values;
(AC) computing, by the computing device, a grid inlier mean value from the inlier mean value computed for each neighborhood size value of the plurality of neighborhood size values;
(AD) computing, by the computing device, a grid inlier variance value from the inlier mean value computed for each neighborhood size value of the plurality of neighborhood size values;
(AE) computing, by the computing device, a non-centrality parameter value using the computed grid outlier mean value, the computed grid outlier variance value, the grid computed inlier mean value, and the computed grid inlier variance value;
(AF) computing, by the computing device, a degrees of freedom value using the defined contamination value;
(AG) repeating, by the computing device, (A) to (K) and (AA) to (AF) with each remaining contamination value of a plurality of contamination values as the defined contamination value;
wherein, after (AG) and before (L), the computer-readable instructions further cause the computing device to
(AH) computing, by the computing device, a probability value for each contamination value of the plurality of contamination values using the difference value computed for each selected, tuned neighborhood size value, the non-centrality parameter value, and the degrees of freedom value computed for each contamination value of the plurality of contamination values; and
(AI) selecting, by the computing device, a tuned contamination value as the contamination value associated with a second extremum value of the probability value computed for each contamination value of the plurality of contamination values,
wherein the defined contamination value output in (M) is the selected, tuned contamination value.
23. The method of claim 22 , wherein, after (AI) and before (M), further comprising:
selecting, by the computing device, a second tuned neighborhood size value as the neighborhood size value associated with the selected, tuned contamination value,
wherein the selected, tuned neighborhood size value output in (M) is the selected, second tuned neighborhood size value.
24. The method of claim 22 , wherein the probability value is computed using a non-central t distribution.
25. The method of claim 22 , wherein the non-centrality parameter value is computed using
p
c
n
=
M
c
n
,
out
-
M
c
n
,
in
1
c
n
(
V
c
n
,
out
+
V
c
n
,
in
)
,
where M c n ,out is the computed grid outlier mean value, V c n ,out is the computed grid outlier variance value, M c n ,in is the grid computed inlier mean value, V c n ,in is the computed grid inlier variance value, and c n is the defined contamination value.
26. The method of claim 22 , wherein the degrees of freedom value is computed using f c n =2c n −2 where c n is the defined contamination value.
27. The method of claim 20 , wherein the difference value is computed using
T
c
n
,
k
n
=
μ
c
n
,
k
n
,
out
-
μ
c
n
,
k
n
,
in
1
c
n
(
v
c
n
,
k
n
,
out
+
v
c
n
,
k
n
,
in
)
,
where μ c n ,k n ,out is the computed outlier mean value, v c n ,k n ,out is the computed outlier variance value, μ c n ,k n ,in is the computed inlier mean value, v c n ,k n ,in is the computed inlier variance value, and c n is the defined contamination value.
28. The method of claim 27 , wherein the outlier mean value is computed using
μ
c
n
,
k
n
,
out
=
∑
i
=
1
c
n
ln
LOF
i
c
n
,
where LOF i is the computed LOF score of an i th selected outlier observation vector of the outlier set of observation vectors, and ln LOF i is a natural logarithm of LOF i .
29. The method of claim 27 , wherein the outlier variance value is computed using
v
c
n
,
k
n
,
out
=
∑
i
=
1
c
n
(
ln
(
LOF
i
)
-
μ
c
n
,
k
n
,
out
)
2
c
n
,
where LOF i is the computed LOF score of an i th selected outlier observation vector of the outlier set of observation vectors, and ln LOF i is a natural logarithm of LOF i .
30. The method of claim 20 , wherein, after (M), further comprising:
receiving, by the computing device, the new observation vector;
determining, by the computing device, a plurality of nearest neighbors to the received new observation vector from the plurality of observation vectors, wherein a number of the plurality of nearest neighbors is the selected, tuned neighborhood size value, wherein the plurality of nearest neighbors have minimum distances to the new observation vector;
computing, by the computing device, a second LOF score for the received new observation vector using the determined plurality of nearest neighbors; and
when the computed second LOF score is greater than the outlier threshold, identifying, by the computing device, the received new observation vector as an outlier.Cited by (0)
No later patents cite this yet.
References (0)
No backward citations on record.