Использование методов анализа данных при разработке адаптивного драйвера манипулятора тема диссертации и автореферата по ВАК РФ 05.13.17, кандидат наук Пономарев, Дмитрий Иванович

• Пономарев, Дмитрий Иванович
• кандидат наук
• 2013

Оглавление диссертации кандидат наук Пономарев, Дмитрий Иванович

СОДЕРЖАНИЕ

Введение

Актуальность темы

Цель работы

Методы исследования

Практическая значимость исследования

Положения, выносимые на защиту

Глава 1. Проблемы разработки драйвера дистанционного манипулятора на

основе МЕМБ-акселерометра и задачи анализа данных

Глава 2. Использование ЕМ-алгоритма в Байесовской фильтрации

управляющих сигналов манипулятора

Линейная динамическая система с дискретным временем

Сглаживающий фильтр Калмана

ЕМ-алгоритм

ЕМ-алгоритм для ЛДС с дискретным временем

Использование ЕМ-алгоритма для обучения нелинейной динамической системы с

дискретным временем

Нелинейная Байесовская фильтрация управляющих сигналов манипулятора

Глава 3. Использование ЕМ-алгоритма в Марковской модели непрерывного

профиля для синхронизации сигналов манипулятора

Марковская модель непрерывного профиля

Обучение модели посредством ЕМ-алгоритма

Синхронизация сигналов манипулятора

Глава 4. Использование метода Прони и методов обнаружения паттернов в компонентах управляющих сигналов манипулятора для идентификации жестов

оператора

Аппроксимация сегментов временных рядов по методу Прони

Использование алгоритмов сокращения размерности пространства поиска для

обнаружения паттернов временного ряда

Обнаружение паттернов в записях сигналов дистанционного манипулятора с

прецизионным акселерометром

Использование алгоритма для обнаружения паттернов

Глава 5. Использование ЕМ-алгоритма для абстракции данных при обнаружении синхронных паттернов - жестов оператора в трехмерных

управляющих сигналах манипулятора

Алгоритм /С-средних в оптимизационной постановке

Алгоритм К-теап$++

Кластеризация данных на основе ЕМ-алгоритма

Алгоритмы поиска последовательных эпизодов

Обнаружение паттернов управляющего сигнала дистанционного манипулятора на

основе абстракции данных

Ускорения вычислений при обнаружении паттернов многомерных временных рядов с

использованием ЫУЮ1АСийА

Анализ главных компонент

Анализ независимых компонент

Заключение

Список использованных источников

Введение диссертации (часть автореферата) на тему «Использование методов анализа данных при разработке адаптивного драйвера манипулятора»

Введение

Актуальность темы

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

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

Для этого решаются следующие задачи:

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

2. выявление на основе моделей требуемых характеристик вычислительных алгоритмов и комплексов программ;

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

В работе используются: линейная и нелинейная Байесовская фильтрация, фильтр Калмана, скрытая Марковская модель, алгоритм ожидания и максимизации правдоподобия, спектральный метод Прони, алгоритм динамического искажения времени, алгоритмы поиска повторяющихся последовательностей, алгоритм Mueen-KeoghMotiffii sco very, абстракция данных, алгоритм k-means, k-means++, алгоритмы поиска повторяющихся эпизодов, анализ независимых компонент, кластеризация на основе алгоритма ожидания и максимизации правдоподобия.

Научная новизна полученных результатов

Научная новизна диссертационного исследования состоит в следующем:

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

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

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

паттернов в многомерных временных рядах с использованием кластеризации на основе алгоритма ожидания и максимизации правдоподобия. 4. Показано, что анализ независимых компонент позволяет сокращать размерность временных рядов при поиске паттернов в результате абстракции данных.

Практическая значимость исследования

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

Положения, выносимые на защиту

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

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

3. Метод обнаружения паттернов в многомерных временных рядах на основе абстракции данных. Абстракция данных осуществляется при помощи кластеризации с использованием алгоритма ожидания и максимизации правдоподобия.

4. Метод сокращения размерности временных рядов на основе анализа независимых компонент при поиске паттернов в результате абстракции данных.

Глава 1. Проблемы разработки драйвера дистанционного манипулятора на основе MEMS-акселерометра и задачи анализа данных

В последнее время получают широкое распространения датчики, произведенные по технологии MEMS. Это объясняется их низкой стоимостью, маленькими размерами и низким энергопотреблением. Такие датчики устанавливаются в мобильных телефонах, ноутбуках, автомобилях, игровых манипуляторах и т.д. Самыми распространенными из них являются акселерометры и гироскопы. В данной работе рассматривается задача разработки манипулятора, отслеживающего движения руки оператора в пространстве, чувствительным элементом которого является MEMS-акселерометр. В процессе разработки такого устройства возникают задачи фильтрации электрических шумов датчиков, а также шумов, связанных с физиологическим дрожанием руки оператора. Кроме того, рассматривается задача обнаружения жестов руки оператора. Это может найти свое применение в качестве одного из способов управления различными элементами операционной системы или приложений при помощи жестов.

В качестве чувствительного элемента устройства, предназначенного для отслеживания движений руки оператора в пространстве, используется MEMS-акселерометр. Это устройство используется как дистанционный манипулятор, например, для управления курсором стандартной компьютерной мыши [1-2]. Внешний вид манипулятора показан на рис. 1.1 (1 и 2, соответственно, две кнопки управления, которые используются как левая и правая кнопка компьютерной мыши, 3 - крепление, при помощи которого это устройство фиксируется на руке оператора).

Рис. 1.1. Внешний вид манипулятора.

Конструкция манипулятора позволяет его легко одевать и снимать, а также производить печать на клавиатуре компьютера, не снимая манипулятор с руки. Блок схема устройства изображена на рис. 1.2.

3

Рис. 1.2. Блок схема устройства.

Основная электронная часть устройства реализована на одной печатной плате (рис. 1.3).

Рис.1.3. Электронная часть манипулятора.

Чувствительным элементом манипулятора (номер 4 на рис. 1.3) является МЕМ8-акселерометр ММА7260()[3]. Данные от акселерометра

оцифровываются при помощи АЦП (номер 2 на рис. 1.3) и далее обрабатываются в микроконтроллере (номер 1 на рис. 1.3). В микросхеме используется преобразователь напряжения (номер 5 на рис. 1.3), т.к. напряжение питания элементов схемы составляет 3.3 В, а напряжение питания от USB - 5 В. Номер 6 на рис. 1.3 - кварцевый генератор, а 3 - мультиплексор. Устройство подключается к компьютеру через разъем microUSB (номер 7 на рис.1.3).

Акселерометр MMA7260Q компании FreescaleSemiconductor имеет три чувствительные оси и способен работать в различных диапазонах ускорений: ±1.5g, ±2g, ±4g, ±6g. Функциональная блок-диаграмма акселерометра показана на рис. 1.4.

g-Selectt о-g-Select2 о-

Sieep Mode с

G-Cell Sensor

Oscillator

Clock Generator

С to V Conve-ter

Gain

Filter

X-Temp Comp

Control Logic EEPROM Trim Circuits

Y Temp Comp

Z-Temp Comp

Х01Л

O Yqut

-О ZouT

Vss

Рис. 1.4. Функциональная диаграмма акселерометра ММА7260().

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

чувствительность для диапазона ± 1.5g составляет 800

мВ

g

, a VcdRU =1.655.

Типичная схема подключения данного акселерометра показана на рис. 1.5а. Выходы акселерометра подключаются к входам АЦП через ЯС фильтр для минимизации шума тактового генератора. Акселерометр позволяет измерять ускорения по трем взаимно перпендикулярным направлениям (рис. 1.56).

POWER SUPPLY

V»

Sleep Mod«

g-Se!ec11 9-Se!«t2

Ж I

YOUI

Zout

—0-

—4Ш-

Vrh %>

PO vss

Pi S

п g

"О* e a

s

М>ц

a)

Рис.1.5. Схема подключения МЕМ8-акселерометра и его чувствительные

оси.

Сигнал МЕМБ-акселерометра в состоянии покоя содержит аддитивный шум [4, 5]. Кроме того, на уровень шума сигнала, получаемого микроконтроллером, оказывают влияние электрические шумы в цепи питания акселерометра, а также шумы АЦП-преобразования. Рис. 1.6 пунктиром показывает график фактических значений сигнала, когда МЕМБ-акселерометр расположен статически на жесткой поверхности. Сплошная черная линия показывает отфильтрованные данные, очищенные от ошибок и шума АЦП-преобразования.

900 1000

Рис.1.6. График фактических значений сигнала МЕМ8-акселерометра и

результат фильтрации.

Проблема фильтрации сигнала МЕМБ-акселерометра в состоянии покоя посредством линейного фильтра Калмана рассматривается в [6].

На рис. 1.7 показано, как устройство крепится на руке пользователя.

Рис.1.7. Манипулятор в руке пользователя.

Ниже приведены данные с одной из чувствительных осей акселерометра, снятых с интервалом дискретизации времени 5 мс (рис. 1.8). Ускорение измеряется в единицах g.

Рис.1.8. Записи сигналов с двух чувствительных осей акселерометра, полученные свременным интервалом 5 мс. Ускорение измеряется в

единицах g.

Сигнал МЕМ8-акселерометра при отслеживании движений руки оператора содержит аддитивный шум. Причиной этого шума является дрожания руки оператора. Чтобы оценить, насколько важна фильтрация шума, производимого процессом физиологического дрожания руки оператора, рассматриваются основные характеристики этого процесса. Проведена серия

измерений, в которых рука операторов с рассматриваемым манипулятором фиксировалась в заданном положении (рис. 1.9).

0.04 003 0.02 0.01 0

-001 -0.02 -0.03 -0.04

I

Рис.1.9. Шум, производимый процессом физиологического дрожания руки оператора. Ускорение измеряется в единицах g.

Анализ записи сигнала на рис. 1.9 показывает, что среднеквадратичное отклонение проекции ускорения на одну из чувствительных осей акселерометра

составляет (8.1 ± 2.3) • 10"2 м/2 • Среднеквадратичное отклонение для монитора с

разрешением в 1280 пикселей составляет величину, равную примерно 8 пикселей. То есть задача фильтрации шума, вызванного процессом физиологического дрожания руки оператора, для рассматриваемого манипулятора является весьма существенной. Как показано в [1, 2], этот шум может быть отфильтрован с использованием линейного фильтра Калмана (рис. 1.10). Использование нелинейного фильтра Калмана при отслеживании движений руки пользователя представлено в [10].

ах

05

0 4 03 0.2 О 1 О -О 1 -0 2 -03 -0 4

___

\

J '1л

I

f 1

10

12

14 15

t,C

Рис.1.10. Временная зависимость проекции ускорения g силы тяжести на чувствительную ось л: акселерометра после линейной фильтрации по Калману.Ускорения измеряется в единицах g.

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

( Stat tiave to S*

Plotter

Patterns

/ ¡1 >7 / _,

а :/ I!

7 / I

2 800 2 850 2 950

Points

Рис.1.11. Рабочее окно программы по отслеживанию жестов руки

оператора.

Разрабатываемое устройство способно отслеживать жесты руки оператора. Отслеживание жестов осуществляется при помощи разработанного программного обеспечения, пример рабочего окна программы показан на рис. 1.11. В левой части рабочего окна программы отображается сигналв режиме реального времени, получаемого от акселерометра, а в правой части -обнаруженные паттерны.

В следующих главах рассматриваются задачи, которые возникают при разработке драйвера такого класса устройств. В главе 2 рассматривается задача фильтрации данных; в главе 3 задача выравнивания и синхронизации сигналов,получаемых от независимых датчиков; в главе 4 задача поиска паттернов в одномерных,а в главе 5 задача поиска паттернов в многомерных управляющих сигналах манипулятора.

Глава 2. Использование ЕМ-алгоритма в Байесовской фильтрации управляющих сигналов манипулятора

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

Рис.2.1. Шум, производимый процессом физиологического дрожания руки

оператора.

Анализ полученных измерений показал, что среднеквадратичная

_2 М

амплитуда шума составила (8.1 ±2.3)-10 —. Стоит отметить, что амплитуда

с

шума зависит от физиологического состояния оператора, а также варьируется от оператора к оператору. А спектральный анализ по методу Фурье показывает, что наибольшая спектральная плотность мощности сигнала лежит в диапазоне от 9 до 12 Гц (рис. 2.2). Полученный результат согласуется с результатами работы [11]. В этой работе установлено, что частота физиологического дрожания руки типичного оператора лежит в диапазоне от 8 до 15 Гц.

Рис.2.2. Спектр управляющего сигнала

Рабочий диапазон углов отклонений осей от направления ускорения силы тяжести для рассматриваемого манипулятора составляет ±40°, или в масштабе

м

ускорения силы тяжести 2gsin(p = 12.6—. Поэтому среднеквадратичное

с

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

Существует множество работ, в которых предлагаются различные способы фильтрации шума, вызванного физиологическим дрожанием руки оператора. Ряд таких работ посвящен фильтрации на основе адаптивного алгоритма наименьших квадратов, в которых процесс физиологического дрожания моделируется линейной комбинацией синусов и косинусов, с различной частотой в диапазоне от 8 до 15 Гц. Например, в работе [12] предложен алгоритм WFLC fWeighted-FrequencyFourierLinearCombiner^), в котором процесс физиологического дрожания руки оператора моделируется линейной комбинацией синусов и косинусов с различными значениями фазы, но одинаковой частоты. Адаптация осуществляется как по амплитуде шума, так и по частоте. Вработе [13] предложеналгоритмВАВМРЪС(0оиЬ1е Adaptive band limited multiple Fourier linear combiner). Его основное отличие от предыдущего алгоритма в том, что синусы и косинусы в линейной комбинации имеют различную частоту в заданном диапазоне. Данные алгоритмы работают в режиме реального времени, достаточно просты в реализации и вычислительно недороги.

Также существуют работы, в которых предлагается использовать фильтр Калмана. В частности, в работе [14] используется расширенный фильтр Калмана, для фильтрации патологического дрожание руки оператора. Стоит отметить, что модель для фильтра задается априори и основана также на моделировании дрожания руки как набора синусов и косинусов.

В данной работе предлагается использовать нелинейную Байесовскую фильтрацию, модель для которой не задается априори, а строится при помощи алгоритма ожидания и максимизации правдоподобия. Построение фильтра Калмана тесно связано с понятием динамической системы. Рассмотри вначале линейную динамическую систему с дискретным временем.

Линейная динамическая система с дискретным временем При описании линейной динамической системы (ЛДС) ключевым является понятие вектора состояния. Обозначим его как х[&]. Вектор состояния, можно определить как минимальный набор данных, необходимый для однозначного описания поведения системы. Или же, как минимальный набор данных о предыдущем поведении системы, которые необходимы для определения его будущего поведения.

Обозначим через у[/с] вектор, составленный из непосредственно наблюдаемых данных. Тогда ЛДС с дискретным временем можно описать следующей системой уравнений:

где введены следующие обозначения:

• +1] - матрица перехода из состояния х[£] в состояние х[£ +1].

• Шум процесса аддитивный белый гауссов шум с нулевым средним

т ГСШ,п = к

значением и ковариационной матрицей £[>у[я](\у[£]) ] = <

[О,« Ф к

• Н[&] - матрица измерений переводит вектор состояния х[£] в непосредственно наблюдаемый вектор у[£].

• Шум измерений также аддитивный белый гауссов шум с нулевым средним значением и ковариационной матрицей

Шум измерений у[&]и шум процесса считаются

некоррелированными между собой. Для использования алгоритма ожидания и максимизации правдоподобия нам понадобится описание сглаживающего фильтра Калмана [15].

Сглаживающий фильтр Калмана

Пусть имеется набор измерений на временном интервале 0 < к < N. Для построения оптимальной оценки будем использовать как данные прошлых измерений у [/], где 0< / < к, так и данные «будущих» измерений у [у], где к < j <Ы. При этом N считается фиксированным. Таким образом, задача сглаживания не является задачей реального времени.

Сглаживающий фильтр Калмана использует прямую и обратную рекурсию. Прямая рекурсия фильтра Калмана дает оценку состояния х/[^]. Обратная рекурсия посредством «информационного» фильтра дает оценку хА[&]. Комбинация этих двух оценок дает окончательную оценку х[&]. При сглаживании имеется возможность использовать данные «будущих» измерений. Это позволяет уменьшить ковариационную матрицу Р[/с]

(сплошная линия) по сравнению с ковариационной матрицей Р (пунктирная линия) прямой рекурсии фильтра Калмана (рис. 2.3).

Information filter

ь-

/

/

/

Error

со vari anee

Kaiman filter P*"

Smoother covariante Pt

0 Time/. A'

Рис. 2.3. Поведение ковариационной матрицы при прямой и обратной

рекурсии и сглаживании.

Далее приведен алгоритм работы сглаживающего фильтра Калмана. Вывод данных соотношений приведен в [15].

1. Прямая рекурсия Инициализация

х[0] = ВДО]], Р[0] = £[(х[0] - £[х[0]])(х[0] - £[х[0]])г].

Для к = 1, ..,N

xf~[k] = F[k]xf[k-1],

V'-[k] = ВДР'[£ - l](F[^])r + Q[* -1],

Gf[k] = + R[*]]"',

xf[k] = xf'[k] + G/[A:](y[*:] - Щ*]*'"^]),

?S[Jc] = (I - G[A:]H[yt])P/_[A:].

2. Обратная рекурсия Инициализация P[N] = Р7[ЛП, x[N] = x7[TV]. Для k= N- 1,7V-2, ...

A [k] = Vf[k](F[k + l])r[P/-[£ +1]]"1,

P[£] = Pf[k] - A[£](P/_[£ +1] - P[k + l])(A[&])r,

x[£] = kf[k] + A[fc](x[£ +1] - xf~[k +1]).

ЕМ-алгоритм

ЕМ-алгоритм - это метод нахождения максимума правдоподобия P{Y \ в) наблюдаемых данных Г={у[1],у[2],...,у[7У]} в модели со скрытыми параметрами X = {x[l],x[2],...,x[7V]} и в - параметры модели. Максимизация правдоподобия, как функции в эквивалентно максимизации логарифма правдоподобия:

Цв) = log P(Y | в) = log J'P(X, Y | Q)dX. (2.2)

X

Используя произвольное распределение скрытых параметров Q(X), получим нижнюю границу L{0):

log \P{Y,X 16)dX = log \Q{X)P{XJ\6) dX x x Q{X)

B Q{X) .(2.3)

= \Q{X)\ogP{XJ\e)dX- \Q(X)\ogQ{X)dX

X X

= F{Q,6)

Если мы определим энергию конфигурации (X, Y) как \ogP(X,Y | в), тогда нижняя граница F(Q,6) < L{9) - это величина, известная в статистике как свободная энергия, только взятая с обратным знаком.

Это итеративный алгоритм, который состоит из Е-шага и М-шага. На Е-шаге выполняется максимизация F(Q,0), как функции Q, при фиксированных параметрах системы 0:

Е-шаг: Q[k +1] а^тах,Р(0Д£]). (2.4)

Q

На М-шаге выполняется максимизация F(Q,6), как функции в, при фиксированном распределении Q, полученном на Е-шаге:

М-шаг: в[к +1] <- argmaxF(Q[k +1],в). (2.5)

в

Легко показать, что максимум на Е-шаге достигается, когда Q в точности совпадает с условным распределением X:

Q[k + l]'(X) = P(X\r,0[k]).(2.6)

В таком случае, выполняется равенство F(Q[k + !]*,#[&]) = L(6[k\). Максимизация на М-шаге достигается путем максимизации первого члена в (2.3), т.к. энтропия не зависит от параметров системы в:

М-шаг: в[к +1]* <-argmax j>(X | Y,0[k])\ogP(X,Y 16)dX. (2.7)

в x

Данное соотношение наиболее часто ассоциируют с ЕМ-алгоритмом. Оно имеет элегантную интерпретацию - это метод покоординатного спуска (рис. 2.4).

Яр,©;

ООО

Рис. 2.4. Представление ЕМ-алгоритма, как метода покоординатного

спуска

ЕМ-алгоритм для ЛДС с дискретным временем

Получим явные формулы, описывающие ЕМ-алгоритм для ЛДС с дискретным временем.Используя уравнения (2.1), описывающие ЛДС с дискретным времени, запишем условные плотности:

Р(у[к] I х[к]) = ехр{-^[у[к] - Нх[£]]г - Нх[£]]}(2тг)~2 | Я р, (2.8)

1 -I -1

Р(х[&] | х[к — 1]) = ехр{-—[х[&] — Ех[& — 1]]гО_1[х[&] — Ех[А: — 1]]}(2л") 2|0| 2, (2.9)

где р - размерность вектора наблюдаемых данных, а / - размерность вектора состояний.В силу условия марковости процесса:

П{х},{у}) = />(х[1])ПР(х[*] I Лк ~ 1])ПР(у[к] | х[*]). (2.10)

к =2

к=I

Предполагая, что плотность начального состояния Гауссова, запишем: Р(х[1]) = ехр{-|[х[1] - я[1]]гУ[1Г'[х[1] - я[1]]}(2,г)~2 | У[1] 2, (2.11)

где 7г[1]— начальное значение вектора состояния и У[1] - начальное значение ковариационной матрицы. Тогда логарифм правдоподобия:

Ь = 1о8 Р{ {X}, {у}) = (I (у[к] - Нх[*])г И-1 (у[к] - Нх[*]))

к=1 ^

4юв I и I - ¥х[к -1])Г<Г' (х[к] - Гх[/с -1]))

2 к=2 1 .(2.12)

IОI -±(х[1] - я[1])гУ[1Г'(х[1] - я[1])

1. 1ТГг,л1 N(0 + 1). „ --1оё|У[1]|----\og27T

Е-шаг, рассматриваемого ЕМ-алгоритма, предполагает вычисление ожидаемого логарифма правдоподобия:

1 = £[1оёР({х},{у})|{у}].(2.13)

Для этого при помощи сглаживающего фильтра вычисляются следующие математические ожидания:

Е[х[к] | {у}], £[х[£](х[£])г |{у}], Е[х[к]{х[к - 1])г | {у}].

Опишем М-шаг. Параметры линейной динамической системы Г,Н,Я^,я[1],У[1]. Каждый из параметров и начальное значение вектора состояния и ковариационной матрицы повторно оценивается, беря частную производную ожидаемого логарифма правдоподобия (2.13), приравнивая ее к нулю и решая (аналитически) полученное уравнение.

М-шаг: • Матрица измерений:

дь_ эн

= -Хи-'у^КВД)7" + 2Х'НВД = О

к=\ к=I

к=1 к=1 • Ковариационная матрица измерений:

= ■- - НВД№])Г + ^нвднг) = о

дЬ N.

ЭЫ1 2 £Г2

= 77 2>№Ш])Т - Н"е,,ВД(у[£])г).

N уЫ

Матрица перехода:

ñf N N —=-XQ-'ВД+£Q_,FP[* - Ц=■0

k=2 k=2

N N

F^CXp^x^P^-I])-1.

k=2 k=2

• Ковариационная матрица шума процесса: dL N-1 1 "

5Q-' 2 2 A=2

dL N-1

Q - -¿ДО] - FP[k - !][£] - P[k][k - l]Fr + FV[k - l]Fr) = 0

5Q"1 2 ^ 2 ,=2 <r=ттЦ" (Z ВД - F- X P[к -1] [k]).

A — 1 k=2 k=2

Начальное значение вектора состояния:

81 =(х[1]-я[1])У[1Г'=0

дл[\]

л[\Г" = к[1].

• Начальное значение ковариационной матрицы:

31 =^V[1]-^(P[1]-X[l](7t[l])r -7Т[1](Х[1])Г +7Г[1](7Г[1])Г)

ЭУ[1]"' 2 L J 2

V[l]"ew = P[l] - x[l](x[l])r.

Полученные соотношения для обучения линейной динамической модели используется как первый этап при обучении нелинейной динамической модели.

Использование ЕМ-алгоритма для обучения нелинейной динамической системы с дискретным временем.

Нелинейная динамическая система в дискретном времени описывает эволюцию состояния х[£ +1] <— х[£] на одном временном шаге и текущую связь входа х[£],и[£] с выходом у[£]

х[к +1] = f (x[£],u[£]) + w[k],

,(2.14) y[*] = g(x[*M*]) + v[*]

где w[£] и v[fc] - Гауссовы шумовые процессы с нулевым средним. Вектор состояния х[А:] эволюционирует в соответствии с нелинейной, но стационарной Марковской динамикой, производимой входом и [к] в присутствии шума w [к]. Выход у[£] нелинейный с шумом, но стационарный и является функцией текущего состояния х[£] и текущего входа и[&]. Нелинейные вектор-функции f(.) и g(.) предполагаются дифференцируемыми. Ниже на E-шаге (ЕМ-

алгоритма) для оценки приблизительного распределения скрытых состояний нелинейной системы (2.14) используется расширенный сглаживатель Рауха, а на М-шаге для нелинейной регрессии вектор-функций f (.) и g(.) используются

радиальные базисные функции (radial basis function - RBF) [16, 17]. Два условных распределения вероятности

Р(х[А:]и[1],...,и[Л^],у[1],...,у[Ж]и = 1,Ж

, ч -'(2Л5)

являются основными на Е-шаге для определения последовательности скрытых состояний нелинейной системы (2.14) на основе последовательностей наблюдаемых выходов {у[1],---,у[А^]} и входов {и[1],...,и[А^]}. Условные

распределения (2.15) являются не Гауссовыми, поэтому уравнения вывода не могут быть представлены в замкнутой форме. Более того, объемы вычислений растут экспоненциально с увеличением длины наблюдаемых временных рядов. Расширенный сглаживатель Рауха аппроксимирует стационарную нелинейную динамическую систему (2.14) нестационарной, но линейной системой [18]. Он применяет стандартный сглаживатель Рауха к локальной линеаризации

нелинейной системы. В каждой точке х в пространстве состояний х, производные вектор-функций и g(.) определяют матрицы

F- = —

х Эх

и G- = — х дх

соответственно. Уравнения (2.14) линеаризуются в окрестности х[&] средней

текущей отфильтрованной (а не сглаженной) оценки состояния х[£] (в момент

24

времени к). Аналогично линеаризуется уравнение для выхода. Эти линеаризации дают уравнения

х[к +1]« f ft*], u[*]) + F- • (х[к) - ад) + w[к],

У [к] - g(x[*],u[*]j + G-x[k] • (ад - ад) +

Если распределения шума и априорные распределения скрытого состояния при к-1 Гауссовы, то, в линеаризованной системе (2.16), условное распределение вероятности скрытого состояния в произвольный момент времени при заданной последовательности входов и выходов также будет Гауссовым. Таким образом, сглаживатель Рауха может использоваться на линеаризованной системе (2.16) для вывода этого условного распределения. В противоположность линейному сглаживателю Рауха, в расширенном сглаживателе Рауха ошибка ковариации для оценки состояния и матрицы усиления Калмана зависит не только от наблюдаемых данных с текущим временным индексом. Более того, если система (2.16) стационарная, матрица усиления Калмана не сходится к значению, при котором сглаживатель Рауха функционирует как оптимальный фильтр Винера в стационарном состоянии.

Список литературы диссертационного исследования кандидат наук Пономарев, Дмитрий Иванович, 2013 год

Список использованных источников

1. Пономарев Д.И. Использование методов Байесовской фильтрации при обработке сигналов манипулятора / Информационные технологии: Модели и методы. Сборник научных трудов. М.: МФТИ. 2010. С.65-72.

2. Kukharenko B.G., Ponomarev D.I. Bayesian filtering of control signal of telerobotic manipulator with precise accelerometer // Проблемымашиностроенияиавтоматизации. 2011. № 1. С.72-76.

3. MMA7260Q XYZ three-axis low g acceleration sensor. Austin, Texas: Freescale Semiconductor, Inc. 2005.

4. Mohn-Yasin F., Korman C.E., Nagel D.J. Measurement of noise characteristics of MEMS accelerometers // Solid-State Electronics. 2003. V. 47. P.357-360.

5. Beeby S., Ensell G., Kraft M., White N. MEMS Mechanical Sensors. Boston, London: Artech House, Inc. 2004.

6. Zidek K., Liska O. Accelerometer tilt application with Kalman filter implementation //Transfer inovacii. 2010. No. 16. P.256-257.

7. Lee I., Yoon G.H., Park J., Seok S., Chun K., Lee K. Development and analysis of the vertical capacitive accelerometer // Sensors and Actuators. 2005. V. A 119. P.8-18.

8. Lyshevski S.E. Mems and Nems: Systems, Devices and Structures. Boca Raton, London, New York, Washington, D.C.: CRC Press LLC. 2002.

9. Leondes C.T. Mems/Nems Handbook Techniques and Applications. V. 4: Sensors and actuators. Springer. 2006.

10. Кухаренко Б.Г., Пономарев Д.И. Нелинейная Байесовская фильтрация многомерных временных рядов // Информационные технологии. 2011. № 6. С.33-39.

11. Elble R.J., Koller W.C., Tremor, John Hopkins Univ. Press, Baltimore, MD, 1985

12. Riviere C.N., Rader R.S., Thakor N.V. Adaptive real-time canceling of physiological tremor for microsurgery / Proceedings of 2nd Int. Symposium on

Medical Robotics and Computer Assisted Surgery. Baltimore, MD. 1995. P.89-96.

13. Veluvolu K.C, Latt W.T., Ang W.T. Double adaptive bandlimited multiple Fourier linear combiner for real-time estimation/filtering of physiological tremor// Biomedical Signal Processing and Control. 2009. V.l. P. 37-44.

14. Bo A.P.L., Poignet P., Geny C. Filtering Voluntary Motion for Pathological Tremor Compensation/ The 2009 IEEE/RSJ International Conference on Intelligent Robots and Systems. 2009. P.55-60.

15. Shumway R.H., Staffer D.S. An approach to time series smoothing and forecasting using the EM algorithm // J. Time Series Analysis. 1982.V.3. No.4. P. 253-264.

16. Moody J., Darken C. Fast learning in networks of locally-tuned processing units //Neural Computation. 1989. V.l. P.281-294.

17. Broomhead D.S., Lowe D. Multivariable functional interpolation and adaptive networks // Complex Systems. 1988. V.2. P.321-355.

18. Simon D. Optimal State Estimation: Kalman, H«, and Nonlinear Approaches. Hoboken, New Jersey: John Wiley & Sons, Inc. 2006.

19. Roweis S., Ghahramani Z. A unifying review of linear Gaussian models // Neural Computation. 1999. V.l 1. No 2. P.305-345.

20. Кухаренко Б. Г. Байесовская фильтрация в технологии спектрального анализа на основе быстрого преобразования Прони // Информационные технологии. 2010. № 8. С.36-42.

21. Orfanidis S.J. Optimum Signal Processing. An Introduction. 2nd Edition. Englewood Cliffs, NJ: Prentice-Hall. 1996.

22. Listgarten J., Neal R.M., Roweis S.T., Emili A. Multiple alignment of continuous time series / Ed. by Saul L.K., Weiss Y., Bottou L. Advances in Neural Information Processing Systems. Cambridge, MA: The MIT Press. 2005. V.17. P.5-13.

23. Dempster A.P., LairdN.M., Rubin D.B. Maximum likelihood from incomplete data via the EM algorithm // Proceedings of the Royal Statistical Society. 1976. P. 1-38.

24. Neal R., Hinton G. A view of the EM algorithm that justifies incremental, sparse, and other variants / Jordan M.I., ed. Learning in Graphical Models. Kluwer Academic Press. 1998. P.355-368.

25. Poritz A.B. Hidden Markov models: A guided tour / Proceedings of the IEEE Conference on Acoustics, Speech and Signal Processing (ICASSP). Morgan Kaufmann. 1988. P.7-13.

26. Listgarten J. Analysis of Sibling Time Series Data: Alignment and Difference Detection. PhD Thesis. University of Toronto: Graduate Department of Computer Science. 2007.

27. Oppenheim A.V., Schafer R.W. Discrete-Time Signal Processing. 2nd ed. Upper Saddle River, NJ: Prentice-Hall. 1999.

28. Dimitriadis D., Potamianos A., Maragos P. A comparison of the squared energy and Teager-Kaiser operators for short-term energy estimation in additive noise // IEEE Transactions on signal processing. 2009. V.57. No.7. P.2569-2581.

29. Витерби А. Границы ошибок для сверточных кодов и асимптотически оптимальный алгоритм декодирования // Некоторые вопросы теории кодирования. М.: Мир. 1970. С. 142-165.

30. Viterbi A.J. Convolutional codes and their performance in communication systems // IEEE Transactions on Communication Technologies. 1971. V.COM-19. P. 751-772.

31. Chiu В., Keogh E., Lonardi S. Probabilistic discovery of time series motifs // Proceedings of the 9th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. August 24-27, 2003. DC, Washington: ACM. 2003. P.493-498.

32. Ferreira P.G., Azevedo P.J., Silva C., Brito R. Mining approximate motifs in time series // Proceedings of the 9th International Conference on Discovery Science. Barcelona: Springer-Verlag. 2006. P.89-101.

33. Castro N., Azevedo P.J. Multiresolution motif discovery in time series // Proceedings of the SIAM International Conference on Data Mining (SDM 2010). American Statistical Association (ASA). 2010. P.665-676.

34. Weiss L., McDonogh R.N. Prony's method, Z-transform, and Pade approximation // SIAM Review. 1963. V.9. № 2. P. 145-149.

35. Porat В., Friedlander B. Performance analysis of a class of transient detection algorithms - a unified framework // IEEE Transactions on Signal Processing. 1992. V.40. No 10. P.2536-2545.

36. Sarkar Т.К., Pereira O. Using the matrix pencil method to estimate the parameters of a sum of complex exponentials // IEEE Antenna and Propagation Magazine. 1995. V.37. No 1. P.48-55.

37. Кухаренко Б.Г. Технология спектрального анализа на основе быстрого преобразования Прони // Информационные технологии. 2008. № 4. С.38-42.

38. Кухаренко Б.Г. Исследование по методу Прони динамики систем на основе временных рядов // Труды МФТИ. 2009. Т.1. № 2. С. 176-192.

39. Кухаренко Б.Г. Исследование режимов колебаний на основе численных решений нелинейных моделей // Проблемы машиностроения и надежности машин. 2011. № 2. С.22-30.

40. Cormen Т.Н., Leiserson С.Е., Rivest R.L., Stein С. Introduction to Algorithms. 2nd Edition. Cambridge, MA: McGraw Hill Book Company, The MIT Press. 2001.

41. Mueen A., Keogh E., Zhu Q., Cash S., Westover B. Exact discovery of time series motifs // Proceedings of the SIAM International Conference on Data Mining (SDM 2009). American Statistical Association (ASA). 2009. P.473^184.

42. Mueen A., Keogh E.J. Online discovery and maintenance of time series motifs // Proceedings of the 16th ASM SIGKDD Conference on Knowledge Discovery and Data Mining (KDD 2010), July 25-28, 2010. Washington, DC: ACM. 2010. P.1089-1098.

43. Mueen A., Keogh E.J. Online discovery and maintenance of time series motifs // Proceedings of the 16th ASM SIGKDD Conference on Knowledge Discovery and Data Mining (KDD 2010), July 25-28, 2010. Washington, DC: ACM. 2010. P.1089-1098.

44. Кухаренко Б.Г., Пономарев Д.И. Нелинейная Байесовская фильтрация многомерных временных рядов // Информационные технологии. 2011. № 6. С.33-39.

45. Бернштейн Н.А. О построении движений. М.: Медгиз. 1947.

46. Бернштейн Н.А. Очерки по физиологии движений и физиологии активности. М.: Медицина. 1966.

47. Niezen G., Hancke G.P. Gesture recognition as ubiquitous input for mobile phones // Devices that Alter Perception. Proceedings of Workshop DAP2008. Seoul, South Korea: SungkyunkwanUniversity.2008. P.16-19.

48. Sakoe H., Chiba S. Dynamic programming algorithm optimization for spoken word recognition // IEEE Transactions on Acoustics, Speech and Signal Processing. 1978. V.26. No 1. P.43-49.

49. Salvador S., Chan P. Toward accurate dynamic time warping in linear time and space//Intelligent Data Analysis. 2007. V.ll.No 5. P.561-580.

50. Tomasi G., Skov Т., van den Berg F. Correlation optimized warping and dynamic time warping as preprocessing methods for chromatographic data // Journal of Chemometrics. 2004. V.18. P.231-241.

51. Sart D., Mueen A., Najjar W., Keogh E., Niennattrakul V. Accelerating Dynamic Time Warping Subsequence Search with GPUs and FPGAs // Proceedings of IEEE ICDM. 2010. P. 1001-1006.

52. NVIDIA CUDA С Programming Guide. Version 4.0. Santa Clara, CA: NVIDIA Corporation. 2011.

53. Han J., Kamber M. Data Mining: Concepts and Techniques, 2nd ed. New York: Morgan Kaufmann Publishers. 2006.

54. Bouman C.A. CLUSTER: An Unsupervised Algorithm for Modeling Gaussian Mixtures. PurdueUniversity, West Lafayette: School of Electrical Engineering. 2005. P. 1-20.

55. Mannila H., Toivonen H., Verkamo A.I. Discovery of frequent episodes in event sequences // Data Mining and Knowledge Discovery. 1997. V.l. No.3. P.259-289.

56. Laxman S., Sastry P.S., Unnikrishnan K. Discovering frequent episodes and leaning hidden Markov models: A formal connection // IEEE Transactions on Knowledge and Data Engineering. 2005. V.l7. No. 11. P. 1505-1517.

57. Arthur D., Vassilvitskii S. K-means++: the advantages of careful seeding / SODA'07 Proceedings of the Eighteenth Annual ACM-SIAM Symposium on Discrete Algorithms. - Philadelphia, PA: SIAM Press. 2007. P.1027-1035.

58. Rissanen J., Information and Complexity in Statistical Modeling, Springer, 2007.

59. Левенштейн В.И. Двоичные коды с исправлением выпадений, вставок и замещений символов // Доклады Академии Наук СССР. 1965. Т. 163. № 4. С.845-848.

60. Jolliffe I.T. Principal Component Analysis. New York, Berlin, Heidelberg: Springer. 2002.

61. Papadimitriou S.,Sun J., Faloutsos C. Streaming pattern discovery in multiple time-series / Proceedings of the 31st Very Large Data Bases Conference (VLDB'05). Trondheim, Norway: VLDB Endowment. 2005. P.697-708.

62. Кухаренко Б.Г. Аккумулирующий анализ главных компонент потоков тензорных данных. Информационные технологии. 2013. № 2. Приложение. С. 1-32.

63. Кухаренко Б.Г., Пономарев Д.И. Обнаружение паттернов многомерных временных рядов на основе абстракции данных // Информационные технологии. 2013. № 4. С.28-34.

64. Cichocki A., Amari S. Adaptive Blind Signal and Image Processing: Learning Algorithms and Applications. Chichester, West Sussex, UK: John Wiley & Sons. 2002.

65. Onoda Т., Sakai M., Yamada S. Careful seeding method based on Independent Components Analysis for K-means clustering /2010 IEEE/WIC/ACM International Conference on Web Intelligence and Intelligent Agent Technology. Toronto, Canada: IEEE Computer Society. 2010. P. 112-115.

66. Onoda Т., Sakai M., Yamada S. Careful seeding method based on Independent Components Analysis for k-means clustering // Journal of Emerging Technologies in Web Intelligence. 2012. V.4. No.l. P.51-59.

67. Кухаренко Б.Г. Анализ независимых компонент записей колебаний в технологии спектрального анализа на основе быстрого преобразования Прони // Информационные технологии. 2009.№ 9. С.20-25.

68. Кухаренко Б.Г. Анализ независимых компонент и скрытая Марковская модель для определения доминантных компонент многомерных временных рядов // Информационные технологии. 2010. № 11. Приложение. С. 1-32.

69. Belouchrani A., Abed-Meraim К., Cardoso J.-F., Molines Е. A blind source separation technique using second-order statistics // IEEE Transactions on Signal Processing. 1997. V.45. P.434-444.

70. Cardoso J.-F. High-order contrasts for independent component analysis // Neural Computation. 1999. V.ll. Issue 1. P.157-192.

71. Nion D., Sidiropoulos N.D. Adaptive algorithms to track the PARAFAC decomposition of a third-order tensor // IEEE Transactions on Signal Processing. 2009. V.57. No.6. P.2299-2310.

72. Kolda T.G., Bader B.W. Tensor Decompositions and Applications // SIAM Review. 2009. V.51. No.3. P.455-500.

73. Кухаренко Б.Г., Пономарев Д.И. Анализ независимых компонент потока векторов для сокращения размерности пространства при кластеризации векторов с целями абстракции данных // Информационные технологии. 2013. № 5. С.2-8.