Зайцев Применение методов Дата Мининг для поддержки процессов управления ИТ-услугами.Учебное пособие 2009

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

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

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

1.4. Иерархические методы кластерного анализа

Суть иерархической кластеризации состоит в последовательном объединении меньших кластеров в большие или разделении больших кластеров на меньшие [24].

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

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

Иерархические дивизимные (делимые) методы. Эти методы яв-

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

Все эти методы не выдают на выходе никаких сведений, кроме, собственно кластеров. Следовательно, эти методы не удовлетворяют выбранному критерию.

1.5. Неиерархические методы кластерного анализа

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

11

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

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

Рис. 1.2. Схема работы алгоритма k-средних

Алгоритм k-средних. Наиболее распространен среди неиерархических методов алгоритм k-средних (рис. 1.2), также называемый

12

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

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

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

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

1.6. Методы рассуждений на основе аналогичных случаев

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

При таком подходе используется термин «k-ближайший сосед». Термин означает, что выбирается k «верхних» (ближайших) соседей для их рассмотрения в качестве множества «ближайших соседей». Поскольку не всегда удобно хранить все данные, иногда хранится только множество «типичных» случаев. В таком случае используемый метод называют рассуждением по аналогии CBR (Case Based Reasoning), рассуждением на основе аналогичных случаев, рассуждением по прецедентам.

13

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

1.7. Линейная регрессия

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

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

Линейная регрессия не выдает на выходе правил «если-то», следовательно, этот метод не удовлетворяет выбранному критерию вида представляемой зависимости.

1.8. Логистическая регрессия

Логистическая регрессия – разновидность множественной регрессии, общее назначение которой состоит в анализе связи между несколькими независимыми переменными (называемыми также регрессорами или предикторами) и зависимой переменной [25]. Бинарная логистическая регрессия, как следует из названия, применяется в случае, когда зависимая переменная является бинарной (т.е. может принимать только два значения). Иными словами, с помощью логистической регрессии можно оценивать вероятность того, что событие наступит для конкретного испытуемого (больной/здоровый, возврат кредита/дефолт и т.д.).

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

14

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

Для решения проблемы задача регрессии может быть сформулирована иначе: вместо предсказания бинарной переменной, мы предсказываем непрерывную переменную со значениями на отрезке [0,1] при любых значениях независимых переменных. Это достигается применением следующего регрессионного уравнения (ло- гит-преобразование):

P =1+1e−y ,

где P – вероятность того, что произойдет интересующее событие; e – основание натуральных логарифмов 2,71…; y – стандартное уравнение регрессии (1.1).

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

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

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

15

Большинство других методов классификации предполагают, что перед началом классификации вероятность того, что объект принадлежит тому или иному классу, одинакова; но это не всегда верно.

Метод наивной байесовской классификации на выходе не выдает информации вида правил «если-то». Следовательно, этот метод не удовлетворяет выбранному критерию вида представляемой зависимости.

1.10. Нейронные сети

Согласно словарю по психофизиологии [35], нейронная сеть – группа взаимодействующих нервных клеток или ее модель. Искусственная нейронная сеть – вычислительная или логическая схема, построенная из однородных процессорных элементов, являющихся упрощенными функциональными моделями нейронов. Как математическая модель искусственная нейронная сеть представляет собой частный случай методов распознавания образов или дискриминантного анализа [5].

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

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

17

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

Целью поиска ассоциативных правил [2, 12] является нахождение закономерностей между связанными событиями в базах данных. Ассоциативное правило имеет вид: «Из события A следует событие B».

Врезультате такого вида анализа мы устанавливаем закономерность следующего вида: «Если в транзакции встретился набор элементов A, то можно сделать вывод, что в этой же транзакции должен появиться набор элементов B)» Построение таких закономерностей дает нам возможность находить очень простые и понятные правила, называемые ассоциативными. Этот метод удовлетворяет выбранному критерию вида представляемой зависимости.

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

2.Алгоритмы нахождения деревьев решений

2.1. Описание дерева решений

Деревья решений – способ представления правил в иерархической, последовательной структуре, где каждому объекту соответствует единственный узел, дающий решение (рис. 2.1). Под правилом понимается логическая конструкция, представленная в виде «если [условие], то [следствие]», или проще «если, то».

Рис. 2.1. Пример дерева решений

18

Подход к построению дерева решений. Пусть нам задано не-

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

Идею построения деревьев решений из множества T, впервые высказанную Хантом, приведем по Р. Куинлену [19, 33]. Пусть через {C1, C2, … Ck} обозначены классы (значения метки класса), тогда могут существовать три ситуации:

1)множество T содержит один или более примеров, относящихся к одному классу Ck. Тогда дерево решений для Т – это лист, определяющий класс Ck;

2)множество T не содержит ни одного примера, т.е. пустое множество. Тогда это снова лист, и класс, ассоциированный с листом, выбирается из другого множества отличного от T, скажем, из множества, ассоциированного с родителем;

3)множество T содержит примеры, относящиеся к разным классам. В этом случае следует разбить множество T на некоторые подмножества. Для этого выбирается один из признаков, имеющий два и более отличных друг от друга значений O1, O2, … On. T разбивается на подмножества T1, T2, … Tn, где каждое подмножество Ti содержит все примеры, имеющие значение Oi для выбранного признака. Это процедура будет рекурсивно продолжаться до тех пор, пока конечное множество не будет состоять из примеров, относящихся к одному и тому же классу.

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

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

На сегодняшний день существует множество алгоритмов, реали-

зующих деревья решений - CART, C4.5, NewId, ITrule, CHAID, CN2

и т.д. Но наибольшее распространение и популярность получили первые два:

CART (Classification and Regression Tree) – алгоритм построения бинарного дерева решений – дихотомической классификационной

19

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

C4.5 (Classification Tree) – улучшенный алгоритм построения дерева решений с неограниченным числом потомков узла. Он не умеет работать с непрерывным целевым полем, поэтому решает только задачи классификации, но не регрессии [32].

Большинство из известных алгоритмов являются так называемыми «жадными алгоритмами». Если один раз был выбран атрибут, и по нему было произведено разбиение на подмножества, то алгоритм не может вернуться назад и выбрать другой атрибут, который дал бы лучшее разбиение. И поэтому на этапе построения нельзя сказать даст ли выбранный атрибут, в конечном итоге, оптимальное разбиение.

Этапы построения деревьев решений. При построении де-

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

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

Для этого были разработаны различные критерии. Мы рассмотрим два из них.

Теоретико-информационный критерий. Алгоритм C4.5, усо-

вершенствованная версия алгоритма ID3 (Iterative Dichotomizer), использует теоретико-информационный подход. Для выбора наиболее подходящего атрибута, предлагается следующий критерий:

где Info(T) – энтропия множества T, а

20