15. Клъстеризация

Постановка на задачата : имаме множество от образи {а₁, , а_n}. Всеки образ се характеризира от n признака {x₁,, x_n}. Необходимо е входното множество от образи да се раздели в m клъстъра(групи) така, че всеки образ от даден клъстър да е по-близо до образите в този клъстър отколкото до всеки образ от останалите клъстъри. За реализацията на клъстеризацията се използва алгоритъма за ефективна клъстеризация, който се реализира като показател за качеството на клъстеризация. Този показател се изчислява по следната формула :

J = _j=1..mGKj|| a - Z_j|| ²

m брой на клъстърите, които сме задали

Kj клъстър съдържащ подмножество от образи

Zj вектор от средните стойности на елементите в клъстъра Kj.

r брой на образите в клъстъра

J - показва сумата от разликите на образите до центровете на техните клъстъри.

При минимизация на тази сума се постига ефективна клъстеризация.

Алгоритъм за клъстеризация :

1. Определят се m центъра na клъстерите : Z₁Z_m . Обикновенно се вземат първите m образа.

2. i = 1 - параметър на цикъла (итерации)

3. Определят се най-близките образи до центровете, т.е. формират се m клъстъра К₁ⁱ,,K_mⁱ - това са клъстърите формирани на i-тата итерация.

4. За клъстърите получени в точка 3 се определят нови коиригирани центрове. Изхожда се от условието, че сумата от квадратите на разстоянията между новия център на зададеният клъстър и образите в него ще бъде минимална. Ji = aK_jⁱ || a Z_jⁱ⁺¹|| , j = 1,,m

5. Ако се получат едни и съши центрове за клъстърите в две последователни итерации се преминава към 6) иначе се връщаме към 3

6. Край

Задачата за клъстеризация се използва в медицината и други области за взимане на решения.

Алгоритъма за клъстеризация по същество представлява обучение без учител.