9306

100

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

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

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

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

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

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

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

101

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

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

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

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

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

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

базы знаний.

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

визуализации:

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

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

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

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

102

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

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

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

илегко интерпретируемыми моделями.

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

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

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

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

103

−Различимость классов – должна обеспечиваться принципиальная возможность установления факта принадлежности или непринадлежности примера к определенному классу. При этом количество примеров должно быть намного больше, чем количество классов.

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

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

Например, стоит задача разбить множество объектов недвижимости на 2 класса: дорогие или недорогие квартиры с помощью набора решающих правил на основе единственного атрибута общая площадь квартиры. Для этого будем использовать множество наблюдений, в каждом из которых должна быть указана общая площадь, а также факт дорогая/недорогая квартира. Графически такое множество наблюдений представлено на рис.4.1. Условно примем, что объект в форме круга указывает на недорогую квартиру, в форме прямоугольника – на дорогую квартиру, а внутри каждого объекта указана общая площадь квартиры.

Рис.4.1. Разделение на классы

104

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

Выберем некоторое пороговое значение общей площади, например, равное 40 квадратным метрам, и разобьем исходное множество на 2 подмножества соответствии с условием общая площадь>40. В результате разбиения в одном подмножестве окажутся все записи, для которых значение атрибута общая площадь больше 40, а во втором – меньше 40. На рис. 4.1 данные подмножества обозначены номерами 1 и 2 соответственно. Легко увидеть, что выбор порогового значения общей площади, равного 40, не позволил получить подмножества, содержащие только объекты одного класса, поэтому для решения задачи применяется разбиение полученных подмножеств. Поскольку для этого имеется только один атрибут – общая площадь, мы будем использовать его и в дальнейшем, но в условиях выберем другой порог. Например, для подмножества 1 применим порог 50, а для подмножества 2 – 20.

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

Рис.4.2. Продолжение деления на классы На рис. 4.2 можно увидеть, что задача решена: исходное множество

удалось разбить на чистые подмножества, содержащие только наблюдения одного класса. Дерево, реализующее данную процедуру, представлено на рис.4.3. В нем подмножества 3 и 5 ассоциированы с классом недорогих квартир, а подмножества 4 и 6 – с классом дорогих квартир.

105

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

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

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

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

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

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

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

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

106

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

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

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

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

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

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

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

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

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

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

− достоверность (confidence) – отношение числа правильно классифицированных примеров к числу неправильно классифицированных:

Nошибка

107

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

Пример построения классифицирующего дерева решений для оценки недвижимости в аналитической платформе Deductor Studio Academic.

Рассмотрим построение модели классификации, относящей объекты недвижимости на основе их признаков к одному из трех классов «дорогие, средние, дешевые квартиры». Таблица 6

Входные атрибуты, влияющие на оценку жилья

108

Шаг 1. Загрузка данных и проверка их качества определяется с помощью визуализаторов Статистика и различных диаграмм.

Шаг 2. Очистка данных, используя следующие обработчики:

−«Парциальная обработка» – восстановление, редактирование, сглаживание данных;

−«Факторный анализ» – понижение размерности входных факторов;

−«Корреляционный анализ» – устранение незначащих факторов;

−«Дубликаты и противоречия» – выявление дубликатов и противоречий;

−«Фильтрация» – фильтрация строк таблицы по условию.

Шаг 3. Трансформация данных (так как обработчик Дерево решений

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

Квантование.

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

109

Для разбиения нужно настроить следующие параметры квантования:

−Способ – выбираем из списка способ квантования по квантилям, чтобы в каждый из квантильных интервалов попадало одинаковое количество квартир.

−Интервал – указываем количество интервалов, на которое будет разбит диапазон исходных данных. Разбиваем на три интервала, так как в необходимо все объекты недвижимости разбить на 3 класса.

−Значение – указываем 3 интервала, например: от 51111,11 до 60000 рублей; от 60000 до 62857,15 рублей; от 62857,15 до75000 рублей.

Шаг 4. Применяя обработчик «Замена значений», по таблице подстановок присваиваем интервалам, полученным на предыдущем шаге метки <Дешевая квартира>, <Средняя квартира>, <Дорогая квартира>.

Шаг 5. Строим модель классификации объектов недвижимости, используя обработчик Дерево решений:

1)Определяем назначение полей

Рис. 4.4. Настройка назначений столбцов в обработчике «Дерево решений»

2)Выбор способа разделения исходного множества на два – обучающее

итестовое.