6 / 20
Модифицированный метод классификации многомерных временных рядов…
ISSN 0236-3933. Вестник МГТУ им. Н.Э. Баумана. Сер. Приборостроение. 2017. № 2
51
3)
отбрасывание кандидатов после оценки их близости к уже рассмотрен-
ным фрагментам временных рядов [3];
4)
применение специального символьного алфавита для кодирования вре-
менных рядов [5].
Используем алгоритм, реализующий третий из указанных подходов. В ра-
боте [3] показано, что данный подход позволяет значительно сократить перебор
без существенной потери точности разделения классов. Идея метода основыва-
ется на предположении, что близкие друг к другу кандидаты дают близкие зна-
чения оценки качества разделения классов.
Введем в рассмотрение порог
,
имеющий смысл перцентили распределе-
ния расстояний между случайно выбранными парами кандидатов. Значение
p-
й
перцентили указывает, что
p
% значений, представленных в распределении, ле-
жат ниже этого уровня. Таким образом, вводя порог
,
мы можем исключить из
рассмотрения до
p
% кандидатов, лежащих в окрестности рассматриваемого
фрагмента временного ряда.
Алгоритм
определения
порога
для
отбрасывания
кандидатов
(
ComputeThresholdAlgorithm)
имеет следующий вид:
Z
←∅
1
q
←
while
q Q
≤
( )
i random P
←
(
)
j
random N l
←
−
(
)
←
, ,
S getCandidate i j l
( )
'
i
random P
←
(
)
'
j
random N l
←
−
(
)
'
', ',
S getCandidate i j l
←
(
)
, '
Z Z dist S S
← ∪
1
q q
← +
end while
( )
Z sort Z
←
100
p Q
Z
←
return
На итерациях алгоритма между случайно выбранными фрагментами
S
,
S'
вычисляем расстояние
(
)
,
,
dist S S
′
и это расстояние добавляем в список
Z
. По
результатам работы алгоритма порог
определяем как значение
p
-й перценти-
ли в отсортированном по возрастанию списке расстояний
Z
.
Для фрагментов
S
,
S
'
многомерных временных рядов алгоритм
ComputeThreshold
использует скалярную свертку: