+ * Implements a Deterministic Finite Automata (DFA) capable of random session + * generation. It is a special case of a first-order Markov model, where the + * transition probability is equally high for all following states. + *
+ * + * @author Steffen Herbold + * @version 1.0 + */ public class DeterministicFiniteAutomaton extends FirstOrderMarkovModel { /** + ** Id for object serialization. + *
*/ private static final long serialVersionUID = 1L; + /** + *+ * Constructor. Creates a new DeterministicFiniteAutomaton. + *
+ * + * @param r + * random number generator used by probabilistic methods of the + * class + */ public DeterministicFiniteAutomaton(Random r) { super(r); } + /** + *+ * Calculates the proability of the next state. Each of the following states + * in the automaton is equally probable. + *
+ * + * @see de.ugoe.cs.eventbench.models.IStochasticProcess#getProbability(java.util.List, + * de.ugoe.cs.eventbench.data.Event) + */ @Override - public double getProbability(List> context, Event symbol) { + public double getProbability(List> context, + Event symbol) { double result = 0.0d; - + List+ * Implements first-order Markov models. The implementation is based on + * {@link HighOrderMarkovModel} and restricts the Markov order to 1. In + * comparison to {@link HighOrderMarkovModel}, more calculations are possible + * with first-order models, e.g., the calculation of the entropy ( + * {@link #calcEntropy()}). + *
+ * + * @author Steffen Herbold + * @version 1.0 + */ +public class FirstOrderMarkovModel extends HighOrderMarkovModel implements + IDotCompatible { + + /** + ** Id for object serialization. + *
*/ private static final long serialVersionUID = 1L; - + + /** + *+ * Maximum number of iterations when calculating the stationary distribution + * as the limit of multiplying the transmission matrix with itself. + *
+ */ final static int MAX_STATDIST_ITERATIONS = 1000; - + + /** + *+ * Constructor. Creates a new FirstOrderMarkovModel. + *
+ * + * @param r + * random number generator used by probabilistic methods of the + * class + */ public FirstOrderMarkovModel(Random r) { super(1, r); } - + + /** + *+ * Generates the transmission matrix of the Markov model. + *
+ * + * @return transmission matrix + */ private Matrix getTransmissionMatrix() { - List+ * Calculates the entropy of the model. To make it possible that the model + * is stationary, a transition from {@link Event#ENDEVENT} to + * {@link Event#STARTEVENT} is added. + *
+ * + * @return entropy of the model or NaN if it could not be calculated + */ + public double calcEntropy() { + Matrix transmissionMatrix = getTransmissionMatrix(); + List+ * The dot represenation of {@link FirstOrderMarkovModel}s is its graph + * representation with the states as nodes and directed edges weighted with + * transition probabilities. + *
+ * + * @see de.ugoe.cs.eventbench.models.IDotCompatible#getDotRepresentation() + */ + @Override public String getDotRepresentation() { StringBuilder stringBuilder = new StringBuilder(); stringBuilder.append("digraph model {" + StringTools.ENDLINE); - List+ * Returns a {@link Graph} represenation of the model with the states as + * nodes and directed edges weighted with transition probabilities. + *
+ * + * @return {@link Graph} of the model + */ public Graph+ * Weight of the edge, i.e., its transition probability. + *
+ */ double weight; - MarkovEdge(double weight) { this.weight = weight; } - public String toString() { return ""+weight; } - } - - public double calcEntropy() { - Matrix transmissionMatrix = getTransmissionMatrix(); - List+ * The weight of the edge as {@link String}. + *
+ */ + public String toString() { + return "" + weight; + } } Index: /trunk/EventBenchCore/src/de/ugoe/cs/eventbench/models/HighOrderMarkovModel.java =================================================================== --- /trunk/EventBenchCore/src/de/ugoe/cs/eventbench/models/HighOrderMarkovModel.java (revision 100) +++ /trunk/EventBenchCore/src/de/ugoe/cs/eventbench/models/HighOrderMarkovModel.java (revision 101) @@ -7,15 +7,34 @@ import de.ugoe.cs.eventbench.data.Event; +/** + *Implements high-order Markov models.
+ * + * @author Steffen Herbold + * @version 1.0 + */ public class HighOrderMarkovModel extends TrieBasedModel { /** + ** Id for object serialization. + *
*/ private static final long serialVersionUID = 1L; + /** + *Constructor. Creates a new HighOrderMarkovModel with a defined Markov order.
+ * @param maxOrder Markov order of the model + * @param r random number generator used by probabilistic methods of the class + */ public HighOrderMarkovModel(int maxOrder, Random r) { super(maxOrder, r); } + /** + *+ * Calculates the probability of the next Event being symbol based on the order of the Markov model. The order is defined in the constructor {@link #HighOrderMarkovModel(int, Random)}. + *
+ * @see de.ugoe.cs.eventbench.models.IStochasticProcess#getProbability(java.util.List, de.ugoe.cs.eventbench.data.Event) + */ @Override public double getProbability(List> context, Event symbol) { Index: /trunk/EventBenchCore/src/de/ugoe/cs/eventbench/models/IDotCompatible.java =================================================================== --- /trunk/EventBenchCore/src/de/ugoe/cs/eventbench/models/IDotCompatible.java (revision 100) +++ /trunk/EventBenchCore/src/de/ugoe/cs/eventbench/models/IDotCompatible.java (revision 101) @@ -1,5 +1,22 @@ package de.ugoe.cs.eventbench.models; +/** + *+ * Models implementing this interface provide a graph representation of + * themselves as a {@link String} with Dot syntax. + *
+ * + * @author Steffen Herbold + * @version 1.0 + */ public interface IDotCompatible { + + /** + *+ * Returns a Dot representation of the model. + *
+ * + * @return string with Dot syntax that describes the model. + */ public abstract String getDotRepresentation(); } Index: /trunk/EventBenchCore/src/de/ugoe/cs/eventbench/models/PredictionByPartialMatch.java =================================================================== --- /trunk/EventBenchCore/src/de/ugoe/cs/eventbench/models/PredictionByPartialMatch.java (revision 100) +++ /trunk/EventBenchCore/src/de/ugoe/cs/eventbench/models/PredictionByPartialMatch.java (revision 101) @@ -7,70 +7,139 @@ import de.ugoe.cs.eventbench.data.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}^1 escape^{i-1}
+ * P_{MM^i}(X_n|X_{n-1},...,X_{n-i})(1-escape)
+ * P_{MM^i} denotes the probability in an i-th order Markov model.
+ *
* Id for object serialization. + *
*/ private static final long serialVersionUID = 1L; - + + /** + *+ * Probability to use a lower-order Markov model + *
+ */ 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) { super(markovOrder, r); this.probEscape = probEscape; } - + + /** + *+ * 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}^1 escape^{i-1}
+ * P_{MM^i}(X_n|X_{n-1},...,X_{n-i})(1-escape)
+ * P_{MM^i} denotes the probability in an i-th order Markov model.
+ *