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
RevLine 
[13]1package de.ugoe.cs.eventbench.models;
[12]2
[93]3import java.security.InvalidParameterException;
4import java.util.ArrayList;
[102]5import java.util.Collection;
[252]6import java.util.HashSet;
[93]7import java.util.LinkedHashSet;
[12]8import java.util.LinkedList;
9import java.util.List;
10import java.util.Random;
[80]11import java.util.Set;
[12]12
13import de.ugoe.cs.eventbench.data.Event;
[23]14import de.ugoe.cs.eventbench.models.Trie.Edge;
15import de.ugoe.cs.eventbench.models.Trie.TrieVertex;
16import edu.uci.ics.jung.graph.Tree;
[12]17
[100]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 */
[17]29public abstract class TrieBasedModel implements IStochasticProcess {
[12]30
[86]31        /**
[100]32         * <p>
[86]33         * Id for object serialization.
[100]34         * </p>
[86]35         */
36        private static final long serialVersionUID = 1L;
37
[100]38        /**
39         * <p>
40         * The order of the trie, i.e., the maximum length of subsequences stored in
41         * the trie.
42         * </p>
43         */
[16]44        protected int trieOrder;
[12]45
[100]46        /**
47         * <p>
48         * Trie on which the probability calculations are based.
49         * </p>
50         */
[182]51        protected Trie<Event<?>> trie = null;
[100]52
53        /**
54         * <p>
55         * Random number generator used by probabilistic sequence generation
56         * methods.
57         * </p>
58         */
[12]59        protected final Random r;
60
[100]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
[342]72         * @throws InvalidParameterException
73         *             thrown if markovOrder is less than 0 or the random number
74         *             generator r is null
[100]75         */
[16]76        public TrieBasedModel(int markovOrder, Random r) {
[12]77                super();
[342]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                }
[100]86                this.trieOrder = markovOrder + 1;
[12]87                this.r = r;
88        }
89
[100]90        /**
91         * <p>
92         * Trains the model by generating a trie from which probabilities are
[182]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.
[100]96         * </p>
97         *
98         * @param sequences
99         *            training data
[342]100         * @throws InvalidParameterException
101         *             thrown is sequences is null
[100]102         */
[325]103        public void train(Collection<List<? extends Event<?>>> sequences) {
[182]104                trie = null;
105                update(sequences);
106        }
[100]107
[182]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
[342]118         * @throws InvalidParameterException
119         *             thrown is sequences is null
[182]120         */
[325]121        public void update(Collection<List<? extends Event<?>>> sequences) {
[252]122                if (sequences == null) {
[342]123                        throw new InvalidParameterException("sequences must not be null");
[252]124                }
[182]125                if (trie == null) {
126                        trie = new Trie<Event<?>>();
127                }
[325]128                for (List<? extends Event<?>> sequence : sequences) {
[100]129                        List<Event<?>> currentSequence = new LinkedList<Event<?>>(sequence); // defensive
130                                                                                                                                                                        // copy
[12]131                        currentSequence.add(0, Event.STARTEVENT);
132                        currentSequence.add(Event.ENDEVENT);
[100]133
[16]134                        trie.train(currentSequence, trieOrder);
[12]135                }
136        }
137
[100]138        /*
139         * (non-Javadoc)
140         *
[17]141         * @see de.ugoe.cs.eventbench.models.IStochasticProcess#randomSequence()
142         */
143        @Override
[12]144        public List<? extends Event<?>> randomSequence() {
[386]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) {
[12]156                List<Event<?>> sequence = new LinkedList<Event<?>>();
[342]157                if (trie != null) {
[386]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);
[342]164
[386]165                                Event<?> currentState = Event.STARTEVENT;
[342]166
[386]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;
[252]184                                                }
[12]185                                        }
186                                }
187                        }
188                }
189                return sequence;
190        }
[100]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         */
[30]199        public String getTrieDotRepresentation() {
[252]200                if (trie == null) {
201                        return "";
202                } else {
203                        return trie.getDotRepresentation();
204                }
[30]205        }
[100]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         */
[23]215        public Tree<TrieVertex, Edge> getTrieGraph() {
[252]216                if (trie == null) {
217                        return null;
218                } else {
219                        return trie.getGraph();
220                }
[23]221        }
[12]222
[100]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         */
[12]231        @Override
232        public String toString() {
[252]233                if (trie == null) {
234                        return "";
235                } else {
236                        return trie.toString();
237                }
[12]238        }
[100]239
240        /*
241         * (non-Javadoc)
242         *
243         * @see de.ugoe.cs.eventbench.models.IStochasticProcess#getNumStates()
244         */
245        @Override
[129]246        public int getNumSymbols() {
[252]247                if (trie == null) {
248                        return 0;
249                } else {
250                        return trie.getNumSymbols();
251                }
[66]252        }
[100]253
254        /*
255         * (non-Javadoc)
256         *
257         * @see de.ugoe.cs.eventbench.models.IStochasticProcess#getStateStrings()
258         */
259        @Override
[129]260        public String[] getSymbolStrings() {
[252]261                if (trie == null) {
262                        return new String[0];
263                }
[129]264                String[] stateStrings = new String[getNumSymbols()];
[100]265                int i = 0;
266                for (Event<?> symbol : trie.getKnownSymbols()) {
[386]267                        if (symbol.toString() == null) {
268                                stateStrings[i] = "null";
269                        } else {
270                                stateStrings[i] = symbol.toString();
271                        }
[70]272                        i++;
273                }
274                return stateStrings;
275        }
[100]276
277        /*
278         * (non-Javadoc)
279         *
280         * @see de.ugoe.cs.eventbench.models.IStochasticProcess#getEvents()
281         */
282        @Override
[102]283        public Collection<? extends Event<?>> getEvents() {
[252]284                if (trie == null) {
285                        return new HashSet<Event<?>>();
286                } else {
287                        return trie.getKnownSymbols();
288                }
[80]289        }
[100]290
291        /*
292         * (non-Javadoc)
293         *
294         * @see
295         * de.ugoe.cs.eventbench.models.IStochasticProcess#generateSequences(int)
296         */
297        @Override
[102]298        public Collection<List<? extends Event<?>>> generateSequences(int length) {
[94]299                return generateSequences(length, false);
[93]300        }
[100]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.");
[94]316                }
[100]317                if (length == 1) {
318                        if (fromStart) {
[94]319                                List<Event<?>> subSeq = new LinkedList<Event<?>>();
320                                subSeq.add(Event.STARTEVENT);
[95]321                                sequenceSet.add(subSeq);
[94]322                        } else {
[100]323                                for (Event<?> event : getEvents()) {
[94]324                                        List<Event<?>> subSeq = new LinkedList<Event<?>>();
325                                        subSeq.add(event);
326                                        sequenceSet.add(subSeq);
327                                }
328                        }
329                        return sequenceSet;
330                }
[102]331                Collection<? extends Event<?>> events = getEvents();
332                Collection<List<? extends Event<?>>> seqsShorter = generateSequences(
[100]333                                length - 1, fromStart);
334                for (Event<?> event : events) {
335                        for (List<? extends Event<?>> seqShorter : seqsShorter) {
[94]336                                Event<?> lastEvent = event;
[100]337                                if (getProbability(seqShorter, lastEvent) > 0.0) {
[94]338                                        List<Event<?>> subSeq = new ArrayList<Event<?>>(seqShorter);
339                                        subSeq.add(lastEvent);
340                                        sequenceSet.add(subSeq);
341                                }
342                        }
343                }
344                return sequenceSet;
345        }
[100]346
347        /*
348         * (non-Javadoc)
349         *
350         * @see
351         * de.ugoe.cs.eventbench.models.IStochasticProcess#generateValidSequences
352         * (int)
353         */
354        @Override
[118]355        public Collection<List<? extends Event<?>>> generateValidSequences(
356                        int length) {
[94]357                // check for min-length implicitly done by generateSequences
[118]358                Collection<List<? extends Event<?>>> allSequences = generateSequences(
359                                length, true);
[102]360                Collection<List<? extends Event<?>>> validSequences = new LinkedHashSet<List<? extends Event<?>>>();
[100]361                for (List<? extends Event<?>> sequence : allSequences) {
362                        if (sequence.size() == length
363                                        && Event.ENDEVENT.equals(sequence.get(sequence.size() - 1))) {
[95]364                                validSequences.add(sequence);
[94]365                        }
366                }
367                return validSequences;
368        }
[12]369
[118]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) {
[342]379                if (sequence == null) {
380                        throw new InvalidParameterException("sequence must not be null");
381                }
[118]382                double prob = 1.0;
[342]383                List<Event<?>> context = new LinkedList<Event<?>>();
384                for (Event<?> event : sequence) {
385                        prob *= getProbability(context, event);
386                        context.add(event);
[118]387                }
388                return prob;
389        }
390
[182]391        /*
392         * (non-Javadoc)
393         *
[129]394         * @see de.ugoe.cs.eventbench.models.IStochasticProcess#getNumFOMStates()
395         */
396        @Override
397        public int getNumFOMStates() {
[252]398                if (trie == null) {
399                        return 0;
400                } else {
401                        return trie.getNumLeafAncestors();
402                }
[129]403        }
[248]404
405        /*
406         * (non-Javadoc)
407         *
408         * @see de.ugoe.cs.eventbench.models.IStochasticProcess#getNumTransitions()
409         */
410        @Override
411        public int getNumTransitions() {
[252]412                if (trie == null) {
413                        return 0;
414                } else {
415                        return trie.getNumLeafs();
416                }
[248]417        }
[12]418}
Note: See TracBrowser for help on using the repository browser.