我有一组300万个向量（每个向量有300个维度），并且我正在这个300个暗淡的空间中寻找一个与所有其他点（向量）大致相等的新点
我能做的是初始化一个随机向量v，并以目标为目标对v进行优化：
其中d_xy是向量x与向量y之间的距离，但这在计算上将非常昂贵。
我正在寻找这个问题的近似解向量，可以在非常大的向量集上快速找到。 （或者任何可以为我做类似事情的库-任何语言）
最佳答案
我同意，通常来说，这是一个非常棘手的优化问题，尤其是在您描述的规模上。每个目标函数评估都需要对m个维度为n-O（nm）的n个点进行O（nm + n ^ 2）运算以计算从每个点到新点的距离，并在给定距离的情况下使用O（n ^ 2）来计算目标。当m = 300和n = 3M时，这非常可怕。因此，即使是一项功能评估也可能很棘手，更不用说解决整个优化问题了。
在另一个答案中提到的一种方法是取点的质心，可以有效地计算出点的O（nm）。这种方法的缺点是，它可能对提议的目标非常不利。例如，考虑一维空间中具有值为1的300万个点和值为0的1个点的情况。通过检查，最优解为v = 0.5，目标值为0（与每个点等距），但是质心将选择目标值为300万的v = 1（比这小一点）。
我认为比质心更好的方法是分别优化每个维度（忽略其他维度的存在）。尽管在这种情况下，目标函数的计算仍然很昂贵，但是一些代数表明目标的导数非常容易计算。它是所有对（i，j）的总和，其中i v的值为4 *（（v-i）+（v-j））。记住，我们正在优化单个维度，因此点i和j都是一维的，就像v一样。因此，对于每个维度，我们可以对数据进行排序（O（n lg n）），然后计算值v的导数使用二进制搜索和基本代数的O（n）时间。然后，我们可以使用scipy.optimize.newton查找导数的零，这将是该维度的最佳值。遍历所有维度，我们将对问题有一个大概的解决方案。
首先考虑在简单设置中与一维数据点{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：1,000秒为0.9秒，10,000点为7.1秒，100,000为122.3秒点。因此，我希望您的300万点完整数据集大约需要1-2个小时。
关于python - 查找与集合中所有向量近似相等距离的向量，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/30777540/