Вы точно человек?
Выявление обобщенных ассоциативных правил - описание алгоритма
Алгоритмы ассоциативных правил
Первый алгоритм поиска ассоциативных правил , называвшийся AIS [62], предложенный Agrawal, Imielinski and Swami был разработан сотрудниками исследовательского центра IBM Almaden в году. С этой работы начался интерес к ассоциативным правилам ; на середину х годов прошлого века пришелся пик исследовательских работ в этой области, и с тех пор каждый год появляется несколько новых алгоритмов. В алгоритме AIS кандидаты множества наборов генерируются и подсчитываются "на лету", во время сканирования базы данных. Создание этого алгоритма было мотивировано желанием использовать язык SQL для вычисления часто встречающихся наборов товаров. Как и алгоритм AIS , SETM также формирует кандидатов "на лету", основываясь на преобразованиях базы данных. Чтобы использовать стандартную операцию объединения языка SQL для формирования кандидата, SETM отделяет формирование кандидата от их подсчета. Неудобство алгоритмов AIS и SETM - излишнее генерирование и подсчет слишком многих кандидатов, которые в результате не оказываются часто встречающимися. Для улучшения их работы был предложен алгоритм Apriori [63]. Работа данного алгоритма состоит из нескольких этапов, каждый из этапов состоит из следующих шагов:. Формирование кандидатов candidate generation - этап, на котором алгоритм , сканируя базу данных, создает множество i-элементных кандидатов i - номер этапа. На этом этапе поддержка кандидатов не рассчитывается. Подсчет кандидатов candidate counting - этап, на котором вычисляется поддержка каждого i-элементного кандидата. Оставшиеся i-элементные наборы называем часто встречающимися. Рассмотрим работу алгоритма Apriori на примере базы данных D. Иллюстрация работы алгоритма приведена на рис. Минимальный уровень поддержки равен 3. На первом этапе происходит формирование одноэлементных кандидатов. Далее алгоритм подсчитывает поддержку одноэлементных наборов. Наборы с уровнем поддержки меньше установленного, то есть 3, отсекаются. В нашем примере это наборы e и f, которые имеют поддержку , равную 1. Оставшиеся наборы товаров считаются часто встречающимися одноэлементными наборами товаров: Далее происходит формирование двухэлементных кандидатов, подсчет их поддержки и отсечение наборов с уровнем поддержки , меньшим 3. Оставшиеся двухэлементные наборы товаров, считающиеся часто встречающимися двухэлементными наборами ab, ac, bd, принимают участие в дальнейшей работе алгоритма. Если смотреть на работу алгоритма прямолинейно, на последнем этапе алгоритм формирует трехэлементные наборы товаров: Набор товаров abc может быть назван часто встречающимся. Однако алгоритм Apriori уменьшает количество кандидатов, отсекая - априори - тех, которые заведомо не могут стать часто встречающимися, на основе информации об отсеченных кандидатах на предыдущих этапах работы алгоритма. Отсечение кандидатов происходит на основе предположения о том, что у часто встречающегося набора товаров все подмножества должны быть часто встречающимися. Если в наборе находится подмножество , которое на предыдущем этапе было определено как нечасто встречающееся, этот кандидат уже не включается в формирование и подсчет кандидатов. Так наборы товаров ad, bc, cd были отброшены как нечасто встречающиеся, алгоритм не рассматривал набор товаров abd, bcd , acd. При рассмотрении этих наборов формирование трехэлементных кандидатов происходило бы по схеме, приведенной в верхнем пунктирном прямоугольнике. Поскольку алгоритм априори отбросил заведомо нечасто встречающиеся наборы, последний этап алгоритма сразу определил набор abc как единственный трехэлементный часто встречающийся набор этап приведен в нижнем пунктирном прямоугольнике. Алгоритм Apriori рассчитывает также поддержку наборов, которые не могут быть отсечены априори. Это так называемая негативная область negative border , к ней принадлежат наборы-кандидаты, которые встречаются редко, их самих нельзя отнести к часто встречающимся, но все подмножества данных наборов являются часто встречающимися. При текущей загрузке на смогу ежедневно уделять изучению курса указанное в темах время. Возможно ли изучение в персональном темпе? Есть ли ограничения на сроки? Мы ищем курсы, покупаем и публикуем их для вас бесплатно. Учеба Академии Учителя Рейтинг Вопросы Магазин. Курсы Школа Высшее образование Мини-МБА Профессиональная переподготовка Повышение квалификации Сертификации. Информация Глоссарий Дипломы Вопросы и ответы Студенты Рейтинг выпускников Мнения Литература Учебные программы. Методы поиска ассоциативных правил. Методы поиска ассоциативных правил Алгоритм AIS. Можно ли пересдать экзамен? Пользовательское соглашение Политика конфиденциальности Реклама на сайте Напишите нам.
В результате такого видеоанализа устанавливаем закономерность следующего вида: Понятие поддержки набора уже рассмотрели. Существует понятие поддержки правила. Достоверность правила показывает, какова вероятность того, что из события A следует событие B. Рассмотрим границы поддержки и достоверности ассоциативного правила. Однако в большинстве случаев, количество правил необходимо ограничивать заранее установленными минимальными и максимальными значениями поддержки и достоверности. Если значение поддержки правила слишком велико, то в результате работы алгоритма будут найдены правила очевидные и хорошо известные. Слишком низкое значение поддержки приведет к нахождению очень большого количества правил, которые, возможно, будут в большей части необоснованными, но не известными и не очевидными для аналитика. Если уровень достоверности слишком мал, то ценность правила вызывает серьезные сомнения. На сегодняшний день существует большое количество методов поиска ассоциативных правил в разных источниках данных. Основными являются методы AIS и SETM. Рассмотрим более подробно каждый из этих методов. Первый алгоритм поиска ассоциативных правил, называвшийся AIS, предложенный Agrawal, Imielinski and Swami был разработан сотрудниками исследовательского центра IBM Almaden в году. С этой работы начался интерес к ассоциативным правилам; на середину х годов прошлого века пришелся пик исследовательских работ в этой области, и с тех пор каждый год появляется несколько новых алгоритмов [14—16]. Каждая транзакция проверяется на наличие больших наборов, выявленных при предыдущем проходе. Соответственно, новые наборы формируются путем расширения имеющихся наборов. Этот алгоритм неэффективен, поскольку генерирует и учитывает слишком много наборов-кандидатов, которые недостаточно большие нечастые. Создание этого алгоритма было мотивировано желанием использовать язык SQL для вычисления часто встречающихся наборов товаров. Чтобы использовать стандартную операцию объединения языка SQL для формирования кандидата, SETM отделяет формирование кандидата от их подсчета [14—16]. Для улучшения их работы был предложен алгоритм Apriori. Работа данного алгоритма состоит из нескольких этапов, каждый из этапов состоит из следующих шагов:. На этом этапе поддержка кандидатов не рассчитывается. Оставшиеся i -элементные наборы называем часто встречающимися. Рассмотрим работу алгоритма Apriori на примере базы данных D. Иллюстрация работы алгоритма приведена на рисунке 2. Минимальный уровень поддержки равен 3. На первом этапе происходит формирование одноэлементных кандидатов. Далее алгоритм подсчитывает поддержку одноэлементных наборов. Наборы с уровнем поддержки меньше установленного, то есть 3, отсекаются. В нашем примере это наборы e и f , которые имеют поддержку, равную 1. Оставшиеся наборы товаров считаются часто встречающимися одноэлементными наборами товаров: Далее происходит формирование двухэлементных кандидатов, подсчет их поддержки и отсечение наборов с уровнем поддержки, меньшим 3. Оставшиеся двухэлементные наборы товаров, считающиеся часто встречающимися двухэлементными наборами ab, ac, bd , принимают участие в дальнейшей работе алгоритма. Если смотреть на работу алгоритма прямолинейно, на последнем этапе алгоритм формирует трехэлементные наборы товаров: Набор товаров abc может быть назван часто встречающимся. Отсечение кандидатов происходит на основе предположения о том, что у часто встречающегося набора товаров все подмножества должны быть часто встречающимися. Если в наборе находится подмножество, которое на предыдущем этапе было определено как нечасто встречающееся, этот кандидат уже не включается в формирование и подсчет кандидатов. Так наборы товаров ad, bc, cd были отброшены как нечасто встречающиеся, алгоритм не рассматривал товаров abd, bcd, acd. При рассмотрении этих наборов формирование трехэлементных кандидатов происходило бы по схеме, приведенной в верхнем пунктирном прямоугольнике. Поскольку алгоритм априори отбросил заведомо нечасто встречающиеся наборы, последний этап алгоритма сразу определил набор abc как единственный трехэлементный часто встречающийся набор этап приведен в нижнем пунктирном прямоугольнике. Алгоритм Apriori рассчитывает также поддержку наборов, которые не могут быть отсечены априори. Это так называемая негативная область negative border , к ней принадлежат наборы-кандидаты, которые встречаются редко, их самих нельзя отнести к часто встречающимся, но все подмножества данных наборов являются часто встречающимися. В зависимости от размера самого длинного часто встречающегося набора алгоритм Apriori сканирует базу данных определенное количество раз. Разновидности алгоритма Apriori, являющиеся его оптимизацией, предложены для сокращения количества сканирований базы данных, количества наборов-кандидатов или того и другого. Были предложены следующие разновидности алгоритма Apriori: AprioriTID и AprioriHybrid [14—16]. С этой целью используется кодирование кандидатов, выполненное на предыдущих проходах. В последующих проходах размер закодированных наборов может быть намного меньше, чем база данных, и таким образом экономятся значительные ресурсы. Анализ времени работы алгоритмов Apriori и AprioriTid показывает, что в более ранних проходах Apriori добивается большего успеха, чем AprioriTid; однако AprioriTid работает лучше Apriori в более поздних проходах. Кроме того, они используют одну и ту же процедуру формирования наборов-кандидатов. Основанный на этом наблюдении, алгоритм AprioriHybrid предложен, чтобы объединить лучшие свойства алгоритмов Apriori и AprioriTid. AprioriHybrid использует алгоритм Apriori в начальных проходах и переходит к алгоритму AprioriTid, когда ожидается, что закодированный набор первоначального множества в конце прохода будет соответствовать возможностям памяти. Однако, переключение от Apriori до AprioriTid требует вовлечения дополнительных ресурсов. Некоторыми авторами были предложены другие алгоритмы поиска ассоциативных правил, целью которых также было усовершенствование алгоритма Apriori. Кратко изложим суть нескольких, для более подробной информации можно рекомендовать [14—16]. Сокращение обеспечивается за счет того, что каждый из k -элементных наборов-кандидатов помимо шага сокращения проходит шаг хеширования. В алгоритме на k-1 этапе во время выбора кандидата создается так называемая хеш-таблица. Каждая запись хеш-таблицы является счетчиком всех поддержек k -элементных наборов, которые соответствуют этой записи в хеш-таблице. Алгоритм использует эту информацию на этапе k для сокращения множества k -элементных наборов-кандидатов. После сокращения подмножества, как это происходит в Apriori, алгоритм может удалить набор-кандидат, если его значение в хеш-таблице меньше порогового значения, установленного для обеспечения [14—16]. К другим усовершенствованным алгоритмам относятся: Этот алгоритм разбиения разделения заключается в сканировании транзакционной базы данных путем разделения ее на непересекающиеся разделы, каждый из которых может уместиться в оперативной памяти. На втором подсчитывается поддержка каждого такого набора относительно всей базы данных. Таким образом, на втором этапе определяется множество всех потенциально встречающихся наборов данных. Алгоритм DIC, Dynamic Itemset Counting. Правила принятия решений I. Правильное обучение и правильное изучение II. Правила безопасности при работе с электроприборами. ОБЩИЕ ПРАВИЛА ФЕСТИВАЛЯ Irregular Verbs — Список неправильных глаголов IV. Правила поведения в аудитории и на экзамене IV. Правила подачи и рассмотрения апелляций. Астрономия Биология География Другие языки Интернет Информатика История Культура Литература Логика Математика Медицина Механика Охрана труда Педагогика Политика Право Психология Религия Риторика Социология Спорт Строительство Технология Транспорт Физика Философия Финансы Химия Экология Экономика Электроника.
Сколько имеют право списать с карты
Где можно сделать узи молочных
Проявления экономического кризиса
Стратегические проблемы развития предприятия
История 3 рейха видео