Mercurial Hosting > traffic-intelligence
comparison python/utils.py @ 322:28661c5887d3
Corrected a major bug for LCSS
Added functions to test all alignments when computing the LCSS with a finite delta
| author | Nicolas Saunier <nicolas.saunier@polymtl.ca> |
|---|---|
| date | Tue, 07 May 2013 18:43:40 +0200 |
| parents | 6c068047edbf |
| children | efd4dd4665ac |
comparison
equal
deleted
inserted
replaced
| 321:a5e40bd04cf4 | 322:28661c5887d3 |
|---|---|
| 177 def LCSS(l1, l2, threshold, distance, delta = float('inf')): | 177 def LCSS(l1, l2, threshold, distance, delta = float('inf')): |
| 178 '''returns the longest common subsequence similarity | 178 '''returns the longest common subsequence similarity |
| 179 based on the threshold on distance between two elements of lists l1, l2 | 179 based on the threshold on distance between two elements of lists l1, l2 |
| 180 ''' | 180 ''' |
| 181 from numpy import zeros, int as npint | 181 from numpy import zeros, int as npint |
| 182 m = len(l1) | 182 n1 = len(l1) |
| 183 n = len(l2) | 183 n2 = len(l2) |
| 184 similarity = zeros((m+1,n+1), dtype = npint) | 184 similarity = zeros((n1+1,n2+1), dtype = npint) |
| 185 for i in xrange(1,m+1): | 185 for i in xrange(1,n1+1): |
| 186 for j in xrange(max(1,i-delta),min(n+1,i+delta)): | 186 for j in xrange(max(1,i-delta),min(n2+1,i+delta+1)): |
| 187 if distance(l1[i-1], l2[j-1])<=threshold: | 187 if distance(l1[i-1], l2[j-1])<=threshold: |
| 188 similarity[i][j] = similarity[i-1][j-1]+1 | 188 similarity[i][j] = similarity[i-1][j-1]+1 |
| 189 else: | 189 else: |
| 190 similarity[i][j] = max(similarity[i-1][j], similarity[i][j-1]) | 190 similarity[i][j] = max(similarity[i-1][j], similarity[i][j-1]) |
| 191 return similarity[-1][-1] | 191 return max(max(similarity[:,-1]), max(similarity[-1,:])) |
| 192 | |
| 193 def normalizedLCSS(l1, l2, threshold, distance, delta = float('inf'), lengthMethod = min): | |
| 194 ''' compute the normalized LCSS | |
| 195 ie, the LCSS divided by the min or mean of the indicator lengths (using lengthMethod) | |
| 196 lengthMethod = lambda x,y:float(x,y)/2''' | |
| 197 return float(LCSS(l1, l2, threshold, distance, delta))/lengthMethod(len(l1), len(l2)) | |
| 198 | |
| 199 def DLCSS(l1, l2, threshold, distance, delta = float('inf'), lengthMethod = min): | |
| 200 ''' compute the LCSS distance''' | |
| 201 return 1-normalizedLCSS(l1, l2, threshold, distance, delta, lengthMethod) | |
| 202 | |
| 203 def alignedLCSS(_l1, _l2, threshold, distance, delta): | |
| 204 '''returns the best matching if using a finite delta by shiftinig the series alignments''' | |
| 205 if len(_l2) < len(_l1): # l1 is the shortest | |
| 206 l1 = _l2 | |
| 207 l2 = _l1 | |
| 208 else: | |
| 209 l1 = _l1 | |
| 210 l2 = _l2 | |
| 211 n1 = len(l1) | |
| 212 n2 = len(l2) | |
| 213 # for i in xrange(delta, n1+n2-delta): # i is the alignment of the end of l1 in l2 | |
| 214 # print l1[min(-i-1,n1):] # min(n1+n2-i,n1) | |
| 215 # print l2[max(0,i-n1):] | |
| 216 # print LCSS(l1[min(-i-1,n1):], l2[max(0,i-n1):], threshold, distance, delta) | |
| 217 lcss = [LCSS(l1[min(-i-1,n1):], l2[max(0,i-n1):], threshold, distance, delta) for i in xrange(delta, n1+n2-delta)] | |
| 218 return max(lcss) | |
| 219 | |
| 220 def normalizedAlignedLCSS(l1, l2, threshold, distance, delta, lengthMethod = min): | |
| 221 return float(alignedLCSS(l1, l2, threshold, distance, delta))/lengthMethod(len(l1), len(l2)) | |
| 222 | |
| 223 def alignedDLCSS(l1, l2, threshold, distance, delta, lengthMethod = min): | |
| 224 return 1-normalizedAlignedLCSS(l1, l2, threshold, distance, delta, lengthMethod) | |
| 192 | 225 |
| 193 def framesToTime(nFrames, frameRate, initialTime = (0.,0.,0.)): | 226 def framesToTime(nFrames, frameRate, initialTime = (0.,0.,0.)): |
| 194 'returns hour, minutes and seconds' | 227 'returns hour, minutes and seconds' |
| 195 from math import floor | 228 from math import floor |
| 196 from datetime import time | 229 from datetime import time |