8 / 20
Модифицированный метод классификации многомерных временных рядов…
ISSN 0236-3933. Вестник МГТУ им. Н.Э. Баумана. Сер. Приборостроение. 2017. № 2
53
шейплет-преобразования в набор включают
/ 2
N
лучших кандидатов, полу-
ченных за один проход алгоритма поиска шейплетов. Поскольку похожие друг
на друга шейплеты, как правило, отражают свойства одного и того же класса,
включение в набор нескольких похожих шейплетов не увеличивает информа-
тивность ВХП. Поэтому рекомендуется оставлять в наборе только шейплеты,
значимо отличающиеся друг от друга. Для этих целей можно использовать ал-
горитм иерархической кластеризации [6].
Предлагаемые модификации метода шейплетов.
Использование генетиче-
ского алгоритма
. Задача поиска шейплетов (3) представляет собой задачу цело-
численной оптимизации. В работе [7] рассмотрена аналогичная постановка за-
дачи и для её решения предложено использовать известный метод градиентного
спуска (после сведения задачи к непрерывной). Поскольку нет никаких основа-
ний полагать, что задача (3) является одноэкстремальной, этот метод может
отыскать лишь ее локальное решение. Генетический же алгоритм может локали-
зовать глобальный экстремум задачи (3) и тем самым повысить точность разде-
ления многомерных временных рядов на классы.
Особей
s
популяции генетического алгоритма определят набор
( )
,
, φ ,
s F H F
=
где вектор
F —
фенотип особи;
H
— генотип особи;
( )
φ
F
— приспособлен-
ность. Фенотип особи задаем тройкой чисел (
i
,
j
,
l
), определяющих фрагмент
временного ряда, т. е. полагаем
(
)
, , .
F i j l
=
Для кодирования значений варьиру-
емых параметров (
i
,
j
,
l
) используем представление генотипа в виде монохромо-
сомы
(
)
, ,
,
i
j
l
H h h h
=
где
, ,
i
j
l
h h h
—
бинарные гены, отвечающие за кодирова-
ние чисел
, ,
i j l
соотвественно.
Для каждой из особей
s
значение функции приспособленности
( )
φ
F
вы-
числяем по следующей схеме.
1. На основе индексов
, ,
i j l
выбираем из множества
Ω
кандидата в шейп-
леты
( , , ).
i j l
=
S S
2. Рассчитываем расстояния от кандидата
S
до всех объектов из множества
Ω
. Формируем новое множество
( )
(
)
{
}
1
Ψ
,
,
.
P
i
i i
D k
=
=
S
S X
3. На множестве
( )
Ψ
S
выполняем оценку точности разделения классов.
Полученную оценку принимаем в качестве значения функции приспособленно-
сти
( )
φ .
F
В генетическом алгоритме отбираются родительские пары по методу «рулет-
ки». С равной вероятностью используем одноточечный или двухточечный опера-
торы скрещивания (оператор кроссинговера) и для каждой пары родителей
формируем два потомка. В качестве оператора мутации применяем оператор
равномерной генной мутации. Методом смертельных штрафов [8] учитываем
ограничения на значения параметров (
i
,
j
,
l
). По общему принципу эволюционных