Цей пошук є повним при кінцевому коефіцієнті розгалуження b і оптимальним при однакових вартостях етапів і характеризується часовою складністю Sk(b d ) і просторовою складністю Sk(bd).
У пошуку з ітеративним поглибленням поєднуються переваги пошуку в глибину і пошуку в ширину. Як і пошук у глибину, він характеризується невибагливими вимогами до пам’яті. Як і пошук у ширину, він є повним, якщо коефіцієнт розгалуження кінцевий, і оптимальним, якщо вартість шляху являє собою неубутувальну функцію глибини вузла. Ітеративне поглиблення є кращим методом неінформованого пошуку за умов, коли є великий простір пошуку, а глибина рішення невідома.
Оскільки сліпий пошук можливий тільки в невеликому просторі варіантів, необхідний певний спосіб спрямованого пошуку.
Стратегії інформованого (евристичного) пошуку — стратегії, що дозволяють визначити, чи є один нецільовий стан більш перспективним порівняно з іншим. Ці стратегії використовують при пошуку шляху на графі в просторі станів певні знання, специфічні для конкретної ПРГ.
Найкраще розглядати евристику як деяке правило впливу, що, хоч і не гарантує успіх (як детермінований метод або процедура прийняття рішення), у більшості випадків виявляється дуже корисним.
У загальному вигляді евристичний пошук можна подати як послідовність таких етапів:
Етап 1. Обрати із множини можливих дій певну дію:
• з урахуванням відповідності до цілі:
— зменшення певної небажаної розбіжності,
— безпосереднє розв’язання тієї чи іншої підзадачі;
• з урахуванням досвіду:
— повторення минулого,
— виявлення ключової дії;
• з урахуванням необхідних умов:
— рішення, обумовлене аналізом ситуації,
— виключення нездійсненного варіанта;
• з урахуванням фактора випадковості:
— перевага віддається розмаїтості.
Етап 2. Здійснити обрану дію і змінити поточну ситуацію.
Етап 3. Оцінити ситуацію:
глибини повертає значення failure, а це означає, що рішення не існує.
• за аналогією:
— відома сама задача,
— відома підзадача;
• за величиною відстані до цілі:
— відстань між двома ситуаціями,
— кількість зусиль, затрачуваних на пошук;
• за математичним критерієм:
— складання переліку необхідних та/або достатніх для одержання даного рішення характеристик,
— чисельна оцінна функція,
— верхні і нижні межі,
— сума вартостей, обраних придатним способом;
• за очікуваним виграшем (критерій, пов’язаний з минулим досвідом):
— простота ситуації,
— коефіцієнт розширення пошуку,
— інший критерій (складність задачі, час витратний на її розв’язування і т. д.).
Етап 4. Відкинути некорисні ситуації.
Етап 5. Якщо досягнуто кінцеву ситуацію — кінець; у протилежному випадку — вибрати нову, вихідну ситуацію і почати спочатку:
• рухатися тільки вперед:
— систематичний розвиток останньої породженої ситуації;
• виконувати всі дії паралельно:
— почергове виконання всіх дій;
• як вихідну обирати найбагатообіцяючу ситуацію:
— стосовно оцінної функції,
— стосовно незначного числа вхідних у неї дій;
• іти на компроміс між:
— глибиною пошуку,
— оцінкою ситуації.
Метод пошуку зі сходженням до вершини (пошук екстремуму, hill climbing)
— проста форма евристичного пошуку, що є фундаментальним методом локального пошуку. У процесі пошуку використовується певна оцінна функція, за допомогою якої можна грубо оцінити, наскільки гарним або поганим є поточний стан. При цьому оцінюють не тільки поточний стан пошуку, але і його нащадків. Для подальшого пошуку вибирається найкращий нащадок; при цьому про його братів і батьків просто забувають. Пошук припиняється, коли досягається стан, що кращий, ніж кожний з його нащадків.
Метод сходження до вершини можна сформулювати в такий спосіб.
Крок 1. Перебуваючи у даній точці простору станів, застосувати правила породження нової множини можливих рішень.
Крок 2. Якщо один з нових станів є розв’язанням проблеми, припинити процес. У протилежному випадку перейти в той стан, що характеризується найвищим значенням оцінної функції. Повернутися до кроку 1.
Пошук зі сходженням до вершини іноді називають жадібним локальним пошуком, оскільки в процесі його виконання відбувається захоплення найкращого сусіднього стану без попередніх міркувань про те, куди варто відправитися далі. Якщо кількість найкращих нащадків вузла більше одного, то метод зазвичай передбачає випадковий вибір нащадка серед них.
У методі зі сходженням до вершини не здійснюється прогнозування за межами станів, що є безпосередньо сусідніми стосовно поточного стану.
Жадібні методи часто показують дуже високу продуктивність, але застосування цієї стратегії наштовхується на такі труднощі:
— необхідність формулювання оцінної функції, яка б адекватно відображала якість поточного стану;
— тенденція зупинятися в локальному максимумі — рішенні, з якого можливий тільки спуск, тобто погіршення стану. Тільки-но метод досягає стану, що має кращу оцінку, ніж його нащадки, він зупиняється. Якщо цей стан не є розв’язанням задачі, а тільки локальним максимумом, то такий метод неприйнятний для даної задачі. Це означає, що рішення може бути оптимальним на обмеженій множині, але через форму всього простору, можливо, ніколи не буде обране найкраще рішення.
Оскільки в цій стратегії дані про попередні стани не зберігаються, то вона без механізмів повернення або інших прийомів відновлення не може відрізнити локальний максимум від глобального, унаслідок чого метод не може бути відновлений із точки, що призвела до невдачі. Існують методи наближеного розв’язання цієї проблеми, наприклад, випадкове збурювання оцінки. Однак гарантовано розв’язувати задачі з використанням даної стратегії пошуку не можна.
Незважаючи на ці обмеження, метод пошуку зі сходженням до вершини може бути досить ефективним, якщо оцінна функція дозволяє уникнути локального максимуму і зациклення методу.
Метод пошуку за першим найкращим збігом (жадібний пошук, best-first search) — форма евристичного пошуку, що використовує оцінну функцію, за допомогою якої можна порівнювати стани в просторі станів.
Кожному стану n відповідає значення оцінної функції f = g(n) + h(n), де g(n) — глибина стану n у просторі пошуку, оцінка якого утримує метод від проходження неправильним шляхом, h(n) — деяка евристична оцінка відстані від стану n до цілі, що веде метод пошуку до евристично найбільш перспективних станів.
Метод порівнює не тільки ті стани, у які можливий перехід з поточного стану, але й усі, до яких можна дістатися. Такий метод потребує великих обчислювальних ресурсів, але його ідея полягає в тому, щоби брати до уваги не тільки найближчі стани, тобто локальну обстановку, а й переглянути якомога більшу ділянку простору станів і бути готовим, у разі потреби, повернутися туди, де він уже був, і піти іншим шляхом, якщо найближчі претенденти не обіцяють істотного прогресу в досягненні мети. Саме ця можливість відмовитися від частини пройденого шляху заради глобальної мети і дозволяє знайти більш ефективний шлях.
Метод використовує списки збережених станів: список Open відстежує поточний стан пошуку, а в Closed записуються вже перевірені стани. На кожному кроці метод записує в список Open стан з урахуванням деякої евристичної оцінки його близькості до цілі. Таким чином, на кожній ітерації розглядаються найбільш перспективні стани зі списку Open. Стани в списку Open сортуються згідно зі значеннями оцінної функції f. Зберігаючи всі стани в списку Open, метод зможе уберегти себе від невдалого завершення. У жадібному методі пошуку за використання пріоритетної черги можливе відновлення точки локального максимуму.
Метод допускає виконання таких кроків:
Крок 1. Установити: Open = {S}, Closed = ?, де S — початковий стан.
Крок 2. Якщо Open = ?, то перейти до кроку 9, у протилежному випадку — перейти до кроку 3.
Крок 3. Видалити перший стан X зі списку Open.
Крок 4. Якщо X — цільовий стан, то зупинення, повернути шлях від S до X; у протилежному випадку — перейти до кроку 5.
Крок 5. Згенерувати нащадків X.
Крок 6. Для кожного нащадка X виконувати кроки 6.1
—6.3.
Крок 6.1. Якщо нащадок не міститься в списках Open та Closed, то зіставити нащадку евристичне значення і додати нащадка в список Open.
Крок 6.2. Якщо нащадок міститься в списку Open і нащадок був досягнутий найкоротшим шляхом, то записати цей стан у список Open.
Крок 6.3. Якщо нащадок міститься в списку Closed і нащадок був досягнутий найкоротшим шляхом, то видалити стан зі списку Closed і додати нащадок у список Open.
Крок 7. Помістити X у список Closed.
Крок 8. Переупорядкувати стани в списку Open відповідно до евристики «кращі ліворуч».
Крок 9. Зупинення. Повернути відмову — список Open порожній.
На кожній ітерації метод видаляє перший елемент зі списку Open. Досягнувши мети, він повертає шлях, що веде до рішення. Помітимо, що кожен стан зберігає інформацію про попередній стан, аби згодом відновити його і дозволити методу знайти найкоротший шлях до рішення.
Якщо перший елемент у списку Open не є рішенням, то метод використовує правила перевірки відповідності й операції, щоби згенерувати всіх можливих нащадків даного елемента. Якщо нащадок уже знаходиться в списку Open або Closed, то метод вибирає найкоротший із двох можливих шляхів досягнення цього стану.
Потім метод обчислює евристичну оцінку станів у списку Open і сортує список відповідно до цих евристичних значень. При цьому кращі стани ставляться на початок списку. Зазначимо, що через евристичну природу оцінювання наступний стан має перевірятися на будь-якому рівні простору станів. Відсортований список Open часто називають пріоритетною чергою (priority queue).
На відміну від пошуку екстремуму, що не зберігає пріоритетну чергу для відбору наступних станів, даний метод відновлюється після помилки і знаходить цільовий стан.
Пошук за першим найкращим збігом нагадує пошук у глибину в тому сенсі, що цей метод надає переваги на шляху до мети постійному крокуванню єдиним шляхом, але метод повертається до попередніх вузлів після потрапляння в глухий кут. Даний метод має ті самі недоліки, що й пошук у глибину: він не є оптимальним, до того ж він неповний (оскільки здатний відправитися по нескінченному шляху та так і не повернутися, щоби випробувати інші можливості). При цьому в найгіршому випадку оцінки часової і просторової складності становлять Sk(b m ), де m — максимальна глибина простору пошуку. Однак гарна евристична функція
Компонент g(n) функції оцінки додає жадібному пошуку властивості пошуку в ширину. Він запобігає можливості заблукання через помилкову оцінку: якщо евристика безупинно повертає гарні оцінки для станів на шляху, що не веде до мети, то значення g буде зростати і домінувати над h, повертаючи процедуру пошуку до найкоротшого шляху. Це рятує метод від зациклення.
Метод рекурсивного пошуку за першим найкращим збігом (Recursive Best-First Search
— RBFS) — простий рекурсивний метод, у якому робляться спроби імітувати роботу стандартного пошуку за першим найкращим збігом, але з використанням тільки лінійного простору. Метод може бути описаний як така функція.
Функція RBFS (вузол node, межа f-вартості f limit ) — повертає рішення result або індикатор невдачі «відмова» і нову межу f-вартості f limit .
Крок 1. Якщо вузол node — цільовий, то повернути result = node.
Крок 2. Сформувати для вузла node множину вузлів-нащадків Successors.
Крок 3. Якщо Successors = ?, то повернути: result = «відмова» та f limit = ?.
Крок 4. Для кожного вузла s у Successors установити: f(s) = max(g(s) + h(s), f (node)).
Крок 5. Установити: best = вузол з найменшим f-значенням у множині Successors.
Крок 6. Якщо f(best) > f limit , то повернути result = «відмова» та f limit = f (best).
Крок 7. Знайти alternative — друге після найменшого f-значення для елементів у множині Successors.
Крок 8. Установити: result, f (best) = RBFS (best, min(f limit , alternative)).
Крок 9. Якщо result ? «відмова», то повернути result.
Перший виклик функції: RBFS (node = початковий вузол, f limit = ?).
Цей метод контролює f-значення найкращого альтернативного шляху, доступного з будь-якого предка поточного вузла. Якщо поточний вузол перевищує дану межу, то поточний етап рекурсії скасовується і рекурсія продовжується з альтернативного шляху. Після скасування даного етапу рекурсії відбувається заміна
дозволяє істотно скоротити таку складність. Величина цього скорочення залежить від конкретної задачі та від якості евристичної функції.
Метод RBFS є оптимальним, якщо евристична функція h(n) є припустимою. Його просторова складність дорівнює Sk(bd), але охарактеризувати часову складність досить важко: вона залежить і від точності евристичної функції, і від того, наскільки часто відбувалася зміна найкращого шляху в процесі розгортання вузлів. Метод RBFS має суттєвий недолік, пов’язаний із занадто частим повторним формуванням вузлів.
Метод пошуку А * — різновид пошуку за першим найкращим збігом. Метод припускає використання для кожного вузла n на графі простору станів оцінної функції виду f (n) = g(n) + h(n), де g(n) відповідає відстані на графі від вузла n до початкового стану, h(n) — оцінка відстані від n до вузла, що подає кінцевий (цільовий) стан. Чим менше значення оцінної функції f (n), тим «краще», тобто вузол n лежить на більш короткому шляху від вихідного стану до цільового. Ідея методу полягає в тому, щоб за допомогою f (n) відшукати найкоротший шлях на графі від вихідного стану до цільового. Звідси випливає, що якщо h(n) — нижня оцінка дійсної відстані до цільового стану, тобто якщо h(n) ніколи не дає завищеної оцінки відстані, то метод А * завжди відшукає оптимальний шлях до цілі за допомогою оцінної функції f (n).
Нехай s — вузол початкового стану; g — вузол цільового стану; Open — список, що містить обрані, але необроблені вузли; Closed — список, що містить оброблені вузли. Тоді метод A * буде полягати у виконанні таких кроків.
Крок 1. Установити: Open = {s}, Closed = ?.
Крок 2. Якщо Open = ?, то припинити виконання — шляху до цільового стану на графі не існує; у протилежному випадку — перейти до кроку 3.
Крок 3. Видалити зі списку Open вузол n, для якого f (n) < f (m) для будь-якого вузла m, що вже знаходиться у списку Open, і перенести його в список Closed.
Крок 4. Сформувати список чергових вузлів, у які можливий перехід з вузла n, і видалити з нього усі вузли, що утворять петлі; з кожним із вузлів, що залишилися, зв’язати покажчик на вузол n.
Крок 5. Якщо у сформованому списку чергових вузлів наявний вузол g, то завершити виконання і сформувати результат —
f-значення кожного вузла уздовж даного шляху найкращим f-значенням його дочірнього вузла. Завдяки цьому запам’ятовується f-значення найкращого листового вузла із забутого піддерева і тому в деякий наступний момент часу може бути прийнято рішення про те, чи варто знову розгортати це піддерево.
Крок 5.1. Обчислити f (n i ).
Крок 5.2. Якщо n i не є присутнім ані в списку Open, ані в списку Closed, то додати його в список Open, приєднати до нього оцінку f (n i ) і установити зворотний покажчик на вузол n.
Крок 5.3. Якщо n i вже присутній у списку Open або в списку Closed, то порівняти нове значення new = f (n i ) з колишнім old = f (n i ). Якщо old < new, то припинити обробку нового вузла. Якщо new < old, замінити новим вузлом колишній у списку, причому, якщо колишній вузол був у списку Closed, перенести його в список Open.
Крок 6. Перейти до кроку 2.
Усі методи А * є припустимими. Пошук А * є оптимальним за умови, що h(n) являє собою припустиму евристичну функцію, тобто за умови, що h(n) ніколи не переоцінює вартість досягнення мети.
Метод А * з ітеративним поглибленням (Iterative-Deepening А *
— IDA * ) створений для скорочення потреб у пам’яті для пошуку А * на основі ідеї ітеративного поглиблення в контексті евристичного пошуку. Основна розбіжність між IDA * і стандартним методом ітеративного поглиблення полягає в тому, що застосовуваною умовою зупинення розгортання слугує f-вартість (g + h), а не глибина; на кожній ітерації цим зупинним значенням є мінімальна f-вартість будь-якого вузла, що перевищує зупинне значення, досягнуте в попередній ітерації. Метод IDA * є практично застосовним для розв’язання багатьох задач з одиничними вартостями етапів і дозволяє уникнути істотних витрат, пов’язаних з підтримкою відсортованої черги вузлів.
Метод IDA * є трохи менш ефективним порівняно з методом RBFS. Обидва ці методи піддаються потенційному експонентному збільшенню складності, пов’язаної з пошуком у графах, оскільки вони не дозволяють визначати наявність повторюваних станів, відмінних від тих, котрі знаходяться в поточному шляху. Тому ці методи здатні багато разів досліджувати один і той самий стан. Методи IDA * та RBFS мають недолік, що в них використовується занадто мало пам’яті. Між ітераціями IDA * зберігає тільки одне — поточну межу f-вартості. RBFS зберігає в пам’яті більше інформації, але кількість використовуваної в ньому пам’яті вимірюється лише значенням Sk(bd): навіть якби було доступно більше пам’яті, RBFS не здатний нею скористатися.
шлях, породжений простежуванням покажчиків від вузла g до вузла s; у протилежному випадку для кожного чергового вузла n i , включеного в список, виконати таку послідовність операцій, що задається кроками 5.1—5.3.
7.3. Пошук асоціативних та секвенціальних закономірностей між пов’язаними подіями в базах знань
Асоціативні правила дозволяють виявляти закономірності між пов’язаними подіями і є одним з інструментів видобування знань з масивів даних.
Основною перевагою асоціативних правил є їх легке сприйняття людиною і проста інтерпретація мовами програмування. Проте вони не завжди корисні. Виокремлюють три види правил:
• корисні правила — містять дійсну інформацію, яка раніше була невідома, але має логічне пояснення. Такі правила можуть бути використані для ухвалення рішень, що приносять вигоду;
• тривіальні правила — містять дійсну і легко з’ясовну інформацію, котра уже відома. Такі правила, хоч і мають пояснення, але не можуть принести якої-небудь користі, оскільки відображають або відомі закони в досліджуваній галузі, або результати минулої діяльності. Іноді такі правила можуть використовуватися для перевірки виконання рішень, прийнятих на підставі попереднього аналізу;
• незрозумілі правила — містять інформацію, яка не може бути пояснена. Такі правила можуть бути одержані або на основі аномальних значень, або глибоко прихованих знань. Напряму такі правила не можна використовувати для ухвалення рішень, оскільки їх нез’ясовність може привести до непередбачуваних результатів. Для кращого розуміння потрібен додатковий аналіз.
Асоціативні правила будуються на основі частих наборів. Так, правила, побудовані на підставі набору T, є всіма можливими комбінаціями об’єктів, що входять у нього.
Розширеною транзакцією називається транзакція, розширена предками всіх елементів, що входять у цю транзакцію.
Нехай I = {i
1 , i
2 , ..., i m } — множина елементів, D — множина транзакцій, де кожна транзакція T — це набір елементів з I, T ? I. Кожна транзакція — це множина елементів (подій), що відбулися одночасно, і являє собою бінарний вектор, де t[k] = 1, якщо елемент i k присутній у транзакції, інакше t[k] = 0. Транзакція T містить X, певний набір елементів з I, якщо X ? T.
Перший метод пошуку асоціативних правил, що називався AIS, був розроблений у 1993 році співробітниками дослідницького центру IBM Almaden.одночасно, і являє собою бінарний вектор, де t[k] = 1, якщо елемент i k присутній у транзакції, інакше t[k] = 0. Транзакція T містить X, певний набір елементів з I, якщо X ? T.
Перший метод пошуку асоціативних правил, що називався AIS, був розроблений у 1993 році співробітниками дослідницького центру IBM Almaden.мент i k присутній у транзакції, інакше t[k] = 0. Транзакція T містить X, певний набір елементів з I, якщо X ? T.
Перший метод пошуку асоціативних правил, що називався AIS, був розроблений у 1993 році співробітниками дослідницького центру IBM Almaden.
Нехай I = {i
1 , i
2 , ..., i m } — множина елементів, D — множина транзакцій, де кожна транзакція T — це набір елементів з I, T ? I. Кожна транзакція — це множина елементів (подій), що відбулися одночасно, і являє собою бінарний вектор, де t[k] = 1, якщо елемент i k присутній у транзакції, інакше t[k] = 0. Транзакція T містить X, певний набір елементів з I, якщо X ? T.
Перший метод пошуку асоціативних правил, що називався AIS, був розроблений у 1993 році співробітниками дослідницького центру IBM Almaden.
Задача знаходження асоціативних правил розбивається на дві підзадачі.
1. Знаходження всіх наборів елементів, що задовольняють порогові minsupport. Ці набори елементів називаються такими, що часто зустрічаються.
2. Генерація правил зі знайдених наборів елементів з вірогідністю, що задовольняє порогові minconfidence.
Один із перших методів, які ефективно розв’язують подібний клас задач, — це метод Aрriori. Крім цього методу останнім часом було розроблено низку інших методів: DHP, Partition, DIC та ін.
Значення для параметрів minsupport та minconfidence вибираються так, щоб обмежити кількість знайдених правил. Якщо підтримка має велике значення, то методи будуть знаходити правила, добре відомі аналітикам або настільки очевидні, що немає ніякого сенсу проводити такий аналіз. З іншого боку, низьке значення підтримки веде до генерації величезної кількості правил, що, звичайно, потребує істотних обчислювальних ресурсів. Проте більшість цікавих правил знаходиться саме при низькому значенні порога підтримки. Хоча занадто низьке значення підтримки веде до генерації статистично необґрунтованих правил.
Пошук асоціативних правил — це зовсім не тривіальна задача, як може здатися на перший погляд. Одна з проблем — алгоритмічна складність при знаходженні наборів елементів, що часто зустрічаються, оскільки зі збільшенням числа елементів I експоненційно зростає число потенційних наборів елементів.
Узагальненим асоціативним правилом (generalized association вило X?Y узагальненим, тому що елементи, які входять у нього, можуть знаходитися на будь-якому рівні таксономії. Також будемо називати x предком x та x нащадком x.
rule) називається імплікація X?Y, де X?I, Y?I та X?Y=? і де жоден з елементів, що входять у набір Y, не є предком жодного елементу, що входить у X. Підтримка і вірогідність підраховуються так само, як і у випадку асоціативних правил. Ми називаємо праrule) називається імплікація X?Y, де X?I, Y?I та X?Y=? і де жоден з елементів, що входять у набір Y, не є предком жодного елементу, що входить у X. Підтримка і вірогідність підраховуються так само, як і у випадку асоціативних правил. Ми називаємо пра
Підтримкою (support) правила X?Y називається частка s, якщо
s % транзакцій з D, містять X ?Y, supp(X?Y) = supp (X?Y).
Відношення кількості транзакцій, до якої входить набір F, до загальної кількості транзакцій називається підтримкою (support) набору F і позначається Supp(F): D D FSupp F =)(.s % транзакцій з D, містять X ?Y, supp(X?Y) = supp (X?Y).
Відношення кількості транзакцій, до якої входить набір F, до загальної кількості транзакцій називається підтримкою (support) набору F і позначається Supp(F): D D FSupp F =)(.
min )(SuppFSupp>
Отже, при пошуку асоціативних правил вимагається знайти безліч усіх наборів великим значенням підтримки: {} min )(SuppFSuppFL>=. min )(SuppFSuppFL>=
Під час пошуку аналітик може вказати мінімальне значення підтримки його наборів, що цікавлять min Supp. Набір називається великим значенням підтримки (large itemset), якщо значення його підтримки більше мінімального значення, заданого користувачем: min )(SuppFSupp>.
Отже, при пошуку асоціативних правил вимагається знайти безліч усіх наборів великим значенням підтримки: {} min )(SuppFSuppFL>=.
При секвенціальному аналізі часто викликає інтерес послідовність подій, що відбуваються. При виявленні закономірностей у таких послідовностях можна з деякою часткою ймовірності передбачати появу подій у майбутньому, що дає змогу ухвалювати правильніші рішення.
Послідовністю називається впорядкована безліч об’єктів. Для цього на множині має бути задано відношення порядку.
Тоді послідовність об’єктів можна описати в такому вигляді:
Вважається, що транзакція Т містить послідовність S, якщо TS? і об’єкти, що входять в S, входять і в множину Т із збереженням відношення порядку. При цьому допускається, що в множині Т між об’єктами з послідовності S можуть знаходитися інші об’єкти.
Підтримкою послідовності S називається відношення кількості транзакцій, в яку входить послідовність S, до загальної кількості транзакцій. Послідовність є великого значення пітримки, якщо її підтримка перевищує мінімальну, задану користувачем: пошуку асоціативних правил є встановлення відношення порядку між об’єктами множини I. Дане відношення може бути визначено різними способами. При аналізі послідовності подій, що відбу-
Секвенціальний аналіз актуальний і для дослідження транзакцій у банкоматах. Основна проблема, для вирішення якої він використовується, — це аналіз даних про похибки на різних банкоматах платіжної мережі. Інформація про послідовність здійснення помилки може допомогти у виявленні неполадок і попередженні нових аварій.
В аналізі такої послідовності важливим є визначення інтервалу часу між збоями. Це дозволяє передбачити момент і характер нових збоїв, а отже, вжити профілактичних заходів. З цієї причини при аналізі даних інтерес викликає не просто послідовність подій, а збої, які відбуваються один за одним.
Основною відмінністю узагальнених асоціативних правил від асоціативних правил є те, що одержувані правила включають елементи, що є предками елементів, які входять у множину транзакцій. Ієрархією (таксономією) елементів називається ліс спрямованих ациклічних дерев, листами яких є елементи транзакцій, а внутрішніми вузлами — групи елементів.
Уведення додаткової інформації про групування елементів у вигляді ієрархії допомагає встановити асоціативні правила не тільки між окремими елементами, але й між різними рівнями ієрархії (групами).
Окремі елементи можуть мати недостатню підтримку, але в цілому група може задовольняти порогові minsupport (Supp min ). Це приводить до того, що раніше не виявлене потенційно цікаве правило, побудоване на елементах нижнього рівня ієрархії, може бути отримано, але його елементами будуть або елементи транзакції, або предки цих елементів.
