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

09.03.2021

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

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

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

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

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

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

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

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

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

Более общей считается вероятностная постановка задачи. Предполагается, что множество пар «объект, класс» X × Y {displaystyle X imes Y} является вероятностным пространством с неизвестной вероятностной мерой P {displaystyle {mathsf {P}}} . Имеется конечная обучающая выборка наблюдений X m = { ( x 1 , y 1 ) , … , ( x m , y m ) } {displaystyle X^{m}={(x_{1},y_{1}),dots ,(x_{m},y_{m})}} , сгенерированная согласно вероятностной мере P {displaystyle {mathsf {P}}} . Требуется построить алгоритм a : X → Y {displaystyle acolon X o Y} , способный классифицировать произвольный объект x ∈ X {displaystyle xin X} .

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

Признаком называется отображение f : X → D f {displaystyle fcolon X o D_{f}} , где D f {displaystyle D_{f}} — множество допустимых значений признака. Если заданы признаки f 1 , … , f n {displaystyle f_{1},dots ,f_{n}} , то вектор x = ( f 1 ( x ) , … , f n ( x ) ) {displaystyle {mathbf {x} }=(f_{1}(x),dots ,f_{n}(x))} называется признаковым описанием объекта x ∈ X {displaystyle xin X} . Признаковые описания допустимо отождествлять с самими объектами. При этом множество X = D f 1 × ⋯ × D f n {displaystyle X=D_{f_{1}} imes dots imes D_{f_{n}}} называют признаковым пространством.

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

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

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

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

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

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

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

Типы классов

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