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

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

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

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

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

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

Пусть $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}$ — множество действительных чисел.

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

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

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

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

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

Типы классов

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

См. также

Литература

Айвазян С. А., Бухштабер В. М., Енюков И. С., Мешалкин Л. Д. Прикладная статистика: классификация и снижение размерности. — М.: Финансы и статистика, 1989.
Вапник В. Н. Восстановление зависимостей по эмпирическим данным. — М.: Наука, 1979.
Гудфеллоу Я., Бенджио И., Курвилль А. Глубокое обучение / пер. с анг. А. А. Слинкина. — 2-е изд., испр.. — М.: ДМК Пресс, 2018. — 652 с. — ISBN 978-5-97060-618-6.
Журавлёв Ю. И., Рязанов В. В., Сенько О. В. «Распознавание». Математические методы. Программная система. Практические применения. — М.: Фазис, 2006. ISBN 5-7036-0108-8.
Загоруйко Н. Г. Прикладные методы анализа данных и знаний. — Новосибирск: ИМ СО РАН, 1999. ISBN 5-86134-060-9.
Шлезингер М., Главач В. Десять лекций по статистическому и структурному распознаванию. — Киев: Наукова думка, 2004. ISBN 966-00-0341-2.
Hastie, T., Tibshirani R., Friedman J. The Elements of Statistical Learning: Data Mining, Inference, and Prediction. — 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.

Ссылки

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