Лабораторная работа 1 По дисциплине: Технологии больших данных Тема: Ассоциативные правила Хилалов С. А. Группа: ип-19-6р Приняла: Тарасова Р. Н. Шымкент 2022 г
жүктеу/скачать 37.74 Kb.
|
- Бұл бет үшін навигация:
- ЛАБОРАТОРНАЯ РАБОТА 1
- Теоретические сведения
- Номер транзакции Наименование элемента Количество
|
МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РЕСПУБЛИКИ КАЗАХСТАН ЮЖНО-КАЗАХСТАНСКИЙ УНИВЕРСИТЕТ им. М.АУЕЗОВА Кафедра: «Вычислительная техника и программное обеспечение» ЛАБОРАТОРНАЯ РАБОТА 1 По дисциплине: Технологии больших данных Тема: Ассоциативные правила Выполнил: Хилалов С.А. Группа: ИП-19-6р Приняла: Тарасова Р.Н. Шымкент - 2022 г Теоретические сведения Apriori – один из наиболее популярных алгоритмов поиска ассоциативных правил. Благодаря использованию свойства анти-монотонности, он способен обрабатывать большие объемы данных за приемлемое время. Разбираем работу алгоритма и особенности его реализации. Современные базы данных имеют очень большие размеры, достигающие гига- и терабайтов, и тенденцию к дальнейшему увеличению. И поэтому, для нахождения ассоциативных правил требуются эффективные масштабируемые алгоритмы, позволяющие решить задачу за приемлемое время. Об одном из таких алгоритмов и пойдет речь в данной статье. Мы опишем алгоритм Apriori. Терминология и обозначения, которыми мы будем пользоваться, даны в статье «Введение в анализ ассоциативных правил». Для того чтобы было возможно применить алгоритм, необходимо провести предобработку данных: привести все данные к бинарному виду; изменить структуру данных.
Таблица 1. Обычный вид базы данных транзакций
Таблица 2. Нормализованный вид Количество столбцов в таблице равно количеству элементов, присутствующих во множестве транзакций DD. Каждая запись соответствует транзакции, где в соответствующем столбце стоит 1, если элемент присутствует в транзакции, и 0 — в противном случае. (см. Определение 1). Заметим, что исходный вид таблицы может быть отличным от приведенного в Таблице 1. Главное, чтобы данные были преобразованы к нормализованному виду, иначе алгоритм не применим. Все элементы таблицы упорядочены в алфавитном порядке (если это числа, они должны быть упорядочены в числовом порядке). Это сделано неслучайно. Итак, данные преобразованы, теперь можно приступить к описанию самого алгоритма. Как было сказано в предыдущей статье, такие алгоритмы работают в два этапа, не является исключением и рассматриваемый нами алгоритм Apriori. На первом шаге необходимо найти часто встречающиеся наборы элементов, а затем, на втором, извлечь из них правила. Количество элементов в наборе будем называть размером набора, а набор, состоящий из kk элементов, — kk-элементным набором. Свойство анти-монотонностиВыявление часто встречающихся наборов элементов — операция, требующая много вычислительных ресурсов и, соответственно, времени. Примитивный подход к решению данной задачи — простой перебор всех возможных наборов элементов. Это потребует O(^{|2I|})O(∣2I∣) операций, где |I|∣I∣ — количество элементов. Apriori использует одно из свойств поддержки, гласящее: поддержка любого набора элементов не может превышать минимальной поддержки любого из его подмножеств. Например, поддержка 3-элементного набора { Хлеб, Масло, Молоко } будет всегда меньше или равна поддержке 2-элементных наборов { Хлеб, Масло }, { Хлеб, Молоко }, { Масло, Молоко }. Дело в том, что любая транзакция, содержащая { Хлеб, Масло, Молоко }, также должна содержать { Хлеб, Масло }, { Хлеб, Молоко }, { Масло, Молоко }, причем обратное не верно. Это свойство носит название анти-монотонности и служит для снижения размерности пространства поиска. Не имей мы в наличии такого свойства, нахождение многоэлементных наборов было бы практически невыполнимой задачей в связи с экспоненциальным ростом вычислений. Свойству анти-монотонности можно дать и другую формулировку: с ростом размера набора элементов поддержка уменьшается, либо остается такой же. Из всего вышесказанного следует, что любой kk-элементный набор будет часто встречающимся тогда и только тогда, когда все его (k-1)(k−1)-элементные подмножества будут часто встречающимися. Все возможные наборы элементов из II можно представить в виде решетки, начинающейся с пустого множества, затем на 1 уровне — 1-элементные наборы, на 2-м — 2-элементные и т.д. На kk уровне представлены kk-элементные наборы, связанные со всеми своими (k-1)(k−1)-элементными подмножествами. Рассмотрим Рисунок 1, иллюстрирующий набор элементов II - {A, B, C, D}A,B,C,D. Предположим, что набор из элементов \{ A, B \}{A,B} имеет поддержку ниже заданного порога и, соответственно, не является часто встречающимся. Тогда, согласно свойству анти-монотонности, все его супермножества также не являются часто встречающимися и отбрасываются. Вся эта ветвь, начиная с \{ A, B \}{A,B}, выделена синим. Использование этой эвристики позволяет существенно сократить пространство поиска. жүктеу/скачать 37.74 Kb. Достарыңызбен бөлісу:
|