Обнаружение закономерностей в последовательностях данных
На множестве объектов может быть задано отношение порядка [ ]. Отношение может быть задано разными способами. Если анализируется последовательность событий во времени, то отношение порядка определяется моментами времени. В этом случае упорядоченное множество объектов представляет последовательность:
, 
.
Обнаружение закономерностей в последовательности данных позволяет предсказать с определенной вероятностью появление событий. Пример последовательности:
.
Последовательности могут содержать циклы, отражающие наличие одного итого же объекта на разных позициях. Например, 
. Транзакция 
содержит последовательность 
, если 
и сохраняется отношение порядка. Допускается размещение других объектов между объектами из последовательности 
. Поддержкой последовательности называется отношение количества транзакций, в которые входит последовательность , к общему количеству транзакций. Последовательность считается частой, если её поддержка превышает минимальную поддержку, заданную аналитиком:
.
Задачей обнаружения закономерностей является поиск всех частых последовательностей:
.
При анализе временных последовательностей актуальным является оценка временных интервалов между событиями. Оценка временных интервалов позволяет предсказать появление ожидаемого события.
Алгоритм поиска ассоциативных правил Apriori
Алгоритм Apriori разработан на основе свойства поддержки наборов: поддержка любого набора объектов не может превышать минимальной поддержки любого из его подмножеств:
|
|
|
.
Это свойство проявляется потому, что набор из трех объектов 
содержит и наборы из двух объектов 
, 
, 
.
На первом шаге алгоритма производится формирование наборов с одним объектом (k = 1) и вычисляется их поддержка. Наборы с поддержкой больше минимально заданной 
отбираются. Для наборов из объектов множества 
имеем: 
, 
. Таким образом, заданной минимальной поддержке удовлетворяют только объекты 
и, следовательно, первое подмножество частых наборов имеет вид:
.
На втором шаге значение 
увеличивается на единицу ( 
) и формируются наборы из двух объектов: 
, 
, 
, 
, 
, 
. Заданной минимальной поддержке удовлетворяют наборы , 
, , и второе подмножество частых наборов:
.
На следующем шаге увеличивается снова на единицу и формируются наборы из трёх объектов: 
, 
. Поддержка набора 
равна 0,25, набора – 0,5. Следовательно, третье подмножество частых наборов имеет вид: 
.
Наборы из четырёх объектов при заданных транзакциях создать невозможно. Таким образом, в результате выполнения алгоритма будет сформировано множество частых наборов
|
|
|
.
Для расчёта поддержки необходимо на каждом шаге сравнивать наборы с заданными транзакциями.
Реализуемый в SQL Server Data Mining алгоритм относится к семейству алгоритмов Apriori. Алгоритм выполняется в два этапа. На первом этапе выполняется поиск частых наборов. На втором этапе осуществляется генерация правил взаимосвязей по частым наборам объектов [2].
Представление результатов
Результаты поиска ассоциативных правил принято представлять в виде правил: если (условие), то (результат). При этом условие представляется набором объектов из множества 
, а результат – объектами, ассоциированными с объектами из условия. Например: если 
, то 
. Ассоциативные правила строятся на основе частых наборов. Поэтому количество правил может быть большим, что затруднит их восприятие. Для оценки полезности правил используется оценка, вычисляемая как отношение транзакций, поддерживающих правило, к общему числу транзакций:
.
Не все правила могут быть полезными.
Краткие итоги
§ Поиск ассоциативных правил предполагает установление закономерностей вида: «Если в транзакции встретился набор объектов А, то в этой же транзакции должен присутствовать набор товаров В».
§ На множестве объектов может быть задано отношение порядка (последовательность объектов). Обнаружение закономерностей в последовательности позволяет предсказать появление объекта, из анализируемого множества, в заданной позиции.
|
|
|
§ Алгоритм Microsoft Association Rules относится к семейству ассоциаций Apriori и используется для нахождения частых наборов объектов (элементов). Этот алгоритм устанавливает наличие частых наборов и генерирует правила взаимосвязей по частым наборам объектов.
§ Частым набором называют такой набор, который достаточно популярен в наборе данных. Порог популярности набора определяется при помощи критерия поддержки.
§ Поддержка используется для оценки популярности набора элементов. Например, поддержка набора элементов (А, В) есть отношение количества транзакций, содержащих набор (А, В), к общему числу наборов.
Контрольные вопросы
1. При решении задач поиска ассоциативных правил в качестве транзакции рассматривают:
а) свойства объектов входящих в набор;
б) множество обнаруженных зависимостей;
в) набор объектов, элементов или товаров;
г) количество объектов в наборе.
2. Значение поддержки набора при ассоциативном поиске определяют:
а) отношением количества транзакций, содержащих набор, к общему количеству транзакций;
|
|
|
б) отношением количества объектов в наборе к количеству объектов, встречающихся во всех транзакциях;
в) отношением количества объектов в наборе к количеству объектов, встречающихся во всех наборах;
г) отношением общего количества транзакций к количеству транзакций, содержащих набор.
3. Заданный набор объектов называют частым, если:
а) поддержка имеет значение близкое к единице;
б) поддержка не меньше среднего значения всех поддержек;
в) поддержка больше поддержки одноэлементных наборов;
г) поддержка больше заданного минимального значения.
4. Ассоциативные правила имеют следующий вид:
а) поддержка набора А больше поддержки набора В;
б) частота набора А меньше больше частоты набора В;
в) если (условие), то (результат);
г) набор объектов А содержит объекты набора В.
5. Полезность определенного ассоциативного правила оценивается:
а) отношением количества объектов, входящих в наборы правила, к общему количеству объектов;
б) отношением транзакций, поддерживающих правило, к общему количеству транзакций;
в) отношением общего количества объектов к количеству объектов, входящих в наборы правил.
г) отношением общего количества транзакций к количеству транзакций, поддерживающих правило.
Литература
1. Барсегян А.А. Методы и модели анализа данных: OLAP и Data Mining / Барсегян А.А., Куприянов М.С., Степаненко В.В., Холод И.И. – СПб.: БХВ-Петербург, 2004. – 336 с.
2. Microsoft SQL Server 2008: Data mining – интеллектуальный анализ данных. Пер. с англ. / Дж. Макленнен, Чж. Танг, Б. Криват. – БХВ-Петербург. 2009. – 720 с.
3. Ларсон Б. Разработка бизнес-аналитики в SQL Server 2005. – СПб.: Питер, 2008. – 684 с.
Дата добавления: 2018-10-26; просмотров: 451; Мы поможем в написании вашей работы! |
Мы поможем в написании ваших работ!