寻找一个向量，大致等于一个集合中的所有向量

Question

我有一个300万个向量（每个300个维度），我正在寻找一个新的点在这个300暗淡的空间是近似的从所有其他点（矢量）等距离

什么我能做的就是初始化随机向量v，超过v的客观运行的优化：

哪里d_xy是向量x之间的距离，向量y，但是这在计算上会非常昂贵。

我在寻找一个大约这个问题的解决方案矢量，可以很快找到非常大的矢量集。 （或者说会做这样的事情我 - 任何语言的任何库）

Answer 1

我同意一般来说这是一个非常艰难的优化问题，特别是在您所描述的规模上。每个目标函数评估需要O（nm + n^2）对于n个维度的m-O（nm）工作来计算从每个点到新点的距离和O（n^2）以计算给定距离的目标。这在m = 300和n = 3M时非常可怕。因此，即使是一个功能评估可能是棘手的，更不用说解决完全优化问题。

在另一个答案中提到的一种方法是取点的质心，可以有效计算 - O（nm）。这种方法的缺点是它可能会对拟议的目标造成严重影响。例如，考虑1维空间中的情况，其中具有值1的300万个点和具有值0的1个点。通过检查，最优解为v = 0.5，目标值为0（与每个点等距），但质心将选择v = 1（好吧，比它小一点），目标值为300万。

我认为比质心更好的方法是分别优化每个维度（忽略其他维度的存在）。虽然目标函数在这种情况下计算仍然很昂贵，但有一点代数表明目标的导数很容易计算。它是所有对（i，j）之和，其中i是值4 *（（v-i）+（v-j））的v和j> v。请记住，我们正在优化一个维度，因此点i和j是一维的，因为v对于每个维度，我们因此可以对数据进行排序（O（n lg n）），然后计算值v in的导数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 

所提出的方法找到精确的最优解，而质心方法有点遗漏。

考虑一个稍微大一点的例子，其中300点的点数为1000，每点从高斯混合物中抽取。每个点的值是正态分布的均值为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：1,000点为0.9秒，10,000点为7.1秒，以及100,000点，122.3秒。因此，我预计这将需要大约1-2个小时为您的完整数据集与300万点。

Answer 2

从this question on the Math StackExchange：

是毫无意义的是等距离的，一般 4个或更多点在飞机上，或n + 2个点。

在统计学，机器学习和计算机科学中考虑的用于表示一点积分的标准是 。质心是最小二乘意义上的最佳选择，但 是许多其他可能性。

质心是平面中的点C，其中平方距离的总和为$ \ sum | CP_i |^2 $为最小。也可以优化一个不同的中心度量，或者坚持代表 是其中一个点（例如加权树的图形理论中心），或者以某种方式为这些点指定权重，并且 那些质心。

注意，具体地说，“质心是最小二乘意义上的最佳选择”，所以对于您的成本函数（这是最小二乘成本）的最优解仅仅是平均所有坐标你的观点（这会给你质心）。