1 | package de.ugoe.cs.eventbench.models;
|
---|
2 |
|
---|
3 | import java.util.ArrayList;
|
---|
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 | import de.ugoe.cs.util.console.Console;
|
---|
10 |
|
---|
11 | public class PredictionByPartialMatch extends TrieBasedModel {
|
---|
12 |
|
---|
13 | double probEscape;
|
---|
14 |
|
---|
15 | public PredictionByPartialMatch(int markovOrder, Random r) {
|
---|
16 | this(markovOrder, r, 0.1);
|
---|
17 | }
|
---|
18 |
|
---|
19 | public PredictionByPartialMatch(int markovOrder, Random r, double probEscape) {
|
---|
20 | super(markovOrder, r);
|
---|
21 | this.probEscape = probEscape;
|
---|
22 | }
|
---|
23 |
|
---|
24 | public void setProbEscape(double probEscape) {
|
---|
25 | this.probEscape = probEscape;
|
---|
26 | }
|
---|
27 |
|
---|
28 | public double getProbEscape() {
|
---|
29 | return probEscape;
|
---|
30 | }
|
---|
31 |
|
---|
32 | @Override
|
---|
33 | protected double getProbability(List<Event<?>> context, Event<?> symbol) {
|
---|
34 | double result = 0.0d;
|
---|
35 | double resultCurrentContex = 0.0d;
|
---|
36 | double resultShorterContex = 0.0d;
|
---|
37 |
|
---|
38 | List<Event<?>> contextCopy = new LinkedList<Event<?>>(context); // defensive copy
|
---|
39 |
|
---|
40 |
|
---|
41 | List<Event<?>> followers = trie.getFollowingSymbols(contextCopy); // \Sigma'
|
---|
42 | int sumCountFollowers = 0; // N(s\sigma')
|
---|
43 | for( Event<?> follower : followers ) {
|
---|
44 | sumCountFollowers += trie.getCount(contextCopy, follower);
|
---|
45 | }
|
---|
46 |
|
---|
47 | int countSymbol = trie.getCount(contextCopy, symbol); // N(s\sigma)
|
---|
48 | if( contextCopy.size()==0 ) {
|
---|
49 | resultCurrentContex = ((double) countSymbol) / sumCountFollowers;
|
---|
50 | } else {
|
---|
51 | resultCurrentContex = ((double) countSymbol / sumCountFollowers)*(1-probEscape);
|
---|
52 | contextCopy.remove(0);
|
---|
53 | double probSuffix = getProbability(contextCopy, symbol);
|
---|
54 | if( followers.size()==0 ) {
|
---|
55 | resultShorterContex = probSuffix;
|
---|
56 | } else {
|
---|
57 | resultShorterContex = probEscape*probSuffix;
|
---|
58 | }
|
---|
59 | }
|
---|
60 | result = resultCurrentContex+resultShorterContex;
|
---|
61 |
|
---|
62 | return result;
|
---|
63 | }
|
---|
64 |
|
---|
65 | public void testStuff() {
|
---|
66 | // basically an inline unit test without assertions but manual observation
|
---|
67 | List<Event<?>> list = new ArrayList<Event<?>>();
|
---|
68 | list.add(new Event<Object>("a"));
|
---|
69 | list.add(new Event<Object>("b"));
|
---|
70 | list.add(new Event<Object>("r"));
|
---|
71 | list.add(new Event<Object>("a"));
|
---|
72 | list.add(new Event<Object>("c"));
|
---|
73 | list.add(new Event<Object>("a"));
|
---|
74 | list.add(new Event<Object>("d"));
|
---|
75 | list.add(new Event<Object>("a"));
|
---|
76 | list.add(new Event<Object>("b"));
|
---|
77 | list.add(new Event<Object>("r"));
|
---|
78 | list.add(new Event<Object>("a"));
|
---|
79 |
|
---|
80 | int maxOrder = 3;
|
---|
81 | PredictionByPartialMatch model = new PredictionByPartialMatch(maxOrder, new Random());
|
---|
82 | model.trie = new Trie<Event<?>>();
|
---|
83 | model.trie.train(list, maxOrder);
|
---|
84 | model.trie.display();
|
---|
85 |
|
---|
86 | List<Event<?>> context = new ArrayList<Event<?>>();
|
---|
87 | Event<Object> symbol = new Event<Object>("a");
|
---|
88 | // expected: 5
|
---|
89 | Console.traceln(""+model.trie.getCount(context, symbol));
|
---|
90 |
|
---|
91 | // expected: 0
|
---|
92 | context.add(new Event<Object>("b"));
|
---|
93 | Console.traceln(""+model.trie.getCount(context, symbol));
|
---|
94 |
|
---|
95 | // expected: 2
|
---|
96 | context.add(new Event<Object>("r"));
|
---|
97 | Console.traceln(""+model.trie.getCount(context, symbol));
|
---|
98 |
|
---|
99 | // exptected: [b, r]
|
---|
100 | context = new ArrayList<Event<?>>();
|
---|
101 | context.add(new Event<Object>("a"));
|
---|
102 | context.add(new Event<Object>("b"));
|
---|
103 | context.add(new Event<Object>("r"));
|
---|
104 | Console.traceln(model.trie.getContextSuffix(context).toString());
|
---|
105 |
|
---|
106 | // exptected: []
|
---|
107 | context = new ArrayList<Event<?>>();
|
---|
108 | context.add(new Event<Object>("e"));
|
---|
109 | Console.traceln(model.trie.getContextSuffix(context).toString());
|
---|
110 |
|
---|
111 | // exptected: {a, b, c, d, r}
|
---|
112 | context = new ArrayList<Event<?>>();
|
---|
113 | Console.traceln(model.trie.getFollowingSymbols(context).toString());
|
---|
114 |
|
---|
115 | // exptected: {b, c, d}
|
---|
116 | context = new ArrayList<Event<?>>();
|
---|
117 | context.add(new Event<Object>("a"));
|
---|
118 | Console.traceln(model.trie.getFollowingSymbols(context).toString());
|
---|
119 |
|
---|
120 | // exptected: []
|
---|
121 | context = new ArrayList<Event<?>>();
|
---|
122 | context.add(new Event<Object>("a"));
|
---|
123 | context.add(new Event<Object>("b"));
|
---|
124 | context.add(new Event<Object>("r"));
|
---|
125 | Console.traceln(model.trie.getFollowingSymbols(context).toString());
|
---|
126 |
|
---|
127 | // exptected: 0.0d
|
---|
128 | context = new ArrayList<Event<?>>();
|
---|
129 | context.add(new Event<Object>("a"));
|
---|
130 | Console.traceln(""+model.getProbability(context, new Event<Object>("z")));
|
---|
131 | }
|
---|
132 | }
|
---|