Задача классификации | это... Что такое Задача классификации? (original) (raw)

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

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

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

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

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

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

Содержание

1 Математическая постановка задачи
- 1.1 Вероятностная постановка задачи
- 1.2 Признаковое пространство
2 Типология задач классификации
- 2.1 Типы входных данных
- 2.2 Типы классов
3 См. также
4 Ссылки
5 Литература

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

Пусть — множество описаний объектов, — множество номеров (или наименований) классов. Существует неизвестная целевая зависимость — отображение $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 признаки делятся на следующие типы:

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

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

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

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

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

Типы классов

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

См. также

Ссылки

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

Литература

Айвазян С. А., Бухштабер В. М., Енюков И. С., Мешалкин Л. Д. Прикладная статистика: классификация и снижение размерности. — М.: Финансы и статистика, 1989.
Вапник В. Н. Восстановление зависимостей по эмпирическим данным. — М.: Наука, 1979.
Журавлев Ю. И., Рязанов В. В., Сенько О. В. «Распознавание». Математические методы. Программная система. Практические применения. — М.: Фазис, 2006. ISBN 5-7036-0108-8.
Загоруйко Н. Г. Прикладные методы анализа данных и знаний. — Новосибирск: ИМ СО РАН, 1999. ISBN 5-86134-060-9.
Паклин Н.Б., Орешков В.И. Бизнес-аналитика: от данных к знаниям (+ СD). -СПб: Питер, 2009. ISBN 978-5-49807-257-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.