Mercurial Hosting > traffic-intelligence
changeset 369:027e254f0b53
lcss subclass for indicators
| author | Nicolas Saunier <nicolas.saunier@polymtl.ca> |
|---|---|
| date | Mon, 15 Jul 2013 16:47:09 -0400 |
| parents | 2db4e76599a1 |
| children | 97e8fa0ee9a1 |
| files | python/indicators.py python/moving.py python/tests/moving.txt python/tests/utils.txt python/utils.py |
| diffstat | 5 files changed, 161 insertions(+), 150 deletions(-) [+] |
line wrap: on
line diff
--- a/python/indicators.py Mon Jul 15 15:08:53 2013 -0400 +++ b/python/indicators.py Mon Jul 15 16:47:09 2013 -0400 @@ -103,57 +103,31 @@ 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 - if indicator1 and indicator2: - return LCSS(indicator1.getValues(), indicator2.getValues(), lambda x,y: (distanceForLCSS(x,y) <= threshold), delta) - else: - return 0 +from utils import LCSS as utilsLCSS -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: - return normalizedLCSS(indicator1.getValues(), indicator2.getValues(), lambda x,y: (distanceForLCSS(x,y) <= threshold), delta, method) - else: - return 0. +class LCSS(utilsLCSS): + '''Adapted LCSS class for indicators, same pattern''' + 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 computeDLCSS(indicator1, indicator2, threshold, delta = float('inf'), method = min): - ''' compute the LCSS distance between two indicators using LCSS''' - from utils import DLCSS - if indicator1 and indicator2: - return DLCSS(indicator1.getValues(), indicator2.getValues(), lambda x,y: (distanceForLCSS(x,y) <= threshold), delta, method) - else: - return 1. + def get(self, indicator1, indicator2): + if indicator1 and indicator2: + return self.compute(indicator1.getValues(), indicator2.getValues()) + else: + return 0 -# 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(), lambda x,y: (distanceForLCSS(x,y) <= threshold), delta) - else: - return 0 + def getNormalized(self, indicator1, indicator2): + if indicator1 and indicator2: + return self.computeNormalized(indicator1.getValues(), indicator2.getValues()) + 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(), lambda x,y: (distanceForLCSS(x,y) <= threshold), 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 - if indicator1 and indicator2: - return alignedDLCSS(indicator1.getValues(), indicator2.getValues(), lambda x,y: (distanceForLCSS(x,y) <= threshold), delta, method) - else: - return 1. + def getDistance(self, indicator1, indicator2): + if indicator1 and indicator2: + return self.computeDistance(indicator1.getValues(), indicator2.getValues()) + else: + return 1. + class SeverityIndicator(TemporalIndicator): '''Class for severity indicators
--- a/python/moving.py Mon Jul 15 15:08:53 2013 -0400 +++ b/python/moving.py Mon Jul 15 16:47:09 2013 -0400 @@ -539,12 +539,8 @@ # version 2: use shapely polygon contains @staticmethod - def norm2LCSS(t1, t2, threshold): - return utils.LCSS(t1, t2, lambda x,y: Point.distanceNorm2(x,y) <= threshold) - - @staticmethod - def normMaxLCSS(t1, t2, threshold): - return utils.LCSS(t1, t2, lambda p1, p2: (p1-p2).normMax() <= threshold) + def lcss(t1, t2, lcss): + return lcss.compute(t1, t2) class CurvilinearTrajectory(Trajectory): '''Sub class of trajectory for trajectories with curvilinear coordinates and lane assignements
--- a/python/tests/moving.txt Mon Jul 15 15:08:53 2013 -0400 +++ b/python/tests/moving.txt Mon Jul 15 16:47:09 2013 -0400 @@ -75,9 +75,12 @@ >>> t1.getTrajectoryInPolygon(np.array([[10,10],[14,10],[14,13],[10,13]])).length() 0 ->>> Trajectory.norm2LCSS(t1, t1, 0.1) +>>> from utils import LCSS +>>> lcss = LCSS(lambda x,y: Point.distanceNorm2(x,y) <= 0.1) +>>> Trajectory.lcss(t1, t1, lcss) 3 ->>> Trajectory.normMaxLCSS(t1, t1, 0.1) +>>> lcss = LCSS(lambda p1, p2: (p1-p2).normMax() <= 0.1) +>>> Trajectory.lcss(t1, t1, lcss) 3 >>> o1 = MovingObject(positions = Trajectory([[0]*3,[2]*3]), velocities = Trajectory([[0]*3,[1]*3]))
--- a/python/tests/utils.txt Mon Jul 15 15:08:53 2013 -0400 +++ b/python/tests/utils.txt Mon Jul 15 16:47:09 2013 -0400 @@ -44,46 +44,65 @@ >>> 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), lambda x,y:(abs(x-y) <= 0.1)) +>>> lcss = LCSS(lambda x,y: abs(x-y) <= 0.1) +>>> lcss.compute(range(5), range(5)) 5 ->>> LCSS(range(1,5), range(5), lambda x,y:(abs(x-y) <= 0.1)) +>>> lcss.compute(range(1,5), range(5)) 4 ->>> LCSS(range(5,10), range(5), lambda x,y:(abs(x-y) <= 0.1)) +>>> lcss.compute(range(5,10), range(5)) 0 ->>> LCSS(range(5), range(10), lambda x,y:(abs(x-y) <= 0.1)) +>>> lcss.compute(range(5), range(10)) 5 ->>> LCSS(range(5), range(10), lambda x,y:(abs(x-y) <= 0.1), 2) +>>> lcss.compute(range(5), range(10), 2) 5 ->>> 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) +>>> lcss.similarityFunc = lambda x,y: x == y +>>> lcss.compute(['a','b','c'], ['a','b','c', 'd']) 3 ->>> LCSS(['a','x','b','c'], ['a','b','c','d','x'], lambda x,y: x == y) +>>> lcss.computeNormalized(['a','b','c'], ['a','b','c', 'd']) #doctest: +ELLIPSIS +1.0 +>>> lcss.computeNormalized(['a','b','c','x'], ['a','b','c', 'd']) #doctest: +ELLIPSIS +0.75 +>>> lcss.compute(['a','b','c'], ['a','b','c', 'd']) 3 ->>> LCSS(['a','b','c','x','d'], ['a','b','c','d','x'], lambda x,y: x == y) +>>> lcss.compute(['a','x','b','c'], ['a','b','c','d','x']) +3 +>>> lcss.compute(['a','b','c','x','d'], ['a','b','c','d','x']) 4 ->>> LCSS(['a','b','c'], ['a','b','x','x','c'], lambda x,y: x == y, 1) +>>> lcss.delta = 1 +>>> lcss.compute(['a','b','c'], ['a','b','x','x','c']) 2 ->>> LCSS(['a','b','c'], ['a','b','c', 'd'], lambda x,y: x == y, returnSubSequence = True) -(3, [(0, 0), (1, 1), (2, 2)]) ->>> LCSS(['a','b','c'], ['x','a','b','c'], lambda x,y: x == y, returnSubSequence = True) -(3, [(0, 1), (1, 2), (2, 3)]) ->>> LCSS(['a','g','b','c'], ['a','b','c', 'd'], lambda x,y: x == y, returnSubSequence = True) -(3, [(0, 0), (2, 1), (3, 2)]) +>>> lcss.delta = float('inf') +>>> lcss.compute(['a','b','c'], ['a','b','c', 'd'], computeSubSequence = True) +3 +>>> lcss.subSequenceIndices +[(0, 0), (1, 1), (2, 2)] +>>> lcss.compute(['a','b','c'], ['x','a','b','c'], computeSubSequence = True) +3 +>>> lcss.subSequenceIndices +[(0, 1), (1, 2), (2, 3)] +>>> lcss.compute(['a','g','b','c'], ['a','b','c', 'd'], computeSubSequence = True) +3 +>>> lcss.subSequenceIndices +[(0, 0), (2, 1), (3, 2)] ->>> alignedLCSS(range(5), range(5), lambda x,y:(abs(x-y) <= 0.1), 2) +>>> alignedLcss = LCSS(lambda x,y:(abs(x-y) <= 0.1), delta = 2, aligned = True) +>>> alignedLcss.compute(range(5), range(5)) 5 ->>> alignedLCSS(range(1,5), range(5), lambda x,y:(abs(x-y) <= 0.1), 2) +>>> alignedLcss.compute(range(1,5), range(5)) 4 ->>> alignedLCSS(range(5,10), range(10), lambda x,y:(abs(x-y) <= 0.1), 2) +>>> alignedLcss.compute(range(5,10), range(10)) 5 ->>> LCSS(range(5,10), range(10), lambda x,y:(abs(x-y) <= 0.1), 2) + +>>> lcss.delta = 2 +>>> lcss.compute(range(5,10), range(10)) 0 ->>> alignedLCSS(range(5), range(5), lambda x,y:(abs(x-y) <= 0.1), 6) +>>> alignedLcss.delta = 6 +>>> alignedLcss.compute(range(5), range(5)) 5 ->>> alignedLCSS(range(5), range(6), lambda x,y:(abs(x-y) <= 0.1), 6) +>>> alignedLcss.compute(range(5), range(6)) 5 ->>> alignedLCSS(range(1,7), range(6), lambda x,y:(abs(x-y) <= 0.1), 10) +>>> lcss.delta = 10 +>>> alignedLcss.compute(range(1,7), range(6)) 5
--- a/python/utils.py Mon Jul 15 15:08:53 2013 -0400 +++ b/python/utils.py Mon Jul 15 16:47:09 2013 -0400 @@ -141,86 +141,105 @@ # sequence section ######################### -def sequenceSimilarities(l1, l2, similarityFunc, delta = float('inf')): - from numpy import zeros, int as npint - n1 = len(l1) - n2 = len(l2) - similarities = 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 similarityFunc(l1[i-1], l2[j-1]): - similarities[i,j] = similarities[i-1,j-1]+1 - else: - similarities[i,j] = max(similarities[i-1,j], similarities[i,j-1]) - return similarities +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 subSequence(similarities, 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 similarities[i][j] == similarities[i][j-1]: - return subSequence(similarities, i, j-1) - elif similarities[i][j] == similarities[i-1][j]: - return subSequence(similarities, i-1, j) - else: - return subSequence(similarities, i-1, j-1) + [(i-1,j-1)] + 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 LCSS(l1, l2, similarityFunc, delta = float('inf'), returnSubSequence = 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 + 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 - similarities = sequenceSimilarities(l1, l2, similarityFunc, delta) - imax = argmax(similarities[:,-1]) - jmax = argmax(similarities[-1,:]) - if returnSubSequence: - if similarities[imax, -1] > similarities[-1, jmax]: - lcss = similarities[imax, -1] - subseq = subSequence(similarities, imax, len(l2)) + 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: - lcss = similarities[-1, jmax] - subseq = subSequence(similarities, len(l1), jmax) - return lcss, subseq - else: - return max(similarities[imax, -1], similarities[-1, jmax]) - -def normalizedLCSS(l1, l2, similarityFunc, delta = float('inf'), lengthFunc = min): - ''' 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(LCSS(l1, l2, similarityFunc, delta))/lengthFunc(len(l1), len(l2)) + return max(self.similarityTable[imax, -1], self.similarityTable[-1, jmax]) -def DLCSS(l1, l2, similarityFunc, delta = float('inf'), lengthFunc = min): - ''' compute the LCSS distance''' - return 1-normalizedLCSS(l1, l2, similarityFunc, delta, lengthFunc) + 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 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 - 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 = [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 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 normalizedAlignedLCSS(l1, l2, similarityFunc, delta, lengthFunc = min): - return float(alignedLCSS(l1, l2, similarityFunc, delta))/lengthFunc(len(l1), len(l2)) + 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 alignedDLCSS(l1, l2, similarityFunc, delta, lengthFunc = min): - return 1-normalizedAlignedLCSS(l1, l2, similarityFunc, delta, lengthFunc) + 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 #########################