source: trunk/EventBenchCore/src/de/ugoe/cs/eventbench/models/TrieBasedModel.java @ 391

Last change on this file since 391 was 391, checked in by sherbold, 12 years ago
  • modified de.ugoe.cs.eventbench.data.Event.equals(Object) such that targetEquals is always called, if the other object can equal the Event object. This simplifies pre-computing the equalities of de.ugoe.cs.eventbench.jfc.data.JFCEvents (project EventBenchConsole?) significantly.
  • minor optimization of de.ugoe.cs.eventbench.models.TrieBasedModel?.randomSequence(int, boolean). Removed obsolete variable currentState.
  • Property svn:mime-type set to text/plain
File size: 10.5 KB
Line 
1package de.ugoe.cs.eventbench.models;
2
3import java.security.InvalidParameterException;
4import java.util.ArrayList;
5import java.util.Collection;
6import java.util.HashSet;
7import java.util.LinkedHashSet;
8import java.util.LinkedList;
9import java.util.List;
10import java.util.Random;
11import java.util.Set;
12
13import de.ugoe.cs.eventbench.data.Event;
14import de.ugoe.cs.eventbench.models.Trie.Edge;
15import de.ugoe.cs.eventbench.models.Trie.TrieVertex;
16import edu.uci.ics.jung.graph.Tree;
17
18/**
19 * <p>
20 * Implements a skeleton for stochastic processes that can calculate
21 * probabilities based on a trie. The skeleton provides all functionalities of
22 * {@link IStochasticProcess} except
23 * {@link IStochasticProcess#getProbability(List, Event)}.
24 * </p>
25 *
26 * @author Steffen Herbold
27 * @version 1.0
28 */
29public abstract class TrieBasedModel implements IStochasticProcess {
30
31        /**
32         * <p>
33         * Id for object serialization.
34         * </p>
35         */
36        private static final long serialVersionUID = 1L;
37
38        /**
39         * <p>
40         * The order of the trie, i.e., the maximum length of subsequences stored in
41         * the trie.
42         * </p>
43         */
44        protected int trieOrder;
45
46        /**
47         * <p>
48         * Trie on which the probability calculations are based.
49         * </p>
50         */
51        protected Trie<Event<?>> trie = null;
52
53        /**
54         * <p>
55         * Random number generator used by probabilistic sequence generation
56         * methods.
57         * </p>
58         */
59        protected final Random r;
60
61        /**
62         * <p>
63         * Constructor. Creates a new TrieBasedModel that can be used for stochastic
64         * processes with a Markov order less than or equal to {@code markovOrder}.
65         * </p>
66         *
67         * @param markovOrder
68         *            Markov order of the model
69         * @param r
70         *            random number generator used by probabilistic methods of the
71         *            class
72         * @throws InvalidParameterException
73         *             thrown if markovOrder is less than 0 or the random number
74         *             generator r is null
75         */
76        public TrieBasedModel(int markovOrder, Random r) {
77                super();
78                if (markovOrder < 0) {
79                        throw new InvalidParameterException(
80                                        "markov order must not be less than 0");
81                }
82                if (r == null) {
83                        throw new InvalidParameterException(
84                                        "random number generator r must not be null");
85                }
86                this.trieOrder = markovOrder + 1;
87                this.r = r;
88        }
89
90        /**
91         * <p>
92         * Trains the model by generating a trie from which probabilities are
93         * calculated. The trie is newly generated based solely on the passed
94         * sequences. If an existing model should only be updated, use
95         * {@link #update(Collection)} instead.
96         * </p>
97         *
98         * @param sequences
99         *            training data
100         * @throws InvalidParameterException
101         *             thrown is sequences is null
102         */
103        public void train(Collection<List<? extends Event<?>>> sequences) {
104                trie = null;
105                update(sequences);
106        }
107
108        /**
109         * <p>
110         * Trains the model by updating the trie from which the probabilities are
111         * calculated. This function updates an existing trie. In case no trie
112         * exists yet, a new trie is generated and the function behaves like
113         * {@link #train(Collection)}.
114         * </p>
115         *
116         * @param sequences
117         *            training data
118         * @throws InvalidParameterException
119         *             thrown is sequences is null
120         */
121        public void update(Collection<List<? extends Event<?>>> sequences) {
122                if (sequences == null) {
123                        throw new InvalidParameterException("sequences must not be null");
124                }
125                if (trie == null) {
126                        trie = new Trie<Event<?>>();
127                }
128                for (List<? extends Event<?>> sequence : sequences) {
129                        List<Event<?>> currentSequence = new LinkedList<Event<?>>(sequence); // defensive
130                                                                                                                                                                        // copy
131                        currentSequence.add(0, Event.STARTEVENT);
132                        currentSequence.add(Event.ENDEVENT);
133
134                        trie.train(currentSequence, trieOrder);
135                }
136        }
137
138        /*
139         * (non-Javadoc)
140         *
141         * @see de.ugoe.cs.eventbench.models.IStochasticProcess#randomSequence()
142         */
143        @Override
144        public List<? extends Event<?>> randomSequence() {
145                return randomSequence(Integer.MAX_VALUE, true);
146        }
147
148        /*
149         * (non-Javadoc)
150         *
151         * @see de.ugoe.cs.eventbench.models.IStochasticProcess#randomSequence()
152         */
153        @Override
154        public List<? extends Event<?>> randomSequence(int maxLength,
155                        boolean validEnd) {
156                List<Event<?>> sequence = new LinkedList<Event<?>>();
157                if (trie != null) {
158                        boolean endFound = false;
159                        while (!endFound) { // outer loop for length checking
160                                sequence = new LinkedList<Event<?>>();
161                                IncompleteMemory<Event<?>> context = new IncompleteMemory<Event<?>>(
162                                                trieOrder - 1);
163                                context.add(Event.STARTEVENT);
164
165                                while (!endFound && sequence.size() < maxLength) {
166                                        double randVal = r.nextDouble();
167                                        double probSum = 0.0;
168                                        List<Event<?>> currentContext = context.getLast(trieOrder);
169                                        for (Event<?> symbol : trie.getKnownSymbols()) {
170                                                probSum += getProbability(currentContext, symbol);
171                                                if (probSum >= randVal) {
172                                                        if (!(symbol == Event.STARTEVENT || symbol == Event.ENDEVENT)) {
173                                                                // only add the symbol the sequence if it is not
174                                                                // START or END
175                                                                context.add(symbol);
176                                                                sequence.add(symbol);
177                                                        }
178                                                        endFound = (symbol == Event.ENDEVENT)
179                                                                        || (!validEnd && sequence.size() == maxLength);
180                                                        break;
181                                                }
182                                        }
183                                }
184                        }
185                }
186                return sequence;
187        }
188
189        /**
190         * <p>
191         * Returns a Dot representation of the internal trie.
192         * </p>
193         *
194         * @return dot representation of the internal trie
195         */
196        public String getTrieDotRepresentation() {
197                if (trie == null) {
198                        return "";
199                } else {
200                        return trie.getDotRepresentation();
201                }
202        }
203
204        /**
205         * <p>
206         * Returns a {@link Tree} of the internal trie that can be used for
207         * visualization.
208         * </p>
209         *
210         * @return {@link Tree} depicting the internal trie
211         */
212        public Tree<TrieVertex, Edge> getTrieGraph() {
213                if (trie == null) {
214                        return null;
215                } else {
216                        return trie.getGraph();
217                }
218        }
219
220        /**
221         * <p>
222         * The string representation of the model is {@link Trie#toString()} of
223         * {@link #trie}.
224         * </p>
225         *
226         * @see java.lang.Object#toString()
227         */
228        @Override
229        public String toString() {
230                if (trie == null) {
231                        return "";
232                } else {
233                        return trie.toString();
234                }
235        }
236
237        /*
238         * (non-Javadoc)
239         *
240         * @see de.ugoe.cs.eventbench.models.IStochasticProcess#getNumStates()
241         */
242        @Override
243        public int getNumSymbols() {
244                if (trie == null) {
245                        return 0;
246                } else {
247                        return trie.getNumSymbols();
248                }
249        }
250
251        /*
252         * (non-Javadoc)
253         *
254         * @see de.ugoe.cs.eventbench.models.IStochasticProcess#getStateStrings()
255         */
256        @Override
257        public String[] getSymbolStrings() {
258                if (trie == null) {
259                        return new String[0];
260                }
261                String[] stateStrings = new String[getNumSymbols()];
262                int i = 0;
263                for (Event<?> symbol : trie.getKnownSymbols()) {
264                        if (symbol.toString() == null) {
265                                stateStrings[i] = "null";
266                        } else {
267                                stateStrings[i] = symbol.toString();
268                        }
269                        i++;
270                }
271                return stateStrings;
272        }
273
274        /*
275         * (non-Javadoc)
276         *
277         * @see de.ugoe.cs.eventbench.models.IStochasticProcess#getEvents()
278         */
279        @Override
280        public Collection<? extends Event<?>> getEvents() {
281                if (trie == null) {
282                        return new HashSet<Event<?>>();
283                } else {
284                        return trie.getKnownSymbols();
285                }
286        }
287
288        /*
289         * (non-Javadoc)
290         *
291         * @see
292         * de.ugoe.cs.eventbench.models.IStochasticProcess#generateSequences(int)
293         */
294        @Override
295        public Collection<List<? extends Event<?>>> generateSequences(int length) {
296                return generateSequences(length, false);
297        }
298
299        /*
300         * (non-Javadoc)
301         *
302         * @see
303         * de.ugoe.cs.eventbench.models.IStochasticProcess#generateSequences(int,
304         * boolean)
305         */
306        @Override
307        public Set<List<? extends Event<?>>> generateSequences(int length,
308                        boolean fromStart) {
309                Set<List<? extends Event<?>>> sequenceSet = new LinkedHashSet<List<? extends Event<?>>>();
310                if (length < 1) {
311                        throw new InvalidParameterException(
312                                        "Length of generated subsequences must be at least 1.");
313                }
314                if (length == 1) {
315                        if (fromStart) {
316                                List<Event<?>> subSeq = new LinkedList<Event<?>>();
317                                subSeq.add(Event.STARTEVENT);
318                                sequenceSet.add(subSeq);
319                        } else {
320                                for (Event<?> event : getEvents()) {
321                                        List<Event<?>> subSeq = new LinkedList<Event<?>>();
322                                        subSeq.add(event);
323                                        sequenceSet.add(subSeq);
324                                }
325                        }
326                        return sequenceSet;
327                }
328                Collection<? extends Event<?>> events = getEvents();
329                Collection<List<? extends Event<?>>> seqsShorter = generateSequences(
330                                length - 1, fromStart);
331                for (Event<?> event : events) {
332                        for (List<? extends Event<?>> seqShorter : seqsShorter) {
333                                Event<?> lastEvent = event;
334                                if (getProbability(seqShorter, lastEvent) > 0.0) {
335                                        List<Event<?>> subSeq = new ArrayList<Event<?>>(seqShorter);
336                                        subSeq.add(lastEvent);
337                                        sequenceSet.add(subSeq);
338                                }
339                        }
340                }
341                return sequenceSet;
342        }
343
344        /*
345         * (non-Javadoc)
346         *
347         * @see
348         * de.ugoe.cs.eventbench.models.IStochasticProcess#generateValidSequences
349         * (int)
350         */
351        @Override
352        public Collection<List<? extends Event<?>>> generateValidSequences(
353                        int length) {
354                // check for min-length implicitly done by generateSequences
355                Collection<List<? extends Event<?>>> allSequences = generateSequences(
356                                length, true);
357                Collection<List<? extends Event<?>>> validSequences = new LinkedHashSet<List<? extends Event<?>>>();
358                for (List<? extends Event<?>> sequence : allSequences) {
359                        if (sequence.size() == length
360                                        && Event.ENDEVENT.equals(sequence.get(sequence.size() - 1))) {
361                                validSequences.add(sequence);
362                        }
363                }
364                return validSequences;
365        }
366
367        /*
368         * (non-Javadoc)
369         *
370         * @see
371         * de.ugoe.cs.eventbench.models.IStochasticProcess#getProbability(java.util
372         * .List)
373         */
374        @Override
375        public double getProbability(List<? extends Event<?>> sequence) {
376                if (sequence == null) {
377                        throw new InvalidParameterException("sequence must not be null");
378                }
379                double prob = 1.0;
380                List<Event<?>> context = new LinkedList<Event<?>>();
381                for (Event<?> event : sequence) {
382                        prob *= getProbability(context, event);
383                        context.add(event);
384                }
385                return prob;
386        }
387
388        /*
389         * (non-Javadoc)
390         *
391         * @see de.ugoe.cs.eventbench.models.IStochasticProcess#getNumFOMStates()
392         */
393        @Override
394        public int getNumFOMStates() {
395                if (trie == null) {
396                        return 0;
397                } else {
398                        return trie.getNumLeafAncestors();
399                }
400        }
401
402        /*
403         * (non-Javadoc)
404         *
405         * @see de.ugoe.cs.eventbench.models.IStochasticProcess#getNumTransitions()
406         */
407        @Override
408        public int getNumTransitions() {
409                if (trie == null) {
410                        return 0;
411                } else {
412                        return trie.getNumLeafs();
413                }
414        }
415}
Note: See TracBrowser for help on using the repository browser.