Комплексний метод побудови вирішуючих правил імовірнісних систем автоматичного розпізнавання, що навчаються

Размещено на http://www.allbest.ru/

МІНІСТЕРСТВО ОСВІТИ І НАУКИ УКРАЇНИ

ДЕРЖАВНИЙ УНІВЕРСИТЕТ ІНФОРМАТИКИ І ШТУЧНОГО ІНТЕЛЕКТУ

Волченко Олена Володимирівна

УДК 004.048+681.327.1

КОМПЛЕКСНИЙ МЕТОД ПОБУДОВИ ВИРІШУЮЧИХ ПРАВИЛ ІМОВІРНІСНИХ СИСТЕМ АВТОМАТИЧНОГО РОЗПІЗНАВАННЯ, ЩО НАВЧАЮТЬСЯ

05.13.23 - Системи та засоби штучного інтелекту

АВТОРЕФЕРАТ

дисертації на здобуття наукового ступеня

кандидата технічних наук

Донецьк - 2008

ДИСЕРТАЦІЄЮ Є РУКОПИС

Роботу виконано на кафедрі програмного забезпечення інтелектуальних систем Державного університету інформатики і штучного інтелекту Міністерства освіти і науки України.

Науковий керівник:

доктор технічних наук, професор

Скобцов Юрій Олександрович,

завідувач кафедри «Автоматизовані системи управління» ДВНЗ «Донецький національний технічний університет» Міністерства освіти і науки України, м. Донецьк

Офіційні опоненти:

доктор технічних наук

Кучеренко Євген Іванович,

професор кафедри штучного інтелекту Харківського національного університету радіоелектроніки Міністерства освіти і науки України, м. Харків

кандидат фізико-математичних наук

Козловський Валерій Анатолійович,

старший науковий співробітник, завідувач лабораторією дискретної математики і прикладної алгебри Інституту прикладної математики та механіки НАН України, м. Донецьк

Захист відбудеться “ 13 ” червня 2008 р. о 14 годині на засіданні спеціалізованої вченої ради К 11.243.01 у Державному університеті інформатики і штучного інтелекту за адресою: 83050, м. Донецьк, пр. Б. Хмельницького 84.

З дисертацією можна ознайомитися в бібліотеці Державного університету інформатики та штучного інтелекту за адресою: 83050, м. Донецьк, вул. Р. Люксембург, 34а.

Автореферат розісланий “ 13 ” травня 2008 р.

Вчений секретар

спеціалізованої вченої ради К 11.243.01 Полівцев С.О.

ЗАГАЛЬНА ХАРАКТЕРИСТИКА РОБОТИ

Актуальність теми. Створення систем автоматичного розпізнавання (САРЗ) є одним з напрямків штучного інтелекту (ШІ), що найбільш інтенсивно розвивається. Це пояснюється не тільки очевидною необхідністю використання цих систем у всіх галузях життєдіяльності людини, але й новим підходом до їхньої реалізації, що полягає у використанні сучасних технологій штучного інтелекту, які суттєво поліпшують якість одержуваних рішень. До таких технологій можна віднести експертні й мультиагентні системи, штучні нейронні мережі, генетичні алгоритми, ДНК-обчислення, когнітивне моделювання, дедуктивні моделі.

З розширенням сфери застосування САРЗ, яке обумовлене у першу чергу розвитком інформаційних технологій і систем, стало очевидним, що для забезпечення високої ефективності й швидкості розпізнавання необхідне створення комплексних методів, що базуються на знаннях з різних наукових галузь. Одним з найбільш характерних прикладів даного твердження є застосування систем розпізнавання у комп'ютерній лінгвістиці - напрямку теорії штучного інтелекту, що займається автоматичною обробкою природних мов та є базовою при створенні систем дистанційного навчання, побудові глобальних розподілених інформаційних структур і пошукових систем, систем тематичної класифікації текстів і реферування. Для вирішення задач автоматичної обробки природних мов застосовуються методи, засновані на морфологічному й латентно-семантичному аналізі для виділення ключових слів текстів, теорія математичної статистики для формування вектора частот ключових слів, теорія розпізнавання образів для реалізації завдань класифікації.

Серед різних типів САРЗ найбільше застосування при рішенні прикладних задач одержали імовірнісні САРЗ відкритого типу, що навчаються. Особливістю таких систем є можливість постійного доповнення навчальної інформації, що спричиняє необхідність побудови вирішуючих правил класифікації при виконанні розпізнавання й, відповідно, зберігання навчальних вибірок даних. Значна кількість сучасних прикладних завдань, розв'язуваних шляхом побудови САРЗ, що навчаються, характеризується великим обсягом вихідних даних, що значно знижує ефективність систем і суттєво збільшує часові витрати на виконання розпізнавання. Так для завдання пошуку й класифікації текстів у мережі Інтернет навчальні вибірки можуть містити кілька десятків тисяч документів. Застосування відомих методів побудови вирішуючих правил класифікації для навчальних вибірок великого обсягу є малоефективним, тому розробка методів перетворення навчальних вибірок і побудови вирішуючих правил класифікації для САРЗ, що навчаються, із застосуванням технологій штучного інтелекту є актуальним науково-технічним завданням.

Зв'язок роботи з науковими програмами, планами, темами. Дисертаційна робота виконана протягом 2005-2008 років відповідно до наукового напрямку кафедри програмного забезпечення інтелектуальних систем Державного університету інформатики і штучного інтелекту в рамках держбюджетної теми «Розробка теоретичних основ і засобів практичної реалізації сучасних комп'ютерних інтелектуальних технологій» (№0104U000116).

Мета і задачі дослідження. Метою дисертаційної роботи є розробка методу побудови вирішуючих правил імовірнісних систем автоматичного розпізнавання відкритого типу, що навчаються, який дозволяє підвищити якість розпізнавання і знизити часові витрати на побудову вирішуючого правила і виконання класифікації.

Для досягнення поставленої мети в дисертації слід вирішити такі завдання.

Провести огляд і аналіз сучасного стану задачі побудови САРЗ, методів побудови вирішуючих правил класифікації у ймовірнісних системах автоматичного розпізнавання, що навчаються, та методи їх оптимізації. Виділити особливості застосування для її вирішення технологій ШІ, визначити найбільш перспективні напрями подальших досліджень.

Розробити комплексний метод побудови вирішуючих правил класифікації ймовірнісних САРЗ відкритого типу, що навчаються, об'єднуючий метод перетворення початкової навчальної вибірки і метод побудови вирішуючих правил класифікації з використанням технологій ШІ.

Створити експериментальну програмну систему для оцінки якості розроблених методів окремо і комплексного методу в цілому.

Провести експериментальні дослідження запропонованих методів, виконати аналіз отриманих результатів за допомогою порівняння з результатами роботи відомих методів рішення даної задачі.

Виконати аналіз ефективності застосування запропонованого комплексного методу при рішенні задач тематичного аналізу текстів.

Об'єктом дослідження. Об'єктом дослідження дисертаційної роботи є системи автоматичного розпізнавання, що навчаються.

Предметом дослідження. Предметом дослідження є методи побудови вирішуючих правил САРЗ, що навчаються, зокрема із застосуванням технологій штучного інтелекту, і способи обробки начальних вибірок для оптимізації одержуваних вирішуючих правил.

Методи дослідження. Теоретичні дослідження, виконані в роботі, ґрунтуються на використанні теорії побудови САРЗ, комп'ютерній лінгвістиці, теорії генетичних алгоритмів, теорії множин і математичної статистики, а також ряді методів, запропонованих автором в роботах з даної тематики. Експериментальні оцінки запропонованих методів засновані на методах статистичної обробки експериментальних даних та імітаційного моделювання.

Наукова новизна одержаних результатів роботи визначається наступними отриманими автором теоретичними і експериментальними результатами.

1. Вперше запропонований і обґрунтований метод побудови скороченої зваженої навчальної вибірки мета-об'єктів, вага яких, на відміну від відомих раніше методів визначення ваги об'єктів навчальної вибірки, розраховується до побудови вирішуючих правил класифікації, що дозволило істотно скоротити навчальну вибірку. Запропонований новий метод коректного додавання даних у вибірку мета-об'єктів, яке є необхідною умовою створення систем автоматичного розпізнавання відкритого типу, що навчаються.

2. Одержав подальший розвиток метод потенційних функцій шляхом розповсюдження його на зважені навчальні мета-вибірки, що дозволило використовувати при побудові вирішуючих правил не тільки значення ознак розпізнаваних об'єктів, але й знання про розташування об'єктів навчальної вибірки у просторі ознак.

3. Розроблений генетичний алгоритм побудови вирішуючих правил класифікації, в якому вперше правило представлене у вигляді псевдобулевої функції, запропонований спосіб імовірнісного формування початкової популяції хромосом, що враховує вагу об'єктів навчальної вибірки, запропонований метод обчислення подвійної фітнес-функції, визначений і теоретично обґрунтований набір генетичних операторів.

4. Запропонований новий метод побудови вирішуючих правил імовірнісних систем автоматичного розпізнавання відкритого типу, що навчаються, який комплексно включає спосіб визначення відособленості класів, метод формування зваженої навчальної вибірки мета-об'єктів, генетичний алгоритм побудови вирішуючого правила, що дозволив підвищити якість розпізнавання, знизити часові витрати на побудову вирішуючих правил і виконання класифікації, скоротити об'єм даних, що зберігаються.

Достовірність запропонованих теоретичних положень підтверджена експериментальними результатами на тестових даних і на прикладі задачі тематичного аналізу текстів.

Практичне значення одержаних результатів. Розроблений в дисертаційній роботі комплексний метод побудови вирішуючих правил класифікації в цілому і методи, що входять до його складу, окремо можуть бути застосовані для вирішення завдань розпізнавання, в яких об'єкти описуються безліччю числових параметрів, і вирішуюче правило класифікації повинно бути знайдене в результаті навчання. Особливу значущість отримані результати мають для САРЗ відкритого типа, що навчаються. Таким чином, розроблений комплексний метод є теоретичною основою створення систем штучного інтелекту різноманітного призначення.

У експериментах на тестових даних запропонований комплексний метод показав збільшення розпізнавальної здатності отриманих вирішуючих правил у порівнянні з вирішуючими правилами, побудованими класичними методами, в середньому на 11% і скорочення часу класифікації розпізнаваних об'єктів за побудованими вирішуючими правилами на 36%.

Застосування розробленого комплексного методу для вирішення задачі побудови спам-фільтрів при фільтрації вхідної електронної кореспонденції, що є однією з найбільш актуальних задач комп'ютерної лінгвістики, привело до підвищення точності класифікації листівок в середньому на 37%.

У дисертації закладений базис для подальшого розвитку теоретичних засад розробки систем штучного інтелекту, орієнтованих на побудову САРЗ, що навчаються, з використанням зважених навчальних вибірок.

Наукові положення, теоретичні та експериментальні результати, викладені в дисертації, були використані при проведенні лабораторних занять і читанні курсів лекцій з дисциплін «Технології ШІ в управлінні», «Еволюційне програмування», «Основи побудови систем розпізнавання образів», «Обробка апріорної інформації в системах розпізнавання образів» на кафедрі програмного забезпечення інтелектуальних систем Державного університету інформатики і штучного інтелекту.

Практична цінність дисертації підтверджується актами про використання отриманих результатів у науково-дослідних роботах відділу розпізнавання мовних образів Донецького інституту проблем штучного інтелекту МОН і НАН України та в розробках ТОВ «Бі-Тек».

Особистий внесок здобувача. Всі основні положення, теоретичні і практичні результати дисертаційної роботи, що виносяться на захист, отримані автором самостійно.

Апробація результатів дисертації. Основні наукові результати дисертаційного дослідження доповідалися та обговорювалися на 7-ми конференціях і семінарах:

V міжнародній науково-практичній конференції «Комп'ютерні системи в автоматизації виробничих процесів» (Хмельницький національний університет, Хмельницький, Україна, 2007 р.);

II міжнародній науковій конференції «Компьютерные науки и информационные технологии» (Саратовський державний університет ім. М.Г. Чернишевського, Саратов, Росія, 2007 р.);

VIII міжнародній науково-технічній конференції «Искусственный интеллект-2007» (Дивноморське, Росія, 2007 р.);

II міжнародній науковій конференції «Современные информационные системы. Проблемы и тенденции развития» (Туапсе, Росія, 2007 р.);

I міжнародній науково-технічній конференції «Інтелектуальні системи в промисловості і освіті - 2007» (Сумський державний університет, Суми, Україна, 2007 р.);

науковому семінарі відділу теорії управляючих систем Інституту прикладної математики та механіки НАН України;

межкафедральному науковому семінарі Державного університету інформатики та штучного інтелекту.

Публікації. Основні результати дисертаційної роботи викладено у 10 наукових роботах, серед яких 5 статей в провідних спеціалізованих виданнях, що входять до переліку ВАК України, та 5 публікацій в збірках матеріалів міжнародних наукових конференцій.

Структура і обсяг дисертації. Дисертаційна робота складається зі вступу, чотирьох розділів, висновків, списку використаних джерел (12 сторінок, 135 найменування) та додатку. Робота містить 24 рисунки на 10 сторінках, 16 таблиць. Загальний обсяг дисертації - 150 сторінок. Повний обсяг дисертації (включаючи список використаних джерел, рисунки та додатки) становить 173 сторінки.

ОСНОВНИЙ ЗМІСТ РОБОТИ

У вступі обґрунтовано актуальність теми дисертації, показано її наукову та практичну цінність, сформульовані мета і задачі дослідження, методи їх виконання. Наведені основні положення, що виносяться на захист, ступінь їх апробації і публікації.

У першому розділі проведено аналіз сучасного стану досліджень в області побудови САРЗ. Як найбільш затребувані виділені САРЗ відкритого типа, що навчаються; як найбільш складне завдання - завдання побудови вирішуючих правил класифікації в результаті навчання. Розглянуті методи побудови вирішуючих правил САРЗ, що навчаються, критерії їх оцінки. За наслідками аналізу розглянутих методів зроблений висновок про ефективність використання евристичних методів при побудові вирішуючих правил класифікації для підвищення ефективності розпізнавання і методів скорочення розміру навчальних вибірок, що мають значний об'єм у багатьох сучасних САРЗ і необмежено зростають в системах відкритого типу, для зменшення об'єму даних, що зберігаються, і часу виконання класифікації. Серед евристичних методів рішення даного виду завдань виділені генетичні алгоритми. Приведені основні теоретичні положення генетичних алгоритмів і виконаний аналіз способів їх використання в задачах побудови САРЗ.

На основі результатів аналізу предметної галузі сформульована мета роботи, вирішувані завдання і прийняті обмеження.

Другий розділ присвячено розробці комплексного методу побудови вирішуючих правил в імовірнісних САРЗ відкритого типа, що навчаються, ефективного як за якістю розпізнавання об'єктів контрольної вибірки, так і за часовими витратами на побудову вирішуючих правил і виконання класифікації.

У підрозділі 2.1 представлена задача класифікації, що розглядається в роботі.

Дана множина об'єктів M, званих надалі допустимими. Кожен об'єкт описується системою ознак, тобто

.

Надалі вважатимемо, що множина M представлена у вигляді об'єднання непересічних підмножин (класів) {V₁,…,V_l}:

.

Є скінчений набір об'єктів

,

, про кожен з яких відомо, до якого класу він належить (це навчальні об'єкти, що становлять навчальну вибірку).

Потрібно по пред'явленому набору значень ознак - опису деякого об'єкту

з M розпізнати його, тобто визначити клас, до якого він належить.

Класифікація розпізнаваного об'єкту здійснюється за допомогою алгоритму, званого вирішуючим правилом класифікації

(1)

де - значення предиката

, , ,

обчислене по множині об'єктів , що представляє i-й клас системи.

В якості алгоритму А в даній роботі використовується функція вигляду

(2)

де - функція відстані між m-им об'єктом навчальної вибірки та розпізнаваним об'єктом , ;

- коефіцієнт коректування, що однозначно визначає приналежність об'єкту одному з класів системи.

В якості критерію оцінки побудованого вирішуючого правила використовується кількість невірних класифікацій об'єктів контрольної вибірки - множина допустимих об'єктів

,

з M, по яких не проводилося навчання

(3)

= 1,

якщо i-й об'єкт класифіковано невірно.

Виконаний в підрозділі 2.2 попередній аналіз можливих способів розташування об'єктів навчальної вибірки в просторі ознак показав, що доцільним є використання методів побудови вирішуючих правил класифікації, різних для відособлених (можливо лінійне розділення) і пересічних в просторі ознак класів.

Для виявлення відособленості класів в просторі ознак в підрозділі 2.3 був запропонований новий критерій, що полягає в побудові кардинальної гіперплощини по найбільш близько розташованим об'єктам даної пари класів і оцінці можливості вірної класифікації цією гіперплощиною всіх об'єктів навчальної вибірки. Він полягає у виконанні наступних кроків.

Метод побудови кардинальної гіперплощини.

1. Розраховується відстань між всіма парами об'єктів двох класів початкової навчальної вибірки

,

Де

, .

2. Знаходиться пара об'єктів , звана кардинальною парою, відстань між якими мінімальна

.

3. Будується гіперплощина Г, звана кардинальною гіперплощиною, яка перетинає відрізок, що з'єднує об'єкти кардинальної пари

(4)

де

.

4. За критерієм (3) обчислюється міра .

Якщо

,

то є вирішуючим правилом і може бути використано для розпізнавання.

Якщо , то класи не можуть бути розділені кардинальною гіперплощиною і необхідне подальше уточнення вирішуючого правила класифікації.

Аналіз особливостей розташування об'єктів навчальної вибірки в просторі ознак показав, що існують області простору ознак, в яких розташовані тільки об'єкти одного класу. Об'єкти таких областей при виконанні розпізнавання класифікуватимуться однаково і, очевидно, можуть бути замінені одним об'єктом, який описує всю область, що дозволить скоротити розмір початкової навчальної вибірки.

У підрозділі 2.4 для скорочення розміру навчальної вибірки запропонований новий метод об'єднання розташованих поруч в просторі ознак об'єктів одного класу в мета-об'єкти, що містять окрім значень ознак інформацію про кількість об'єднаних в них об'єктів початкової вибірки.

Об'єкт нової навчальної вибірки, побудований в результаті об'єднання розташованих поруч об'єктів початкової вибірки, назвемо мета-об'єктом, навчальну вибірку, складену з мета-об'єктів, - мета-вибіркою.

Метод побудови навчальної вибірки мета-об'єктів.

1. Розраховується відстань між всіма парами об'єктів навчальної вибірки

,

Де

; .

2. Вибирається об'єкт f (початкова точка формування мета-об'єкту) одного з класів k₁, для якого сума відстаней до всіх об'єктів найбільш близько розташованого класу k₂ максимальна

.

3. Знаходяться об'єкти S_o, (конкуруючі точки), кожний з яких знаходиться на мінімальній відстані від f серед об'єктів свого класу

.

4. Вибираються всі об'єкти класу k₁, відстань до яких f менша, ніж до найближчого S_o і вони поміщаються в множину W_f

.

5. Формується мета-об'єкт з одержаної множини об'єктів W_f, значення ознак якого розраховуються як координати центру мас системи з t матеріальних точок (вважається, що об'єкти початкової навчальної вибірки, що є у просторі ознак матеріальними точками, мають масу, рівну 1 одиниці маси

система автоматичний розпізнавання комплексний

), .

Отриманий мета-об'єкт зі значеннями ознак і вагою m_f =p, належить тому ж класу, що і об'єкти множини W_f.

6. Видаляються з початкової вибірки всі об'єкти, включені в мета-об'єкт .

7. Виконуються пункти 2-5 до тих пір, поки в початковій навчальній вибірці не залишиться жодного об'єкту.

Відзначимо, що метод побудови мета-вибірки може використовуватися як для двохкласових, так і для багатокласових систем і характеризується наступними особливостями: один мета-об'єкт може містити від 1 до об'єктів початкової навчальної вибірки; два мета-об'єкти не можуть містити один і той же об'єкт початкової вибірки; мета-об'єкт відноситься до того ж класу, що і всі об'єкти, в нього включені. Вибір способів знаходження початкової і конкуруючої точок побудови мета-об'єктів був здійснений з декількох запропонованих варіантів за наслідками проведених експериментальних досліджень.

Для забезпечення коректної роботи САРЗ відкритого типу при додаванні об'єктів в роботі запропонований метод додавання об'єктів в навчальну мета-вибірку. Особливістю запропонованого методу є виявлення можливості включення об'єктів, що додаються, у вже наявні мета-об'єкти (якщо відстань в просторі ознак від об'єкту, що додається, до найближчого мета-об'єкту цього ж класу менша за відстань до найближчого мета-об'єкту іншого класу) або необхідності побудови нового мета-об'єкту. Оскільки мета-об'єкти окрім значень ознак характеризуються масою, то для розрахунку «ступеня близькості» між ними використовується міра, аналогічна мірі розрахунку сили тяжіння між зарядженими матеріальними точками різної маси.

Метод додавання об'єктів в навчальну мета-вибірку.

1. Розраховується сила тяжіння між об'єктом, що додається, і всіма мета-об'єктами всіх класів

,

Де

, , , .

2. Вибираються мета-об'єкти , (по одному для кожного з класів системи), що мають найбільшу силу тяжіння до об'єкту серед об'єктів свого класу:

3. Серед об'єктів , визначається мета-об'єкт, що має найбільшу силу тяжіння до об'єкту , і номер його класу

4. Визначається можливість включення у мета-об'єкт або створення нового мета-об'єкту за правилами:

Якщо , то включається в , тобто

Якщо , то створюється новий мета-об'єкт

,

і належить тому ж класу, що і .

Виділимо основні особливості запропонованих в роботі методів обробки початкових навчальних вибірок для систем розпізнавання відкритого типу. Метод побудови навчальної вибірки мета-об'єктів дозволяє скоротити об'єм даних, по яких проводиться навчання, тобто зменшити час побудови вирішуючих правил класифікації і понизити вимоги до ресурсів системи, оскільки в системах розпізнавання відкритого типу необхідне зберігання навчальної вибірки. Метод додавання даних у вибірку мета-об'єктів дозволяє аналізувати необхідність розширення навчальної вибірки шляхом створення нових мета-об'єктів або додавання даних у вже створені, і аналізувати необхідність перестроювання вирішуючих правил у разі невірної класифікації даних, що додаються. У сукупності ці методи дозволяють виконувати ефективне формування навчальної вибірки у САРЗ відкритого типу.

Необхідність врахування маси мета-об'єктів при побудові вирішуючих правил класифікації приводить до необхідності коректування самих алгоритмів побудови вирішуючих правил класифікації, і, разом з тим, дозволяє здійснювати ефективнішу класифікацію розпізнаваних об'єктів.

У підрозділі 2.5 пропонується метод побудови вирішуючих правил для зважених навчальних вибірок. Як основа для розробки методу побудови зважених вирішуючих правил класифікації був вибраний метод потенційних функцій.

Характеристику мета-об'єкту, яка використоіується при побудові вирішуючих правил класифікації і містить інформацію про об'єкти навчальної вибірки, в нього включені, називатимемо вагою мета-об'єкту. Вирішуюче правило класифікації, побудоване по зваженій навчальній вибірці, - зваженим вирішуючим правилом.

Проведені в роботі експериментальні дослідження показали, що масу мета-об'єктів найефективніше враховувати в коефіцієнтах коректування вирішуючого правила (2):

де P_m - маса i-ого мета-об'єкта, .

Таким чином, в результаті запропонованого способу розрахунку коефіцієнтів коректування, в роботі одержано метод потенційних функцій для зважених навчальних вибірок.

Оцінку ефективності зважених вирішуючих правил здійснюватимемо по кількості невірних класифікацій об'єктів контрольної вибірки (3) і по довжині одержуваного вирішуючого правила класифікації:

(5)

За наслідками проведених експериментальних досліджень ефективності методу побудови зважених вирішуючих правил було одержано, що як і в класичному методі потенційних функцій, одержувані рішення істотно залежать від порядку проходження мета-об'єктів в навчальній мета-вибірці.

У підрозділі 2.6 для подолання такої залежності був розроблений генетичний алгоритм побудови вирішуючих правил класифікації, що має наступні особливості.

При виборі способу кодування хромосом генетичного алгоритму вирішуюче правило класифікації було представлено у вигляді псевдобулевої функції.

Вводиться двійковий вектор

,

Де

Вирішуюча функцію представляється у вигляді:

(6)

Очевидно, що (6) є лінійною псевдобулевою функцією

.

Завданням побудови функції , що реалізується за допомогою генетичного алгоритму, назвемо завдання знаходження двійкового вектора X, що задовольняє критерію (5). Таким чином, для вирішення завдання побудови вирішуючого правила класифікації в генетичному алгоритмі використані хромосоми, що є двійковими векторами.

Для звуження простору пошуку рішень генетичним алгоритмом у роботі був запропонований метод розрахунку подвійної фітнес-функції, який полягає у видаленні декількох генів з хромосом, розрахунку для кожної зі скорочених хромосом декількох фітнес-функцій, відповідних значенням видалених генів, і виборі в якості хромосоми кращої за розрахованими значеннями фітнес-функцій.

Для побудови вирішуючих правил, ефективних як за якістю розпізнавання, так і по довжині одержуваних вирішуючих правил в роботі був запропонований новий підхід до вибору стратегії елітізма. Так фітнес-функція в генетичному алгоритмі обчислюється за кількістю невірно класифікованих об'єктів вирішуючим правилом, побудованим по хромосомі X_i:

Вибір елітних хромосом, які переходять у наступну популяцію без застосування генетичних операторів, здійснюється серед хромосом, що мають кращу фітнес-функцію, шляхом вибору хромосом з мінімальною кількістю одиничних генів.

Генерація хромосом початкової популяції здійснювалася з урахуванням розташування мета-об'єктів в просторі ознак. Для кожного з мета-об'єктів був розрахований ризик бути класифікованим невірно. Вірогідність для деякого гена хромосом початкової популяції прийняти одиничне значення була вибрана пропорційно розрахованому ризику невірної класифікації.

Виходячи з особливостей вирішуваної задачі, були вибрані наступні генетичні оператори:

- турнірний відбір для вибору батьківських хромосом;

- одноточковий кросинговер для формування нащадків;

- парна мутація, що міняє місцями два вибрані гени в хромосомі;

- циклічне зрушення, згідно якому значення і-го біта присвоюються (і-1)-ому біту для , а n-ому біту присвоюється 1-го біта;

- знижуюча мутація, яка міняє значення вибраного одиничного гена на нульове, що дозволить зменшувати довжину шуканої потенційної функції;

- підвищуюча мутація, яка міняє значення вибраного нульового гена на одиничне, що дозволить збільшувати довжину шуканої потенційної функції.

Вибір парної мутації і циклічного зрушення заснований на тому, що ці генетичні оператори не змінюють довжини вирішуючого правила, відповідного хромосомі, а тільки змінюють мета-об'єкти, які включені в це правило. Вибір підвищуючій та знижуючій мутацій, обумовлений необхідністю зміни довжини потенційної функції для зменшення кількості невірних класифікацій і часу виконання розпізнавання.

Зупинка генетичного алгоритму здійснюється при знаходженні вирішуючого правила, що вірно класифікує всі об'єкти навчальної вибірки або при генерації заданого числа поколінь.

У підрозділі 2.7 запропонований метод побудови вирішуючого правила класифікації для САРЗ відкритого типа, що навчаються, вживаний як для побудови вирішуючих правил по початковій вибірці, так і для його коректування при додаванні нових об'єктів в навчальну вибірку. Основною особливістю запропонованого методу є комплексний підхід до рішення задачі побудови ефективного вирішуючого правила класифікації, що стало можливим завдяки запропонованим в роботі способу визначення відособленості класів, методу формування зваженої навчальної вибірки мета-об'єктів, генетичному алгоритму побудови вирішуючого правила.

Третій розділ присвячено експериментальним дослідженням ефективності застосування запропонованого в роботі комплексного методу при побудові вирішуючих правил класифікації в імовірнісних САРЗ, що навчаються.

Приведений опис створеного програмного середовища для виконання експериментальних досліджень, генерації тестових даних і підсистеми реалізації обраних для порівняння та запропонованих у роботі методів рішення задачі побудови вирішуючих правил класифікації Приведена схема і запропонований опис інформаційних потоків і модулів програмної системи, описані принципи генерації тестових даних.

Для оцінки ефективності застосування запропонованого в роботі комплексного методу в цілому і методів, які входять до його складу, в експериментальних дослідженнях аналізувалася залежність якості одержуваних результатів від довжини навчальних вибірок і ступеня перетину класів в просторі ознак. Оцінювання здійснювалося за допомогою порівняння одержуваних результатів запропонованих у роботі методів з класичними методами рішення даних задач і в залежності від власних параметрів методів.

Експериментальні дослідження ефективності використання кардинальної гіперплощини як способу визначення відособленості класів показали, що вона дозволяє мінімально в 56% випадків виявити відособленість класів і отримати в якості вирішуючого правила кардинальну гіперплощину.

Аналіз проведених експериментів по побудові вибірок мета-об'єктів по початковим навчальних вибіркам показав, що метод побудови вибірок мета-об'єктів дозволяє скоротити початковий розмір в порівнянні в 50 разів для відособлених в просторі ознак класів і в 20 разів для об'єктів, класи яких перетинаються на 20%.

Необхідно відзначити, що обчислювальна складність методу побудови мета-вибірки склала , де l - кількість класів системи розпізнавання, що значно менше обчислювальної складності відомого алгоритму STOLP, що має обчислювальну складність порядку .

Оцінка коректності методу побудови мета-вибірки показала, що на відміну від відомих методів скорочення навчальних вибірок, метод побудови мета-вибірки не змінює закону розподілення значень ознак мета-об'єктів у порівнянні з об'єктами початкової вибірки, тобто зберігає початковий опис класу об'єктів розпізнавання.

Аналіз результатів побудови вирішуючих правил зваженим методом потенційних функцій по мета-вибірках показав, що його застосування в порівнянні з класичним методом потенційних функцій дозволяє збільшити ефективність розпізнавання побудованими вирішуючими правилами на 2,5% і зменшити довжину вирішуючого правила (час класифікації розпізнаваного об'єкту) на 30%.

Генетичний алгоритм побудови вирішуючих правил класифікації в порівнянні з класичним методом потенційних функцій дозволяє збільшити ефективність розпізнавання на 9,6%. Також було одержано, що запропоновані в роботі спосіб формування початкової популяції, метод розрахунку подвійної фітнес-функції і спосіб відбору елітних хромосом дозволяють досягати мінімальної кількості невірних класифікацій на початкових популяціях алгоритму, а далі виконується мінімізація довжини одержуваного вирішуючого правила за рахунок вибраного набору генетичних операторів.

Експериментальні дослідження ефективності застосування комплексного методу при побудові вирішуючих правил класифікації показали, що його використання дозволяє скоротити довжину вирішуючого правила класифікації на 36?% і підвищити ефективність розпізнавання на 11% (середня помилка розпізнавання складає 0,83%).

Для систем розпізнавання відкритого типа при додаванні нових об'єктів в навчальну вибірку необхідність у перестроюванні вирішуючого правила класифікації склала 14%, що на 28% менше результатів, що одержуються при використанні класичних методів.

При оцінці ефективності комплексного методу на відомих тестових прикладах (об'єкти одного класу розташовані усередині області об'єктів іншого класу) було одержано, що в середньому комплексний метод дозволяє вірно класифікувати 96,88% об'єктів, що на 3,5% більше результатів, одержуваних відомими на сьогодні методами побудови вирішуючих правил класифікації (табл. 1).

Таблиця 1. - Порівняння кількості правильних класифікацій (%) вирішуючими правилами для тестового прикладу

№ класу	Метод потенційних функцій	Метод k-найближчих сусідів	Нейронні мережі	Генетичний алгоритм	Комплексний метод
			2:10:10:2 нейронів	2:20:20:2 нейронів
1	100,0	96,85	100,0	100,0	94,44	97,93
2	18,19	59,09	0,0	0,0	87,5	89,92
Середнє значення	85,65	90,23	82,47	82,47	93,22	96,88

У четвертому розділі розглянуте застосування запропонованого комплексного методу побудови вирішуючих правил класифікації для вирішення однієї з найбільш складних задач комп'ютерної лінгвістики - задачі побудови спам-фільтрів в системах управління електронною кореспонденцією. Приведений опис розробленої системи обробки електронної кореспонденції і особливості застосування комплексного методу при побудові спам-фільтрів цієї системи.

Для оцінки ефективності використання спам-фільтрів, побудованих з використанням запропонованого комплексного методу, виконане порівняння ефективності їх роботи з результатами класифікації електронної кореспонденції спам-фільтром BayesIt! поштової програми The Bat! Аналіз отриманих результатів показав, що використання комплексного методу побудови вирішуючих правил класифікації дозволяє збільшити ефективність фільтрації спаму в середньому на 24% при природному навчанні (при відсутності початкової навчальної вибірки) і на 43% при форсованому навчанні ( при наявності початкової навчальної вибірки розміром 200 електронних листівок).

У додатку приведені акти про використання результатів дисертаційного дослідження.

ВИСНОВКИ

У дисертаційній роботі запропоновано нове рішення актуальної задачі розробки ефективних методів побудови вирішуючих правил імовірнісних систем автоматичного розпізнавання відкритого типу, що навчаються. Запропоноване рішення полягає в застосуванні комплексного підходу, що включає як обробку вхідних даних, так і побудову вирішуючих правил з використанням генетичних алгоритмів. Отримані результати мають важливе наукове і прикладне значення для створення ефективних систем автоматичного розпізнавання, що навчаються, особливо систем відкритого типу. Проведені дослідження дозволили отримати наступні результати.

1. В результаті аналізу сучасного стану завдання побудови систем автоматичного розпізнавання, методів побудови вирішуючих правил у системах розпізнавання, що навчаються, і методів скорочення навчальних вибірок було показано, що існуючі методи не дозволяють будувати ефективні за якістю і часом розпізнавання системи для прикладних завдань, що характеризуються значним об'ємом початкових даних, і можливістю їх поповнення в процесі роботи.

2. На підставі аналізу можливих варіантів розташування об'єктів навчальної вибірки у просторі ознак був запропонований спосіб визначення відособленості класів шляхом побудови кардинальної гіперплощини, що дозволяє одержувати вирішуюче правило для відособлених класів мінімальної довжини.

3. Вперше був запропонований і обґрунтований метод скорочення початкової навчальної вибірки шляхом побудови вибірки мета-об'єктів для двокласових і багатокласових систем розпізнавання, що дозволяє по безлічі розташованих поруч об'єктів деякого класу будувати мета-об'єкти, що описуються окрім значень ознак розпізнавання масою. Виконаний аналіз способів визначення початкової і конкуруючої точок побудови мета-об'єктів, оцінена достовірність розробленого методу по статистичних характеристиках початкової і одержаної навчальних вибірок. Для систем розпізнавання відкритого типа запропонований новий метод додавання нових об'єктів в навчальну мета-вибірку, запропонований новий метод коректного додавання даних у вибірку мета-об'єктів, що є необхідною умовою створення систем розпізнавання відкритого типу, що навчаються.

4. Одержав подальший розвиток метод потенційних функцій шляхом розповсюдження його на зважені навчальні мета-вибірки, що дозволило використовувати при побудові вирішуючих правил не тільки значення ознак розпізнаваних об'єктів, але знання про розташування об'єктів навчальної вибірки у просторі ознак.

5. Розроблений генетичний алгоритм побудови вирішуючого правила по мета-вибірці, у якому вперше правило представлене у вигляді псевдобулевої функції, запропонований спосіб імовірнісного формування початкової популяції хромосом, що враховує вагу об'єктів навчальної вибірки, запропонований метод обчислення подвійної фітнес-функції, визначений і обґрунтований набір генетичних операторів, серед яких виділяються знижуюча та підвищуюча мутації, і оператор циклічного зрушення.

5. Запропонований новий метод побудови вирішуючих правил імовірнісних систем автоматичного розпізнавання, що навчаються, який комплексно включає спосіб визначення відособленості класів, метод формування зваженої навчальної вибірки мета-об'єктів, генетичний алгоритм побудови вирішуючого правила, що дозволив підвищити якість розпізнавання, знизити часові витрати на побудову вирішуючого правила і виконання класифікації, скоротити об'єм даних, що зберігаються.

6. У експериментах на тестових даних запропонований комплексний метод показав збільшення здатності розпізнавання одержуваними вирішуючими правилами, у порівнянні з вирішуючими правилами, побудованими класичними методами, в середньому на 11% і скорочення часу класифікації розпізнаваних об'єктів на 36%. У експериментах на відомих тестових прикладах комплексний метод дозволив побудувати вирішуючі правила, що забезпечують в середньому 96,88% правильних класифікацій, що на 3,5% більше результатів, одержуваних найбільш ефективними на сьогодні методами побудови вирішуючих правил класифікації, зокрема, методами на основі генетичних алгоритмів.

7. Застосування розробленого комплексного методу для вирішення завдання побудови спам-фільтрів при фільтрації вхідної електронної кореспонденції дозволило підвищити точність класифікації листівок у середньому на 37%.

8. Результати, одержані в дисертаційній роботі, використані у науково-дослідних роботах відділу розпізнавання мовних образів Донецького інституту проблем штучного інтелекту МОН і НАН України, у розробках ТОВ «Бі-Тек», а також в учбовому процесі кафедри програмного забезпечення інтелектуальних систем Державного університету інформатики і штучного інтелекту.

ПУБЛІКАЦІЇ ЗА ТЕМОЮ ДИСЕРТАЦІЇ

1. Е.В. Волченко Модифицированный метод потенциальных функций // Бионика интеллекта - 2006. - №1(64). - с. 86-92.

2. Е.В.Волченко Генетический алгоритм биссекции графов // Искусственный интеллект. - 2007. - №1. - с. 233-237.

3. Е.В.Волченко Анализ эффективности выбора условий формирования обучающей выборки мета-объектов. // Вестник Хмельницкого национального университета. - 2007. - №2, Том 1. Технические науки. - с. 85-89.

4. Е.В.Волченко Метод формирования обучающей выборки мета-объектов для многоклассовых систем распознавания // Искусственный интеллект. - 2007. - №4. - с. 284-290.

5. Е.В.Волченко Генетический алгоритм построения потенциальной функции // Зб. наук. пр. ДонНТУ. Серія: Обчислювальна техніка та автоматизація, випуск 12 (118). - Донецьк: ДонНТУ. - 2007. - с. 133-142.

6. Е.В.Волченко Анализ эффективности выбора условий формирования обучающей выборки мета-объектов // Реферативний збірник наукових праць за результатами міжнародної науково-практичної конференції „Комп'ютерні системи в автоматизації виробничих процесів”. - Хмельницький, 2007. - с. 21.

7. Е.В.Волченко Генетический анализ биссекции графов // Тезисы докладов Международной научной конференции «Компьютерные науки и информационные технологии». - Саратов, 2007. - с. 22-24.

8. Е.В.Волченко Метод формирования обучающей выборки мета-объектов для многоклассовых систем распознавания // Искусственный интеллект. Интеллектуальные системы: Материалы восьмой международной научно-технической конференции. - Донецк-Таганрог-Минск, 2007. - с. 225-227.

9. Е.В.Волченко Метод построения решающего правила вероятностной обучающейся системы распознавания средствами генетических алгоритмов // Материалы второй международной научной конференции «Современные информационные системы. Проблемы и тенденции развития». - Харьков-Туапсе, 2007. - с. 467-468.

10. Е.В.Волченко Многошаговое построение решающих правил обучающихся систем распознавания // Материали першої міжнародної науково-технічної конференції «Інтелектуальні системи в промисловості та освіті - 2007». - Суми, 2007. - с. 16-18.

АНОТАЦІЯ

Волченко О.В. Комплексний метод побудови вирішуючих правил імовірнісних систем автоматичного розпізнавання, що навчаються. - Рукопис.

Дисертація на здобуття наукового ступеня кандидата технічних наук за спеціальністю 05.13.23 - Системи та засоби штучного інтелекту. - Державний університет інформатики та штучного інтелекту, Донецьк, 2008.

Дисертація присвячена рішенню актуальної задачі розробки ефективних методів побудови вирішуючих правил імовірнісних систем автоматичного розпізнавання відкритого типу, що навчаються. Запропонований і обґрунтований новий метод побудови скороченої зваженої навчальної вибірки мета-об'єктів, вага яких розраховується до побудови вирішуючих правил класифікації, що дозволило істотно скоротити навчальну вибірку. Запропонований новий метод коректного додавання даних у вибірку мета-об'єктів, необхідний при побудові систем розпізнавання відкритого типу, що навчаються. Запропонований метод побудови потенційних функцій по зважених навчальних мета-вибірках, що дозволило використовувати при побудові вирішуючих правил значення ознак розпізнаваних об'єктів і знання про розташування об'єктів навчальної вибірки у просторі ознак. Розроблений генетичний алгоритм побудови вирішуючих правил класифікації, в якому правило представлене у вигляді псевдобулевої функції, запропонований спосіб імовірнісного формування початкової популяції хромосом, що враховує вагу об'єктів навчальної вибірки, запропонований метод обчислення подвійної фітнес-функції, визначений і теоретично обґрунтований набір генетичних операторів. Запропонований новий метод побудови вирішуючих правил імовірнісних систем автоматичного розпізнавання відкритого типу, що навчаються, що комплексно включає спосіб визначення відособленості класів, метод формування зваженої навчальної вибірки мета-об'єктів, генетичний алгоритм побудови вирішуючого правила, що дозволив підвищити якість розпізнавання, знизити часові витрати на побудову вирішуючого правила і виконання класифікації, скоротити об'єм даних, що зберігаються.

Ключові слова: системи автоматичного розпізнавання, що навчаються, вирішуюче правило, мета-об'єкт, генетичний алгоритм, фітнес-функція, кросинговер, мутація, циклічне зрушення, електронна кореспонденція, спам-фільтр.

АННОТАЦИЯ

Волченко Е.В. Комплексный метод построения решающих правил вероятностных обучающихся систем автоматического распознавания. - Рукопись.

Диссертация на соискание ученой степени кандидата технических наук по специальности 05.13.23 - Системы и средства искусственного интеллекта.- Государственный университет информатики и искусственного интеллекта, Донецк, 2008.

Диссертация посвящена решению актуальной задачи разработки эффективных методов построения решающих правил вероятностных обучающихся систем автоматического распознавания открытого типа. Предложенное решение заключается в применении комплексного подхода, включающего как обработку входных данных, так построение решающих правил с использованием генетических алгоритмов.

Впервые предложен и обоснован метод построения сокращенной взвешенной обучающей выборки мета-объектов, вес которых, в отличие от известных ранее методов определения веса объектов обучающей выборки, рассчитывается до построения решающих правил классификации, что позволило существенно сократить обучающую выборку. Предложен новый метод корректного добавления данных в выборку мета-объектов, которое является необходимым условием создания обучающихся систем автоматического распознавания открытого типа.

Получил дальнейшее развитие метод потенциальных функций путем распространения его на взвешенные обучающие мета-выборки, что позволило использовать при построении решающих правил не только значения признаков распознаваемых объектов, но знания о расположении объектов обучающей выборки в признаковом пространстве.

Разработан генетический алгоритм построения решающих правил классификации, в котором впервые правило представлено в виде псевдобулевой функции, предложен способ вероятностного формирования начальной популяции хромосом, учитывающий вес объектов обучающей выборки, предложен метод вычисления двойной фитнесс-функции, определен и обоснован набор генетических операторов.

Предложен новый метод построения решающих правил вероятностных обучающихся систем автоматического распознавания открытого типа, комплексно включающий в себя способ определения обособленности классов, метод формирования взвешенной обучающей выборки мета-объектов, генетический алгоритм построения решающего правила, позволивший повысить качество распознавания, понизить временные затраты на построение решающего правила и выполнение классификации, сократить объем хранимых данных.

В экспериментах на тестовых данных предложенный комплексный метод показал увеличение эффективности получаемых решающих правил по сравнению решающими правилами, построенными классическими методами, в среднем на 11% и сокращение времени классификации распознаваемых объектов на 36%. В экспериментах на известных тестовых примерах комплексный метод позволил построить решающие правила, обеспечивающие в среднем 96,88% правильных классификаций, что на 3,5% больше результатов, получаемых наиболее эффективными на сегодняшний день методами построения решающих правил классификации, в том числе, методами на основе генетических алгоритмов. Применение разработанного комплексного метода для решения задачи построения спам-фильтров при фильтрации входящей электронной корреспонденции позволило повысить точность классификации текстов в среднем на 37%.

Ключевые слова: обучающиеся системы автоматического распознавания, решающее правило, мета-объект, генетический алгоритм, фитнесс-функция, кроссинговер, мутация, циклический сдвиг, электронная корреспонденция, спам-фильтр.

ABSTRACT

Volchenko E.V. Complex method of construction of solving rules of likelihood trained systems of automatic recognition. - Manuscript.

The thesis for a Candidate's degree in Technical Sciences on specialty 05.13.23- Systems and tools of artificial intelligence. - State university of informatics and artificial intelligence, Donetsk, 2008.

The thesis is devoted to the solution of an actual problem of development of effective methods of construction for solving rules of likelihood trained systems of automatic recognition of the open type. A method of construction of the reduced weighed training sample of meta-objects which weight pays off before construction of solving rules of classification that has allowed to reduce training sample essentially is offered and proved. The new method of correct addition of the meta-objects given in sample, necessary is offered at construction of trained systems of recognition of the open type. The method of potential functions on the weighed training meta-samples that has allowed to use at construction of solving rules of value of attributes of distinguished objects and knowledge of an arrangement of objects of training sample in attribute space offered. The genetic algorithm of construction of solving rules of classification in which corrected is developed is presented in the form of pseudo-boolean functions, the way of likelihood formation of an initial population of the chromosomes, the considering weight of objects of training sample is offered, the method of calculation double fitness-function is offered, the set of genetic operators is certain and theoretically proved. The new method of construction of solving rules of likelihood trained systems of automatic recognition of the open type, in a complex including way of definition of isolation of classes, method of formation of the weighed training sample of meta-objects, genetic algorithm of construction of the solving rule, allowed to raise quality of recognition is offered, to lower time expenses for construction of a solving rule and performance of classification, to reduce volume data.

Key words: Trained systems of the automatic recognition, solving rule, meta-object, genetic algorithm, fitness-function, a crossover, a mutation, cyclic shift, the electronic correspondence, a spam-filter.

Размещено на Allbest.ru

...