Ім'я файлу: 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

Міністерство освіти і науки України

Національний університет “Львівська політехніка”

Інститут комп’ютерних наук та інформаційних технологій

Кафедра САПР


Лабораторна робота №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сть залежить:

  1. вiд кiлькостi вибираємих центрiв кластерiв;

  1. вiд вибору початкових центрiв кластерiв;

  1. вiд послiдовностi проглядання образiв;

  1. в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,6)
(5,1)
(-2,-3)



Xi
Точка
Відстань до 1-го центру
Відстань до 2-го центру
Відстань до 3-го центру
Кластер

X1
(-6,6)
0
12.083
9.848
1

X2
(-5,6)
1
11.180
9.486
1

X3
(-4,5)
11.18
9.848
8.246
2

X4
(-3,4)
10.440
8.544
7.280
2

X5
(5,-1)
12.083
2
7.280
3

X6
(5,0)

12.529
1
7.615
3

X7
(5,1)
13.038
0
8.0622
3

X8
(6,1)
13.892
1
8.944
3

X9
(7,1)
14.764
2
9.848
3

X10
(-4,-4)
2.828
10.295
2.236
1

X11
(-3,-4)
3.60
9.433
1.414
1

X12
(-2,-3)
5
8.062
0
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:



(-4, 0.2)
(3.5, 4.5)
(5.6, 0.4)



Xi
Точка
Відстань до 1-го центру
Відстань до 2-го центру
Відстань до 3-го центру
Кластер

X1
(-6,6)
6.135
9.617
12.880
1

X2
(-5,6)
5.885
8.631
11.988
1

X3
(-4,5)
4.8
7.516
10.645
2

X4
(-3,4)
3.929
6.519
9.323
2

X5
(5,-1)
9.079
5.700
1.523
3

X6
(5,0)

9.002
4.743
0.721
3

X7
(5,1)
9.035
3.807
0.848
3

X8
(6,1)
10.031
4.301
0.721
3

X9
(7,1)
11.029
4.949
1.523
3

X10
(-4,-4)
4.2
11.335
10.56
1

X11
(-3,-4)
4.317
10.7
9.66
1

X12
(-2,-3)
3.773
9.300
8.325
1



Отож, при повторному підрахунку відстаней між центрами кластерів та початковими точками, розподіл по кластерам не змінився. Алгоритм можна вважати завершеним.
Перший кластер: 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 ітерацій, адже мені пощастило підібрати належні початкові координати для центральних точок.
скачати

© Усі права захищені
написати до нас