Mercurial Hosting > traffic-intelligence
changeset 366:90bdabc06e9f
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 | 22ddb8f85495 |
children | d44eba0db517 |
files | python/tests/utils.txt python/utils.py |
diffstat | 2 files changed, 43 insertions(+), 28 deletions(-) [+] |
line wrap: on
line diff
--- a/python/tests/utils.txt Fri Jul 12 11:28:47 2013 -0400 +++ b/python/tests/utils.txt Mon Jul 15 12:12:47 2013 -0400 @@ -44,29 +44,37 @@ >>> stepPlot([3, 5, 7, 8], 1, 10, 0) ([1, 3, 3, 5, 5, 7, 7, 8, 8, 10], [0, 0, 1, 1, 2, 2, 3, 3, 4, 4]) ->>> LCSS(range(5), range(5), 0.1, lambda x,y:abs(x-y)) +>>> LCSS(range(5), range(5), lambda x,y:(abs(x-y) <= 0.1)) 5 ->>> LCSS(range(1,5), range(5), 0.1, lambda x,y:abs(x-y)) +>>> LCSS(range(1,5), range(5), lambda x,y:(abs(x-y) <= 0.1)) 4 ->>> LCSS(range(5,10), range(5), 0.1, lambda x,y:abs(x-y)) +>>> LCSS(range(5,10), range(5), lambda x,y:(abs(x-y) <= 0.1)) 0 ->>> LCSS(range(5), range(10), 0.1, lambda x,y:abs(x-y)) +>>> LCSS(range(5), range(10), lambda x,y:(abs(x-y) <= 0.1)) 5 ->>> LCSS(range(5), range(10), 0.1, lambda x,y:abs(x-y), 2) +>>> LCSS(range(5), range(10), lambda x,y:(abs(x-y) <= 0.1), 2) 5 - ->>> alignedLCSS(range(5), range(5), 0.1, lambda x,y:abs(x-y), 2) -5 ->>> alignedLCSS(range(1,5), range(5), 0.1, lambda x,y:abs(x-y), 2) +>>> LCSS(['a','b','c'], ['a','b','c', 'd'], lambda x,y: x == y) +3 +>>> LCSS(['a','b','c'], ['a','b','c', 'd'], lambda x,y: x == y, 2) +3 +>>> LCSS(['a','x','b','c'], ['a','b','c','d','x'], lambda x,y: x == y) +3 +>>> LCSS(['a','b','c','x','d'], ['a','b','c','d','x'], lambda x,y: x == y) 4 ->>> alignedLCSS(range(5,10), range(10), 0.1, lambda x,y:abs(x-y), 2) +>>> alignedLCSS(range(5), range(5), lambda x,y:(abs(x-y) <= 0.1), 2) 5 ->>> LCSS(range(5,10), range(10), 0.1, lambda x,y:abs(x-y), 2) +>>> alignedLCSS(range(1,5), range(5), lambda x,y:(abs(x-y) <= 0.1), 2) +4 + +>>> alignedLCSS(range(5,10), range(10), lambda x,y:(abs(x-y) <= 0.1), 2) +5 +>>> LCSS(range(5,10), range(10), lambda x,y:(abs(x-y) <= 0.1), 2) 0 ->>> alignedLCSS(range(5), range(5), 0.1, lambda x,y:abs(x-y), 6) +>>> alignedLCSS(range(5), range(5), lambda x,y:(abs(x-y) <= 0.1), 6) 5 ->>> alignedLCSS(range(5), range(6), 0.1, lambda x,y:abs(x-y), 6) +>>> alignedLCSS(range(5), range(6), lambda x,y:(abs(x-y) <= 0.1), 6) 5 ->>> alignedLCSS(range(1,7), range(6), 0.1, lambda x,y:abs(x-y), 10) +>>> alignedLCSS(range(1,7), range(6), lambda x,y:(abs(x-y) <= 0.1), 10) 5
--- a/python/utils.py Fri Jul 12 11:28:47 2013 -0400 +++ b/python/utils.py Mon Jul 15 12:12:47 2013 -0400 @@ -138,12 +138,15 @@ ######################### -# maths section +# sequence section ######################### -def LCSS(l1, l2, threshold, distance, delta = float('inf')): +def LCSS(l1, l2, similarityFunc, delta = float('inf')): '''returns the longest common subsequence similarity based on the threshold on distance between two elements of lists l1, l2 + similarityFunc returns True or False whether the two points are considered similar + + eg distance(p1, p2) < epsilon ''' from numpy import zeros, int as npint n1 = len(l1) @@ -151,23 +154,23 @@ similarity = zeros((n1+1,n2+1), dtype = npint) for i in xrange(1,n1+1): for j in xrange(max(1,i-delta),min(n2+1,i+delta+1)): - if distance(l1[i-1], l2[j-1])<=threshold: + if similarityFunc(l1[i-1], l2[j-1]): similarity[i][j] = similarity[i-1][j-1]+1 else: similarity[i][j] = max(similarity[i-1][j], similarity[i][j-1]) return max(max(similarity[:,-1]), max(similarity[-1,:])) -def normalizedLCSS(l1, l2, threshold, distance, delta = float('inf'), lengthMethod = min): +def normalizedLCSS(l1, l2, similarityFunc, delta = float('inf'), lengthMethod = min): ''' compute the normalized LCSS ie, the LCSS divided by the min or mean of the indicator lengths (using lengthMethod) lengthMethod = lambda x,y:float(x,y)/2''' - return float(LCSS(l1, l2, threshold, distance, delta))/lengthMethod(len(l1), len(l2)) + return float(LCSS(l1, l2, similarityFunc, delta))/lengthMethod(len(l1), len(l2)) -def DLCSS(l1, l2, threshold, distance, delta = float('inf'), lengthMethod = min): +def DLCSS(l1, l2, similarityFunc, delta = float('inf'), lengthMethod = min): ''' compute the LCSS distance''' - return 1-normalizedLCSS(l1, l2, threshold, distance, delta, lengthMethod) + return 1-normalizedLCSS(l1, l2, similarityFunc, delta, lengthMethod) -def alignedLCSS(_l1, _l2, threshold, distance, delta): +def alignedLCSS(_l1, _l2, similarityFunc, delta): '''returns the best matching if using a finite delta by shiftinig the series alignments''' if len(_l2) < len(_l1): # l1 is the shortest l1 = _l2 @@ -180,15 +183,19 @@ # for i in xrange(min(delta,n1), max(n1+n2-delta, n2+1)): # i is the alignment of the end of l1 in l2 # print l1[min(-i-1,n1):] # min(n1+n2-i,n1) # print l2[max(0,i-n1):] - # print LCSS(l1[min(-i-1,n1):], l2[max(0,i-n1):], threshold, distance, delta) - 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))] + # print LCSS(l1[min(-i-1,n1):], l2[max(0,i-n1):], similarityFunc, delta) + 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))] return max(lcss) -def normalizedAlignedLCSS(l1, l2, threshold, distance, delta, lengthMethod = min): - return float(alignedLCSS(l1, l2, threshold, distance, delta))/lengthMethod(len(l1), len(l2)) +def normalizedAlignedLCSS(l1, l2, similarityFunc, delta, lengthMethod = min): + return float(alignedLCSS(l1, l2, similarityFunc, delta))/lengthMethod(len(l1), len(l2)) -def alignedDLCSS(l1, l2, threshold, distance, delta, lengthMethod = min): - return 1-normalizedAlignedLCSS(l1, l2, threshold, distance, delta, lengthMethod) +def alignedDLCSS(l1, l2, similarityFunc, delta, lengthMethod = min): + return 1-normalizedAlignedLCSS(l1, l2, similarityFunc, delta, lengthMethod) + +######################### +# maths section +######################### def framesToTime(nFrames, frameRate, initialTime = (0.,0.,0.)): 'returns hour, minutes and seconds'