МІНІСТЕРСТВО ОСВІТИ УКРАЇНИ Національний університет “Львівська політехніка” ДОСЛІДЖЕННЯ АЛГОРИТМІВ РОЗПІЗНАВАННЯ ОБРАЗІВ. АЛГОРИТМ “ІСОМАД (ISODATA)” Методичні вказівки до лабораторної роботи №3 з курсу “Основи проектування систем штучного інтелекту” ДОСЛІДЖЕННЯ АЛГОРИТМІВ РОЗПІЗНАВАННЯ ОБРАЗІВ. АЛГОРИТМ “ІСОМАД (ISODATA)”. Методичні вказівки до лабораторної роботи №3 з курсу “Основи проектування систем штучного інтелекту” для студентів базового напрямку 6.08.04 “Комп’ютерні науки”./ 1.Мета роботи Вивчити основні принципи роботи алгоритму розпізнавання образів ІСОМАД. 2. Короткі теоретичні відомості 2.1. Алгоритм ІСОМАД Крок 1 Задаються параметри, що визначають процес кластеризації: К - необхідна кількість кластерів;
- параметр, з яким порівнюється кількість вибіркових образів, що ввійшли в кластер;
- параметр, що характеризує середньоквадратичне відхилення;
- параметр, що характеризує компактність; L - максимальна кількість пар центрів кластерів, які можна об’єднати; І - допустима кількість циклів і ітерацій. Крок 2 Задані N образів розподіляються по кластерах, що відповідають вибраним початковим цетрам за правилами
якщо
i=1,2, ... , Nc ,
Крок 3 Ліквідуються підмножини образів, в склад яких входять менше
елементів, т.б. якщо для деяког j виконується умова Nj<
, то підмножини Sj виключається із перегляду і значення Nc зменшується по 1. Крок 4 Кожен центр кластера Zj , j =1,2, ... , Nc, локалізується і коректується
j=1,2, ... ,Nc де Nj - число об’єктів, що ввійшли в підмножину Sj. Крок 5 Обчислюється середня відстань
між об’єктами, що входять в підмножину
, і відповідним центром кластера за формулою:
, j=1,2,...,
. Крок 6 Обчислюється узагальнене середня відстань між об’єктами, що знаходяться в окремих кластерах, і відповідними центрами кластерів за формулою:
Крок 7 а) Якщо біжучий цикл ітерації - останній, то задається
; перехід до 11. б) Якщо умова
виконуєтьяс то перехід до кроку 8. в) Якщо біжучий цикл ітерацій має перший порядковий номер, або виконується умова
, то перехід на крок 11; інакше крок 8 Крок 8 Для кожної підмножини вибіркових образів за допомогою співвідношення:
, і=1,2,..., n; j=1,2,...,
вираховуєтьяс вектор середньоквадратичного відхилення
, де n є розмірність образа, Хik є і-ю компонентою к-го об’єктів підмножини Sj, Zij є і-ю компонентою вектора, що представляє центр кластера Zj , i Nj - кількість вибіркових образів, включених в підмножину Sj. Кожна компонента вектора середнього квадратичного відхилення
характеризує середньоквадратичне відхилення образу, що входить в півмножину Sj, по одній із головних осей координат. Крок 9 В кожному векторі середньоквадратичного відхилення
, j=1,2,...,Nc, виконуються умови
мах >
і а)

або б)
,
то кластер з центром Zj розщеплюється на два повних кластера з центрами
і
відповідно, кластера із центром
ліквідується, а значення
збільшується на 1. Для визначення центра кластера
до компонент вектора
, що відповідає максимальній компоненті вектора
, додається задана величина
; центр кластера
визначається відніманням цієї ж величини
із цієї компоненти вектора Z,
Якщо розщеплення відбувається на даному кроці, то перейти на крок 2, інакше крок 11. Крок 11 Вираховується відстані
між усіма парами центрів кластерів
Крок 12 Відстані
порівнюються з параметрами
. Ті < вітдалей, які виявилися меншими за
ранжуються в порядку зростання
; Причому
, а L - max кількість пар центрів кластерів, які можна об’єднати. Крок 13 Кожна віддаль Dieje вирахувано для певної пари кластерів із центрами Zil Zjl. До цих пар послідовності, що відповідає збільшенню відстані між центрами, застосовується процедура злиття: кластери з центрами Zil і Zjl, l=1,2,...,L, об’єднуються (при умові, що в біжучому циклі ітерації процедура злиття не застосовувалася ні до того, ні до іншого кластера), причому новий центр кластера визначається за формулою
Центри кластерів Zil i Zjl ліквідуються і значення Nc зменшується по1. Допускається лише попарне злиття кластерів і центр отриманого в результаті кластера розраховується, виходячи із позицій,що займаються центрами об’єднаних кластерів і взятих із вагами, визначеними кількістю вибіркових образів у відповідному кластері. Крок 14 Якщо біжучий цикл ітерації - останній, то виконання алгоритма припиняється. Інакше вертається на крок 1, якщо користувач які не є один із параметрів, чи на крок 2. Завершенням циклу ітерації вважається кожен перехід до кроків 1 або 2. 3. КОНТРОЛЬНІ ЗАПИТАННЯ 3.1. Поняття систем розпізнавання без навчання, таких, що навчають та самонавчальних. 3.2. Зміст параметрів, що визначають процес кластеризації. 3.3. Умова розщеплення двох кластерів. 3.4.Умова злиття двох кластерів. 3.5. Умова завершення алгоритму ІСОМАД. 4. ІНДИВІДУАЛЬНЕ ЗАВДАННЯ Здійснити розпізнавання образів із застосуванням алгоритму ІСОМАД. а) К = 3;
= 1;
= 1;
=4; L = 0; І =5. 4.1. Х1(0,3), Х2(3,3), Х3(3,4), Х4(3,9), Х5(4,8), Х6(9,5), Х7(9,6), Х8(10,5), Х9(10,5), Х10(10,6), Х11(11,11). 4.2. Х1(0,9), Х2(2,2), Х3(2,3), Х4(2,8), Х5(3,7), Х6(8,4), Х7(8,5), Х8(9,4), Х9(9,5), Х10(11,11). 4.3. Х1(0,6), Х2(6,6), Х3(7,7), Х4(8,8), Х5(7,15), Х6(8,15), Х7(9,15), Х8(10,15), Х9(11,15), Х10(14,2), Х11(15,3), Х12(16,4). 4.4. Х1(1,4), Х2(1,5), Х3(1,6), Х4(1,4), Х5(5,0), Х6(6,0), Х7(7,0), Х8(6,1), Х9(5,5), Х10(6,6), Х11(7,7), Х12(8,8). 4.5. Х1(0,2), Х2(2,2), Х3(2,3), Х4(2,4), Х5(5,0), Х6(6,0), Х7(7,0), Х8(8,4), Х9(8,5), Х10(9,4), Х11(9,5), Х12(10,10). б) К = 4;
= 1;
= 1;
=4; L = 0; І =4. 4.6. Х1(3,10), Х2(3,3), Х3(3,4), Х4(3,9), Х5(4,8), Х6(9,5), Х7(9,6), Х8(10,5), Х9(10,5), Х10(10,6), Х11(11,12). 4.7. Х1(2,8), Х2(2,1), Х3(2,3), Х4(2,8), Х5(3,7), Х6(8,4), Х7(8,5), Х8(9,4), Х9(9,5), Х10(10,11). 4.8. Х1(3,5), Х2(2,2), Х3(2,3), Х4(2,4), Х5(5,0), Х6(6,0), Х7(7,0), Х8(8,4), Х9(8,5), Х10(9,4), Х11(9,5), Х12(10,9). 4.9. Х1(1,3), Х2(0,5), Х3(0,7), Х4(1,4), Х5(5,0), Х6(6,0), Х7(7,0), Х8(6,1), Х9(5,5), Х10(6,6), Х11(7,7), Х12(8,8). 4.10. Х1(3,5), Х2(6,6), Х3(7,7), Х4(8,8), Х5(7,15), Х6(8,15), Х7(9,15), Х8(10,15), Х9(11,15), Х10(14,2), Х11(15,3), Х12(17,4). в) К = 3;
= 2;
= 1;
=4; L = 1; І =5. 4.11. Х1(0,3), Х2(2,2), Х3(2,3), Х4(2,4), Х5(5,0), Х6(6,0), Х7(7,0), Х8(8,4), Х9(8,5), Х10(9,4), Х11(9,5), Х12(9,9). 4.12. Х1(1,3), Х2(0,5), Х3(1,6), Х4(1,4), Х5(5,0), Х6(6,0), Х7(7,0), Х8(6,1), Х9(5,5), Х10(6,6), Х11(7,7), Х12(8,9). 4.13. Х1(2,3), Х2(6,6), Х3(7,7), Х4(8,8), Х5(7,15), Х6(8,15), Х7(9,15), Х8(10,15), Х9(11,15), Х10(14,2), Х11(15,3), Х12(16,4). 4.14. Х1(2,10), Х2(3,3), Х3(3,4), Х4(3,9), Х5(4,8), Х6(9,5), Х7(9,6), Х8(10,5), Х9(10,5), Х10(10,6), Х11(12,12). 4.15. Х1(2,7), Х2(2,2), Х3(2,3), Х4(2,8), Х5(3,7), Х6(8,4), Х7(8,5), Х8(9,4), Х9(9,5), Х10(11,11). г) К = 3;
= 2;
= 1;
=5; L = 0; І =5. 4.16. Х1(1,5), Х2(2,2), Х3(2,3), Х4(2,4), Х5(5,0), Х6(6,0), Х7(7,0), Х8(8,4), Х9(8,5), Х10(9,4), Х11(9,5), Х12(9,8). 4.17. Х1(0,4), Х2(0,5), Х3(0,6), Х4(1,4), Х5(5,0), Х6(6,0), Х7(7,0), Х8(6,2), Х9(5,5), Х10(6,6), Х11(7,7), Х12(9,9). 4.18. Х1(1,9), Х2(2,2), Х3(2,3), Х4(2,5), Х5(3,7), Х6(8,4), Х7(8,5), Х8(9,4), Х9(9,5), Х10(9,10). 4.19. Х1(5,5), Х2(6,6), Х3(7,7), Х4(8,8), Х5(7,15), Х6(8,15), Х7(9,15), Х8(10,15), Х9(11,15), Х10(14,2), Х11(15,3), Х12(15,4). 4.20. Х1(2,9), Х2(3,3), Х3(3,4), Х4(3,9), Х5(4,8), Х6(9,5), Х7(9,6), Х8(10,5), Х9(10,5), Х10(10,6), Х11(11,9). ґ) К = 2;
= 2;
= 1;
=5; L = 0; І =5. 4.21. Х1(0,3), Х2(0,4), Х3(0,6), Х4(1,4), Х5(5,0), Х6(6,2), Х7(7,1), Х8(6,1), Х9(5,5), Х10(6,6), Х11(7,7), Х12(8,9). 4.22. Х1(5,7), Х2(5,5), Х3(7,7), Х4(8,8), Х5(7,15), Х6(8,15), Х7(9,15), Х8(10,15), Х9(11,15), Х10(13,3), Х11(15,3), Х12(16,5). 4.23. Х1(0,1), Х2(1,3), Х3(3,4), Х4(3,9), Х5(4,8), Х6(8,5), Х7(9,6), Х8(10,5), Х9(10,5), Х10(10,6), Х11(10,12). 4.24. Х1(1,10), Х2(2,2), Х3(3,3), Х4(2,8), Х5(3,7), Х6(8,4), Х7(8,5), Х8(9,4), Х9(9,5), Х10(10,10). 4.25. Х1(1,5), Х2(1,2), Х3(2,3), Х4(2,4), Х5(5,0), Х6(6,1), Х7(7,0), Х8(8,4), Х9(9,5), Х10(9,4), Х11(9,6), Х12(10,10). 5. ЗМІСТ ЗВІТУ 5.1. Мета роботи. 5.2. Блок схема алгоритму ІСОМАД. 5.3. Лабораторне завдання. 5.4. Результати виконання індивідуального завдання. 5.5. Аналіз результатів та помилок, допущених при виконанні роботи. 5.6. Висновки. 6. Література 6.1. Ту Дж., Гонсалес Р. Принцыпы распознавания образов.М.,Мир,1978 6.2. Фор А. Восприятие и распознавание образов.М.,Машиностроение,1989 6.3. А.Л.Горелик, В.А.Скрипкин. Методы распознавания: Учеб. Пособие для вузов. 3-е изд., перераб. И доп.- М.: Высш.шк., 1989.-232 с. 6.4. А.Л.Горелик, В.А.Скрипкин. Некоторые вопросы построения систем распознавания. М., Сов. Радио, 1974, 224 с.