![]() | Ім'я файлу: lab_8_Kravets.docx Розширення: docx Розмір: 220кб. Дата: 22.11.2021 скачати Пов'язані файли: 5.docx Лаба 4_РТП_СЗІ_Кліщ Богдан.docx Лаба 5_РТП_СЗІ_Кліщ.docx Тести, статистика праці.docx Реферат Лесько П.В. Авторське право ЕЛЕП-11.docx.doc Індивідуальна нормативне.docx lab2.docx ЦЕРКВА РІЗДВА ПРЕСВЯТОЇ БОГОРОДИЦІ У САМБОРІ.docx ШАБЕЛЬКО КУРСОВА.docx Розраха.docx Сучасні методики здорового харчування.docx Звіт до БД 2.docx звіт_від_ред.docx Сєрий.docx Сенсорне виховання.doc СПЗ_ЛАБ_1.docx lab5_бд.docx Фізика5 Моя лаба.doc Вебинар англ.docx 5.docx ЛР 3 ФДП.docx Методичка до ПЗ №5-6.doc зразок РГР 2021 (1).docx курсова 1.docx Міністерство_освіти_та_науки_України_PI.docx Контрольна робота Павло Коцаба.docx Метод Баркера.docx Grej_R._S.docx знайомий реферат.docx ОКРО.docx Міністерство освіти і науки України Національний університет “Львівська політехніка” Інститут комп’ютерних наук та інформаційних технологій Кафедра САПР ![]() Лабораторна робота №8. з дисципліни: “Методи та системи штучного інтелекту” на тему: “Дослідження алгоритмів розпізнавання образів. Алгоритм K-внутрішніх групових середніх”. Виконав Ст. групи КН-308 Кравець О.Б. Прийняв: Викл. Головацький Р.І. Дата: 15.11.2021 р. Оцінка (3) Львів-2021р. Тема: “Дослідження алгоритмів розпізнавання образів. Алгоритм K-внутрішніх групових середніх”. Мета: “Вивчити принципи роботи алгоритму K-внутрішніх групових середніх розпізнавання образів. Навчитись застосовувати його на практиці. Написати програму реалізації алгоритму з графічним інтерфейсом користувача”. Індивідуальне завдання. Здійснити розпізнавання образів із застосуванням алгоритму K-внутрішніх групових середніх. Задані наступні координати точок які необхідно кластеризувати: X1(-6,6) X2(-5,6) X3(-4,5) X4(-3,4) X5(5,-1) X6(5,0) X7(5,1) X8(6,1) X9(7,1) X10(-4,-4) X11(-3,-4) X12(-2,-3) Покроково описати повний хід виконання Вашої лабораторної роботи: який пункт завдання виконуєте, чому саме таким методом, як його перевіряєте, отримали те що планувалось чи ні і т.д. Теоретичні відомості. Алгоритм k-внутрішніх групових середніх розпізнавання образів.КРОК 1. Вибираються k початкових центрiв кластерiв Z1(1), Z2(1),...,Zk(1). Цей вибір здiйснюється довiльно i, звичайно, в якостi початкових центрiв використовуються першi k результатiв вибiрки з заданої множини образiв. КРОК 2.На 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льним чином. КРОК 3.На основi результатів кроку 2 визначаються новi центри кластерiв Zj(k+1), j=1,2,...,k, виходячи з умови, що сума квадратiв вiдстаней мiж усiма образами, що належать множині Sj(k), i новiм центром кластера повинна бути мiнiмальною. Iншими словами, новi центри кластерiв Zj(k+1) вибираються таким чином, щоб мiнiмiзувати показник якостi Jj=Σ||X-Zj(k+1)||^2, j=1,2,...,k. XєSj(k) Центр Zj(k+1), що забезпечує мiнiмiзацiю показника якостi, є, по сутi, вибiрковим середнiм, визначеним по множинi Sj(k). Вiдповiдно, новi центри кластерiв визначаються як: Zj(k+1)=(1/Nj)ΣX, j=1,2,...,k, XЄSj(k), де Nj- число вибiркових образiв, що входять в множину типу Sj(k). Очевидно, що назва алгоритму "К внутрiшнiх групових" визначається способом, прийнятим для послiдовної корекцiї призначення центрiв кластерiв. КРОК 4.Рiвнiсть Zj(k+1) при j=1,2,...,k є умовою збiжностi алгоритму, i при її досягненнi виконання алгоритму припиняється. Iнакше, крок 2. Якiсть залежить: вiд кiлькостi вибираємих центрiв кластерiв; вiд вибору початкових центрiв кластерiв; вiд послiдовностi проглядання образiв; вiд геометричної особливостi даних. Практичне застосування алгоритму вимагає проведення експериментiв, пов'язаних iз вибором рiзних значень параметра k i початковим розмiщенням центрiв кластерiв. Блок – схема алгоритму. ![]() Ручні обчислення. Задані наступні координати точок які необхідно кластеризувати: X1(-6,6) X2(-5,6) X3(-4,5) X4(-3,4) X5(5,-1) X6(5,0) X7(5,1) X8(6,1) X9(7,1) X10(-4,-4) X11(-3,-4) X12(-2,-3) Нехай початковими центрами кластерів будуть X1(-6,6), X7(5,1), X12(-2,-3) при К=3. Перш за все, варто знайти відстані між центроїдами та іншими точками, встановити належність кожної з них до певного кластера. Всі результати в подальшому зводитимуться в таблиці для зручності. Ітерація 1:
Обчислюємо нові центри кластерів. Центр першого кластера: (-6-5-4-3-2)/5=-4, (6+6-4-4-3)/5 = 0.2 Центр другого кластера: (-4-3)/2= 3.5 , (5+4)/2=4.5 Центр третього кластера: (5+5+5+6+7)/5=5.6, (-1+0+1+1+1)/5=0.4 Проводимо тотожні попереднім розрахунки, замінивши центроїди. Ітерація 2:
Отож, при повторному підрахунку відстаней між центрами кластерів та початковими точками, розподіл по кластерам не змінився. Алгоритм можна вважати завершеним. Перший кластер: X1(-6,6) X2(-5,6) X10(-4,-4) X11(-3,-4) X12(-2,-3) Другий кластер: X3(-4,5) X4(-3,4) Третій кластер: X5(5,-1) X6(5,0) X7(5,1) X8(6,1) X9(7,1) Графічний результат виконання програми. ![]() Рис. 1. Корегування розміщення центроїд при К=3, де чорний колір- перша ітерація, а зелений - відповідно друга. ![]() Рис. 2. Відображення кластерів на координатній площині. Висновки: Під час виконання даної лабораторної роботи я вивчив принципи роботи алгоритму K-внутрішніх групових середніх розпізнавання образів та навчився застосовувати його на практиці. Таким чином, маючи у наявності вибірку з 14 точок, я зміг рівномірного їх розбити на кластери (К=3) таким чином, аби відстані між ними та центроїдами були мінімальними. Важливо зауважити, що весь процес складається лише з двоx ітерацій, адже мені пощастило підібрати належні початкові координати для центральних точок. |