Searching for dynamic time warping step pattern

Question

I am looking for dynamic time warping step pattern (dtw package for R) , which would allow assignment of one query index value to several reference index values (symmetric2 does that for example). I would, however, like to limit the assignment of several query index values to one reference index value such that only one per a ref. index value is allowed. In other words preceding query index values were not allowed to be assigned to the same reference index value.

Here is an example for R:

reference <- structure(list(date = structure(c(15218, 15219, 15220, 15221, 
15222, 15223, 15224, 15225, 15226, 15227, 15228, 15229, 15230, 
15231, 15232, 15233, 15234, 15235, 15236, 15237, 15238, 15239, 
15240, 15241, 15242, 15243, 15244, 15245, 15246, 15247, 15248, 
15249, 15250, 15251, 15252, 15253, 15254, 15255, 15256, 15257, 
15258, 15259, 15260, 15261, 15262, 15263, 15264, 15265, 15266, 
15267, 15268, 15269, 15270, 15271, 15272, 15273, 15274, 15275, 
15276, 15277, 15278, 15279, 15280, 15281, 15282, 15283, 15284, 
15285, 15286, 15287, 15288, 15289, 15290, 15291, 15292, 15293, 
15294, 15295, 15296, 15297, 15298, 15299, 15300, 15301, 15302, 
15303, 15304, 15305, 15306, 15307, 15308, 15309, 15310, 15311, 
15312, 15313, 15314, 15315, 15316, 15317, 15318, 15319, 15320, 
15321, 15322, 15323, 15324, 15325, 15326, 15327, 15328, 15329, 
15330, 15331, 15332, 15333, 15334, 15335, 15336, 15337, 15338, 
15339, 15340, 15341, 15342, 15343, 15344, 15345, 15346, 15347, 
15348, 15349, 15350, 15351, 15352, 15353, 15354, 15355, 15356, 
15357, 15358, 15359, 15360, 15361, 15362, 15363, 15364, 15365, 
15366, 15367, 15368, 15369, 15370, 15371, 15372, 15373, 15374, 
15375, 15376, 15377, 15378, 15379, 15380, 15381, 15382, 15383, 
15384, 15385, 15386, 15387, 15388, 15389, 15390, 15391, 15392, 
15393, 15394, 15395, 15396, 15397, 15398, 15399, 15400, 15401, 
15402, 15403, 15404, 15405, 15406, 15407, 15408, 15409, 15410, 
15411, 15412, 15413, 15414, 15415, 15416, 15417, 15418, 15419, 
15420, 15421, 15422, 15423, 15424, 15425, 15426, 15427, 15428, 
15429, 15430, 15431, 15432, 15433, 15434, 15435, 15436, 15437, 
15438, 15439, 15440, 15441, 15442, 15443, 15444, 15445, 15446, 
15447, 15448, 15449, 15450, 15451, 15452, 15453, 15454, 15455, 
15456, 15457, 15458, 15459, 15460, 15461, 15462, 15463, 15464, 
15465, 15466, 15467, 15468, 15469, 15470, 15471, 15472, 15473, 
15474, 15475, 15476, 15477, 15478, 15479, 15480, 15481, 15482, 
15483, 15484, 15485, 15486, 15487, 15488, 15489, 15490, 15491, 
15492, 15493, 15494, 15495, 15496, 15497, 15498, 15499, 15500, 
15501, 15502, 15503, 15504, 15505, 15506, 15507, 15508, 15509, 
15510, 15511, 15512, 15513, 15514, 15515, 15516, 15517, 15518, 
15519, 15520, 15521, 15522, 15523, 15524, 15525, 15526, 15527, 
15528, 15529, 15530, 15531, 15532, 15533, 15534, 15535, 15536, 
15537, 15538, 15539, 15540, 15541, 15542, 15543, 15544, 15545, 
15546, 15547, 15548, 15549, 15550, 15551, 15552, 15553, 15554, 
15555, 15556, 15557, 15558, 15559, 15560, 15561, 15562, 15563, 
15564, 15565, 15566, 15567, 15568, 15569, 15570, 15571, 15572, 
15573, 15574, 15575, 15576, 15577, 15578, 15579, 15580, 15581, 
15582, 15583, 15584), class = "Date"), value = c(3.32839119647413, 
3.34603352984559, 3.36355987402806, 3.38096991271589, 3.39826332960344, 
3.41543980838506, 3.43249903275512, 3.44944068640796, 3.46626445303796, 
3.48297001633945, 3.49955706000681, 3.51602526773439, 3.53237432321654, 
3.54860391014763, 3.56471371222201, 3.58070341313403, 3.59657269657806, 
3.61232124624846, 3.62794874583957, 3.64345487904576, 3.65883932956138, 
3.6741017810808, 3.68924191729836, 3.70425942190843, 3.71915397860536, 
3.73392527108351, 3.74857298303724, 3.76309679816091, 3.77749640014887, 
3.79177147269547, 3.80592169949509, 3.81996831865104, 3.83393095282951, 
3.84780686256915, 3.8615933084086, 3.8752875508865, 3.88888685054149, 
3.90238846791221, 3.91578966353732, 3.92908769795544, 3.94227983170523, 
3.95536332532531, 3.96833543935435, 3.98119343433097, 3.99393457079383, 
4.00655610928155, 4.0190553103328, 4.0314294344862, 4.0436757422804, 
4.05579149425404, 4.06777395094576, 4.07962037289422, 4.09132802063804, 
4.10289415471587, 4.11431603566636, 4.12559092402814, 4.13671608033986, 
4.14768876514016, 4.15850623896768, 4.16916576236107, 4.17966459585896, 
4.19, 4.20016543643947, 4.21015788364065, 4.21997987735426, 4.22963395333098, 
4.23912264732151, 4.24844849507654, 4.25761403234677, 4.26662179488289, 
4.2754743184356, 4.28417413875559, 4.29272379159356, 4.3011258127002, 
4.30938273782621, 4.31749710272227, 4.32547144313909, 4.33330829482736, 
4.34101019353778, 4.34857967502104, 4.35601927502782, 4.36333152930884, 
4.37051897361478, 4.37758414369634, 4.38452957530421, 4.39135780418908, 
4.39807136610166, 4.40467279679264, 4.4111646320127, 4.41754940751255, 
4.42382965904288, 4.43000792235439, 4.43597830457426, 4.44164594441166, 
4.44702992499026, 4.45214932943372, 4.4570232408657, 4.46167074240988, 
4.46611091718991, 4.47036284832946, 4.4744456189522, 4.47837831218178, 
4.48218001114187, 4.48586979895615, 4.48946675874826, 4.49298997364189, 
4.49645852676068, 4.49989150122831, 4.50330798016844, 4.50672704670473, 
4.51016778396086, 4.51364927506048, 4.51719060312725, 4.52081085128485, 
4.52452910265694, 4.52836444036718, 4.53233594753924, 4.53646270729677, 
4.54076380276345, 4.54525831706295, 4.54996533331891, 4.55490393465502, 
4.56009320419493, 4.56561236413086, 4.57150614324981, 4.57774188456758, 
4.58428693110001, 4.59110862586293, 4.59817431187215, 4.6054513321435, 
4.61290702969281, 4.62050874753589, 4.62822382868858, 4.63601961616669, 
4.64386345298605, 4.65172268216249, 4.65956464671182, 4.66735668964988, 
4.67506615399248, 4.68266038275545, 4.69010671895461, 4.69737250560579, 
4.70442508572481, 4.7112318023275, 4.71775999842968, 4.72397701704717, 
4.7298502011958, 4.73534689389139, 4.74043443814976, 4.74508017698675, 
4.74925145341816, 4.75291561045984, 4.75603999112759, 4.75859193843725, 
4.7604250490315, 4.76145561043944, 4.76174500200653, 4.76135460307825, 
4.76034579300006, 4.75877995111741, 4.75671845677578, 4.75422268932063, 
4.75135402809742, 4.74817385245162, 4.74474354172869, 4.7411244752741, 
4.7373780324333, 4.73356559255178, 4.72974853497498, 4.72598823904837, 
4.72234608411742, 4.71888344952759, 4.71566171462435, 4.71274225875316, 
4.71018646125949, 4.70805570148879, 4.70641135878653, 4.70531481249819, 
4.70482744196921, 4.70501062654508, 4.70592574557124, 4.70763417839317, 
4.71019730435632, 4.7137826631524, 4.71846196054287, 4.72415282497784, 
4.73077288490742, 4.73823976878173, 4.74647110505086, 4.75538452216495, 
4.76489764857409, 4.77492811272841, 4.785393543078, 4.79621156807299, 
4.80729981616349, 4.8185759157996, 4.82995749543145, 4.84136218350913, 
4.85270760848277, 4.86391139880248, 4.87489118291836, 4.88556458928053, 
4.8958492463391, 4.90566278254418, 4.91492282634589, 4.92354700619434, 
4.93145295053963, 4.93855828783188, 4.94478064652121, 4.95003765505772, 
4.95424694189153, 4.95732613547274, 4.95919286425147, 4.95976475667784, 
4.95904874276869, 4.95715495083234, 4.95415580675609, 4.95012373642723, 
4.94513116573307, 4.9392505205609, 4.93255422679801, 4.92511471033171, 
4.9170043970493, 4.90829571283806, 4.89906108358531, 4.88937293517833, 
4.87930369350443, 4.8689257844509, 4.85831163390504, 4.84753366775415, 
4.83666431188552, 4.82577599218646, 4.81494113454426, 4.80423216484621, 
4.79372150897963, 4.78348159283179, 4.77358484229001, 4.76410368324158, 
4.7551105415738, 4.74667784317395, 4.73887801392936, 4.7317834797273, 
4.72546666645508, 4.72, 4.7153114071749, 4.71124993887287, 4.70776970710155, 
4.70482482386858, 4.7023694011816, 4.70035755104826, 4.69874338547619, 
4.69748101647305, 4.69652455604647, 4.69582811620409, 4.69534580895356, 
4.69503174630252, 4.69484004025861, 4.69472480282947, 4.69464014602275, 
4.69454018184609, 4.69437902230714, 4.69411077941352, 4.69368956517289, 
4.69306949159289, 4.69220467068115, 4.69104921444533, 4.68955723489307, 
4.687682844032, 4.68538015386977, 4.68260327641403, 4.6793063236724, 
4.67544340765255, 4.6709686403621, 4.6658361338087, 4.66, 4.65348013986565, 
4.64635174642032, 4.63865186979916, 4.63041756013732, 4.62168586756994, 
4.61249384223219, 4.6028785342592, 4.59287699378613, 4.58252627094812, 
4.57186341588033, 4.56092547871791, 4.549749509596, 4.53837255864976, 
4.52683167601433, 4.51516391182486, 4.50340631621651, 4.49159593932442, 
4.47976983128375, 4.46796504222963, 4.45621862229723, 4.44456762162169, 
4.43304909033816, 4.42170007858178, 4.41055763648772, 4.39965881419112, 
4.38904066182713, 4.37874022953089, 4.36879456743757, 4.3592407256823, 
4.35011575440023, 4.34128184602259, 4.33257248392019, 4.32398165463758, 
4.31550334471933, 4.30713154070999, 4.29886022915413, 4.2906833965963, 
4.28259502958106, 4.27458911465297, 4.26665963835659, 4.25880058723648, 
4.2510059478372, 4.2432697067033, 4.23558585037935, 4.22794836540991, 
4.22035123833953, 4.21278845571277, 4.20525400407419, 4.19774186996835, 
4.19024603993981, 4.18276050053313, 4.17527923829286, 4.16779623976357, 
4.16030549148982, 4.15280098001616, 4.14527669188715, 4.13772661364735, 
4.13014473184133, 4.12252503301363, 4.11486150370883, 4.10714813047147, 
4.09942747484561, 4.09174571939962, 4.08410228221451, 4.07649658137128, 
4.06892803495094, 4.06139606103451, 4.05390007770298, 4.04643950303737, 
4.03901375511869, 4.03162225202794, 4.02426441184614, 4.01693965265429, 
4.0096473925334, 4.00238704956449, 3.99515804182855, 3.98795978740661, 
3.98079170437966, 3.97365321082872, 3.96654372483479, 3.95946266447889, 
3.95240944784202, 3.94538349300519, 3.93838421804941, 3.93141104105569, 
3.92446338010504, 3.91754065327846, 3.91064227865698, 3.90376767432158, 
3.89691625835329, 3.89008744883311, 3.88328066384205)), .Names = c("date", 
"value"), row.names = c(NA, -367L), class = "data.frame")

query <- structure(list(ID = 1:10, value = c(3.5, 4.2, 4.5, 4.4, 4.7, 
4.8, 5.1, 4.9, 4.1, 3.7)), .Names = c("ID", "value"), row.names = c(NA, 
-10L), class = "data.frame")

Dynamic time warping:

library(dtw)

# symmetric2 is used as a default step.pattern
DTW <- dtw(query$value, reference$value, keep = TRUE)     
matched <- data.frame(Date = reference$date[DTW$index2], ID = query$ID[DTW$index1], value = query$value[DTW$index1])

library(plyr)

matched.plot <- ddply(matched, c("ID", "value"), summarize, date = mean(Date), date.min = min(Date), date.max = max(Date))

library(ggplot2)

ggplot() + geom_line(data = reference, aes(x = date, y = value)) +
geom_errorbarh(data = matched.plot, aes(x = date, y = value, xmin = date.min, xmax = date.max), color = "red", height = 0) +
geom_text(data = matched.plot, aes(x = date, y = value, label = ID), color = "red")

In figure above query index ID's 6, 7 and 8 are assigned to the same reference index value. I would like to avoid that. I have tried about every single step pattern available in dtw package. Either I have understood something wrong or I have not found a step pattern, which would allow assignment of several query index values to one reference index value, but not vice versa.

Is it theoretically possible to implement such a step pattern algorithm? If yes, any suggestions how to do it would be highly appreciated.

Answer 1

If I understand, you wish that each element of reference is paired to a distinct element of query. This is normally achieved with the asymmetric step pattern (see e.g. http://staffwww.dcs.shef.ac.uk/people/S.Wrigley/com326/asym.html). Note that reference would be on the horizontal axis (it's easy to get confused).

Your specific case, however, is more tricky because query is ~40 times shorter than the other timeseries; the asymmetric pattern, which limits the local slope between 0 and 2, allows no solution.

It happens that your request might be approximately accommodated by Latecki's Minimum Variance Matching (MVM) algorithm (think of it as an "infinite slope" variant of the asymmetric algorithm). See the papers An elastic partial shape matching technique, doi:10.1016/j.patcog.2007.03.004, Section 3.8 of http://www.jstatsoft.org/v31/i07/, and ?mvmStepPattern.

In short:

al<-dtw(query$value,reference$value,keep=T,step=mvmStepPattern(100))
dtwPlotThreeWay(al,match=10,type.align="o")