Главная > Интеллектуальные системы > Введение в статистическую теорию распознавания образов
<< Предыдущий параграф
Следующий параграф >>
<< Предыдущий параграф Следующий параграф >>
Макеты страниц

10.2.1. Улучшение разделимости, сохранение структуры, расстояния между объектами выборки.

Пусть дано множество из классифицпрованпых векторов Пусть вектор принадлежит классу , где — положительное целое число, — число классов. Итеративное преобразование переводит это множество в множество из векторов-признаков Функциональный вид этого преобразования явно не определен. Признаки выбираются таким образом, чтобы максимизировать критерий вида

где

и

обозначают, соответственно, множества векторов-наблюдений, векторов-признаков и индексов классификации. Член характеризует степень соответствия структуры векторов-признаков структуре векторов-наблюдений. Член характеризует разделимость классов в пространстве Наконец, — множитель, устанавливающий относительную важность и при определении Мера степени соответствия между и X строится, исходя из расстояний между объектами в пространствах и X. К настоящему времени предложены три таких меры, или критерия:

1. Критерий монотонности [Шепард, 1962а, б];

где

а — ранг расстояния, определяемый в соответствии с (10.18).

2. Критерий «напряжения» [Крускал, 1964а, б]:

3. Критерий непрерывности [Шепард, 1966]:

Суммирование производится по всем парам Веса обычно выбираются так, чтобы меньшим соответствовали большие веса. Типичное правило приписывания весов задается выражением

где а — неотрицательный свободный параметр.

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

В качестве можно использовать любой критерий разделимости. В гл. 9 мы рассматривали некоторые из таких критериев, в том числе критерии представляющие собой меру разброса (см. (9.13) — (9.16)), расстояние Бхатачария и дивергенцию. В случае нелинейного преобразования фактор простоты играет существенно более важную роль при оценке критериев. Поэтому, хотя имеется много критериев разделимости и все они могут быть использованы в качестве предпочтение отдается критериям, имеющим простой вид. Например, можно использовать след матрицы разброса внутри классов:

где — математическое ожидание векторов У, отнесенных к классу — число объектов в классе Если использовать качестве и нормировать систему координат так, чтобы матрица стала единичной матрицей, то этот критерий совпадает с критерием Можно переписать (10.33), выразив через расстояния между объектами. Читатель может легко проверить, что

где в качестве берется выборочное среднее

Выражение (10.34) представляет в виде взвешенной суммы квадратов расстояний между объектами одного и того же класса. Можно несколько видоизменить приписав этим квадратам расстояний веса в соответствии с (10.32):

где

Как только выбраны, признаки У можно найти, например, методом наискорейшего спуска. Рекуррентную процедуру минимизации можно записать в общем виде следующим образом:

где

— подходящим образом выбранная положительная константа. Например, если использовать (10.30) в качестве меры сохранения структуры, критерий принимает вид

а рекуррентное выражение для

Для определения оптимальных У может быть также использован алгоритм случайного поиска [Калверт, 1969]. На каждом шаге вычисляется следующим образом:

где — случайный вектор той же размерности, что и Если дает улучшение критерия по сравнению с то принимается в качестве нового У; в противном случае генерируется новое V. Алгоритм заканчивает работу, когда дальнейшее улучшение получить уже не удается.

К сожалению, итеративпый характер рассмотренных алгоритмов ограничивает их применимость (см. замечания в начале этого параграфа). Рассмотрим теперь неитеративный алгоритм, по-прежнему основанный на идее улучшения разделимости и сохранения структуры.

<< Предыдущий параграф Следующий параграф >>
Оглавление