8879

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

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

Выделяют пять основных типов задач, решаемых методами Data Mining:

1.Классификация – это установление зависимости дискретной выходной пере-

менной от входных переменных.

2.Регрессия – это установление зависимости непрерывной выходной переменной

от входных переменных.

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

4.Ассоциация – выявление закономерностей между связанными событиями.

Примером такой закономерности служит правило, указывающее, что из собы-

тия X следует событие Y. Такие правила называются ассоциативными. Впер-

вые эта задача была предложена для нахождения типичных шаблонов поку-

пок, совершаемых в супермаркетах, поэтому иногда ее называют анализом рыночной корзины (market basket analysis). Если же нас интересует последова-

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

бытиями. Примером такой закономерности служит правило, указывающее,

что из события X спустя время t последует событие Y.

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

как регрессия, классификация и кластеризация.

Прогнозирование – одна из самых востребованных задач анализа данных.

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

щем, можно принимать более обоснованные управленческие решения, планировать

31

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

Существует множество методов, позволяющих сделать прогноз. Среди стати-

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

ных. Развитие методов прогнозирования непосредственно связано с развитием ин-

формационных технологий, в частности, с ростом объемов хранимых данных и усложнением методов и алгоритмов прогнозирования, реализованных в инструмен-

тах интеллектуального анализа данных – Data Mining.

Ввиду того, что Data Mining развивается на стыке таких дисциплин, как мате-

матика, статистика, теория информации, машинное обучение, теория баз данных,

программирование, параллельные вычисления, вполне закономерно, что большин-

ство алгоритмов и методов Data Mining были разработаны на основе подходов, при-

меняемых в этих дисциплинах.

Эти методы стали весьма широко и эффективно применяться в связи с бурным развитием в последнее десятилетие XX века самих методик и соответствующих ин-

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

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

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

На сегодняшний день наибольшее распространение в Data Mining получили

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

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

32

Общая постановка задачи обучения следующая. Имеется множество объектов

(ситуаций) и множество возможных ответов (откликов, реакций). Между ответами и объектами существует некоторая зависимость, но она неизвестна. Известна только конечная совокупность прецедентов – пар вида «объект – ответ», – называемая обу-

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

Основные этапы решения задач методами Data Mining:

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

Подготовка данных для автоматизированного анализа; то есть приведение данных к форме, пригодной для применения конкретных выбранных методов

DM.

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

Проверка построенных моделей; что дает судить об адекватности построенной модели.

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

Каждый из алгоритмов Data Mining использует определенный подход к визуа-

лизации:

1.Для деревьев решений это визуализатор дерева решений, список правил, таб-

лица сопряженности.

2.Для нейронных сетей в зависимости от инструмента это может быть тополо-

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

33

3.Для линейной регрессии в качестве визуализатора выступает линия регрессии,

диаграммы рассеивания.

4.Для кластеризации – дендрограммы, карты Кохонена.

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

Деревья решений (decision trees) относятся к числу самых популярных и мощ-

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

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

ные значения, то при помощи метода дерева решений решается задача классифика-

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

т.е. решает задачу численного прогнозирования.

Деревья решений – иерархические древовидные структуры, состоящие из ре-

шающих правил вида «если – то», которые могут быть сформулированы на есте-

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

В отличие от методов, использующих статистический подход, деревья реше-

ний основаны на машинном обучении и в большинстве случаев не требуют предпо-

ложений о статистическом распределении значений признаков.

Для эффективного построения дерева решений должны выполняться следую-

щие условия:

Описание атрибутов – анализируемые данные должны быть представлены

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

описывающих классифицируемые объекты).

34

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

Различимость классов – должна обеспечиваться принципиальная возможность установления факта принадлежности или непринадлежности примера

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

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

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

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

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

Например, стоит задача разбить множество объектов недвижимости на 2 клас-

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

а также факт дорогая/недорогая квартира. Графически такое множество наблюдений представлено на рис. 15. Условно примем, что объект в форме круга указывает на недорогую квартиру, в форме прямоугольника – на дорогую квартиру, а внутри каждого объекта указана общая площадь квартиры.

35

Рис. 15. Разделение на классы Необходимо разбить множества на подмножества так, чтобы в них попали

только объекты одного класса.

Выберем некоторое пороговое значение общей площади, например равное 40

квадратным метрам, и разобьем исходное множество на 2 подмножества соответ-

ствии с условием общая площадь>40. В результате разбиения в одном подмноже-

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

40, а во втором – меньше 40. На рис. 4.1 данные подмножества обозначены номера-

ми 1 и 2 соответственно. Легко увидеть, что выбор порогового значения общей пло-

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

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

Например, для подмножества 1 применим порог 50, а для подмножества 2 – 20.

Результаты повторного разбиения представлены на рис. 16.

Рис. 16. Продолжение деления на классы

36

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

Дерево, реализующее данную процедуру, представлено на рис.17. В нем подмноже-

ства 3 и 5 ассоциированы с классом недорогих квартир, а подмножества 4 и 6 – с

классом дорогих квартир.

Рис. 17. Построенное дерево решений (по одному атрибуту)

Применяя построенную модель к новым объектам недвижимости, можно ука-

зать их ценовую категорию на основании того, в какое из подмножеств модель по-

местит соответствующую запись.

Таким образом, мы получили систему правил вида «если...то..», которые поз-

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

Обладая высокой объясняющей способностью и интерпретируемостью, дере-

вья решений могут использоваться и как эффективные классификаторы, и как ин-

струмент исследования предметной области.

Процесс построения дерева решений не является однозначно определенным.

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

37

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

нить ее, точность, эффективность и способность к работе с новыми данными.

Точность дерева решений определяется на основе числа правильно и непра-

вильно классифицированных примеров.

Эффективность разбиения оценивается по чистоте полученных дочерних уз-

лов относительно целевой переменной. От ее типа и будет зависеть выбор предпо-

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

ной, то необходимо использовать такие критерии, как индекс Джини, прирост ин-

формации или тест хи-квадрат. Если выходная переменная является непрерывной,

то для оценки эффективности разбиения используются метод уменьшения диспер-

сии или F-критерий Фишера.

Для определения меры эффективности деревьев решений используют тестовое множество – набор примеров, которые ранее не использовались при построении де-

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

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

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

Каждый узел дерева имеет следующие характеристики:

количество примеров, попавших в узел;

доли примеров, относящихся к каждому из классов;

число классифицированных примеров (для узлов);

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

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

поддержка (support) – отношение числа правильно классифицированных

Значение поддержки находится в интервале [0;1].

достоверность (confidence) – отношение числа правильно классифициро-

ванных примеров к числу неправильно классифицированных:

38

S Nкл

Nошибка

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

2.3.4. Раздел 4. Data Mining: ассоциативные правила.

Аффинитивный анализ (affinity analysis) – один из распространенных мето-

дов Data Mining. Его название происходит от английского слова affinity, которое в переводе означает «близость», «сходство». Цель данного метода – исследование взаимной связи между событиями, которые происходят совместно. Разновидностью аффинитивного анализа является анализ рыночной корзины (market basket analysis),

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

лее событиями. Такие правила называются ассоциативными правилами (association rules).

Пусть I = {i1, i2, i3, …in} – множество (набор) товаров, называемых элемен-

тами,

D – множество транзакций Т, где каждая из них является набором элементов из I,T I.

Любая транзакция представляет собой бинарный вектор, где t[k] = 1, если ik

элемент присутствует в ней, иначе t[k] = 0.

Говорят, что транзакция T содержит X (некоторый набор элементов из I), ес-

ли X T.

Ассоциативным правилом называется импликация X Y, где X I, Y I и X Y = .

39

Примерами приложения ассоциативных правил могут быть следующие зада-

чи:

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

-определение доли клиентов, положительно относящихся к нововведени-

ям в их обслуживании;

-определение профиля посетителей веб-ресурса;

-определение доли случаев, в которых новое лекарство показывает опас-

ный побочный эффект.

Базовым понятием в теории ассоциативных правил является транзакция – не-

которое множество событий, происходящих совместно. Типичная транзакция – при-

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

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

тия? Эту связь и устанавливают ассоциативные правила. Например, может быть об-

наружено ассоциативное правило, утверждающее, что клиент, купивший молоко, с

вероятностью 75 % купит и хлеб.

Ассоциативное правило состоит из двух наборов предметов, называемых условие (antecedent) и следствие (consequent), записываемых в виде X → Y, что чита-

ется следующим образом: «Из X следует Y». Таким образом, ассоциативное правило формулируется в виде: «Если условие, то следствие».

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

Ассоциативные правила описывают связь между наборами предметов, соот-

ветствующими условию и следствию. Эта связь характеризуется двумя показателя-

ми – поддержкой (support) и достоверностью (confidence).

Обозначим базу данных транзакций как D, а число транзакций в этой базе как

N. Каждая транзакция Di представляет собой некоторый набор предметов. Зададим,

что S – поддержка, C – достоверность.

40