[16] | 1 | package de.ugoe.cs.eventbench.models;
|
---|
| 2 |
|
---|
| 3 | import java.util.ArrayList;
|
---|
| 4 | import java.util.List;
|
---|
| 5 | import java.util.Random;
|
---|
| 6 |
|
---|
| 7 | import de.ugoe.cs.eventbench.data.Event;
|
---|
[29] | 8 | import de.ugoe.cs.util.StringTools;
|
---|
[16] | 9 | import de.ugoe.cs.util.console.Console;
|
---|
| 10 | import edu.uci.ics.jung.graph.Graph;
|
---|
| 11 | import edu.uci.ics.jung.graph.SparseMultigraph;
|
---|
| 12 | import edu.uci.ics.jung.graph.util.EdgeType;
|
---|
| 13 |
|
---|
| 14 | import Jama.Matrix;
|
---|
| 15 |
|
---|
[25] | 16 | public class FirstOrderMarkovModel extends HighOrderMarkovModel implements IDotCompatible {
|
---|
[16] | 17 |
|
---|
[86] | 18 | /**
|
---|
| 19 | * Id for object serialization.
|
---|
| 20 | */
|
---|
| 21 | private static final long serialVersionUID = 1L;
|
---|
| 22 |
|
---|
[16] | 23 | final static int MAX_STATDIST_ITERATIONS = 1000;
|
---|
| 24 |
|
---|
| 25 | public FirstOrderMarkovModel(Random r) {
|
---|
| 26 | super(1, r);
|
---|
| 27 | }
|
---|
| 28 |
|
---|
| 29 | private Matrix getTransmissionMatrix() {
|
---|
| 30 | List<Event<?>> knownSymbols = new ArrayList<Event<?>>(trie.getKnownSymbols());
|
---|
| 31 | int numStates = knownSymbols.size();
|
---|
| 32 | Matrix transmissionMatrix = new Matrix(numStates, numStates);
|
---|
| 33 |
|
---|
| 34 | for( int i=0 ; i<numStates ; i++ ) {
|
---|
| 35 | Event<?> currentSymbol = knownSymbols.get(i);
|
---|
| 36 | List<Event<?>> context = new ArrayList<Event<?>>();
|
---|
| 37 | context.add(currentSymbol);
|
---|
| 38 | for( int j=0 ; j<numStates ; j++ ) {
|
---|
| 39 | Event<?> follower = knownSymbols.get(j);
|
---|
| 40 | double prob = getProbability(context, follower);
|
---|
| 41 | transmissionMatrix.set(i, j, prob);
|
---|
| 42 | }
|
---|
| 43 | }
|
---|
| 44 | return transmissionMatrix;
|
---|
| 45 | }
|
---|
| 46 |
|
---|
[25] | 47 | public String getDotRepresentation() {
|
---|
| 48 | StringBuilder stringBuilder = new StringBuilder();
|
---|
[29] | 49 | stringBuilder.append("digraph model {" + StringTools.ENDLINE);
|
---|
[16] | 50 |
|
---|
| 51 | List<Event<?>> knownSymbols = new ArrayList<Event<?>>(trie.getKnownSymbols());
|
---|
| 52 |
|
---|
| 53 | for( Event<?> symbol : knownSymbols) {
|
---|
| 54 | final String thisSaneId = symbol.getShortId().replace("\"", "\\\"").replaceAll("[\r\n]","");
|
---|
[29] | 55 | stringBuilder.append(" " + symbol.hashCode() + " [label=\""+thisSaneId+"\"];" + StringTools.ENDLINE);
|
---|
[16] | 56 | List<Event<?>> context = new ArrayList<Event<?>>();
|
---|
| 57 | context.add(symbol);
|
---|
| 58 | List<Event<?>> followers = trie.getFollowingSymbols(context);
|
---|
| 59 | for( Event<?> follower : followers ) {
|
---|
[29] | 60 | stringBuilder.append(" "+symbol.hashCode()+" -> " + follower.hashCode() + " ");
|
---|
| 61 | stringBuilder.append("[label=\"" + getProbability(context, follower) + "\"];" + StringTools.ENDLINE);
|
---|
[16] | 62 | }
|
---|
| 63 | }
|
---|
[29] | 64 | stringBuilder.append('}' + StringTools.ENDLINE);
|
---|
[25] | 65 | return stringBuilder.toString();
|
---|
[16] | 66 | }
|
---|
| 67 |
|
---|
| 68 | public Graph<String, MarkovEdge> getGraph() {
|
---|
| 69 | Graph<String, MarkovEdge> graph = new SparseMultigraph<String, MarkovEdge>();
|
---|
| 70 |
|
---|
| 71 | List<Event<?>> knownSymbols = new ArrayList<Event<?>>(trie.getKnownSymbols());
|
---|
| 72 |
|
---|
| 73 | for( Event<?> symbol : knownSymbols) {
|
---|
| 74 | String from = symbol.getShortId();
|
---|
| 75 | List<Event<?>> context = new ArrayList<Event<?>>();
|
---|
| 76 | context.add(symbol);
|
---|
| 77 |
|
---|
| 78 | List<Event<?>> followers = trie.getFollowingSymbols(context);
|
---|
| 79 |
|
---|
| 80 | for( Event<?> follower : followers ) {
|
---|
| 81 | String to = follower.getShortId();
|
---|
| 82 | MarkovEdge prob = new MarkovEdge(getProbability(context, follower));
|
---|
| 83 | graph.addEdge(prob, from, to, EdgeType.DIRECTED);
|
---|
| 84 | }
|
---|
| 85 | }
|
---|
| 86 | return graph;
|
---|
| 87 | }
|
---|
| 88 |
|
---|
| 89 | static public class MarkovEdge {
|
---|
| 90 | double weight;
|
---|
| 91 | MarkovEdge(double weight) { this.weight = weight; }
|
---|
| 92 | public String toString() { return ""+weight; }
|
---|
| 93 | }
|
---|
| 94 |
|
---|
| 95 | public double calcEntropy() {
|
---|
| 96 | Matrix transmissionMatrix = getTransmissionMatrix();
|
---|
| 97 | List<Event<?>> knownSymbols = new ArrayList<Event<?>>(trie.getKnownSymbols());
|
---|
| 98 | int numStates = knownSymbols.size();
|
---|
| 99 |
|
---|
| 100 | int startStateIndex = knownSymbols.indexOf(Event.STARTEVENT);
|
---|
| 101 | int endStateIndex = knownSymbols.indexOf(Event.ENDEVENT);
|
---|
| 102 | if( startStateIndex==-1 ) {
|
---|
| 103 | Console.printerrln("Error calculating entropy. Initial state of markov chain not found.");
|
---|
| 104 | return Double.NaN;
|
---|
| 105 | }
|
---|
| 106 | if( endStateIndex==-1 ) {
|
---|
| 107 | Console.printerrln("Error calculating entropy. End state of markov chain not found.");
|
---|
| 108 | return Double.NaN;
|
---|
| 109 | }
|
---|
| 110 | transmissionMatrix.set(endStateIndex, startStateIndex, 1);
|
---|
| 111 |
|
---|
| 112 | // Calculate stationary distribution by raising the power of the transmission matrix.
|
---|
| 113 | // The rank of the matrix should fall to 1 and each two should be the vector of the
|
---|
| 114 | // stationory distribution.
|
---|
| 115 | int iter = 0;
|
---|
| 116 | int rank = transmissionMatrix.rank();
|
---|
| 117 | Matrix stationaryMatrix = (Matrix) transmissionMatrix.clone();
|
---|
| 118 | while( iter<MAX_STATDIST_ITERATIONS && rank>1 ) {
|
---|
| 119 | stationaryMatrix = stationaryMatrix.times(stationaryMatrix);
|
---|
| 120 | rank = stationaryMatrix.rank();
|
---|
| 121 | iter++;
|
---|
| 122 | }
|
---|
| 123 |
|
---|
| 124 | if( rank!=1 ) {
|
---|
| 125 | Console.traceln("rank: " + rank);
|
---|
| 126 | Console.printerrln("Unable to calculate stationary distribution.");
|
---|
| 127 | return Double.NaN;
|
---|
| 128 | }
|
---|
| 129 |
|
---|
| 130 | double entropy = 0.0;
|
---|
| 131 | for( int i=0 ; i<numStates ; i++ ) {
|
---|
| 132 | for( int j=0 ; j<numStates ; j++ ) {
|
---|
| 133 | if( transmissionMatrix.get(i,j)!=0 ) {
|
---|
| 134 | double tmp = stationaryMatrix.get(i, 0);
|
---|
| 135 | tmp *= transmissionMatrix.get(i, j);
|
---|
| 136 | tmp *= Math.log(transmissionMatrix.get(i,j))/Math.log(2);
|
---|
| 137 | entropy -= tmp;
|
---|
| 138 | }
|
---|
| 139 | }
|
---|
| 140 | }
|
---|
| 141 | return entropy;
|
---|
| 142 | }
|
---|
| 143 |
|
---|
| 144 | }
|
---|