Mercurial Hosting > traffic-intelligence

changeset 322:28661c5887d3

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
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'