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