Mercurial Hosting > traffic-intelligence

comparison python/utils.py @ 366:90bdabc06e9f

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
updated LCSS to be more generic with a single similarity function
author Nicolas Saunier <nicolas.saunier@polymtl.ca>
date Mon, 15 Jul 2013 12:12:47 -0400
parents a50a69e04c2a
children 2db4e76599a1
comparison
equal deleted inserted replaced
365:22ddb8f85495 366:90bdabc06e9f
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 # maths section 141 # sequence section
142 ######################### 142 #########################
143 143
144 def LCSS(l1, l2, threshold, distance, delta = float('inf')): 144 def LCSS(l1, l2, similarityFunc, delta = float('inf')):
145 '''returns the longest common subsequence similarity 145 '''returns the longest common subsequence similarity
146 based on the threshold on distance between two elements of lists l1, l2 146 based on the threshold on distance between two elements of lists l1, l2
147 similarityFunc returns True or False whether the two points are considered similar
148
149 eg distance(p1, p2) < epsilon
147 ''' 150 '''
148 from numpy import zeros, int as npint 151 from numpy import zeros, int as npint
149 n1 = len(l1) 152 n1 = len(l1)
150 n2 = len(l2) 153 n2 = len(l2)
151 similarity = zeros((n1+1,n2+1), dtype = npint) 154 similarity = zeros((n1+1,n2+1), dtype = npint)
152 for i in xrange(1,n1+1): 155 for i in xrange(1,n1+1):
153 for j in xrange(max(1,i-delta),min(n2+1,i+delta+1)): 156 for j in xrange(max(1,i-delta),min(n2+1,i+delta+1)):
154 if distance(l1[i-1], l2[j-1])<=threshold: 157 if similarityFunc(l1[i-1], l2[j-1]):
155 similarity[i][j] = similarity[i-1][j-1]+1 158 similarity[i][j] = similarity[i-1][j-1]+1
156 else: 159 else:
157 similarity[i][j] = max(similarity[i-1][j], similarity[i][j-1]) 160 similarity[i][j] = max(similarity[i-1][j], similarity[i][j-1])
158 return max(max(similarity[:,-1]), max(similarity[-1,:])) 161 return max(max(similarity[:,-1]), max(similarity[-1,:]))
159 162
160 def normalizedLCSS(l1, l2, threshold, distance, delta = float('inf'), lengthMethod = min): 163 def normalizedLCSS(l1, l2, similarityFunc, delta = float('inf'), lengthMethod = min):
161 ''' compute the normalized LCSS 164 ''' compute the normalized LCSS
162 ie, the LCSS divided by the min or mean of the indicator lengths (using lengthMethod) 165 ie, the LCSS divided by the min or mean of the indicator lengths (using lengthMethod)
163 lengthMethod = lambda x,y:float(x,y)/2''' 166 lengthMethod = lambda x,y:float(x,y)/2'''
164 return float(LCSS(l1, l2, threshold, distance, delta))/lengthMethod(len(l1), len(l2)) 167 return float(LCSS(l1, l2, similarityFunc, delta))/lengthMethod(len(l1), len(l2))
165 168
166 def DLCSS(l1, l2, threshold, distance, delta = float('inf'), lengthMethod = min): 169 def DLCSS(l1, l2, similarityFunc, delta = float('inf'), lengthMethod = min):
167 ''' compute the LCSS distance''' 170 ''' compute the LCSS distance'''
168 return 1-normalizedLCSS(l1, l2, threshold, distance, delta, lengthMethod) 171 return 1-normalizedLCSS(l1, l2, similarityFunc, delta, lengthMethod)
169 172
170 def alignedLCSS(_l1, _l2, threshold, distance, delta): 173 def alignedLCSS(_l1, _l2, similarityFunc, delta):
171 '''returns the best matching if using a finite delta by shiftinig the series alignments''' 174 '''returns the best matching if using a finite delta by shiftinig the series alignments'''
172 if len(_l2) < len(_l1): # l1 is the shortest 175 if len(_l2) < len(_l1): # l1 is the shortest
173 l1 = _l2 176 l1 = _l2
174 l2 = _l1 177 l2 = _l1
175 else: 178 else:
178 n1 = len(l1) 181 n1 = len(l1)
179 n2 = len(l2) 182 n2 = len(l2)
180 # for i in xrange(min(delta,n1), max(n1+n2-delta, n2+1)): # i is the alignment of the end of l1 in l2 183 # for i in xrange(min(delta,n1), max(n1+n2-delta, n2+1)): # i is the alignment of the end of l1 in l2
181 # print l1[min(-i-1,n1):] # min(n1+n2-i,n1) 184 # print l1[min(-i-1,n1):] # min(n1+n2-i,n1)
182 # print l2[max(0,i-n1):] 185 # print l2[max(0,i-n1):]
183 # print LCSS(l1[min(-i-1,n1):], l2[max(0,i-n1):], threshold, distance, delta) 186 # print LCSS(l1[min(-i-1,n1):], l2[max(0,i-n1):], similarityFunc, delta)
184 lcss = [LCSS(l1[min(-i-1,n1):], l2[max(0,i-n1):], threshold, distance, delta) for i in xrange(min(delta,n1), max(n1+n2-delta, n2+1))] 187 lcss = [LCSS(l1[min(-i-1,n1):], l2[max(0,i-n1):], similarityFunc, delta) for i in xrange(min(delta,n1), max(n1+n2-delta, n2+1))]
185 return max(lcss) 188 return max(lcss)
186 189
187 def normalizedAlignedLCSS(l1, l2, threshold, distance, delta, lengthMethod = min): 190 def normalizedAlignedLCSS(l1, l2, similarityFunc, delta, lengthMethod = min):
188 return float(alignedLCSS(l1, l2, threshold, distance, delta))/lengthMethod(len(l1), len(l2)) 191 return float(alignedLCSS(l1, l2, similarityFunc, delta))/lengthMethod(len(l1), len(l2))
189 192
190 def alignedDLCSS(l1, l2, threshold, distance, delta, lengthMethod = min): 193 def alignedDLCSS(l1, l2, similarityFunc, delta, lengthMethod = min):
191 return 1-normalizedAlignedLCSS(l1, l2, threshold, distance, delta, lengthMethod) 194 return 1-normalizedAlignedLCSS(l1, l2, similarityFunc, delta, lengthMethod)
195
196 #########################
197 # maths section
198 #########################
192 199
193 def framesToTime(nFrames, frameRate, initialTime = (0.,0.,0.)): 200 def framesToTime(nFrames, frameRate, initialTime = (0.,0.,0.)):
194 'returns hour, minutes and seconds' 201 'returns hour, minutes and seconds'
195 from math import floor 202 from math import floor
196 from datetime import time 203 from datetime import time