+ * 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.autoquest.usageprofiles.IStochasticProcess#getProbability(java.util.List, + * de.ugoe.cs.autoquest.eventcore.Event) + */ + @Override + public double getProbability(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.autoquest.usageprofiles.IDotCompatible#getDotRepresentation() + */ + @Override + public String getDotRepresentation() { + StringBuilder stringBuilder = new StringBuilder(); + stringBuilder.append("digraph model {" + StringTools.ENDLINE); + + List+ * Returns a {@link Graph} representation 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; + + /** + *+ * Constructor. Creates a new MarkovEdge. + *
+ * + * @param weight + * weight of the edge, i.e., its transition probability + */ + MarkovEdge(double weight) { + this.weight = weight; + } + + /** + *+ * The weight of the edge as {@link String}. + *
+ */ + public String toString() { + return "" + weight; + } + } + +} Index: trunk/autoquest-core-usageprofiles/src/main/java/de/ugoe/cs/autoquest/usageprofiles/HighOrderMarkovModel.java =================================================================== --- trunk/autoquest-core-usageprofiles/src/main/java/de/ugoe/cs/autoquest/usageprofiles/HighOrderMarkovModel.java (revision 922) +++ trunk/autoquest-core-usageprofiles/src/main/java/de/ugoe/cs/autoquest/usageprofiles/HighOrderMarkovModel.java (revision 922) @@ -0,0 +1,84 @@ +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 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.autoquest.usageprofiles.IStochasticProcess#getProbability(java.util.List, + * de.ugoe.cs.autoquest.eventcore.Event) + */ + @Override + public double getProbability(List+ * 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/autoquest-core-usageprofiles/src/main/java/de/ugoe/cs/autoquest/usageprofiles/IMemory.java =================================================================== --- trunk/autoquest-core-usageprofiles/src/main/java/de/ugoe/cs/autoquest/usageprofiles/IMemory.java (revision 922) +++ trunk/autoquest-core-usageprofiles/src/main/java/de/ugoe/cs/autoquest/usageprofiles/IMemory.java (revision 922) @@ -0,0 +1,40 @@ +package de.ugoe.cs.autoquest.usageprofiles; + +import java.util.List; + +/** + *+ * This interface defines basic functions for classes that implement a memory about the recent + * events of a sequences. + *
+ * + * @author Steffen Herbold + * @version 1.0 + * + * @param
+ * Returns the last num memorized elements. If the history is shorter than
+ * num, the length of the returned {@link java.util.List} may be less than
+ * num.
+ *
+ * This interface defines the functionalities provided by stochastic processes. + *
+ * + * @author Steffen Herbold + * @version 1.0 + */ +public interface IStochasticProcess extends Serializable { + + /** + *+ * Returns the probability, that the next event is {@code symbol} given the last events are + * {@code context}. The last element of {@code context} is the most recent in the history, the + * first element is the oldest. + *
+ * + * @param context + * recently observed symbols + * @param symbol + * event for which the probability is calculated + * @return probabilty the {@code symbol} is the next event, given the last events + * {@code context} + * @throws IllegalArgumentException + * thrown if context or symbol is null + */ + double getProbability(List+ * Returns the probabilitiy that a given sequence is generated by the stochastic process. + *
+ * + * @param sequence + * sequences of which the probability is calculated + * @return probability of the sequences; 1.0 if sequence is empty or null + * @throws IllegalArgumentException + * thrown if sequence is null + */ + double getProbability(List+ * Generates a random sequence of events. The sequence starts with {@link Event#STARTEVENT} and + * finishes with {@link Event#ENDEVENT}. + *
+ * + * @return randomly generated sequence + */ + public List+ * Generates a random sequence of events. The sequence starts with {@link Event#STARTEVENT} and + * finishes with + *
+ * Generates all sequences of a given length are possible, i.e., have a positive probability.
+ * All states are used as possible starting states.
+ *
+ * Generates all sequences of given length that can are possible, i.e., have positive
+ * probability.
+ * If {@code fromStart==true}, all generated sequences start in {@link Event#STARTEVENT}.
+ * Otherwise this method is the same as {@link #generateSequences(int)}.
+ *
+ * Generates all sequences starting with {@link Event#STARTEVENT} and finishing with + * {@link Event#ENDEVENT} of a given length. It is possible that no such sequence exists with + * the defined length and the returned set is empty. If {@code length} is less than 2 the + * returned set is always empty. + *
+ * + * @param length + * @return generated sequences + * @throws IllegalArgumentException + * thrown if length is less than or equal to 0 + */ + public Collection+ * Returns the number of states known by the stochastic process, i.e., the size of its alphabet. + *
+ * + * @return number of states + */ + public int getNumSymbols(); + + /** + *+ * Returns a string representation of all known states. + *
+ * + * @return string representation for all known states + */ + public String[] getSymbolStrings(); + + /** + *+ * Returns the number of states the process would have if it would be flattened through + * state-splitting to a first-order Markov model. + *
+ *+ * If it is not possible to flatten the model, -1 is returned. + *
+ * + * @return number of states an equivalent FOM would have; -1 if not available + */ + public int getNumFOMStates(); + + /** + *+ * Returns the number of transitions the process would have if it would be flattened through + * state-splitting to a first-order Markov model. + *
+ * + * @return number of transitions an equivalent FOM would have; -1 if not available + */ + public int getNumTransitions(); + + /** + *+ * Returns all states known by the stochastic process, i.e., its {@link Event}s. + *
+ * + * @return events known by the process + */ + public Collection+ * Implements a round-trip buffered memory of a specified length that can be used to remember the + * recent history. Every event that happend longer ago than the length of the memory is forgotten, + * hence the memory is incomplete. + *
+ * + * @author Steffen Herbold + * @version 1.0 + * + * @param+ * Maximum length of the memory. + *
+ */ + private int length; + + /** + *+ * Internal storage of the history. + *
+ */ + private List+ * Constructor. Creates a new IncompleteMemory. + *
+ * + * @param length + * number of recent events that are remembered + * @throws IllegalArgumentException + * This exception is thrown if the length is smaller than 1 + */ + public IncompleteMemory(int length) { + if (length < 1) { + throw new IllegalArgumentException("Length of IncompleteMemory must be at least 1."); + } + this.length = length; + history = new LinkedList+ * Returns the current length of the memory. This can be less than {@link #length}, if the + * overall history is less than {@link #length}. + *
+ * + * @return length of the current memory + */ + public int getLength() { + return history.size(); + } +} Index: trunk/autoquest-core-usageprofiles/src/main/java/de/ugoe/cs/autoquest/usageprofiles/ModelFlattener.java =================================================================== --- trunk/autoquest-core-usageprofiles/src/main/java/de/ugoe/cs/autoquest/usageprofiles/ModelFlattener.java (revision 922) +++ trunk/autoquest-core-usageprofiles/src/main/java/de/ugoe/cs/autoquest/usageprofiles/ModelFlattener.java (revision 922) @@ -0,0 +1,131 @@ +package de.ugoe.cs.autoquest.usageprofiles; + +import java.util.LinkedList; +import java.util.List; +import java.util.Random; + +import de.ugoe.cs.autoquest.eventcore.Event; +import de.ugoe.cs.autoquest.eventcore.StringEventType; + +/** + *+ * This class provides functions to create flattened first-order Markov models from + * {@link HighOrderMarkovModel}s and {@link PredictionByPartialMatch} models through state + * splitting. + *
+ *+ * If possible, the normal high-order markov model should be used, as the Events may be broken by + * the flattener, as, e.g., the information {@link ReplayableEvent}s contain is not preserved. + *
+ * + * @author Steffen Herbold + * @version 1.0 + */ +public class ModelFlattener { + + private static final String EVENT_SEPARATOR = "-=-"; + + Trie+ * Takes a {@link HighOrderMarkovModel} and returns a {@link FirstOrderMarkovModel} that + * conserves the high-order memory through state splitting. + *
+ * + * @param model + * model that is flattened + * @return flattened first-order Markov model + */ + public FirstOrderMarkovModel flattenHighOrderMarkovModel(HighOrderMarkovModel model) { + int markovOrder = model.trieOrder - 1; + FirstOrderMarkovModel firstOrderModel = new FirstOrderMarkovModel(new Random()); + firstOrderModel.trieOrder = 2; + if (markovOrder == 1) { + firstOrderModel.trie = new Trie+ * This method is not available yet and always return null! + *
+ *+ * Takes a {@link PredictionByPartialMatch} model and returns a {@link FirstOrderMarkovModel} + * that conserves the high-order memory through state splitting. + *
+ * + * @param model + * model that is flattened + * @return flattened first-order Markov model + */ + public FirstOrderMarkovModel flattenPredictionByPartialMatch(PredictionByPartialMatch model) { + // TODO implement method + return null; + } + + /** + *+ * Converts all nodes of the given depth into first-order node through state-splitting. For each + * node at the given depth a new node is created and appropriate transitions will be added. + *
+ *+ * This method traverses through the tree recursively. If the recursion reaches the desired + * depth in the tree, node are added. + *
+ * + * @param currentNode + * node whose sub-trie is currently traversed + * @param parentIDs + * ID strings of the ancestors of the currentNode + * @param depth + * depth to go - NOT the current depth. + */ + private void generateFirstOrderTrie(TrieNode
+ * 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.
+ *
+ * This class implements a
+ * Id for object serialization. + *
+ */ + private static final long serialVersionUID = 1L; + + /** + *+ * Collection of all symbols occuring in the trie. + *
+ */ + private Collection+ * Reference to the root of the trie. + *
+ */ + private final TrieNode+ * Contructor. Creates a new Trie. + *
+ */ + public Trie() { + rootNode = new TrieNode+ * Copy-Constructor. Creates a new Trie as the copy of other. The other trie must noch be null. + *
+ * + * @param other + * Trie that is copied + */ + public Trie(Trie+ * Returns a collection of all symbols occuring in the trie. + *
+ * + * @return symbols occuring in the trie + */ + public Collection+ * Trains the current trie using the given sequence and adds all subsequence of length + * {@code maxOrder}. + *
+ * + * @param sequence + * sequence whose subsequences are added to the trie + * @param maxOrder + * maximum length of the subsequences added to the trie + */ + public void train(List+ * Adds a given subsequence to the trie and increases the counters accordingly. + *
+ * + * @param subsequence + * subsequence whose counters are increased + * @see TrieNode#add(List) + */ + protected void add(List+ * Returns the child of the root node associated with the given symbol or creates it if it does + * not exist yet. + *
+ * + * @param symbol + * symbol whose node is required + * @return node associated with the symbol + * @see TrieNode#getChildCreate(Object) + */ + protected TrieNode+ * Returns the child of the root node associated with the given symbol or null if it does not + * exist. + *
+ * + * @param symbol + * symbol whose node is required + * @return node associated with the symbol; null if no such node exists + * @see TrieNode#getChild(Object) + */ + protected TrieNode+ * Returns the number of occurences of the given sequence. + *
+ * + * @param sequence + * sequence whose number of occurences is required + * @return number of occurences of the sequence + */ + public int getCount(List
+ * Returns the number of occurences of the given prefix and a symbol that follows it.
+ * Convenience function to simplify usage of {@link #getCount(List)}.
+ *
+ * Searches the trie for a given sequence and returns the node associated with the sequence or + * null if no such node is found. + *
+ * + * @param sequence + * sequence that is searched for + * @return node associated with the sequence + * @see TrieNode#find(List) + */ + public TrieNode+ * Returns a collection of all symbols that follow a given sequence in the trie. In case the + * sequence is not found or no symbols follow the sequence the result will be empty. + *
+ * + * @param sequence + * sequence whose followers are returned + * @return symbols following the given sequence + * @see TrieNode#getFollowingSymbols() + */ + public Collection+ * Returns the longest suffix of the given context that is contained in the tree and whose + * children are leaves. + *
+ * + * @param context + * context whose suffix is searched for + * @return longest suffix of the context + */ + public List+ * Helper class for graph visualization of a trie. + *
+ * + * @author Steffen Herbold + * @version 1.0 + */ + static public class Edge {} + + /** + *+ * Helper class for graph visualization of a trie. + *
+ * + * @author Steffen Herbold + * @version 1.0 + */ + static public class TrieVertex { + + /** + *+ * Id of the vertex. + *
+ */ + private String id; + + /** + *+ * Contructor. Creates a new TrieVertex. + *
+ * + * @param id + * id of the vertex + */ + protected TrieVertex(String id) { + this.id = id; + } + + /** + *+ * Returns the id of the vertex. + *
+ * + * @see java.lang.Object#toString() + */ + @Override + public String toString() { + return id; + } + } + + /** + *+ * Returns a {@link Graph} representation of the trie. + *
+ * + * @return {@link Graph} representation of the trie + */ + protected Tree+ * Returns the string representation of the root node. + *
+ * + * @see TrieNode#toString() + * @see java.lang.Object#toString() + */ + @Override + public String toString() { + return rootNode.toString(); + } + + /** + *+ * Returns the number of symbols contained in the trie. + *
+ * + * @return number of symbols contained in the trie + */ + public int getNumSymbols() { + return knownSymbols.size(); + } + + /** + *+ * Returns the number of trie nodes that are ancestors of a leaf. This is the equivalent to the + * number of states a first-order markov model would have. + *
+ *
+ * @return number of trie nodes that are ancestors of leafs.
+ */
+ public int getNumLeafAncestors() {
+ List
+ * Returns the number of trie nodes that are leafs.
+ *
+ * Updates the list of known symbols by replacing it with all symbols that are found in the
+ * child nodes of the root node. This should be the same as all symbols that are contained in
+ * the trie.
+ *
+ * Two Tries are defined as equal, if their {@link #rootNode} are equal.
+ *
+ * Implements a skeleton for stochastic processes that can calculate probabilities based on a trie.
+ * The skeleton provides all functionalities of {@link IStochasticProcess} except
+ * {@link IStochasticProcess#getProbability(List, Event)}.
+ *
+ * Id for object serialization.
+ *
+ * The order of the trie, i.e., the maximum length of subsequences stored in the trie.
+ *
+ * Trie on which the probability calculations are based.
+ *
+ * Random number generator used by probabilistic sequence generation methods.
+ *
+ * Constructor. Creates a new TrieBasedModel that can be used for stochastic processes with a
+ * Markov order less than or equal to {@code markovOrder}.
+ *
+ * Trains the model by generating a trie from which probabilities are calculated. The trie is
+ * newly generated based solely on the passed sequences. If an existing model should only be
+ * updated, use {@link #update(Collection)} instead.
+ *
+ * Trains the model by updating the trie from which the probabilities are calculated. This
+ * function updates an existing trie. In case no trie exists yet, a new trie is generated and
+ * the function behaves like {@link #train(Collection)}.
+ *
+ * Returns a Dot representation of the internal trie.
+ *
+ * Returns a {@link Tree} of the internal trie that can be used for visualization.
+ *
+ * The string representation of the model is {@link Trie#toString()} of {@link #trie}.
+ *
+ * This class implements a node of a trie. Each node is associated with a symbol and has a counter.
+ * The counter marks the number of occurences of the sequence defined by the path from the root of
+ * the trie to this node.
+ *
+ * Id for object serialization.
+ *
+ * Counter for the number of occurences of the sequence.
+ *
+ * Symbol associated with the node.
+ *
+ * Child nodes of this node. If the node is a leaf this collection is empty.
+ *
+ * Constructor. Creates a new TrieNode without a symbol associated.
+ * Constructor. Creates a new TrieNode. The symbol must not be null.
+ *
+ * Copy-Constructor. Creates a new TrieNode as copy of other. Other must not be null.
+ *
+ * Adds a given subsequence to the trie and increases the counters accordingly.
+ *
+ * Returns the symbol associated with the node.
+ *
+ * Returns the number of occurences of the sequence represented by the node.
+ *
+ * Returns the child of the node associated with the given symbol or creates it if it does not
+ * exist yet.
+ *
+ * Returns the child of the node associated with the given symbol or null if it does not exist.
+ *
+ * Returns all children of this node.
+ *
+ * Searches the sub-trie of this trie node for a given sequence and returns the node associated
+ * with the sequence or null if no such node is found.
+ *
+ * Returns a collection of all symbols that follow a this node, i.e., the symbols associated
+ * with the children of this node.
+ *
+ * The string representation of a node is {@code symbol.toString()#count}
+ *
+ * Generates a {@link Tree} represenation of the trie.
+ *
+ * Appends the current node to the dot representation of the trie.
+ *
+ * Checks if the node is a leaf.
+ *
+ * Checks if the node is the root.
+ *
+ * Recursive methods that collects all nodes that are ancestors of leafs and stores them in the
+ * set.
+ *
+ * Returns the number of descendants of this node that are leafs. This does not only include
+ * direct children of this node, but all leafs in the sub-trie with this node as root.
+ *
+ * Sets the {@link #count} of this node.
+ *
+ * This function should only be used sparingly and very carefully! The count is usually
+ * maintained automatically by the training procedures.
+ *
+ * Two TrieNodes are defined as equal, if their {@link #count}, {@link #symbol}, and
+ * {@link #children} are equal.
+ *
+ * This constructor should only be used to create the root node of the trie!
+ *