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

Last change on this file since 386 was 386, checked in by sherbold, 12 years ago
  • added method randomSequence(maxLength,validEnd) to the interface de.ugoe.cs.eventbench.models.IStochasticProcess (and implementing classes) to allow optimized generation of sessions of a pre-defined length.
  • Property svn:mime-type set to text/plain
File size: 10.6 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                                Event<?> currentState = Event.STARTEVENT;
166
167                                while (!endFound && sequence.size() < maxLength) {
168                                        double randVal = r.nextDouble();
169                                        double probSum = 0.0;
170                                        List<Event<?>> currentContext = context.getLast(trieOrder);
171                                        for (Event<?> symbol : trie.getKnownSymbols()) {
172                                                probSum += getProbability(currentContext, symbol);
173                                                if (probSum >= randVal) {
174                                                        if (!(symbol == Event.STARTEVENT || symbol == Event.ENDEVENT)) {
175                                                                // only add the symbol the sequence if it is not
176                                                                // START or END
177                                                                context.add(symbol);
178                                                                currentState = symbol;
179                                                                sequence.add(currentState);
180                                                        }
181                                                        endFound = (symbol == Event.ENDEVENT)
182                                                                        || (!validEnd && sequence.size() == maxLength);
183                                                        break;
184                                                }
185                                        }
186                                }
187                        }
188                }
189                return sequence;
190        }
191
192        /**
193         * <p>
194         * Returns a Dot representation of the internal trie.
195         * </p>
196         *
197         * @return dot representation of the internal trie
198         */
199        public String getTrieDotRepresentation() {
200                if (trie == null) {
201                        return "";
202                } else {
203                        return trie.getDotRepresentation();
204                }
205        }
206
207        /**
208         * <p>
209         * Returns a {@link Tree} of the internal trie that can be used for
210         * visualization.
211         * </p>
212         *
213         * @return {@link Tree} depicting the internal trie
214         */
215        public Tree<TrieVertex, Edge> getTrieGraph() {
216                if (trie == null) {
217                        return null;
218                } else {
219                        return trie.getGraph();
220                }
221        }
222
223        /**
224         * <p>
225         * The string representation of the model is {@link Trie#toString()} of
226         * {@link #trie}.
227         * </p>
228         *
229         * @see java.lang.Object#toString()
230         */
231        @Override
232        public String toString() {
233                if (trie == null) {
234                        return "";
235                } else {
236                        return trie.toString();
237                }
238        }
239
240        /*
241         * (non-Javadoc)
242         *
243         * @see de.ugoe.cs.eventbench.models.IStochasticProcess#getNumStates()
244         */
245        @Override
246        public int getNumSymbols() {
247                if (trie == null) {
248                        return 0;
249                } else {
250                        return trie.getNumSymbols();
251                }
252        }
253
254        /*
255         * (non-Javadoc)
256         *
257         * @see de.ugoe.cs.eventbench.models.IStochasticProcess#getStateStrings()
258         */
259        @Override
260        public String[] getSymbolStrings() {
261                if (trie == null) {
262                        return new String[0];
263                }
264                String[] stateStrings = new String[getNumSymbols()];
265                int i = 0;
266                for (Event<?> symbol : trie.getKnownSymbols()) {
267                        if (symbol.toString() == null) {
268                                stateStrings[i] = "null";
269                        } else {
270                                stateStrings[i] = symbol.toString();
271                        }
272                        i++;
273                }
274                return stateStrings;
275        }
276
277        /*
278         * (non-Javadoc)
279         *
280         * @see de.ugoe.cs.eventbench.models.IStochasticProcess#getEvents()
281         */
282        @Override
283        public Collection<? extends Event<?>> getEvents() {
284                if (trie == null) {
285                        return new HashSet<Event<?>>();
286                } else {
287                        return trie.getKnownSymbols();
288                }
289        }
290
291        /*
292         * (non-Javadoc)
293         *
294         * @see
295         * de.ugoe.cs.eventbench.models.IStochasticProcess#generateSequences(int)
296         */
297        @Override
298        public Collection<List<? extends Event<?>>> generateSequences(int length) {
299                return generateSequences(length, false);
300        }
301
302        /*
303         * (non-Javadoc)
304         *
305         * @see
306         * de.ugoe.cs.eventbench.models.IStochasticProcess#generateSequences(int,
307         * boolean)
308         */
309        @Override
310        public Set<List<? extends Event<?>>> generateSequences(int length,
311                        boolean fromStart) {
312                Set<List<? extends Event<?>>> sequenceSet = new LinkedHashSet<List<? extends Event<?>>>();
313                if (length < 1) {
314                        throw new InvalidParameterException(
315                                        "Length of generated subsequences must be at least 1.");
316                }
317                if (length == 1) {
318                        if (fromStart) {
319                                List<Event<?>> subSeq = new LinkedList<Event<?>>();
320                                subSeq.add(Event.STARTEVENT);
321                                sequenceSet.add(subSeq);
322                        } else {
323                                for (Event<?> event : getEvents()) {
324                                        List<Event<?>> subSeq = new LinkedList<Event<?>>();
325                                        subSeq.add(event);
326                                        sequenceSet.add(subSeq);
327                                }
328                        }
329                        return sequenceSet;
330                }
331                Collection<? extends Event<?>> events = getEvents();
332                Collection<List<? extends Event<?>>> seqsShorter = generateSequences(
333                                length - 1, fromStart);
334                for (Event<?> event : events) {
335                        for (List<? extends Event<?>> seqShorter : seqsShorter) {
336                                Event<?> lastEvent = event;
337                                if (getProbability(seqShorter, lastEvent) > 0.0) {
338                                        List<Event<?>> subSeq = new ArrayList<Event<?>>(seqShorter);
339                                        subSeq.add(lastEvent);
340                                        sequenceSet.add(subSeq);
341                                }
342                        }
343                }
344                return sequenceSet;
345        }
346
347        /*
348         * (non-Javadoc)
349         *
350         * @see
351         * de.ugoe.cs.eventbench.models.IStochasticProcess#generateValidSequences
352         * (int)
353         */
354        @Override
355        public Collection<List<? extends Event<?>>> generateValidSequences(
356                        int length) {
357                // check for min-length implicitly done by generateSequences
358                Collection<List<? extends Event<?>>> allSequences = generateSequences(
359                                length, true);
360                Collection<List<? extends Event<?>>> validSequences = new LinkedHashSet<List<? extends Event<?>>>();
361                for (List<? extends Event<?>> sequence : allSequences) {
362                        if (sequence.size() == length
363                                        && Event.ENDEVENT.equals(sequence.get(sequence.size() - 1))) {
364                                validSequences.add(sequence);
365                        }
366                }
367                return validSequences;
368        }
369
370        /*
371         * (non-Javadoc)
372         *
373         * @see
374         * de.ugoe.cs.eventbench.models.IStochasticProcess#getProbability(java.util
375         * .List)
376         */
377        @Override
378        public double getProbability(List<? extends Event<?>> sequence) {
379                if (sequence == null) {
380                        throw new InvalidParameterException("sequence must not be null");
381                }
382                double prob = 1.0;
383                List<Event<?>> context = new LinkedList<Event<?>>();
384                for (Event<?> event : sequence) {
385                        prob *= getProbability(context, event);
386                        context.add(event);
387                }
388                return prob;
389        }
390
391        /*
392         * (non-Javadoc)
393         *
394         * @see de.ugoe.cs.eventbench.models.IStochasticProcess#getNumFOMStates()
395         */
396        @Override
397        public int getNumFOMStates() {
398                if (trie == null) {
399                        return 0;
400                } else {
401                        return trie.getNumLeafAncestors();
402                }
403        }
404
405        /*
406         * (non-Javadoc)
407         *
408         * @see de.ugoe.cs.eventbench.models.IStochasticProcess#getNumTransitions()
409         */
410        @Override
411        public int getNumTransitions() {
412                if (trie == null) {
413                        return 0;
414                } else {
415                        return trie.getNumLeafs();
416                }
417        }
418}
Note: See TracBrowser for help on using the repository browser.