Технология анализа data mining. Методы Data Mining. Методы исследования данных в Data Mining

Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже

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

Подобные документы

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

контрольная работа , добавлен 14.06.2013


Основы для проведения кластеризации. Использование Data Mining как способа "обнаружения знаний в базах данных". Выбор алгоритмов кластеризации. Получение данных из хранилища базы данных дистанционного практикума. Кластеризация студентов и задач.

курсовая работа , добавлен 10.07.2017


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

контрольная работа , добавлен 02.09.2010


Data mining, developmental history of data mining and knowledge discovery. Technological elements and methods of data mining. Steps in knowledge discovery. Change and deviation detection. Related disciplines, information retrieval and text extraction.

доклад , добавлен 16.06.2012


Data Mining как процесс поддержки принятия решений, основанный на поиске в данных скрытых закономерностей (шаблонов информации). Его закономерности и этапы реализации, история разработки данной технологии, оценка преимуществ и недостатков, возможности.

эссе , добавлен 17.12.2014


Классификация задач DataMining. Создание отчетов и итогов. Возможности Data Miner в Statistica. Задача классификации, кластеризации и регрессии. Средства анализа Statistica Data Miner. Суть задачи поиск ассоциативных правил. Анализ предикторов выживания.

курсовая работа , добавлен 19.05.2011


Перспективные направления анализа данных: анализ текстовой информации, интеллектуальный анализ данных. Анализ структурированной информации, хранящейся в базах данных. Процесс анализа текстовых документов. Особенности предварительной обработки данных.

реферат , добавлен 13.02.2014


Классификация задач Data Mining. Задача кластеризации и поиска ассоциативных правил. Определению класса объекта по его свойствам и характеристикам. Нахождение частых зависимостей между объектами или событиями. Оперативно-аналитическая обработка данных.

контрольная работа , добавлен 13.01.2013

Министерство образования и науки РФ

Федеральное государственное бюджетное образовательное учреждение высшего профессионального образования

«НАЦИОНАЛЬНЫЙ ИССЛЕДОВАТЕЛЬСКИЙ ТОМСКИЙ ПОЛИТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ»

Институт Кибернетики

Направление Информатика и вычислительная техника

Кафедра ВТ

Контрольная работа

по дисциплине информатика и вычислительная техника

Тема: Методы Data Mining

Введение

Data Mining. Основные понятия и определения

1 Этапы в процессе интеллектуального анализа данных

2 Компоненты систем интеллектуального анализа

3 Методы исследования данных в Data Mining

Методы Data Mining

1 Вывод ассоциативных правил

2 Нейросетевые алгоритмы

3 Методы ближайшего соседа и k-ближайших соседей

4 Деревья решений

5 Алгоритмы кластеризации

6 Генетические алгоритмы

Сферы применения

Производители средств Data Mining

Критика методов

Заключение

Список литературы

Введение

Результатом развития информационных технологий является колоссальный объем данных, накопленных в электронном виде, растущий быстрыми темпами. При этом данные, как правило, обладают разнородной структурой (тексты, изображения, аудио, видео, гипертекстовые документы, реляционные базы данных). Накопленные за длительный срок данные могут содержать в себе закономерности, тенденции и взаимосвязи, являющиеся ценной информацией при планировании, прогнозировании, принятии решений, контроле за процессами. Однако человек физически не способен эффективно анализировать такие объемы неоднородных данных. Методы традиционной математической статистики долгое время претендовали на роль основного инструмента анализа данных. Однако они не позволяют синтезировать новые гипотезы, а могут использоваться лишь для подтверждения заранее сформулированных гипотез и “грубого” разведочного анализа, составляющего основу оперативной аналитической обработки данных (online analytical processing, OLAP). Нередко именно формулировка гипотезы оказывается самой сложной задачей при проведении анализа для последующего принятия решений, поскольку далеко не все закономерности в данных очевидны с первого взгляда. Поэтому технологии интеллектуального анализа данных (Data mining) рассматриваются как одна из самых важных и многообещающих тем для исследований и применения в отрасли информационных технологий. Под интеллектуальным анализом данных в этом случае понимается процесс определения новых, корректных и потенциально полезных знаний на основе больших массивов данных. Так, MIT Technology Review охарактеризовал Data Mining как одну из десяти развивающихся технологий, которые изменят мир.

1. Data Mining. Основные понятия и определения

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

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

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

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

Эта концепция анализа данных, предполагает, что:

§ данные могут быть неточными, неполными (содержать пропуски), противоречивыми, разнородными, косвенными, и при этом иметь гигантские объёмы; поэтому понимание данных в конкретных приложениях требует значительных интеллектуальных усилий;

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

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

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

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

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

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

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

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

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

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

1.1 Этапы в процессе интеллектуального анализа данных

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

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

2. Сбор данных.

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

a. Очистка данных - исключение противоречий и случайных "шумов" из исходных данных

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

4. Анализ данных. В рамках данного этапа применяются алгоритмы интеллектуального анализа с целью извлечения паттернов.

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

Использование новых знаний.

1.2 Компоненты систем интеллектуального анализа

Обычно в системах интеллектуального анализа данных выделяются следующие главные компоненты:

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

2. Сервер базы данных или хранилища данных. Указанный сервер отвечает за извлечение существенных данных на основании пользовательского запроса.

База знаний. Это знания о предметной области, которые указывают, как проводить поиск и оценивать полезность результирующих паттернов.

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

Модуль оценки паттернов. Данный компонент вычисляет меры интереса или полезности паттернов.

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

1.3 Методы исследования данных в Data Mining

Большинство аналитических методов, используемые в технологии Data Mining - это известные математические алгоритмы и методы. Новым в их применении является возможность их использования при решении тех или иных конкретных проблем, обусловленная появившимися возможностями технических и программных средств. Следует отметить, что большинство методов Data Mining были разработаны в рамках теории искусственного интеллекта. Рассмотрим наиболее широко употребляемые методы:

Вывод ассоциативных правил.

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

Выбор близкого аналога исходных данных из уже имеющихся исторических данных. Называются также методом «ближайшего соседа».

Деревья решений - иерархическая структура, базирующаяся на наборе вопросов, подразумевающих ответ «Да» или «Нет».

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

В следующей главе подробнее опишем вышеперечисленные методы.

2. Методы Data Mining

2.1 Вывод ассоциативных правил

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

Ассоциативные правила определяются как утверждения вида {X1,X2,…,Xn} -> Y, где подразумевается, что Y может присутствовать в транзакции при условии, что X1,X2,…,Xn присутствуют в этой же транзакции. Следует обратить внимание, что слово "может" подразумевает, что правило не является тождеством, а выполняется только с некоторой вероятностью. Кроме того, в качестве Y может выступать набор элементов, а не только один элемент. Вероятность нахождения Y в транзакции, в которой имеются элементы X1,X2,…,Xn, называется достоверностью (confidence). Процент транзакций, содержащих правило, от общего числа транзакций называется поддержкой (support). Уровень достоверности, который должна превышать достоверность правила, называется интересностью (interestingness).

Существуют различные типы ассоциативных правил. В простейшей форме ассоциативные правила сообщают только о наличии или отсутствии ассоциации. Такие правила называются булевыми ассоциативными правилами (Boolean Association Rule). Пример такого правила: «покупатели, которые приобретают йогурт, так же приобретают масло с низким уровнем жира».

Правила, которые собирают несколько ассоциативных правил вместе, называются мультиуровневые или обобщенные ассоциативные правила (Multilevel or Generalized Association Rules). При построении таких правил, элементы обычно группируются согласно иерархии, и поиск ведется на самом высоком концептуальном уровне. Например, "покупатели, которые приобретают молоко, так же приобретают хлеб". В этом примере, молоко и хлеб содержат иерархию различных типов и брендов, однако поиск на нижнем уровне не позволит найти интересные правила.

Более сложным типом правил являются количественные ассоциативные правила (Quantitative Association Rules). Этот тип правил ищется с применением количественных (например, цена) или категориальных (например, пол) атрибутов, и определен как {, ,…,} -> . Например, "покупатели, чей возраст находится между 30 и 35 годами с доходом более 75000 в год покупают машины стоимостью более 20000".

Вышеперечисленные типы правил не затрагивают тот факт, что транзакции, по своей природе, зависят от времени. Например, поиск до того, как продукт был выставлен на продажу или после того, как он исчез с рынка, неблагоприятно повлияет на пороговое значение поддержки. С учетом этого, в введена концепция атрибутного времени жизни в алгоритмах поиска временных ассоциативных правил (Temporal Association Rules).

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

С момента появления алгоритма Apriori, этот алгоритм является наиболее часто применяемым на первом шаге. Многие улучшения, например, по скорости и по масштабируемости, направлены на совершенствование алгоритма Apriori, на исправление его ошибочного свойства генерировать слишком много кандидатов на наиболее часто встречающиеся наборы элементов. Apriori генерирует наборы элементов используя только большие наборы, найденные на предыдущем шаге, без повторного рассмотрения транзакций. Модифицированный алгоритм AprioriTid улучшает Apriori за счет того, что использует базу данных только при первом проходе. При подсчетах на последующих шагах используются лишь данные, созданные при первом проходе и имеющие гораздо меньший размер, чем исходная база данных. Это приводит к колоссальному росту производительности. Дальнейшая усовершенствованная версия алгоритма, названная AprioriHybrid, может быть получена, если при нескольких первых проходах использовать Apriori, а затем, на более поздних проходах, когда k-ые наборы-кандидаты уже могут быть целиком размещены в памяти компьютера, переключатся на AprioriTid.

Дальнейшие усилия по улучшению алгоритма Apriori связаны с распараллеливанием алгоритма (Count Distribution, Data Distribution, Candidate Distribution и др.), его масштабированием(Intelligent Data Distribution, Hybrid Distribution), введение новых структур данных, таких как деревья часто встречающихся элементов(FP-growth).

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

2.2 Нейросетевые алгоритмы

Искусственные нейронные сети появились в результате применения математического аппарата к исследованию функционирования нервной системы человека с целью ее воспроизведения. А именно: способность нервной системы обучаться и исправлять ошибки, что должно позволить смоделировать, хотя и достаточно грубо, работу человеческого мозга. Основной структурной и функциональной частью нейронной сети является формальный нейрон (formal neuron), представленный на рис. 1, где x0 , x1,..., xn - компоненты вектора входных сигналов, w0 ,w1,...,wn - значения весов входных сигналов нейрона, а y - выходной сигнал нейрона.

Рис. 1. Формальный нейрон: синапсы (1), сумматор (2), преобразователь (3).

Формальный нейрон состоит из элементов 3 типов: синапсов, сумматора и преобразователя. Синапс характеризует силу связи между двумя нейронами.

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

Описанные выше формальные нейроны можно объединять таким образом, что выходные сигналы одних нейронов являются входными для других. Полученное множество связанных между собой нейронов называют искусственными нейронными сетями (artificial neural networks, ANN) или, коротко, нейронными сетями.

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

Входные нейроны (input nodes), на которые подаются входные сигналы. Такие нейроны нейроны имеют, как правило, один вход с единичным весом, смещение отсутствует, а значение выхода нейрона равно входному сигналу;

Выходные нейроны (output nodes), выходные значения которых представляют результирующие выходные сигналы нейронной сети;

Скрытые нейроны (hidden nodes), не имеющие прямых связей с входными сигналами, при этом значения выходных сигналов скрытых нейронов не являются выходными сигналами ИНС.

По структуре межнейронных связей различают два класса ИНС:

ИНС прямого распространения, в которых сигнал распространяется только от входных нейронов к выходным.

Рекуррентные ИНС - ИНС с обратными связями. В таких ИНС сигналы могут передаваться между любыми нейронами, вне зависимости от их расположения в ИНС.

Существуют два общих подхода к обучению ИНС:

Обучение с учителем.

Обучение без учителя.

Обучение с учителем (supervised learning) подразумевает использование заранее сформированного множества обучающих примеров. Каждый пример содержит вектор входных сигналов и соответствующий вектор эталонных выходных сигналов, которые зависят от поставленной задачи. Данное множество называют обучающей выборкой или обучающим множеством. Обучение нейронной сети направлено на такое изменение весов связей ИНС, при котором значение выходных сигналов ИНС как можно меньше отличаются от требуемых значений выходных сигналов для данного вектора входных сигналов.

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

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

2.3 Методы ближайшего соседа и k-ближайших соседей

В основе алгоритмов ближайших соседей (nearest neighbor algorithm) и k-ближайших соседей (k-nearest neighbor algorithm, KNN) лежит сходство объектов. Алгоритм ближайшего соседа выделяет среди всех известных объектов объект, максимально близкий (используется метрика расстояния между объектами, например, евклидова) к новому ранее неизвестному объекту. Главная проблема метода ближайшего соседа это его чувствительность к выбросам в обучающих данных.

Описанную проблему позволяет избегать алгоритм KNN, выделяющий среди всех наблюдений уже k-ближайших соседей, похожих на новый объект. На основе классов ближайших соседей выносится решение касательно нового объекта. Важной задачей данного алгоритма является подбор коэффициента k - количество записей, которые будут считаться похожими. Модификация алгоритма, при которой вклад соседа пропорционален расстоянию до нового объекта (метод k-взвешенных ближайших соседей) позволяет достичь большей точности классификации. Метод k ближайших соседей, так же, позволяет оценить точность прогноза. Например, все k ближайших соседей имеют один и тот же класс, то вероятность, что проверяемый объект будет иметь такой же класс, очень высока.

Среди особенностей алгоритма стоит отметить устойчивость к аномальным выбросам, так как вероятность попадания такой записи в число k-ближайших соседей мала. Если же это произошло, то влияние на голосование (особенно взвешенное) (при k>2) также, скорее всего, будет незначительным, и, следовательно, малым будет и влияние на итог классификации. Также, преимуществами являются проста реализации, легкость интерпретации результата работы алгоритма, возможность модификации алгоритма, путём использования наиболее подходящих функций сочетания и метрик, что позволяет подстроить алгоритм под конкретную задачу. Алгоритм KNN обладает и рядом недостатков. Во-первых, набор данных, используемый для алгоритма, должен быть репрезентативным. Во-вторых, модель нельзя отделить от данных: для классификации нового примера нужно использовать все примеры. Эта особенность сильно ограничивает использование алгоритма.

2.4 Деревья решений

Под термином «деревья решений» подразумевается семейство алгоритмов, основанных на представлении классификационных правил в иерархической, последовательной структуре. Это самый популярный класс алгоритмов для решения задач интеллектуального анализа данных.

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

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

Действие алгоритмов построения деревьев решений базируется на применении методов регрессионного и корреляционного анализа. Один из самых популярных алгоритмов этого семейства - CART (Classification and Regression Trees), основанный на разделении данных в ветви дерева на две дочерние ветви; при этом дальнейшее разделение той или иной ветви зависит от того, много ли исходных данных описывает данная ветвь. Некоторые другие сходные алгоритмы позволяют разделить ветвь на большее количество дочерних ветвей. В данном случае разделение производится на основе наиболее высокого для описываемых ветвью данных коэффициента корреляции между параметром, согласно которому происходит разделение, и параметром, который в дальнейшем должен быть предсказан.

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

2.5 Алгоритмы кластеризации

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

Применение кластерного анализа в общем виде сводится к следующим этапам:

· отбор выборки объектов для кластеризации;

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

· вычисление значений меры сходства между объектами;

· применение метода кластерного анализа для создания групп сходных объектов (кластеров);

· представление результатов анализа.

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

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

Еще одна классификация алгоритмов кластеризации - на четкие и нечеткие алгоритмы. Четкие (или непересекающиеся) алгоритмы каждому объекту выборки ставят в соответствие номер кластера, то есть каждый объект принадлежит только одному кластеру. Нечеткие (или пересекающиеся) алгоритмы каждому объекту ставят в соответствие набор вещественных значений, показывающих степень отношения объекта к кластерам. Таким образом, каждый объект относится к каждому кластеру с некоторой вероятностью.

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

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

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

,

где c j - «центр масс» кластера j (точка со средними значениями характеристик для данного кластера).

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

Случайно выбрать k точек, являющихся начальными «центрами масс» кластеров.

2. Отнести каждый объект к кластеру с ближайшим «центром масс».

Если критерий остановки алгоритма не удовлетворен, вернуться к п. 2.

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

Наиболее популярным алгоритмом нечеткой кластеризации является алгоритм c-средних (c-means). Он представляет собой модификацию метода k-средних. Шаги работы алгоритма:

1. Выбрать начальное нечеткое разбиение n объектов на k кластеров путем выбора матрицы принадлежности U размера n x k .

2. Используя матрицу U, найти значение критерия нечеткой ошибки:

,

где c k - «центр масс» нечеткого кластера k :

3. Перегруппировать объекты с целью уменьшения этого значения критерия нечеткой ошибки.

4. Возвращаться в п. 2 до тех пор, пока изменения матрицы U не станут незначительными.

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

Следующая группа алгоритмов - алгоритмы, основанные на теории графов. Суть таких алгоритмов заключается в том, что выборка объектов представляется в виде графа G=(V, E) , вершинам которого соответствуют объекты, а ребра имеют вес, равный «расстоянию» между объектами. Достоинством графовых алгоритмов кластеризации являются наглядность, относительная простота реализации и возможность вносения различных усовершенствований, основанные на геометрических соображениях. Основными алгоритмам являются алгоритм выделения связных компонент, алгоритм построения минимального покрывающего (остовного) дерева и алгоритм послойной кластеризации.

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

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

Алгоритм послойной кластеризации формирует последовательность подграфов графа G , которые отражают иерархические связи между кластерами:

,

где G t = (V, E t ) - граф на уровне с t , ,

с t - t-ый порог расстояния, m - количество уровней иерархии,
G 0 = (V, o) , o - пустое множество ребер графа, получаемое при t 0 = 1,
G m = G , то есть граф объектов без ограничений на расстояние (длину ребер графа), поскольку t m = 1.

Посредством изменения порогов расстояния {с 0 , …, с m }, где 0 = с 0 < с 1 < …< с m = 1, возможно контролировать глубину иерархии получаемых кластеров. Таким образом, алгоритм послойной кластеризации способен создавать как плоское разбиение данных, так и иерархическое.

Кластеризация позволяет добиться следующих целей:

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

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

· обнаружение новых нетипичных объектов, которые не попали ни в один кластер.

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

2.6 Генетические алгоритмы

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

Эта группа методов использует итеративный процесс эволюции последовательности поколений моделей, включающий операции отбора, мутации и скрещивания. В начале работы алгоритма популяция формируется случайным образом. Для оценки качества закодированных решений используют функцию приспособленности, которая необходима для вычисления приспособленности каждой особи. По результатам оценивания особей наиболее приспособленные из них выбираются для скрещивания. В результате скрещивания выбранных особей посредством применения генетического оператора кроссинговера создается потомство, генетическая информация которого формируется в результате обмена хромосомной информацией между родительскими особями. Созданные потомки формируют новую популяцию, причем часть потомков мутирует, что выражается в случайном изменении их генотипов. Этап, включающий последовательность «Оценивание популяции» - «Селекция» - «Скрещивание» - «Мутация», называется поколением. Эволюция популяции состоит из последовательности таких поколений.

Выделяют следующие алгоритмы отбора особей для скрещивания:

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

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

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

· Аутбридинг. Формировании пары на основе дальнего родства, для максимально далеких особей. Аутбридинг направлен на предупреждение сходимости алгоритма к уже найденным решениям, заставляя алгоритм просматривать новые, неисследованные области.

Алгоритмы формирования новой популяции:

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

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

· Турнирный отбор. Турнирный отбор реализует n турниров, чтобы выбрать n особей. Каждый турнир построен на выборке k элементов из популяции, и выбора лучшей особи среди них. Наиболее распространен турнирный отбор с k = 2.

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

3. Сферы применения

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

Маркетинг

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

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

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

Промышленность

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

Медицина

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

Молекулярная генетика и генная инженерия

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

Прикладная химия

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

Борьба с преступностью

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

Другие приложения

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

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

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

4. Производители средств Data Mining

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

Среди платных инструментов и систем анализ данных лидерами являются SAS Institute (SAS Enterprise Miner), SPSS (SPSS, Clementine) и StatSoft (STATISTICA Data Miner). Достаточно известными являются решения от Angoss (Angoss KnowledgeSTUDIO), IBM(IBM SPSS Modeler), Microsoft (Microsoft Analysis Services) и (Oracle) Oracle Data Mining.

Выбор свободного программного обеспечения также отличается разнообразием. Существуют как универсальные средства анализа, такие как JHepWork, KNIME, Orange, RapidMiner, так и специализированные средства, например Carrot2 - фрэймворк для кластеризации текстовых данных и результатов поисковых запросов, Chemicalize.org - решение в области прикладной химии, NLTK (Natural Language Toolkit) инструмент для обработки естественного языка (natural language processing).

5. Критика методов

Результаты Data Mining в большой мере зависят от уровня подготовки данных, а не от «чудесных возможностей» некоторого алгоритма или набора алгоритмов. Около 75% работы над Data Mining состоит в сборе данных, который совершается еще до применения инструментов анализа. Неграмотное применение инструментов, приведет к бессмысленной трате потенциала компании, а иногда и миллионов долларов.

Мнение Херба Эдельштайна (Herb Edelstein), известного в мире эксперта в области Data Mining, Хранилищ данных и CRM: «Недавнее исследование компании Two Crows показало, что Data Mining находится все еще на ранней стадии развития. Многие организации интересуются этой технологией, но лишь некоторые активно внедряют такие проекты. Удалось выяснить еще один важный момент: процесс реализации Data Mining на практике оказывается более сложным, чем ожидается.команды увлеклись мифом о том, что средства Data Mining просты в использовании. Предполагается, что достаточно запустить такой инструмент на терабайтной базе данных, и моментально появится полезная информация. На самом деле, успешный Data Mining проект требует понимания сути деятельности, знания данных и инструментов, а также процесса анализа данных». Таким образом, прежде чем использовать технологию Data Mining, необходимо тщательно проанализировать ограничения, накладываемые методами, и связанные с ней критические вопросы, а также трезво оценить возможности технологии. К критическим вопросам относятся следующие:

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

2. Сложность разработки и эксплуатации приложения Data Mining.

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

3. Квалификация пользователя.

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

4. Извлечение полезных сведений невозможно без хорошего понимания сути данных.

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

5. Сложность подготовки данных.

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

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

6. Большой процент ложных, недостоверных или бесполезных результатов.

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

7. Высокая стоимость.

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

8. Наличие достаточного количества репрезентативных данных.

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

нейросетевой алгоритм кластеризация данные mining

Заключение

Дана краткая характеристика сфер применения и приведена критика технологии Data Mining и мнение экспертов в этой области.

Список литературы

1. Han and Micheline Kamber. Data Mining: Concepts and Techniques. Second Edition. - University of Illinois at Urbana-Champaign

Berry, Michael J. A. Data mining techniques: for marketing, sales, and customer relationship management - 2nd ed.

Siu Nin Lam. Discovering Association Rules in Data Mining. - Department of Computer Science University of Illinois at Urbana-Champaign

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

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

Существует множество определений DataMining , которые друг друга дополняют. Вот некоторые из них.

DataMining – это процесс обнаружения в базах данных нетривиальных и практически полезных закономерностей. (BaseGroup)

DataMining – это процесс выделения, исследования и моделирования больших объемов данных для обнаружения неизвестныхдо этого структур(patters) с целью достижения преимуществ в бизнесе(SAS Institute)

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

DataMining – это исследование и обнаружение «машиной»(алгоритмами, средствами искусственного интеллекта) в сырых данных скрытых знаний,котор ые ранее не были известны, нетривиальны, практически полезны, доступны для интерпрета ции человеком.(А.Баргесян «Технологии анализа данных»)

DataMining – это процесс обнаружения полезных знаний о бизнесе.(Н.М.Абдикеев «КБА»)

Свойства обнаруживаемых знаний

Рассмотрим свойства обнаруживаемых знаний.

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

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

Задачи DataMining

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

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

кластеризация, прогнозирование, ассоциация, визуализация, анализ и обнаружение

отклонений, оценивание, анализ связей, подведение итогов.

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

Классификация (Classification)

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

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

Если число классов ограничено двумя, то имеет место бинарная классификация , к которой могут быть сведены многие более сложные задачи. Например, вместо определения таких степеней кредитного риска, как «Высокий», «Средний» или «Низкий», можно использовать всего две - «Выдать» или «Отказать».

Для классификации в DataMining используется множество различных моделей: нейронные сети , деревья решений , машины опорных векторов, метод k-ближайших соседей, алгоритмы покрытия и др., при построении которых применяется обучение с учителем, когда выходная переменная (метка класса ) задана для каждого наблюдения. Формально классификация производится на основе разбиения пространства признаков на области, в пределах каждой из которых многомерные векторы рассматриваются как идентичные. Иными словами, если объект попал в область пространства, ассоциированную с определенным классом, он к нему и относится.

Кластеризация (Clustering)

Краткое описание. Кластеризация является логическим продолжением идеи

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

Пример метода решения задачи кластеризации: обучение "без учителя" особого вида нейронных сетей - самоорганизующихся карт Кохонена.

Ассоциация (Associations)

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

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

Последовательность (Sequence) или последовательная ассоциация (sequentialassociation)

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

Правило последовательности: после события X через определенное время произойдет событие Y.

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

Регрессия, прогнозирование (Forecasting)

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

Для решения таких задач широко применяются методы математической статистики, нейронные сети и др.

Дополнительные задачи

Определение отклонений или выбросов (DeviationDetection) , анализ отклонений или выбросов

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

Оценивание (Estimation)

Задача оценивания сводится к предсказанию непрерывных значений признака.

Анализ связей (LinkAnalysis)

Задача нахождения зависимостей в наборе данных.

Визуализация (Visualization, GraphMining)

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

Пример методов визуализации - представление данных в 2-D и 3-D измерениях.

Подведение итогов (Summarization)

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

Достаточно близким к вышеупомянутой классификации является подразделение задач DataMining на следующие: исследования и открытия, прогнозирования и классификации, объяснения и описания.

Автоматическое исследование и открытие (свободный поиск)

Пример задачи: обнаружение новых сегментов рынка.

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

Прогнозирование и классификация

Пример задачи: предсказание роста объемов продаж на основе текущих значений.

Методы: регрессия, нейронные сети, генетические алгоритмы, деревья решений.

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

Объяснение и описание

Пример задачи: характеристика клиентов по демографическим данным и историям покупок.

Методы: деревья решения, системы правил, правила ассоциации, анализ связей.

Если доход клиента больше, чем 50 условных единиц, и его возраст - более 30 лет, тогда класс клиента - первый.

Сравнение кластеризации и классификации

Характеристика	Классификация	Кластеризация
Контролируемость обучения	Контролируемое	Неконтролируемое
Стратегии	Обучение с учителем	Обучение без учителя
Наличие метки класса	Обучающее множество сопровождается меткой, указывающей класс, к которому относится наблюдение	Метки класса обучающего множества неизвестны
Основание для классификации	Новые данные классифицируются на основании обучающего множества	Дано множество данных с целью установления существования классов или кластеров данных

Сферы применения DataMining

Следует отметить, что на сегодняшний день наибольшее распространение технология DataMining получила при решении бизнес-задач. Возможно, причина в том, что именно в этом направлении отдача от использования инструментов DataMining может составлять, по некоторым источникам, до 1000% и затраты на ее внедрение могут достаточно быстро окупиться.

Мы будем рассматривать четыре основные сферы применения технологии DataMining подробно: наука, бизнес, исследования для правительства и Web-направление.

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

Выдавать ли кредит клиенту

Сегментация рынка

Привлечение новых клиентов

Мошенничествос кредитными карточками

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

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

Применение DataMining для решения Web-задач . Основные направления: поисковыемашины (searchengines), счетчики и другие.

Электронная коммерция

В сфере электронной коммерции DataMining применяется для формирования

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

Основные задачи DataMining в промышленном производстве:

· комплексный системный анализ производственных ситуаций;

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

· выработка вариантов оптимизационных решений;

· прогнозирование качества изделия в зависимости от некоторых параметров

технологического процесса;

· обнаружение скрытых тенденций и закономерностей развития производственных

процессов;

· прогнозирование закономерностей развития производственных процессов;

· обнаружение скрытых факторов влияния;

· обнаружение и идентификация ранее неизвестных взаимосвязей между

производственными параметрами и факторами влияния;

· анализ среды взаимодействия производственных процессов и прогнозирование

изменения ее характеристик;

процессами;

· визуализацию результатов анализа, подготовку предварительных отчетов и проектов

допустимых решений с оценками достоверности и эффективности возможных реализаций.

Маркетинг

В сфере маркетинга DataMining находит очень широкое применение.

Основные вопросы маркетинга "Что продается?", "Как продается?", "Кто является

потребителем?"

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

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

Также успешно здесь используется поиск временных закономерностей.

Розничная торговля

В сфере розничной торговли, как и в маркетинге, применяются:

· алгоритмы поиска ассоциативных правил (для определения часто встречающихся наборов

товаров, которые покупатели покупают одновременно). Выявление таких правил помогает

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

и их размещения на складах и т.д.

· использование временных последовательностей, например, для определения

необходимых объемов запасов товаров на складе.

· методы классификации и кластеризации для определения групп или категорий клиентов,

знание которых способствует успешному продвижению товаров.

Фондовый рынок

Вот список задач фондового рынка, которые можно решать при помощи технологии Data

Mining:· прогнозирование будущих значений финансовых инструментов и индикаторов поих

прошлым значениям;

· прогноз тренда (будущего направления движения - рост, падение, флэт) финансового

инструмента и его силы (сильный, умеренно сильный и т.д.);

· выделение кластерной структуры рынка, отрасли, сектора по некоторому набору

характеристик;

· динамическое управление портфелем;

· прогноз волатильности;

· оценка рисков;

· предсказание наступления кризиса и прогноз его развития;

· выбор активов и др.

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

Применение DataMining в CRM

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

CRM (CustomerRelationshipManagement) - управление отношениями с клиентами.

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

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

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

WebMining

WebMining можно перевести как "добыча данных в Web". WebIntelligence или Web.

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

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

Методы

Классификация методов

Различают две группы методов :

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

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

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

Рассмотрим подробнее представленные выше группы.

Статистические методы Data mining

В эти методы представляют собой четыре взаимосвязанных раздела:

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

Арсенал статистических методов Data Mining классифицирован на четыре группы методов :

1. Дескриптивный анализ и описание исходных данных.
2. Анализ связей (корреляционный и регрессионный анализ, факторный анализ, дисперсионный анализ).
3. Многомерный статистический анализ (компонентный анализ, дискриминантный анализ, многомерный регрессионный анализ, канонические корреляции и др.).
4. Анализ временных рядов (динамические модели и прогнозирование).

Кибернетические методы Data Mining

Второе направление Data Mining - это множество подходов, объединенных идеей компьютерной математики и использования теории искусственного интеллекта.

К этой группе относятся такие методы :

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

Кластерный анализ

Цель кластеризации - поиск существующих структур.

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

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

Характеристиками кластера можно назвать два признака:

• внутренняя однородность;
• внешняя изолированность.

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

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

Кластеры могут быть непересекающимися, или эксклюзивными (non-overlapping, exclusive), и пересекающимися (overlapping) .

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

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

Приведем краткую характеристику подходов к кластеризации.

Алгоритмы, основанные на разделении данных (Partitioningalgorithms), в т.ч. итеративные:

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

Методы, основанные на концентрации объектов (Density-basedmethods):

• основаны на возможности соединения объектов;
• игнорируют шумы, нахождение кластеров произвольной формы.

Грид- методы (Grid-based methods):

• квантование объектов в грид-структуры.

Модельные методы (Model-based):

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

Методы кластерного анализа. Итеративные методы.

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

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

Алгоритм k-средних (k-means)

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

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

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

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

1. Первоначальное распределение объектов по кластерам.

• Выбирается число k, и на первом шаге эти точки считаются "центрами" кластеров.
• Каждому кластеру соответствует один центр.

Выбор начальныхцентроидов может осуществляться следующим образом:

• выбор k-наблюдений для максимизации начального расстояния;
• случайный выбор k-наблюдений;
• выбор первых k-наблюдений.

В результате каждый объект назначен определенному кластеру.

2. Итеративный процесс.

Вычисляются центры кластеров, которыми затем и далее считаются покоординатные средние кластеров. Объекты опять перераспределяются.

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

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

На рисунке приведен пример работы алгоритма k-средних для k, равного двум.

Пример работы алгоритма k-средних (k=2)

Выбор числа кластеров является сложным вопросом. Если нет предположений относительно этого числа, рекомендуют создать 2 кластера, затем 3, 4, 5 и т.д., сравнивая полученные результаты.

Проверка качества кластеризации

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

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

Достоинства алгоритма k-средних:

• простота использования;
• быстрота использования;
• понятность и прозрачность алгоритма.

Недостатки алгоритма k-средних:

• алгоритм слишком чувствителен к выбросам, которые могут искажать среднее.

Возможным решением этой проблемы является использование модификации алгоритма -алгоритм k-медианы;

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

Байесовские сети

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

Удобно и интуитивно понятно представлять зависимости между элементами посредством направленного пути, соединяющего эти элементы в графе. Если зависимость между элементами x и y не является непосредственной и осуществляется посредством третьего элемента z, то логично ожидать, что на пути между x и y будет находиться элемент z. Такие узлы-посредники будут «отсекать» зависимость между x и y, т.е. моделировать ситуацию условной независимости между ними при известном значении непосредственных факторов влияния. Такими языками моделирования являются байесовские сети, которые служат для описания условных зависимостей между понятиями некой предметной области.

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

Свойства классификации:

1. Использование всех переменных и определение всех зависимостей между ними.

2. Наличие двух предположений относительно переменных:

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

Различают два основных сценария применения байесовских сетей:

1. Описательный анализ. Предметная область отображается в виде графа, узлы которого представляют понятия, а направленные дуги, отображаемые стрелками, иллюстрируют непосредственные зависимости между этими понятиями. Связь между понятиями x и y означает: знание значения x помогает сделать более обоснованное предположение о значении y. Отсутствие непосредственной связи между понятиями моделирует условную независимость между ними при известных значениях некоторого набора «разделяющих» понятий. Например, размер обуви ребенка, очевидно, связан с умением ребенка читать через возраст. Так, больший размер обуви дает большую уверенность, что ребенок уже читает, но если нам уже известен возраст, то знание размера обуви уже не даст нам дополнительной информации о способности ребенка к чтению.

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

2. Классификация и прогнозирование. Байесовская сеть, допуская условную независимость ряда понятий, позволяет уменьшить число параметров совместного распределения, делая возможным их доверительную оценку на имеющихся объемах данных. Так, при 10 переменных, каждая из которых может принимать 10 значений, число параметров совместного распределения – 10 миллиардов - 1. Если допустить, что между этими переменными друг от друга зависят только 2 переменные, то число параметров становится 8*(10-1) + (10*10-1) = 171. Имея реалистичную по вычислительным ресурсам модель совместного распределения, неизвестное значение какого-либо понятия мы можем прогнозировать как, например, наиболее вероятное значение этого понятия при известных значениях других понятий.

Отмечают такие достоинства байесовских сетей как метода DataMining:

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

Байесовские сети достаточно просто интерпретируются и позволяют на этапе прогностического моделирования легко проводить анализ по сценарию "что, если";

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

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

Наивно-байесовский подход имеет следующие недостатки:

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

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

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

Искусственные нейронные сети

Искуственные нейронные сети(далее нейронные сети) могут быть синхронные и асинхронные. В синхронных нейронных сетях в каждый момент времени свое состояние меняет лишь один нейрон. В асинхронных - состояние меняется сразу у целой группы нейронов, как правило, у всего слоя. Можно выделить две базовые архитектуры - слоистые и полносвязные сети. Ключевым в слоистых сетях является понятие слоя. Слой - один или несколько нейронов, на входы которых подается один и тот же общий сигнал. Слоистые нейронные сети - нейронные сети, в которых нейроны разбиты на отдельные группы (слои) так, что обработка информации осуществляется послойно. В слоистых сетях нейроны i-го слоя получают входные сигналы, преобразуют их и через точки ветвления передают нейронам (i+1) слоя. И так до k-го слоя, который выдает выходные сигналы для интерпретатора и пользователя. Число нейронов в каждом слое не связано с количеством нейронов в других слоях, может быть произвольным. В рамках одного слоя данные обрабатываются параллельно, а в масштабах всей сети обработка ведется последовательно - от слоя к слою. К слоистым нейронным сетям относятся, например, многослойные персептроны, сети радиальных базисных функций, когнитрон, некогнитрон, сети ассоциативной памяти. Однако сигнал не всегда подается на все нейроны слоя. В когнитроне, например, каждый нейрон текущего слоя получает сигналы только от близких ему нейронов предыдущего слоя.

Слоистые сети, в свою очередь, могут быть однослойными и многослойными.

Однослойная сеть - сеть, состоящая из одного слоя.

Многослойная сеть - сеть, имеющая несколько слоев.

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

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

Все входные сигналы подаются всем нейронам.

Обучение нейронных сетей

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

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

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

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

Переобучение нейронной сети

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

Инструменты DataMining

Разработкой в секторе DataMining всемирного рынка программного обеспечения заняты как всемирно известные лидеры, так и новые развивающиеся компании. Инструменты DataMining могут быть представлены либо как самостоятельное приложение, либо как дополнения к основному продукту. Последний вариант реализуется многими лидерами рынка программного обеспечения. Так, уже стало традицией, что разработчики универсальных статистических пакетов, вдополнение к традиционным методам статистического анализа, включают в пакет определенныйнаборметодов DataMining. Этотакиепакетыкак SPSS (SPSS, Clementine), Statistica (StatSoft), SAS Institute (SAS Enterprise Miner). Некоторые разработчики OLAP- решений также предлагают набор методов DataMining, например, семейство продуктов Cognos. Есть поставщики, включающие DataMining решения в функциональность СУБД: это Microsoft (MicrosoftSQLServer ), Oracle , IBM (IBMIntelligentMinerforData ).

Список литературы

Абдикеев Н.М. Данько Т.П. Ильдеменов С.В. Киселев А.Д, «Реинжиниринг бизнес-процессов. Курс MBA», М.: Изд-во Эксмо, 2005. - 592 с. - (МВА)

Абдикеев Н.М., Киселев А.Д. «Управление знаниями в корпорации и реинжиниринг бизнеса» - М.:Инфра-М, 2011.- 382 с. – ISBN 978-5-16-004300-5

Барсегян А.А., Куприянов М.С., Степаненко В.В., ХолодИ.И. «Методы и модели анализа данных: OLAP и Data Mining», Спб:БХВ-Петербург,2004,336с., ISBN 5-94157-522-Х

Дюк В ., Самойленко А ., «Data Mining. Учебный курс» Спб:Питер,2001, 386с.

Чубукова И.А., Курс Data Mining, http://www.intuit.ru/department/database/datamining/

IanH. Witten, Eibe Frank, Mark A. Hall, Morgan Kaufmann, Data Mining: Practical Machine Learning Tools and Techniques (Third Edition), ISBN 978-0-12-374856-0

Petrushin V.A. , Khan L. , Multimedia Data Mining and Knowledge Discovery

Что такое Data Mining

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

Подобного рода информация обычно используется при прогнозировании, стратегическом планировании, анализе рисков, и ценность ее для предприятия очень высока. Видимо, поэтому процесс ее поиска и получил название Data Mining (mining по-английски означает «добыча полезных ископаемых», а поиск закономерностей в огромном наборе фактических данных действительно сродни этому). Термин Data Mining обозначает не столько конкретную технологию, сколько сам процесс поиска корреляций, тенденций, взаимосвязей и закономерностей посредством различных математических и статистических алгоритмов: кластеризации, создания субвыборок, регрессионного и корреляционного анализа. Цель этого поиска - представить данные в виде, четко отражающем бизнес-процессы, а также построить модель, при помощи которой можно прогнозировать процессы, критичные для планирования бизнеса (например, динамику спроса на те или иные товары или услуги либо зависимость их приобретения от каких-то характеристик потребителя).

Отметим, что традиционная математическая статистика, долгое время остававшаяся основным инструментом анализа данных, равно как и средства оперативной аналитической обработки данных (online analytical processing, OLAP), о которых мы уже неоднократно писали (см. материалы на эту тему на нашем компакт-диске), не всегда могут успешно применяться для решения таких задач. Обычно статистические методы и OLAP используются для проверки заранее сформулированных гипотез. Однако нередко именно формулировка гипотезы оказывается самой сложной задачей при реализации бизнес-анализа для последующего принятия решений, поскольку далеко не все закономерности в данных очевидны с первого взгляда.

В основу современной технологии Data Mining положена концепция шаблонов, отражающих закономерности, свойственные подвыборкам данных. Поиск шаблонов производится методами, не использующими никаких априорных предположений об этих подвыборках. Если при статистическом анализе или при применении OLAP обычно формулируются вопросы типа «Каково среднее число неоплаченных счетов заказчиками данной услуги?», то применение Data Mining, как правило, то подразумевает ответы на вопросы типа «Существует ли типичная категория клиентов, не оплачивающих счета?». При этом именно ответ на второй вопрос нередко обеспечивает более нетривиальный подход к маркетинговой политике и к организации работы с клиентами.

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

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

Исходные данные для Data Mining

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

Типы закономерностей, выявляемых методами Data Mining

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

Ассоциация - высокая вероятность связи событий друг с другом (например, один товар часто приобретается вместе с другим);

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

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

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

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

Методы исследования данных в Data Mining

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

Регрессионный, дисперсионный и корреляционный анализ (реализован в большинстве современных статистических пакетов, в частности в продуктах компаний SAS Institute, StatSoft и др.);

Методы анализа в конкретной предметной области, базирующиеся на эмпирических моделях (часто применяются, например, в недорогих средствах финансового анализа);

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

Алгоритмы - выбор близкого аналога исходных данных из уже имеющихся исторических данных. Называются также методом «ближайшего соседа»;

Деревья решений - иерархическая структура, базирующаяся на наборе вопросов, подразумевающих ответ «Да» или «Нет»; несмотря на то, что данный способ обработки данных далеко не всегда идеально находит существующие закономерности, он довольно часто используется в системах прогнозирования в силу наглядности получаемого ответа;

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

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

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

Подробнее об этих и других алгоритмах Data Mining, а также о реализующих их средствах можно прочесть в книге «Data Mining: учебный курс» В.А.Дюка и А.П.Самойленко, выпущенной издательством «Питер» в 2001 году . Сегодня это одна из немногих книг на русском языке, посвященная данной проблеме.

Ведущие производители средств Data Mining

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

К современным средствам Business Intelligence относятся генераторы отчетов, средства аналитической обработки данных, средства разработки BI-решений (BI Platforms) и так называемые Enterprise BI Suites - средства анализа и обработки данных масштаба предприятия, которые позволяют осуществлять комплекс действий, связанных с анализом данных и с созданием отчетов, и нередко включают интегрированный набор BI-инструментов и средства разработки BI-приложений. Последние, как правило, содержат в своем составе и средства построения отчетов, и OLAP-средства, а нередко - и Data Mining-средства.

По данным аналитиков Gartner Group, лидерами на рынке средств анализа и обработки данных масштаба предприятия являются компании Business Objects, Cognos, Information Builders, а претендуют на лидерство также Microsoft и Oracle (рис. 1). Что касается средств разработки BI-решений, то основными претендентами на лидерство в этой области являются компании Microsoft и SAS Institute (рис. 2).

Отметим, что средства Business Intelligence компании Microsoft относятся к сравнительно недорогим продуктам, доступным широкому кругу компаний. Именно поэтому мы и собираемся рассмотреть некоторые практические аспекты применения Data Mining на примере продуктов этой компании в последующих частях данной статьи.

Литература:

1. Дюк В.А. Data Mining - интеллектуальный анализ данных. - http://www.olap.ru/basic/dm2.asp .

2. Дюк В.А., Самойленко А.П. Data Mining: учебный курс. - СПб.: Питер, 2001.

3. B. de Ville. Microsoft Data Mining. Digital Press, 2001.

В настоящее время элементы искусственного интеллекта активно внедряются в практическую деятельность менеджера. В отличие от традиционных систем искусственного интеллекта, технология интеллектуального поиска и анализа данных или "добыча данных" (Data Mining - DM), не пытается моделировать естественный интеллект, а усиливает его возможности мощностью современных вычислительных серверов, поисковых систем и хранилищ данных. Нередко рядом со словами "Data Mining" встречаются слова "обнаружение знаний в базах данных" (Knowledge Discovery in Databases).

Рис. 6.17.

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

В основу современной технологии Data Mining (Discovery-driven Data Mining) положена концепция шаблонов (Patterns), отражающих фрагменты многоаспектных взаимоотношений в данных. Эти шаблоны представляют собой закономерности, свойственные выборкам данных, которые могут быть компактно выражены в понятной человеку форме. Поиск шаблонов производится методами, не ограниченными рамками априорных предположений о структуре выборки и виде распределений значений анализируемых показателей. На рис. 6.17 показана схема преобразования данных с использованием технологии Data Mining.

Рис. 6.18.

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

Важное положение Data Mining - нетривиальность разыскиваемых шаблонов. Это означает, что найденные шаблоны должны отражать неочевидные, неожиданные (Unexpected) регулярности в данных, составляющие так называемые скрытые знания (Hidden Knowledge). К деловым людям пришло понимание, что "сырые" данные (Raw Data) содержат глубинный пласт знаний, и при грамотной его раскопке могут быть обнаружены настоящие самородки, которые можно использовать в конкурентной борьбе.

Сфера применения Data Mining ничем не ограничена - технологию можно применять всюду, где имеются огромные количества каких-либо "сырых" данных!

В первую очередь методы Data Mining заинтересовали коммерческие предприятия, развертывающие проекты на основе информационных хранилищ данных (Data Warehousing). Опыт многих таких предприятий показывает, что отдача от использования Data Mining может достигать 1000%. Известны сообщения об экономическом эффекте, в 10-70 раз превысившем первоначальные затраты от 350 до 750 тыс. долларов. Есть сведения о проекте в 20 млн долларов, который окупился всего за 4 месяца. Другой пример - годовая экономия 700 тыс. долларов за счет внедрения Data Mining в одной из сетей универсамов в Великобритании.

Компания Microsoft официально объявила об усилении своей активности в области Data Mining. Специальная исследовательская группа Microsoft, возглавляемая Усамой Файядом, и шесть приглашенных партнеров (компании Angoss, Datasage, Epiphany, SAS, Silicon Graphics, SPSS) готовят совместный проект по разработке стандарта обмена данными и средств для интеграции инструментов Data Mining с базами и хранилищами данных.

Data Mining является мультидисциплинарной областью, возникшей и развивающейся на базе достижений прикладной статистики, распознавания образов, методов искусственного интеллекта, теории баз данных и др. (рис. 6.19). Отсюда обилие методов и алгоритмов, реализованных в различных действующих системах Data Mining. [Дюк В.А. www.inftech.webservis.ru/it/datamining/ar2.html]. Многие из таких систем интегрируют в себе сразу несколько подходов. Тем не менее, как правило, в каждой системе имеется какая-то ключевая компонента, на которую делается главная ставка.

Можно назвать пять стандартных типов закономерностей, выявляемых с помощью методов Data Mining: ассоциация, последовательность, классификация, кластеризация и прогнозирование.

Рис. 6.19. Области применения технологии Data Mining

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

Если существует цепочка связанных во времени событий, то говорят о последовательности. Так, например, после покупки дома в 45% случаев в течение месяца приобретается и новая кухонная плита, а в пределах двух недель 60% новоселов обзаводятся холодильником.

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

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