9.2. Фильтрация множеств

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

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

Обратная фильтрация заключается в формировании _P точек, лежащих в окрестности наперед заданной точки.

Таким образом, прямая фильтрация применяется для «прореживания» множества точек, а обратная – для выделения точек в заданной области.

Пусть – конечное множество векторов. Процессы прямой и обратной фильтрации основаны на сравнении расстояния между парами векторов вычисляемого по формуле:

где – вес для выравнивания диапазона, соответствующий i-й координате выравниваемых векторов; p – параметр метрики, .

Веса для выравнивания диапазона предназначены для выравнивания разбросов векторов из V:

,

где

Рассмотрим алгоритмы прямой фильтрации множеств, среди которых выделяют следующие:

1) метод первой точки вне окрестности;

2) метод ближайшей точки вне окрестности;

3) метод наиболее удаленной точки вне окрестности.

Во всех перечисленных методах применятся отношение фильтрации, предназначенное для сравнения взвешенных расстояний между точками, которые еще не «задержаны» фильтром, и точками, уже «задержанными». Отношение фильтрации задается в виде:

где – вектор, который еще не задержан фильтром; – задержанный фильтром вектор. Параметр прямой фильтрации регулирует отношение фильтрации следующим образом: если расстояние между точками и больше или равно _d, то эти точки считаются существенно отличающимися. В противном случае точки считаются несущественно отличающимися.

Метод первой точки вне окрестности

Метод первой точки вне окружности запишем в виде последовательностей шагов алгоритма 2.

Алгоритм 2. Алгоритм фильтрации множества методом первой точки вне окрестности

Шаг 0. Начальные данные: – исходное множество векторов с заданной последовательностью точек; _d – радиус окрестности; – множество векторов, задержанных фильтром.

Шаг 1. – первая точка, задержанная фильтром;

Шаг 2. Если , то перебирая последовательно точки множества , находим первую такую точку что (т.е. существенно отличается от отфильтрованных векторов).

Если такой точки в множестве нет, то переход к шагу 3, иначе –; .

Шаг 3. Останов, – искомое множество отфильтрованных точек.

Замечание 1. Иногда требуется получить отфильтрованное множество векторов, содержащее _P точек. В этом случае задают начальное _d и реализуют шаги алгоритма 2.

Если , то начальное d увеличивают и снова осуществляют шаги алгоритма 2.

Если , то начальное d уменьшают и осуществляют алгоритм 2.

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

Замечание 2. Множество точек, задержанных фильтром методом первой точки вне окрестности, зависит как от начальной точки, так и от порядка обработки точек.

Замечание 3. Можно рассмотреть и вариант процесса прямой фильтрации с несколькими начальными точками. Эти точки помещаются в верхней части списка и обязательно задерживаются фильтром. Все остальные точки фильтруются обычным способом.

Метод ближайшей точки вне окрестности

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

Алгоритм 3. Алгоритм фильтрации множества методом ближайшей точки вне окрестности

Шаг 0. Начальные данные: – исходное множество точек; _d – радиус окрестности; – множество векторов, задержанных фильтром; – множество векторов, существенно отличающихся от задержанных фильтром.

Шаг 1. – первая точка, задержанная фильтром;

Шаг 2. Если , то переход к шагу 4, иначе заполняем множество S такими точками из , которые существенно отличаются от точек множества , перебирая

Если множество , то переход к шагу 4.

Шаг 3. Выбор ближайшей точки вне окрестности, т.е. находим точку :

, переход к Шагу 2.

Шаг 4. Останов, – искомое множество отфильтрованных точек.

Замечание 4. Метод ближайшей точки вне окрестности не зависит от порядка обработки векторов, хотя зависимость от начальной точки остается.

Метод наиболее удаленной точки вне окрестности

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

Алгоритм метода наиболее удаленной точки вне окрестности аналогичен алгоритму 3 за исключением шага 3:

Шаг 3*. Выбор наиболее удаленной точки вне окрестности, т. е. находим точку :

, переход к Шагу 2.

Обратная фильтрация

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

Пусть – множество векторов, которое нужно обработать с помощью процедуры обратной фильтрации. Пусть – обратная начальная точка (расположенная в начале списка из точек перед «подачей» в фильтр). При обратной фильтрации устанавливается порядок точек (от ближайшей до самой удаленной) в соответствии с их расположением от обратной начальной точки . Если – объем обратного множества, то в процессе обратной фильтрации получаем точку и ее ближайших соседей, которые образуют обратный список. Приведем шаги алгоритмов реализации процедуры обратной фильтрации для случаев, когда: 1) задан радиус окрестности точки; 2) задано число точек конечного списка.

Алгоритм 4. Алгоритм метода обратной фильтрации с заданным радиусом окрестности

Шаг 0. Начальные данные: – исходное множество точек; _d – радиус окрестности; – обратная начальная точка; – множество векторов, задержанных фильтром.

Шаг 1. Множество – искомое множество точек. Останов

Алгоритм 5. Алгоритм метода обратной фильтрации с заданным числом точек

Шаг 0. Начальные данные: – исходное множество точек; _d – радиус окрестности; – обратная начальная точка; –множество векторов, задержанных фильтром; – заданное число точек, задержанных фильтром.

Шаг 1. Для всех вычисление расстояний

Шаг 2. Упорядочение точек по возрастанию расстояний , т.е. формирование списка , где

Шаг 3. Множество задержанных фильтром векторов:

Останов.

Рассмотрим примеры, демонстрирующие работу алгоритмов.

Пример 1. Предположим, что семь точек, изображенных на рисунке 20, образуют список в порядке возрастания их номеров.

После прямой фильтрации списка с использованием первой точки вне окрестности, параметра метрики и радиуса окрестности фильтром задерживаются 4 точки: и . Точка задерживается как начальная, а точка – это первая точка вне - окрестности точек и . Точка задерживается как первая из точек, встреченных вне - окрестности точек .

Пример 2. Предположим, что семь точек, изображенных на рисунке 21, образуют список в порядке возрастания их номеров.

После прямой фильтрации списка с использованием ближайшей точки вне окрестности, параметра метрики и радиуса окрестности фильтром задерживаются 3 точки: и . Точка задерживается как начальная, а точка – это ближайшая точка вне - окрестности точки . Точка задерживается как ближайшая точка вне - окрестности точек и . Так как вне трех - окрестностей больше нет точек, то процесс закончен. Заметим, что если бы мы использовали метод первой точки вне окрестности, то задержались бы точки и .