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

Так как истинная размерность данных определяется локальными размерностями, то при неограниченном числе наблюдений и отсутствии шума истинная размерность находится уменьшением размера локальных областей до тех пор, пока получаемая размерность не достигнет предельного значения. На практике, однако, имеется несколько факторов, усложняющих эту процедуру: 1) ограниченное число наблюдений; 2) наличие шума; 3) большой расход машинного времени.

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

Наиболее простая процедура оценки локальной размерности состоит в вычислении собственных значений выборочной ковариационной матрицы в локальной области и подсчете числа доминирующих собственных значений. Величина порога, выбранного для отделения доминирующих собственных значений, влияет на оценку размерности. Пусть величина порога составляет от величины наибольшего собственного значения. Число объектов, необходимое для оценки числа доминирующих собственных значений, обычно во много раз меньше, чем требуется для оценки самих собственных значений. Опыт показывает, что это число должно лишь в 2—3 раза прёвышать число доминирующих собственных значений независимо от числа переменных Например при достаточно, чтобы даже для Так как для большинства приложений то для определения собственных значений следует использовать метод, примененный в примере 2.20.

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

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

Рассмотрим один из воможных алгоритмов решения этой задачи [Фукунага, 1971а].

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

Рис. 10.3. Влияние шума.

Размер задается или радиусом гиперсферы, или числом объектов в локальной области. Оператор должен иметь возможность корректировать размер всякий раз, когда в этом возникнет необходимость.

2. Выбор локальных центров. Решение этой задачи требует поиска в пространстве высокой размерности и включает много компромиссных решений, касающихся, например, выбора размера локальной области, величины перекрытия и метода поиска. Одно из возможных решений состоит в том, чтобы в качестве первого локального центра выбрать первый объект из списка объектов. Объекты локальной области, построенной вокруг этого первого объекта, используются для определения локальной размерности, а затем исключаются из списка. Эта процедура повторяется до тех пор, пока список не станет пустым. Для определения истинной размерности исходных данных вычисляются статистики локальных размерностей.

Пример 10.1. Гауссовская последовательность является распространенной случайной функцией, так как она с приемлемой точностью аппроксимирует многие сигналы, встречающиеся на практике, а для ее описания достаточно трех параметров, как показано в (10.2). В рассматриваемом примере параметры были равномерно распределены в интервалах

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

а При каждом случайно выбранном наборе параметров генерировалось 100 20-мерных объектов. Результаты, относящиеся к этому примеру, приведены в табл. 10.1.

Данные приведены лишь для некоторых типичных локальных областей, так как разница между максимальными и минимальными размерностями невелика. Табл. 10.16 — это одна из итоговых таблиц, построенных в процессе работы алгоритма. Опа показывает, что истинная размерность равна 2. Глобальное разложение Карунена — Лоева дает размерность 4 для критерия и 6 для критерия

Пример 10.2. В этом примере для генерирования данных также использовалась гауссовская последовательность с тремя случайными параметрами, равномерно распределенными в интервалах

При каждом случайно выбранном наборе параметров генерировалось по 125 20-мерных объектов. В табл. 10.2 приведены итоговые результаты.

Таблица 10.2

Итоговая таблица гауссовской последовательности с тремя случайными параметрами

Таблица показывает, что истинная размерность равна 2 и 3, в то время как размерность глобального разложения Карунена — Лоева равна 4 и 7 для критериев соответственно.