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