Метод Apriori для поиска связей между переменными в большой базе данных | Статья в журнале «Молодой ученый»

Отправьте статью сегодня! Журнал выйдет 18 июля, печатный экземпляр отправим 22 июля.

Опубликовать статью в журнале

Автор:

Рубрика: Информационные технологии

Опубликовано в Молодой учёный №21 (311) май 2020 г.

Дата публикации: 25.05.2020

Статья просмотрена: 9 раз

Библиографическое описание:

Афанасьев, А. И. Метод Apriori для поиска связей между переменными в большой базе данных / А. И. Афанасьев. — Текст : непосредственный // Молодой ученый. — 2020. — № 21 (311). — С. 41-44. — URL: https://moluch.ru/archive/311/70549/ (дата обращения: 09.07.2020).



В статье автором рассматривается метод Apriori для поиска ассоциативных правил между переменными в большой базе данных

Ключевые слова: база данных, набор элементов, Apriori, набор, правило, транзакция.

Связи — это очень важная тема для понимания при проектировании базы данных. Современные базы данных очень большие, достигают ГБ и терабайт и имеют тенденцию к дальнейшему увеличению. Поэтому для нахождения ассоциативных правил требуются эффективные масштабируемые алгоритмы, которые позволяют решить проблему за разумное время. Один из таких алгоритмов будет обсуждаться в этой статье. Опишем алгоритм Apriori.

Данный алгоритм использует широкую стратегию поиска для подсчета объектов и использует функцию генерации кандидатов на основе свойств поддержки нисходящей линии связи. Он ищет ассоциативные правила и применяется к базам данных, которые содержат огромное количество транзакций. Изучение ассоциативных правил — это метод, используемый в интеллектуальном анализе данных для изучения взаимосвязи между переменными базы данных.

Вот пример использования алгоритма Apriori. Допустим, у нас есть база данных о транзакциях в супермаркетах. Вы можете рассматривать базу данных как огромную таблицу, в которой каждая строка представляет собой номер транзакции, а каждый столбец — отдельную покупку [4]. Проиллюстрируем это на рис. 1.

Рис. 1. База данных транзакций супермаркета

С помощью алгоритма Apriori мы можем идентифицировать приобретенные продукты, то есть устанавливать ассоциативные правила.

Что это дает нам:

Вы можете определить продукты, которые часто покупаются вместе. Основная задача маркетинга — заставить клиентов покупать больше. Сопутствующие товары называются наборами. Пример:

Вы можете заметить, что чипсы, чипсы с соусом и сода часто стоят на прилавках поблизости. Это называется двухэлементным набором. Когда база данных достаточно велика, будет гораздо сложнее «увидеть» взаимосвязь, особенно при работе с трехэлементными или более крупными наборами. Для этого был создан алгоритм Apriori.

Как работает алгоритм Apriori? Прежде чем перейти к сути алгоритма, необходимо определить 3 параметра [1]:

  1. Сначала необходимо установить заданный размер. Хотите определить двухэлементный, трехэлементный набор или любой другой?
  2. Во-вторых, поддержка коммутатора — это количество транзакций, включенных в сумму, деленное на общее количество транзакций. Набор для немедленной поддержки — самая распространенная тенденция.
  3. В-третьих, определите надежность, то есть условную вероятность того, что конкретный товар окажется в корзине с другими товарами. Пример: фишки в вашем наборе с вероятностью 67 % окажутся в одной корзине с газировкой.

Простой алгоритм Apriori состоит из трех этапов:

  1. Ассоциация. Посмотрите на базу данных и определите частоту отдельных продуктов.
  2. Отсечение. Настройки, которые удовлетворяют поддержке и надежности, переходят к следующей итерации с двухкомпонентными наборами,
  3. Повторение. Предыдущие два шага повторяются для каждого заданного значения, пока не будет получен ранее определенный размер.

Если говорить о переменных — это то, что можно измерить, контролировать или манипулировать в исследованиях (от английского корня 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 с.

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


Ключевые слова

база данных, транзакция, правило, набор, набор элементов, Apriori

Похожие статьи

Организация сбора технологических данных с буровой и передачи...

Набор данных не должен иметь элементов, данных более чем из одного типа записи. Один и тот же элемент данных не должен повторяться в одном и том же наборе данных. Если это не оговорено отдельно, элемент данных с признаком отсутствия значения -9999.0 не требует...

Анализ поисковых алгоритмов при решении задач идентификации...

База данных; расстояние Хемминга; сравнение строк; расстояние Левенштейна; метод расширенной выборки; сигнатурный алгоритм; метод N-gram; алгоритм последовательного перебора; деревья поиска; поиск данных.

Основы разработки баз данных реального времени

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

Концепция базы данных для системы электронного...

Рис. 2. Физическая ER-модель базы данных. Задачей базы данных будет заполнение таблицы HISTORY и построение пути документа с учетом типов документов и загруженности сотрудников. Алгоритм заполнения таблицы: 1) Определение статуса документа, завершен документ или нет.

Обзор методов формирования баз знаний | Статья в сборнике...

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

Использование современных СУБД в информационных системах...

СУБД работает с базами данных, построенными по определенным принципам.

Системы управления базами данных по типу управляемой БД

Реляционная модель некоторой предметной области представляет собой набор отношений, изменяющихся во времени.

Обнаружение последовательностных паттернов в событиях...

База данных — бинарный файл, состоящий из целых чисел. Каждая строка представляет из себя одну последовательность. Положительные числа представляют из себя элементы последовательности. Число «-1» является разделителем набора элементов, а число...

Организация базы данных в автоматизированных системах

Основные составные элементы банка данныхбаза данных и система управления базой данных.

Для обозначения объектов базы данных используются следующие термины: – элемент данных — наименьшая единица данных, представляющая конкретное значение

Интеллектуализация базы знаний систем Service Desk

База знаний это некий набор правил необходимый для корректной работы системы, требующий регулярного обновления.

- процесс обработки данных в информацию и получения знаний для принятия решений. Data sources — источники данных для базы данных (БД).

Технология ADO и средства доступа к реляционным базам данных

Коротко на вопрос «Что такое ADO?» можно ответить так: это основная технология доступа к данным, не только реляционные базы данных для платформы.NET. Более конкретно — это набор объектов...

Похожие статьи

Организация сбора технологических данных с буровой и передачи...

Набор данных не должен иметь элементов, данных более чем из одного типа записи. Один и тот же элемент данных не должен повторяться в одном и том же наборе данных. Если это не оговорено отдельно, элемент данных с признаком отсутствия значения -9999.0 не требует...

Анализ поисковых алгоритмов при решении задач идентификации...

База данных; расстояние Хемминга; сравнение строк; расстояние Левенштейна; метод расширенной выборки; сигнатурный алгоритм; метод N-gram; алгоритм последовательного перебора; деревья поиска; поиск данных.

Основы разработки баз данных реального времени

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

Концепция базы данных для системы электронного...

Рис. 2. Физическая ER-модель базы данных. Задачей базы данных будет заполнение таблицы HISTORY и построение пути документа с учетом типов документов и загруженности сотрудников. Алгоритм заполнения таблицы: 1) Определение статуса документа, завершен документ или нет.

Обзор методов формирования баз знаний | Статья в сборнике...

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

Использование современных СУБД в информационных системах...

СУБД работает с базами данных, построенными по определенным принципам.

Системы управления базами данных по типу управляемой БД

Реляционная модель некоторой предметной области представляет собой набор отношений, изменяющихся во времени.

Обнаружение последовательностных паттернов в событиях...

База данных — бинарный файл, состоящий из целых чисел. Каждая строка представляет из себя одну последовательность. Положительные числа представляют из себя элементы последовательности. Число «-1» является разделителем набора элементов, а число...

Организация базы данных в автоматизированных системах

Основные составные элементы банка данныхбаза данных и система управления базой данных.

Для обозначения объектов базы данных используются следующие термины: – элемент данных — наименьшая единица данных, представляющая конкретное значение

Интеллектуализация базы знаний систем Service Desk

База знаний это некий набор правил необходимый для корректной работы системы, требующий регулярного обновления.

- процесс обработки данных в информацию и получения знаний для принятия решений. Data sources — источники данных для базы данных (БД).

Технология ADO и средства доступа к реляционным базам данных

Коротко на вопрос «Что такое ADO?» можно ответить так: это основная технология доступа к данным, не только реляционные базы данных для платформы.NET. Более конкретно — это набор объектов...

Задать вопрос