Алгоритм пикового группирования

Алгоритм нечеткой самоорганизации C-means

В данном алгоритме подаваемый на вход очередной обучающий вектор X^k принадлежит различным кластерам (представленным своими центрами C_i, i =1, 2,..., M) в степени u^k_i, 0< u^k_i <1, при соблюдении условия

sum[i=1:M](u^k_i)=1.

При этом значение u^k_i тем больше, чем ближе X^k к C_i. Погрешность соотнесения обучающих векторов X^k и центров C_i для всех p обучающих векторов может быть выражена следующим образом

E=sum[i=1:M](sum[k=1:p]((u^k_i)^m*|X^k-C_i|₂)),

где m - показатель, выбираемый из ряда 1, 2, 3,....

Цель обучения - подбор таких значений центров C_i, которые обеспечивают минимальное значение погрешности E при одновременном соблюдении условия

sum[i=1:M](u^k_i)=1.

Решение этой задачи можно свести к минимизации функции Лагранжа в виде

LE=sum[i=1:M](sum[k=1:p]((u^k_i)^m*|X^k-C_i|₂))+

+sum[k=1:p](L_k*(sum[i=1:M](u^k_i)-1)),

где L_k, k =1, 2,..., p - множители Лагранжа.

Доказано, что решение этой задачи можно представить в виде

C_i=sum[k=1:p]((u^k_i)^m*X^k)/sum[k=1:p]((u^k_i)^m),
u^k_i=1/sum[l=1:M](((d^k_i)²/(d^k_l)²))^1/(m-1)),

где d^k_i=|X^k-C_i|₂ - эвклидово расстояние между X^k и C_i.

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

1. Выполнить случайный выбор коэффициентов u^k_i из диапазона [0,1] при соблюдении условия sum[i=1:M](u^k_i)=1.

2. Вычислить все M центров C_i по приведенной выше формуле.

3. Рассчитать значение погрешности E. Если это значение меньше установленного порога или незначительно изменилось относительно предыдущей итерации, то закончить вычисления. Иначе перейти к п. 4.

4. Рассчитать новые значения u^k_i по приведенной выше формуле и перейти к п. 2.

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

На вероятность отыскания глобального минимума влияет выбор начальных значений u^k_i и C_i.

Специально для подбора "хороших" начальных значений центров C_i разработаны процедуры инициализации, две из которых представлены ниже.

Для отыскания "первого приближения" к наилучшему расположению центров C_i в данном алгоритме используются так называемые пиковые функции.

При подаче на вход сети p обучающих векторов X^k создается равномерная сетка, покрывающая все пространство, занимаемое данными векторами.

Узлы сетки обозначим как V_l, для каждого из них рассчитывается значение пиковой функции

m(V_l)=sum[k=1:p](exp(-(|X^k-V_l|₂^2*b/(2*s²)))),

где s - константа, индивидуально подбираемая для каждой задачи.

Значение m(V_l) пропорционально количеству обучающих векторов X^k, находящихся в окрестности потенциального центра V_l.

Малое значение m(V_l) говорит о том, что V_l в области, где количество векторов X^k мало.

Следует отметить, что коэффициент s оказывает незначитетьное влияние на соотношение значений V_l для разных узлов сетки, поэтому подбор его величины не является критичным.

После расчета m(V_l) для всех потенциальных центров (узлов сетки) отбирается узел, имеющий наибольшее значение пиковой функции.

С этим узлом отождествляется первый центр C₁.

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

Это удобно сделать переопределением пиковой функции

m_new(V_l)=m(V_l)-m(C₁)*exp(-(|V_l-C₁|^2*b/(2*s²))),

где m(C₁) - значение пиковой функции в центре C₁.

Процесс последовательного отыскания центров C₁, C₂, C₃,... завершается после обнаружения центра C_M.

Основной недостаток алгоритма пикового группирования - экспоненциальный рост сложности с увеличением размерности векторов входных данных X^k.

Следовательно, он применим лишь при при небольшом количестве входных сигналов N.

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

В этом алгоритме в качестве потенциальных центров рассматриваются обучающие векторы X^k, k =1, 2,..., p.

Пиковая функция m(Xⁱ) определяется в следующем виде

m(Xⁱ)=sum[k=1:p](exp(-(|X^k-Xⁱ|^2*b/(r₁/2)²))),

где значение коэффициента r₁ определяет размер сферы соседства.

При большой плотности входных векторов вокруг Xⁱ значение функции велико, и, напротив, малое значение m(Xⁱ) свидетельствует о незначительном количестве соседей.

После расчета значений m(Xⁱ) для всех входных векторов в качестве первого центра C₁ принимается Xⁱ с наибольшим значением пиковой функции.

Для отыскания второго центра используется модифицированная пиковая функция в виде

mnew(Xi)=m(Xi)-m(C1)*exp(-(|Xi-C1|22*b/(r2/2)2)),

где r₂ задает новый размер сферы соседства, обычно r₂>=r₁.

Пиковая функция m_new(Xⁱ) принимает нулевое значение для Xⁱ=C₁.