Mercurial Hosting > traffic-intelligence

comparison python/utils.py @ 370:97e8fa0ee9a1

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
work in progress for complete alignment
author Nicolas Saunier <nicolas.saunier@polymtl.ca>
date Mon, 15 Jul 2013 18:18:44 -0400
parents 027e254f0b53
children 924e38c9f70e
comparison
equal deleted inserted replaced
369:027e254f0b53 370:97e8fa0ee9a1
136 for i in xrange(len(ref[0])): 136 for i in xrange(len(ref[0])):
137 print('{0}-{1} & {2:0.3} & {3:0.3} \\\\'.format(self.categories[i],self.categories[i+1],ref[1][i], ref[0][i])) 137 print('{0}-{1} & {2:0.3} & {3:0.3} \\\\'.format(self.categories[i],self.categories[i+1],ref[1][i], ref[0][i]))
138 138
139 139
140 ######################### 140 #########################
141 # sequence section
142 #########################
143
144 class LCSS:
145 '''Class that keeps the LCSS parameters
146 and puts together the various computations'''
147 def __init__(self, similarityFunc, delta = float('inf'), aligned = False, lengthFunc = min):
148 self.similarityFunc = similarityFunc
149 self.aligned = aligned
150 self.delta = delta
151 self.lengthFunc = lengthFunc
152
153 def similarities(self, l1, l2):
154 from numpy import zeros, int as npint
155 n1 = len(l1)
156 n2 = len(l2)
157 self.similarityTable = zeros((n1+1,n2+1), dtype = npint)
158 for i in xrange(1,n1+1):
159 for j in xrange(max(1,i-self.delta),min(n2+1,i+self.delta+1)):
160 if self.similarityFunc(l1[i-1], l2[j-1]):
161 self.similarityTable[i,j] = self.similarityTable[i-1,j-1]+1
162 else:
163 self.similarityTable[i,j] = max(self.similarityTable[i-1,j], self.similarityTable[i,j-1])
164
165 def subSequence(self, i, j):
166 '''Returns the subsequence of two sequences
167 http://en.wikipedia.org/wiki/Longest_common_subsequence_problem'''
168 if i == 0 or j == 0:
169 return []
170 elif self.similarityTable[i][j] == self.similarityTable[i][j-1]:
171 return self.subSequence(i, j-1)
172 elif self.similarityTable[i][j] == self.similarityTable[i-1][j]:
173 return self.subSequence(i-1, j)
174 else:
175 return self.subSequence(i-1, j-1) + [(i-1,j-1)]
176
177 def computeLCSS(self, l1, l2, computeSubSequence = False):
178 '''returns the longest common subsequence similarity
179 based on the threshold on distance between two elements of lists l1, l2
180 similarityFunc returns True or False whether the two points are considered similar
181
182 eg distance(p1, p2) < epsilon
183 '''
184 from numpy import argmax
185 self.similarities(l1, l2)
186 imax = argmax(self.similarityTable[:,-1])
187 jmax = argmax(self.similarityTable[-1,:])
188 if computeSubSequence:
189 if self.similarityTable[imax, -1] > self.similarityTable[-1, jmax]:
190 lcss = self.similarityTable[imax, -1]
191 self.subSequenceIndices = self.subSequence(imax, len(l2))
192 else:
193 lcss = self.similarityTable[imax, -1]
194 self.subSequenceIndices = self.subSequence(len(l1), jmax)
195 return lcss
196 else:
197 return max(self.similarityTable[imax, -1], self.similarityTable[-1, jmax])
198
199 def compute(self, _l1, _l2, computeSubSequence = False):
200 '''returns the best matching if using a finite delta by shiftinig the series alignments'''
201 if self.aligned:
202 if len(_l2) < len(_l1): # l1 is the shortest
203 l1 = _l2
204 l2 = _l1
205 else:
206 l1 = _l1
207 l2 = _l2
208 n1 = len(l1)
209 n2 = len(l2)
210 # for i in xrange(min(delta,n1), max(n1+n2-delta, n2+1)): # i is the alignment of the end of l1 in l2
211 # print l1[min(-i-1,n1):] # min(n1+n2-i,n1)
212 # print l2[max(0,i-n1):]
213 # print LCSS(l1[min(-i-1,n1):], l2[max(0,i-n1):], similarityFunc, delta)
214 lcss = [self.computeLCSS(l1[min(-i-1,n1):], l2[max(0,i-n1):]) for i in xrange(min(self.delta,n1), max(n1+n2-self.delta, n2+1))]
215 return max(lcss)
216 else:
217 return self.computeLCSS(_l1, _l2, computeSubSequence)
218
219 def get(self, l1, l2, computeSubSequence = False):
220 '''get methods are to be shadowed in child classes '''
221 return self.compute(l1, l2, computeSubSequence)
222
223 def computeAlignement(self):
224 from numpy import mean
225 return mean([j-i for i,j in self.subSequenceIndices])
226
227 def computeNormalized(self, l1, l2):
228 ''' compute the normalized LCSS
229 ie, the LCSS divided by the min or mean of the indicator lengths (using lengthFunc)
230 lengthFunc = lambda x,y:float(x,y)/2'''
231 return float(self.compute(l1, l2))/self.lengthFunc(len(l1), len(l2))
232
233 def getNormalized(self, l1, l2):
234 return self.computeNormalized(l1, l2)
235
236 def computeDistance(self, l1, l2):
237 ''' compute the LCSS distance'''
238 return 1-self.computeNormalized(l1, l2)
239
240 def getDistance(self, l1, l2):
241 return self.computeDistance(l1, l2)
242
243 #########################
244 # maths section 141 # maths section
245 ######################### 142 #########################
143
144 def argMaxDict(d):
145 return max(d.iterkeys(), key=(lambda key: d[key]))
246 146
247 def framesToTime(nFrames, frameRate, initialTime = (0.,0.,0.)): 147 def framesToTime(nFrames, frameRate, initialTime = (0.,0.,0.)):
248 'returns hour, minutes and seconds' 148 'returns hour, minutes and seconds'
249 from math import floor 149 from math import floor
250 from datetime import time 150 from datetime import time
303 xx = arange(min(x), max(x),(max(x)-min(x))/1000) 203 xx = arange(min(x), max(x),(max(x)-min(x))/1000)
304 plot(xx, [poly(z) for z in xx]) 204 plot(xx, [poly(z) for z in xx])
305 return coef 205 return coef
306 206
307 ######################### 207 #########################
208 # sequence section
209 #########################
210
211 class LCSS:
212 '''Class that keeps the LCSS parameters
213 and puts together the various computations'''
214 def __init__(self, similarityFunc, delta = float('inf'), aligned = False, lengthFunc = min):
215 self.similarityFunc = similarityFunc
216 self.aligned = aligned
217 self.delta = delta
218 self.lengthFunc = lengthFunc
219 self.alignmentShift = 0
220
221 def similarities(self, l1, l2):
222 from numpy import zeros, int as npint
223 n1 = len(l1)
224 n2 = len(l2)
225 self.similarityTable = zeros((n1+1,n2+1), dtype = npint)
226 for i in xrange(1,n1+1):
227 for j in xrange(max(1,i-self.delta),min(n2+1,i+self.delta+1)):
228 if self.similarityFunc(l1[i-1], l2[j-1]):
229 self.similarityTable[i,j] = self.similarityTable[i-1,j-1]+1
230 else:
231 self.similarityTable[i,j] = max(self.similarityTable[i-1,j], self.similarityTable[i,j-1])
232
233 def subSequence(self, i, j):
234 '''Returns the subsequence of two sequences
235 http://en.wikipedia.org/wiki/Longest_common_subsequence_problem'''
236 if i == 0 or j == 0:
237 return []
238 elif self.similarityTable[i][j] == self.similarityTable[i][j-1]:
239 return self.subSequence(i, j-1)
240 elif self.similarityTable[i][j] == self.similarityTable[i-1][j]:
241 return self.subSequence(i-1, j)
242 else:
243 return self.subSequence(i-1, j-1) + [(i-1,j-1)]
244
245 def computeLCSS(self, l1, l2, computeSubSequence = False):
246 '''returns the longest common subsequence similarity
247 based on the threshold on distance between two elements of lists l1, l2
248 similarityFunc returns True or False whether the two points are considered similar
249
250 eg distance(p1, p2) < epsilon
251 '''
252 from numpy import argmax
253 self.similarities(l1, l2)
254 imax = argmax(self.similarityTable[:,-1])
255 jmax = argmax(self.similarityTable[-1,:])
256 if computeSubSequence:
257 if self.similarityTable[imax, -1] > self.similarityTable[-1, jmax]:
258 self.similarityTable = self.similarityTable[:imax+1, :]
259 self.subSequenceIndices = self.subSequence(imax, len(l2))
260 else:
261 self.similarityTable = self.similarityTable[:, :jmax+1]
262 self.subSequenceIndices = self.subSequence(len(l1), jmax)
263 return self.similarityTable[-1,-1]
264 else:
265 return max(self.similarityTable[imax, -1], self.similarityTable[-1, jmax])
266
267 def _compute(self, _l1, _l2, computeSubSequence = False):
268 '''returns the best matching if using a finite delta by shiftinig the series alignments'''
269 if self.aligned:
270 from numpy import argmax
271 if len(_l2) < len(_l1): # l1 is the shortest
272 l1 = _l2
273 l2 = _l1
274 else:
275 l1 = _l1
276 l2 = _l2
277 n1 = len(l1)
278 n2 = len(l2)
279 # for i in xrange(min(delta,n1), max(n1+n2-delta, n2+1)): # i is the alignment of the end of l1 in l2
280 # print l1[min(-i-1,n1):] # min(n1+n2-i,n1)
281 # print l2[max(0,i-n1):]
282 # print LCSS(l1[min(-i-1,n1):], l2[max(0,i-n1):], similarityFunc, delta)
283 lcssValues = {}
284 similarityTables = {}
285 for i in xrange(min(self.delta,n1), max(n1+n2-self.delta, n2+1), max(1,self.delta)):
286 print l1[min(-i-1,n1):] # min(n1+n2-i,n1)
287 print l2[max(0,i-n1):]
288 lcssValues[i] = self.computeLCSS(l1[min(-i-1,n1):], l2[max(0,i-n1):])
289 print i, lcssValues[i]
290 similarityTables[i] = self.similarityTable
291 imax = argMaxDict(lcssValues)
292 self.similarityTable = similarityTables[imax]
293 self.subSequenceIndices = self.subSequence(self.similarityTable.shape[0]-1, self.similarityTable.shape[1]-1)
294 self.alignmentShift = max(0,imax-n1)-min(-imax-1,n1)
295 return lcssValues[imax]
296 else:
297 return self.computeLCSS(_l1, _l2, computeSubSequence)
298
299 def compute(self, l1, l2, computeSubSequence = False):
300 '''get methods are to be shadowed in child classes '''
301 return self._compute(l1, l2, computeSubSequence)
302
303 def computeAlignement(self):
304 from numpy import mean
305 return mean([j-i for i,j in self.subSequenceIndices])+self.alignmentShift
306
307 def _computeNormalized(self, l1, l2):
308 ''' compute the normalized LCSS
309 ie, the LCSS divided by the min or mean of the indicator lengths (using lengthFunc)
310 lengthFunc = lambda x,y:float(x,y)/2'''
311 return float(self.compute(l1, l2))/self.lengthFunc(len(l1), len(l2))
312
313 def computeNormalized(self, l1, l2):
314 return self._computeNormalized(l1, l2)
315
316 def _computeDistance(self, l1, l2):
317 ''' compute the LCSS distance'''
318 return 1-self.computeNormalized(l1, l2)
319
320 def computeDistance(self, l1, l2):
321 return self._computeDistance(l1, l2)
322
323 #########################
308 # plotting section 324 # plotting section
309 ######################### 325 #########################
310 326
311 def plotPolygon(poly, options = ''): 327 def plotPolygon(poly, options = ''):
312 'Plots shapely polygon poly' 328 'Plots shapely polygon poly'