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

Ассоциативное правило имеет вид: "Из события A следует событие B".

Алгоритм AIS.

В алгоритме AIS кандидаты множества наборов генерируются и подсчитываются "на лету", во время сканирования базы данных.

Алгоритм SETM.

SETM также формирует кандидатов "на лету", основываясь на преобразованиях базы данных. Чтобы использовать стандартную операцию объединения языка SQL для формирования кандидата, SETM отделяет формирование кандидата от их подсчета.

Неудобство алгоритмов AIS и SETM - излишнее генерирование и подсчет слишком многих кандидатов, которые в результате не оказываются часто встречающимися.

 

Для улучшения их работы был предложен алгоритм Apriori.

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

- Формирование кандидатов - этап, на котором алгоритм, сканируя базу данных, создает множество i-элементных кандидатов (i - номер этапа).

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

 

Методы визуализации

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

· представлять пользователю информацию в наглядном виде;

· компактно описывать закономерности, присущие исходному набору данных;

· снижать размерность или сжимать информацию;

· восстанавливать пробелы в наборе данных;

· находить шумы и выбросы в наборе данных.

Методы визуализации, в зависимости от количества используемых измерений, принято классифицировать на две группы [22]:

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

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

Наиболее известные способы многомерного представления информации:

· параллельные координаты;

· "лица Чернова" - основная идея представления информации состоит в кодировании

значений различных переменных в характеристиках или чертах человеческого лица;

· лепестковые диаграммы.

8. Этапы процесса Data Mining: анализ предметной области; · постановка задачи; · подготовка данных; построение моделей;· проверка и оценка моделей;· выбор модели;· применение модели;· коррекция и обновление модели.

 

Этап 1. Анализ предметной области

Исследование - это процесс познания определенной предметной области, объекта или явления с определенной целью.

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

 

Например, при решении задачи "Выдавать ли кредит?" важными являются все данные про частную жизнь (дети, образования и т.д).

 

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

 

Этап 2. Постановка задачи

Постановка задачи Data Mining включает следующие шаги:

· формулировка задачи;

· формализация задачи.

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

 

Этап 3. Подготовка данных

Цель этапа: разработка базы данных для Data Mining.

На этап подготовки данных, по некоторым оценкам, может быть потрачено до 80% всего времени, отведенного на проект.

1. Определение и анализ требований к данным

На этом этапе осуществляется моделирование данных, т.е. определение и анализ требований к данным, которые необходимы для осуществления Data Mining. При

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

Сбор данных

Если нет ХД. В этом случае источником для исходных данных являются

оперативные, справочные и архивные БД, т.е. данные из существующих информационных систем.

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

 

Предварительная обработка данных

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

Оценивание качества данных. Данные могут быть высокого качества и низкого качества, последние - это так называемые грязные или "плохие" данные (пропущенные значения, дубликаты данных, шумы и выбросы).

Данные высокого качества - это полные, точные, своевременные данные, которые

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

Рассмотрим наиболее распространенные виды грязных данных:

Пропущенные значения (Missing Values).

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

· данные вообще не были собраны (например, при анкетировании скрыт возраст);

· некоторые атрибуты могут быть неприменимы для некоторых объектов (например,

атрибут "годовой доход" неприменим к ребенку).

Шумы и выбросы.

Выбросы - резко отличающиеся объекты или наблюдения в наборе данных.

Задача аналитика - не только их обнаружить, но и оценить степень их влияния на

результаты дальнейшего анализа - информативной часть либо ошибки.

 

4. построение моделей;·

 

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

Аналитик создает модель как подобие изучаемого объекта. Модели могут быть записаны в виде различных изображений, схем, математических формул и т.д.

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

 

Для построения моделей используются различные методы и алгоритмы Data Mining.

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

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

 

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

Постановка задачи формализует суть задачи, так, наличие входных и выходных

переменных при решении задачи классификации определяет выбор одного из методов "обучение с учителем"(при наличии лишь вх. переменных - "обучение без учителя").

 

Этапы подготовки данных, построения модели, оценки модели и выбора лучшей

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

· подготовка данных (если причина некорректности модели - в данных);

· построение модели (если причина некорректности - во внутренних параметрах самой

модели).