5 / 20
А.П. Карпенко, П.И. Сотников
50
ISSN 0236-3933. Вестник МГТУ им. Н.Э. Баумана. Сер. Приборостроение. 2017. № 2
временных рядов из исходного набора данных [2], т. е. для поиска кандидатов
используют так называемый алгоритм «грубой силы» (
англ.
Brute-Force
Algorithm
). Псевдокод данного алгоритма представлен далее.
←∅
min
l
l
←
While
max
l l
≤
shapelets
←∅
( )
Ω,
candidates GenerateCandidates l
←
for each
S
in
candidates
(
)
Ω, S
quality CheckCandidate
←
(
)
.
,
shapelets add S quality
end for
1
l
l
← +
(
)
sortByQuality shapelets
(
)
, ,
merge k shapelets
←
end while
return
Входными данными алгоритма являются множество
Ω
и границы
min max
,
.
l
l
Процедура
GenerateCandidates
генерирует все возможные фрагменты длины
l
из
множества
Ω
и сохраняет их в неупорядоченном списке кандидатов
candidates
.
В список
shapelets
включаются все сгенерированные кандидаты вместе с полу-
ченными для них оценками качества разделения классов
quality
. Далее с помо-
щью процедуры
sortByQuality
производится сортировка элементов списка в по-
рядке убывания значений для оценки качества разделения классов. Функция
merge
выполняет слияние списков
и
shapelets
таким образом, что при этом
выбираются только
k
лучших кандидатов.
В представленном алгоритме число рассматриваемых кандидатов из одного
временного ряда длины
N
равно
( )
2
,
O N
а общее число кандидатов для всего
набора данных
Ω
объема
P
равно
(
)
2
.
O PN
Поскольку время вычисления рас-
стояния от кандидата до любого временного ряда из набора
Ω
можно оценить
величиной
(
)
2
,
O PN
общая сложность алгоритма составляет
(
)
2 4
,
O P N
т. е.
очень быстро растет с ростом величин
P
,
N
.
Известен ряд подходов, обеспечивающих сокращение времени поиска
шейплетов:
1)
кэширование вычислений при расчете расстояний от кандидата до вре-
менных рядов [1];
2)
отбрасывание кандидатов на основе предварительной оценки их каче-
ства [1];