Алгоритма основано на
Download 1.17 Mb. Pdf ko'rish
|
DATA MINING CONCEPTS AND TECHNIQUES 3RD
|
1 , . В этом разделе вы познакомитесь с методами обнаружения простейших форм частых паттернов, подобных тем, которые обсуждались для анализа потребительской корзины в разделе 6.1.1. Мы начнем с представления Apriori, базового алгоритма поиска часто встречающихся наборов элементов (раздел 6.2.1). В разделе 6.2.2 мы рассмотрим, как генерировать правила строгой ассоциации из часто используемых наборов элементов. 6.2.1. Алгоритм априори: поиск часто встречающихся наборов элементов с помощью генерации ограниченных кандидатов Априори — это основополагающий алгоритм, предложенный Р. Агравалом и Р. Шрикантом в 1994 г. для поиска часто встречающихся наборов элементов для логических ассоциативных правил [AS94b]. Название алгоритма основано на том факте, что алгоритм использует предварительное знание часто встречающихся свойств набора элементов, как мы увидим позже. Apriori использует итеративный подход, известный как поуровневый поиск, при котором наборы k элементов используются для изучения (k + 1) наборов элементов. Во-первых, набор часто встречающихся наборов из 1 элементов находится путем сканирования базы данных для накопления количества для каждого элемента и сбора тех элементов, которые удовлетворяют минимальной поддержке. Полученное множество обозначим через L1. Затем L1 используется для поиска L2, набора часто встречающихся наборов из 2 элементов, который используется для поиска L3, и так далее, пока не перестанут быть найдены более частые наборы из k элементов. Нахождение каждого Lk требует одного полного сканирования базы данных. Обозначение относится к j -му элементу в li (например, относится к предпоследнему элементу в l1). Для эффективной реализации Apriori предполагает, что элементы в транзакции или наборе элементов — это означает, что элементы отсортированы. Раздел 6.2.3 описывает несколько вариантов алгоритма Apriori для повышения эффективности и масштабируемости. В разделе 6.2.4 представлены методы расширения шаблонов для поиска часто встречающихся наборов элементов, которые ограничивают последующее пространство поиска только наборами данных, содержащими текущие часто встречающиеся наборы элементов. В разделе 6.2.5 представлены методы анализа часто встречающихся наборов элементов, которые используют преимущество вертикального формата данных. 1. Шаг соединения: чтобы найти Lk, набор наборов- кандидатов-элементов генерируется путем соединения Lk 1 с самим собой. Этот набор кандидатов обозначается Ck. Пусть l1 и l2 — наборы элементов в Lk 1. , «Как в алгоритме используется свойство априори?» Чтобы понять это, давайте посмотрим, как Lk 1 используется для поиска Lk for. Далее следует двухэтапный процесс, состоящий из действий соединения и сокращения. [СБОР ДАННЫХ: КОНЦЕПЦИИ И МЕТОДЫ, 3-Е ИЗДАНИЕ] Чтобы повысить эффективность поуровневой генерации часто встречающихся наборов элементов, для сокращения пространства поиска используется важное свойство, называемое априорным свойством. Априорное свойство: все непустые подмножества часто встречающегося набора элементов также должны быть частыми. Свойство априори основано на следующем наблюдении. По определению, если набор элементов I не удовлетворяет минимальному порогу поддержки, min_sup, то I встречается нечасто, т. е. если элемент A добавляется в набор элементов I, то результирующий набор элементов (т. е. ) не может встречаться чаще, чем I. Следовательно, . Это свойство принадлежит к особой категории свойств, называемой антимонотонностью, в том смысле, что если набор не может пройти тест, все его надмножества также не пройдут этот тест. Это называется антимонотонностью , потому что свойство является монотонным в контексте провала теста. отсортированы в лексикографическом порядке. Для (k 1)-набора li } так как { } не является подпрограммой }. Однако из } и { }) тоже не часто, т. набор элементов набора { }; и (2) { набор элементов предыдущего набора элементов, но набора элементов { максимальный частый набор элементов, мы можем только утверждать, что оба набора элементов ({ часты, но мы не можем утверждать, что их фактическая поддержка подсчитывается. . 6.2. Методы майнинга частых наборов предметов 1 211 : свойство Apriori имеет множество применений. Например, его также можно использовать для сокращения поиска. Джиавэй Хан во время вычисления куба данных (глава 5). Machine Translated by Google 212 Джиавэй Хан такие, что из Lk 1 соединяются, если их первые Lk 1 соединяются, если ( Условие просто гарантирует, что не будут созданы дубликаты. Результирующий набор элементов, образованный путем соединения l1 и l2 , равен Рисунок 6.2. Генерация наборов элементов-кандидатов и частых наборов элементов, где минимальное число поддерживаемых элементов равно 2. . Объединение выполняется там, где элементы элементов являются общими. То есть члены l1 и l2 из Априори [СБОР ДАННЫХ: КОНЦЕПЦИИ И МЕТОДЫ, 3-Е ИЗДАНИЕ] , . Давайте рассмотрим конкретный пример, основанный на базе данных транзакций AllElectronics, D , из таблицы 6.1. В этой базе данных девять транзакций, то есть . Мы используем рис. 6.2 , чтобы проиллюстрировать априорный алгоритм поиска часто встречающихся наборов элементов в D. . 2. Шаг сокращения: Ck является надмножеством Lk, т. е. его элементы могут быть или не быть частыми, но все частые наборы k элементов включены в Ck. Сканирование базы данных для определения количества каждого кандидата в Ck приведет к определению Lk (т. е. все кандидаты, число которых не меньше минимального числа поддержки, являются частыми по определению и, следовательно, принадлежат Lk). Ck, однако, может быть огромным, и это может потребовать больших вычислений. Чтобы уменьшить размер Ck, свойство априори используется следующим образом. Любой (k 1)-набор элементов, который не является частым, не может быть подмножеством частого k-набора элементов. Следовательно, если какое-либо (k 1)-подмножество кандидата k-набора элементов не находится в Lk 1, то кандидат также не может быть частым и поэтому может быть удален из Ck. Это тестирование подмножества можно выполнить быстро, поддерживая хеш-дерево всех часто встречающихся наборов элементов. Machine Translated by Google Т100 Т700 И1, И2, И5 Список item_ID И1, И2, И3 Т900 И2, И3 Т300 И2, И4 Т200 И2, И3 И1, И3 Т500 И1, И2, И4 Т400 ТИД И1, И2, И3, И5 Т800 И1, И3 Т600 , 3. Чтобы обнаружить набор часто встречающихся наборов из 2 элементов, L2, алгоритм использует соединение для создания набора-кандидата из наборов из 2 элементов, C2. Обратите внимание, что при наличии набора k-кандидатов нам нужно только проверить, являются ли его (k 1)- подмножества частыми, поскольку алгоритм Apriori использует стратегию поиска по уровням. Результирующая урезанная версия C3 показана в первой таблице нижней строки рисунка 6.2. [СБОР ДАННЫХ: КОНЦЕПЦИИ И МЕТОДЫ, 3-Е ИЗДАНИЕ] к 6. Генерация набора возможных наборов из 3 элементов, C3, подробно показана на рис. 6.3 . C2 состоит из шага обрезки, поскольку каждое подмножество кандидатов также является частым. 1. В первой итерации алгоритма каждый элемент является членом набора наборов кандидатов 1-элементов, C1. Алгоритм просто сканирует все транзакции, чтобы подсчитать количество вхождений каждого элемента. 2-наборы. Обратите внимание, что ни один кандидат не удаляется из C2 во время . На этапе соединения мы сначала получаем {{I1, I2, I3}, {I1, I2, I5}, {I1, I3, I5}, {I2, I3, I4}, {I2, I3, I5}, { И2, И4, И5}}. Основываясь на априорном свойстве, согласно которому все подмножества часто встречающегося набора элементов также должны быть частыми, мы можем определить, что последние четыре кандидата не могут быть частыми. Поэтому мы удаляем их из C3, тем самым экономя усилия на ненужное получение их подсчетов во время последующего сканирования D для определения L3. 2. Предположим, что минимально необходимое количество опор равно 2, т. е. . (Здесь мы имеем в виду абсолютную поддержку, потому что используем подсчет поддержки. Соответствующая относительная поддержка равна %.) Затем можно определить множество часто встречающихся наборов из 1 элементов, L1 . Он состоит из наборов кандидатов из 1 элементов, удовлетворяющих минимальной поддержке. В нашем примере все кандидаты в C1 удовлетворяют минимальной поддержке. 4. Затем сканируются транзакции в D и накапливается количество поддержки каждого набора элементов-кандидатов в C2 , как показано в средней таблице второй строки на рис. 6.2. 5. Затем определяется набор часто встречающихся наборов из 2 элементов, L2, состоящий из тех наборов-кандидатов из 2 элементов в C2 , которые имеют минимальную поддержку. Таблица 6.1 Транзакционные данные для филиала AllElectronics Джиавэй Хан эквивалентно доле k 1 = 0 шт. требует, чтобы два соединяющихся набора элементов 213 с момента определения Machine Translated by Google , 7. Транзакции в D сканируются для определения L3, состоящего из тех наборов-кандидатов из 3 элементов в C3 , которые имеют минимальную поддержку (рис. 6.2). [СБОР ДАННЫХ: КОНЦЕПЦИИ И МЕТОДЫ, 3-Е ИЗДАНИЕ] 8. Алгоритм использует для генерации набора кандидатов из 4 наборов элементов, C4. Хотя объединение приводит к {{I1, I2, I3, I5}}, набор элементов {I1, I2, I3, I5} удаляется, поскольку его подмножество {I2, I3, I5} встречается нечасто. Таким образом, алгоритм завершает работу, найдя все часто встречающиеся наборы. На рис. 6.4 показан псевдокод алгоритма Apriori и связанных с ним процедур. Шаг 1 априори находит часто встречающиеся наборы из 1 элемента, L1. На шагах со 2 по 10 Lk 1 используется для генерации кандидатов Ck , чтобы найти Lk для . Процедура apriori_gen создает кандидатов, а затем использует свойство Apriori для исключения тех, у которых подмножество не является частым (шаг 3). Эта процедура описана позже. Как только все кандидаты будут сгенерированы, база данных сканируется (шаг 4). Для каждой транзакции функция подмножества используется для поиска всех подмножеств транзакции, являющихся кандидатами (шаг 5), и накапливается количество для каждого из этих кандидатов (шаги 6 и 7). Наконец, все кандидаты, удовлетворяющие минимальной поддержке (шаг 9), образуют набор часто встречающихся наборов L (шаг 11). Затем можно вызвать процедуру для создания правил ассоциации из часто используемых наборов элементов. Такая процедура описана в разделе 6.2.2. Рис. 6.3. Генерация и удаление наборов-кандидатов из 3 элементов C3 из L2 с использованием свойства Apriori. 214 Джиавэй Хан Machine Translated by Google , Процедура apriori_gen выполняет два вида действий, а именно объединение и удаление, как описано выше. В компоненте соединения Lk 1 соединяется с Lk 1 для создания потенциальных кандидатов (шаги 1– 4). Компонент prune (шаги 5–7) использует свойство Apriori для удаления кандидатов, имеющих нечастое подмножество. Тест для нечастых подмножеств показан в процедуре has_infrequent_subset. l, порождаем все непустые подмножества l. мин_конф, " если Условная вероятность выражается в терминах количества поддерживаемых наборов элементов, где количество транзакций, содержащих наборы элементов, и количество транзакций, содержащих набор элементов A. На основе этого уравнения можно сгенерировать правила ассоциации следующим образом: 6.2.2. Генерация ассоциативных правил из часто встречающихся наборов элементов После того, как частые наборы элементов из транзакций в базе данных D были найдены, можно легко сгенерировать из них строгие ассоциативные правила (где строгие ассоциативные правила удовлетворяют как минимальной поддержке, так и минимальной достоверности). Это можно сделать с помощью уравнения (6.4) для уверенности, которую мы снова покажем здесь для полноты: [СБОР ДАННЫХ: КОНЦЕПЦИИ И МЕТОДЫ, 3-Е ИЗДАНИЕ] s из l, выведите правило «где min_conf — минимальный доверительный порог. Рис. 6.4. Априорный алгоритм обнаружения часто встречающихся наборов элементов для извлечения правил логических ассоциаций. Джиавэй Хан 215 Machine Translated by Google Джиавэй Хан 216 , Сокращение транзакций (уменьшение количества сканируемых транзакций в будущих итерациях): транзакция, которая не содержит частых k-элементных наборов, не может содержать частых ( )- элементных наборов. Следовательно, такая транзакция может быть помечена или удалена из дальнейшего рассмотрения, поскольку последующая база данных просматривает наборы j-элементов, где не нужно будет рассматривать такую транзакцию. Разделение (разделение данных для поиска наборов элементов- кандидатов): можно использовать метод разделения, требующий всего двух сканирований базы данных для поиска часто используемых наборов элементов (рис. 6.6). Он состоит из двух фаз. На этапе I алгоритм делит транзакции D на n непересекающихся частей. Если минимальный порог относительной поддержки для транзакций в D является минимальным числом поддержки для {I1, I2} I5, достоверность = 2/4 = 50% Техника на основе хеширования (хеширование наборов элементов в соответствующие сегменты): Техника на основе хеширования может использоваться для уменьшения размера наборов k-кандидатов, Ck, для . Например, при сканировании каждой транзакции в базе данных для создания частых наборов из 1 элемента, L1, мы можем генерировать все наборы из 2 элементов для каждой транзакции, хешировать (т. е. отображать) их в разные сегменты структуры хэш-таблицы и увеличьте количество соответствующих ковшей (рис. 6.5). Набор из 2 элементов с соответствующим количеством сегментов в хэш-таблице, который ниже порога поддержки, не может быть частым и, следовательно, должен быть удален из набора кандидатов. Такой метод, основанный на хешировании, может существенно уменьшить количество проверяемых наборов k-кандидатов (особенно когда Давайте попробуем пример, основанный на транзакционных данных для AllElectronics, показанных ранее в Таблице 6.1 . Данные содержат часто встречающийся набор элементов {I1, I2, I5}. Какие правила ассоциации можно сгенерировать из X? Непустые подмножества X — это {I1, I2}, {I1, I5}, {I2, I5}, {I1}, {I2} и {I5}. Результирующие правила ассоциации показаны ниже, каждое из которых указано со своей достоверностью: {I2, I5} I1, достоверность = 2/2 = 100% , {I1, I5} I2, достоверность = 2/2 = 100% ). I5 {I1, I2}, достоверность = 2/2 = 100% I2 {I1, I5}, достоверность = 2/7 = 29% [СБОР ДАННЫХ: КОНЦЕПЦИИ И МЕТОДЫ, 3-Е ИЗДАНИЕ] I1 {I2, I5}, достоверность = 2/6 = 33% Создание правил ассоциации 6.2.3. Повышение эффективности Apriori «Как мы можем еще больше повысить эффективность майнинга на основе Apriori?» Было предложено множество вариантов априорного алгоритма, направленных на повышение эффективности исходного алгоритма. Некоторые из этих вариантов резюмируются следующим образом: Поскольку правила генерируются из частых наборов элементов, каждый из них автоматически удовлетворяет минимальной поддержке. Часто используемые наборы элементов можно заранее сохранить в хэш-таблицах вместе с их счетчиками, чтобы к ним можно было быстро получить доступ. Если минимальный доверительный порог составляет, скажем, 70 %, то выводятся только второе, третье и последнее правила, потому что только они являются сильными. Обратите внимание, что, в отличие от обычных правил классификации, правила ассоциации могут содержать более одного конъюнкта в правой части правила. Machine Translated by Google Выборка (анализ подмножества заданных данных). Основная идея подхода выборки состоит в том, чтобы выбрать случайную выборку S из заданных данных D, а затем найти часто встречающиеся наборы элементов в S вместо D. Таким образом, мы торгуем от некоторой степени точности против эффективности. Размер выборки S таков, что поиск часто встречающихся наборов элементов в S может выполняться в основной памяти, поэтому в целом требуется только одно сканирование транзакций в S. Поскольку мы ищем часто встречающиеся наборы элементов в S , а не в D, возможно, что мы пропустим некоторые глобальные часто встречающиеся наборы элементов. Чтобы уменьшить эту возможность, мы используем более низкий порог поддержки, чем минимальная поддержка, чтобы найти частые наборы элементов, локальные для S (обозначенная L база данных затем используется для вычисления фактической частоты каждого набора элементов в L , чтобы определить, все ли глобальные частые наборы элементов являются входит в л Однако любой набор элементов, который потенциально является частым по отношению к D, должен встречаться как частый набор элементов по крайней мере в одном из разделов. раздел — это × количество транзакций в этом разделе. Для каждого раздела находятся все локальные часто встречающиеся наборы элементов (т. е. наборы элементов, часто встречающиеся в разделе). Таким образом, все локальные наборы часто встречающихся элементов являются наборами-кандидатами по отношению к D. Набор часто встречающихся наборов элементов из всех разделов формирует глобальные наборы- кандидаты по отношению к D. На этапе II ). Остальная часть механизма А проводится второе сканирование D , в котором оценивается фактическая поддержка каждого кандидата для определения глобальных частых наборов элементов. Размер раздела и количество разделов задаются таким образом, чтобы каждый раздел помещался в основную память и, следовательно, считывался только один раз на каждой фазе. Если Л [СБОР ДАННЫХ: КОНЦЕПЦИИ И МЕТОДЫ, 3-Е ИЗДАНИЕ] Локальный частый набор элементов может быть или не быть частым по отношению ко всей базе данных, D. 1 Джиавэй Хан : Доказательство этого свойства оставляем в качестве упражнения (см . упражнение 6.3d). 217 . . 1 Рис. 6.6. Интеллектуальный анализ путем разделения данных. с с с Рисунок 6.5. Хэш-таблица H2 для наборов-кандидатов из двух элементов. Эта хеш-таблица была сгенерирована путем сканирования транзакций таблицы 6.1 при определении L1. Если минимальное количество поддержки равно, скажем, 3, то наборы элементов в корзинах 0, 1, 3 и 4 не могут быть частыми, и поэтому их не следует включать в C2. с Machine Translated by Google Джиавэй Хан 218 6.2.4. Подход на основе роста по шаблону для добычи часто встречающихся наборов элементов Мы повторно исследуем анализ базы данных транзакций D из таблицы 6.1 в примере 6.3 , используя подход с частым ростом паттерна. Первое сканирование базы данных такое же, как и в Apriori, которое выводит набор часто встречающихся элементов (1-наборы элементов) и их количество поддержки (частоты). Это приводит к меньшему количеству сканирований базы данных, чем при использовании Apriori для поиска всех часто используемых наборов элементов. Динамический подсчет наборов элементов (добавление наборов-кандидатов в разные моменты сканирования): был предложен метод динамического подсчета наборов элементов, в котором база данных разбивается на блоки, отмеченные начальными точками. В этом варианте новые наборы элементов-кандидатов могут быть добавлены в любой начальной точке, в отличие от Apriori, который определяет новые наборы элементов-кандидатов только непосредственно перед каждым полным сканированием базы данных. Этот метод использует количество до тех пор, как нижняя граница фактического количества. Если текущий счет превышает минимальную поддержку, набор элементов добавляется в коллекцию частых наборов элементов и может использоваться для создания более длинных кандидатов. Рост FP (поиск частых наборов элементов без генерации кандидатов) Затем FP-дерево строится следующим образом. Сначала создайте корень дерева с пометкой «null». Просканируйте базу данных D во второй раз. Элементы в каждой транзакции обрабатываются в порядке L (т. е. сортируются по убыванию количества поддержки), и для каждого создается ветвь. Другие варианты обсуждаются в следующей главе. Пусть минимальное количество поддержки равно 2. Набор часто встречающихся элементов отсортирован в порядке убывания количества поддержки. Этот результирующий набор или список обозначается L. Таким образом, мы имеем L = {{I2: 7}, {I1: 6}, {I3: 6}, {I4: 2}, {I5: 2}}. Возможно, все еще потребуется сгенерировать огромное количество наборов кандидатов. Например, если имеется 104 часто встречающихся набора из 1 элемента, априорный алгоритм должен сгенерировать более 107 наборов из 2 элементов-кандидатов. Однако он может пострадать от двух нетривиальных затрат: [СБОР ДАННЫХ: КОНЦЕПЦИИ И МЕТОДЫ, 3-Е ИЗДАНИЕ] Как мы видели, во многих случаях априорный метод генерации и тестирования кандидатов значительно уменьшает размер наборов кандидатов, что приводит к хорошему приросту производительности. В противном случае можно выполнить второй проход, чтобы найти часто встречающиеся наборы элементов, которые были пропущены при первом проходе. Выборочный подход особенно полезен, когда эффективность имеет первостепенное значение, например, в приложениях с интенсивными вычислениями, которые должны запускаться часто. «Можем ли мы разработать метод, который извлекает полный набор часто встречающихся наборов элементов без такого дорогостоящего процесса генерации кандидатов?» Интересный метод в этой попытке называется частым паттерн-ростом или просто FP-ростом, который использует следующую стратегию « разделяй и властвуй ». Во-первых, он сжимает базу данных, представляющую часто встречающиеся элементы, в часто встречающееся дерево шаблонов или FP-дерево, которое сохраняет информацию об ассоциации набора элементов. Затем он делит сжатую базу данных на набор условных баз данных (особый вид спроецированной базы данных), каждая из которых связана с одним часто встречающимся элементом или «фрагментом шаблона», и исследует каждую базу данных отдельно. Для каждого «фрагмента шаблона» необходимо исследовать только связанные с ним наборы данных. Следовательно, этот подход может существенно уменьшить размер наборов данных для поиска, а также «рост» исследуемых закономерностей. Вы увидите, как это работает, в примере 6.5. фактически содержит все часто встречающиеся наборы элементов в D, то требуется только одно сканирование D. Может потребоваться многократное сканирование всей базы данных и проверка большого набора кандидатов путем сопоставления с образцом. Просматривать каждую транзакцию в базе данных, чтобы определить поддержку наборов элементов-кандидатов, дорого. Machine Translated by Google Рисунок 6.7 Дерево FP регистрирует сжатую информацию о частых образцах. который связан как ребенок с I2: 2 Для облегчения обхода дерева создается таблица заголовков элементов, в которой каждый элемент указывает на свое вхождение в дереве через цепочку узловых ссылок. Дерево, полученное после сканирования всех транзакций, показано на рис. 6.7 с соответствующими узлами-связями. Таким образом, проблема поиска частых шаблонов в базах данных трансформируется в задачу анализа FP-дерева. и I5: 1 [СБОР ДАННЫХ: КОНЦЕПЦИИ И МЕТОДЫ, 3-Е ИЗДАНИЕ] , , FP-дерево добывается следующим образом. Начните с каждого часто встречающегося шаблона длины-1 (в качестве начального шаблона суффикса), создайте его базу условных шаблонов («подбазу данных», которая состоит из набора префиксных путей в дереве FP, встречающихся вместе с шаблоном суффикса) , затем построить его (условное) FP-дерево и выполнить рекурсивную добычу на дереве. Рост паттерна достигается за счет объединения суффиксного паттерна с частыми паттернами, сгенерированными из условного FP-дерева. Анализ FP-дерева обобщен в Таблице 6.2 и детализирован следующим образом. Сначала мы рассмотрим I5, который является последним элементом в L, а не первым. Причина начала с конца списка станет очевидной, когда мы объясним процесс извлечения FP-дерева. I5 встречается в двух ветвях FP- дерева на рис. 6.7 . (Вхождения I5 можно легко найти, проследив его цепочку узловых связей.) Пути, образованные этими ветвями, таковы: I2, I1, I5: 1 и I2, I1, I3, I5: 1 . Поэтому, рассматривая I5 как суффикс, два соответствующих ему пути префикса — это I2, I1: 1 и I2, I1, I3: 1, которые образуют основу его условного шаблона. Используя эту базу условных шаблонов в качестве базы данных транзакций, мы строим I5-условное FP-дерево, которое содержит только один путь, I2: 2, I1: 2; I3 не включен, потому что его количество поддержки, равное 1, меньше минимального количества поддержки. Единственный путь генерирует все комбинации частых шаблонов: {I2, I5: 2}, {I1, I5: 2}, {I2, I1, I5: 2}. . , сделка. Например, сканирование первой транзакции «T100: I1, I2, I5», содержащей три элемента (I2, I1, I5 в порядке L ), приводит к построению первой ветви дерева с тремя узлами, I2: 1, где I2 связан как дочерний с корнем, I1 связан с I2, а I5 связан с I1. Вторая транзакция, T200, содержит элементы I2 и I4 в порядке L , что приведет к ответвлению, в котором I2 связан с корнем, а I4 связан с I2. Однако эта ветвь будет иметь общий префикс I2 с существующим путем для T100. Поэтому вместо этого мы увеличиваем счетчик узла I2 на 1 и создаем новый узел I4: 1. В общем, при рассмотрении ветки, которую нужно добавить для транзакции, счетчик каждого узла вдоль общего префикса увеличивается на 1, а узлы для элементов, следующих за префиксом, создаются и соответственно связываются. , И1: 1 , 219 Джиавэй Хан Machine Translated by Google Таблица 6.2 Анализ FP-дерева путем создания оснований условных (под)шаблонов Рис. 6.8. Условное FP-дерево, связанное с условным узлом I3. , , [СБОР ДАННЫХ: КОНЦЕПЦИИ И МЕТОДЫ, 3-Е ИЗДАНИЕ] Для I4 два его префиксных пути образуют базу условного шаблона {{I2 I1: 1}, {I2: 1}}, которая генерирует одноузловое условное FP-дерево I2: 2 и выводит один частый шаблон {I2 , I4: 2}. Как и в предыдущем анализе, базой условного шаблона I3 является {{I2, I1: 2}, {I2: 2}, {I1: 2}}. Его условное FP-дерево имеет две ветви, I2: 4, I1: 2 и I1: 2, как показано на рис. 6.8, которое генерирует набор шаблонов {{I2, I3: 4}, {I1, I3: 4}, { И2, И1, И3: 2}}. Наконец, базой условного шаблона I1 является {{I2: 4}}, с FP-деревом, которое содержит только один узел, I2: 4, который генерирует один частый шаблон, {I2, I1: 4}. Этот процесс майнинга показан на рис. 6.9. , {{И2, И1: 1}, {И2: 1}} {И2, И3: 4}, {И1, И3: 4}, {И2, И1, I3 Вещь База I4 , Частые генерируемые шаблоны {И2, И4: 2} И2: 4 I1 Условное FP-дерево И2: 2 И5: 2} {И2, И5: 2}, {И1, И5: 2}, {И2, И1, I1: {И2, И1: 4} {{И2, И1: 1}, {И2, И1, И3: 1}} И2: 4, И1: 2 2 I5 Условный шаблон И3: 2} {{I2: 4}} И2: 2, И1: 2 {{И2, И1: 2}, {И2: 2}, {И1: 2}} 220 Джиавэй Хан Machine Translated by Google Рисунок 6.9. Алгоритм роста FP для обнаружения частых наборов элементов без генерации кандидатов. Это известно как вертикальный формат данных. Метод FP-роста преобразует проблему поиска длинных частых шаблонов в рекурсивный поиск более коротких в гораздо меньших условных базах данных с последующим объединением суффикса. Он использует наименее часто встречающиеся элементы в качестве суффикса, обеспечивая хорошую избирательность. Метод существенно снижает затраты на поиск. Когда база данных большая, иногда нереально построить FP-дерево в основной памяти. Интересная альтернатива состоит в том, чтобы сначала разбить базу данных на набор спроецированных баз данных, а затем построить FP-дерево и обработать его в каждой спроецированной базе данных. Этот процесс может быть рекурсивно применен к любой проецируемой базе данных, если ее FP-дерево все еще не помещается в основную память. В качестве альтернативы данные могут быть представлены в формате item-TID_set (т. е. где item — это имя элемента, а TID_set — набор идентификаторов транзакций, содержащих этот элемент. Как априорный, так и FP-метод роста извлекают частые шаблоны из набора транзакций в формате TID- itemset (т. е. ), где TID — это идентификатор транзакции, а itemset — это набор товаров, купленных в TID транзакции. Это известно как горизонтальный формат данных. В этом подразделе мы рассмотрим, как можно эффективно анализировать наборы частых элементов, используя вертикальный формат данных, который является сутью алгоритма Eclat (преобразование класса эквивалентности). , [СБОР ДАННЫХ: КОНЦЕПЦИИ И МЕТОДЫ, 3-Е ИЗДАНИЕ] Исследование производительности метода FP-роста показывает, что он эффективен и масштабируем для анализа как длинных, так и коротких частых паттернов и примерно на порядок быстрее, чем алгоритм Apriori. 6.2.5. Анализ часто встречающихся наборов элементов с использованием вертикального формата данных Джиавэй Хан 221 Machine Translated by Google Таблица 6.3 Вертикальный формат данных набора данных транзакций D таблицы 6.1 Таблица 6.42 — Наборы элементов в вертикальном формате данных Анализ частых наборов элементов с использованием вертикального формата данных [СБОР ДАННЫХ: КОНЦЕПЦИИ И МЕТОДЫ, 3-Е ИЗДАНИЕ] Интеллектуальный анализ может быть выполнен на этом наборе данных путем пересечения TID_sets каждой пары часто встречающихся одиночных элементов. Минимальное число опор равно 2. Поскольку каждый элемент в таблице 6.3 встречается часто , всего выполняется 10 пересечений, что приводит к восьми непустым наборам из 2 элементов, как показано в таблице 6.4. Обратите внимание, что поскольку наборы элементов {I1, I4} и {I3, I5} содержат только одну транзакцию, они не принадлежат множеству частых наборов из 2 элементов. Рассмотрим горизонтальный формат данных базы данных транзакций D из таблицы 6.1 в примере 6.3. Его можно преобразовать в вертикальный формат данных, показанный в таблице 6.3 , путем однократного сканирования набора данных. Основываясь на априорном свойстве, данный набор из 3 элементов является кандидатом в набор из 3 элементов только в том случае, если каждое из его подмножеств из 2 элементов является частым. Процесс генерации кандидатов здесь сгенерирует только два набора из 3 элементов: {I1, I2, I3} и {I1, I2, I5}. Путем пересечения наборов TID_set любых двух соответствующих наборов из 2 элементов этих наборов из 3 элементов-кандидатов получается таблица 6.5 , где есть только два часто встречающихся набора из 3 элементов: {I1, I2, I3: 2} и {I1, I2, I5: 2 }. , , {Т300, Т600, Т800, Т900} {Т100, Т200, Т300, Т400, Т600, Т800, Т900} {Т200, Т400} {И2, И4} {Т100, Т800} TID_set I1 {И1, И2} {И3, И5} I3 {Т500, Т700, Т800, Т900} набор предметов {И1, И4} {И2, И3} I5 {Т100, Т400, Т500, Т700, Т800, Т900} {Т100, Т800} {И2, И5} {Т300, Т500, Т600, Т700, Т800, Т900} {Т200, Т400} {Т100, Т800} набор предметов {T800} {И1, И3} I2 {Т100, Т400, Т800, Т900} {Т400} {И1, И5} TID_set I4 222 Джиавэй Хан Machine Translated by Google В Разделе 6.1.2 мы видели, как интеллектуальный анализ частых наборов элементов может генерировать огромное количество частых наборов элементов, особенно когда порог min_sup установлен на низком уровне или когда в наборе данных существуют длинные шаблоны. Пример 6.2 показал, что закрытые часто встречающиеся наборы элементов могут существенно сократить количество шаблонов, генерируемых при анализе часто встречающихся наборов элементов, сохраняя при этом полную информацию о множестве часто встречающихся наборов элементов1. частые наборы предметов и их поддержка. Таким образом, на практике в большинстве случаев предпочтительнее анализировать набор закрытых наборов часто встречающихся элементов, а не набор всех наборов часто встречающихся элементов. Пример 6.6 иллюстрирует процесс извлечения часто встречающихся наборов элементов путем изучения вертикального формата данных. Во-первых, мы преобразуем горизонтально отформатированные данные в вертикальный формат, сканируя набор данных один раз. Счетчик поддержки набора элементов — это просто длина TID_set набора элементов. Начиная с частых наборов k элементов, можно использовать для построения наборов кандидатов (k + 1) на основе априорного свойства. Вычисление выполняется путем пересечения TID_sets частых k-наборов элементов для вычисления TID_sets соответствующих (k + 1)-наборов элементов. Этот процесс повторяется, каждый раз k увеличивается на 1 до тех пор, пока не будут найдены наборы часто встречающихся элементов или наборы-кандидаты . этот метод заключается в том, что нет необходимости сканировать базу данных, чтобы найти поддержку (k + 1)-itemsets (для ). Это связано с тем, что набор TID_set каждого набора k-элементов содержит полную информацию, необходимую для подсчета такой поддержки. Однако наборы TID_sets могут быть довольно длинными, занимая значительный объем памяти, а также время вычислений для пересечения длинных наборов. Чтобы еще больше снизить стоимость регистрации длинных TID_sets, а также последующие затраты на пересечения, мы можем использовать технику, называемую diffset, которая отслеживает только различия TID_sets (k + 1)- itemset и соответствующего k -набор элементов. Например, в примере 6.6 мы имеем {I1} = {T100, T400, T500, T700, T800, T900} и {I1, I2} = {T100, T400, T800, T900}. Разница между ними равна diffset ( {I1, I2}, {I1}) = {T500, T700}. Таким образом, вместо записи четырех TID, составляющих пересечение {I1} и {I2}, мы можем вместо этого использовать diffset для записи только двух TID, указывающих разницу между {I1} и {I1, I2}. Эксперименты показывают, что в определенных ситуациях, например, когда набор данных содержит много плотных и длинных шаблонов, этот метод может существенно снизить общую стоимость анализа вертикального формата часто используемых наборов элементов. [СБОР ДАННЫХ: КОНЦЕПЦИИ И МЕТОДЫ, 3-Е ИЗДАНИЕ] «Как мы можем майнить закрытые частые наборы предметов?» Наивный подход состоял бы в том, чтобы сначала извлечь полный набор наборов часто встречающихся элементов, а затем удалить каждый набор часто встречающихся элементов, являющийся правильным подмножеством существующего набора часто используемых элементов и имеющий ту же поддержку, что и существующий набор часто встречающихся элементов. Однако это довольно затратно. Как показано в примере 6.2, этот метод должен сначала получить наборы часто встречающихся элементов, чтобы получить набор часто встречающихся элементов длиной 100, и все это до того, как он сможет начать исключать избыточные наборы элементов. Это запредельно дорого. На самом деле существуют только 6.2.6. Закрытые и максимальные паттерны майнинга , 223 Джиавэй Хан 1 Таблица 6.53 — Наборы элементов в вертикальном формате данных : Помните, что X является закрытым частым набором элементов в наборе данных S , если не существует надлежащего набора суперэлементов Y , такого что Y имеет такое же количество поддержки, что и X в S, и X удовлетворяет минимальной поддержке . TID_set {Т800, Т900} {И1, И2, И5} {Т100, Т800} набор предметов {И1, И2, И3} Machine Translated by Google Рассмотрим, например, предыдущую базу данных транзакций, содержащую только две транзакции: { }, где . Поскольку проецируемая база данных имеет ту же поддержку, что и глобальная таблица заголовков, ее можно удалить из глобальной таблицы заголовков. Аналогичную обрезку можно сделать для . После майнинга спроецированной базы данных больше ничего не нужно добывать. Помимо сокращения пространства поиска в процессе добычи закрытого набора элементов, еще одна важная оптимизация заключается в выполнении эффективной проверки каждого вновь полученного частого набора элементов, чтобы увидеть, закрыт ли он. Это связано с тем, что процесс майнинга не может гарантировать закрытие каждого сгенерированного часто используемого набора элементов. , очень небольшое количество закрытых частых наборов элементов в наборе данных примера 6.2 . Рекомендуемая методология заключается в поиске закрытых частых наборов элементов непосредственно в процессе майнинга. Когда создается новый часто встречающийся набор элементов, необходимо выполнить два вида проверки закрытия: (1) проверку надмножества, которая проверяет, является ли этот новый часто встречающийся набор надмножеством некоторых уже найденных закрытых наборов с той же поддержкой, и (2) проверка подмножества, которая проверяет, является ли вновь найденный набор элементов подмножеством уже найденного закрытого набора элементов с той же поддержкой . и нет необходимости явно выполнять проверку надмножества. Это связано с тем, что если часто встречающийся набор элементов обнаруживается позже, чем набор элементов X, и имеет ту же поддержку, что и X, он должен быть в спроецированной базе данных X и должен быть сгенерирован во время слияния наборов элементов. Это требует от нас сокращения пространства поиска, как только мы сможем определить случай закрытых наборов элементов во время майнинга. Стратегии обрезки включают следующее: Чтобы помочь в проверке подмножества, можно построить сжатое дерево шаблонов, чтобы поддерживать набор закрытых наборов элементов, добытых до сих пор. Дерево шаблонов аналогично по структуре FP-дереву, за исключением того, что все найденные закрытые наборы элементов хранятся явно в соответствующих ветвях дерева. Для эффективной проверки подмножества мы можем использовать следующее свойство: Если текущий , [СБОР ДАННЫХ: КОНЦЕПЦИИ И МЕТОДЫ, 3-Е ИЗДАНИЕ] Слияние элементов: если каждая транзакция, содержащая частый набор элементов X, также содержит набор элементов Y, но не какое-либо правильное надмножество элементов Y, тогда формируется частый закрытый набор элементов, и нет необходимости искать какой-либо набор элементов, содержащий X, но не содержащий Y. Например, в Таблица 6.2 из примера 6.5 спроецированная условная база данных для набора элементов префикса {I5:2} представляет собой {{I2, I1}, {I2, I1, I3}}, из которой мы можем видеть, что каждая из ее транзакций содержит набор элементов {I2, I1 }, но нет правильного надмножества {I2, I1}. Набор элементов {I2, I1} можно объединить с {I5}, чтобы сформировать закрытый набор элементов {I5, I2, I1: 2}, и нам не нужно искать закрытые наборы элементов, которые содержат I5, но не содержат {I2, I1}. Сокращение набора подэлементов: если часто используемый набор элементов X является подходящим подмножеством уже найденного частого закрытого набора элементов Y и support_count(X) = support_count(Y), то X и все потомки X в дереве перечисления наборов не могут быть часто встречающимися закрытыми наборами элементов и, таким образом, можно обрезать. Как и в примере 6.2, предположим, что в базе данных транзакций есть только две транзакции: { }, а минимальное число поддерживаемых значений равно min_sup = 2. Проекция на первый элемент, , выводит часто встречающийся набор элементов, { }, на основе оптимизации слияния наборов элементов . Поскольку поддержка ({ }) = поддержка ({ }) = 2, а { } является правильным подмножеством { }, нет необходимости проверять его спроецированную базу данных. Аналогичную обрезку можно сделать и для . Таким образом, анализ закрытых часто используемых наборов элементов в этом наборе данных завершается после анализа спроецированной базы данных. Пропуск элементов: при анализе закрытых наборов элементов в глубину на каждом уровне будет префикс набора элементов X , связанный с таблицей заголовков и проектируемая база данных. Если локальный частый элемент p имеет одинаковую поддержку в нескольких таблицах заголовков на разных уровнях, мы можем безопасно удалить p из таблиц заголовков на более высоких уровнях. , в Джиавэй Хан 224 Machine Translated by Google 6.3. Какие паттерны интересны? — Методы оценки паттернов 6.3.1. Строгие правила не обязательно интересны Предположим, нас интересует анализ сделок в AllElectronics в отношении покупки компьютерных игр и видео. Пусть игра относится к транзакциям, содержащим компьютерные игры, а видео — к транзакциям, содержащим видео. Данные показывают, что из 10 000 проанализированных транзакций 6000 транзакций клиентов включали компьютерные игры, 7500 — видео, а 4000 — как компьютерные игры, так и видео. Предположим, что программа интеллектуального анализа данных для обнаружения правил ассоциации запускается на данных, используя минимальную поддержку, скажем, 30% и минимальную достоверность 60%. Обнаружено следующее правило ассоциации: (6.6) Интересно ли правило, можно оценить либо субъективно, либо объективно. набор может быть включен в другой уже найденный закрытый набор, тогда (1) и имеет ту же поддержку, (2) длина меньше, чем у , и (3) все элементы в содержатся в Большинство алгоритмов анализа ассоциативных правил используют структуру поддержки-достоверности. В конечном счете, только пользователь может судить, интересно ли данное правило, и это суждение, будучи субъективным, может отличаться от одного пользователя к другому. Однако объективные меры интереса, основанные на статистике, лежащей в основе данных, могут использоваться как один из шагов к цели отсеивания неинтересных правил, которые в противном случае были бы представлены пользователю. «Как мы можем сказать, какие сильные правила ассоциации действительно интересны?» Давайте рассмотрим следующий пример. Хотя минимальная поддержка и пороги достоверности помогают отсеять или исключить исследование большого количества неинтересных правил, многие из сгенерированных правил по-прежнему не интересны пользователям. К сожалению, это особенно актуально при майнинге с низкими порогами поддержки или майнинге по длинным паттернам. Это было основным узким местом для успешного применения анализа ассоциативных правил. [СБОР ДАННЫХ: КОНЦЕПЦИИ И МЕТОДЫ, 3-Е ИЗДАНИЕ] . На основе этого свойства можно построить двухуровневую структуру хеш-индекса для быстрого доступа к дереву шаблонов: первый уровень использует идентификатор последнего элемента в качестве хэш-ключа (поскольку этот идентификатор должен находиться в ветви ) , а второй уровень использует поддержку в качестве хеш-ключа (поскольку и имеют одинаковую поддержку). Это существенно ускорит процесс проверки подмножества. Это обсуждение иллюстрирует методы эффективного исследования закрытых наборов часто встречающихся элементов. «Можем ли мы расширить эти методы для эффективного извлечения максимально часто встречающихся наборов элементов?» Поскольку максимально часто встречающиеся наборы элементов имеют много общего с закрытыми часто встречающимися наборами элементов, многие из методов оптимизации, разработанных здесь, могут быть расширены до извлечения максимально часто встречающихся наборов элементов. Однако мы оставляем этот метод в качестве упражнения для заинтересованных читателей. В этом разделе мы сначала рассмотрим, как даже правила строгой ассоциации могут быть неинтересными и вводящими в заблуждение (раздел 6.3.1). Затем мы обсудим, как можно дополнить структуру поддержки-уверенности дополнительными мерами интереса, основанными на корреляционном анализе (раздел 6.3.2). В разделе 6.3.3 представлены дополнительные меры по оценке шаблонов. Затем он обеспечивает общее сравнение всех мер, обсуждаемых здесь. К концу вы узнаете, какие меры оценки шаблонов наиболее эффективны для обнаружения только интересных правил. Вводящее в заблуждение «сильное» правило ассоциации , 225 Джиавэй Хан Machine Translated by Google Download 1.17 Mb. Do'stlaringiz bilan baham: 
|