Mercurial Hosting > traffic-intelligence
changeset 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 | a5e40bd04cf4 |
children | efd4dd4665ac |
files | python/indicators.py python/tests/utils.txt python/utils.py |
diffstat | 3 files changed, 89 insertions(+), 25 deletions(-) [+] |
line wrap: on
line diff
--- a/python/indicators.py Tue May 07 02:02:55 2013 +0200 +++ b/python/indicators.py Tue May 07 18:43:40 2013 +0200 @@ -121,39 +121,57 @@ return DLCSS +def distanceForLCSS(x, y): # lambda x,y:abs(x-y) + if x == None or y == None: + return float('inf') + else: + return abs(x-y) + +# non-aligned LCSS computations, ok for delta = inf def computeLCSS(indicator1, indicator2, threshold, delta = float('inf')): ''' compute the LCSS between two indicators using LCSS''' from utils import LCSS - - def distance(x, y): # lambda x,y:abs(x-y) - if x == None or y == None: - return float('inf') - else: - return abs(x-y) if indicator1 and indicator2: - return LCSS(indicator1.getValues(), indicator2.getValues(), threshold, distance, delta) + return LCSS(indicator1.getValues(), indicator2.getValues(), threshold, distanceForLCSS, delta) else: return 0 -def computeNormalizedLCSS(indicator1, indicator2, threshold, delta = float('inf'), method= 'min'): +def computeNormalizedLCSS(indicator1, indicator2, threshold, delta = float('inf'), method= min): ''' compute the normalized LCSS between two indicators using LCSS ie, the LCSS divided by the min or mean of the indicator lengths''' - + from utils import normalizedLCSS if indicator1 and indicator2: - if method == 'min': - denominator = min(len(indicator1), len(indicator2)) - elif method == 'mean': - denominator = float(len(indicator1) + len(indicator2))/2 - else: - print('Unknown denominator method name') - denominator = 1. - return float(computeLCSS(indicator1, indicator2, threshold, delta))/denominator + return normalizedLCSS(indicator1.getValues(), indicator2.getValues(), threshold, distanceForLCSS, delta, method) else: return 0. -def computeDLCSS(indicator1, indicator2, threshold, delta = float('inf'), method = 'min'): +def computeDLCSS(indicator1, indicator2, threshold, delta = float('inf'), method = min): ''' compute the LCSS distance between two indicators using LCSS''' - return 1-computeNormalizedLCSS(indicator1, indicator2, threshold, delta, method) + from utils import DLCSS + return DLCSS(indicator1.getValues(), indicator2.getValues(), threshold, distanceForLCSS, delta, method) + +# aligned LCSS computations +def computeAlignedLCSS(indicator1, indicator2, threshold, delta = float('inf')): + ''' compute the aligned LCSS between two indicators using LCSS''' + from utils import alignedLCSS + if indicator1 and indicator2: + return alignedLCSS(indicator1.getValues(), indicator2.getValues(), threshold, distanceForLCSS, delta) + else: + return 0 + +def computeNormalizedAlignedLCSS(indicator1, indicator2, threshold, delta = float('inf'), method= min): + ''' compute the normalized aligned LCSS between two indicators using LCSS + ie, the LCSS divided by the min or mean of the indicator lengths''' + from utils import normalizedAlignedLCSS + if indicator1 and indicator2: + return normalizedAlignedLCSS(indicator1.getValues(), indicator2.getValues(), threshold, distanceForLCSS, delta, method) + else: + return 0. + +def computeAlignedDLCSS(indicator1, indicator2, threshold, delta = float('inf'), method = min): + ''' compute the aligned LCSS distance between two indicators using LCSS''' + from utils import alignedDLCSS + return alignedDLCSS(indicator1.getValues(), indicator2.getValues(), threshold, distanceForLCSS, delta, method) class SeverityIndicator(TemporalIndicator): '''Class for severity indicators
--- a/python/tests/utils.txt Tue May 07 02:02:55 2013 +0200 +++ b/python/tests/utils.txt Tue May 07 18:43:40 2013 +0200 @@ -50,4 +50,17 @@ 4 >>> LCSS(range(5,10), range(5), 0.1, lambda x,y:abs(x-y)) 0 +>>> LCSS(range(5), range(10), 0.1, lambda x,y:abs(x-y)) +5 +>>> LCSS(range(5), range(10), 0.1, lambda x,y:abs(x-y), 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) +4 + +>>> alignedLCSS(range(5,10), range(10), 0.1, lambda x,y:abs(x-y), 2) +5 +>>> LCSS(range(5,10), range(10), 0.1, lambda x,y:abs(x-y), 2) +0
--- a/python/utils.py Tue May 07 02:02:55 2013 +0200 +++ b/python/utils.py Tue May 07 18:43:40 2013 +0200 @@ -179,16 +179,49 @@ based on the threshold on distance between two elements of lists l1, l2 ''' from numpy import zeros, int as npint - m = len(l1) - n = len(l2) - similarity = zeros((m+1,n+1), dtype = npint) - for i in xrange(1,m+1): - for j in xrange(max(1,i-delta),min(n+1,i+delta)): + n1 = len(l1) + n2 = len(l2) + 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: similarity[i][j] = similarity[i-1][j-1]+1 else: similarity[i][j] = max(similarity[i-1][j], similarity[i][j-1]) - return similarity[-1][-1] + return max(max(similarity[:,-1]), max(similarity[-1,:])) + +def normalizedLCSS(l1, l2, threshold, distance, 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)) + +def DLCSS(l1, l2, threshold, distance, delta = float('inf'), lengthMethod = min): + ''' compute the LCSS distance''' + return 1-normalizedLCSS(l1, l2, threshold, distance, delta, lengthMethod) + +def alignedLCSS(_l1, _l2, threshold, distance, 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 + l2 = _l1 + else: + l1 = _l1 + l2 = _l2 + n1 = len(l1) + n2 = len(l2) + # for i in xrange(delta, n1+n2-delta): # 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(delta, n1+n2-delta)] + 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 alignedDLCSS(l1, l2, threshold, distance, delta, lengthMethod = min): + return 1-normalizedAlignedLCSS(l1, l2, threshold, distance, delta, lengthMethod) def framesToTime(nFrames, frameRate, initialTime = (0.,0.,0.)): 'returns hour, minutes and seconds'