Актуальность темы дипломной работы (стр. 3 )

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

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

Оценивание классификационных методов следует проводить, исходя из следующих характеристик [14]: скорость, робастность, интерпретируемость, надежность.

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

Таблица 1.1. Сравнительная характеристика методов Data Mining

Свойства   Методы	Точность	Масштабируемость	Интерпретируемость	Пригодность к использованию	Трудоемкость	Разносторонность	Быстрота	Популярность, широта использования
Классические методы (линейная регрессия)	средняя	высокая	высокая/ средняя	высокая	средняя	средняя	высокая	низкая
нейронные сети	высокая	низкая	низкая	низкая	средняя	низкая	очень низкая	Низкая
методы визуализации	высокая	очень низкая	высокая	высокая	очень высокая	низкая	чрезвычайно низкая	высокая/ средняя
деревья решений	низкая	высокая	высокая	высокая/ средняя	высокая	высокая	высокая/ средняя	высокая/ средняя
k-ближайшего соседа	низкая	очень низкая	высокая/ средняя	средняя	средняя/ низкая	низкая	высокая	низкая

Метод деревьев решений

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

В наиболее простом виде дерево решений - это способ представления правил в иерархической, последовательной структуре. Основа такой структуры - ответы "Да" или "Нет" на ряд вопросов. Корень - исходный вопрос, внутренний узел дерева является узлом проверки определенного условия. Далее идет следующий вопрос и т. д., пока не будет достигнут конечный узел дерева, являющийся узлом решения. Бинарные деревья являются самым простым, частным случаем деревьев решений. В остальных случаях, ответов и, соответственно, ветвей дерева, выходящих из его внутреннего узла, может быть больше двух. На этапе построения модели, собственно, и строится дерево классификации или создается набор неких правил. На этапе использования модели построенное дерево, или путь от его корня к одной из вершин, являющийся набором правил для конкретного клиента, используется для ответа на поставленный вопрос. Правилом является логическая конструкция, представленная в виде "если : то :". Внутренние узлы дерева являются атрибутами базы данных. Эти атрибуты называют прогнозирующими, или атрибутами расщепления (splitting attribute). Конечные узлы дерева, или листы, именуются метками класса, являющимися значениями зависимой категориальной переменной. Каждая ветвь дерева, идущая от внутреннего узла, отмечена предикатом расщепления. Последний может относиться лишь к одному атрибуту расщепления данного узла. Характерная особенность предикатов расщепления: каждая запись использует уникальный путь от корня дерева только к одному узлу-решению. Объединенная информация об атрибутах расщепления и предикатах расщепления в узле называется критерием расщепления (splitting criterion). Качество построенного дерева решения весьма зависит от правильного выбора критерия расщепления [7].

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

Метод построения правил классификации: алгоритм построения 1-правил [10]

Пусть у нас есть независимые переменные A1...Aj...Ak, принимающие значения <x11..x1n>,…<x1j..xnj>,…<x1k..xnk> соответственно, и зависимая переменная C, принимающая значения c1...cr. Для любого возможного значения каждой независимой переменной формируется правило, которое классифицирует объект из обучающей выборки. В если-части правила указывают значение независимой переменной (Если Aj=xij). В то-части правила указывается наиболее часто встречающееся значение зависимой переменной у данного значения независимой переменной (то C = cr). Ошибкой правила является количество объектов, имеющих данное значение рассматриваемой независимой переменной (Aj=xij), но не имеющих наиболее часто встречающееся значение зависимой переменной у данного значения независимой переменной (C≠cr). Оценив ошибки, выбирается переменная, для которой ошибка набора минимальна.

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

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

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

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

Плюсы алгоритма заключаются в следующем [16]:

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

На первом шаге алгоритма задается число k – количество ближайших соседей. На втором шаге находятся k записей с минимальным расстоянием до вектора признаков нового объекта (поиск соседей). Функция для расчета расстояния должна отвечать следующим правилам:

d(x, y) ≥ 0, d(x, y) = 0 тогда и только тогда, когда x = y;

d(x, y) = d(y, x);

d(x, z) ≤ d(x, y) + d(y, z), при условии, что точки x, y, z не лежат на одной прямой.

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

       ,        (1.1)

где m – количество атрибутов, yi - значение атрибута известной записи, xi - значение атрибута новой записи.

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

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