1 | package de.ugoe.cs.eventbench.models;
|
---|
2 |
|
---|
3 | import java.util.Collection;
|
---|
4 | import java.util.LinkedList;
|
---|
5 | import java.util.List;
|
---|
6 | import java.util.Random;
|
---|
7 |
|
---|
8 | import de.ugoe.cs.eventbench.data.Event;
|
---|
9 |
|
---|
10 | /**
|
---|
11 | * <p>
|
---|
12 | * Implements Prediction by Partial Match (PPM) based on the following formula
|
---|
13 | * (LaTeX-style notation):<br>
|
---|
14 | * P_{PPM}(X_n|X_{n-1},...,X_{n-k}) = \sum_{i=k}^1 escape^{i-1}
|
---|
15 | * P_{MM^i}(X_n|X_{n-1},...,X_{n-i})(1-escape)<br>
|
---|
16 | * P_{MM^i} denotes the probability in an i-th order Markov model.
|
---|
17 | * </p>
|
---|
18 | *
|
---|
19 | * @author Steffen Herbold
|
---|
20 | *
|
---|
21 | */
|
---|
22 | public class PredictionByPartialMatch extends TrieBasedModel {
|
---|
23 |
|
---|
24 | /**
|
---|
25 | * <p>
|
---|
26 | * Id for object serialization.
|
---|
27 | * </p>
|
---|
28 | */
|
---|
29 | private static final long serialVersionUID = 1L;
|
---|
30 |
|
---|
31 | /**
|
---|
32 | * <p>
|
---|
33 | * Probability to use a lower-order Markov model
|
---|
34 | * </p>
|
---|
35 | */
|
---|
36 | double probEscape;
|
---|
37 |
|
---|
38 | /**
|
---|
39 | * <p>
|
---|
40 | * Constructor. Creates a new PredictionByPartialMatch model with a given
|
---|
41 | * Markov order and a default escape probability of 0.1.
|
---|
42 | * </p>
|
---|
43 | *
|
---|
44 | * @param markovOrder
|
---|
45 | * Markov order of the model
|
---|
46 | * @param r
|
---|
47 | * random number generator used by probabilistic methods of the
|
---|
48 | * class
|
---|
49 | */
|
---|
50 | public PredictionByPartialMatch(int markovOrder, Random r) {
|
---|
51 | this(markovOrder, r, 0.1);
|
---|
52 | }
|
---|
53 |
|
---|
54 | /**
|
---|
55 | * <p>
|
---|
56 | * Creates a new PredictionByPartialMatch model with a given Markov order
|
---|
57 | * and escape probability.
|
---|
58 | * </p>
|
---|
59 | *
|
---|
60 | * @param markovOrder
|
---|
61 | * Markov order of the model
|
---|
62 | * @param r
|
---|
63 | * random number generator used by probabilistic methods of the
|
---|
64 | * class
|
---|
65 | * @param probEscape
|
---|
66 | * escape probability used by the model
|
---|
67 | */
|
---|
68 | public PredictionByPartialMatch(int markovOrder, Random r, double probEscape) {
|
---|
69 | super(markovOrder, r);
|
---|
70 | this.probEscape = probEscape;
|
---|
71 | }
|
---|
72 |
|
---|
73 | /**
|
---|
74 | * <p>
|
---|
75 | * Sets the escape probability of the model.
|
---|
76 | * </p>
|
---|
77 | *
|
---|
78 | * @param probEscape
|
---|
79 | * new escape probability
|
---|
80 | */
|
---|
81 | public void setProbEscape(double probEscape) {
|
---|
82 | this.probEscape = probEscape;
|
---|
83 | }
|
---|
84 |
|
---|
85 | /**
|
---|
86 | * <p>
|
---|
87 | * Returns the escape probability of the model.
|
---|
88 | * </p>
|
---|
89 | *
|
---|
90 | * @return escape probability of the model
|
---|
91 | */
|
---|
92 | public double getProbEscape() {
|
---|
93 | return probEscape;
|
---|
94 | }
|
---|
95 |
|
---|
96 | /**
|
---|
97 | * <p>
|
---|
98 | * Calculates the probability of the next event based on the formula:<br>
|
---|
99 | * P_{PPM}(X_n|X_{n-1},...,X_{n-k}) = \sum_{i=k}^1 escape^{i-1}
|
---|
100 | * P_{MM^i}(X_n|X_{n-1},...,X_{n-i})(1-escape)<br>
|
---|
101 | * P_{MM^i} denotes the probability in an i-th order Markov model.
|
---|
102 | * </p>
|
---|
103 | */
|
---|
104 | @Override
|
---|
105 | public double getProbability(List<? extends Event<?>> context,
|
---|
106 | Event<?> symbol) {
|
---|
107 | double result = 0.0d;
|
---|
108 | double resultCurrentContex = 0.0d;
|
---|
109 | double resultShorterContex = 0.0d;
|
---|
110 |
|
---|
111 | List<Event<?>> contextCopy;
|
---|
112 | if (context.size() >= trieOrder) {
|
---|
113 | contextCopy = new LinkedList<Event<?>>(context.subList(
|
---|
114 | context.size() - trieOrder + 1, context.size()));
|
---|
115 | } else {
|
---|
116 | contextCopy = new LinkedList<Event<?>>(context);
|
---|
117 | }
|
---|
118 |
|
---|
119 | Collection<Event<?>> followers = trie.getFollowingSymbols(contextCopy); // \Sigma'
|
---|
120 | int sumCountFollowers = 0; // N(s\sigma')
|
---|
121 | for (Event<?> follower : followers) {
|
---|
122 | sumCountFollowers += trie.getCount(contextCopy, follower);
|
---|
123 | }
|
---|
124 |
|
---|
125 | int countSymbol = trie.getCount(contextCopy, symbol); // N(s\sigma)
|
---|
126 | if (contextCopy.size() == 0) {
|
---|
127 | resultCurrentContex = ((double) countSymbol) / sumCountFollowers;
|
---|
128 | } else {
|
---|
129 | if (sumCountFollowers == 0) {
|
---|
130 | resultCurrentContex = 0.0;
|
---|
131 | } else {
|
---|
132 | resultCurrentContex = ((double) countSymbol / sumCountFollowers)
|
---|
133 | * (1 - probEscape);
|
---|
134 | }
|
---|
135 | contextCopy.remove(0);
|
---|
136 | double probSuffix = getProbability(contextCopy, symbol);
|
---|
137 | if (followers.size() == 0) {
|
---|
138 | resultShorterContex = probSuffix;
|
---|
139 | } else {
|
---|
140 | resultShorterContex = probEscape * probSuffix;
|
---|
141 | }
|
---|
142 | }
|
---|
143 | result = resultCurrentContex + resultShorterContex;
|
---|
144 |
|
---|
145 | return result;
|
---|
146 | }
|
---|
147 | }
|
---|