Поиск ассоциативных правил

Одной из наиболее распространённых задач анализа данных является определение часто встречающихся
наборов объектов в большом множестве наборов.
Впервые это задача была предложена поиска ассоциативных правил для нахождения типичных шаблонов покупок,
совершаемых в супермаркетах, поэтому иногда ее еще называют анализом рыночной корзины (market basket analysis).

Формальная постановка задачи

Пусть имеется база данных, состоящая из покупательских транзакций.
Каждая транзакция – это набор товаров, купленных покупателем за один визит. Такую транзакцию еще называют рыночной корзиной.

Пусть I = <ii,i2. ij. in> – множество (набор) товаров (объектов) общим числом n.
Пусть D – множество транзакций D = <T1,T2,Tr. Tm> , где каждая транзакция T – это набор элементов из I. .

В сфере торговли, например, такими объектами являются товары, представленные в прайс-листе:

Они соответствуют следующему множеству объектов: I=<шоколад, хлеб, масло, вода, молоко, орехи>.
Примерами транзакций могут быть T1 = < хлеб, масло, молоко >, T2 = < шоколад, вода, орехи >.
Множество транзакций, в которые входит объект ij , обозначим следующим образом:
.
Множество D может быть представлено следующим образом:

В данном примере, множеством транзакций, содержащим объект «Вода», является следующее множество:

Некоторый произвольный набор объектов (itemset) обозначим следующим образом:
, например F = <хлеб, масло>.
Набор, состоящий из k элементов, называется k-элементным набором.
Множество транзакций, в которые входит набор F, обозначим следующим образом:
.
В данном примере:

Отношение количества транзакций, в которое входит набор F, к общему количеству транзакций
называется поддержкой (support) набора F и обозначается Supp(F):
.
Для набора < масло, вода >поддержка будет равна 0,5, т.к. данный набор входит в две транзакции
с номерами 1 и 2, а всего транзакций четыре.
При поиске аналитик может указать минимальное значение поддержки интересующих его наборов Suppmin .
Набор называется частым (large itemset), если значение его поддержки больше минимального значения поддержки,
заданного пользователем: Supp(F) > Suppmin .
Таким образом, при поиске ассоциативных правил требуется найти множество всех частых наборов:
L = <F | Supp(F) > Suppmin> .
В данном примере частыми наборами при Suppmin = 0,5 являются следующие:

Представление результатов

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

  • нахождение всех частых наборов объектов:
  • генерация ассоциативных правил из найденных частых наборов объектов.
  • Ассоциативные правила имеют следующий вид:

    где условие — обычно не логическое выражение (как в классификационных правилах),
    а набор объектов из множества I, с которым связаны (ассоциированы) объекты, включенные
    в результат данного правила.
    Например, ассоциативное правило: «если (молоко, масло), то (хлеб)» означает, что если
    потребитель покупает молоко и масло, то он покупает и хлеб.
    Основным достоинством ассоциативных правил является их лёгкое восприятие человеком и
    простая интерпретация языками программирования. Однако, они не всегда полезны.
    Выделяют три вида правил:

  • полезные правила — содержат действительную информацию, которая ранее была неизвестна, но имеет логическое объяснение. Такие правила могут быть использованы для принятия решений, приносящих выгоду;
  • тривиальные правила — содержат действительную и легко объяснимую информацию, которая уже известна. Такие правила не могут принести пользу, т.к. отражают или известные законы в исследуемой области, или результаты прошлой деятельности. Иногда такие правила могут использоваться для проверки выполнения решений, принятых на основании предыдущего анализа;
  • непонятные правила — содержат информацию, которая не может быть объяснена. Такие правила могут быть получены на основе аномальных значений, или сугубо скрытых знаний. Напрямую такие правила нельзя использовать для принятия решений, т.к. их необъяснимость может привести к непредсказуемым результатам. Для лучшего понимания требуется дополнительный анализ.
  • Ассоциативные правила строятся на основе частых наборов. Так правила, построенные на основании набора F,
    являются возможными комбинациями объектов, входящих в него.
    Например, для набора <масло, вода, орехи>, могут быть построены следующие правила:

    Таким образом, количество ассоциативных правил может быть очень большим и трудновоспринимаемым для человека.
    К тому же, не все из построенных правил несут в себе полезную информацию.
    Для оценки их полезности вводятся следующие величины:
    Поддержка(support) — показывает, какой процент транзакций поддерживает данное правило.
    Так как правило строится на основании набора, то, значит, правило X=>Y имеет поддержку, равную поддержке набора F,
    который составляют X и Y:
    Y> = Supp_F = \frac<|D_|><|D|>» src=»http://bourabai.ru/tpoi/analysis4.htm/analysis/15850347eb2e7f0d58b68b436079549f.png»>.
    Очевидно, что правила, построенные на основании одного и того же набора, имеют одинаковую поддержку,
    например, поддержка Supp(если (вода, масло), то (орехи) = Supp(вода, масло, орехи) = 0,5.

    Достоверность(confidence) — показывает вероятность того, что из наличия в транзакции набора X следует наличие в ней набора Y.
    Достоверностью правила X=>Y является отношение числа транзакций, содержащих X и Y, к числу транзакций, содержащих набор Х:
    Y> = \frac<|D_|> <|D_X|>= \frac>» src=»http://bourabai.ru/tpoi/analysis4.htm/analysis/536eb0f797741ab5b4d153fce8250cbc.png»>.
    Очевидно, что чем больше достоверность, тем правило лучше, причем у правил, построенных на основании одного и того же набора,
    достоверность будет разная, например:

    К сожалению, достоверность не позволяет определить полезность правила. Если процент наличия в транзакциях набора Y
    при условии наличия в нем набора Х меньше, чем процент безусловного наличия набора Y, т.е.:
    Y> = \frac> .
    Это значит, что вероятность случайно угадать наличие в транзакции набора Y больше, чем предсказать это с помощью правила X=>Y.
    Для исправления такой ситуации вводится мера — улучшение.
    Улучшение(improvement) — показывает, полезнее ли правило случайного угадывания. Улучшение правила является отношением
    числа транзакций, содержащих наборы X и Y, к произведению количества транзакций, содержащих набор Х, и количества транзакций,
    содержащих набор Y:
    Y> = \frac<|D_|> <|D_X||D_Y|>= \frac>» src=»http://bourabai.ru/tpoi/analysis4.htm/analysis/99a045ac0a4e9c95363f4dd2b1509483.png»>.
    Например, impr(если (вода, масло), то (орехи) = 0,5/(0,5*0,5) = 2.
    Если улучшение больше единицы, то это значит, что с помощью правила предсказать наличие набора Y вероятнее, чем случайное угадывание,
    если меньше единицы, то наоборот.
    В последнем случае можно использовать отрицательное правило, т.е. правило, которое предсказывает отсутствие набор Y:
    X => не Y.
    Правда, на практике такие правила мало применимы. Например, правило: «если (вода, масло), то не (молоко)» мало полезно,
    т.к. слабо выражает поведение покупателя.
    Данные оценки используются при генерации правил. Аналитик при поиске ассоциативных правил
    задает минимальные значения перечисленных величин. В результате те правила, которые не удовлетворяют этим условиям,
    отбрасываются и не включаются в решение задачи. С этой точки зрения нельзя объединять разные правила, хотя и имеющие
    общую смысловую нагрузку.
    Например, следующие правила:

    нельзя объединить в одно:

    т.к. достоверности их будут разные, следовательно, некоторые из них могут быть исключены, а некоторые — нет.

    Алгоритм Apriori

    Содержание:

    Свойство анти-монотонности

    Выявление часто встречающихся наборов элементов – операция, требующая много вычислительных ресурсов и, соответственно, времени.
    Примитивный подход к решению данной задачи – простой перебор всех возможных наборов элементов.
    Это потребует O(2 | I | ) операций, где |I| – количество элементов.
    Apriori использует одно из свойств поддержки, гласящее: поддержка любого набора элементов не может превышать
    минимальной поддержки любого из его подмножеств. Например, поддержка 3-элементного набора <Хлеб, Масло, Молоко>
    будет всегда меньше или равна поддержке 2-элементных наборов <Хлеб, Масло>, <Хлеб, Молоко>, <Масло, Молоко>.
    Дело в том, что любая транзакция, содержащая <Хлеб, Масло, Молоко>, также должна содержать <Хлеб, Масло>, <Хлеб, Молоко>, <Масло, Молоко>,
    причем обратное не верно.

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

    Свойству анти-монотонности можно дать и другую формулировку: с ростом размера набора элементов поддержка уменьшается,
    либо остается такой же. Из всего вышесказанного следует, что любой k-элементный набор будет часто встречающимся тогда и только тогда,
    когда все его (k-1)-элементные подмножества будут часто встречающимися.

    Все возможные наборы элементов из I можно представить в виде решетки, начинающейся с пустого множества, затем
    на 1 уровне 1-элементные наборы, на 2-м – 2-элементные и т.д. На k уровне представлены k-элементные наборы,
    связанные со всеми своими (k-1)-элементными подмножествами.

    Рассмотрим рисунок, иллюстрирующий набор элементов I – .
    Предположим, что набор из элементов имеет поддержку ниже заданного порога и, соответственно, не является часто встречающимся.
    Тогда, согласно свойству анти-монотонности, все его супермножества также не являются часто встречающимися и отбрасываются.
    Вся эта ветвь, начиная с , выделена фоном. Использование этой эвристики позволяет существенно сократить пространство поиска.

    Описание алгоритма

    Алгоритм Apriori определяет часто встречающиеся наборы за несколько этапов.
    На i-ом этапе определяются все часто встречающиеся i-элементные наборы. Каждый этап состоит из двух шагов:

    1. формирование кандидатов (candidate generation);
    2. подсчет поддержки кандидатов (candidate counting).

    Рассмотрим i-ый этап. На шаге формирования кандидатов алгоритм создает множество кандидатов из i-элементных наборов,
    чья поддержка пока не вычисляется. На шаге подсчета кандидатов алгоритм сканирует множество транзакций,
    вычисляя поддержку наборов-кандидатов. После сканирования отбрасываются кандидаты, поддержка которых меньше
    определенного пользователем минимума, и сохраняются только часто встречающиеся i-элементные наборы.
    Во время первого этапа выбранное множество наборов-кандидатов содержит все одно-элементные частые наборы.
    Алгоритм вычисляет их поддержку во время шага подсчёта поддержки кандидатов.
    Описанный алгоритм можно записать в виде следующего псевдокода:

    Обозначения, используемые в алгоритме:

  • Lk — множество k-элементных наборов, чья поддержка не меньше заданной пользователем. Каждый член множества имеет набор упорядоченных ( ijSuppmin :
  • Ck — множество кандидатов k-элементных наборов потенциально частых. Каждый член множества имеет набор упорядоченных ( ijТПОИк оглавлениюк дискретной математикетехнологии программирования

    Мало ли что я обещал гоям?
    Российскую пенсию будут получать только израильтяне!
    Мой кошелёк — Минц всё равно уже вывез деньги ПФ за рубеж

    КПРФ против антинародного законопроекта (20.07.2018)

    Часть 2. Поиск ассоциативных правил в XML-данных

    Поиск ассоциативных правил в статических и динамических XML-документах

    Серия контента:

    Этот контент является частью # из серии # статей: Интеллектуальный анализ XML-данных

    Этот контент является частью серии: Интеллектуальный анализ XML-данных

    Следите за выходом новых статей этой серии.

    Другие статьи этого цикла

    XML все больше становится предпочтительным языком представления, хранения данных и обмена данными во многих областях. Ввиду быстрого роста объемов информации, представленной в XML-формате, люди ищут рациональные методы решения задач хранения и анализа XML-документов. В первой статье этого цикла, «Несколько подходов к интеллектуальному анализу XML-данных», мы рассмотрели некоторые методы поиска скрытых знаний в XML-документах.

    Из этой статьи вы узнаете об особенностях поиска ассоциативных правил XML (в отличие от поиска ассоциативных правил в реляционных данных). Мы также рассмотрим метод оценки достоверности ассоциативных правил XML, полученных из XML-документов, содержание которых меняется со временем. Эти различия и новый метод анализа данных XML иллюстрируются на нескольких примерах.

    Поиск ассоциативных правил в реляционных данных

    В первой части обсуждались ассоциативные правила, введенные Агравалом и Срикантом в 1993 году (Agrawal and Srikant, см. раздел Ресурсы) для реляционных данных с целью определения интересных соотношений, которые можно извлечь из набора транзакций при анализе потребительской корзины. Алгоритм для извлечения этого типа знаний называется алгоритмом Apriori. В нем используются понятия поддержки и достоверности.

    Если есть набор отдельных элементов I и набор транзакций D, где любая транзакция T из D содержит только элементы из I, ассоциативным правилом R называется импликация «X к Y,» где X и Y ― не связанные между собой элементы из I. Правило R имеет поддержку S в D, если s% транзакций из D содержат оба элемента X и Y, и достоверность c, если c% транзакций из D, содержащих X, содержат также и Y.

    Например, ассоциативным правилом при анализе потребительской корзины будет: «Те, кто покупает продукт X, также покупают продукт Y, и это происходит в s% транзакций с достоверностью c%».

    Транзакции и элементы при реляционном подходе

    Понятие ассоциативных правил было введено для реляционных данных. В этом контексте транзакция представляет собой запись в таблице, а элемент — значение атрибута таблицы. Следовательно, набор транзакций представляет собой набор записей с одними и теми же атрибутами (столбцы и поля таблицы).

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

    Рисунок 1. Набор транзакций и элементов при реляционном подходе

    Поиск ассоциативных правил в XML

    Поиск ассоциативных правил в XML-документах отличается от поиска правил в реляционных данных, потому что в XML-формате информация может быть структурирована по-разному. Как правило, поиск ассоциативных правил XML означает поиск отношения между составными частями одного или нескольких XML-документов.

    Транзакции и элементы ассоциативных правил XML

    В работах по анализу статических XML-документов используются концепции транзакций и элементов XML-данных. Набор транзакций представляет собой список сложных узлов, сформированных посредством запросов к XML-документам по определенным путям; один сложный узел образует транзакцию. Элементы – это простые узлы, дочерние по отношению к узлу транзакции.

    В реляционных данных транзакция, извлеченная из таблицы, всегда содержит фиксированное количество элементов: число атрибутов, или столбцов, таблицы. XML-транзакция может иметь различное количество элементов в зависимости от уровня вложенности в документ и XML-схемы. Все вложенные пути в XML-документе, начиная с корня, можно представить как записи. Для любого узла документа каждый потомок рассматривается как запись, относящаяся к другим записям, расположенным на той же глубине или имеющим аналогичные теги (подробнее см. в разделе Ресурсы).

    На рисунке 2 показан пример, где каждый узел (здесь Джон Браун и Мелисса Уайт) – это транзакции, а каждый узел

    — элемент. Каждая транзакция staff_member содержит одну или несколько публикаций под именем соответствующего сотрудника. Каждая публикация содержит элементы publi_what, publi_where и publi_when. (см. текстовую версию XML-документа из рисунка 2.)

    Рисунок 2. Транзакции и элементы в XML-документе

    Контекст, тело и голова ассоциативных правил XML

    Контекст ассоциативных правил XML ― это анализируемые разделы XML-документов. Иногда нет необходимости анализировать всю информацию, содержащуюся в XML-документе. Следовательно, выбор контекста зависит от способности пользователей определить ограничения для множества XML-транзакций.

    На рисунке 3 показан пример выделения контекста. Для анализа выбираются только те транзакции, которые относятся к сотрудникам, опубликовавшим работы после 2006 года. В данном случае только Меллисса Уайт публиковалась после 2006 года.

    Рисунок 3. Выбор контекста в XML-документе

    Если ассоциативное правило XML является импликацией X к Y (аналогично реляционному подходу, но между двумя сложными XML-узлами), то X — это тело правила, а Y — его голова. Тело и голова всегда определяются в контексте правила. Аналогично, поддержка и достоверность правила рассчитываются по отношению к определенному контексту.

    Предположим, что контекст транзакций, отраженных на рисунке 3, охватывает всех сотрудников, которые публиковались после 2000, а не 2006 года. На рисунке 4 показан пример тела и головы того ассоциативного правила XML, в котором найдена гипотетическая связь между

    (значение «Data mining book» – это тело правила) и

    (значение «ABC publishing» – голова правила).

    Рисунок 4. Тело и голова в XML-документе

    Примеры ассоциативных правил XML

    На рисунке 5 показан пример XML-документа (department.xml) в виде дерева. Документ содержит данные о научных публикациях студентов и сотрудников, включая сведения о том, что, где и когда они публиковали. В целях рассмотрения общих концепций поиска ассоциативных правил XML предположим, что узлы и пусты, так что это статический, а не динамический XML-документ.

    Рисунок 5. Статический XML-документ в виде дерева

    Следующие два ассоциативных правила XML иллюстрируют понятия транзакции, элемента, контекста, тела и головы правила с использованием документа, показанного на рисунке 5.

    Пример 1 ассоциативного правила XML Предположим, что нужно найти ассоциативные правила в информации о научных публикациях сотрудников, публиковавшихся после 2005 года. Пусть получено следующее правило:

    «Сотрудники, публиковавшиеся после 2005 года в журнале XYZ, также ведут проекты в области ABC».

    Рисунок 6 иллюстрирует концепции этого примера:

    • контекст содержит все сложные узлы , потому что требовалось найти публикации сотрудников, но не студентов;
    • выбор контекста означает выбор тех записей о публикациях, в которых значение

    больше 2005;

  • каждый узел — это транзакция; узел сложный и имеет другие дочерние узлы;
  • все простые узлы в составе сложного узла , относящиеся к научным публикациям и проектам, являются элементами – то есть узлами на следующих путях:
    • staff/project/collab;
    • узлы на пути staff/publication/publi_where образуют голову правила;
    • узлы на пути staff/project/domain образуют тело правила.

      Рисунок 6. Ассоциативные правила XML в примере 1

      «Студенты, публиковавшиеся в издании ABC, также сотрудничают с сотрудниками по научно-исследовательским проектам.

    • контекст содержит все сложные узлы и , потому что не требовалось искать публикации только сотрудников или только студентов;
    • никакого выбора контекста нет, потому что рассматривается весь контекст, определенный выше;
    • каждый сложный узел

    является транзакцией;

  • все простые узлы в составе сложных узлов и , относящиеся к научным публикациям и проектам, являются элементами, или узлами на следующих путях:
    • student/publication/publi_what;
    • student/publication/publi_where;
    • student/publication/publi_when;
    • staff/publication/publi_what;
    • staff/publication/publi_where;
    • staff/publication/publi_when;
    • staff/project/name;
    • staff/project/domain;
    • узлы на пути student/publication/publi_where образуют голову правила;
    • узлы на пути staff/project/collab образуют тело правила.

      Рисунок 7. Ассоциативные правила XML в примере 2

      Как видно из примеров 1 и 2, концепции транзакции и элемента при поиске ассоциативных правил в XML-документах обладают гибкостью.

      Пример документа, показанного на рисунке 5, рисунке 6 и рисунке 7, считается статическим, и элементы и игнорируются. Предположим, что эти два узла не пустые, а получают значения в зависимости от срока действия XML-документа. Например, каждый год может создаваться новая версия документа department.xml. Версия 2007 года будет иметь 01/01/2007 и 31/12/2007 . Ассоциативные правила, описанные выше, будут справедливы только для 2007 года. Любые старые правила (обнаруженные в версиях XML-документа за предыдущие годы) могут быть или не быть таким же, как правила 2007 года. Таким образом, ассоциативные правила для динамических (многоверсионных) XML-документов требуют особого способа оценки их действительности в последующих версиях документа. Эти правила называются динамическими и обсуждаются в следующем разделе.

      Динамические ассоциативные правила XML

      В реальных приложениях ассоциативные правила, выявленные в первоначальной версии динамических XML-документов, зависят от количества и интенсивности изменений между последовательными версиями документа. Об ассоциативных правилах динамических XML-документов после ряда изменений можно судить по влиянию исторических изменений на первоначальные правила.

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

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

      Рассматривая влияние изменений на первоначальный набор действительных правил, можно определить новые действительные ассоциативные правила XML после ряда изменений без повторного применения полного алгоритма поиска ассоциативных правил к окончательной версии. На рисунке 8 показан динамический XML-документ, используемый для этого примера. Он содержит каталог интернет-магазина за четыре дня. Каталог каждый день разный, так как он отражает деятельность продавцов и покупателей на сайте (добавляются или удаляются товары, меняются цены, обновляются описания и т.д.). (См. текстовую версию рисунка 8.)

      Рисунок 8. Динамический XML-документ четырех последовательных версий

      Цель этого примера заключается в том, чтобы показать шаги по поиску динамических ассоциативных правил XML – а не то, как были найдены первоначальные правила XML (до внесения изменений). Первоначальные правила можно найти, используя любой известный алгоритм поиска ассоциативных правил XML.

      Шаг 1: Подготовка

      Для данного примера предположим, что этот шаг был выполнен в момент времени T0:

    • минимальная поддержка и достоверность, принятые для правил, установлены как min_sup = 22%, min_conf = 30%, prov_sup = 18% и prov_ conf = 20%;
    • были обнаружены следующие два ассоциативных правила XML:
      • Re = «когда в продаже есть аудиоплеер, в продаже есть также мобильный телефон» с поддержкой (Re) = 25% и достоверностью (Re) = 33%;
      • Rp = «когда в продаже есть набор инструментов для барбекю, в продаже есть также чемодан» с поддержкой (Rp) = 20% и достоверностью (Rp) = 25%.
      • Предположим, что общее число транзакций, проанализированных для получения вышеуказанных правил, составило 20.

      Из этих результатов видно, что:

      Re — это действительное правило, потому что min_sup

    Ресурсы для скачивания

    Похожие темы

    • Оригинал статьи
    • Часть 1. Несколько подходов к интеллектуальному анализу XML-данных: в первой статье этого цикла содержится введение в добычу скрытых знаний из XML-документов. Она знакомит читателей с интеллектуальным анализом данных, иерархической структурой информации и связями между элементами.
    • Часть 3. Кластеризация XML-документов для повышения качества интеллектуального анализа данных: безызбыточная методология перерасчета новых кластеров XML-документов после их изменения. Метод и его применение иллюстрируются наглядным примером.
    • Extracting Variable Knowledge from Multi-Versioned XML Documents (L.I. Rusu, W. Rahayu, and D. Taniar, 2006): о новом методе определения того, как знания, выявленные в первоначальных XML-документах, меняются во времени при изменении содержания и структуры документов.
    • Mining Changes from Versions of Dynamic XML Documents (L.I. Rusu, W. Rahayu, and D. Taniar, 2006): о простом методе поиска ассоциативных правил по изменениям между версиями динамических XML-документов с использованием информации, содержащейся в сводном дельта-документе.
    • Mining Association Rules between Sets of Items in Large Databases (R. Agrawal, T. Imielinski, and A.N. Swami, 1993): об эффективном алгоритме, который находит все значимые ассоциативные правила между элементами крупной базы данных.
    • Deriving General Association Rules from XML Data (Q. Ding, K. Ricords, and J. Lumpkin, 2003): авторы рассматривают задачу извлечения общих ассоциативных правил из XML-данных и предлагают подход к решению этой задачи.
    • Комментарии

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

      2..3. Задача поиска ассоциативных правил.

      Поиск ассоциативных правил является одним из самых популярных приложений Data Mining. Суть задачи заключается в определении часто встречающихся наборов объектов в большом множестве таких наборов. Данная задача является частным случаем задачи классификации. Первоначально она решалась при анализе тенденций в поведении покупателей в супермаркетах. Анализу подвергались данные о совершаемых ими покупках, которые покупатели складывают в тележку (корзину). Это послужило причиной второго часто встречающегося названия — анализ рыночных корзин (Basket Analysis). При анализе этих данных интерес, прежде всего, представляет информация о том, какие товары покупаются вместе, в какой последовательности, какие категории потребителей, какие товары предпочитают, в какие периоды времени и т. п. Такая информация позволяет более эффективно планировать закупку товаров, проведение рекламной кампании и т. д.

      Например, из набора покупок, совершаемых в магазине, можно выделить следующие наборы товаров, которые покупаются вместе:

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

      Задача поиска ассоциативных правил актуальна не только в сфере торговли. Например, в сфере обслуживания интерес представляет, какими услугами клиенты предпочитают пользоваться в совокупности. Для получения этой информации задача решается применительно к данным об услугах, которыми пользуется один клиент в течение определенного времени (месяца, года). Это помогает определить, например, как наиболее выгодно составить пакеты услуг, предлагаемых клиенту.

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

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

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

      2.4. Задача кластеризации

      Задача кластеризации состоит в разделении исследуемого множества объектов на группы «похожих» объектов называемых кластерами. Слово кластер английского происхождения переводится как сгусток, пучок, группа. Родственные понятия, используемые в литературе,- класс, таксон, сгущение. Часто решение задачи разбиения множества элементов на кластеры называют кластерным анализом.

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

      Концептуально сегментирование основано на предпосылке, что все потребители разные. У них разные потребности, разные требования к товару, они ведут себя по-разному: в процессе выбора товара, в процессе приобретения товара, в процессе использования товара, в процессе формирования реакции товара. В связи с этим необходимо по-разному подходить к работе с потребителями: предлагать им различные по характеристикам товары, по-разному продвигать и продавать товары. Для того чтобы определить, чем отличаются потребители друг от друга и как эти отличия отражаются на требованиях к товару, и производится сегментирование потребителей.

      В маркетинге критериями сегментации являются: географическое местоположение, социально-демографические характеристики, мотивы совершения покупки и т. п.

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

      Для научных исследований изучение результатов кластеризации, а именно выяснение причин, по которым объекты объединяются в группы, способно открыть новые перспективные направления. Традиционным примером, который обычно приводят для этого случая, является периодическая таблица элементов. В 1869 г. Дмитрий Менделеев разделил 60 известных в то время элементов на кластеры или периоды. Элементы, попавшие в одну группу, обладали схожими характеристиками. Изучение причин, по которым элементы разбивались на явно выраженные кластеры, в значительной степени определило приоритеты научных изысканий на годы вперед. Но лишь спустя 50 лет квантовая физика дала убедительные объяснения периодической системы.

      Кластеризация отличается от классификации тем, что для проведения анализа не требуется иметь выделенную зависимую переменную. С этой точки зрения она относится к классу unsupervised learning. Эта задача решается на начальных этапах исследования, когда о данных мало что известно. Ее решение помогает лучше понять данные, и с этой точки зрения задача кластеризации является описательной задачей.

      Для задачи кластеризации характерно отсутствие каких-либо различий как между переменными, так и между объектами. Напротив, ищутся группы наиболее близких, похожих объектов. Методы автоматического разбиения на кластеры редко используются сами по себе, просто для получения групп схожих объектов. После определения кластеров применяются другие методы Data Mining, для того чтобы попытаться установить, а что означает такое разбиение, чем оно вызвано.

      Кластерный анализ позволяет рассматривать достаточно большой объем информации и резко сокращать, сжимать большие массивы информации, делать их компактными и наглядными.

      Отметим ряд особенностей, присущих задаче кластеризации.

      Во-первых, решение сильно зависит от природы объектов данных (и их атрибутов). Так, с одной стороны, это могут быть однозначно определенные, четко количественно очерченные объекты, а с другой — объекты, имеющие вероятностное или нечеткое описание.

      Во-вторых, решение значительно зависит также и от представления кластеров и предполагаемых отношений объектов данных и кластеров. Так, необходимо учитывать такие свойства, как возможность/невозможность принадлежности объектов нескольким кластерам. Необходимо определение самого понятия принадлежности кластеру: однозначная (принадлежит/не принадлежит), вероятностная (вероятность принадлежности), нечеткая (степень принадлежности).

      Поиск ассоциативных правил

      Обучение для трейдеров:

      Методы Data Mining и Machine Learning позволяют автоматизировать работу трейдера-исследователя, который пытается найти закономерности в котировках финансовых инструментов, чтобы использовать эти закономерности в своей торговле.

      Исследуем, как ведут себя дневные свечи фьючерса S&P 500 в зависимости от дня недели.

      Загрузим данные по индексу S&P 500 с сайта Yahoo Finance:

      Разделим данные по дням недели. Сначала выясним, какой тип имеет индекс полученного временного ряда:

      Для работы с датами в Python имеется модуль datetime.date . Воспользуемся функцией isocaledar, которая для заданной даты возвращает три числа: год, номер недели в году (начиная с 1) и номер дня недели (начиная с понедельника, которому соответсвует число 1). Первой неделей считается та, что содержит четверг.

      Число записей (строк) в полученном наборе данных можно узнать с помощью стандартной функции len() :

      Далее нам потребуется список названий дней недели:

      Для доступа к отдельных записям временного ряда будем использовать функцию ix() :

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

      Нули соответствуют выходным дням (праздникам) или тем дням, когда изменение цены закрытия не превысило установленный порог.

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

      Преобразуем полученный динамический список списков x в матрицу, чтобы ускорить вычисления:

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

      Теперь попытаемся выяснить, сколько раз в понедельник цена закрытия упала по сравнению с ценой закрытия предыдущего дня:

      Если бы вместо матрицы numpy мы использовали обычный список Python, то вместо row.item(0) мы бы написали row[0] .

      Заметим, что можно было организовать вычисления другим способом:

      Теперь проведём то же самое исследование для всех дней недели: сколько раз цена росла, сколько раз падала и сколько раз изменение цены закрытия не превысило заданный порог.

      Небольшая разница в числах, полученных вторым способом, объясняется тем, что мы выбрали другой способ подсчёта дней. В первом способе мы учитываем все дни недели (кроме субботы и воскресенья), независимо от того, проводилась в эти дни торговля или нет, поэтому все праздники увеличивают число случаев, когда изменение цены не превысило заданный порог. Во втором способе мы считаем только те дни, в которые фьючерс торговался (праздничные дни в наборе данных, полученных с сервера yahoo Financе, отсутствуют).

      Является ли это правило статистически значимым или отличие от 50% объясняется случайным отклонением? На этот вопрос отвечает критерий знаков:

      Если бы из 49 случаев, когда цена в понедельник росла, правило выполнилось хотя бы 32 раза, то мы посчитали бы такое правило статистически значимым (при том же выбранном уровне значимости 0.05), поскольку полученное p-значение оказалось бы меньше 0.05:

      Кроме критерия знаков, можно воспользоваться критерием \(\chi^2\) Пирсона. Он позволяет опровергнуть гипотезу о независимости двух случайных переменных. Для этого построим таблицу сопряжённости:

      Мы уже знаем, сколько раз цена в четверг росла или падала при условии, что рассматриваемый сигнал наблюдался (в понедельник цена росла). Но нам ещё надо выяснить, как часто в четверг цена росла или падала при отсутствии сигнала (т.е. в те недели, когда цена в понедельник падала). Сделаем это.

      Тест Пирсона реализован в пакете scipy.stats в виде функции chi2_contingency() :

      Второе число в результате – это p-значение. Если оно меньше наперёд заданного уровня значимости (обычно выбирают 0.05), то гипотеза о независимости рассматриваемых переменных отклоняется, т.е. считается, что между переменными имеется статистическая связь (которая может быть обусловлена причинно-следственной связью или нет, это уже другой вопрос). В данном случае можно считать, что связь не выявлена.

      Как видим, оба критерия (и тест знаков, и тест Пирсона) дали одинаковый результат. Поэтому нам придётся продолжить исследование, мы ещё надеемся найти какую-нибудь закономерность.

      Запрограммируем функцию, которая принимает два числа (номера дней недели: 1 — понедельник и т.д.) и вычисляет поддержку, достоверность и статистическую значимость соответствующего правила. Рост цены в заданный день будем кодировать положительным числом, а падение – отрицательным. Например, два параметра -2 и 3 будут означать, что мы проверяем правило: “падение цены во вторник влечёт за собой рост цены в среду”. (Теперь понятно, почему мы были вынуждены считать понедельник единицей, а не нулём?)

      Далее нам потребуется функция, которая вычисляет знак числа, т.е. возвращает 1 для положительного аргумента, -1 – для отрицательного:

      Поиск ассоциативных правил.

      1. Постановка задачи 6.1.1. Формальная постановка задачи

      •Одной из наиболее распространенных задач анализа данных является определение часто встречающихся наборов объектов в большом множестве наборов.

      Опишем эту задачу в обобщенном виде. Для этого обозначим объекты, составляющие исследуемые наборы (itemsets), следующим множеством:

      ij — объекты, входящие в анализируемые наборы; п — общее количество объектов.

      В сфере торговли, например, такими объектами являются товары, представнные в прайс-листе (табл. 6.1).

      Они соответствуют следующему множеству объектов:

      Наборы объектов из множества I, хранящиеся в БД и подвергаемые анализу, называются транзакциями. Опишем транзакцию как подмножество множества I:

      Такие транзакции в магазине соответствуют наборам товаров, покупаемых потребителем и сохраняемых в БД в виде товарного чека или накладной. В них перечисляются приобретаемые покупателем товары, их цена, количество и др. Например, следующие транзакции соответствуют покупкам, совершаемым потребителями в супермаркете:

      Набор транзакций, информация о которых доступна для анализа, обозначим следующим множеством:

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

      Например, в магазине таким множеством будет:

      Для использования методов Data Mining множество D может быть представлено в виде табл. 6.2.

      Множество транзакций, в которые входит объект ij,обозначим следующим образом:

      В данном примере множеством транзакций, содержащих объект вода, является следующее множество:

      Некоторый произвольный набор объектов (itemset) обозначим следующим образом:

      Набор, состоящий из к объектов, называется kэлементным набором (в данном примере это 2-элементный набор).

      Множество транзакций, в которые входит набор F, обозначим следующим образом:

      В данном примере:

      Отношение количества транзакций, в которое входит набор F, к общему количеству транзакций называется поддержкой (support) набора F и обозначается Supp(F):

      Для набора <кокосы, вода>поддержка будет равна 0,5, т. к. данный набор входит в две транзакции (с номерами 1 и 2), а всего транзакций 4.

      При поиске аналитик может указать минимальное значение поддержки интересующих его наборов Suppmin. Набор называется частым (large itemset), если значение его поддержки больше минимального значения поддержки, задан­ного пользователем:

      Таким образом, при поиске ассоциативных правил требуется найти множество всех частых наборов:

      В данном примере частыми наборами при Suppmin = 0,5 являются следующие: