Поиск вектора, который примерно одинаково удален от всех векторов в наборе

Question

У меня есть набор из 3 миллионов векторов (по 300 измерений каждый), и я ищу новый пункт в этом 300 тусклом пространстве, который приблизительно равен на одинаковом расстоянии от всех других точек (векторов)

Что я мог сделать, это инициализировать случайный вектор V, и запустить оптимизацию над V с целью:

Где d_xy расстояние между вектором х и вектор y, но это было бы очень дорогостоящим.

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

Answer 1

Я согласен с тем, что в целом это довольно сложная проблема оптимизации, особенно в том масштабе, который вы описываете. Для каждой оценки объектной функции O (nm + n^2) работает для n точек измерения m - O (nm) для вычисления расстояний от каждой точки до новой точки и O (n^2) для вычисления цели, заданной расстояниями , Это довольно страшно, когда m = 300 и n = 3M. Таким образом, даже оценка одной функции, вероятно, неразрешима, не говоря уже о решении полной проблемы оптимизации.

Один из подходов, упомянутый в другом ответе, заключается в том, чтобы взять центроид точек, который можно вычислить эффективно - O (нм). Недостатком такого подхода является то, что он может сделать ужасно по предлагаемой цели. Например, рассмотрим ситуацию в 1-мерном пространстве с 3 миллионами точек со значением 1 и 1 точкой со значением 0. При проверке оптимальное решение v = 0,5 с объективным значением 0 (оно равноудалено от каждой точки), но центроид выберет v = 1 (ну, чуть меньше, чем это) с целевым значением 3 миллиона.

Подход, который, как я думаю, будет лучше, чем центроид, - это оптимизировать каждый размер отдельно (игнорируя существование других измерений).Хотя объектная функция по-прежнему дорого вычисляется в этом случае, бит алгебры показывает, что производную от цели довольно легко вычислить. Это сумма по всем парам (i, j), где i < v и j> v значения 4 * ((v-i) + (v-j)). Помните, что мы оптимизируем одно измерение, так что точки i и j одномерны, как и v. Поэтому для каждого измерения мы можем сортировать данные (O (n lg n)), а затем вычислить производную для значения v в O (n), используя бинарный поиск и базовую алгебру. Затем мы можем использовать scipy.optimize.newton, чтобы найти нуль производной, которая будет оптимальным значением для этой размерности. Итерируя по всем измерениям, мы будем иметь приблизительное решение нашей проблемы.

Сначала рассмотрит предложенный подход в сравнении с центроидом метода в простой установке, с 1-мерными точками данных {0, 3, 3}:

import bisect 
import scipy.optimize 

def fulldist(x, data): 
    dists = [sum([(x[i]-d[i])*(x[i]-d[i]) for i in range(len(x))])**0.5 for d in data] 
    obj = 0.0 
    for i in range(len(data)-1): 
     for j in range(i+1, len(data)): 
      obj += (dists[i]-dists[j]) * (dists[i]-dists[j]) 
    return obj 

def f1p(x, d): 
    lownum = bisect.bisect_left(d, x) 
    highnum = len(d) - lownum 
    lowsum = highnum * (x*lownum - sum([d[i] for i in range(lownum)])) 
    highsum = lownum * (x*highnum - sum([d[i] for i in range(lownum, len(d))])) 
    return 4.0 * (lowsum + highsum) 

data = [(0.0,), (3.0,), (3.0,)] 
opt = [] 
centroid = [] 
for d in range(len(data[0])): 
    thisdim = [x[d] for x in data] 
    meanval = sum(thisdim)/len(thisdim) 
    centroid.append(meanval) 
    thisdim.sort() 
    opt.append(scipy.optimize.newton(f1p, meanval, args=(thisdim,))) 
print "Proposed", opt, "objective", fulldist(opt, data) 
# Proposed [1.5] objective 0.0 
print "Centroid", centroid, "objective", fulldist(centroid, data) 
# Centroid [2.0] objective 2.0 

Предложенный подход находит точное оптимальное решение, в то время как Метод центроида промахивается немного.

Рассмотрим несколько больший пример с 1000 точками размера 300, с каждой точкой, взятой из гауссовой смеси. Значение каждой точки является нормальным распределением со средним 0 и дисперсией 1 с вероятностью 0,1 и нормально распределены со средним значением 100 и дисперсией 1 с вероятностью 0,9:

data = [] 
for n in range(1000): 
    d = [] 
    for m in range(300): 
     if random.random() <= 0.1: 
      d.append(random.normalvariate(0.0, 1.0)) 
     else: 
      d.append(random.normalvariate(100.0, 1.0)) 
    data.append(d) 

Полученных объективных значениями было 1.1e6 для предложенного подхода и 1.6e9 для центроидный подход, то есть предлагаемый подход уменьшил цель более чем на 99,9%. Очевидно, что различия в объективном значении сильно зависят от распределения точек.

Наконец, чтобы проверить масштабирование (исключая вычисления конечного целевого значения, поскольку они в целом неразрешимы), я получаю следующее масштабирование с m = 300: 0,9 секунды для 1000 пунктов, 7,1 секунды для 10 000 точек и 122,3 секунды для 100 000 очков. Поэтому я ожидаю, что это займет около 1-2 часов для вашего полного набора данных с 3 миллионами точек.

Answer 2

От this question on the Math StackExchange:

Там нет смысла, что находится на одинаковом расстоянии от 4 или более точек в общем положения в плоскости, или n + 2 точки в n измерениях.

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

Центроид - это точка C в плоскости, для которой сумма квадратов квадратов $ \ sum | CP_i |^2 $ минимальна. Можно также оптимизировать другую меру централизованности или настаивать на том, чтобы представитель являлся одной из точек (например, теоретико-графическим центром взвешенного оконечного дерева ) или присваивал веса некоторым точкам и центроид этих.

Обратите внимание, в частности, «центроид является оптимальным выбором в наименьших квадратов толку», поэтому оптимальное решение вашей функции стоимости (которая является стоимость наименьших квадратов) просто усреднить все координаты ваши очки (что даст вам центроид).