Еще Раз О Поисках Наибольшей Конденсации В Облаке Точек

В очередной раз я столкнулся с задачей — найти в облаке точек место их наибольшей концентрации.

В этот раз ситуация была такая:

существует определенное количество (можно предположить, что не более 16 миллионов) измерений набора параметров.
Количество параметров в наборе от 2 до 5.
измерение параметров может быть относительно успешным — тогда их результат будет близок к истинному (неизвестны параметры и тип распределения) или неудачным — тогда результат будет случайным (опять же с неизвестными параметрами распределения).
Невозможно определить по одному измерению, удалось ли оно.
Можно предположить, что точка конденсации существует. Если их несколько одинакового качества (что формально никогда не определяется), можно выпустить любой.
ответ необходимо дать за один проход по исходным данным: пересчитывать их или сохранять целиком — дорого.
И, как обычно, хочется, чтобы алгоритм выглядел проще и работал быстрее.

Для простоты можно считать, что значения измеряемых параметров являются действительными числами от 0 до 1. Мы хотим получить результат с разрешением 3 десятичных знака для случая 5 параметров и 4 и более для 4 и менее параметров.

Понятно, что большое количество исходных точек делает сомнительными методы, основанные на обработке парных точек.

Даже эффективное определение расстояния до ближайшей точки потребует значительных усилий по реализации.

Построение гистограмм тоже непросто: заранее неизвестен даже желаемый размер ячейки.

Возможно, например, что все измерения дадут результат в шаре диаметром 0,1, а успешные будут локализованы в области размером 0,003. И нужно будет указать положение этой области (в N-мерном пространстве!) Можно было бы строить гистограммы распределения отдельных параметров, надеясь, что сгущение N-мерных точек можно восстановить из позиций сгущения проекций точек на отдельные координаты, но лучше оставить этот вариант как резервное копирование: опасно терять информацию о взаимосвязях между параметрами, а во время прогнозирования могут возникнуть проблемы с паразитными областями конденсата.

Вариант, который показался мне наиболее перспективным, — использовать к-д дерево .

Если построить бинарное дерево, каждый узел которого соответствует разделению области пространства на две части по одной из координат (координаты сортируются по циклу – x₁ ,Икс₂ ,…,Икс_к ,Икс₁ ,Икс₂ ,.

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

Пусть будет N точек.

Выберем значение K меньше N, например, K=[sqrt(N)] или K=[N^2/3 ].

Найдем область наименьшего объема (т. е.

лежащего на наибольшей глубине дерева), содержащего не менее K точек.

Если таких областей несколько, выберите ту, которая набрала больше всего баллов.

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

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

К сожалению, построение дерева kd стоит дорого и занимает много памяти.

Я готов выделить по 8 байт на точку, но тратить больше было бы нежелательно.

Чтобы сэкономить время и память, я решил построить дерево kd неявно.

Пусть у нас есть точка (x₁ ,Икс₂ ,…,Икс_к ).

Запишем его координаты в двоичной системе.

Икс₁ =0.x₁₁ Икс₁₂ Икс₁₃ … Икс₂ =0.x₂₁ Икс₂₂ Икс₂₃ … Икс₃ =0.x₃₁ Икс₃₂ Икс₃₃ … … И допустим 64-битное целое число Р= х₁₁ Икс₂₁ .

Икс_к1 Икс₁₂ .

Икс_к2 … Это число представляет собой путь по дереву на глубину 64 уровня.

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

Если мы отсортируем P-коды для всех точек в порядке возрастания, мы получим точки в порядке обхода дерева.

Для любых двух точек P_а и П_б найти самый глубокий узел, общими потомками которого они являются: просто найдите самый старший ненулевой бит в числе P_а ^П_б .

И все необходимые фрагменты задачи на таком представлении решаются в нескольких строках: Нахождение уровня, на котором находится наименьшая точка, содержащая не менее K точек:

   

     ulong mask=ulong.MaxValue;
     K--;
     for(int i=K;i<m_np;i++) mask=Math.Min(mask,m_Arr[i]^m_Arr[i-K]);

Здесь m_Arr — массив кодов, m_np — количество заполненных элементов в нем, маска — число, старший разряд которого определяет нужный уровень.

Ищем на найденном уровне область, содержащую максимальное количество точек (мы знаем, что их не менее K):

mask=InvMask(mask); int ms=0,me=0; for(int i=0;i<m_np-K;i++){ ulong a=m_Arr[i]; int h=i+K; if(((a^m_Arr[h])&mask)==0){ while(h<m_np-1 && ((a^m_Arr[h+1])&mask)==0) h++; K=h-i; ms=i; me=i=h; } }

Здесь InvMask(mask) — это вычисление маски, содержащей 1 во всех битах выше старшего ненулевого бита маски маски.

Вычисляем мс – начало искомой области и мс – ее конец.

Находим более тяжелого потомка:

int h=(ms+me)/2; ulong samp=m_Arr[h]; ulong cb=samp^m_Arr[ms],ce=samp^m_Arr[me]; if(cb>ce) { ms=h; ce=InvMask(ce); while(ms>0 && ((m_Arr[ms-1]^samp)&ce)==0) ms--; } else { me=h; cb=InvMask(cb); while(me<m_np-1 && ((m_Arr[me+1]^samp)&cb)==0) me++; }

Здесь спуск не обязательно идет на один уровень.

Таким образом, решается проблема поиска конденсата.

Вся программа была выполнена в 100 строках, исходный код (на C#) можно найти.

Здесь .

Реальная проблема имеет несколько более сложную формулировку.

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

Но небольшие модификации алгоритма могут решить эти проблемы.

Например, если место в массиве закончилось, а точки продолжают поступать, мы можем отсортировать и проредить массив уже набранных кодов — на положение и качество сгущения это не повлияет. В заключение несколько примеров работы (два параметра, 10^5 и 10^7 баллов - для одного реального и нескольких синтетических примеров).

Понятно, что алгоритм еще нуждается в доработке (уточнении найденного положения), и что для реального случая это слишком расчетливо; более простых решений было бы достаточно.

Но я хочу немного перестраховаться.

Еще раз о поисках наибольшей конденсации в облаке точек

Теги: #kd дерево #путанный поиск #Алгоритм