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;
|
---|
8 | import de.ugoe.cs.util.StringTools;
|
---|
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 |
|
---|
16 | /**
|
---|
17 | * <p>
|
---|
18 | * Implements first-order Markov models. The implementation is based on
|
---|
19 | * {@link HighOrderMarkovModel} and restricts the Markov order to 1. In
|
---|
20 | * comparison to {@link HighOrderMarkovModel}, more calculations are possible
|
---|
21 | * with first-order models, e.g., the calculation of the entropy (
|
---|
22 | * {@link #calcEntropy()}).
|
---|
23 | * </p>
|
---|
24 | *
|
---|
25 | * @author Steffen Herbold
|
---|
26 | * @version 1.0
|
---|
27 | */
|
---|
28 | public class FirstOrderMarkovModel extends HighOrderMarkovModel implements
|
---|
29 | IDotCompatible {
|
---|
30 |
|
---|
31 | /**
|
---|
32 | * <p>
|
---|
33 | * Id for object serialization.
|
---|
34 | * </p>
|
---|
35 | */
|
---|
36 | private static final long serialVersionUID = 1L;
|
---|
37 |
|
---|
38 | /**
|
---|
39 | * <p>
|
---|
40 | * Maximum number of iterations when calculating the stationary distribution
|
---|
41 | * as the limit of multiplying the transmission matrix with itself.
|
---|
42 | * </p>
|
---|
43 | */
|
---|
44 | final static int MAX_STATDIST_ITERATIONS = 1000;
|
---|
45 |
|
---|
46 | /**
|
---|
47 | * <p>
|
---|
48 | * Constructor. Creates a new FirstOrderMarkovModel.
|
---|
49 | * </p>
|
---|
50 | *
|
---|
51 | * @param r
|
---|
52 | * random number generator used by probabilistic methods of the
|
---|
53 | * class
|
---|
54 | */
|
---|
55 | public FirstOrderMarkovModel(Random r) {
|
---|
56 | super(1, r);
|
---|
57 | }
|
---|
58 |
|
---|
59 | /**
|
---|
60 | * <p>
|
---|
61 | * Generates the transmission matrix of the Markov model.
|
---|
62 | * </p>
|
---|
63 | *
|
---|
64 | * @return transmission matrix
|
---|
65 | */
|
---|
66 | private Matrix getTransmissionMatrix() {
|
---|
67 | List<Event<?>> knownSymbols = new ArrayList<Event<?>>(
|
---|
68 | trie.getKnownSymbols());
|
---|
69 | int numStates = knownSymbols.size();
|
---|
70 | Matrix transmissionMatrix = new Matrix(numStates, numStates);
|
---|
71 |
|
---|
72 | for (int i = 0; i < numStates; i++) {
|
---|
73 | Event<?> currentSymbol = knownSymbols.get(i);
|
---|
74 | List<Event<?>> context = new ArrayList<Event<?>>();
|
---|
75 | context.add(currentSymbol);
|
---|
76 | for (int j = 0; j < numStates; j++) {
|
---|
77 | Event<?> follower = knownSymbols.get(j);
|
---|
78 | double prob = getProbability(context, follower);
|
---|
79 | transmissionMatrix.set(i, j, prob);
|
---|
80 | }
|
---|
81 | }
|
---|
82 | return transmissionMatrix;
|
---|
83 | }
|
---|
84 |
|
---|
85 | /**
|
---|
86 | * <p>
|
---|
87 | * Calculates the entropy of the model. To make it possible that the model
|
---|
88 | * is stationary, a transition from {@link Event#ENDEVENT} to
|
---|
89 | * {@link Event#STARTEVENT} is added.
|
---|
90 | * </p>
|
---|
91 | *
|
---|
92 | * @return entropy of the model or NaN if it could not be calculated
|
---|
93 | */
|
---|
94 | public double calcEntropy() {
|
---|
95 | Matrix transmissionMatrix = getTransmissionMatrix();
|
---|
96 | List<Event<?>> knownSymbols = new ArrayList<Event<?>>(
|
---|
97 | 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
|
---|
113 | // transmission matrix.
|
---|
114 | // The rank of the matrix should fall to 1 and each two should be the
|
---|
115 | // vector of the stationory distribution.
|
---|
116 | int iter = 0;
|
---|
117 | int rank = transmissionMatrix.rank();
|
---|
118 | Matrix stationaryMatrix = (Matrix) transmissionMatrix.clone();
|
---|
119 | while (iter < MAX_STATDIST_ITERATIONS && rank > 1) {
|
---|
120 | stationaryMatrix = stationaryMatrix.times(stationaryMatrix);
|
---|
121 | rank = stationaryMatrix.rank();
|
---|
122 | iter++;
|
---|
123 | }
|
---|
124 |
|
---|
125 | if (rank != 1) {
|
---|
126 | Console.traceln("rank: " + rank);
|
---|
127 | Console.printerrln("Unable to calculate stationary distribution.");
|
---|
128 | return Double.NaN;
|
---|
129 | }
|
---|
130 |
|
---|
131 | double entropy = 0.0;
|
---|
132 | for (int i = 0; i < numStates; i++) {
|
---|
133 | for (int j = 0; j < numStates; j++) {
|
---|
134 | if (transmissionMatrix.get(i, j) != 0) {
|
---|
135 | double tmp = stationaryMatrix.get(i, 0);
|
---|
136 | tmp *= transmissionMatrix.get(i, j);
|
---|
137 | tmp *= Math.log(transmissionMatrix.get(i, j)) / Math.log(2);
|
---|
138 | entropy -= tmp;
|
---|
139 | }
|
---|
140 | }
|
---|
141 | }
|
---|
142 | return entropy;
|
---|
143 | }
|
---|
144 |
|
---|
145 | /**
|
---|
146 | * <p>
|
---|
147 | * The dot represenation of {@link FirstOrderMarkovModel}s is its graph
|
---|
148 | * representation with the states as nodes and directed edges weighted with
|
---|
149 | * transition probabilities.
|
---|
150 | * </p>
|
---|
151 | *
|
---|
152 | * @see de.ugoe.cs.eventbench.models.IDotCompatible#getDotRepresentation()
|
---|
153 | */
|
---|
154 | @Override
|
---|
155 | public String getDotRepresentation() {
|
---|
156 | StringBuilder stringBuilder = new StringBuilder();
|
---|
157 | stringBuilder.append("digraph model {" + StringTools.ENDLINE);
|
---|
158 |
|
---|
159 | List<Event<?>> knownSymbols = new ArrayList<Event<?>>(
|
---|
160 | trie.getKnownSymbols());
|
---|
161 |
|
---|
162 | for (Event<?> symbol : knownSymbols) {
|
---|
163 | final String thisSaneId = symbol.getShortId().replace("\"", "\\\"")
|
---|
164 | .replaceAll("[\r\n]", "");
|
---|
165 | stringBuilder.append(" " + symbol.hashCode() + " [label=\""
|
---|
166 | + thisSaneId + "\"];" + StringTools.ENDLINE);
|
---|
167 | List<Event<?>> context = new ArrayList<Event<?>>();
|
---|
168 | context.add(symbol);
|
---|
169 | List<Event<?>> followers = trie.getFollowingSymbols(context);
|
---|
170 | for (Event<?> follower : followers) {
|
---|
171 | stringBuilder.append(" " + symbol.hashCode() + " -> "
|
---|
172 | + follower.hashCode() + " ");
|
---|
173 | stringBuilder.append("[label=\""
|
---|
174 | + getProbability(context, follower) + "\"];"
|
---|
175 | + StringTools.ENDLINE);
|
---|
176 | }
|
---|
177 | }
|
---|
178 | stringBuilder.append('}' + StringTools.ENDLINE);
|
---|
179 | return stringBuilder.toString();
|
---|
180 | }
|
---|
181 |
|
---|
182 | /**
|
---|
183 | * <p>
|
---|
184 | * Returns a {@link Graph} represenation of the model with the states as
|
---|
185 | * nodes and directed edges weighted with transition probabilities.
|
---|
186 | * </p>
|
---|
187 | *
|
---|
188 | * @return {@link Graph} of the model
|
---|
189 | */
|
---|
190 | public Graph<String, MarkovEdge> getGraph() {
|
---|
191 | Graph<String, MarkovEdge> graph = new SparseMultigraph<String, MarkovEdge>();
|
---|
192 |
|
---|
193 | List<Event<?>> knownSymbols = new ArrayList<Event<?>>(
|
---|
194 | trie.getKnownSymbols());
|
---|
195 |
|
---|
196 | for (Event<?> symbol : knownSymbols) {
|
---|
197 | String from = symbol.getShortId();
|
---|
198 | List<Event<?>> context = new ArrayList<Event<?>>();
|
---|
199 | context.add(symbol);
|
---|
200 |
|
---|
201 | List<Event<?>> followers = trie.getFollowingSymbols(context);
|
---|
202 |
|
---|
203 | for (Event<?> follower : followers) {
|
---|
204 | String to = follower.getShortId();
|
---|
205 | MarkovEdge prob = new MarkovEdge(getProbability(context,
|
---|
206 | follower));
|
---|
207 | graph.addEdge(prob, from, to, EdgeType.DIRECTED);
|
---|
208 | }
|
---|
209 | }
|
---|
210 | return graph;
|
---|
211 | }
|
---|
212 |
|
---|
213 | /**
|
---|
214 | * Inner class used for the {@link Graph} representation of the model.
|
---|
215 | *
|
---|
216 | * @author Steffen Herbold
|
---|
217 | * @version 1.0
|
---|
218 | */
|
---|
219 | static public class MarkovEdge {
|
---|
220 | /**
|
---|
221 | * <p>
|
---|
222 | * Weight of the edge, i.e., its transition probability.
|
---|
223 | * </p>
|
---|
224 | */
|
---|
225 | double weight;
|
---|
226 |
|
---|
227 | /**
|
---|
228 | * <p>
|
---|
229 | * Constructor. Creates a new MarkovEdge.
|
---|
230 | * </p>
|
---|
231 | *
|
---|
232 | * @param weight
|
---|
233 | * weight of the edge, i.e., its transition probability
|
---|
234 | */
|
---|
235 | MarkovEdge(double weight) {
|
---|
236 | this.weight = weight;
|
---|
237 | }
|
---|
238 |
|
---|
239 | /**
|
---|
240 | * <p>
|
---|
241 | * The weight of the edge as {@link String}.
|
---|
242 | * </p>
|
---|
243 | */
|
---|
244 | public String toString() {
|
---|
245 | return "" + weight;
|
---|
246 | }
|
---|
247 | }
|
---|
248 |
|
---|
249 | }
|
---|