Поскольку каждая вершина графа объединяет характерные точки
с определенным сходством, то, прежде всего, необходимо определить,
какие точки относятся к одной и той же вершине. Множество точек,
относящихся к одной вершине, назовем кластером. Число точек кла-
стера обозначим
N
. Каждый кластер включает множество наборов
значений характерных признаков
y
k
1
, y
k
2
, . . . , y
km
. Каждый набор ха-
рактерных признаков
y
k
1
, y
k
2
, . . . , y
km
образует точку
y
k
(
k
= 1
, . . . , n
)
в
m
-мерном пространстве. В нашем случае набор значений харак-
терных признаков помимо собственно геометрических координат то-
чек может содержать дополнительно, например, бинарные признаки,
определяющие, является ли данная точка началом траектории или нет,
является ли она точкой перегиба или нет, является ли данная точка
концом траектории или нет и т.п
Для нахождения кластеров воспользуемся одним из известных ме-
тодов четкой кластеризации, чаще всего называемым методом кла-
стеризации
с
-средних [12]. Напомним, в чем заключается суть этого
метода.
В основе метода кластеризации
с
-средних лежит метод целе-
вой функции. Целевая функция (критерий) создается таким образом,
чтобы
•
минимизировать расстояние между точкой в кластере и центром
кластера;
•
максимизировать расстояние между центрами кластеров.
Один из таких критериев известен как сумма квадратичных ошибок
внутри класса, использующая евклидову норму для характеристики
расстояния.
Этот критерий обозначается как
J
(
U, v
)
, где
U
— разбиение всех
точек на кластеры (непересекающиеся подмножества точек, объедине-
ние которых совпадает с исходным множеством точек, разбиваемым на
кластеры). Параметр
v
— это вектор кластерных центров (множество
кластерных центров, соответствующих разбиению
U
).
Формула критерия (целевой функции) будет следующей:
J
(
U, v
) =
n
k
=1
c
i
=1
χ
ik
(
d
ik
)
2
.
Здесь
d
ik
— мера евклидова или какого-либо другого расстояния (в
m
-
мерном пространстве характеристических параметров
R
m
)
между
k
-м
m
-мерным вектором
y
k
и
i
-м кластерным центром
v
i
, вычисляемая по
формуле
d
ik
=
d
(
y
k
−
v
i
) =
m
j
=1
(
y
kj
−
v
ij
)
2
1
/
2
.
ISSN 0236-3933. Вестник МГТУ им. Н.Э. Баумана. Сер. “Приборостроение”. 2007. № 3 61
