gerrit.onap Code Review - policy/apex-pdp.git/blob

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