§ 3. D-алгоритм для таксономии траекторий

Если в моменты времени  наблюдаются не один, а несколько  процессов или объектов, описываемых  характеристиками, то протокол наблюдений представляет собой «куб данных» размером . Каждый объект за время  описывает в пространстве  свойств некоторую -мерную траекторию. Если мы хотим выделить подмножества (таксоны) объектов с одинаковыми или похожими траекториями, то нам нужно найти расстояния между всеми парами траекторий и применить один из алгоритмов таксономии. В простейшем случае в каждый момент времени можно вычислить евклидово расстояние между двумя объектами и сумму этих расстояний за все время  считать мерой расстояния между двумя траекториями.

Однако нередко встречаются случаи, когда похожие по своей природе процессы протекают с разной скоростью, и тогда простое совмещение их во времени даст большое значение расстояния. Иногда похожие процессы начинают наблюдаться в разные фазы их развития и не ясно, какие участки двух процессов совмещать друг с другом при вычислении расстояния между ними.

Именно для таких сложных случаев был разработан D-алгоритм [87]. Его основное отличие состоит в том, что при определении расстояния между траекториями применяется описанный выше метод динамического программирования, при котором сдвигается начало процесса и нелинейно растягивается или сжимается одна траектория по оси времени с целью получения наилучшего совмещения двух траекторий. Величина, пропорциональная усилию по деформации оси времени, служит мерой расстояния между траекториями. В результате среди кривых, приведенных на рис. 44, удается в один таксон поместить кривые 1 и 3, а кривые 2 и 4 — во второй. Это выглядит более естественно по сравнению с вариантом объединения в один таксон кривых 1 и 2 что получилось бы без динамического программирования.

Рис. 44

D-алгоритм может быть полезным для анализа сложных динамических процессов, например процессов протекания различных заболеваний у групп больных, состояния которых наблюдаются в последовательные моменты времени. При этом одно и то же заболевание протекает у разных больных по-разному (с разной скоростью в разные фазы болезни), наблюдения за больными начинаются в разные фазы болезни. D-метод позволяет синхронизировать наблюдаемые процессы, определять фазу заболевания и прогнозировать наиболее вероятное состояние больного в следующие моменты времени.