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

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

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

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

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

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

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

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

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