2 * ============LICENSE_START=======================================================
3 * Copyright (C) 2016-2018 Ericsson. All rights reserved.
4 * Modifications Copyright (C) 2020 Nordix Foundation.
5 * ================================================================================
6 * Licensed under the Apache License, Version 2.0 (the "License");
7 * you may not use this file except in compliance with the License.
8 * You may obtain a copy of the License at
10 * http://www.apache.org/licenses/LICENSE-2.0
12 * Unless required by applicable law or agreed to in writing, software
13 * distributed under the License is distributed on an "AS IS" BASIS,
14 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
15 * See the License for the specific language governing permissions and
16 * limitations under the License.
18 * SPDX-License-Identifier: Apache-2.0
19 * ============LICENSE_END=========================================================
22 package org.onap.policy.apex.examples.adaptive.model.java;
24 import java.util.Arrays;
25 import java.util.LinkedHashMap;
26 import java.util.LinkedList;
27 import java.util.List;
30 import org.apache.commons.math3.distribution.TDistribution;
31 import org.apache.commons.math3.util.FastMath;
32 import org.onap.policy.apex.core.engine.executor.context.TaskSelectionExecutionContext;
33 import org.onap.policy.apex.examples.adaptive.concepts.AnomalyDetection;
34 import org.onap.policy.apex.model.basicmodel.concepts.ApexException;
35 import org.slf4j.Logger;
38 * The Class AnomalyDetectionPolicyDecideTaskSelectionLogic.
40 public class AnomalyDetectionPolicyDecideTaskSelectionLogic {
42 // Recurring string constants
43 private static final String ANOMALY_DETECTION_ALBUM = "AnomalyDetectionAlbum";
44 private static final String ANOMALY_DETECTION = "AnomalyDetection";
47 private static final double ANOMALY_SENSITIVITY = 0.05;
48 private static final int FREQUENCY = 360;
51 * Some utility methods
53 // exponential = 2(n+1)
54 private static final double EMA_EXPONENT = 2.0 / (7.0 + 1.0);
55 private static final double EMA_EXPONENT_1 = (1.0 - EMA_EXPONENT);
58 * A map to hold the Anomaly degree/levels/probabilities required for each task.<br>
59 * If there is no task defined for a calculated anomaly-degree, then the default task is
61 * The map use (LinkedHashMap) is an insertion-ordered map, so the first interval matching a
64 // CHECKSTYLE:OFF: checkstyle:magicNumber
65 private static final Map<double[], String> TASK_INTERVALS = new LinkedHashMap<>();
68 TASK_INTERVALS.put(new double[] {0.0, 0.1}, null); // null will mean default task
69 TASK_INTERVALS.put(new double[] {0.25, 0.5}, "AnomalyDetectionDecideTask1");
70 TASK_INTERVALS.put(new double[] {0.5, 1.01}, "AnomalyDetectionDecideTask2");
72 // CHECKSTYLE:ON: checkstyle:magicNumber
77 * @param executor the executor
80 public boolean getTask(final TaskSelectionExecutionContext executor) {
81 String id = executor.subject.getId();
82 executor.logger.debug(id);
83 String inFields = executor.inFields.toString();
84 executor.logger.debug(inFields);
85 final double now = (Double) (executor.inFields.get("MonitoredValue"));
86 final Integer iteration = (Integer) (executor.inFields.get("Iteration"));
87 // get the double[forecastedValue, AnomalyScore, AnomalyProbability]
88 final double[] vals = forecastingAndAnomaly(executor, now);
89 final double anomalyness = vals[2];
91 for (final Map.Entry<double[], String> i : TASK_INTERVALS.entrySet()) {
92 if (checkInterval(anomalyness, i.getKey())) {
98 executor.subject.getDefaultTaskKey().copyTo(executor.selectedTask);
100 executor.subject.getTaskKey(task).copyTo(executor.selectedTask);
102 executor.logger.debug(
103 "TestAnomalyDetectionTSLPolicy0000DecideStateTaskSelectionLogic.getTask():\t************\t\t\t\t"
104 + "Iteration:\t{}\tValue:\t{}\tForecast:\t{}\tAnomalyScore:\t{}\tAnomalyProbability:\t{}\t"
105 + "Invoking Task:\t{}", iteration, now, vals[0], vals[1], vals[2], executor.selectedTask);
110 * Anomaly detection and forecast.
112 * @param value The current value
113 * @return Null if the function can not be executed correctly, otherwise double[forecastedValue,
114 * AnomalyScore, AnomalyProbability]
116 private double[] forecastingAndAnomaly(final TaskSelectionExecutionContext executor, final double value) {
118 executor.getContextAlbum(ANOMALY_DETECTION_ALBUM).lockForWriting(ANOMALY_DETECTION);
119 } catch (final ApexException e) {
120 executor.logger.error("Failed to acquire write lock on \"AnomalyDetection\" context", e);
121 return new double[0];
124 // Get the context object
125 AnomalyDetection anomalyDetection =
126 (AnomalyDetection) executor.getContextAlbum(ANOMALY_DETECTION_ALBUM).get(ANOMALY_DETECTION);
127 if (anomalyDetection == null) {
128 anomalyDetection = new AnomalyDetection();
129 executor.getContextAlbum(ANOMALY_DETECTION_ALBUM).put(ANOMALY_DETECTION, anomalyDetection);
132 // Check the lists are initialized
133 if (!anomalyDetection.isInitialized()) {
134 anomalyDetection.init(FREQUENCY);
137 boolean unsetfirstround = false;
139 int frequency = anomalyDetection.getFrequency();
140 frequency = frequency + 1;
142 // reset frequency counter
143 if (frequency >= FREQUENCY) {
144 unsetfirstround = true;
147 anomalyDetection.setFrequency(frequency);
149 if (unsetfirstround && anomalyDetection.getFirstRound()) {
150 anomalyDetection.setFirstRound(false);
153 // --------- calculate the forecasted value - simple version
154 final Double lastForecast = anomalyDetection.getFrequencyForecasted().get(frequency);
156 // get forecast for current value
157 final double forecastedValue = lastForecast == null ? value : expMovingAverage(value, lastForecast);
159 // --------- calculate the anomalyScore
160 final double anomalyScore = lastForecast == null ? 0.0 : FastMath.abs(lastForecast - value);
162 anomalyDetection.getFrequencyForecasted().set(frequency, forecastedValue);
164 // anomaly score is ignored in the first frequency period
165 if (!anomalyDetection.getFirstRound()) {
166 ((LinkedList<Double>) anomalyDetection.getAnomalyScores()).addLast(anomalyScore);
169 // CHECKSTYLE:OFF: checkstyle:magicNumber
170 // max FREQUENCY*4 anomaly scores history
171 listSizeControl(anomalyDetection.getAnomalyScores(), FREQUENCY * 4);
173 // ---------- calculate the anomaly probability
174 double anomalyProbability = 0.0;
175 if (anomalyDetection.getAnomalyScores().size() > 30) {
177 anomalyProbability = getStatsTest(anomalyDetection.getAnomalyScores(), ANOMALY_SENSITIVITY);
179 // CHECKSTYLE:ON: checkstyle:magicNumber
182 executor.getContextAlbum(ANOMALY_DETECTION_ALBUM).unlockForWriting(ANOMALY_DETECTION);
183 } catch (final ApexException e) {
184 executor.logger.error("Failed to release write lock on \"AnomalyDetection\" context", e);
185 return new double[0];
188 return new double[] {forecastedValue, anomalyScore, anomalyProbability};
192 * Is the passed value inside the interval, i.e. (value < interval[1] && value>=interval[0]).
194 * @param value The value to check
195 * @param interval A 2 element double array describing an interval
196 * @return true if the value is between interval[0] (inclusive) and interval[1] (exclusive),
197 * i.e. (value < interval[1] && value>=interval[0]). Otherwise false;
199 private static boolean checkInterval(final double value, final double[] interval) {
200 if (interval == null || interval.length != 2) {
201 throw new IllegalArgumentException("something other than an interval passed to checkInterval");
203 final double min = interval[0];
204 final double max = interval[1];
205 return (value < max && value >= min);
209 * calculate the anomaly probability using statistical test.
211 * @param values the values
212 * @param significanceLevel the significance level
213 * @return the anomaly probability
215 private static double getStatsTest(final List<Double> values, final double significanceLevel) {
216 if (isAllEqual(values)) {
219 // the targeted value or the last value
220 final double currentV = values.get(values.size() - 1);
221 Double[] lvaluesCopy = values.toArray(new Double[values.size()]);
222 Arrays.sort(lvaluesCopy); // takes ~40% of method time
224 double mean = getMean(lvaluesCopy);
225 // get the test value: val
226 double val = getV(lvaluesCopy, mean, true);
227 // get the p value for the test value
228 double pvalue = getPValue(lvaluesCopy, val, mean); // takes approx 25% of method time
230 // check the critical level
231 while (pvalue < significanceLevel) { // takes approx 20% of method time
232 // the score value as the anomaly probability
233 final double score = (significanceLevel - pvalue) / significanceLevel;
234 if (Double.compare(val, currentV) == 0) {
237 // do the critical check again for the left values
238 lvaluesCopy = removevalue(lvaluesCopy, val);
239 if (isAllEqual(lvaluesCopy)) {
243 mean = getMean(lvaluesCopy);
244 val = getV(lvaluesCopy, mean, true);
245 pvalue = getPValue(lvaluesCopy, val, mean);
251 * Get the test value based on mean from sorted values.
253 * @param lvalues the l values
254 * @param mean the mean
255 * @param maxValueOnly : only the max extreme value will be tested
256 * @return the value to be tested
258 private static double getV(final Double[] lvalues, final double mean, final boolean maxValueOnly) {
259 double val = lvalues[lvalues.length - 1];
260 // max value as the extreme value
264 // check the extreme side
265 if ((val - mean) < (mean - lvalues[0])) {
272 * calculate the P value for the t distribution.
274 * @param lvalues the l values
275 * @param val the value
276 * @param mean the mean
277 * @return the p value
279 private static double getPValue(final Double[] lvalues, final double val, final double mean) {
281 final double z = FastMath.abs(val - mean) / getStdDev(lvalues, mean);
283 final double n = lvalues.length;
284 final double s = (z * z * n * (2.0 - n)) / (z * z * n - (n - 1.0) * (n - 1.0));
285 final double t = FastMath.sqrt(s);
286 // default p value = 0
288 if (!Double.isNaN(t)) {
289 // t distribution with n-2 degrees of freedom
290 final TDistribution tDist = new TDistribution(n - 2);
291 pvalue = n * (1.0 - tDist.cumulativeProbability(t));
292 // set max pvalue = 1
293 pvalue = pvalue > 1.0 ? 1.0 : pvalue;
299 * exponential moving average.
301 * @param value the value
302 * @param lastForecast the last forecast
305 private static double expMovingAverage(final double value, final double lastForecast) {
306 return (value * EMA_EXPONENT) + (lastForecast * EMA_EXPONENT_1);
310 * Remove the first occurrence of the value val from the array.
312 * @param lvalues the l values
313 * @param val the value
314 * @return the double[]
316 private static Double[] removevalue(final Double[] lvalues, final double val) {
317 for (int i = 0; i < lvalues.length; i++) {
318 if (Double.compare(lvalues[i], val) == 0) {
319 final Double[] ret = new Double[lvalues.length - 1];
320 System.arraycopy(lvalues, 0, ret, 0, i);
321 System.arraycopy(lvalues, i + 1, ret, i, lvalues.length - i - 1);
329 * get mean value of double list.
331 * @param lvalues the l values
334 private static double getMean(final Double[] lvalues) {
336 for (final double d : lvalues) {
340 return sum / lvalues.length;
344 * get standard deviation of double list.
346 * @param lvalues the l values
347 * @param mean the mean
350 private static double getStdDev(final Double[] lvalues, final double mean) {
352 for (final double d : lvalues) {
353 temp += (mean - d) * (mean - d);
355 return FastMath.sqrt(temp / lvalues.length);
359 * Chop head off list to make it length max .
361 * @param list the list to chop
362 * @param max the max size
364 private static void listSizeControl(final List<?> list, final int max) {
365 final int k = list.size();
367 // Chop the head off the list.
368 list.subList(0, k - max).clear();
373 * return true if all values are equal.
375 * @param lvalues the l values
376 * @return true, if checks if is all equal
378 private static boolean isAllEqual(final List<Double> lvalues) {
379 final double first = lvalues.get(0);
380 for (final Double d : lvalues) {
381 if (Double.compare(d, first) != 0) {
389 * return true if all values are equal.
391 * @param lvalues the l values
392 * @return true, if checks if is all equal
394 private static boolean isAllEqual(final Double[] lvalues) {
395 final double first = lvalues[0];
396 for (final Double d : lvalues) {
397 if (Double.compare(d, first) != 0) {