10.2.2. Неитеративный алгоритм.

Неитеративный вариапг алгоритма построения нелинейного преобразования получается следующим образом. Из конечного множества классифицированных объектов образуем скалярную функцию расстояния, которая связывает расстояния в исходном пространстве с расстояниями в преобразованном пространстве. Эта функция расстояния «в

среднем» уменьшает расстояния внутри классов, сохраняя неизменными расстояния между классами.

Построенная по небольшому числу «опорных точек», функция расстояния задает некоторое преобразование, которое можно применить для модификации еще не классифицированных объектов в реальном времени. При этом не требуется использовать итеративные вычислительные процедуры. Кроме того, не накладывается никаких ограничений ни на число классов, ни на число переменных [Кунтц, 1972а].

Начнем с того, что перепишем (10.39) в виде

где — некоторая константа (т. e. b не зависит от Следовательно, можно использовать первый член (10.42) в качестве эквивалентного критерия

где

и

Критерий (10.43) имеет тот же вид, что и критерий напряжений (10.30), и измеряет степень улучшения разделимости и сохранения структуры исходной конфигурации. Предположим, что в качестве можно взять любые положительные числа. В таком случае У (10.43) минимизируется, если

для каждой пары Равенство (10.46) определяет дискретную зависимость между расстояниями в пространствах X и Y. Прежде всего мы обобщим (10.46) таким образом, чтобы это выражение определяло зависимость между всеми расстояниями в пространствах X и Y, а затем используем эту функцию расстояния для отображения точек из пространства X в пространство У. Используя определение можно переписать (10.46) в виде

Соотношения (10.47) показывают, что точки, характеризующие дискретную зависимость между расстояниями, лежат на одной из двух прямых линий, проходящих через начало координат, как показано на рис. 10.7. На рис. 10.7 большая часть малых расстояний — расстояния внутри классов, между тем как большие расстояния, — в основном, расстояния между классами. Этого может не быть в случае сложных конфигураций.

Рис. 10.7. Дискретная функция расстояния.

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

Мы будем предполагать, что дискретная функция расстояния (10.47) достаточно регулярна, так что связь между расстояниями и может быть с достаточной точностью аппроксимирована полиномом низкого порядка, т. е.

для всех пар , где

— небольшое целое число. Коэффициенты этого полинома можно однозначно определить из условия минимума критерия Можно записать этот критерий в виде

где

в определить оптимальные коэффициенты из условия

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

где

и

Следовательно, оптимальный выбор определяется выражением

Формула (10.57) достаточно проста с точки зрения объема вычислений. Матрица размерности и вектор размерности можно вычислить непосредственно после того, как определены все парные расстояния и выбран коэффициент

Обращение матрицы несложно, так как порядок полинома невысок. На рис. 10.8 приведены два примера функций расстояния, наложенных на линейные зависимости (10.47). Данные, на основании которых они получены, описаны в конце этого параграфа.

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

Рис. 10.8. Полиномиальные функции расстояний,

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

Пусть — евклидово расстояние в -мерном пространстве У. Тогда данную точку У можно однозначно определить набором расстояний между У и соответствующим образом выбранными опорными точками Чтобы убедиться в этом, ваметим, что можно образовать уравнений

где - известные расстояния между Но уравнение (10.58) определяет прямую линию, так как квадратичные члены

сокращаются, и мы получаем

Вводя обозначения

можно записать уравнение (10.59) в матричной форме

Если точки выбраны таким образом, что матрица V невырождена, то (10.63) можно разрешить относительно У.

Опорные точки в пространстве X можно определить разными способами. Например, можно найти набор из векторов, представляющих собой математические ожидания локальных «сгущений» объектов («детали этой процедуры рассматриваются в гл. 11). Их образы в пространстве У, образующие матрицу можно найти следующим образом:

1. Вычислить парных расстояний между опорными точками в пространстве X,

2. Используя функцию расстояния, найти соответствующие расстояния между точками в пространстве У.

3. Найти точек в пространстве У, таких, что расстояния между ними совпадают с расстояниями, найденными на предыдущем

дыдущем шаге. Это не представляет труда, так как размерность пространства лишь на единицу меньше числа точек.

Таким образом, после того как по объектам обучающей последовательности определены опорные точки в пространствах X и Y, мы можем отобразить новый объект X в пространство У с помощью следующего алгоритма.

1. Вычислить расстояние от отображаемой точки X до опорной точки для вычислить используя функцию расстояния.

3. Решить (10.63), т. е.

Уравнение (10.65) определяет У как линейное преобразование вектора С, который является нелинейной функцией от Это преобразование имеет очень простой вид.

Преобразование (10.65) можно упростить. Заметим, что линейный классификатор, определенный на У, может оказаться не лучшим, чем классификатор, определенный на С. Поэтому векторы С, так же, как и векторы У, можно использовать в качестве признаков. Использование С вместо У исключает необходимость нахождения и выполнения трудоемкого линейного преобразования. В примере, который приводится ниже, будет выбран упрощенный метод.

При выводе (10.63) предполагалось, что точка У, расположенная на заданном расстоянии от каждой опорной точки, действительно существует. Однако, если эти расстояния заданы произвольно, наличие такой точки гарантировать нельзя. Тем на менее, решение уравнения (10.63) дает некоторую точку. Как интерпретировать У в этом случае? Можно обойти это затруднение, если без дополнительной аргументации задать линейное преобразование в виде (10.65). К сожалению, этим мы наносим ущерб ранее приведенным аргументам, касающимся улучшения разделимости.

Однако геометрическая интерпретация может помочь объяснить, что происходит с У в этом случае. Каждое уравнение в (10.59) или (10.63) определяет гиперплоскость, связанную с гиперсферами с центрами в и радиусами При размерности 2 эта гиперплоскость превращается в прямую, связанную с двумя окружностями. В аналитической геометрии эта прямая называется радикальной осью двух окружностей [Моррилл, 1951].

Понятие радикальной оси двух окружностей иллюстрируется рис. 10.9. Если две окружности пересекаются, радикальная ось является их общей хордой, проходящей через точки пересечения.

Радикальная ось не существует, когда окружности являются концентрическими.

Решением уравнения (10.63) является пересечение радикальных осей пар гиперсфер, На рис. 10.10 показаны два случая, когда не существует точки У, находящейся на заданном расстоянии от каждой опорной точки.

Рис. 10.9. Положение радикальной оси двух окружностей. а) пересекающиеся окружности; б) непересекающиеся окружности.

Решением уравнения (10.65) является, как показано на рисунке, пересечение радикальных осей. Это решение дает приемлемую компромиссную точку.

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

Пример 10.4. Объекты, показанные на рис. 10.11, не являются линейно разделимыми из-за того, что распределение класса В бимодально. Однако, поскольку перекрытие невелико, нелинейное преобразование может, по-видимому, улучшить разделимость. Эти объекты генерировались в соответствии с нормальными распределениями следующим образом.

Класс А: 100 объектов, порожденных нормальным распределением с математическим ожиданием и ковариационной матрицей

Класс В: 2 раза по 50 объектов, порожденных двумя нормальными распределениями с математическими ожиданиями и ковариационными матрицами

(кликните для просмотра скана)

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

Рис. 10.12. (см. скан) График разброса отображенных объектов для [Кунтц, 1972а].

Эффективность преобразования определялась путем применения преобразования (10.62) ко всем оставшимся объектам. Эти преобразованные объекты классифицировались классификатором, основанным на вычислении расстояний (см. гл. 4), и в качестве меры разделимости использовался процент полученных при этом ошибок. Результаты при разных значениях приведены в табл. 10.4. На рис. 10.12 показаны преобразованные объекты при Может показаться, что чем меньше и чем больше тем лучше результат. Однако в этом случае мы получаем сильное искажение, поскольку функция расстояния приобретает резко колебательный характер (как видно из рис. 10.8).

Таблица 10.4 (см. скан) Ошибки классификации (в процентах) для различных значений порядка полинома и настраиваемою параметра

Предпочтительнее, однако, чтобы преобразование было не слишком «вычурным». Поэтому выбор не самых крайних, а промежуточных значений для представляется более правильным.