Алгоритм К внутригрупповых средних

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

Алгоритм:

Шаг 1. Выбирается К исходных центров кластеров z₁(1), z₂(1), …, z_K(1). Этот выбор производится произвольно, и обычно в качестве исходных центров используются первые К результатов выборки из заданного множества образов.

Шаг 2. На k – ом шаге итерации заданное множество образов {х} распределяется по К кластерам по следующему правилу:

х S_j(k), если ||х – z_j(k)|| < ||х – z_i(k)||

для всех i=1, 2, …, K, i≠j, где S_j(k) – множество образов,

входящих в кластер с центром z_j(k).

В случае равенства решение принимается произвольным образом.

Шаг 3. На основе результатов шага №2 определяются новые центры кластеров z_j(k+1), j=1, 2, …, K, исходя из условия, что сумма квадратов расстояний между всеми образами, принадлежащими множеству S_j(k), и новым центром кластера должна быть минимальной. То есть новые центры кластеров z_j(k+1) выбираются таким образом, чтобы минимизировать показатель качества

J_j= , j=1, 2, …, K.

Центр z_j(k+1), обеспечивающий минимизацию показателя качества, является, в сущности, выборочным средним, определенным по множеству S_j(k). Следовательно, новые центры кластеров определяются как

z_j(k+1)= , j=1, 2, …, K, где N_j – число выборочных

изображений, входящих в множество S_j(k).

Шаг 4. Равенство z_j(k+1) = z_j(k) при j=1, 2, …, K является условием сходимости алгоритма, и при его достижении выполнение алгоритма заканчивается. В противном случае алгоритм повторяется от шага №2.

Качество работы алгоритмов, основанных на вычислении К внутригрупповых средних, зависит от числа выбираемых центров кластеров, от выбора исходных центров кластеров, от последовательности осмотра образов и, естественно, от геометрических особенностей данных. Хотя для этого алгоритма общее доказательство сходимости не известно, получения приемлемых результатов можно ожидать в тех случаях, когда данные образуют характерные гроздья, отстоящие друг от друга достаточно далеко.

Пример:

Шаг1. k=2. z1(1)=x1; z2(1)=x2;

Шаг2.. Поскольку ||x3-z₁(1)|| < ||x3-z₂(1)|| то S₁(1) = {x1,x3}. Аналогичным образом устанавливаем, что остальные образы расположены ближе к образу z₂(1) и S₂(1) = {x2,x4, x5}.

Шаг3. Коррекция назначения центров кластеров:

z1(2)= (x1+x3) =(0,0.5)’.

z2(2)= (x2+x4+x5)=(2.3, 2.6)’.

Шаг4. Так как z1(2)!=z1(1) и z2(2)!=z2(1), то возврат к шагу2.

Шаг2. ||xi-z1(2)|| < ||xi-z2(2)|| для i=1,3, а также ||xi-z2(2)|| < ||xi-z1(2)|| для i=2,4,5. Таким образом, S1(2)={x1,x3}; S2(2)={x2,x4,x5}.

Шаг3. Коррекция назначения центров кластеров:

z1(3)= (x1+x3) =(0, 0.5)’.

z2(3)= (x2+x4+x5)=(2.3, 2.6)’.

Получаем те же результаты, что и на предыдущей итерации

Шаг4. Так как z1(3)=z1(2) и z2(3)=z2(2), то алгоритм сходится и заканчивает свою работу.

Получены следующие центры классов:

z1= ; z2=