DTW timeseries clustering algorithm in J

dtw.ijs

load '~Projects/u.ijs'
load '~Projects/pq.ijs'

distance=: |@-

dtw=: dyad define
n=. #x

d=. x distance/"1 y

D=. (d , _ $~ 1 , n) ,"1 |: (_ $~ 1 , >:n)

for_i. i.n
do.
  for_j. i.n
  do.
    if. (0 = i) *. (0 = j) do. continue. end.
    
    m=. (D {~ <(i);(j-1)) <. (D {~ <(i-1);(j)) <. (D {~ <(i-1);(j-1))
    m=. m + (<i ; j) { D
    
    D=. m (<i ; j) } D
  end.
end.

D=. }:"1 }: D

d findBest D
)

findBest=: dyad define
d=. x
D=. y

'm n'=. $D

from=. 0 0
to=. <: m , n

pq=. conew 'PQ'
create__pq''

NB. weight ; iter ; cost ; position
push__pq (D{~<from) ; 1 ; (d{~<from) ; from

visited=. (m , n) $ _

routes=. (1 1) ; (1 0) ; (0 1)

found=. ''
iter=. 1

while. 0 < size__pq
do.
  'weight it cost pos'=. pop__pq''
  
  iter=. iter >. it
  
  if. (#to) = (+/ to = pos)
  do.
    found=. it ; cost
    break.
  end.
  
  for_route. routes
  do.
    next=. pos + >route
    
    if. 0 < +/ next > to
    do. continue.
    end.
    
    newWeight=. weight + (D{~<next)
    
    if. newWeight > visited{~<next
    do. continue.
    end.
    
    visited=. newWeight (<next) } visited
    
    push__pq (newWeight ; (it + 1); (cost + d{~<next) ; next)
  end.
end.

found
)