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

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

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

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

Кафедра САПР


Лабораторна робота №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 ітерацій, адже мені пощастило підібрати належні початкові координати для центральних точок.
скачати

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