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

 

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

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

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

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

Секвенциальный анализ широко используется, например, в телекоммуникационных компаниях, для анализа данных об авариях на различных узлах сети. Информация о последовательности совершения аварий может помочь в обнаружении неполадок и предупреждении новых аварий. Например, если известна последовательность сбоя: { e₃, e₈, e₆, e₁₁, e₁₂, …}, где e_i – код сбоя, то на основании факта о появления сбоя e₈ можно сделать вывод о скором появлении сбоя e₆. Зная это, можно принять профилактические меры, устраняющие причины возникновения сбоя. Если дополнительно обладать и знаниями о времени между сбоями, то можно предсказать не только факт его появления, но и время, что зачастую не менее важно.

Модели Data Mining

 

Цель технологии Data Mining состоит в нахождении в данных таких знаний, которые не могут быть найдены обычными методами. На основании приведенной ранее классификации задач Data Mining можно выделить два типа моделей, используемых для представления этих знаний: предсказательные (predictive) и описательные (descriptive).

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

 

К таким моделям относятся:

· модели классификации – описывают правила или набор правил, в соответствии с которыми можно отнести описание любого нового объекта к одному из классов. Такие правила строятся на основании информации о существующих объектах путем разбиения их на классы;

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

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

К таким моделям относятся:

· регрессионные модели – описывают функциональные зависимости между зависимыми и независимыми показателями и переменными в понятной человеку форме. Стоит заметить, что такие модели описывают функциональную зависимость не только между непрерывными числовыми параметрами, но и между категориальными параметрами;

· модели кластеров – описывают группы (кластеры), на которые можно разделить объекты, данные о которых подвергаются анализу. Группируются объекты (наблюдения, события) на основе данных (свойств), описывающих сущность объектов. Объекты внутри кластера должны быть «похожими» друг на друга и отличаться от объектов, вошедших в другие кластеры. Чем сильнее «похожи» объекты внутри кластера и чем больше отличий между самими кластерами, тем точнее кластеризация;

· модели исключений – описывают исключительные ситуации в записях (например, отдельных пациентов врача), которые резко отличаются чем-либо от основного множества записей (группы больных). Знание исключений может быть использовано двояким образом. Возможно, эти записи представляют собой случайный сбой, например ошибки операторов, вводивших данные в компьютер. Подобные ошибки следует исключать из анализа. С другой стороны, отдельные, исключительные записи могут представлять самостоятельный интерес для исследования, так как они могут указывать, например, на некоторые редкие, но важные аномальные заболевания. Даже сама идентификация этих записей, не говоря уже об их последующем анализе и детальном рассмотрении, может оказаться очень полезной для понимания сущности изучаемых объектов или явлений;

· итоговые модели – служат для выявления ограничений на данные анализируемого массива. Построение итоговых моделей состоит в нахождении каких-либо фактов, которые верны для всех или почти всех записей в изучаемой выборке данных, но которые достаточно редко встречались бы во всем мыслимом многообразии записей данного формата и, например, характеризовались идентичными распределениями значений полей. Например, при изучении выборки по пациентам не старше 30 лет, перенесшим инфаркт миокарда, обнаруживается, что все пациенты, описанные в этой выборке, либо курят более 5 пачек сигарет в день, либо имеют вес не ниже 95 кг. Подобные ограничения важны для понимания данных массива, по сути дела это новое знание, извлеченное в результате анализа. Можно сказать, что неявно решается задача классификации, хотя фактически задан только один класс, представленный имеющимися данными;

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

Для построения рассмотренных моделей используются различные методы и алгоритмы Data Mining. Ввиду того, что технология Data Mining развивалась и развивается на стыке таких дисциплин, как статистика, теория информации, машинное обучение и теория баз данных, вполне закономерно, что большинство алгоритмов и методов Data Mining были разработаны на основе различных технологий и концепций.

Методы Data Mining

 

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

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

При использовании технологии дистилляции шаблонов один образец (шаблон) информации извлекается из исходных данных и преобразуется в некие формальные конструкции, вид которых зависит от конкретного используемого метода Data Mining. На этапах прогнозирования и анализа исключений используются полученные формальные конструкции, которые значительно компактнее самих баз данных. К методам данной группы относят различные логические методы (нечеткие запросы и анализы, символьные правила, деревья решений, генетические алгоритмы), методы визуализации, методы кросс-табуляции (байесовские сети доверия, кросс-табличная визуализация), статистические методы, методы, основанные на нейронных сетях.

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

Методы Data Mining также можно классифицировать по задачам Data Mining. В соответствии с такой классификацией можно выделить две группы. Первая из них – это разделение методов Data Mining на решающие задачи сегментации (т.е. задачи классификации и кластеризации) и задачи прогнозирования.

Если классифицировать методы в соответствии с используемыми в них моделями, то получаем разделение на методы, направленные на получение описательных результатов, и методы, направленные на получение результатов прогнозирования.

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

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