МІНІСТЕРСТВО ОСВІТИ УКРАЇНИ Національний університет “Львівська політехніка” ДОСЛІДЖЕННЯ АЛГОРИТМІВ РОЗПІЗНАВАННЯ ОБРАЗІВ. АЛГОРИТМ МАКСИМIННОЇ ВIДСТАНI Методичні вказівки до лабораторної роботи №2 з курсу “Основи проектування систем штучного інтелекту” для студентів базового напрямку 6.08.04 “Комп’ютерні науки” ЗАТВЕРДЖЕНО на засіданні кафедри Системи автоматизованого проектування Протокол №__ від ___________1999р. Львів 1999 ДОСЛІДЖЕННЯ АЛГОРИТМІВ РОЗПІЗНАВАННЯ ОБРАЗІВ. АЛГОРИТМ МАКСИМIННОЇ ВIДСТАНI. Методичні вказівки до лабораторної роботи №1 з курсу “Основи проектування систем штучного інтелекту” для студентів базового напрямку 6.08.04 “Комп’ютерні науки”./Укл.А.Б.Керницький, Ю.В.Стех – Львів: НУ”ЛП”, 1999р.- 7 с. Укладачі А.Б.Керницький, асистент, Ю.В.Стех, канд.техн.наук, доц. Відповідальний за випуск С.П.Ткаченко, канд.техн.наук, доц. Рецензенти В.М.Теслюк, канд.техн.наук, доц. О.М.Матвійків, канд.техн.наук, доц. 1.Мета роботи Вивчити принципи роботи максимінного алгоритму розпізнавання образів. Написати програму реалізації алгоритму з графічним інтерфейсом користувача. 2. Короткі теоретичні відомості 2.1. Максимінний алгоритм розпізнавання образів Алгоритм використовує евклiдову вiдстань. Алгоритм, у принципi, аналогiчний схемi евристичного алгоритму порогової величини, за виключенням тiєї обставини, що, в першу чергу, вин виявляє найвiддален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лення кластера, не виконується. ( 1. Z1=X1 2. Обчислити Di1 3. Вибрати Ki(1)=max{Di1} ( i(1 ; L1=Ki(1) ( 4. Z2=Xi 5. Обчислити Di1, Di2 ( i(1,2 6. Обчислити Ai=min{Di1,Di2} ( i(1,2 7. Обчислити Ki(2)=max{Ai} ( i(1,2 ; L2=Ki(2) ( 8. Якщо L2>0.5L1, тодi Z3=Xi. Iнакше - STOP. 9. Визначити середню арифметичну величину попереднiх максимальних вiдстаней: Lc.a.=(L1+L2)/2 10. Обчислити Di1, Di2, Di3 ( i(1,2,3 11. Обчислити Ai=min{Di1, Di2, Di3} 12. Обчислити Ki(3)=max{Ai} ; L3=Ki(3) ( 13. Якщо Li>0.5La.c., тодi Z4=Xi. Iнакше - STOP. 14. Обчислити Lc.a.=(L1+L2+L3)/3 3. КОНТРОЛЬНІ ЗАПИТАННЯ 3.1. Поняття систем розпізнавання без навчання, таких, що навчають та самонавчальних. 3.2. Переваги та недоліки максимінного алгоритму. 3.3. Схема алгоитму. 3.4. Умова збіжності максимінного алгоритму. 4. ІНДИВІДУАЛЬНЕ ЗАВДАННЯ Здійснити розпізнавання образів із застосуванням максимінного алгоритму. 4.1. Х1(0,1), Х2(0,3), Х3(1,2), Х4(2,3), Х5(2,8), Х6(2,10), Х7(3,9), Х8(4,5), Х9(4,10), Х10(7,6), Х11(7,7), Х12(8,7), Х13(8,7), Х14(8,8), Х15(10,3), Х16(11,3), Х17(11,2). 4.2. Х1(0,1), Х2(0,2), Х3(0,3), Х4(4,1), Х5(5,1), Х6(5,2), Х7(5,3), Х8(6,9), Х9(8,6), Х10(9,2), Х11(9,5), Х12(9,6), Х13(9,7), Х14(10,1), Х15(10,2), Х16(10,3), Х17(11,3). 4.3. Х1(0,1), Х2(2,0), Х3(1,1), Х4(2,1), Х5(3,1), Х6(2,2), Х7(7,5), Х8(7,6), Х9(19,6), Х10(19,7), Х11(18,9), Х12(19,8), Х13(20,8), Х14(10,9), Х15(11,9), Х16(9,10), Х17(10,10), Х18(10,11). 4.4. Х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(10,10), Х11(7,7), Х12(8,7), 4.5. Х1(1,4), Х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), Х13(12,7), Х14(12,12), Х15(0,3). 4.6. Х1(0,4), Х2(0,5), Х3(0,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), Х13(12,7), Х14(12,12), Х15(0,3). 4.7. Х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(16,4). 4.8. Х1(2,10), Х2(3,3), Х3(3,4), Х4(3,9), Х5(4,8), Х6(0,5), Х7(9,6), Х8(10,5), Х9(10,5), Х10(10,6), Х11(11,11), Х12(0,4). 4.9. Х1(1,2), Х2(1,3), Х3(1,4), Х4(1,5), Х5(2,2), Х6(2,3), Х7(2,4), Х8(3,7), Х9(3,8), Х10(3,9), Х11(4,8), Х12(4,9), Х13(10,6), Х14(10,7), Х15(13,4), Х16(13,5), Х17(13,6). 4.10. Х1(2,0) ,Х2(3,0), Х3(2,2), Х4(3,2), Х5(4,2), Х6(3,3), Х7(8,6), Х8(8,7), Х9(20,7), Х10(20,8), Х11(19,10), Х12(20,9), Х13(21,9), Х14(11,10), Х15(12,10), Х16(10,11), Х17(11,11), Х18(11,12). 4.13. Х1(1,0), Х2(1,3), Х3(1,4), Х4(1,5), Х5(2,2), Х6(2,3), Х7(2,4), Х8(3,7), Х9(3,8), Х10(3,9), Х11(4,8), Х12(4,9), Х13(10,6), Х14(10,7), Х15(13,4), Х16(13,5), Х17(13,6). 4.14. Х1(2,1) ,Х2(3,0), Х3(2,2), Х4(3,2), Х5(4,2), Х6(3,3), Х7(8,6), Х8(8,7), Х9(20,7), Х10(20,8), Х11(19,10), Х12(19,9), Х13(22,9), Х14(11,10), Х15(13,10), Х16(10,11), Х17(11,11), Х18(11,12). 4.16. Х1(1,1), Х2(1,2), Х3(0,2), Х4(2,4), Х5(2,9), Х6(2,9), Х7(3,8), Х8(4,4), Х9(3,10), Х10(7,6), Х11(7,8), Х12(8,8), Х13(8,7), Х14(8,9), Х15(10,3), Х16(11,3), Х17(11,2). 4.16. Х1(1,8), Х2(2,3), Х3(2,3), Х4(2,8), Х5(3,7), Х6(8,4), Х7(8,5), Х8(9,4), Х9(9,5), Х10(10,10), Х11(19,10), Х12(19,9), Х13(22,9), Х14(11,10). 4.11. Х1(1,1), Х2(0,3), Х3(0,4), Х4(4,1), Х5(5,1), Х6(5,2), Х7(5,3), Х8(6,9), Х9(8,6), Х10(9,2), Х11(9,5), Х12(9,6), Х13(9,7), Х14(10,1), Х15(10,2), Х16(10,3), Х17(11,3). 4.12. Х1(1,1), Х2(2,0), Х3(5,1), Х4(2,1), Х5(3,1), Х6(2,2), Х7(7,5), Х8(7,6), Х9(19,6), Х10(19,7), Х11(18,9), Х12(19,8), Х13(20,8), Х14(10,9), Х15(11,9), Х16(9,10), Х17(10,10), Х18(10,11). 4.17. Х1(4,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(16,4). 4.18. Х1(1,3), Х2(2,1), Х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.19. Х1(1,4), Х2(0,5), Х3(0,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.20. Х1(1,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(10,11). N 21 N 22 N 22 N 23 N 24 N 25  1 1 1 1 1 12 1 12 1 12 7 12  2 2 2 2 2 11 2 11 2 11 8 11  2,5 1 2,5 1 2,5 12 2,5 12 2,5 12 8 12  0 2 0 2 0 11 0 11 0 11 9 11  0 1 0 1 0,5 1 0 1 0 1 0,5 1  0,5 0,5 0,5 0,5 0,5 0,5 0,5 0,5 0 0 0,5 0,5  2 0,5 2 0,5 2 0,5 2 0,5 2 0,5 2 0,5  2 1,5 2 1,5 2 1,5 2 1,5 2 1,5 2 1,5  1 1,5 1 1,5 1 1,5 1 1,5 1 1,5 1 1,5  0,5 1,5 15 1,5 15 1,5 25 1,5 25 1,5 26 6  10 10 15 2 15 2 25 2 25 2 25 5  11 10 15 2,5 15 2,5 25 2,5 25 2,5 25 6  10 9 16 2 16 2 16 2 16 2 16 2  11 9 16 0,5 16 0,5 16 0,5 16 0,5 16 0,5  11 9,5 16 1 16 1 16 1 16 1 16 1  12 0 0 0 1 0 1 0 0 0 0 0  13 0 10 10 0 10 0 10 0 0 10 0  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 с. Навчальне видання ДОСЛІДЖЕННЯ АЛГОРИТМІВ РОЗПІЗНАВАННЯ ОБРАЗІВ. АЛГОРИТМ МАКСИМIННОЇ ВIДСТАНI Методичні вказівки до лабораторної роботи №1 з курсу “Основи проектування систем штучного інтелекту” для студентів базового напрямку 6.08.04 “Комп’ютерні науки” Укладачі А.Б.Керницький, асистент, Ю.В.Стех, канд.техн.наук, доц. Редактор Грабовська О.О.