Дорошенко Анастасія Володимирівна

УДК 004.048:004.896

МЕТОДИ ТА ІНФОРМАЦІЙНІ ТЕХНОЛОГІЇ КЛАСИФІКАЦІЇ ДЛЯ ЗАВДАНЬ ВИДОБУВАННЯ ДАНИХ

05.13.06 – інформаційні технології

Автореферат

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

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

Львів – 2008

Дисертацією є рукопис.

Робота виконана у Національному університеті „Львівська політехніка” Міністерства освіти і науки України.

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

доктор технічних наук, професор Ткаченко Роман Олексійович, Національний університет „Львівська політехніка”, професор кафедри автоматизованих систем управління.

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

доктор технічних наук, професор Пасічник Володимир Володимирович, Національний університет „Львівська політехніка”, директор інституту комп’ютерних наук та інформаційних технологій, завідувач кафедри інформаційних систем та мереж.

кандидат фізико-математичних наук, доцент Гече Федір Елемірович, Ужгородський національний університет, доцент кафедри кібернетики та прикладної математики.

Захист відбудеться “  ” березня 2008 р. о 16.00 годині на засіданні спеціалізованої вченої ради Д35.052.14 при Національному університеті „Львівська політехніка” за адресою: 79013, м. Львів, вул. С.Бандери, 12.

З дисертацією можна ознайомитись у бібліотеці Національного університету „Львівська політехніка” за адресою: 79013, м. Львів, вул. Професорська,1.

Автореферат розіслано “ 19 ” лютого 2008 р.

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

cпеціалізованої вченої ради

к.т.н., доцент ____________________________ А.Є. Батюк

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

Актуальність теми. Стрімкий розвиток технічних засобів та інформаційних технологій відбору та зберігання даних, збільшення розмірів сховищ даних ставлять підвищені вимоги до обробки та аналізу інформації. Одержання нової корисної інформації вимагає постійного вдосконалення: підвищення швидкодії, здатності опрацьовувати великі обсяги даних одночасно, підвищення якості аналізу. Сукупність таких методів та засобів обробки та аналізу даних відома під назвою "видобування даних" (Data Mining). Основний внесок в розвиток видобування даних внесли його засновник Г. Пятецький-Шапіро, В. Дюк, А. Самойленко, Д. Хенд, Дж. Бігус, Т. Лін, Дж. Хен.

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

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

Відомі методи і засоби класифікації, зокрема статистичні моделі, нейронні мережі, машини опорних векторів, розвиток яких пов’язаний із іменами Ф. Розенблатта, Т. Кохонена, С. Пайперта, Р. Хемінга, Д. Хопфілда та українських вчених В. Глушкова, О. Івахненка, М. Амосова, А. Кухтенка, В. Васильєва, В. Вапніка, З. Рабіновича, В. Грицика, Є. Бодянського, М. Згуровського, О. Різника, Ю. Зайченка, зазвичай забезпечують розв’язання задач з достатньою для практики точністю класифікації, однак не враховують всі перелічені особливості задач видобування даних, а отже, розв’язують їх із незадовільною швидкістю, вимагають вдосконалення та адаптації.

Модель геометричних перетворень (МГП), вперше запропонована в працях Ткаченка Р.О., є основою побудови нейроподібних структур аналізу і опрацювання даних великих обсягів для майже вироджених задач з поганою зумовленістю, застосовувалась переважно в якості ефективного засобу передбачення і прогнозування часових послідовностей. Отже, дослідження структур моделі геометричних перетворень з метою адаптації їх для розв’язання задач класифікації у галузі інтелектуального аналізу даних є актуальними і необхідними.

Зв'язок теми дисертації з науковими програмами, планами, темами. Наукові та практичні результати дисертаційної роботи застосовувались для виконання наукових досліджень кафедри “Автоматизовані системи управління” Національного університету “Львівська політехніка” в програмах ДБ/Візуалізація “Нейромережеві ситуаційні карти особливостей для візуалізації режимів в електроенергетичних системах енергопостачальних компаній” (№ державної реєстрації 0105U000601б), ДБ/СДО „Нейромережні технології класифікації лексико-семантичної інформації для систем дистанційної освіти” (№ державної реєстрації 0107U001115).

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

Для досягнення поставленої мети у роботі розв’язані такі задачі:

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

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

3. Розроблено метод та інформаційну технологію прийняття рішень про належність до класу на основі правила „переможець забирає все” (WTA) з використанням матриці штрафів та заохочень;

4. Розроблено кусковий метод побудови розділяючих поверхонь на основі формування дерева поділу на класи і матриці штрафів-заохочень;

5. Запропоновано, обґрунтовано та реалізовано процедуру формування рівномірної вибірки для вузлів дерева поділу на класи;

6. Вдосконалено метод навчання нейроподібних структур моделі геометричних перетворень доповненням його процедурою оптимізації імітацією відпалу металу;

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

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

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

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

Наукова новизна отриманих результатів:

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

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

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

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

Практичне значення одержаних результатів:

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

Застосування розроблених методів налагодження та оптимізації нейроподібних структур і програмних продуктів на їх основі в задачах електронної комерції забезпечило підвищення точності класифікації в середньому на 2–7 %, а в окремих випадках на 10–20 %, скоротило час отримання розв’язків.

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

Особистий внесок здобувача. Усі теоретичні та експериментальні дослідження, розроблення методів алгоритмічного та програмного забезпечення виконані автором самостійно. У працях, опублікованих у співавторстві, автору належать: розроблення та реалізація глобального та локального підходів до розв’язання задачі класифікації [4], аналіз існуючих методів класифікації, розроблення та реалізація кластерного методу розв’язання задач класифікації для видобування даних [3,4], розроблення методу підвищення точності класифікації на основі застосування оптимізаційного методу відпалу металу [5,6].

Апробація роботи. Основні наукові і практичні результати роботи доповідалися та обговорювалися на: XІХ відкритій науково-технічній конференції молодих науковців і спеціалістів Фізико-механічного інституту ім. Г.В. Карпенка НАН України КМН-2005 (м. Львів, 2005); Міжнародних наукових конференціях „Інтелектуальні системи прийняття рішень та прикладні аспекти інформаційних технологій” (м. Євпаторія, 2005–2007); Першій міжнародній конференції молодих науковців “Комп’ютерні науки та інженерія – 2006” (м. Львів, 2006); Second International conference on computer science and information technologies (м. Львів, 2007).

Публікації. Результати дисертаційної роботи опубліковані у 12 наукових працях, серед яких 6 статей у фахових виданнях (2 з них одноосібні) та 6 – у матеріалах та тезах конференцій.

Структура та обсяг роботи. Дисертація складається з вступу, чотирьох розділів, висновків, списку основної використаної літератури та додатків. Робота містить 121 сторінку основного тексту, список літератури з 110 найменувань, 30 сторінок додатків. Загальний обсяг дисертації – 161 сторінка.

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

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

У першому розділі здійснено аналітичний огляд методів та алгоритмів класифікації для задач видобування даних, визначено основні особливості задач видобування даних, які визначають вимоги до методів класифікації, а саме: велика інформаційна ємність завдань, суперечливість та неповнота даних, виродженість задач, неоднорідність представлення даних, нерівномірність даних в просторі, різна вага помилок. Виконано критичний аналіз існуючих методів класифікації, виходячи із можливості їх застосування для розв’язання завдань видобування даних, визначено найефективніші з них, такі як: машини опорних векторів, нейронні мережі (багатошаровий перцептрон та РБФ-мережі) та нейроподібні структури на основі моделі геометричних перетворень. Показано важливість розроблення методів класифікації для завдань видобування даних на основі моделі геометричних перетворень як найефективнішої, для якої, однак, немає розроблених ефективних методів класифікації.

У другому розділі викладено основні засади та результати досліджень розроблених автором методів класифікації на основі МГП, які враховують особливості завдань видобування даних.

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

Розроблено локальний та глобальний підходи до класифікації для задач видобування даних на основі лінійного варіанта МГП.

Глобальний підхід до класифікації реалізується шляхом побудови за допомогою МГП неперервної гіперповерхні відгуку, сформованої за результатами навчання на тренувальних даних. Структура такої МГП (рис.1.) складається з шару вхідних нейронів, на які подаються первинні ознаки об’єктів класифікації , прихованого шару із латеральними зв’язками між нейронами, сигналів на виходах прихованого шару та вихідних сигналів, які задають належність до визначених класів – . Послідовність формування вихідних сигналів такої мережі описується формулами , де , – вектор-рядок матриці тренувальних даних з найбільшою віддаллю (за Евклідом) від початку координат, – апроксимуюча функція.

Локальний підхід до класифікації реалізується на основі застосування гібридної структури (рис.2), де попередньо перетворюються первинні входи-ознаки на входи РБФ за співвідношенням, де Dj – величина евклідової віддалі між поточним вектором-точкою та j-м базовим; – параметр крутизни функції, Rj – величина сигналу, що відповідає j-му РБФ входу.

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

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

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

Таблиця 1

Структура бази даних |

...

...

... | ... | ... | ... | ...

...

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

Нехай дані містяться у великому сховищі правильно класифікованих прикладів типу вхід–вихід , де xi – вхідний вектор, а y – бажаний вихідний сигнал, що відповідає вхідному вектору. Отже, існує база даних, структуру якої наведено в табл. 1, де – дані, що описують об’єкт, – значення, що вказує, до якого класу належить цей об’єкт, – кількість входів, – кількість векторів у базі даних.

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

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

Таблиця 2

Матриця штрафів та заохочень |

Вектор розпізнано

як клас 1 | Вектор розпізнано

як клас 2 | Вектор розпізнано

як клас K

Вектор належить до класу 1 | ...

Вектор належить до класу 2 | ...

… | ... | ... | ... | ...

Вектор належить до класу K | ...

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

Обчислюється щільність представлення об’єктів класу за формулою:

,

де – щільність представлення об’єктів i-го класу (); – кількість екземплярів i-го класу (); – загальна кількість векторів у базі даних.

Формується нова матриця штрафів із врахуванням обчислених щільностей (табл. 3.).

Таблиця 3

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

Вектор розпізнано

як клас 1 | Вектор розпізнано

як клас 2 | Вектор розпізнано

як клас K

Вектор належить до класу 1 | ...

Вектор належить до класу 2 | ...

… | ... | ... | ... | ...

Вектор належить до класу K | ...

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

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

- густина представлення точок різних класів в просторі реалізацій є суттєво неоднорідною;

- розділення класів гіперплощиною не враховує суттєвої нелінійності розв’язуваних задач.

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

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

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

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

1. Початково кількість штрафних балів мінімізується за методом штрафів та заохочень.

2. Вибірка із спрогнозованими виходами, заміненими на ідентифікатори класів (”клас 1”, ”клас ”) – як тренувальна, так і тестова – ділиться на 2 кластери: вектори, розпізнані нейромережею як ”клас1”, та вектори, розпізнані як “клас ”.

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

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

5. Якщо для певного кластера оптимальним є значення k11, k12, k21, k22, при яких нейромережа передбачає для тренувальної вибірки лише один клас (”клас 1” чи “клас 2”) –процедура кластеризації для цього кластера припиняється, інакше – продовжується виконання кластеризації (рис.2.16).

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

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

У третьому розділі запропоновано доповнити розроблені та описані у розділі 2 методи класифікації прикінцевими процедурами оптимізації, зокрема, випадковою корекцією елементів декомпозиції (метод Монте-Карло) та методом імітації відпалу металу.

Розглянуто процедуру виділення елементів декомпозиції даних. Нехай вектор даних х є реалізацією випадкового вектора Х. Оскільки існує m можливих значень одиничного вектора q , то необхідно розглянути m можливих проекцій вектора даних х. За формулою , j = 1,2,…,m, де – проекції вектора х на основні напрямні, представлені одиничними векторами q j. Ці проекції називаються головними компонентами, а їх кількість відповідає розмірності вектора даних х.

Виділення головних компонент (ГК) здійснюється також на виходах нейронів прихованого шару в процесі навчання нейроподібної структури МГП.

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

Після виділення ГК формується та навчається додаткова нейроподібна структура МГП (рис. 4), на входи якої подаються вектори ГК, а виходами є значення відповідних виходів початкових навчальних даних.

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

Рис.4. Нейроподібна структура для отримання елементів декомпозиції

У режимі застосування на входи навченої нейроподібної структури подаються вектори:

...

Визначаються

...,

Отримуємо елементи декомпозиції

...,

Початково маємо

або ,

де елементи декомпозиції, а =1, i = 1,2,…, m .

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

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

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

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

(1)

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

Розрахунок відсотків неправильно класифікованих представників класів. Якщо NC1 – кількість представників класу 1 у навчальній вибірці, NC2 – кількість представників класу 2 у навчальній вибірці,NWC1 – кількість неправильно класифікованих представників класу 1, NWC2 – кількість неправильно класифікованих представників класу 2.

Тоді відсоток неправильно класифікованих представників класів обчислюється на основі співвідношень

Розрахунок кількості штрафних балів. Для того, щоб обчислити кількість штрафних балів, необхідно визначити штрафи, які нараховують за помилкове розпізнавання. Отже, якщо Ш1 – штраф, що нараховується, якщо елемент класу 1 розпізнано як елемент класу 2, Ш2 – штраф, що нараховується, якщо елемент класу 2 розпізнано як елемент класу 1.

Тоді значення штрафної функції – сумарної кількості отриманих штрафних балів (ШБ) дорівнює:

Метод оптимізації для задач класифікації

1. Початкові значення =1.

2. Обчислюються значення похибки, за якою проводиться оптимізація (ШФ,  чи ).

3. За допомогою давача випадкових чисел із рівномірним розподілом обираються з діапазону (-D, D) значення D.

4. Обчислюються нові значення = +D.

5. Обчислюються значення виходів при нових .

6. Перетворюється отримане значення в позначення класу, до якого належить даний елемент.

7. Обчислюється нове значення похибки, за якою проводиться оптимізація (ШФ, чи ).

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

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

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

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

На рис.5 зображено структурну схему розробленої нейроподібної структури на основі моделі геометричних перетворень, де первинні ознаки об’єктів класифікації – вхідні дані, елементи декомпозиції, отримані на основі вхідних даних, вагові коефіцієнти, y вихід, що задає належність до визначених класів.

Формування вихідних сигналів такої нейроподібної структури можна описати формулою

.

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

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

2. Доки , повторити L=100 разів такі дії:

- обрати новий розв’язок з околу ;

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

- якщо – прийняти =; інакше, при , прийняти з ймовірністю ; генеруємо випадкове число r з інтервалу (0,1) та порівнюємо його із значенням ; якщо  r, прийняти новий розв’язок ; у протилежному випадку – проігнорувати його.

3. Зменшити температуру з використанням коефіцієнта зменшення k, що обирається з інтервалу (0,1), та повернутися до пункту . Пропонується використовувати значення k=0,9.

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

У четвертому розділі описано результати застосування розроблених методів класифікації для підвищення якості електронної комерції. Подано опис створених інформаційних технологій на основі розроблених методів для класифікації клієнтів інтернет-магазину, для максимізації прибутковості інтернет-аукціону та для виявлення потенційних клієнтів компанії за даними маркетингового дослідження. Розроблені методи були реалізовані у вигляді скриптів, написаних мовою Python і можуть бути інтегровані у програмний пакет funс*net. Наведено результати проведених експериментів, які підтвердили ефективність застосування розроблених методів. Поєднання цих методів дало змогу одночасно опрацьовувати вибірки розміром близько 30000 записів, кожен з яких описується 62 ознаками за час близько 10–30 секунд із точністю 85–93 %. Експериментально підтверджено, що застосування розроблених методів дозволило збільшити точність класифікації на 10–20порівняно із результатами, отриманими на основі застосування відомих пакетів на основі ШНМ.

ВИСНОВКИ

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

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

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

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

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

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

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

7. Розроблені інформаційні технології прийняття рішень для завдань електронної комерції (класифікація клієнтів, виявлення шахраїв, класифікація лотів Інтернет-аукціону eBuy)дозволили підвищити ефективність розв’язання задач видобування даних великих розмірностей (порядку сотні атрибутів), представлених тренувальними вибірками значних обсягів (десятки тисяч векторів) в умовах, коли в заданому просторі реалізації не виконується гіпотеза компактності.

8. Застосування розроблених методів налагодження та оптимізації нейроподібних структур і програмних продуктів на їх основі в задачах електронної комерції забезпечило підвищення точності класифікації в середньому на 2–7 %, а в окремих випадках на 10–20 % (від 85 до 95 % правильно класифікованих даних), скоротило час отримання розв’язків приблизно в 5 разів (з 60–120 до 10–30 секунд), що свідчить про ефективність застосованих методів.

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

1.

2.

3.

4.

5.

6.

7.

8.

9.

10.

11.

12.

АНОТАЦІЯ

Дорошенко А.В. Методи та інформаційні технології класифікації для завдань видобування даних. – Рукопис.

Дисертація на здобуття наукового ступеня кандидата технічних наук за спеціальністю 05.13.06 – Інформаційні технології. – Національний університет ”Львівська політехніка”, Львів, 2008.

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

В дисертаційній роботі з метою врахування такої особливості задач видобування даних, як різна вага помилок під час класифікації, розроблено метод та інформаційну технологію класифікації на основі правила „переможець забирає все” (WTA) з використанням матриці штрафів та заохочень, що надає можливість враховувати неоднакову вагу помилок при розпізнаванні об’єктів різних класів. Розроблено метод кускової побудови розділяючих поверхонь на основі дерева поділу на класи, що забезпечує підвищення точності розпізнавання об’єктів, для яких в заданому просторі реалізацій не виконується гіпотеза компактності. Запропоновано, досліджено і реалізовано метод послідовного вирівнювання тренувальної вибірки по кластерах, що формуються у вузлах дерева, який забезпечує покращання точності розв’язання задач класифікації для вибірок, представлених в просторі реалізацій нерівномірно. Вдосконалено метод навчання нейроподібних структур моделі геометричних перетворень доповненням його процедурою оптимізації методом імітації відпалу металу за параметрами головних компонентів, що дало змогу покращити якість класифікації завдяки використанню інших, окрім середньоквадратичного, критеріїв якості. Розроблено та застосовано програмні скрипти мовою Python, які виконують передобробку даних та реалізують розроблені метод вирівнювання вибірки, метод штрафів і заохочень та кусковий метод побудови розділяючих поверхонь. Створено інформаційні технології на основі розроблених методів, які застосовано для задач електронної комерції. Наведено результати проведених експериментів, які свідчать про ефективність застосованих методів.

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

АННОТАЦИЯ

Дорошенко А.В. Методы и информационные технологии классификации для задач интеллектуального анализа данных. – Рукопись.

Диссертация на соискание ученой степени кандидата технических наук по специальности 05.13.06 – Информационные технологии. – Национальный университет ”Львовская политехника”, Львов, 2008.

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

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

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

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

ANNOTATION

Doroshenko A.V. Methods and information technologies for solution of classification tasks of data mining. – Manuscript.

Thesis for obtaining scientific degree Candidate of Technical Science by specialty 05.13.06 – information technologies. – Lviv National Polytechnic University, Lviv, 2008.

Dissertation is dedicated to the decision of actual scientific and technical task – creation of new methods and information technologies for solution of classification tasks of data mining by geometrical data modeling.

The method of penalty and encouragement is developed in dissertation based on geometrical data modeling and on the rule "winner takes all". This method permits to assure higher accuracy of classification by considering the different weight of classification errors. The method of building separating surface is developed. This method lets increase the dimension and measure of training and testing data due to division data on clusters. The method of sequential smoothing of training data by clusters based on class division tree is developed. This method lets increase the accuracy of classification for data irregularly presented in space of realization. The method of training of geometrical data model is modernized due to usage of optimization by simulating annealing algorithm. The information technologies based on described method for solution tasks of e-commerce are developed.

Keywords: information technologies, classification, data mining, geometrical data modeling.

Підписано до друку 15.02.2008 р.

Формат 60?90 1/16. Папір офсетний.

Друк на різографі. Умовн. друк. арк. 1,5. Обл..-видав. арк. 0,89.

Тираж 100 прим. Зам. 80097.

Поліграфічний центр

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

вул Ф.Колеси, 2, 79000, Львів.