В статье автором рассматривается метод Apriori для поиска ассоциативных правил между переменными в большой базе данных
Ключевые слова: база данных, набор элементов, Apriori, набор, правило, транзакция.
Связи — это очень важная тема для понимания при проектировании базы данных. Современные базы данных очень большие, достигают ГБ и терабайт и имеют тенденцию к дальнейшему увеличению. Поэтому для нахождения ассоциативных правил требуются эффективные масштабируемые алгоритмы, которые позволяют решить проблему за разумное время. Один из таких алгоритмов будет обсуждаться в этой статье. Опишем алгоритм Apriori.
Данный алгоритм использует широкую стратегию поиска для подсчета объектов и использует функцию генерации кандидатов на основе свойств поддержки нисходящей линии связи. Он ищет ассоциативные правила и применяется к базам данных, которые содержат огромное количество транзакций. Изучение ассоциативных правил — это метод, используемый в интеллектуальном анализе данных для изучения взаимосвязи между переменными базы данных.
Вот пример использования алгоритма Apriori. Допустим, у нас есть база данных о транзакциях в супермаркетах. Вы можете рассматривать базу данных как огромную таблицу, в которой каждая строка представляет собой номер транзакции, а каждый столбец — отдельную покупку [4]. Проиллюстрируем это на рис. 1.
Рис. 1. База данных транзакций супермаркета
С помощью алгоритма Apriori мы можем идентифицировать приобретенные продукты, то есть устанавливать ассоциативные правила.
Что это дает нам:
Вы можете определить продукты, которые часто покупаются вместе. Основная задача маркетинга — заставить клиентов покупать больше. Сопутствующие товары называются наборами. Пример:
Вы можете заметить, что чипсы, чипсы с соусом и сода часто стоят на прилавках поблизости. Это называется двухэлементным набором. Когда база данных достаточно велика, будет гораздо сложнее «увидеть» взаимосвязь, особенно при работе с трехэлементными или более крупными наборами. Для этого был создан алгоритм Apriori.
Как работает алгоритм Apriori? Прежде чем перейти к сути алгоритма, необходимо определить 3 параметра [1]:
- Сначала необходимо установить заданный размер. Хотите определить двухэлементный, трехэлементный набор или любой другой?
- Во-вторых, поддержка коммутатора — это количество транзакций, включенных в сумму, деленное на общее количество транзакций. Набор для немедленной поддержки — самая распространенная тенденция.
- В-третьих, определите надежность, то есть условную вероятность того, что конкретный товар окажется в корзине с другими товарами. Пример: фишки в вашем наборе с вероятностью 67 % окажутся в одной корзине с газировкой.
Простой алгоритм Apriori состоит из трех этапов:
- Ассоциация. Посмотрите на базу данных и определите частоту отдельных продуктов.
- Отсечение. Настройки, которые удовлетворяют поддержке и надежности, переходят к следующей итерации с двухкомпонентными наборами,
- Повторение. Предыдущие два шага повторяются для каждого заданного значения, пока не будет получен ранее определенный размер.
Если говорить о переменных — это то, что можно измерить, контролировать или манипулировать в исследованиях (от английского корня var).Переменные очень разные по своим свойствам переменные, и, следовательно, мы можем сказать, что эти переменные отличаются по характеристикам, особенно от роли, которую они играют в исследованиях, типу измерений и т. д.
Но вернемся к Apriori, который обычно рассматривается как алгоритм самообучения, поэтому его часто используют для поиска интересных закономерностей и отношений. Это модификация алгоритма Apriori, которая может классифицировать отмеченные данные. Кстати, Apriori прост, понятен в реализации и имеет множество модификаций. При этом алгоритм может быть довольно ресурсоемким- его расчеты могут занять много времени. Имеется огромное количество реализаций данного алгоритма и одни из самых популярных это ARtool, Weka и Orange.
Apriori — один из самых популярных алгоритмов поиска ассоциативных правил. Благодаря использованию антимонотонных свойств можно обрабатывать большие объемы данных в разумные сроки. Чтобы применить этот алгоритм, необходимо обработать данные: обратить внимание на все данные в двоичном виде; изменить структуру данных (табл.1–2) [5].
Таблица 1
Обычный вид базы данных транзакций
|
Номер транзакции |
Наименование элемента |
Количество |
|
1001 |
А |
2 |
|
1001 |
D |
3 |
|
1001 |
E |
1 |
|
1002 |
А |
2 |
|
1002 |
F |
1 |
|
1003 |
B |
2 |
|
1003 |
А |
2 |
|
1003 |
C |
2 |
|
... |
... |
... |
Таблица 2
Нормализованный вид
|
TID |
A |
B |
C |
D |
E |
F |
G |
H |
I |
K |
... |
|
1001 |
1 |
0 |
0 |
1 |
1 |
0 |
0 |
0 |
0 |
0 |
... |
|
1002 |
1 |
0 |
0 |
0 |
0 |
1 |
0 |
0 |
0 |
0 |
... |
|
1003 |
1 |
1 |
1 |
0 |
0 |
0 |
0 |
0 |
1 |
0 |
... |
Количество столбцов в таблице равно количеству элементов, присутствующих в большом количестве транзакций. Обратите внимание, что первоначальная форма таблицы не может быть описана в таблице 1. Главное, чтобы данные были преобразованы в стандартизированное представление, в противном случае применяется алгоритм. Все элементы этой таблицы расположены в алфавитном порядке (если они являются числами, они должны быть расположены в числовом порядке). Это не случайно.
Итак, данные преобразованы, теперь можно приступить к описанию алгоритма. Алгоритмы работают в два этапа, и проанализированный алгоритм Apriori не является исключением. На первом этапе нужно найти общие наборы элементов, а затем извлечь из них правила. Количество элементов в наборе будет называться размером набора, а количество, состоящее из k элементов — набором k-элементов [2].
Обнаружение общих наборов элементов — это операция, которая требует много вычислительных ресурсов и, следовательно, времени. Примитивный подход к решению этой проблемы — это простой поиск всех возможных наборов элементов. Apriori использует одно из свойств поддержки, что любой набор элементов не может превышать минимальную поддержку любого из его подмножеств.
Например, поддержка трехэлементного набора { Хлеб, Масло, Молоко } будет всегда меньше или равна поддержке 2-элементных наборов { Хлеб, Масло }, { Хлеб, Молоко }, { Масло, Молоко }. Дело в том, что любая транзакция, содержащая { Хлеб, Масло, Молоко }, также должна содержать { Хлеб, Масло }, { Хлеб, Молоко }, { Масло, Молоко }, причем обратное не верно. Это свойство называется анти-монотонностью и служит для уменьшения размерности пространства поиска. Если у нас нет такого свойства, поиск компонентов может быть практически невозможен.
Вот функция генерации кандидатов. На этот раз нет необходимости снова обращаться к базе данных. Чтобы получить наборы k-элементов, мы используем (k-1) (k-1) — наборы элементов, которые были определены на предыдущем шаге и являются общими. Напомним, что наш начальный набор хранится в упорядоченном виде. Поколение кандидатов также будет состоять из двух этапов. Каждый кандидат k будет создан путем расширения общего набора размеров (k-1) (k-1) путем добавления элемента другого (k-1) (k-1) — набора элементов. Основываясь на свойстве анти-монотонности, все наборы k должны быть удалены, если хотя бы одно из (k-1) (k-1) подмножеств не является общим. После генерации кандидатов следующая задача — рассчитать поддержку каждого кандидата [3].
Гораздо быстрее и эффективнее использовать подход, основанный на хранении кандидатов в хэш-дереве. Внутренние узлы дерева содержат хеш-таблицы с сообщениями потомкам, а страницы — кандидатам. Дерево нам пригодится для быстрого расчета поддержки кандидатов. Хэш-дерево создается каждый раз, когда формируются кандидаты. Как только число кандидатов становится больше порогового значения, корень становится хеш-таблицей, то есть становится внутренним узлом, и для него создаются потомки. И все примеры распространяются на узлы-потомки в соответствии со значениями хеш-функции элементов, включенных в набор, и т. Д. Каждый новый кандидат хэшируется на внутренних узлах, пока не достигнет страницы первого узла, где он будет храниться до числа из наборов снова превышать порог.
Создано хеш-дерево с наборами кандидатов, теперь с хеш-деревом легко рассчитать поддержку для каждого кандидата. Для этого вам нужно «пропустить» каждую транзакцию через дерево и увеличить счетчики для тех кандидатов, элементы которых также содержатся в транзакции.
Затем на втором уровне хэш-функция применяется ко вторым элементам и т. д. На k-уровне k-элемент отключается.
После того, как каждая транзакция исходной базы данных «пропущена» через дерево, вы можете проверить, соответствуют ли значения поддержки кандидата минимальному порогу. Кандидаты, для которых выполняется условие, переводятся в общую категорию. Кроме того, мы должны помнить о поддержке набора, это будет полезно для нас, когда вы получите правила. Эти же шаги используются для поиска (k + 1) (k + 1) наборов элементов и т. д.
Как только вы нашли все обычные наборы элементов, вы можете приступить к генерации правил. Извлечение правил — менее трудоемкая задача. Во-первых, чтобы рассчитать действительность правила, достаточно знать поддержку самого курса и сумму, которая лежит в терминах правила. Обратите внимание, что числитель остается постоянным. Тогда допустимость имеет минимальное значение, если знаменатель имеет максимальное значение, и это происходит, когда условием правила является набор, состоящий из одного элемента. Все надмножества этого набора имеют меньшую или равную поддержку и соответственно большую надежность. Это свойство можно использовать при извлечении правил [3].
Если мы начинаем извлекать правила, сначала рассматривая только один элемент в условии правила, и это правило имеет необходимую поддержку, то все правила, где условия являются надмножествами элемента, также имеют значение надежности выше заданного порога. Рекурсивная процедура используется для извлечения всех правил.
Литература:
1. Голицына О. Л. Базы данных. — М.: Форум, 2016. — 400 c.
2. Илюшечкин В. М. Основы использования и проектирования баз данных. — М.: Юрайт, 2016. — 516 c.
3. Кнут Д. Искусство программирования. Т. З. Сортировка и поиск. — М.: Издательский дом «Вильямс», 2019–801 с.
4. Макконнелл Дж. Основы современных алгоритмов. 2-е дополненное издание / Пер. с англ. под ред. С. К. Ландо, дополнение М. В. Ульянова. — М.: Техносфера, 2016. — 368 с.
5. Угринович Н. Д. Информатика. — М.: БИНОМ, 2018. — 183 с.
