Методика пошуку асоціативних правил

Abstract

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

With the appearance of large volumes of stored information, the tasks related to the need of their processing become urgent. Artificial intelligence methods are used to analyze various kinds of data. Accumulating data is characterized by disordered and unstructured data when each storage unit cannot be represented by a finite number of features. In recent years, associative rule search methods have been widely used to process large arrays of unstructured data. The problem is that the number of possible associations with the increase of the number of items in each of the transactions increases exponentially and requires considerable computational cost. Therefore, in the process of associative rules formation, the techniques, which allow to reduce the number of associations that need to be analyzed, are widely used. The purpose of this work is to develop a methodology for finding associative rules based on preliminary analysis and compression of an array of transactions representing different subject sets. The paper proposes an approach to the formation of a sample of items most characteristic for a simplified array of transactions, on the basis of which associative binary relations are formed and their characteristics are calculated to determine whether such relations are rules. To do this, the array is first compressed by searching for transactions with the same subject sets using an equivalence relation. Then, to detect transactions with recurring items, a pairwise intersection of the subject sets is performed. At the initial stage of formation, the transaction database is an array of disordered data that needs to be structured and classified by the number of subject sets. As a result of research, the paper offers a method of finding associative rules, which are based on the procedures of "compressing" the original array of transactions to their entry in the database