double arrow

Эвристический алгоритм максиминного расстояния

3

Алгоритм основан на принципе максиминного (максимально-минимального ) расстояния. Алгоритм аналогичен схеме простого выявления кластеров, за исключением того, что в первую очередь он выявляет наиболее удаленные кластеры.

Пусть дана выборка из m n – мерных образов. Необходимо получить представление о количестве кластеров, выделяющихся в этих данных.

Алгоритм:

1) На первом шаге алгоритма один из объектов, например х1, произвольным образом назначается центром первого кластера z1

2) Затем отыскивается образ, отстоящий от образа х1 на наибольшее расстояние, который и назначается центром кластера z2

3) На k – ом шаге итерации для каждого из оставшихся образов выборки вычисляем расстояния до всех ранее полученных центров кластеров. В каждой паре этих расстояний выбираем минимальное. После этого находим среди всех полученных минимальных расстояний максимальное. Если последнее составляет значительную часть расстояния между полученными центрами кластеров (скажем, по меньшей мере половину этого расстояния), то соответствующий образ назначается центром следующего кластера. В противном случае выполнение алгоритма прекращается. В общем случае, процедура повторяется до тех пор, пока на каком – либо шаге не будет получено максимальное расстояние, для которого условие, определяющее выделение нового кластера не выполняется. При отнесении выборочных образов, не вошедших в кластерные центры, к одному из учрежденных кластеров, используется критерий, предусматривающий введение классифицируемого образа в тот кластер, центр которого для него ближайший.

Пример:

1. Назначаем центром кластера z1 первое изображение объекта x1.

2. Ищем изображение объекта, отстоящее от изображения x1 на наибольшее расстояние. Наибольшим расстоянием является S(x1, x3). Назначаем центром второго кластера z2 – x6.

3. Для каждого из оставшихся образов вычисляем расстояния до всех ранее полученных центров кластеров. Из полученных наборов расстояний для каждого образа выбираем минимальное = min[(s(xi,z1)),(s(xi,z2))].

x2: min[(s(x2,z1)),(s(x2,z2))] = .

x3: min[(s(x3,z1)),(s(x3,z2))] = 3.

x4: min[(s(x4,z1)),(s(x4,z2))] = .

x5: min[(s(x5,z1)),(s(x5,z2))] = .

После этого находим среди всех полученных минимальных расстояний максимальное.

Максимальное расстояние Max= 3.

Расстояние S между центрами кластеров z1 и z2 = .

Для полученного максимального расстояния условие, определяющее выделение нового кластера не выполняется, следовательно алгоритм заканчивает свою работу.

Итак, получаем два кластера: {x1, x2},{x3, x4, x5, x6}.


Понравилась статья? Добавь ее в закладку (CTRL+D) и не забудь поделиться с друзьями:  


3

Сейчас читают про: