Добавил:
Upload Опубликованный материал нарушает ваши авторские права? Сообщите нам.
Вуз: Предмет: Файл:
CCC / лаби_ССС.doc
Скачиваний:
17
Добавлен:
06.06.2015
Размер:
792.58 Кб
Скачать

МІНІСТЕРСТВО ОСВІТИ І НАУКИ, МОЛОДІ ТА СПОРТУ УКРАЇНИ

Державний вищий навчальний заклад

Національний гірничий університет”

Лабораторний практикум з дисципліни “Самонавчання складних систем”

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

“Системний аналіз і управління”

Дніпропетровськ, 2011

Вступ

Тут має бути якась писня – до півсторінки.

Лабораторна робота №1.

Побудова й використання асоціативних правил.

Завдання.

1. За наведеною у початкових даних таблицею, яка є фрагментом бази даних транзакцій побудувати асоціативні правила, використовуючи алгоритм Apriory. В ході побудови застосовувати наступні параметри: мінімальна підтримка правила 12%, мінімальна достовірність правила 80%.

2. Розрахувати додаткові характеристики асоціативних правил. Зробити висновки щодо значущості кожного з отриманих правил.

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

Початкові данні знаходяться в файлі lab_CCC_vars.xls в робочому каталозі дисципліни на сервері локальної комп’ютерної мережі кафедри (лист “асоціативні правила”).

Методичні вказівки до виконання роботи.

Алгоритм Apriory.

Даний алгоритм був запропонований у 1994 році американськими вченими індійського походження Агравалом та Шрікантом. У його основі лежить поняття “частий набір” (frequent itemset). Асоціативні правила будуються не для усіх можливих сполучень товарів, а лише для тих, які зустрічаються в початковій базі даних достатньо часто.

Частим набором називається непуста множина товарів, підтримка якої не менша за певний, заданий наперед рівень, що має назву “мінімальна підтримка”. Алгоритм Apriory складається з двох послідовних процедур:

  • знаходження усіх частих наборів;

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

В алгоритмі використовується правило анти монотонності: “Якщо певний набір не є частим, то додавання до нього одного або декількох предметів не зробить його частим”.

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

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

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

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

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

Приклад.

Множина транзакцій представлена у таблиці 1.1. використовуючи мінімальний рівень підтримки 25% та мінімальну достовірність 80%, створити базу асоціативних правил поведінки покупців.

Таблиця 1.1. Транзакції в овочевому магазині.

№ транзакції

Предметні набори

1

Капуста, перець, кукурудза

2

Спаржа, кабачки, кукурудза

3

Кукурудза, Помідори, квасоля, кабачки

4

Перець, кукурудза, Помідори, квасоля

5

Квасоля, спаржа, капуста

6

Кабачки, спаржа, квасоля, Помідори

7

Помідори, кукурудза

8

Капуста, Помідори, перець

9

Кабачки, спаржа, квасоля

10

Квасоля, кукурудза

11

Перець, капуста, квасоля, кабачки

12

Спаржа, квасоля, кабачки

13

Кабачки, кукурудза, спаржа, квасоля

14

Кукурудза, перець, помідори, квасоля, капуста

Користуючись вищенаведеним алгоритмом, насамперед перевіряємо, чи всі продукти відповідають умовам “частих наборів”, тобто перевіряємо підтримку наборів першого рівня. Заданий рівень підтримки 25% свідчить, що продукт має зустрічатися в транзакціях не менше 4 разів .

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

Таблиця 1.2. Нормалізований вид множини транзакцій

№ транзакції

Спаржа

Квасоля

Капуста

Кукурудза

Перець

Кабачки

Перець

1

0

0

1

1

1

0

0

2

1

0

0

1

0

1

0

3

0

1

0

1

0

1

1

4

0

1

0

1

1

0

1

5

1

1

0

0

0

0

1

6

1

1

0

0

0

1

1

7

0

0

0

1

0

0

1

8

0

0

1

0

1

0

1

9

1

1

0

0

0

1

0

10

0

1

0

1

0

0

1

11

0

1

1

0

1

1

0

12

1

1

0

0

0

1

1

13

1

1

0

1

0

1

0

14

0

1

1

1

1

0

1

Сума

6

10

4

8

5

7

9

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

Таблиця 1.3. Предметні набори з двох овочів

Набір

Кількість

Набір

Кількість

Набір

Кількість

Спаржа, квасоля

5

Квасоля, кукурудза

5

Капуста, помідори

2

Спаржа, капуста

1

Квасоля, перець

3

Кукурудза, перець

3

Спаржа, кукурудза

2

Квасоля, кабачки

6

Кукурудза, кабачки

3

Спаржа, перець

0

Квасоля, помідори

4

Кукурудза, помідори

4

Спаржа, кабачки

5

Капуста, кукурудза

2

Перець, кабачки

1

Спаржа, помідори

1

Капуста, перець

4

Перець, помідори

3

Квасоля, капуста

3

Капуста, кабачки

1

Кабачки, помідори

2

Як видно з таблиці 1.3, за прийнятими критеріями підтримки частими є лише сім наборів з двох овочів:

{спаржа, квасоля}; {спаржа, кабачки}; {квасоля, кукурудза}; {квасоля, кабачки}; {квасоля, помідори}; {капуста, перець}; {кукурудза, помідори}.

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

{спаржа, квасоля} + {спаржа, кабачки} = {спаржа, квасоля, кабачки}.

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

Таблиця 1.4. Предметні набори з трьох овочів

Набір

Кількість

Набір

Кількість

Спаржа, квасоля, кабачки

4

Квасоля, кабачки, помідори

2

Квасоля, кукурудза, кабачки

3

Квасоля, кукурудза, помідори

3

З огляду на отримані дані, множин третього порядку всього одна

{спаржа, квасоля, кабачки}.

Подальше виділення чистих наборів сенсу не має. Таким чином, в розглянутій задачі виділено 14 однопредметних частих наборів, 7 – двох предметних та 1 – трьох предметних. Маючи їх всі, переходимо до генерації асоціативних правил.

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

  1. виділення в наборі можливого часткового набору ;

  2. якщо , то записується асоціація вигляду , де , або точніше ;

  3. всі отримані правила оцінюються за підтримкою та достовірністю. Такі, що не задовольняють обраним критеріям, відкидаються.

Проілюструємо процедуру наступним прикладом. Набір {спаржа, квасоля, кабачки} може бути розділений на наступні не порожні часткові набори: {спаржа}, {квасоля}, {кабачки}, {спаржа, квасоля}, {спаржа, кабачки}, {квасоля, кабачки}. Відповідно може бути записано шість варіантів правил:

Якщо {спаржа}, то {квасоля, кабачки};

Якщо {квасоля}, то {спаржа, кабачки};

Якщо {кабачки}, то {спаржа, квасоля};

Якщо {спаржа, квасоля}, то {кабачки};

Якщо {спаржа, кабачки}, то {квасоля};

Якщо {квасоля, кабачки}, то {спаржа}.

Для першого правила підтримка – це відсоток рядків початкової бази даних, де одночасно зустрічаються як умова {спаржа}, так і наслідок {квасоля, кабачки}. Таких рядків 4 з 14 транзакцій. Тобто = 4/14 = 28,6%.

Достовірність цього правила вимірюється як відношення частоти зустрічі усього набору до частоти умови, тобто = 4/6 = 66,7%.

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

Таблиця 1.5. Асоціативні правила із двома предметами в умові

Якщо умова, то наслідок

Підтримка

Достовірність

якщо {спаржа}, то {квасоля й кабачки}

4/14 = 28,6%

4/6 = 66,7%

якщо {квасоля}, то {спаржа й кабачки}

4/14 = 28,6%

4/10 = 40%

якщо {кабачки}, то {спаржа й квасоля}

4/14 = 28,6%

4/7 = 57,1%

якщо {спаржа й квасоля}, то {кабачки}

4/14 = 28,6%

4/5 = 80%

якщо {спаржа й кабачки}, то {квасоля}

4/14 = 28,6%

4/5 = 80%

якщо {квасоля й кабачки}, то {спаржа}

4/14 = 28,6%

4/6 = 66,7%

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

Таблиця 1.6. Асоціативні правила з одним предметом в умові

Якщо умова, то наслідок

Підтримка

Достовірність

Якщо {спаржа}, то {квасоля}

5/14 = 35,7%

5/6 = 83,3%

Якщо {квасоля}, то {спаржа}

5/14 = 35,7%

5/10 = 50%

Якщо {спаржа}, то {кабачки}

5/14 = 35,7%

5/6 = 83,3%

Якщо {кабачки}, то {спаржа}

5/14 = 35,7%

5/7 = 71,4%

Якщо {квасоля}, то {кукурудза}

5/14 = 35,7%

5/10 = 50%

Якщо {кукурудза}, то {квасоля}

5/14 = 35,7%

5/8 = 62,5%

Якщо {квасоля}, то {кабачки}

6/14 = 42,9%

6/10 = 60%

Якщо {кабачки}, то {квасоля}

6/14 = 42,9%

6/7 = 85,7%

Якщо {квасоля}, то {помідори}

4/14 = 28,6%

4/10 = 40%

Якщо {помідори}, то {квасоля}

4/14 = 28,6%

4/6 = 66,7%

Якщо {капуста}, то {перець}

4/14 = 28,6%

4/5 = 80 %

Якщо {перець}, то {капуста)

4/14 = 28,6%

4/5 = 80 %

Якщо {кукурудза}, то {помідори}

4/14 = 28,6%

4/8 = 50 %

Якщо {помідори}, то {кукурудза}

4/14 = 28,6%

4/6 = 66,7 %

Повертаючись до початкових умов задачі (мінімальна підтримка 25%, мінімальна достовірність 80%), відкидаємо правила, які не задовольняють вимогам до значущості. Аби впорядкувати правила (встановити пріоритет їх перевірки при використанні у базі знань), розрахуємо синтетичний показник значущості, який дорівнює добутку підтримки на достовірність.

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

Таблиця 1.7. Асоціативні правила

Якщо умова, то наслідок

Підтримка, S

Достовірність, C

C S

Якщо {кабачки}, то {квасоля}

6/14 = 42,9%

6/7 = 85,7%

0,3677

Якщо {спаржа}, то {квасоля}

5/14 = 35,7%

5/6 = 83,3%

0,2971

Якщо {спаржа}, то {кабачки}

5/14 = 35,7%

5/6 = 83,3%

0,2974

Якщо {капуста}, то {перець}

4/14 = 28,6%

4/5 = 80%

0,2288

Якщо {перець}, то {капуста}

4/14 = 28,6%

4/5 = 80%

0,2288

Якщо {спаржа й квасоля}, то {кабачки}

4/14 = 28,6%

4/5 = 80%

0,2288

Якщо {спаржа й кабачки}, то {квасоля}

4/14 = 28,6%

4/5 = 80%

0,2288

Таким чином, у результаті застосування алгоритму Аргіогі нам удалося виявити 7 асоціативних правил, які з достовірністю не менше 80 % показують, які продукти з вихідного набору найчастіше продаються разом. Це знання дозволить розробити більш досконалу маркетингову стратегію, оптимізувати закупівлі та розміщення товару на прилавках і вітринах.

Лабораторна робота №2.

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

Завдання.

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

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

3. Подати задані значення аргументів на вхід нейронної мережі. Виходом вважати обчислене значення функції; виходом - логічну функцію, що дорівнює “1”, якщо більше середнього значення, та “0”, якщо менше.

4. Задати контрольні приклади та оцінити швидкість і точність алгоритму. В результаті навчання і тестування нейронної мережі необхідно побудувати графік залежності ймовірності (частотності) правильної відповіді від:

- кількості нейронів в прихованому шарі при заданій кількості вхідних нейронів (в межах від 1 до 10);

- кількості прикладів в навчальній вибірці при заданій кількості нейронів у вхідному і прихованому шарах (в межах від 10 до 100);

- значення порогу спрацювання нейронів вихідного шару при фіксованих значеннях інших параметрів.

Початкові дані знаходяться в файлі lab_CCC_vars.xls в робочому каталозі дисципліни на сервері локальної комп’ютерної мережі кафедри (лист “нейронні мережі”).

Методичні вказівки.

Алгоритм зворотного поширення похибки.

Алгоритм зворотного поширення похибки (АЗПП) відноситься до класичних алгоритмів навчання прямо зв’язаної нейронної мережі з учителем. В його основі лежить багаторазовий показ певного набору прикладів, для яких відомі наперед еталонні (визначені експериментально) відповіді, або ж бажані реакції нейронної мережі. Для кожного шару, починаючи з останнього, вихідного, у ході порівняння реакцій мережі та - еталонного значення ( номер нейрона у останньому шарі, загалом шарів).

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

, (2.1)

де - номер шару; - активація нейрона того шару; - кількість нейронів у шарі.

Для вихідного шару розрахункова формула має вигляд

, (2.2)

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

Величина корекції вагових коефіцієнтів того шару обчислюється за формулою

(2.3)

де - коефіцієнт інерційності, t - номер поточної ітерації.

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

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

Крок 2. Подача на вхід навчального образу і розрахунок виходу мережі.

Крок 3. Розрахунок помилки вихідного шару.

Крок 4. Розрахунок помилки попереднього шару – повторюється для усіх шарів, аж до першого.

Крок 5. Корекція вагових коефіцієнтів останнього шару за формулою

, (2.4)

де - обчислено за (2.3).

Крок 6. Корекція вагових коефіцієнтів усіх попередніх шарів аж до першого.

Крок 7. Якщо подані всі вхідні образи, то перехід на крок 8, інакше перехід на крок 2 (подається наступний образ).

Крок 8. Якщо помилка апроксимації менша за наперед визначену величину , то перехід на крок 9, в іншому випадку – рандомізація образів й перехід на крок 2.

Крок 9. Подаємо на вхід навченої мережі контрольний вектор і знаходимо прогноз .

Крок 10. Закінчення алгоритму.

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

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

- помилки вихідного шару (для кожного нейрону окремо для кожного образу):

- перший нейрон,

- другий нейрон.

- помилки прихованого шару (нейронів три, приклад той самий, що й для шару 2)

- перший нейрон,

- другий нейрон,

- третій нейрон.

- корекції вагових коефіцієнтів нейронів другого шару (розмір матриці 3*2)

;

;

;

;

;

.

- корекції вагових коефіцієнтів першого шару (розмір матиці 3*3)

;

;

;

;

;

;

;

;

.

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

Лабораторна робота № 3.

Реалізація та дослідження радіально-базисних нейронних мереж

Завдання.

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

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

3. Подати задані значення аргументів на вхід нейронної мережі. Виходом вважати обчислене значення функції; виходом - логічну функцію, що дорівнює “1”, якщо більше середнього значення, та “0”, якщо менше.

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

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

Початкові дані знаходяться в файлі lab_CCC_vars.xls в робочому каталозі дисципліни на сервері локальної комп’ютерної мережі кафедри (лист “нейронні мережі”).

Лабораторна робота № 4.

Реалізація та дослідження багаторядного МГВА

Соседние файлы в папке CCC