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