7.4. Різновиди алгоритму Apriori

Уведення інформації про групування елементів може використовуватися для відсікання «нецікавих» правил.

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

— елементи на верхніх рівнях ієрархії прагнуть до значно більших значень підтримки порівняно з елементами на нижніх рівнях;

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

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

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

Виявлення узагальнених асоціативних правил.

Нехай I — ліс спрямованих дерев. Дуги в I — це залежності між елементами. Нехай елементи, що належать I, розташовані в деякій ієрархії. Якщо є дуга від a до b, то говорять, що a — предок b та b — нащадок a (a — це узагальнення b).

Необхідно знайти закономірності, що є узагальненими асоціативними правилами виду X?Y, причому supp(X?Y) ? minsupport та conf(X?Y) ? minconfidence.

Це визначення задачі має одну проблему. Справа в тому, що за такого визначення задачі, будуть знайдені «зайві» узагальнені асоціативні правила. Для розв’язання цієї проблеми розглянемо такий параметр правила, як рівень інтересу.

Визначення «цікавих» правил.

Нехай множини елементів, що входять в Z тільки в тому випадку, якщояхом підміни одного чи кількох елементів їхніми предками. Будемо називати правила предками правила X?Y. найближчим предком правила X ? Y, якщо не існує такого правила X?Y, що X?Y — це предок X?Y та X?Y — це предок X?Y.

Z — це предок Z, де Z та Z — ієрархію (Z, Z ? I). Z є предком Z можна одержати із Z шлX?Y, X?Y, X?Y

Правило X?Y є

Подібні визначення можна дати і для правил: X?Y, X?Y.

Нехай Pr(X) — це ймовірність того, що всі елементи з X міс

тяться в одній розширеній транзакції. Тоді supp(X?Y) = Pr(X?Y) та conf(X?Y) = Pr(Y|X). Якщо підтримка {x,y} більше значення мінімальної підтримки, то і підтримка {x,y}, і підтримка {x,y}, і підтримка {x,y} будуть більше порога мінімальної підтримки. Однак якщо вірогідність правила X?Y більше мінімальної вірогідності, тільки правило X?Y гарантовано буде мати вірогідність більшу, ніж мінімальна. Підтримка елементу, узятого із внутрішнього рівня ієрархії, не дорівнює сумі підтримок елементів, що є безпосередніми нащадками цього елементу. Pr(X?Y) та conf(X?Y) = Pr(Y|X). Якщо підтримка {x,y} більше значення мінімальної підтримки, то і підтримка {x,y}, і підтримка {x,y}, і підтримка {x,y} будуть більше порога мінімальної підтримки. Однак якщо вірогідність правила X?Y більше мінімальної вірогідності, тільки правило X?Y гарантовано буде мати вірогідність більшу, ніж мінімальна. Підтримка елементу, узятого із внутрішнього рівня ієрархії, не дорівнює сумі підтримок елементів, що є безпосередніми нащадками цього елементу.

Розглянемо правило X?Y. Нехай Z = X ? Y. Помітимо, що supp(X?Y) = supp(Z). Назвемо E Z [Pr(Z)] очікуваним значенням Pr(Z) відносно Z. Нехай Z = {z

1 , ..., z n }, Z={z

1 , ..., z j , z j+1 , ..., z n }, 1 ? j ? n. Тоді можна визначити:supp(X?Y) = supp(Z). Назвемо E Z [Pr(Z)] очікуваним значенням Pr(Z) відносно Z. Нехай Z = {z

1 , ..., z n }, Z={z

1 , ..., z j , z j+1 , ..., z n }, 1 ? j ? n. Тоді можна визначити:Pr(Z) відносно Z. Нехай Z = {z

1 , ..., z n }, Z={z

1 , ..., z j , z j+1 , ..., z n }, 1 ? j ? n. Тоді можна визначити:

1 n

1 j j+1 n 1 ? j ? n. Тоді можна визначити:тяться в одній розширеній транзакції. Тоді supp(X?Y) = Pr(X?Y) та conf(X?Y) = Pr(Y|X). Якщо підтримка {x,y} більше значення мінімальної підтримки, то і підтримка {x,y}, і підтримка {x,y}, і підтримка {x,y} будуть більше порога мінімальної підтримки. Однак якщо вірогідність правила X?Y більше мінімальної вірогідності, тільки правило X?Y гарантовано буде мати вірогідність більшу, ніж мінімальна. Підтримка елементу, узятого із внутрішнього рівня ієрархії, не дорівнює сумі підтримок елементів, що є безпосередніми нащадками цього елементу.

Розглянемо правило X?Y. Нехай Z = X ? Y. Помітимо, що supp(X?Y) = supp(Z). Назвемо E Z [Pr(Z)] очікуваним значенням Pr(Z) відносно Z. Нехай Z = {z

1 , ..., z n }, Z={z

1 , ..., z j , z j+1 , ..., z n }, 1 ? j ? n. Тоді можна визначити:

Аналогічно E X?Y [Pr(Y|X)] визначимо як очікуване значення ві

Правило X?Y називається R-цікавим щодо правила-предка, якщо підтримка правила X?Y у R разів більше очікуваної підтримки правила X?Y щодо предка або якщо вірогідність правила X?Y у R разів більше очікуваної вірогідності правила X?Y щодо правила-предка.

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

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

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

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

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

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

правила X?Y (наприклад, AB?CD), причому X?Y = ABCD. Підтримка правила дорівнює підтримці множини, що часто трапляллється. Вірогідність правила обчислюється за формулою conf(X?Y) = supp(X?Y)/supp(X). Правило додається до резуль-conf(X?Y) = supp(X?Y)/supp(X). Правило додається до резуль-правила X?Y (наприклад, AB?CD), причому X?Y = ABCD. Підтримка правила дорівнює підтримці множини, що часто трапляллється. Вірогідність правила обчислюється за формулою conf(X?Y) = supp(X?Y)/supp(X). Правило додається до резуль-

Етап 3. З результуючого списку правил видаляються всі «нецікаві» правила.

Базовий метод пошуку множин, що часто трапляються.

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

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

Даний метод можна записати як послідовність кроків.

Крок 1. Виділити і занести в L

1 множини елементів і груп елементів, що часто трапляються. Установити: k = 2.

Крок 2. Якщо L k–1 ? ?, тоді перейти до кроку 3, у протилежному випадку — перейти до кроку 7.

Крок 3. Згенерувати C k — множину кандидатів потужністю k на основі L k–1 .

Крок 4. Для всіх транзакцій t?D виконати кроки 4.1

—4.3.

Крок 4.1. Розширити транзакцію t предками всіх елементів, що входять у транзакцію.

Крок 4.2. Видалити дублікати з транзакції t.

Крок 4.3. Для всіх кандидатів с?C k виконати: якщо с ? t, то установити: c.count = c.count + 1.

Крок 5. Зробити відбір кандидатів: L k = {с?C k | c.count ? minsupport}.

Крок 6. Установити: k = k + 1. Перейти до кроку 3.

Крок 7. Зупинення. Повернути як результат L k .

Функція генерації кандидатів. Для того щоб одержати k-елементні набори, скористаємося (k–1)-елементними наборами, які були визначені на попередньому кроці і є такими, що часто трапляються.

Метод генерації кандидатів буде складатися з двох кроків.

Крок 1. Об’єднання. Кожний кандидат C k буде формуватися шляхом розширення набору, що часто трапляється, розміром (k – 1) додаванням елементу з іншого (k – 1)-елементного набору: включити до C k ті елементи a

1 , a

2 , ..., a k–1 , b k–1 з L k–1 : a, b ? L k–1 , для яких: a

1 = b

1 , a

2 = b

2 , ... , a k–2 = b k–2 , a k–1 < b k–1 .

Крок 2. Видалення надлишкових правил. На підставі властивості антимонотонності, варто видалити всі набори з C k , як-

туючого списку правил, якщо вірогідність цього правила більше порога minconf.

Хеш-дерево можна використовувати для ефективного підрахунку підтримки кандидатів.

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

7.4. Різновиди алгоритму Apriori

Виявлення частих наборів об’єктів — операція, що потребує великої кількості обчислень, а отже, і часу. Алгоритм Apriori (масштабувальний метод пошуку асоціативних правил) описаний у 1994 р. Срікантом Рамакрішнан (Ramakrishnan Srikant) і Ракешом Агравалом (Rakesh Agrawal). Він використовує одну з властивостей підтримки, що свідчить: підтримка будь-якого набору об’єктів не може перевищувати мінімальної підтримки будь-якої з його підмножин: EF SuppSupp?, при FE?.

Наприклад, підтримка 3-об’єктного набору (подія 1, подія 2, подія 3} буде завжди меншою або дорівнювати підтримці 2-об’єктних наборів {подія 1, подія 2}, {подія 2, подія 3), (подія 1, подія 3). Це пояснюється тим, що будь-яка транзакція, що містить (подія 1, подія 2, подія 3), містить також і набори {подія 1, подія 2), {подія 2, подія 3), {подія 1, подія 3), причому зворотне неправильне.

Алгоритм Apriori визначає набори, що часто трапляються, за декілька кроків. На і-ому етапі визначаються всі і-елементні набори, що часто трапляються. Кожний етап складається з двох

що хоча б одна з його (k–1) підмножин не є такою, що часто трпаляється.

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

Описаний алгоритм можна записати у вигляді такого псевдокоду: менша заданої користувачем. Кожний член множини має набір C k — безліч кандидатів k-елементних потенційно частих на

L

1 = 1-елементні набори, що часто трапляються для (k = 2; L k – 1 <> ?; k ++) C k = Apriorigen (Fk – 1) / / генерація кандидатів для всіх транзакцій t ? D виконати

С t = subset (C k , t) / / видалення зайвих правил

Для всіх кандидатів c ? C t виконати c. count ++ кінець для всіх кінець для всіх L k = {c ? Ck ? c.count >= Supp min } / / відбір кандидатів

Кінець для для (k = 2; L k – 1 <> ; k ++) C k = Apriorigen (Fk – 1) / / генерація кандидатів для всіх транзакцій t ? D виконати

С t = subset (C k , t) / / видалення зайвих правил

Для всіх кандидатів c ? C t виконати c. count ++ кінець для всіх кінець для всіх L k = {c ? Ck ? c.count >= Supp min } / / відбір кандидатів

Кінець для C k = Apriorigen (Fk – 1) / / генерація кандидатів для всіх транзакцій t ? D виконати

С t = subset (C k , t) / / видалення зайвих правил

Для всіх кандидатів c ? C t виконати c. count ++ кінець для всіх кінець для всіх L k = {c ? Ck ? c.count >= Supp min } / / відбір кандидатів

Кінець для

С t = subset (C k , t) / / видалення зайвих правил

Для всіх кандидатів c ? C t виконати c. count ++ кінець для всіх кінець для всіх L k = {c ? Ck ? c.count >= Supp min } / / відбір кандидатів

Кінець для c. count ++ кінець для всіх кінець для всіх L k = {c ? Ck ? c.count >= Supp min } / / відбір кандидатів

Кінець для L k = c Ck c.count >= Supp min / / відбір кандидатів

Кінець для

Результат U k k L= L

1 = 1-елементні набори, що часто трапляються для (k = 2; L k – 1 <> ?; k ++) C k = Apriorigen (Fk – 1) / / генерація кандидатів для всіх транзакцій t ? D виконати

С t = subset (C k , t) / / видалення зайвих правил

Для всіх кандидатів c ? C t виконати c. count ++ кінець для всіх кінець для всіх L k = {c ? Ck ? c.count >= Supp min } / / відбір кандидатів

Кінець для

Результат U k k L=

Опишемо позначення, що використовуються в алгоритмі: L k — множина k-елементних частих наборів, чия підтримка не упорядкованих (i j < i p , якщо j < p) елементів F і значення підтримки набору Supp F > Supp min : ки набору Supp F > Supp min : L k = (F

1 , Supp

1 ), (F

2 , Supp

2 ), …, (F q , Supp q ), упорядкованих (i j < i p , якщо j < p) елементів F і значення підтримки набору Supp F > Supp min : L k = {(F

1 , Supp

1 ), (F

2 , Supp

2 ), …, (F q , Supp q )}, борів. Кожний член множини має набір упорядкованих (i j < i p , якщо j < p) елементів F і значення підтримки набору Supp.

Опишемо даний алгоритм по кроках.

Крок 1. Привласнити k = 1 і виконати відбір eсіх k-елементних наборів, у яких підтримка більшa за мінімально задану користувачем Supp min .

Крок 2. k = k + 1.якщо j < p) елементів F і значення підтримки набору Supp.

Опишемо даний алгоритм по кроках.

Крок 1. Привласнити k = 1 і виконати відбір eсіх k-елементних наборів, у яких підтримка більшa за мінімально задану користувачем Supp min .

Крок 2. k = k + 1.

Крок 1. Привласнити k = 1 і виконати відбір eсіх k-елементних наборів, у яких підтримка більшa за мінімально задану користувачем Supp min .

Крок 2. k = k + 1.

Крок 2. k = k + 1.борів. Кожний член множини має набір упорядкованих (i j < i p , якщо j < p) елементів F і значення підтримки набору Supp.

Опишемо даний алгоритм по кроках.

Крок 1. Привласнити k = 1 і виконати відбір eсіх k-елементних наборів, у яких підтримка більшa за мінімально задану користувачем Supp min .

Крок 2. k = k + 1.

кроків: формування кандидатів (candidate generation) і підрахунку підтримки кандидатів (candidate counting).

дидати (k – 1) = елементні часті набори. Кожний кандидат с ? С k формуватиметься шляхом додавання до (k – 1)-елементного частого набору — р елемента з іншого (k – 1)-елементного частого набору — q. Причому додається останній елемент набору q, який за порядком вищий, ніж останній елемент набору ()

11 q.itemp.item ?? < kk p.

При цьому перші всі k – 2 елементи обох наборів однакові ()

222211 q.itemp.item...,,q.itemp.item,q.itemp.item ?? === kk . Це може бути записано у вигляді наступного SQL-подібного запиту.

11 q.itemp.item ?? < kk p

При цьому перші всі k – 2 елементи обох наборів однакові ()

222211 q.itemp.item...,,q.itemp.item,q.itemp.item ?? === kk . Це може бути записано у вигляді наступного SQL-подібного запиту.

222211 q.itemp.item...,,q.itemp.item,q.itemp.item ?? === kk бути записано у вигляді наступного SQL-подібного запиту. where p.item

1 = q.item

1 , p.item

2 = q.item

2 , …, p.item k – 2 = q.item k – 2 , p.item k – 1 < q.item k – 1 p.item k – 1 < q.item k – 1

Крок 3. Якщо не вдається створювати k-елементні набори, то завершити алгоритм, інакше виконати наступний крок.

Крок 4. Створити множину k-елементних наборів кандидатів у часті набори. Для цього необхідно об’єднати в k-елементні кандидати (k – 1) = елементні часті набори. Кожний кандидат с ? С k формуватиметься шляхом додавання до (k – 1)-елементного частого набору — р елемента з іншого (k – 1)-елементного частого набору — q. Причому додається останній елемент набору q, який за порядком вищий, ніж останній елемент набору ()

11 q.itemp.item ?? < kk p.

При цьому перші всі k – 2 елементи обох наборів однакові ()

222211 q.itemp.item...,,q.itemp.item,q.itemp.item ?? === kk . Це може бути записано у вигляді наступного SQL-подібного запиту. insert into C k select p.item

1 , p.item

2 , …, p.item k – 1 , q.item k – 1 from L k – 1 p, L k – 1 q where p.item

1 = q.item

1 , p.item

2 = q.item

2 , …, p.item k – 2 = q.item k – 2 , p.item k – 1 < q.item k – 1

Крок 5. Для кожної транзакції Т з множини D вибрати кандидамножині

1?k L Це можна записати у вигляді такого псевдокоду: для всіх наборів с ? С k виконати для всіх (k – 1) — піднаборів s із с виконати якщо (s ? L k – 1 ), то видалити с із С k

Крок 6. Для кожного кандидата з множини С k збільшити значення підтримки на одиницю.

Крок 7. Вибрати тільки кандидатів L k з множини С k , у яких значення підтримки більше заданої користувачем min Supp. Повернутися до кроку 2.

Результатом роботи алгоритму є об’єднання всіх множин L k для всіх k.

Після того, як хеш-дерево з кандидатами-наборами побудовамістяться і в транзакції, kik CTC=?. На кореневому рівні хеш-містяться і в транзакції, kik CTC=?. На кореневому рівні хеш-

тів C і з множини С k , присутніх у транзакції Т. Для кожного набору з побудованої множини С k видалити набір, якщо хоча б одна з його (k – 1) підмножин не є тим, що часто трапляється, тобто відсутній у но, легко підрахувати підтримку для кожного кандидата. Для цього потрібно «пропустити» кожну транзакцію через дерево і збільшити лічильники для тих кандидатів, чиї елементи також

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

Такі самі дії застосовуються для знаходження (k + 1)-елементних наборів і т. д.

Алгоритм AprioriTid є різновидом алгоритму Apriori. Відмінною рисою даного алгоритму є підрахунок значення підтримки кандидатів не при скануванні множини D, а за допомогою мно

Кожний член множини k C є парою вигляду k }де кожний F k є потенційно частим k-елементним набором, представленим у транзакції з ідентифікатором TID. Множина DC=

1 відповідає безлічі транзакцій, хоча кожний об’єкт у транзакції відповідає ним у транзакції з ідентифікатором TID. Множина DC=

1 відповідає безлічі транзакцій, хоча кожний об’єкт у транзакції відповідає >??<TcCc k ,T.TID

Такі самі дії застосовуються для знаходження (k + 1)-елементних наборів і т. д.

Алгоритм AprioriTid є різновидом алгоритму Apriori. Відмінною рисою даного алгоритму є підрахунок значення підтримки кандидатів не при скануванні множини D, а за допомогою множини k C, що є безліччю кандидатів (k-елементних наборів) потенційно частих, у відповідність яким ставиться ідентифікатор TID транзакцій, в яких вони містяться.

Кожний член множини k C є парою вигляду F k }>, де кожний F k є потенційно частим k-елементним набором, представленим у транзакції з ідентифікатором TID. Множина DC=

1 відповідає безлічі транзакцій, хоча кожний об’єкт у транзакції відповідає одно-об’єктному набору в множині

1 C, що містить цей об’єкт.

Член множини k C, відповідний транзакції T, є парою такого вигляду: {} >??<TcCc k ,T.TID.

Підмножина наборів у k C з однаковими TID (тобто містяться в одній і тій самій транзакції) називається записом. Якщо транзакція не містить жодного k-елементного кандидата, то k C не матиме запису для цієї транзакції. Тобто кількість записів у k C може бути датів. Проте для малих значень k кожний запис може бути більшим, ніж відповідна транзакція, оскільки k C включає всіх кандидатів до-елементних наборів, що містяться в транзакції.

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

режі.

У ньому використовується така властивість підтримки послідовностей: для будь-якої послідовності L k її підтримка буде менша, ніж підтримка послідовностей із множини

1?k L. Алгоритм MSAP для пошуку подій, які йдуть одна за одною, використовує

Для того щоб було можливо застосувати метод Apriori, необхідно провести передобробку даних: по-перше, привести всі дані до бінарного вигляду; по-друге, змінити структуру даних — подати їх у вигляді таблиці. Кількість стовпців у таблиці дорівнює кількості елементів, наявних у множині транзакцій D. Кожний запис відповідає транзакції, де у відповідному стовпці стоїть 1, якщо елемент є у транзакції, і 0

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

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

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

|I| ) операцій, де |I| — кількість елементів.

Резюме за змістом теми

Подання інформації про поводження ПСШІ в процесі формування ланцюжка логічного виведення при пошуку рішення є важливим з таких причин:

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

Іншим різновидом алгоритму Apriori є алгоритм MSAP (Mining Sequential Alarm Patterns), спеціально розроблений для виконання секвенціального аналізу збоїв телекомунікаційної мепоняття «термінового вікна» (Urgent Window). Це дозволяє виявляти не просто однакові послідовності подій, а такі, що відбуваються одна за одною. В іншому даний алгоритм працює за тим самим принципом, що й Apriori.

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

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

— програмісти, котрі супроводжують, налагоджують і модернізують систему, мають потребу в інструменті, що дозволяє заглянути в «нутро» системи на рівні більш високому, ніж виклик окремих мовних процедур;

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

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

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

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

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

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

Основними характеристиками асоціативних правил є підтримка, достовірність і поліпшення.

Підтримка (support) показує, який відсоток транзакцій підтримує дане правило.

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

Поліпшення (improvement) показує, чи корисніше правило випадкового вгадування,

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

Алгоритм Apriori використовує одну із властивостей підтримки, що свідчить: підтримка будь-якого набору об’єктів не може перевищувати мінімальної підтримки будь-якої з його підмножин.

Терміни та поняття до теми

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

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

Функціональні пояснення (цільові, мотиваційні пояснення) будуються за принципом «X необхідно для проходження Y», тобто виконувані системою кроки розуміються стосовно до поставленої мети.

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

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

Стан — це колекція характеристик, що можуть використовуватися для визначення стану або статусу об’єкта.

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

Стратегія пошуку в просторі станів — порядок, у якому відбувається розгортання станів.

Питання для самоконтролю

1. Назвіть методи формування пояснень.

2. У чому полягає метод фіксації ситуацій?

3. Обґрунтуйте стратегію пошуку в просторі станів.

4. За допомогою яких показників оцінюють продуктивність методів пошуку?

5. Охарактеризуйте пошук з поверненнями.

6. З яких етапів складається евристичний пошук?

7. Проаналізуйте масштабувальний метод пошуку асоціативних правил Apriori.

Завдання для індивідуальної роботи, обов’язкові та додаткові практичні завдання

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

2. Наведіть приклад стратегії пошуку в просторі станів — порядок, у якому відбувається розгортання станів.

3. Опишіть пошук асоціативних і секвенціальних закономірностей між пов’язаними подіями в базах знань.

4. Поясніть приклад масштабувального методу пошуку асоціативних правил Apriori.

Література для поглибленого вивчення матеріалу

1. Люгер Дж. Ф. Искусственный интеллект. — М. : Вильямс, 2005.

— 864 с.

2. Інформаційні системи в економіці : монографія / под ред. Устенко С. В. — К. : КНЕУ, 2011. — 424 с.

3. Іванченко Г. Ф. Системи штучного інтелекту : навч. посіб. — К. : КНЕУ, 2011. — 382 с.