3.3.4. Алгоритм максиминного расстояния

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

Возьмем выборку, состоящую из десяти двумерных образов (рис. 3.9,а). Для того чтобы получить представление о количестве кластеров, выделяющихся в этих данных, целесообразно воспользоваться алгоритмом, основанным на максиминном расстоянии. Описание алгоритма упрощают таблицы, приведенные на рис. 3.9,б. Одна из них содержит выборочные образы, другая — список центров кластеров, установленных алгоритмом; до начала работы алгоритма эта таблица пустая. На первом шаге алгоритма один из объектов, например произвольным образом назначается центром первого кластера (на рис. 3.9,б этот центр обозначен ). Цифры, расположенные на этом рисунке над стрелками, обозначают порядковый номер шага, на котором производится выделение соответствующего центра кластера.

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

(кликните для просмотра скана)

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

На следующем шаге алгоритма вычисляется расстояние между тремя выделенными центрами кластеров и всеми остальными выборочными образами; в каждой группе из трех расстояний выбирается минимальное. После этого, как и на предыдущем шаге, находится максимальное из этих минимальных расстояний. Если последнее составляет значительную часть «типичных» предыдущих максимальных расстояний, то соответствующий образ назначается центром кластера . В противном случае выполнение алгоритма прекращается. Хорошей мерой для оценки типичных предыдущих расстояний является их среднее значение. Если воспользоваться этим критерием в данном примере и потребовать, чтобы новое максимальное расстояние составляло по меньшей мере половину среднего, то из рис. 3.9, а следует, что очередное максимальное расстояние, которым оказалось расстояние между образами , не удовлетворяет такому условию. Поэтому на данном шаге работа алгоритма прерывается. В общем случае описанная процедура повторяется до тех пор, пока на каком-либо шаге не будет получено максимальное расстояние, для которого условие, определяющее выделение нового кластера, не выполняется.

В этом простом примере были выделены три кластерных центра . При отнесении остальных выборочных образов к одному из учрежденных кластеров используется критерий, предусматривающий введение классифицируемого образа в тот кластер, центр которого для него ближайший. В таком случае из рис. 3.9, а заключаем, что получены три кластера: . Результаты соответствуют нашим интуитивным представлениям об этих данных. Можно более точно определить центры кластеров, вычислив для каждого набора выборочное среднее по формуле (3.3.6). Эти средние можно считать новыми центрами кластеров.