- Timestamp:
- 04/11/11 14:43:03 (14 years ago)
- Location:
- trunk/EventBenchCore
- Files:
-
- 2 added
- 5 edited
-
.classpath (modified) (1 diff)
-
lib/collections-generic-4.01.jar (added)
-
lib/commons-codec-1.5.jar (added)
-
src/de/ugoe/cs/eventbench/data/Event.java (modified) (3 diffs)
-
src/de/ugoe/cs/eventbench/ppm/PredictionByPartialMatch.java (modified) (10 diffs)
-
src/de/ugoe/cs/eventbench/ppm/Trie.java (modified) (7 diffs)
-
src/de/ugoe/cs/eventbench/ppm/TrieNode.java (modified) (3 diffs)
Legend:
- Unmodified
- Added
- Removed
-
trunk/EventBenchCore/.classpath
r1 r5 20 20 <classpathentry kind="lib" path="lib/vecmath-1.3.1.jar"/> 21 21 <classpathentry kind="lib" path="lib/wstx-asl-3.2.6.jar"/> 22 <classpathentry kind="lib" path="lib/commons-codec-1.5.jar"/> 22 23 <classpathentry combineaccessrules="false" kind="src" path="/JavaHelperLib"/> 23 24 <classpathentry kind="output" path="bin"/> -
trunk/EventBenchCore/src/de/ugoe/cs/eventbench/data/Event.java
r2 r5 26 26 27 27 28 private String idInfo = null;28 private String idInfo = ""; 29 29 30 30 public Event(String type) { … … 59 59 if (targetShort!=null) { 60 60 shortId = targetShort+"."+getType(); 61 if (idInfo!= null) {61 if (idInfo!="") { 62 62 shortId += "."+idInfo; 63 63 } … … 68 68 public String getStandardId() { 69 69 String id = target + "." + getType(); 70 if ( idInfo!= null) {70 if ( idInfo!="" ) { 71 71 id += "." + idInfo; 72 72 } -
trunk/EventBenchCore/src/de/ugoe/cs/eventbench/ppm/PredictionByPartialMatch.java
r1 r5 1 1 package de.ugoe.cs.eventbench.ppm; 2 2 3 import java.util.ArrayList; 3 4 import java.util.LinkedHashSet; 5 import java.util.LinkedList; 4 6 import java.util.List; 5 7 import java.util.Random; … … 12 14 public class PredictionByPartialMatch { 13 15 14 private String initialSymbol = "G LOBALSTARTSTATE";15 private String endSymbol = "G LOBALENDSTATE";16 private String initialSymbol = "GS"; 17 private String endSymbol = "GE"; 16 18 17 19 private int maxOrder = 3; … … 20 22 21 23 private Set<String> knownSymbols; 24 25 private double probEscape = 0.2d; // TODO getter/setter - steering parameter! 26 27 private Random r = new Random(); // TODO should be defined in the constructor 22 28 23 29 // the training is basically the generation of the trie … … 29 35 30 36 for(List<Event<?>> sequence : sequences) { 31 IncompleteMemory<String> latestActions = new IncompleteMemory<String>(maxOrder); // TODO need to check if it should be maxOrder+1 32 latestActions.add(initialSymbol); 33 for(Event<?> currentAction : sequence) { 34 String currentId = currentAction.getStandardId(); 35 latestActions.add(currentId); 36 knownSymbols.add(currentId); 37 if( latestActions.getLength()==maxOrder ) { // FIXME needs special case for sequences shorter than maxOrder 38 trie.add(latestActions.getLast(maxOrder)); 39 } 40 } 41 latestActions.add(endSymbol); 42 if( latestActions.getLength()==maxOrder ) { // FIXME needs special case for sequences shorter than maxOrder 37 List<String> stringSequence = new LinkedList<String>(); 38 stringSequence.add(initialSymbol); 39 for( Event<?> event : sequence ) { 40 stringSequence.add(event.getStandardId()); 41 } 42 stringSequence.add(endSymbol); 43 44 trainStringTrie(stringSequence); 45 } 46 } 47 48 private void trainStringTrie(List<String> sequence) { 49 knownSymbols = new LinkedHashSet<String>(); 50 IncompleteMemory<String> latestActions = new IncompleteMemory<String>(maxOrder); 51 int i=0; 52 for(String currentAction : sequence) { 53 String currentId = currentAction; 54 latestActions.add(currentId); 55 knownSymbols.add(currentId); 56 i++; 57 if( i>=maxOrder ) { 43 58 trie.add(latestActions.getLast(maxOrder)); 44 59 } 45 60 } 46 } 47 48 public void printRandomWalk(Random r) { 61 int sequenceLength = sequence.size(); 62 for( int j=maxOrder-1 ; j>0 ; j-- ) { 63 trie.add(sequence.subList(sequenceLength-j, sequenceLength)); 64 } 65 } 66 67 public void testStuff() { 68 // basically an inline unit test without assertions but manual observation 69 List<String> list = new ArrayList<String>(); 70 list.add(initialSymbol); 71 list.add("a"); 72 list.add("b"); 73 list.add("r"); 74 list.add("a"); 75 list.add("c"); 76 list.add("a"); 77 list.add("d"); 78 list.add("a"); 79 list.add("b"); 80 list.add("r"); 81 list.add("a"); 82 list.add(endSymbol); 83 84 PredictionByPartialMatch model = new PredictionByPartialMatch(); 85 model.trie = new Trie<String>(); 86 model.trainStringTrie(list); 87 model.trie.display(); 88 Console.println("------------------------"); 89 model.randomSequence();/* 90 Console.println("------------------------"); 91 model.randomSequence(); 92 Console.println("------------------------"); 93 model.randomSequence(); 94 Console.println("------------------------");*/ 95 96 List<String> context = new ArrayList<String>(); 97 String symbol = "a"; 98 // expected: 5 99 Console.traceln(""+model.trie.getCount(context, symbol)); 100 101 // expected: 0 102 context.add("b"); 103 Console.traceln(""+model.trie.getCount(context, symbol)); 104 105 // expected: 2 106 context.add("r"); 107 Console.traceln(""+model.trie.getCount(context, symbol)); 108 109 // exptected: [b, r] 110 context = new ArrayList<String>(); 111 context.add("a"); 112 context.add("b"); 113 context.add("r"); 114 Console.traceln(model.trie.getContextSuffix(context).toString()); 115 116 // exptected: [] 117 context = new ArrayList<String>(); 118 context.add("e"); 119 Console.traceln(model.trie.getContextSuffix(context).toString()); 120 121 // exptected: {a, b, c, d, r} 122 context = new ArrayList<String>(); 123 Console.traceln(model.trie.getFollowingSymbols(context).toString()); 124 125 // exptected: {b, c, d} 126 context = new ArrayList<String>(); 127 context.add("a"); 128 Console.traceln(model.trie.getFollowingSymbols(context).toString()); 129 130 // exptected: [] 131 context = new ArrayList<String>(); 132 context.add("a"); 133 context.add("b"); 134 context.add("r"); 135 Console.traceln(model.trie.getFollowingSymbols(context).toString()); 136 } 137 138 // TODO needs to be changed from String to <? extends Event> 139 public List<String> randomSequence() { 140 List<String> sequence = new LinkedList<String>(); 141 49 142 IncompleteMemory<String> context = new IncompleteMemory<String>(maxOrder-1); 50 51 143 context.add(initialSymbol); 144 sequence.add(initialSymbol); 52 145 53 146 String currentState = initialSymbol; … … 61 154 probSum += getProbability(currentContext, symbol); 62 155 if( probSum>=randVal ) { 63 currentContext.add(symbol); 156 context.add(symbol); 157 currentState = symbol; 158 sequence.add(currentState); 159 break; 160 } 161 } 162 } 163 return sequence; 164 } 165 166 /*public void printRandomWalk(Random r) { 167 IncompleteMemory<String> context = new IncompleteMemory<String>(maxOrder-1); 168 169 context.add(initialSymbol); 170 171 String currentState = initialSymbol; 172 173 Console.println(currentState); 174 while(!endSymbol.equals(currentState)) { 175 double randVal = r.nextDouble(); 176 double probSum = 0.0; 177 List<String> currentContext = context.getLast(maxOrder); 178 // DEBUG // 179 Console.traceln("Context: " + currentContext.toString()); 180 double tmpSum = 0.0d; 181 for( String symbol : knownSymbols ) { 182 double prob = getProbability(currentContext, symbol); 183 tmpSum += prob; 184 Console.traceln(symbol + ": " + prob); 185 } 186 Console.traceln("Sum: " + tmpSum); 187 // DEBUG-END // 188 for( String symbol : knownSymbols ) { 189 probSum += getProbability(currentContext, symbol); 190 if( probSum>=randVal-0.3 ) { 191 context.add(symbol); 64 192 currentState = symbol; 65 193 Console.println(currentState); … … 68 196 } 69 197 } 70 } 71 198 }*/ 199 200 private double getProbability(List<String> context, String symbol) { 201 // FIXME needs exception handling for unknown symbols 202 // if the symbol is not contained in the trie, context.remove(0) will fail 203 double result = 0.0d; 204 double resultCurrentContex = 0.0d; 205 double resultShorterContex = 0.0d; 206 207 List<String> contextCopy = new LinkedList<String>(context); // defensive copy 208 209 210 List<String> followers = trie.getFollowingSymbols(contextCopy); // \Sigma' 211 int sumCountFollowers = 0; // N(s\sigma') 212 for( String follower : followers ) { 213 sumCountFollowers += trie.getCount(contextCopy, follower); 214 } 215 216 int countSymbol = trie.getCount(contextCopy, symbol); // N(s\sigma) 217 if( contextCopy.size()==0 ) { 218 resultCurrentContex = ((double) countSymbol) / sumCountFollowers; 219 } else { 220 resultCurrentContex = ((double) countSymbol / sumCountFollowers)*(1-probEscape); 221 contextCopy.remove(0); 222 double probSuffix = getProbability(contextCopy, symbol); 223 if( followers.size()==0 ) { 224 resultShorterContex = probSuffix; 225 } else { 226 resultShorterContex = probEscape*probSuffix; 227 } 228 } 229 result = resultCurrentContex+resultShorterContex; 230 231 return result; 232 } 233 234 /* 72 235 private double getProbability(List<String> context, String symbol) { 73 236 double result = 0.0; … … 75 238 List<String> contextSuffix = trie.getContextSuffix(context); 76 239 if( contextSuffix.isEmpty() ) { 77 result = 1.0d / knownSymbols.size(); 240 // unobserved context! everything is possible... assuming identical distribution 241 result = 1.0d / knownSymbols.size(); // why 1.0 and not N(symbol) 78 242 } else { 79 243 countContextSymbol = trie.getCount(contextSuffix, symbol); … … 85 249 86 250 if( followers.isEmpty() ) { 87 throw new AssertionError("Invalid return value of getContextSuffix!");251 throw new AssertionError("Invalid return value of trie.getContextSuffix()!"); 88 252 } 89 253 if( countContextSymbol!=0 ) { … … 91 255 } else { // escape 92 256 double probEscape = ((double) followers.size()) / (followers.size()+countContextFollowers); 93 contextSuffix.remove(0); 257 contextSuffix.remove(0); 94 258 double probSuffix = getProbability(contextSuffix, symbol); 95 259 result = probEscape*probSuffix; … … 98 262 99 263 return result; 100 } 264 }*/ 101 265 102 266 @Override -
trunk/EventBenchCore/src/de/ugoe/cs/eventbench/ppm/Trie.java
r1 r5 1 1 package de.ugoe.cs.eventbench.ppm; 2 2 3 import java.awt.Dimension; 4 import java.awt.Rectangle; 5 import java.awt.Shape; 3 6 import java.util.LinkedList; 4 7 import java.util.List; 5 8 9 import javax.swing.JFrame; 10 11 import org.apache.commons.collections15.Transformer; 12 13 import edu.uci.ics.jung.algorithms.layout.Layout; 14 import edu.uci.ics.jung.algorithms.layout.TreeLayout; 15 import edu.uci.ics.jung.graph.DelegateTree; 16 import edu.uci.ics.jung.graph.Tree; 17 import edu.uci.ics.jung.visualization.BasicVisualizationServer; 18 import edu.uci.ics.jung.visualization.decorators.ToStringLabeller; 19 import edu.uci.ics.jung.visualization.renderers.Renderer.VertexLabel.Position; 20 6 21 public class Trie<T> { 7 22 23 // Children of the Trie root 24 // should contain counts of all elements 8 25 private List<TrieNode<T>> children = new LinkedList<TrieNode<T>>(); 9 26 … … 11 28 public void add(List<T> subsequence) { 12 29 if( !subsequence.isEmpty() ) { 13 subsequence = new LinkedList<T>(subsequence); // copy list!30 subsequence = new LinkedList<T>(subsequence); // defensive copy! 14 31 T firstSymbol = subsequence.get(0); 15 32 getChildCreate(firstSymbol).add(subsequence); … … 37 54 } 38 55 56 // get the count of "sequence" 39 57 public int getCount(List<T> sequence) { 40 58 int count = 0; … … 46 64 } 47 65 66 // get the count of "sequence,follower" 48 67 public int getCount(List<T> sequence, T follower) { 49 68 List<T> tmpSequence = new LinkedList<T>(sequence); … … 54 73 55 74 public TrieNode<T> find(List<T> sequence) { 75 List<T> sequenceCopy = new LinkedList<T>(sequence); 56 76 TrieNode<T> result = null; 57 if( !sequence .isEmpty() ) {58 TrieNode<T> node = getChild(sequence .get(0));77 if( !sequenceCopy.isEmpty() ) { 78 TrieNode<T> node = getChild(sequenceCopy.get(0)); 59 79 if( node!=null ) { 60 result = node.find(sequence); 80 sequenceCopy.remove(0); 81 result = node.find(sequenceCopy); 61 82 } 62 83 } … … 64 85 } 65 86 87 // returns all symbols that follow the defined sequence 66 88 public List<T> getFollowingSymbols(List<T> sequence) { 67 List<T> result = null; 68 TrieNode<T> node = find(sequence); 69 if( node!=null ) { 70 result = node.getFollowingSymbols(); 89 List<T> result = new LinkedList<T>(); 90 if( sequence==null || sequence.isEmpty() ) { 91 for( TrieNode<T> child : children ) { 92 result.add(child.getSymbol()); 93 } 94 } else { 95 TrieNode<T> node = find(sequence); 96 if( node!=null ) { 97 result = node.getFollowingSymbols(); 98 } 71 99 } 72 100 return result; 73 101 } 74 102 103 // longest suffix of context, that is contained in the tree and whose children are leaves 75 104 public List<T> getContextSuffix(List<T> context) { 76 List<T> contextSuffix = new LinkedList<T>(context); 105 List<T> contextSuffix = new LinkedList<T>(context); // defensive copy 77 106 boolean suffixFound = false; 78 107 … … 87 116 } 88 117 } 89 contextSuffix.remove(0); 118 if( !suffixFound ) { 119 contextSuffix.remove(0); 120 } 90 121 } 91 122 } 92 123 93 124 return contextSuffix; 125 } 126 127 128 static public class Edge{} 129 130 static public class TrieVertex { 131 private String id; 132 protected TrieVertex(String id) { 133 this.id = id; 134 } 135 public String toString() { 136 return id; 137 } 138 } 139 140 private Tree<TrieVertex, Edge> getGraph() { 141 DelegateTree<TrieVertex, Edge> graph = new DelegateTree<TrieVertex, Edge>(); 142 143 TrieVertex root = new TrieVertex("root"); 144 graph.addVertex(root); 145 146 for( TrieNode<T> node : children ) { 147 node.getGraph(root, graph); 148 } 149 150 return graph; 151 } 152 153 public void display() { 154 Tree<TrieVertex, Edge> graph = this.getGraph(); 155 Layout<TrieVertex, Edge> layout = new TreeLayout<TrieVertex, Edge>(graph, 60); 156 // The BasicVisualizationServer<V,E> is parameterized by the edge types 157 BasicVisualizationServer<TrieVertex,Edge> vv = 158 new BasicVisualizationServer<TrieVertex,Edge>(layout); 159 vv.setPreferredSize(new Dimension(1100,850)); //Sets the viewing area size 160 161 162 final Rectangle rect = new Rectangle(40, 20); 163 164 Transformer<TrieVertex, Shape> vertexShapeTransformer = 165 new Transformer<TrieVertex, Shape>() { 166 public Shape transform(TrieVertex s) { 167 return rect; 168 } 169 }; 170 vv.getRenderer().getVertexLabelRenderer().setPosition(Position.CNTR); 171 vv.getRenderContext().setVertexShapeTransformer(vertexShapeTransformer); 172 vv.getRenderContext().setVertexLabelTransformer(new ToStringLabeller<TrieVertex>()); 173 174 JFrame frame = new JFrame("Trie"); 175 frame.setDefaultCloseOperation(JFrame.DISPOSE_ON_CLOSE); 176 frame.getContentPane().add(vv); 177 frame.pack(); 178 frame.setVisible(true); 94 179 } 95 180 -
trunk/EventBenchCore/src/de/ugoe/cs/eventbench/ppm/TrieNode.java
r1 r5 5 5 import java.util.List; 6 6 7 import de.ugoe.cs.eventbench.ppm.Trie.Edge; 8 import de.ugoe.cs.eventbench.ppm.Trie.TrieVertex; 7 9 import de.ugoe.cs.util.StringTools; 10 import edu.uci.ics.jung.graph.DelegateTree; 8 11 9 12 … … 80 83 } 81 84 85 // returns all symbols that follow this node 82 86 public List<T> getFollowingSymbols() { 83 87 List<T> followingSymbols = new LinkedList<T>(); … … 97 101 } 98 102 103 public void getGraph(TrieVertex parent, DelegateTree<TrieVertex, Edge> graph) { 104 TrieVertex vertex = new TrieVertex(getSymbol().toString()+"#"+getCount()); 105 graph.addChild( new Edge() , parent, vertex ); 106 for( TrieNode<T> node : children ) { 107 node.getGraph(vertex, graph); 108 } 109 } 110 99 111 }
Note: See TracChangeset
for help on using the changeset viewer.
