• Гідрологія і Гідрометрія
• Господарське право
• Економіка будівництва
• Економіка природокористування
• Економічна теорія
• Земельне право
• Історія України
• Кримінально виконавче право
• Медична радіологія
• Методи аналізу
• Міжнародне приватне право
• Міжнародний маркетинг
• Основи екології
• Предмет Політологія
• Соціальне страхування
• Технічні засоби організації дорожнього руху
• Товарознавство продовольчих товарів

I. Генетичні алгоритми

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

ТЕРНОПІЛЬСЬКИЙ НАЦІОНАЛЬНИЙ ЕКОНОМІЧНИЙ УНІВЕРСИТЕТ

ФАКУЛЬТЕТ КОМП’ЮТЕРНИХ ІНФОРМАЦІЙНИХ ТЕХНОЛОГІЙ

Кафедра комп’ютерних наук

МЕТОДИЧНІ ВКАЗІВКИ

ДО ВИКОНАННЯ ЛАБОРАТОРНИХ РОБІТ

З дисципліни

"ІНТЕЛЕКТУАЛЬНИЙ АНАЛІЗ ДАНИХ”

для студентів спеціальності 6.080400

„Програмне забезпечення автоматизованих систем”

Тернопіль-2010

Л.І.Гончар, В.І. Манжула. // Методичні вказівки до виконання лабораторних робіт з дисципліни ”Інтелектуальний аналіз даних” для студентів напрямку „Комп’ютерні науки”.-Тернопіль, 2010.

Укладачі: Гончар Людмила Іванівна, доцент кафедри КН, ТНЕУ

Манжула Володимир Іванович, ст.. викладач кафедри КН, ТНЕУ

Відповідальний за випуск: Дивак Микола Петрович,д.т.н., професор,

завідувач кафедри КН, ТНЕУ

Шпак Володимир Богданович,

інженер кафедри КН, ТНЕУ

Рецензенти:завідувач кафедри Безпеки інформаційних технологій

ТНЕУ, д.т.н., професор Карпінський М.П.

доцент кафедри Біотехнічних систем Тернопільського

національного технічного університету імені І.Пулюя,

к.т.н., доцент Шадріна Г.М.

Затверджено на засіданні кафедри комп’ютерних наук ТНЕУ,

Протокол № від лютого 2010 р.

ЗМІСТ

ВСТУП...........................................................................................................................................4

I. Генетичні алгоритми......................................................................................................5

1.1.Генетичні успадкування — концептуа­льні засади генетичних алгоритмів.......................5

1.2. Загальна схема генетичних алгоритмів.................................................................................6

1.3. Доступне програмне забезпечення генетичних алгоритмів ...............................................9

Лабораторна робота № 1……………………………………………………………………10

II. Доступне програмне забезпечення дейтамайнінгу POLYANALYST……………..29

Лабораторна робота № 2………………………………………………………………………29

ЛІТЕРАТУРА..............................................................................................................................44

.

ВСТУП

Засоби сучасної інформаційної технології в останній час уможливили накопичення і зберігання великих обсягів даних про бізнесові процеси. Ці дані можуть знаходитися в корпоративних базах або сховищах даних. Вони містять важливі закономірності і зв’язки між системними характеристиками, які можуть бути використані для прийняття обгрунтованих управлінських рішень. Наразі виникла проблема розробки методів відкриття таких закономірностей, про існування яких користувачі можуть і не знати. Проте традиційний аналіз даних передбачує введення даних в стандартні або настроєні користувачем моделі, тобто в будь-якому випадку допускається, що зв'язки між різними показниками добре відомі і можуть бути виражені математично. Однак, в багатьох випадках зв'язки не можуть бути апріорі відомі. У таких ситуаціях моделювання стає неможливим і тут можна застосовувати дейтамайнінг (Data Mining) – інтелектуальний аналіз даних (ІАД). Тому, особливо важливим аспектом підготовки спеціалістів напрямку "Комп'ютерні науки” є успішне засвоєння ними дисципліни "Інтелектуальний аналіз даних”.

У результаті вивчення дисципліни “Інтелектуальний аналіз даних” студент повинен :

Знати - сутність та призначення Data Mining; характеристики процесів та активностей дейтамайнінгу;дерево методів дейтамайнінгу; доступне програмне забезпечення ІАД; призначення та основні характеристики генетичних алгоритмів і програмних агентів, ; вивчити основні методи генетичного пошуку.

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

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

I. Генетичні алгоритми

1.1. Генетичні успадкування —концептуа­льні засади генетичних алгоритмів

У загальному значенні генетичні алгоритми (Genetic Algorithms) — це тип алгоритмів, інспірованих механізмами еволюції живої природи, які застосовуються, головно, до задач глобальної оптимізації (зокрема, задач комбінаторної оптимізації) і деякою мірою для дейтамайнінгу, зокрема, для комбіну­вання шаблонів з правил індукції, які були відкриті до цього, навчання нейромереж, пошуку зразків у даних, відкриття шаб­лонів у тексті тощо. Генетичні алгоритми належать нині до стан­дартного інструментарію методів дейтамайнінгу.

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

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

Майже в кожній клітині будь-якої тварини є ряд хромосом, що несуть інформацію про цю тварину. Основна частина хромосоми — нитка ДНК (молекула дезоксирибоза Нуклеїнової Кислоти), яка складається з чотирьох видів спеціальних з'єднань (молекул) — нуклеотидів, що чергуються в певній послідовності. Нуклеотиди позначають буквами А, Т, С і G, і саме порядок їх розміщеня є кодом усіх генетичних властивостей даного організму. Кажучи точніше, ДНК визначає, які хімічні реакції будуть відбуватися в даній клітині, як вона буде розвиватися і які функції виконувати­ме. Отже, генетичний код окремого індивідуума — це просто дуже довгий рядок комбінацій із чотирьох букв А, Т, С і G, а сам ген — це відрізок ланцюга ДНК, що відповідає за певну власти­вість особи, наприклад за колір очей, тип волосся, колір шкіри і т. д. Різні значення генів називають аллелями. Вся сукупність гене­тичних ознак людини кодується за допомогою приблизно 60 тис. генів, які разом містять більше ніж 90 млн нуклеотидів.

У мейозі, зокрема, відбувається наступне: парні хромосоми со­матичної клітини зближуються впритул, потім їх нитки ДНК розри­ваються в кількох випадкових місцях і хромосоми обмінюються своїми ідентичними ділянками. Цей процес забезпечує появу нових варіантів хромосом І називається перехрещуванням хромосом або кросинговером (від анг. crossing-over). Кожна з хромосом, що знову з'явилася, виявиться потім усередині однієї зі статевих клітин, і її генетична інформація може реалізуватися в нащадках даної особи.

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

Важливе місце в еволюційній теорії відводиться поняттю по­пуляції як елементарній еволюційній одиниці. Популяція — це сукупність особин певного виду організмів, які здатні до вільного схрещування, населяють певну територію і деякою мірою ізольо­вані від сусідніх популяцій. У рамках кожної популяції відбува­ється процес розмноження — репродукції (Reproduction), що являє собою комбінацію послідовностей (strings, хромосом) у опуляци для створення нової послідовності (нащадка). За реродукціі нащадок бере частини позицій генів від обох батьків, матиме частину ознак кожного із них. На рис. 9.13а) показана спрощена схема процесу репродукції, де ознаки батьків виражені хромосомою, котра складається з шести генів, що мають дві аллелі, позначені на схемі нулями і одиницями. Нащадок отримав чотири гени від другого батька (перша, друга, третя і шоста по­зиція) і два від першого (четверта і п'ята позиції).

У генетичних алгоритмах важливе значення мають: форму­вання початкового ряду елементів (популяції), операції кросинговера, що в теорії генетичних алгоритмів частіше називають кросовером (Cross-over), і мутації (Mutation).

Кросовер -— це комбінування (змішування) хромосом шляхом замін значень генів і утворення нових хромосом на їх місцях. На рис. 1. б) наведена спрощена схема кросовера, де показано, як шляхом заміни ідентичних ділянок двох батьків отримані два нащадки з новими ознаками.

Мутація — спонтанне перетворення (видозміна) символів (характерних особливостей) у послідовності (хромосомі). На рис. 1 в) показано, як у результаті мутації п'ятого гена (зна­чення 0 замінено 1) отримана нова хромосома.

Рисунок 1. Схема генеративних процесів:

а) репродукції осіб популяції; б) кросовера осіб популяції; в) мутації хромосоми

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

Переглядів: 2109