Принятие решений

Хj=(xj1, xj2,…, xjp), j=1, 2,…, n, p³1. (2.2)

Получается матрица данных размерностью n×p,

, (2.3)

номер строки которой – номер объекта, номер столбца – номер признака каждого объекта.

От природы основных признаков объекта зависят важные теоретические выводы. Объекты, подлежащие классификации, представл

ены в пространстве признаков. Формально это признаковое пространство является p-мерным. Но в связи с корреляцией (зависимостью) между признаками оно может быть преобразовано в пространство меньшей размерности.

Обычной математической основой для классификации объектов являются функции на парах элементов (Xi, Xj), i, j=1,2,…, n, вычисляемые по их признакам. В результате получается матрица сходства rij или различия uij между всеми возможными парами (Xi, Xj). Эти коэффициенты бывают трех видов.

1. Коэффициенты типа расстояния имеют общий вид

, (2.4)

где xis – значение s-го признака для элемента Xi, p – число признаков, m – положительное целое число. При m = 1 – манхэттеновское расстояние, при m = 2 – евклидово расстояние.

2. Коэффициент ассоциативности (КА)

a(Xi, Xj)=pc/p,

pc – число совпадающих признаков элементов Xi, Xj, p – общее число признаков. КА используется для элементов, представленных в виде двоичного кода или словесных обозначений.

3. Коэффициент корреляции (КК) между векторами Xi, Xj определяет меру их угловой близости и выражается через их нормированное скалярное произведение

i, j = 1,2,…, n, (2.5a)

или

, i, j =1,2,…, n. (2.5b)

4. Условная вероятность принадлежности элемента X к классам w1,w2,…,wk, Р (X/wt), t =1,2,…, k, используется в том случае, когда известны, хотя бы приближенно, законы распределения вероятностей значений признаков объектов в каждом классе.

5. Линии регрессии применяются в том случае, когда элементы классов концентрируются вдоль некоторых линий (рис. 2.3), приближенные уравнения которых находятся по данным наблюдениям.

При решении различных задач классификации в зависимости от вида признаков, описывающих классы, используются и различные виды расстояний (метрик) r(Xi, Xj). Но все они должны удовлетворять следующим условиям:

r(Xi, Xj) ³ 0 – неотрицательность,

r(Xi, Xj) = 0 тогда и только тогда, когда Xi=Xj – аксиома тождества,

r(Xi, Xj) = (Xj, Xi) – аксиома симметрии,

r(Xi, Xj) £ r(Xi, Xs) + r(Xs, Xj) – аксиома треугольника.

Кроме отмеченных выше видов расстояний в классификаии используются следующие:

,

(2.6a)

- расстояние Махаланобиса, в котором S – ковариационная матрица каждого класса, значок «’» обозначает транспонирование, (Xi-Xj) – вектор-строка, (Xi-Xj)’ – вектор-столбец. Если матрица S диагональная, на главной диагонали ее стоят дисперсии признаков s12,s22,…,sР2, то расстояние Махаланобиса принимает вид

(2.6b)

Далее для проведения классификации математическими методами необходимо задать математическое правило классификации, соответственно связанное с выбранной мерой близости объектов. Поэтому классификация проводится по расстояниям, коэффициентам ассоциативности и корреляции, по вероятностям, по линиям регрессии. Например, при классификации по расстоянию два объекта Xi, Xj относятся к одному классу ws, sÎ{1,2,…, k}, если r(Xi, Xj)£r0, r0 – заданное пороговое значение расстояния для каждого класса; при классификации по вероятности объект X относят к тому классу wi0, для которого условная вероятность максимальна,

(2.7)

Итак, для проведения классификации объектов математическими методами необходимо составить их описание числовыми признаками, задать меру их близости и правило классификации.

2.3 Критерий оптимальной классификации

При проведении классификации данного множества объектов с использованием различных методов и алгоритмов, как правило, получаются различные результаты. Естественно оптимальным вариантом классификации считать тот вариант, который содержит наименьшее число ошибок. Поэтому за критерий качества классификации принимается минимум вероятности ошибки классификации Рош. Этот критерий применим лишь в случаях, когда можно найти оценку величины Рош. Но во многих ситуациях это невозможно, и тогда при выборе наилучшей классификации используют функционалы качества разбиения, среди которых выделим три основных вида: функционалы от внутриклассовых расстояний Ф(rij(o)), функционалы от межклассовых расстояний U(rij(m)), функционалы смешанного типа V(rij(o), rij(m)). Как правило, функционалы Ф(rij(o)) минимизируются, а функционалы U(rij(m)) максимизируются.

2.4 Основные условия, гарантирующие оптимальную классификацию

Для получения оптимальной классификации необходимо выполнение следующих условий:

1. Представление объектов в виде p-мерных векторов (р³1) должно достаточно полно отражать основные свойства каждого класса. К примеру, если множество наблюдений содержит всю информацию, получаемую с черно–белого телевизора, то при этом невозможно построить алгоритм выделения «красных» входных сигналов.

2. Должны быть заданы представительные (репрезентативные) подмножества наблюдений каждого класса. Если наблюдения, по которым изучаются характеристики класса, не представляют множество других элементов класса, то после обучения будут получены очень неполные (и возможно ошибочные) знания об этом классе и нельзя ожидать хорошего распознавания.

3. При выборе расстояния (метрики) в пространстве наблюдений (пока неизвестным способом) объекты, относящиеся к одному классу, должны быть близки один к другому. На рис. 2.4, а представлен случай, когда расстояние Евклида неприемлемо, так как существуют точки, для которых внутриклассовые расстояние больше межклассовых, например r(X1, X2)>r(X2, X3), X1, X2Îw1, X3Îw2.

Здесь целесообразно использовать расстояние Махаланобиса (2.6), которое ввиду диагональности ковариационной матрицы примет вид

Для всех точек представленного множества внутриклассовое расстояние Малаханобиса не больше межклассового.

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

 Скачать реферат