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

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

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

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

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

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

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

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

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

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

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

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

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

В зависимости от множества [math]\displaystyle{ D_f }[/math] признаки делятся на следующие типы:

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

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

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

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

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

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

Типы классов

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

См. также

Ссылки

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

Литература

Айвазян С. А., Бухштабер В. М., Енюков И. С., Мешалкин Л. Д. Прикладная статистика: классификация и снижение размерности. — М.: Финансы и статистика, 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. 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.

Искусственный интеллект
История	История искусственного интеллекта Зима искусственного интеллекта Дартмутский семинар
Философия	Тест Тьюринга Китайская комната Сильный и слабый искусственные интеллекты Дружественный искусственный интеллект Этика искусственного интеллекта Проблема контроля
Направления	Агентный подход Адаптивное управление Инженерия знаний Модель жизнеспособной системы Машинное обучение Нейронная сеть Нечёткая логика Обработка естественного языка Распознавание образов Роевой интеллект Символический ИИ Эволюционные алгоритмы Экспертная система
Применение	Голосовое управление Задача классификации Классификация документов Кластеризация документов Кластерный анализ Локальный поиск Машинный перевод Оптическое распознавание символов Распознавание речи Распознавание рукописного ввода Игровой ИИ Промпт
Исследователи	Чарлз Бэббидж Владимир Вапник Джозеф Вейценбаум Норберт Винер Виктор Глушков Владимир Городецкий Ян ЛеКун Алексей Ляпунов Джон Маккарти Марвин Мински Аллен Ньюэлл Сеймур Пейперт Джуда Перл Гермоген Поспелов Дмитрий Поспелов Фрэнк Розенблатт Герберт Александер Саймон Алан Тьюринг Патрик Уинстон Виктор Финн Сергей Фомин Демис Хассабис Джеффри Хинтон Ноам Хомский Клод Шеннон Эндрю Ын Элиезер Юдковский

Машинное обучение и data mining
Задачи	Задача классификации Обучение без учителя Обучение с частичным привлечением учителя Регрессионный анализ AutoML Ассоциативные правила Выделение признаков Обучение признакам Обучение ранжированию Грамматический вывод Онлайновое обучение
Обучение с учителем	Метод k-ближайших соседей Наивный байесовский классификатор Дерево решений Метод опорных векторов Линейная регрессия Логистическая регрессия Перцептрон Ансамбли моделей Бэггинг Бустинг Random forest Метод релевантных векторов
Кластерный анализ	Метод k-средних Метод нечёткой кластеризации Иерархическая кластеризация EM-алгоритм BIRCH CURE DBSCAN OPTICS Mean-shift
Снижение размерности	Факторный анализ Метод главных компонент CCA ICA LDA Неотрицательное матричное разложение t-SNE
Структурное прогнозирование	Графовая вероятностная модель Байесовская сеть Скрытая марковская модель CRF
Выявление аномалий	Метод k-ближайших соседей Локальный уровень выброса
Графовые вероятностные модели	Байесовская сеть Марковская сеть Скрытая марковская модель
Нейронные сети	Ограниченная машина Больцмана Самоорганизующаяся карта Функция активации Сигмоида Softmax Радиально-базисная функция Метод обратного распространения ошибки Глубокое обучение Многослойный перцептрон Рекуррентная нейронная сеть Долгая краткосрочная память Управляемый рекуррентный блок Свёрточная нейронная сеть U-Net Автокодировщик
Обучение с подкреплением	Марковский процесс Уравнение Беллмана Жадный алгоритм Q-обучение SARSA Temporal difference (TD)
Теория	Теория Вапника — Червоненкиса Дилемма смещения–дисперсии Теория вычислительного обучения Минимизация эмпирического риска Оккамово обучение PAC learning Статистическая теория обучения
Журналы и конференции	NeurIPS ICML ML JMLR ArXiv:cs.LG