Changeset 101 for trunk/EventBenchCore/src/de/ugoe/cs/eventbench/models/FirstOrderMarkovModel.java

Timestamp:

07/04/11 15:21:50 (13 years ago)

Author:

sherbold

Message:

• code documentation

File:

• trunk/EventBenchCore/src/de/ugoe/cs/eventbench/models/FirstOrderMarkovModel.java (modified) (4 diffs)

trunk/EventBenchCore/src/de/ugoe/cs/eventbench/models/FirstOrderMarkovModel.java

@@ -14 +14 @@
 import Jama.Matrix;
 
-public class FirstOrderMarkovModel extends HighOrderMarkovModel implements IDotCompatible {
-
-        /**
+/**
+ * <p>
+ * 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()}).
+ * </p>
+ * 
+ * @author Steffen Herbold
+ * @version 1.0
+ */
+public class FirstOrderMarkovModel extends HighOrderMarkovModel implements
+                IDotCompatible {
+
+        /**
+         * <p>
          * Id for object serialization.
+         * </p>
          */
         private static final long serialVersionUID = 1L;
-        
+
+        /**
+         * <p>
+         * Maximum number of iterations when calculating the stationary distribution
+         * as the limit of multiplying the transmission matrix with itself.
+         * </p>
+         */
         final static int MAX_STATDIST_ITERATIONS = 1000;
-        
+
+        /**
+         * <p>
+         * Constructor. Creates a new FirstOrderMarkovModel.
+         * </p>
+         * 
+         * @param r
+         *            random number generator used by probabilistic methods of the
+         *            class
+         */
         public FirstOrderMarkovModel(Random r) {
                 super(1, r);
         }
-        
+
+        /**
+         * <p>
+         * Generates the transmission matrix of the Markov model.
+         * </p>
+         * 
+         * @return transmission matrix
+         */
         private Matrix getTransmissionMatrix() {
-                List<Event<?>> knownSymbols = new ArrayList<Event<?>>(trie.getKnownSymbols());
+                List<Event<?>> knownSymbols = new ArrayList<Event<?>>(
+                                trie.getKnownSymbols());
                 int numStates = knownSymbols.size();
                 Matrix transmissionMatrix = new Matrix(numStates, numStates);
-                
-                for( int i=0 ; i<numStates ; i++ ) {
+
+                for (int i = 0; i < numStates; i++) {
                         Event<?> currentSymbol = knownSymbols.get(i);
                         List<Event<?>> context = new ArrayList<Event<?>>();
                         context.add(currentSymbol);
-                        for( int j=0 ; j<numStates ; j++ ) {
+                        for (int j = 0; j < numStates; j++) {
                                 Event<?> follower = knownSymbols.get(j);
                                 double prob = getProbability(context, follower);
@@ -44 +82 @@
                 return transmissionMatrix;
         }
-        
+
+        /**
+         * <p>
+         * 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.
+         * </p>
+         * 
+         * @return entropy of the model or NaN if it could not be calculated
+         */
+        public double calcEntropy() {
+                Matrix transmissionMatrix = getTransmissionMatrix();
+                List<Event<?>> knownSymbols = new ArrayList<Event<?>>(
+                                trie.getKnownSymbols());
+                int numStates = knownSymbols.size();
+
+                int startStateIndex = knownSymbols.indexOf(Event.STARTEVENT);
+                int endStateIndex = knownSymbols.indexOf(Event.ENDEVENT);
+                if (startStateIndex == -1) {
+                        Console.printerrln("Error calculating entropy. Initial state of markov chain not found.");
+                        return Double.NaN;
+                }
+                if (endStateIndex == -1) {
+                        Console.printerrln("Error calculating entropy. End state of markov chain not found.");
+                        return Double.NaN;
+                }
+                transmissionMatrix.set(endStateIndex, startStateIndex, 1);
+
+                // Calculate stationary distribution by raising the power of the
+                // transmission matrix.
+                // The rank of the matrix should fall to 1 and each two should be the
+                // vector of the stationory distribution.
+                int iter = 0;
+                int rank = transmissionMatrix.rank();
+                Matrix stationaryMatrix = (Matrix) transmissionMatrix.clone();
+                while (iter < MAX_STATDIST_ITERATIONS && rank > 1) {
+                        stationaryMatrix = stationaryMatrix.times(stationaryMatrix);
+                        rank = stationaryMatrix.rank();
+                        iter++;
+                }
+
+                if (rank != 1) {
+                        Console.traceln("rank: " + rank);
+                        Console.printerrln("Unable to calculate stationary distribution.");
+                        return Double.NaN;
+                }
+
+                double entropy = 0.0;
+                for (int i = 0; i < numStates; i++) {
+                        for (int j = 0; j < numStates; j++) {
+                                if (transmissionMatrix.get(i, j) != 0) {
+                                        double tmp = stationaryMatrix.get(i, 0);
+                                        tmp *= transmissionMatrix.get(i, j);
+                                        tmp *= Math.log(transmissionMatrix.get(i, j)) / Math.log(2);
+                                        entropy -= tmp;
+                                }
+                        }
+                }
+                return entropy;
+        }
+
+        /**
+         * <p>
+         * The dot represenation of {@link FirstOrderMarkovModel}s is its graph
+         * representation with the states as nodes and directed edges weighted with
+         * transition probabilities.
+         * </p>
+         * 
+         * @see de.ugoe.cs.eventbench.models.IDotCompatible#getDotRepresentation()
+         */
+        @Override
         public String getDotRepresentation() {
                 StringBuilder stringBuilder = new StringBuilder();
                 stringBuilder.append("digraph model {" + StringTools.ENDLINE);
 
-                List<Event<?>> knownSymbols = new ArrayList<Event<?>>(trie.getKnownSymbols());
-                
-                for( Event<?> symbol : knownSymbols) {
-                        final String thisSaneId = symbol.getShortId().replace("\"", "\\\"").replaceAll("[\r\n]","");
-                        stringBuilder.append(" " + symbol.hashCode() + " [label=\""+thisSaneId+"\"];" + StringTools.ENDLINE);
+                List<Event<?>> knownSymbols = new ArrayList<Event<?>>(
+                                trie.getKnownSymbols());
+
+                for (Event<?> symbol : knownSymbols) {
+                        final String thisSaneId = symbol.getShortId().replace("\"", "\\\"")
+                                        .replaceAll("[\r\n]", "");
+                        stringBuilder.append(" " + symbol.hashCode() + " [label=\""
+                                        + thisSaneId + "\"];" + StringTools.ENDLINE);
                         List<Event<?>> context = new ArrayList<Event<?>>();
-                        context.add(symbol); 
+                        context.add(symbol);
                         List<Event<?>> followers = trie.getFollowingSymbols(context);
-                        for( Event<?> follower : followers ) {
-                                stringBuilder.append(" "+symbol.hashCode()+" -> " + follower.hashCode() + " ");
-                                stringBuilder.append("[label=\"" + getProbability(context, follower) + "\"];" + StringTools.ENDLINE);
+                        for (Event<?> follower : followers) {
+                                stringBuilder.append(" " + symbol.hashCode() + " -> "
+                                                + follower.hashCode() + " ");
+                                stringBuilder.append("[label=\""
+                                                + getProbability(context, follower) + "\"];"
+                                                + StringTools.ENDLINE);
                         }
                 }
@@ -65 +179 @@
                 return stringBuilder.toString();
         }
-        
+
+        /**
+         * <p>
+         * Returns a {@link Graph} represenation of the model with the states as
+         * nodes and directed edges weighted with transition probabilities.
+         * </p>
+         * 
+         * @return {@link Graph} of the model
+         */
         public Graph<String, MarkovEdge> getGraph() {
                 Graph<String, MarkovEdge> graph = new SparseMultigraph<String, MarkovEdge>();
-                
-                List<Event<?>> knownSymbols = new ArrayList<Event<?>>(trie.getKnownSymbols());
-                
-                for( Event<?> symbol : knownSymbols) {
+
+                List<Event<?>> knownSymbols = new ArrayList<Event<?>>(
+                                trie.getKnownSymbols());
+
+                for (Event<?> symbol : knownSymbols) {
                         String from = symbol.getShortId();
                         List<Event<?>> context = new ArrayList<Event<?>>();
-                        context.add(symbol); 
-                        
+                        context.add(symbol);
+
                         List<Event<?>> followers = trie.getFollowingSymbols(context);
-                        
-                        for( Event<?> follower : followers ) {
+
+                        for (Event<?> follower : followers) {
                                 String to = follower.getShortId();
-                                MarkovEdge prob = new MarkovEdge(getProbability(context, follower));
+                                MarkovEdge prob = new MarkovEdge(getProbability(context,
+                                                follower));
                                 graph.addEdge(prob, from, to, EdgeType.DIRECTED);
                         }
@@ -86 +210 @@
                 return graph;
         }
-        
+
+        /**
+         * Inner class used for the {@link Graph} representation of the model.
+         * 
+         * @author Steffen Herbold
+         * @version 1.0
+         */
         static public class MarkovEdge {
+                /**
+                 * <p>
+                 * Weight of the edge, i.e., its transition probability.
+                 * </p>
+                 */
                 double weight;
-                MarkovEdge(double weight) { this.weight = weight; }
-                public String toString() { return ""+weight; }
-        }
-        
-        public double calcEntropy() {
-                Matrix transmissionMatrix = getTransmissionMatrix();
-                List<Event<?>> knownSymbols = new ArrayList<Event<?>>(trie.getKnownSymbols());
-                int numStates = knownSymbols.size();
-                
-                int startStateIndex = knownSymbols.indexOf(Event.STARTEVENT);
-                int endStateIndex = knownSymbols.indexOf(Event.ENDEVENT);
-                if( startStateIndex==-1 ) {
-                        Console.printerrln("Error calculating entropy. Initial state of markov chain not found.");
-                        return Double.NaN;
-                }
-                if( endStateIndex==-1 ) {
-                        Console.printerrln("Error calculating entropy. End state of markov chain not found.");
-                        return Double.NaN;
-                }
-                transmissionMatrix.set(endStateIndex, startStateIndex, 1);
-                
-                // Calculate stationary distribution by raising the power of the transmission matrix.
-                // The rank of the matrix should fall to 1 and each two should be the vector of the
-                // stationory distribution. 
-                int iter = 0;
-                int rank = transmissionMatrix.rank();
-                Matrix stationaryMatrix = (Matrix) transmissionMatrix.clone();
-                while( iter<MAX_STATDIST_ITERATIONS && rank>1 ) {
-                        stationaryMatrix = stationaryMatrix.times(stationaryMatrix);
-                        rank = stationaryMatrix.rank();
-                        iter++;
-                }
-                
-                if( rank!=1 ) {
-                        Console.traceln("rank: " + rank);
-                        Console.printerrln("Unable to calculate stationary distribution.");
-                        return Double.NaN;
-                }
-                
-                double entropy = 0.0;
-                for( int i=0 ; i<numStates ; i++ ) {
-                        for( int j=0 ; j<numStates ; j++ ) {
-                                if( transmissionMatrix.get(i,j)!=0 ) {
-                                        double tmp = stationaryMatrix.get(i, 0);
-                                        tmp *= transmissionMatrix.get(i, j);
-                                        tmp *= Math.log(transmissionMatrix.get(i,j))/Math.log(2);
-                                        entropy -= tmp;
-                                }
-                        }
-                }
-                return entropy;
+
+                /**
+                 * <p>
+                 * Constructor. Creates a new MarkovEdge.
+                 * </p>
+                 * 
+                 * @param weight
+                 *            weight of the edge, i.e., its transition probability
+                 */
+                MarkovEdge(double weight) {
+                        this.weight = weight;
+                }
+
+                /**
+                 * <p>
+                 * The weight of the edge as {@link String}.
+                 * </p>
+                 */
+                public String toString() {
+                        return "" + weight;
+                }
         }