Алгоритмы поиска ассоциативных правил — это методы обучения машин на основе правил обнаружения интересующих пользователя связей среди переменных в большой базе данных.
Введение.
Сегодня очень большое внимание уделяется методикам «обнаружения знаний» в базах данных. Современные базы данных обладают просто гигантскими размерами, которые могут достигать Гига и Терабайтов. И существует тенденция к их дальнейшему росту, что определяет потребность в формировании эффективных масштабируемых алгоритмов, которые позволяют решить поставленные задачи за разумный период времени. Одним из наиболее известных методов обнаружения знаний являются алгоритмы ассоциативных правил, позволяющие найти различного рода закономерности.
Ассоциациями является выявление закономерностей среди взаимосвязанных событий. В качестве примера такой закономерности можно привести правило, которое указывает, что из события X следует событие Y. Такой тип правил носит название ассоциативных.
Сущность задачи состоит в определении часто встречающейся совокупности объектов в значительном множестве таких совокупностей. Такая задача может считаться как частный случай задачи классификации. Изначально ее решали при выполнении анализа тенденций в действиях покупателей в супермаркетах. Анализу должна была подвергаться информация об осуществляемых покупках, которые клиенты супермаркета кладут в корзину. Это явилось причиной появления еще одного популярного названия, а именно, анализ рыночных корзин.
Итоговые результаты, которые были получены при помощи анализа рыночной корзины, предоставляют возможность оптимизации ассортимента товаров и товарных запасов, увеличения объемов продаж за счет предложения покупателям сопутствующих товаров, а также способны влиять на расположение их в презентационном блоке информационного портала. К примеру, когда по итогам анализа было выявлено, что совместная покупка макарон и кетчупа представляет собой типичный шаблон, то, если разместить данные товары на едином уровне просмотра, можно «спровоцировать» клиента на их совместную покупку.
При выполнении анализа подобной информации интерес, в первую очередь, имеют данные о том, какие именно товары предпочитают и в какие временные периоды различные группы покупателей. Эти информационные данные могут позволить наиболее эффективно спланировать закупку товаров, проведение рекламных кампаний, а также сэкономить время.
Алгоритмы поиска ассоциативных правил
Самой распространенной задачей анализа данных считается нахождение часто встречающейся совокупности объектов в большом наборе таких совокупностей. Решение проблемы определения ассоциативных правил, как и в любых других задачах, может быть сведено к обработке начальных данных и выработке итоговых результатов. Результаты, которые получаются при решении такой задачи, обычно, представляются в форме ассоциативных правил. По этой причине в их поиске следует выделить следующие этапы:
- Поиск всех частых совокупностей объектов.
- Выработка ассоциативных правил из выявленных частых наборов объектов.
Часто организации накапливают значительные информационные объемы из каждодневных операций. К примеру, большим количеством информационных данных, собираемых каждодневно в кассах, могут считаться данные о покупках, совершаемых клиентами. Таблица, приведенная ниже, является примером таких данных, известных как анализ рыночной корзины.
Рисунок 1. Таблица. Автор24 — интернет-биржа студенческих работ
Все строки в этой таблице соответствуют транзакциям, которые содержат уникальный идентификатор TID и набор компонентов, приобретенных этим клиентом. Торгующая организация заинтересована в анализе этой информации, так как анализ способен оказать помощь в определении покупательского поведения своих клиентов. Подобную очень ценную информацию можно использовать для поддержки разных бизнес-приложений, таких как рыночное развитие, управление товарами и взаимоотношениями с клиентами.
Это все является анализом ассоциаций, которые предоставляют возможность обнаружения интересных взаимоотношений, скрытых в значительных по объемам выборках информационных данных. Найденные отношения можно представить в форме ассоциативных правил или наборов часто применяемых компонентов. К примеру, такое правило можно вывести из набора данных, изображенных в таблице выше:
{} Молоко → {} хлеб
Данное правило показывает, что присутствует тесная взаимная связь между продажами молока и хлеба. То есть, есть много клиентов, покупающих молоко, которые также приобретают и хлеб. Торгующие организации могут применять данный вид правил для нахождения новых возможностей в продаже своей продукции покупателям.
Кроме информации из потребительской корзины, ассоциативный анализ может использоваться также и в других сферах, таких как, биологическая информатика, медицинская диагностика, Web-mining и научный анализ данных. К примеру, при выполнении анализа данных планеты Земля, ассоциативная модель способна выявить существующие связи между океанами, земной поверхностью и процессами, происходящими в атмосфере. Подобная информация способна оказать помощь специалистам в лучшем понимании того, как разные компоненты планеты Земля могут взаимодействовать друг с другом.
Современные информационные базы данных обладают очень большими размерами, и поэтому, для определения ассоциативных правил необходимы эффективные масштабируемые алгоритмы, которые позволяют решить задачу за приемлемый отрезок времени. Одним из таких алгоритмов считается алгоритм Apriori. Для практического использования данного алгоритма, следует выполнить следующую предварительную обработку данных:
- Преобразовать все информационные данные в бинарный формат.
- Осуществить изменение структуры данных.
