Задача классификации

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

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

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

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

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

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

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

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

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

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

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

В зависимости от множества $D_f$ признаки делятся на следующие типы:

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

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

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

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

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

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

Типы классов

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

См. также

• Задачи прогнозирования
• Распознавание образов

Ссылки

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

Литература

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