Задача классифика́ции — задача, в которой имеется множество объектов ( ситуаций ), разделённых, некоторым образом, на классы . Задано конечное множество объектов, для которых известно, к каким классам они относятся. Это множество называется выборкой . Классовая принадлежность остальных объектов неизвестна. Требуется построить алгоритм , способный классифицировать (см. ниже) произвольный объект из исходного множества .

Классифици́ровать объект — значит, указать номер (или наименование) класса, к которому относится данный объект.

Классифика́ция объекта — номер или наименование класса, выдаваемый алгоритмом классификации в результате его применения к данному конкретному объекту.

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

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

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

Математическая постановка задачи

Пусть ${\displaystyle X}$ — множество описаний объектов, ${\displaystyle Y}$ — множество номеров (или наименований) классов. Существует неизвестная целевая зависимость — отображение ${\displaystyle y^{*}\colon X\to Y}$ , значения которой известны только на объектах конечной обучающей выборки ${\displaystyle X^{m}=\{(x_{1},y_{1}),\dots ,(x_{m},y_{m})\}}$ . Требуется построить алгоритм ${\displaystyle a\colon X\to Y}$ , способный классифицировать произвольный объект ${\displaystyle x\in X}$ .

Вероятностная постановка задачи

Более общей считается вероятностная постановка задачи. Предполагается, что множество пар «объект, класс» ${\displaystyle X\times Y}$ является вероятностным пространством с неизвестной вероятностной мерой ${\displaystyle {\mathsf {P}}}$ . Имеется конечная обучающая выборка наблюдений ${\displaystyle X^{m}=\{(x_{1},y_{1}),\dots ,(x_{m},y_{m})\}}$ , сгенерированная согласно вероятностной мере ${\displaystyle {\mathsf {P}}}$ . Требуется построить алгоритм ${\displaystyle a\colon X\to Y}$ , способный классифицировать произвольный объект ${\displaystyle x\in X}$ .

Признаковое пространство

Признаком называется отображение ${\displaystyle f\colon X\to D_{f}}$ , где ${\displaystyle D_{f}}$ — множество допустимых значений признака. Если заданы признаки ${\displaystyle f_{1},\dots ,f_{n}}$ , то вектор ${\displaystyle {\mathbf {x} }=(f_{1}(x),\dots ,f_{n}(x))}$ называется признаковым описанием объекта ${\displaystyle x\in X}$ . Признаковые описания допустимо отождествлять с самими объектами. При этом множество ${\displaystyle X=D_{f_{1}}\times \dots \times D_{f_{n}}}$ называют признаковым пространством .

В зависимости от множества ${\displaystyle D_{f}}$ признаки делятся на следующие типы:

• бинарный признак: ${\displaystyle D_{f}=\{0,1\}}$ ;
• номинальный признак: ${\displaystyle D_{f}}$ — конечное множество;
• порядковый признак: ${\displaystyle D_{f}}$ — конечное упорядоченное множество;
• количественный признак: ${\displaystyle D_{f}}$ — множество действительных чисел .

Часто встречаются прикладные задачи с разнотипными признаками, для их решения подходят далеко не все методы.

Типология задач классификации

Типы входных данных

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

Классификацию сигналов и изображений называют также распознаванием образов .

Типы классов

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

См. также

• Задачи прогнозирования
• Распознавание образов
• Наивный байесовский классификатор
• Метод k ближайших соседей
• Линейный классификатор
• Классификация текстов

Ссылки

• — профессиональный вики-ресурс, посвященный машинному обучению и интеллектуальному анализу данных
• Константин Воронцов . Курс лекций , МФТИ , 2004-2008
• Юрий Лифшиц . (Слайды) — лекция №6 из курса
• ( апплет ), Е.М. Миркес и университет Лейстера.

Литература

• Айвазян С. А., Бухштабер В. М., Енюков И. С., Мешалкин Л. Д. Прикладная статистика : классификация и снижение размерности . — М.: Финансы и статистика, 1989.
• Вапник В. Н. Восстановление зависимостей по эмпирическим данным. — М.: Наука, 1979.
• Журавлёв Ю. И. , Рязанов В. В., Сенько О. В. «Распознавание». Математические методы. Программная система. Практические применения. — М.: Фазис, 2006. ISBN 5-7036-0108-8 .
• Загоруйко Н. Г. Прикладные методы анализа данных и знаний. — Новосибирск : ИМ СО РАН, 1999. ISBN 5-86134-060-9 .
• Шлезингер М., Главач В. Десять лекций по статистическому и структурному распознаванию. — Киев : Наукова думка , 2004. ISBN 966-00-0341-2 .
• Hastie, T., Tibshirani R., Friedman J. . — 2nd ed. — Springer-Verlag, 2009. — 746 p. — ISBN 978-0-387-84857-0 . .
• Mitchell T. Machine Learning. — McGraw-Hill Science/Engineering/Math, 1997. ISBN 0-07-042807-7 .