Алгоритм кластеризации ISODATA(ИСОМАД) предназначен для разделения заданного множества образов (в данном случае точек двумерного пространства) на подмножества (кластеры), связанные определенным свойством, например основанное на близости точек по геометрическому расстоянию. Алгоритм эвристический, т.е. результат работы во многом зависит от заданных начальных параметров.

При работе с набором {x₁, x₂, ..., x_N}, составленным из N элементов, алгоритм ИСОМАД выполняет следующие основные шаги.

Шаг 1. Задаются параметры, определяющие процесс кластеризации:

Шаг 2. Заданные N образов распределяются по кластерам, соответствующим выбранным исходным центрам, по правилу

xÎ S_j, если ||х – z_j|| < ||х – z_i||, i=1,2, ..., N_c; i¹ j,

применяемому ко всем образам х, вошедшим в выборку; через S_j обозначено подмножество образов выборки, включенных в кластер с центром z_j.

Шаг 3. Ликвидируются подмножества образов, в состав которых входит менее Q_N элементов, т. е. если для некоторого j выполняется условие N_j < Q_N, то подмножество S_j исключается из рассмотрения и значение N_c уменьшается на 1.

Шаг 4. Каждый центр кластера z_j, j=1, 2, ..., N_c, локализуется и корректируется посредством приравнивания его выборочному среднему, найденному по соответствующему подмножеству S_j, т. е.

где N_j —число объектов, вошедших в подмножество Nj.

Шаг 5. Вычисляется среднее расстояние D_j между объектами, входящими в подмножество S_j, и соответствующим центром кластера по формуле

Шаг 6. Вычисляется обобщенное среднее расстояние между объектами, находящимися в отдельных кластерах, и соответствующими центрами кластеров по формуле

Шаг 7. (а) Если текущий цикл итерации—последний, то задается Q_c=0; переход к шагу 11. (б) Если условие N_c<=К/2 выполняется, то переход к шагу 8. (в) Если текущий цикл итерации имеет четный порядковый номер или выполняется условие N_c>=K/2, то переход к шагу 11; в противном случае процесс итерации продолжается.

Шаг 8. Для каждого подмножества выборочных образов с помощью соотношения

вычисляется вектор среднеквадратичного отклонения s _j = (s _1j, s _2j, ..., s _nj)', где п есть размерность образа, x_ik, есть i-я компонента k-ro объекта в подмножестве S_j, z_ij есть i-я компонента вектора, представляющего центр кластера z_j, и N_j —количество выборочных образов, включенных в подмножество S_c. Каждая компонента вектора среднеквадратичного отклонения s _j характеризует среднеквадратичное отклонение образа, входящего в подмножество S_j, по одной из главных осей координат.

Шаг 9. В каждом векторе среднеквадратичного отклонения s _j, j=1, 2, ..., N_c, отыскивается максимальная компонента s _jmax.

Шаг 10. Если для любого s _jmax, j=1, 2, ..., N_c, выполняются условия s _jmax>Q_s,и

а)

б) N_j < К/2,

то кластер с центром z_j расщепляется на два новых кластера с центрами z_j⁺ и z_j^- соответственно, кластер с центром z_j ликвидируется, а значение N_c увеличивается на 1. Для определения центра кластера z_j+ к компоненте вектора z_j, соответствующей максимальной компоненте вектора s _j, прибавляется заданная величина g _j; центр кластера z_j^- определяется вычитанием этой же величины g _j из той же самой компоненты вектора z_j. В качестве величины g _j можно выбрать некоторую долю значения максимальной среднеквадратичной компоненты s _jmax, т. е. положить g _j = ks _jmax, где 0 < k <= 1. При выборе g _j следуег руководствоваться в основном тем, чтобы ее величина была достаточно большой для различения разницы в расстояниях от произвольного образа до новых двух центров кластеров, но достаточно малой, чтобы общая структура кластеризации существенно не изменилась.

Если расщепление происходит на этом шаге, надо перейти к шагу 2, в противном случае продолжать выполнение алгоритма.

Шаг 11. Вычисляются расстояния D_ij между всеми парами центров кластеров:

Шаг 12. Расстояния D_ij сравниваются с параметром Q_c. Те L расстояний, которые оказались меньше Q_c, ранжируются в порядке возрастания:

причем D_i1j1 < D_i2j2 < ... < D_iLjL,. a L—максимальное число пар центров кластеров, которые можно объединить. Следующий шаг осуществляет процесс слияния кластеров.

Шаг 13. Каждое расстояние D_iljl вычислено для определенной пары кластеров с центрами z_il и z_jl. К этим парам в последовательности, соответствующей увеличению расстояния между центрами, применяется процедура слияния, осуществляемая на основе следующего правила.

Кластеры с центрами z_il и z_jl, i=1, 2, ..., L, объединяются (при условии, что в текущем цикле итерации процедура слияния не применялась ни к тому, ни к другому кластеру), причем новый центр кластера определяется по формуле

Центры кластеров z_il и z_jl ликвидируются и значение N_c уменьшается на 1.

Отметим, что допускается только попарное слияние кластеров и центр полученного в результате кластера рассчитывается, исходя из позиций, занимаемых центрами объединяемых кластеров и взятых с весами, определяемыми количеством выборочных образов в соответствующем кластере. Опыт свидетельствует о том, что использование более сложных процедур объединения кластеров может привести к получению неудовлетворительныхрезультатов. Описанная процедура обеспечивает выбор в качестве центра объединенного кластера точки, представляющей истинное среднее сливаемых подмножеств образов. Важно также иметь в виду, что, поскольку к каждому центру кластера процедуру слияния можно применить только один раз, реализация данного шага ни при каких обстоятельствах не может привести к получению L объединенных кластеров.

В данном случае N ==8 и п = 2. В качестве начальных условий задаем N_c=1, z₁ = (0,0)' и следующие значения параметров процесса кластеризации:

К=2, Q_N=1, Q_s=1, Q_c=4, L=0, I=4.

S₁ ={x₁, x₂, ..., x₈} и N₁ = 8.

Шаг 3. Поскольку N₁ > Q_N, ни одно подмножество не ликвидируется.

Шаг 4. Корректируется положение центра кластера:

Шаг 5. Вычисляется расстояние D_j:

Шаг 6. Вычисляется расстояние D:

Шаг 7. Поскольку данный цикл итерации—не последний и N_c = К/2, осуществляется переход к шагу 8.

Шаг 8. Для подмножества S₁ вычисляется вектор среднеквадратичного отклонения:

Шаг 9. Максимальная компонента вектора s ₁ равна 1,99, следовательно, s ₁max = 1,99.

Шаг 10. Поскольку s ₁max > Q_s, и N_c = К/2, кластер с центром z₁ расщепляется на два новых кластера. Следуя процедуре, предусмотренной шагом 10, выбираем g _j = 0,5s _jmax = 1,0. При этом

Для удобства записи будем называть центры этих кластеров z₁ и z₂ соответственно. Значение N_c увеличивается на 1; переход к шагу 2.

S₁ ={x₄, x₅, ..., x₈}, S₂ ={x₁, x₂, x₃} и N₁ = 5, N₂ = 3.

Шаг 3. Поскольку обе величины—и N₁, и N₂—больше Q_N, ни одно подмножество не ликвидируется.

Шаг 5. Вычисляется расстояние D_j, j=1,2:

Шаг 6. Вычисляется расстояние D:

Шаг 7. Поскольку данная итерация имеет четный порядковый номер, условие (в) шага 7 выполняется. Поэтому следует перейти к шагу 11.

Шаг 12. Величина расстояния D₁₂ сопоставляется с параметром Q_c. В данном случае D₁₂ > Q_c.

Шаг 14. Поскольку данный цикл итерации—не последний, необходимо принять решение: вносить или не вносить изменения в параметры процесса кластеризации. Так как в данном (простом) случае 1) число выделенных кластеров соответствует заданному, 2) расстояние между ними больше среднего разброса, характеризуемого среднеквадратичными отклонениями, и 3) каждый кластер содержит существенную часть общего количества выборочных образов, то делается вывод о том, что локализация центров кластеров правильно отражает специфику анализируемых данных. Следовательно, переходим к шагу 2.

Шаг 8. Для множеств S₁ ={x₄, x₅, ..., x₈}, S₂ ={x₁, x₂, x₃}

Шаг 9. В данном случае s ₁max = 0,75 и s ₂max = 0,82.

Шаг 10. Условия расщепления кластеров не выполняются. Следовательно, переходим к шагу 11. .

Шаг 14. На данном цикле итерации не были получены новые-результаты, за исключением изменения векторов среднеквадратичного отклонения. Поэтому переходим к шагу 2.

Шаг 7. Поскольку данный цикл итерации—последний, задаем Q_c = 0 и переходим к шагу 11.

Используемая литература:

Ту Дж., Гонсалес Р. “Принципы распознавания образов” Мир:1978г.