Ознайомитись із поняттям кластеризації. Навчитись застосовувати методи розпізнавання образів, зокрема такі як :
1) алгоритм порогової величини;
2) максимінного алгоритму;
3) алгоритм К-внутрішніх групових середніх.
А також навчитись застосовувати їх на практиці при складанні програм.
Короткі теоретичні відомості
Основним завданням процесу кластеризації є розподіл заданої множини образів на класи (кластери), котрі дають змогу досліджувати подібність і відмінність між образами в класах і робити обґрунтовані висновки про кластерні образи в кластерах.
На етапі вибору алгоритму кластеризації здійснюється вибір одного із алгоритмів, котрі містяться у бібліотеці алгоритмів кластеризації. Цей етап передбачає вибір міри подібності образів у кластері та критеріїв кластеризації.
Бібліотека алгоритмів містить відомий алгоритм порогової величини .
Цей алгоритм полягає у обчисленні кластерів для кожної точки образу заданої множини .Відтак обчислюють кількості точок образів у кожній області кластеризації і за перший
кластер приймають область з максимальною кількістю точок образів. Ця множина точок
вилучається з подальшого розглядуце роблять доти, доки не отримаємо пусту множину точок образів. Очевидно, що цей алгоритм має найвищу складність серед усіх алгоритмів бібліотеки.
Основним недоліком алгоритму є те, що він вимагає задання порогової величини Т і результат його роботи залежить від вибору початкової точки – першого центра кластера.
Максимінний алгоритм використовує евклiдову вiдстань. Один з об'єктiв (X1) довiльним чином назначається центром першого кластера. Потiм вiдшукується образ, розмiщений вiд образа X1 найдалi, який призначається центром кластера Z2. На третьому кроцi алгоритму здiйснюється обчислення вiдстаней мiж всiма iншими образами вибiрки i центрами кластерiв Z1 i Z2. В кожнiй парi цих вибірок вибирається мiнiмальне. Пiсля цього видiляється максимальне з цих мiнiмальних вiдстаней. Якщо останнє складає значну частину вiдстанi мiж кластерами Z1 i Z2 (половина цiєї вiдстанi), вiдповiдний образ призначається центром кластера Z3. Iнакше - виконання алгоритму припиняється. В загальному випадку описана процедура повторюється до тих пiр, поки на якомусь кроцi не буде отримане максимальне значення вiдстанi, для якої умова, що викликає видiлення кластера, не виконується.
Для алгоритму К-середніх вибираються центри кластерiв Z1(1), Z2(1),...,Zk(1).
Потім на k-му кроцi iтерацiї задана множина образiв розподiляється по k кластерах за таким правилом : XєSj(k), якщо ||X-Zj(k)||<=||X-Zj(k)||, для всiх i=1,2,...,k, i¹j, де Sj(k) - множина образiв, якi входять в кластер з центром Zj(k). У випадку рiвностi рiшення приймаються довiльним чином.
Потім на основi результатів кроку 2 визначаються новi центри кластерiв Zj(k+1), j=1,2,...,k, які вибираються таким чином, щоб мiнiмiзувати показник якостi.
Центр Zj(k+1), що забезпечує мiнiмiзацiю показника якостi, є, по сутi, вибiрковим середнiм, визначеним по множинi Sj(k).
Рiвнiсть Zj(k+1) при j=1,2,...,k є умовою збiжностi алгоритму, i при її досягненнi виконання алгоритму припиняється. Інакше процедура повторюється.
Практичне застосування алгоритму вимагає проведення експериментiв, пов'язаних iз вибором рiзних значень параметра k i початковим розмiщенням центрiв кластерів.