examples/examples-adaptive/src/main/java/org/onap/policy/apex/examples/adaptive/model/java/AnomalyDetectionPolicyDecideTaskSelectionLogic.java

   1 /*-
   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
   9  *
  10  *      http://www.apache.org/licenses/LICENSE-2.0
  11  *
  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.
  17  *
  18  * SPDX-License-Identifier: Apache-2.0
  19  * ============LICENSE_END=========================================================
  20  */
  21
  22 package org.onap.policy.apex.examples.adaptive.model.java;
  23
  24 import java.util.Arrays;
  25 import java.util.LinkedHashMap;
  26 import java.util.LinkedList;
  27 import java.util.List;
  28 import java.util.Map;
  29 import org.apache.commons.math3.distribution.TDistribution;
  30 import org.apache.commons.math3.util.FastMath;
  31 import org.onap.policy.apex.core.engine.executor.context.TaskSelectionExecutionContext;
  32 import org.onap.policy.apex.examples.adaptive.concepts.AnomalyDetection;
  33 import org.onap.policy.apex.model.basicmodel.concepts.ApexException;
  34
  35 /**
  36  * The Class AnomalyDetectionPolicyDecideTaskSelectionLogic.
  37  */
  38 public class AnomalyDetectionPolicyDecideTaskSelectionLogic {
  39
  40     // Recurring string constants
  41     private static final String ANOMALY_DETECTION_ALBUM = "AnomalyDetectionAlbum";
  42     private static final String ANOMALY_DETECTION = "AnomalyDetection";
  43
  44     // configuration
  45     private static final double ANOMALY_SENSITIVITY = 0.05;
  46     private static final int FREQUENCY = 360;
  47
  48     /*
  49      * Some utility methods
  50      */
  51     // exponential = 2(n+1)
  52     private static final double EMA_EXPONENT = 2.0 / (7.0 + 1.0);
  53     private static final double EMA_EXPONENT_1 = (1.0 - EMA_EXPONENT);
  54
  55     /**
  56      * A map to hold the Anomaly degree/levels/probabilities required for each task.<br>
  57      * If there is no task defined for a calculated anomaly-degree, then the default task is
  58      * used.<br>
  59      * The map use (LinkedHashMap) is an insertion-ordered map, so the first interval matching a
  60      * query is used.
  61      */
  62     // CHECKSTYLE:OFF: checkstyle:magicNumber
  63     private static final Map<double[], String> TASK_INTERVALS = new LinkedHashMap<>();
  64
  65     static {
  66         TASK_INTERVALS.put(new double[] {0.0, 0.1}, null); // null will mean default task
  67         TASK_INTERVALS.put(new double[] {0.25, 0.5}, "AnomalyDetectionDecideTask1");
  68         TASK_INTERVALS.put(new double[] {0.5, 1.01}, "AnomalyDetectionDecideTask2");
  69     }
  70     // CHECKSTYLE:ON: checkstyle:magicNumber
  71
  72     /**
  73      * Gets the task.
  74      *
  75      * @param executor the executor
  76      * @return the task
  77      */
  78     public boolean getTask(final TaskSelectionExecutionContext executor) {
  79         String id = executor.subject.getId();
  80         executor.logger.debug(id);
  81         String inFields = executor.inFields.toString();
  82         executor.logger.debug(inFields);
  83         final double now = (Double) (executor.inFields.get("MonitoredValue"));
  84         final Integer iteration = (Integer) (executor.inFields.get("Iteration"));
  85         // get the double[forecastedValue, AnomalyScore, AnomalyProbability]
  86         final double[] vals = forecastingAndAnomaly(executor, now);
  87         final double anomalyness = vals[2];
  88         String task = null;
  89         for (final Map.Entry<double[], String> i : TASK_INTERVALS.entrySet()) {
  90             if (checkInterval(anomalyness, i.getKey())) {
  91                 task = i.getValue();
  92                 break;
  93             }
  94         }
  95         if (task == null) {
  96             executor.subject.getDefaultTaskKey().copyTo(executor.selectedTask);
  97         } else {
  98             executor.subject.getTaskKey(task).copyTo(executor.selectedTask);
  99         }
 100         executor.logger.debug(
 101             "TestAnomalyDetectionTSLPolicy0000DecideStateTaskSelectionLogic.getTask():\t************\t\t\t\t"
 102                 + "Iteration:\t{}\tValue:\t{}\tForecast:\t{}\tAnomalyScore:\t{}\tAnomalyProbability:\t{}\t"
 103                 + "Invoking Task:\t{}", iteration, now, vals[0], vals[1], vals[2], executor.selectedTask);
 104         return true;
 105     }
 106
 107     /**
 108      * Anomaly detection and forecast.
 109      *
 110      * @param value The current value
 111      * @return Null if the function can not be executed correctly, otherwise double[forecastedValue,
 112      *         AnomalyScore, AnomalyProbability]
 113      */
 114     private double[] forecastingAndAnomaly(final TaskSelectionExecutionContext executor, final double value) {
 115         try {
 116             executor.getContextAlbum(ANOMALY_DETECTION_ALBUM).lockForWriting(ANOMALY_DETECTION);
 117         } catch (final ApexException e) {
 118             executor.logger.error("Failed to acquire write lock on \"AnomalyDetection\" context", e);
 119             return new double[0];
 120         }
 121
 122         // Get the context object
 123         AnomalyDetection anomalyDetection =
 124                 (AnomalyDetection) executor.getContextAlbum(ANOMALY_DETECTION_ALBUM).get(ANOMALY_DETECTION);
 125         if (anomalyDetection == null) {
 126             anomalyDetection = new AnomalyDetection();
 127             executor.getContextAlbum(ANOMALY_DETECTION_ALBUM).put(ANOMALY_DETECTION, anomalyDetection);
 128         }
 129
 130         // Check the lists are initialized
 131         if (!anomalyDetection.isInitialized()) {
 132             anomalyDetection.init(FREQUENCY);
 133         }
 134
 135         boolean unsetfirstround = false;
 136
 137         int frequency = anomalyDetection.getFrequency();
 138         frequency = frequency + 1;
 139
 140         // reset frequency counter
 141         if (frequency >= FREQUENCY) {
 142             unsetfirstround = true;
 143             frequency = 0;
 144         }
 145         anomalyDetection.setFrequency(frequency);
 146
 147         if (unsetfirstround && anomalyDetection.getFirstRound()) {
 148             anomalyDetection.setFirstRound(false);
 149         }
 150
 151         // --------- calculate the forecasted value - simple version
 152         final Double lastForecast = anomalyDetection.getFrequencyForecasted().get(frequency);
 153
 154         // get forecast for current value
 155         final double forecastedValue = lastForecast == null ? value : expMovingAverage(value, lastForecast);
 156
 157         // --------- calculate the anomalyScore
 158         final double anomalyScore = lastForecast == null ? 0.0 : FastMath.abs(lastForecast - value);
 159
 160         anomalyDetection.getFrequencyForecasted().set(frequency, forecastedValue);
 161
 162         // anomaly score is ignored in the first frequency period
 163         if (!anomalyDetection.getFirstRound()) {
 164             ((LinkedList<Double>) anomalyDetection.getAnomalyScores()).addLast(anomalyScore);
 165         }
 166
 167         // CHECKSTYLE:OFF: checkstyle:magicNumber
 168         // max FREQUENCY*4 anomaly scores history
 169         listSizeControl(anomalyDetection.getAnomalyScores(), FREQUENCY * 4);
 170
 171         // ---------- calculate the anomaly probability
 172         double anomalyProbability = 0.0;
 173         if (anomalyDetection.getAnomalyScores().size() > 30) {
 174             // 0.5
 175             anomalyProbability = getStatsTest(anomalyDetection.getAnomalyScores(), ANOMALY_SENSITIVITY);
 176         }
 177         // CHECKSTYLE:ON: checkstyle:magicNumber
 178
 179         try {
 180             executor.getContextAlbum(ANOMALY_DETECTION_ALBUM).unlockForWriting(ANOMALY_DETECTION);
 181         } catch (final ApexException e) {
 182             executor.logger.error("Failed to release write lock on \"AnomalyDetection\" context", e);
 183             return new double[0];
 184         }
 185
 186         return new double[] {forecastedValue, anomalyScore, anomalyProbability};
 187     }
 188
 189     /**
 190      * Is the passed value inside the interval, i.e. (value < interval[1] && value>=interval[0]).
 191      *
 192      * @param value The value to check
 193      * @param interval A 2 element double array describing an interval
 194      * @return true if the value is between interval[0] (inclusive) and interval[1] (exclusive),
 195      *         i.e. (value < interval[1] && value>=interval[0]). Otherwise false;
 196      */
 197     private static boolean checkInterval(final double value, final double[] interval) {
 198         if (interval == null || interval.length != 2) {
 199             throw new IllegalArgumentException("something other than an interval passed to checkInterval");
 200         }
 201         final double min = interval[0];
 202         final double max = interval[1];
 203         return (value < max && value >= min);
 204     }
 205
 206     /**
 207      * calculate the anomaly probability using statistical test.
 208      *
 209      * @param values the values
 210      * @param significanceLevel the significance level
 211      * @return the anomaly probability
 212      */
 213     private static double getStatsTest(final List<Double> values, final double significanceLevel) {
 214         if (isAllEqual(values)) {
 215             return 0.0;
 216         }
 217         // the targeted value or the last value
 218         final double currentV = values.get(values.size() - 1);
 219         Double[] lvaluesCopy = values.toArray(new Double[values.size()]);
 220         Arrays.sort(lvaluesCopy); // takes ~40% of method time
 221         // get mean
 222         double mean = getMean(lvaluesCopy);
 223         // get the test value: val
 224         double val = getV(lvaluesCopy, mean, true);
 225         // get the p value for the test value
 226         double pvalue = getPValue(lvaluesCopy, val, mean); // takes approx 25% of method time
 227
 228         // check the critical level
 229         while (pvalue < significanceLevel) { // takes approx 20% of method time
 230             // the score value as the anomaly probability
 231             final double score = (significanceLevel - pvalue) / significanceLevel;
 232             if (Double.compare(val, currentV) == 0) {
 233                 return score;
 234             }
 235             // do the critical check again for the left values
 236             lvaluesCopy = removevalue(lvaluesCopy, val);
 237             if (isAllEqual(lvaluesCopy)) {
 238                 return 0.0;
 239             }
 240
 241             mean = getMean(lvaluesCopy);
 242             val = getV(lvaluesCopy, mean, true);
 243             pvalue = getPValue(lvaluesCopy, val, mean);
 244         }
 245         return 0.0;
 246     }
 247
 248     /**
 249      * Get the test value based on mean from sorted values.
 250      *
 251      * @param lvalues the l values
 252      * @param mean the mean
 253      * @param maxValueOnly : only the max extreme value will be tested
 254      * @return the value to be tested
 255      */
 256     private static double getV(final Double[] lvalues, final double mean, final boolean maxValueOnly) {
 257         double val = lvalues[lvalues.length - 1];
 258         // max value as the extreme value
 259         if (maxValueOnly) {
 260             return val;
 261         }
 262         // check the extreme side
 263         if ((val - mean) < (mean - lvalues[0])) {
 264             val = lvalues[0];
 265         }
 266         return val;
 267     }
 268
 269     /**
 270      * calculate the P value for the t distribution.
 271      *
 272      * @param lvalues the l values
 273      * @param val the value
 274      * @param mean the mean
 275      * @return the p value
 276      */
 277     private static double getPValue(final Double[] lvalues, final double val, final double mean) {
 278         // calculate z value
 279         final double z = FastMath.abs(val - mean) / getStdDev(lvalues, mean);
 280         // calculate T
 281         final double n = lvalues.length;
 282         final double s = (z * z * n * (2.0 - n)) / (z * z * n - (n - 1.0) * (n - 1.0));
 283         final double t = FastMath.sqrt(s);
 284         // default p value = 0
 285         double pvalue = 0.0;
 286         if (!Double.isNaN(t)) {
 287             // t distribution with n-2 degrees of freedom
 288             final TDistribution tDist = new TDistribution(n - 2);
 289             pvalue = n * (1.0 - tDist.cumulativeProbability(t));
 290             // set max pvalue = 1
 291             pvalue = pvalue > 1.0 ? 1.0 : pvalue;
 292         }
 293         return pvalue;
 294     }
 295
 296     /**
 297      * exponential moving average.
 298      *
 299      * @param value the value
 300      * @param lastForecast the last forecast
 301      * @return the double
 302      */
 303     private static double expMovingAverage(final double value, final double lastForecast) {
 304         return (value * EMA_EXPONENT) + (lastForecast * EMA_EXPONENT_1);
 305     }
 306
 307     /**
 308      * Remove the first occurrence of the value val from the array.
 309      *
 310      * @param lvalues the l values
 311      * @param val the value
 312      * @return the double[]
 313      */
 314     private static Double[] removevalue(final Double[] lvalues, final double val) {
 315         for (int i = 0; i < lvalues.length; i++) {
 316             if (Double.compare(lvalues[i], val) == 0) {
 317                 final Double[] ret = new Double[lvalues.length - 1];
 318                 System.arraycopy(lvalues, 0, ret, 0, i);
 319                 System.arraycopy(lvalues, i + 1, ret, i, lvalues.length - i - 1);
 320                 return ret;
 321             }
 322         }
 323         return lvalues;
 324     }
 325
 326     /**
 327      * get mean value of double list.
 328      *
 329      * @param lvalues the l values
 330      * @return the mean
 331      */
 332     private static double getMean(final Double[] lvalues) {
 333         double sum = 0.0;
 334         for (final double d : lvalues) {
 335
 336             sum += d;
 337         }
 338         return sum / lvalues.length;
 339     }
 340
 341     /**
 342      * get standard deviation of double list.
 343      *
 344      * @param lvalues the l values
 345      * @param mean the mean
 346      * @return stddev
 347      */
 348     private static double getStdDev(final Double[] lvalues, final double mean) {
 349         double temp = 0.0;
 350         for (final double d : lvalues) {
 351             temp += (mean - d) * (mean - d);
 352         }
 353         return FastMath.sqrt(temp / lvalues.length);
 354     }
 355
 356     /**
 357      * Chop head off list to make it length max .
 358      *
 359      * @param list the list to chop
 360      * @param max the max size
 361      */
 362     private static void listSizeControl(final List<?> list, final int max) {
 363         final int k = list.size();
 364         if (k > max) {
 365             // Chop the head off the list.
 366             list.subList(0, k - max).clear();
 367         }
 368     }
 369
 370     /**
 371      * return true if all values are equal.
 372      *
 373      * @param lvalues the l values
 374      * @return true, if checks if is all equal
 375      */
 376     private static boolean isAllEqual(final List<Double> lvalues) {
 377         final double first = lvalues.get(0);
 378         for (final Double d : lvalues) {
 379             if (Double.compare(d, first) != 0) {
 380                 return false;
 381             }
 382         }
 383         return true;
 384     }
 385
 386     /**
 387      * return true if all values are equal.
 388      *
 389      * @param lvalues the l values
 390      * @return true, if checks if is all equal
 391      */
 392     private static boolean isAllEqual(final Double[] lvalues) {
 393         final double first = lvalues[0];
 394         for (final Double d : lvalues) {
 395             if (Double.compare(d, first) != 0) {
 396                 return false;
 397             }
 398         }
 399         return true;
 400     }
 401 }