Mercurial Hosting > traffic-intelligence

changeset 370:97e8fa0ee9a1

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
work in progress for complete alignment
author Nicolas Saunier <nicolas.saunier@polymtl.ca>
date Mon, 15 Jul 2013 18:18:44 -0400
parents 027e254f0b53
children 924e38c9f70e
files python/indicators.py python/utils.py
diffstat 2 files changed, 125 insertions(+), 109 deletions(-) [+]
line wrap: on
line diff
--- a/python/indicators.py	Mon Jul 15 16:47:09 2013 -0400
+++ b/python/indicators.py	Mon Jul 15 18:18:44 2013 -0400
@@ -110,21 +110,21 @@
     def __init__(self, threshold, delta = float('inf'), aligned = False, lengthFunc = min):
         utilsLCSS.__init__(self, lambda x,y: (distanceForLCSS(x,y) <= threshold), delta, aligned, lengthFunc)
 
-    def get(self, indicator1, indicator2):
+    def compute(self, indicator1, indicator2):
         if indicator1 and indicator2:
-            return self.compute(indicator1.getValues(), indicator2.getValues())
+            return self._compute(indicator1.getValues(), indicator2.getValues())
         else:
             return 0
 
-    def getNormalized(self, indicator1, indicator2):
+    def computeNormalized(self, indicator1, indicator2):
         if indicator1 and indicator2:
-            return self.computeNormalized(indicator1.getValues(), indicator2.getValues())
+            return self._computeNormalized(indicator1.getValues(), indicator2.getValues())
         else:
             return 0.
 
-    def getDistance(self, indicator1, indicator2):
+    def computeDistance(self, indicator1, indicator2):
         if indicator1 and indicator2:
-            return self.computeDistance(indicator1.getValues(), indicator2.getValues())
+            return self._computeDistance(indicator1.getValues(), indicator2.getValues())
         else:
             return 1.
         
--- a/python/utils.py	Mon Jul 15 16:47:09 2013 -0400
+++ b/python/utils.py	Mon Jul 15 18:18:44 2013 -0400
@@ -138,111 +138,11 @@
 
 
 #########################
-# sequence section
+# maths section
 #########################
 
-class LCSS:
-    '''Class that keeps the LCSS parameters
-    and puts together the various computations'''
-    def __init__(self, similarityFunc, delta = float('inf'), aligned = False, lengthFunc = min):
-        self.similarityFunc = similarityFunc
-        self.aligned = aligned
-        self.delta = delta
-        self.lengthFunc = lengthFunc
-
-    def similarities(self, l1, l2):
-        from numpy import zeros, int as npint
-        n1 = len(l1)
-        n2 = len(l2)
-        self.similarityTable = zeros((n1+1,n2+1), dtype = npint)
-        for i in xrange(1,n1+1):
-            for j in xrange(max(1,i-self.delta),min(n2+1,i+self.delta+1)):
-                if self.similarityFunc(l1[i-1], l2[j-1]):
-                    self.similarityTable[i,j] = self.similarityTable[i-1,j-1]+1
-                else:
-                    self.similarityTable[i,j] = max(self.similarityTable[i-1,j], self.similarityTable[i,j-1])
-
-    def subSequence(self, i, j):
-        '''Returns the subsequence of two sequences
-        http://en.wikipedia.org/wiki/Longest_common_subsequence_problem'''
-        if i == 0 or j == 0:
-            return []
-        elif self.similarityTable[i][j] == self.similarityTable[i][j-1]:
-            return self.subSequence(i, j-1)
-        elif self.similarityTable[i][j] == self.similarityTable[i-1][j]:
-            return self.subSequence(i-1, j)
-        else:
-            return self.subSequence(i-1, j-1) + [(i-1,j-1)]
-
-    def computeLCSS(self, l1, l2, computeSubSequence = False):
-        '''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 argmax
-        self.similarities(l1, l2)
-        imax = argmax(self.similarityTable[:,-1])
-        jmax = argmax(self.similarityTable[-1,:])
-        if computeSubSequence:
-            if self.similarityTable[imax, -1] > self.similarityTable[-1, jmax]:
-                lcss = self.similarityTable[imax, -1]
-                self.subSequenceIndices = self.subSequence(imax, len(l2))
-            else:
-                lcss = self.similarityTable[imax, -1]
-                self.subSequenceIndices = self.subSequence(len(l1), jmax)
-            return lcss
-        else:
-            return max(self.similarityTable[imax, -1], self.similarityTable[-1, jmax])
-
-    def compute(self, _l1, _l2, computeSubSequence = False):
-        '''returns the best matching if using a finite delta by shiftinig the series alignments'''
-        if self.aligned:
-            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(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):], similarityFunc, delta)
-            lcss = [self.computeLCSS(l1[min(-i-1,n1):], l2[max(0,i-n1):]) for i in xrange(min(self.delta,n1), max(n1+n2-self.delta, n2+1))]
-            return max(lcss)
-        else:
-            return self.computeLCSS(_l1, _l2, computeSubSequence)
-
-    def get(self, l1, l2, computeSubSequence = False):
-        '''get methods are to be shadowed in child classes '''
-        return self.compute(l1, l2, computeSubSequence)
-
-    def computeAlignement(self):
-        from numpy import mean
-        return mean([j-i for i,j in self.subSequenceIndices])
-
-    def computeNormalized(self, l1, l2):
-        ''' compute the normalized LCSS
-        ie, the LCSS divided by the min or mean of the indicator lengths (using lengthFunc)
-        lengthFunc = lambda x,y:float(x,y)/2'''
-        return float(self.compute(l1, l2))/self.lengthFunc(len(l1), len(l2))
-
-    def getNormalized(self, l1, l2):
-        return self.computeNormalized(l1, l2)
-
-    def computeDistance(self, l1, l2):
-        ''' compute the LCSS distance'''
-        return 1-self.computeNormalized(l1, l2)
-
-    def getDistance(self, l1, l2):
-        return self.computeDistance(l1, l2)
-    
-#########################
-# maths section
-#########################
+def argMaxDict(d):
+    return max(d.iterkeys(), key=(lambda key: d[key]))
 
 def framesToTime(nFrames, frameRate, initialTime = (0.,0.,0.)):
     'returns hour, minutes and seconds'
@@ -305,6 +205,122 @@
     return coef
 
 #########################
+# sequence section
+#########################
+
+class LCSS:
+    '''Class that keeps the LCSS parameters
+    and puts together the various computations'''
+    def __init__(self, similarityFunc, delta = float('inf'), aligned = False, lengthFunc = min):
+        self.similarityFunc = similarityFunc
+        self.aligned = aligned
+        self.delta = delta
+        self.lengthFunc = lengthFunc
+        self.alignmentShift = 0
+
+    def similarities(self, l1, l2):
+        from numpy import zeros, int as npint
+        n1 = len(l1)
+        n2 = len(l2)
+        self.similarityTable = zeros((n1+1,n2+1), dtype = npint)
+        for i in xrange(1,n1+1):
+            for j in xrange(max(1,i-self.delta),min(n2+1,i+self.delta+1)):
+                if self.similarityFunc(l1[i-1], l2[j-1]):
+                    self.similarityTable[i,j] = self.similarityTable[i-1,j-1]+1
+                else:
+                    self.similarityTable[i,j] = max(self.similarityTable[i-1,j], self.similarityTable[i,j-1])
+
+    def subSequence(self, i, j):
+        '''Returns the subsequence of two sequences
+        http://en.wikipedia.org/wiki/Longest_common_subsequence_problem'''
+        if i == 0 or j == 0:
+            return []
+        elif self.similarityTable[i][j] == self.similarityTable[i][j-1]:
+            return self.subSequence(i, j-1)
+        elif self.similarityTable[i][j] == self.similarityTable[i-1][j]:
+            return self.subSequence(i-1, j)
+        else:
+            return self.subSequence(i-1, j-1) + [(i-1,j-1)]
+
+    def computeLCSS(self, l1, l2, computeSubSequence = False):
+        '''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 argmax
+        self.similarities(l1, l2)
+        imax = argmax(self.similarityTable[:,-1])
+        jmax = argmax(self.similarityTable[-1,:])
+        if computeSubSequence:
+            if self.similarityTable[imax, -1] > self.similarityTable[-1, jmax]:
+                self.similarityTable = self.similarityTable[:imax+1, :]
+                self.subSequenceIndices = self.subSequence(imax, len(l2))
+            else:
+                self.similarityTable = self.similarityTable[:, :jmax+1]
+                self.subSequenceIndices = self.subSequence(len(l1), jmax)
+            return self.similarityTable[-1,-1]
+        else:
+            return max(self.similarityTable[imax, -1], self.similarityTable[-1, jmax])
+
+    def _compute(self, _l1, _l2, computeSubSequence = False):
+        '''returns the best matching if using a finite delta by shiftinig the series alignments'''
+        if self.aligned:
+            from numpy import argmax
+            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(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):], similarityFunc, delta)
+            lcssValues = {}
+            similarityTables = {}
+            for i in xrange(min(self.delta,n1), max(n1+n2-self.delta, n2+1), max(1,self.delta)):
+                print l1[min(-i-1,n1):] # min(n1+n2-i,n1)
+                print l2[max(0,i-n1):]
+                lcssValues[i] = self.computeLCSS(l1[min(-i-1,n1):], l2[max(0,i-n1):])
+                print i, lcssValues[i]
+                similarityTables[i] = self.similarityTable
+            imax = argMaxDict(lcssValues)
+            self.similarityTable = similarityTables[imax]
+            self.subSequenceIndices = self.subSequence(self.similarityTable.shape[0]-1, self.similarityTable.shape[1]-1)
+            self.alignmentShift = max(0,imax-n1)-min(-imax-1,n1)
+            return lcssValues[imax]
+        else:
+            return self.computeLCSS(_l1, _l2, computeSubSequence)
+
+    def compute(self, l1, l2, computeSubSequence = False):
+        '''get methods are to be shadowed in child classes '''
+        return self._compute(l1, l2, computeSubSequence)
+
+    def computeAlignement(self):
+        from numpy import mean
+        return mean([j-i for i,j in self.subSequenceIndices])+self.alignmentShift
+
+    def _computeNormalized(self, l1, l2):
+        ''' compute the normalized LCSS
+        ie, the LCSS divided by the min or mean of the indicator lengths (using lengthFunc)
+        lengthFunc = lambda x,y:float(x,y)/2'''
+        return float(self.compute(l1, l2))/self.lengthFunc(len(l1), len(l2))
+
+    def computeNormalized(self, l1, l2):
+        return self._computeNormalized(l1, l2)
+
+    def _computeDistance(self, l1, l2):
+        ''' compute the LCSS distance'''
+        return 1-self.computeNormalized(l1, l2)
+
+    def computeDistance(self, l1, l2):
+        return self._computeDistance(l1, l2)
+    
+#########################
 # plotting section
 #########################