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

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