In [6]:
# -*- coding: utf-8 -*-
class Dtw(object):
def __init__(self, seq1, seq2,
patterns = [(-1,-1), (-1,0), (0,-1)],
weights = [{(0,0):2}, {(0,0):1}, {(0,0):1}],
band_r=0.5):
self._seq1 = seq1
self._seq2 = seq2
self._r = min(10, band_r*max(len(seq1), len(seq2)))
assert len(patterns) == len(weights)
self._patterns = patterns
self._weights = weights
self._map = {(-1, -1): 0}
def get_distance(self, idx1, idx2):
if idx1<0 or idx2<0 or idx1>=len(self._seq1) or idx2>=len(self._seq2):
return 0
return abs(self._seq1[idx1] - self._seq2[idx2])
def calculate_path(self, idx1, idx2, pattern, weight):
g = self.calculate(idx1+pattern[0], idx2+pattern[1])
sum_d = 0
for coor_offset, w in weight.items():
i1, i2 = map(sum, zip((idx1, idx2), coor_offset))
sum_d += self.get_distance(i1, i2)
return g + sum_d
def calculate(self, idx1, idx2):
if (idx1, idx2) in self._map:
return self._map[(idx1, idx2)]
if idx1 < 0 or idx2 < 0 or abs(idx1-idx2) > self._r:
return float('inf')
min_prev_dp = float('inf')
for i in range(len(self._patterns)):
min_prev_dp = min(min_prev_dp, self.calculate_path(idx1, idx2, self._patterns[i], self._weights[i]))
self._map[(idx1, idx2)] = min_prev_dp
return self._map[(idx1, idx2)]
@property
def dtw_matrix_dict(self):
return self._map
def print_dtw_matrix(self):
print(' '+' '.join(["{:^7d}".format(i) for i in range(len(self._seq2))]))
for i in range(len(self._seq1)):
str = "{:^4d}: ".format(i)
for j in range(len(self._seq2)):
if (i,j) not in self._map:
str += "{:^7s} ".format('-')
else:
str += "{:^7.3f} ".format(self._map[(i,j)])
print (str)
def get_dtw(self):
g = self.calculate(len(self._seq1)-1, len(self._seq2)-1)
N = len(self._seq1) + len(self._seq2)
return g/N
In [3]:
PATTERNS_1 = [(0,-1), (-1,-1), (-1,0)]
WEIGHTS_SYM_1 = [{(0,0):1}, {(0,0):2}, {(0,0):1}]
WEIGHTS_ASYM_1 = [{}, {(0,0):1}, {(0,0):1}]
WEIGHTS_ASYM_1_2 = [{(0,0):100}, {(0,0):10}, {(0,0):1}]
PATTERNS_2 = [(-1,-3), (-1,-2), (-1,-1), (-2,-1), (-3,-1)]
WEIGHTS_SYM_2 = [{(0,-2):2, (0,-1):1, (0,0):1}, \
{(0,-1):2, (0,0):1}, \
{(0,0):2}, \
{(-1,0):2, (0,0):1}, \
{(-2,0):2, (-1,0):1, (0,0):1}]
WEIGHTS_ASYM_2 = [{(0,-2):1, (0,-1):1, (0,0):1/3}, \
{(0,-1):1, (0,0):1/2}, \
{(0,0):1}, \
{(-1,0):1, (0,0):1}, \
{(-2,0):1, (-1,0):1, (0,0):1}]
In [4]:
import numpy as np
seq1 = [1, 1, 2, 9]*2
seq2 = [0, 1, 1, 2]*2
In [14]:
seq1 = (np.array(seq1)-np.mean(seq1))/np.std(seq1)
seq2 = (np.array(seq2)-np.mean(seq2))/np.std(seq2)
In [15]:
d = Dtw(seq1, seq2, PATTERNS_1, WEIGHTS_SYM_1)
d.get_dtw()
Out[15]:
In [16]:
d.print_dtw_matrix()
In [7]:
d = Dtw(seq1, seq2, PATTERNS_1, WEIGHTS_ASYM_1)
d.get_dtw()
Out[7]:
In [10]:
d.print_dtw_matrix()
In [9]:
d = Dtw(seq1, seq2, PATTERNS_2, WEIGHTS_SYM_2)
d.get_dtw()
Out[9]:
In [10]:
d.print_dtw_matrix()
In [11]:
d = Dtw(seq1, seq2, PATTERNS_2, WEIGHTS_ASYM_2)
d.get_dtw()
Out[11]:
In [12]:
d.print_dtw_matrix()
In [20]:
# -*- coding: utf-8 -*-
class Dtw(object):
def __init__(self, seq1, seq2,
patterns = [(-1,-1), (-1,0), (0,-1)],
weights = [{(0,0):2}, {(0,0):1}, {(0,0):1}],
band_r=0.3):
self._seq1 = seq1
self._seq2 = seq2
self.len_seq1 = len(seq1)
self.len_seq2 = len(seq2)
self.len_pattern = len(patterns)
self.sum_w = [sum(ws.values()) for ws in weights]
self._r = int(len(seq1)*band_r)
assert len(patterns) == len(weights)
self._patterns = patterns
self._weights = weights
def get_distance(self, i1, i2):
return abs(self._seq1[i1] - self._seq2[i2])
def calculate(self):
g = list([float('inf')]*self.len_seq2 for i in range(self.len_seq1))
cost = list([0]*self.len_seq2 for i in range(self.len_seq1))
g[0][0] = 2*self.get_distance(0, 0)
for i in range(self.len_seq1):
for j in range(max(0,i-self._r), min(i+self._r+1, self.len_seq2)):
for pat_i in range(self.len_pattern):
coor = (i+self._patterns[pat_i][0], j+self._patterns[pat_i][1])
if coor[0]<0 or coor[1]<0:
continue
dist = 0
for w_coor_offset, d_w in self._weights[pat_i].items():
w_coor = (i+w_coor_offset[0], j+w_coor_offset[1])
dist += d_w*self.get_distance(w_coor[0], w_coor[1])
this_val = g[coor[0]][coor[1]] + dist
this_cost = cost[coor[0]][coor[1]] + self.sum_w[pat_i]
if this_val < g[i][j]:
g[i][j] = this_val
cost[i][j] = this_cost
return g[self.len_seq1-1][self.len_seq2-1]/cost[self.len_seq1-1][self.len_seq2-1], g, cost
def print_table(self, tb):
print(' '+' '.join(["{:^7d}".format(i) for i in range(self.len_seq2)]))
for i in range(self.len_seq1):
str = "{:^4d}: ".format(i)
for j in range(self.len_seq2):
str += "{:^7.3f} ".format(tb[i][j])
print (str)
def print_g_matrix(self):
_, tb, _ = self.calculate()
self.print_table(tb)
def print_cost_matrix(self):
_, _, tb = self.calculate()
self.print_table(tb)
def get_dtw(self):
ans, _, _ = self.calculate()
return ans
In [21]:
import numpy as np
seq1 = [1, 1, 2, 9]*2
seq2 = [0, 1, 1, 2]*2
seq1 = (np.array(seq1)-np.mean(seq1))/np.std(seq1)
seq2 = (np.array(seq2)-np.mean(seq2))/np.std(seq2)
In [22]:
d = Dtw(seq1, seq2, PATTERNS_1, WEIGHTS_ASYM_1)
d.get_dtw()
Out[22]:
In [23]:
d.print_g_matrix()
In [24]:
d.print_cost_matrix()
In [10]:
vec1=[1,7,2,3,6,9,4,1]
vec2=[1,8,8,8,2,7,7,7,0]
Dtw(vec1,vec2,PATTERNS_1,WEIGHTS_SYM_1).print_g_matrix()
In [33]:
Dtw(vec1,vec2,PATTERNS_1,WEIGHTS_SYM_1).print_cost_matrix()
In [36]:
Dtw(vec1,vec2,PATTERNS_1,WEIGHTS_SYM_1).get_dtw()
Out[36]:
In [34]:
Dtw(vec1, vec2, PATTERNS_1, WEIGHTS_ASYM_1_2).print_g_matrix()
In [35]:
Dtw(vec1, vec2, PATTERNS_1, WEIGHTS_ASYM_1_2).print_cost_matrix()
In [37]:
Dtw(vec1,vec2,PATTERNS_1,WEIGHTS_ASYM_1_2).get_dtw()
Out[37]:
In [ ]:
In [47]:
from math import gcd
ct=0
for i in range(101):
for j in range(i, 101):
a = i
b = j-i
c = 100-j
if gcd(a,gcd(b,c))==1:
ct+=1
print(a,b,c)
In [ ]:
from math import gcd
ct=0
for i in range(101):
for j in range(i, 101):
a = i
b = j-i
c = 100-j
if gcd(a,gcd(b,c))!=1:
continue
ct+=1
print(ct)