// Copyright 2012 Georg-August-Universität Göttingen, Germany // // Licensed under the Apache License, Version 2.0 (the "License"); // you may not use this file except in compliance with the License. // You may obtain a copy of the License at // // http://www.apache.org/licenses/LICENSE-2.0 // // Unless required by applicable law or agreed to in writing, software // distributed under the License is distributed on an "AS IS" BASIS, // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. // See the License for the specific language governing permissions and // limitations under the License. package de.ugoe.cs.autoquest.usageprofiles; import java.util.Collection; import java.util.LinkedList; import java.util.List; import java.util.Random; import de.ugoe.cs.autoquest.eventcore.Event; /** *
* Implements Prediction by Partial Match (PPM) based on the following formula (LaTeX-style
* notation):
* P_{PPM}(X_n|X_{n-1},...,X_{n-k}) = \sum_{i=k}^min escape^{k-i} P_{MM^i}(X_n
* |X_{n-1},...,X_{n-i})(1-escape)+escape^(k-min)P(X_n|X_{n-i},... ,X_{n-min})
* P_{MM^i} denotes the probability in an i-th order Markov model.
*
* Id for object serialization. *
*/ private static final long serialVersionUID = 1L; /** ** Minimum order of the Markov model. *
*/ protected int minOrder; /** ** Probability to use a lower-order Markov model *
*/ protected double probEscape; /** ** Constructor. Creates a new PredictionByPartialMatch model with a given Markov order and a * default escape probability of 0.1. *
* * @param markovOrder * Markov order of the model * @param r * random number generator used by probabilistic methods of the class */ public PredictionByPartialMatch(int markovOrder, Random r) { this(markovOrder, r, 0.1); } /** ** Creates a new PredictionByPartialMatch model with a given Markov order and escape * probability. *
* * @param markovOrder * Markov order of the model * @param r * random number generator used by probabilistic methods of the class * @param probEscape * escape probability used by the model */ public PredictionByPartialMatch(int markovOrder, Random r, double probEscape) { this(markovOrder, 0, r, probEscape); } /** ** Creates a new PredictionByPartialMatch model with a given Markov order and escape * probability. *
* * @param markovOrder * Markov order of the model * @param minOrder * minimum order of the model; if this order is reached, there is no escape * @param r * random number generator used by probabilistic methods of the class * @param probEscape * escape probability used by the model * @throws IllegalArgumentException * thrown if minOrder is less than 0 or greater than markovOrder or probEscape is * not in the interval (0,1) */ public PredictionByPartialMatch(int markovOrder, int minOrder, Random r, double probEscape) { super(markovOrder, r); if (minOrder < 0) { throw new IllegalArgumentException("minOrder must be greather than or equal to 0"); } if (minOrder > markovOrder) { throw new IllegalArgumentException( "minOrder must be less than or equal to markovOrder"); } if (probEscape <= 0.0 || probEscape >= 1.0) { throw new IllegalArgumentException("probEscape must be in the interval (0,1)"); } this.probEscape = probEscape; this.minOrder = minOrder; } /** ** Sets the escape probability of the model. *
* * @param probEscape * new escape probability */ public void setProbEscape(double probEscape) { this.probEscape = probEscape; } /** ** Returns the escape probability of the model. *
* * @return escape probability of the model */ public double getProbEscape() { return probEscape; } /** *
* Calculates the probability of the next event based on the formula:
* P_{PPM}(X_n|X_{n-1},...,X_{n-k}) = \sum_{i=k}^min escape^{k-i} P_{MM^i}(X_n
* |X_{n-1},...,X_{n-i})(1-escape)+escape^(k-min)P(X_n|X_{n-i},... ,X_{n-min})
* P_{MM^i} denotes the probability in an i-th order Markov model.
*