Определение 1
.
Минимальным ограничивающим параллелепипе-
дом
, или
минимальным ограничивающим регионом
(МОП или MBR
— minimum bounding rectangle) для последовательности
{
S
i
}
, все эле-
менты которой принадлежат
n
(
S
i
∈
n
)
, будем называть
n
-мерный
параллелепипед минимального объема со сторонами, параллельными
осям координат, который целиком содержит точки этой последователь-
ности.
Отметим, что MBR(
{
Si
}
) определяется двумя точками в
n
:
P
min
и
P
max
:
P
min
(
x
1
, . . . , x
n
) :
x
i
= min
j
(
S
ji
);
P
max
(
x
1
, . . . , x
n
) :
x
i
= max
j
(
S
ij
)
.
Определение 2
.
Расширением параллелепипеда
R
на величину
δ
получен параллелепипед
R
, такой, что центр
R
совпадает с центром
параллелепипеда
R
, а координаты вершин
R
отличаются от координат
соответствующихвершин
R
на величину
δ
вдоль каждой из осей в
направлении от центра
R
.
Другими словами, операция расширения параллелепипеда
MBR(
{
Qi
}
), определяемого точками
P
min
(
x
11
, . . . , x
1
n
)
и
P
max
(
x
21
, . . .
. . . , x
2
n
)
, на величину
δ
образует параллелепипед, определяемый точ-
ками
P
min
(
x
11
−
δ, . . . , x
1
n
−
δ
)
и
P
max
(
x
21
+
δ, . . . , x
2
n
+
δ
)
.
Операция расширения региона позволяет работать с зашумленны-
ми сигналами.
Определение 3.
Разбиением последовательности
{
S
i
}
длиной
N
на
K
подпоследовательностей
(
K < N
)
будем называть такой на-
бор из
K
−
1
целыхчисел
{
M
i
}
: 1
< M
i
< N
, и
M
i
=
M
j
, если
i
=
j
, который определяет
K
частей исходной последовательности:
{
X
1
, . . . , X
m
0
−
1
}
,
{
X
m
0
, . . . , X
m
1
−
1
}
, . . . ,
{
X
mk
−
1
, X
N
}
. Среднюю дли-
ну такихподпоследовательностей
λ
будем называть
диаметром раз-
биения
.
Пусть даны последовательность
{
S
i
}
и запрос
{
Q
i
}
, для которых
необходимо вычислить меру близости. Для этого разобьем
{
S
i
}
на
подпоследовательности, и для каждой из подпоследовательностей по-
строим минимальный ограничивающий параллелепипед
R
i
. Каждый
параллелепипед расширим на величину
δ
. Таким образом, последова-
тельности
{
S
i
}
ставим в соответствие последовательность
{
R
i
}
. За-
метим, что между любыми двумя
R
i
,
R
j
f
{
R
i
}
установлены соотно-
шения
непосредственного следования
— для нихможно определить,
является ли
R
i
непосредственным предшественником
R
j
или нет. Тог-
да процедура вычисления меры похожести последовательностей
{
Q
i
}
и
{
S
i
}
выглядит следующим образом.
108 ISSN 0236-3933. Вестник МГТУ им. Н.Э. Баумана. Сер. “Приборостроение”. 2007. № 2
