Новости    Библиотека    Байки    Ссылки    О сайте


предыдущая главасодержаниеследующая глава

Приложение 5. I. Формальное описание процедуры сокращения размерности исходного описания с использованием информации о признаках (первая задача)

1. Постановка задачи. Пусть X - I-мерное пространство исходного описания, a Ỹ - J-мерное подпространство признаков, оптимизированное по какому-либо из изложенных в главе IV критерию.

Обозначим также Y - полное I-мерное пространство признаков (преобразованное пространство исходного описания), первые J базисных векторов которого совпадают с базисом подпространства Ỹ, т. е. с признаками. Пусть х∈Х точка пространства исходного описания, а y и ỹ - отображения х в Y и Ỹ соответственно. Эти отображения осуществляются некоторым линейным оператором WT (матрицей перехода), т. е.


где


оператор проектирования на первые J осей. Индекс "т" означает операцию транспонирования.

Так как строки матрицы


(или первые J строк WT) являются признаками, то, следовательно, в этой матрице отражены все свойства используемого критерия.

Рассмотрим воздействие матрицы перехода в подпространство признаков на вектор


исходного описания

(5.I.1)

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


"берут на себя" наибольшую долю полной дисперсии взаимных расстояний. Доля дисперсии, приходящаяся на оставшиеся I-J новых осей, незначительна, следовательно, она мала и на каждую из них. Таким образом, преобразованный вектор


можно разбить на два подвектора


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

Если величина критерия преобразованного вектора Y па последние I - J осей


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

Произведем замену некоторых параметров, например, - линейными комбинациями оставшихся

(5.I.2)

Измененный вектор исходного описания имеет вид


Преобразуем этот вектор в пространство признаков с помощью матрицы перехода W̃T

(5.I.3)

Потребуем теперь, чтобы новый вектор z в некотором смысле не слишком сильно отличался от вектора ỹ, переведенного в пространство признаков по полному исходному описанию (5.1.1). Для этого образуем какую-либо выпуклую функцию модуля разности этих векторов


и будем искать ее минимум но совокупности векторов


в среднем для всех реализаций учебной выборки и по всем наборам индексов {js} размера S:

(5.I.4)

Требуется найти максимальное число S исключаемых исходных параметров и указать каких именно, т. е. указать набор индексов


при которых функционал (5,1.4) не превышал бы некоторого заданного значения d.

Формально задача сокращения исходного описания с точки зрения наблюдателя, находящегося в подпространстве признаков, может быть записана следующим образом


при условии


где


Очевидно, в такой постановке для больших I и S (а именно такие значения представляют интерес) эта задача практически нереализуема, так как минимум требуется искать, с одной стороны, по векторам


(это для данного набора индексов {js} поддается аналитическому решению), а с другой - требуется перебирать наборы индексов CSI раз, причем число исключаемых параметров S также переменно. Поэтому первым шагом к субоптимальному решению является отказ от поиска векторов


2. Субоптимальный алгоритм. В качестве коэффициентов линейных комбинаций (5.1.2) можно использовать элементы wij самой матрицы перехода WT из X в Y.

В самом деле, если, как уже указывалось, последние координаты в (5.1. 1)


в среднем достаточно малы, то мы не совершим большой ошибки в силу непрерывности WT, если "насильственно" сделаем некоторые из них


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


Пусть для простоты


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


то любой из них может быть представлен в виде

(5.I.5)

где D - определитель, составленный из элементов матрицы перехода, которые соответствуют заменяемым исходным параметрам в уравнении (5. I. 3).

(5.I.6)

Ds - определитель, полученный из определителя D заменой s-го столбца элементами ct.


(5.I.7)

Разлагая Ds no s-му столбцу, (5.1.5) можно записать n более удобном виде:

(5.I.8)

где Ats - алгебраическое дополнение D (5.1.6).

Линейные комбинации (5.1.8) подставляем в вектор исходного описания и переводим его в пространство признаков (5.1.3). Если теперь близость векторов ỹ и z определить как близость в среднем, то средний квадрат ошибки представления признаков с помощью сокращенного описания для данного набора индексов


можно получить в виде:

(5.I.9)

или

(5.I.10)

где λt - дисперсия взаимных расстояний между образами на направление


Можно требовать так же, как и при нахождении признаков, среднюю близость ỹ и z с весом, чтобы лучше учесть различие между "близкими" образами за счет несколько большей потери для различных "далеких". Введение весов не меняет существа самой процедуры. Необходимо лишь заменить дисперсии ^ на взвешенные дисперсии λ*t.


Как видно из (5.1. 9), перебор по подмножествам индексов {js}, s = 1, 2, . . ., S для нахождения минимума слишком велик, если число заменяемых параметров S исходного описания велико.

3. Упрощенный алгоритм. Дальнейшим шагом упрощения решения задачи является отказ от полного перебора вариантов, который заменяется последовательным перебором по одной переменной (по одному индексу js, s = 1, 2, . . .) некоторое число раз, до тех пор, пока величина ошибки (5. I. 10) не достигнет заданного порога.

На первом шаге ищется перебором такой исходный параметр xjs, замена которого линейными комбинациями оставшихся из некоторого t-го уравнения связи ("подвал" уравнения (5.1.1)) дает наименьшее расхождение между векторами ỹ и z (5.1.1)" (5.1.3).

Величина расхождения в этом случае определяется выражением

(5.I.11)

Очевидно, что для определения минимума (5.1.11) следует в каждой строке "подвала" матрицы перехода WT выбрать самый "жирный" по модулю элемент и просчитать (5.1.11) по всем возможным уравнениям связи (5.1.1).

На втором шаге процедура повторяется с учетом того, что один исходный параметр уже исключен, и т. д. После каждого шага величина (5.1. 11) сравнивается с порогом d̄2 и после его достижения процедура обрывается.

Выбор самого "жирного" элемента в строке матрицы перехода удобно интерпретировать геометрически. Как уже указывалось, строки этой матрицы представляют собой векторы, заданные относительно арифметического базиса исходного описания, т. е. координаты этих векторов-признаков представляют собой косинусы углов с базисом описания. Наиболее "жирный" по модулю элемент строки есть наименьший угол между отбрасываемой (неинформативной) осью в пространстве признаков и каким-либо параметром исходного описания. Очевидно, что если отбросить эти параметры, то величина расхождения (5.1.11) будет наименьшая. Это несправедливо, к сожалению, для совокупности параметров, если матрица признаков не ортогональная.

Эти геометрические представления позволяют указать па самую простую процедуру минимизации описания (а соответственно, паи' менее оптимальную).

4. Простейший алгоритм. В каждом уравнении связи


находится самый "жирный" по модулю элемент wtjs. Эти элементы упорядочиваются по величине, и замена исходных параметров производится последовательно начиная с самого "жирного".

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

предыдущая главасодержаниеследующая глава





Пользовательский поиск


Диски от INNOBI.RU




© Злыгостев Алексей Сергеевич, подборка материалов, оцифровка, статьи, оформление, разработка ПО 2001-2017
При копировании материалов проекта обязательно ставить активную ссылку на страницу источник:
http://informaticslib.ru/ "InformaticsLib.ru: Информатика"