Классификация. 
Системы поддержки принятия решений

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

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

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

Рассмотрим один из наиболее популярных методов и, соответственно, технологий классификации, входящих в Data Mining, — метод деревьев решений (decision trees). Деревья решений основаны на машинном обучении, в их основе лежат решающие правила вида «если, то…», которые могут быть сформулированы на естественном языке. В основе метода лежит процесс рекурсивного разделения (разбиения) исходного множества наблюдений или объектов на подмножества таким способом, чтобы значения зависимой переменной в каждом из них были как можно более однородными. На каждом шаге разбиение производится только по одной независимой переменной, а именно по такой, которая делает его наилучшим. Разделение производится с помощью решающих правил, в которых осуществляется проверка значений атрибутов по заданному условию. Решающие правила образуют иерархическую древовидную структуру, позволяющую выполнять классификацию объектов и наблюдений. Эта структура и называется деревом решений. Каждый путь от вершины до листа дерева (конечного узла) образует правило. В режиме предсказания новый объект «прогоняется» сквозь дерево правил и «оседает» в каком-либо листе, т. е. в терминальном узле.

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

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

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

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

Начальный узел дерева является входным: через него проходят все объекты, предъявляемые дереву. Обычно входной узел называют корневым узлом. Следовательно, дерево растет сверху вниз. Узлы и листья, подчиненные узлу более высокого иерархического уровня, называются потомками, или дочерними узлами, а тот узел по отношению к ним — предком, или родительским узлом (рис. 10.7).

Рис. 10.7. Дерево решений.

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

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

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