查找与集合中所有向量的距离大致相等的向量

Question

我有一组 300 万个向量（每个向量 300 个维度），我正在寻找这个 300 dim space 中的 new 点，大约是与所有其他点（向量）的距离相等

我能做的是初始化一个随机向量 v，然后运行使用 objective 对 v 进行优化：

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

我正在寻找此问题的近似解向量，可以在非常大的向量集上快速找到。（或者任何可以为我做类似事情的图书馆——任何语言）

Answer 1

来自this question on the Math StackExchange：

There is no point that is equidistant from 4 or more points in general position in the plane, or n+2 points in n dimensions.

Criteria for representing a collection of points by one point are considered in statistics, machine learning, and computer science. The centroid is the optimal choice in the least-squares sense, but there are many other possibilities.

The centroid is the point C in the the plane for which the sum of squared distances $\sum |CP_i|^2$ is minimum. One could also optimize a different measure of centrality, or insist that the representative be one of the points (such as a graph-theoretic center of a weighted spanning tree), or assign weights to the points in some fashion and take the centroid of those.

请注意，具体来说，"the centroid is the optimal choice in the least-squares sense"，因此成本函数的最佳解决方案（这是最小二乘成本）只是对所有点的坐标进行平均（这将为您提供质心） .

Answer 2

我同意，一般来说，这是一个非常棘手的优化问题，尤其是在您描述的规模下。每个 objective 函数求值需要 O(nm + n^2) 对维度 m 的 n 个点进行操作——O(nm) 计算每个点到新点的距离，O(n^2) 计算objective 给定距离。当 m=300 和 n=3M 时，这非常可怕。因此，即使是一个函数评估也可能是棘手的，更不用说解决完整的优化问题了。

另一个答案中提到的一种方法是取点的质心，这可以有效地计算——O(nm)。这种方法的一个缺点是它可能在提议的 objective 上做得非常糟糕。例如，考虑一维 space 中有 300 万个值为 1 的点和 1 个值为 0 的点的情况。通过检查，最优解是 v=0.5，objective 值为 0（它是等距的从每个点），但质心将 select v=1（好吧，比那个小一点） objective 价值 300 万。

我认为比质心更好的一种方法是分别优化每个维度（忽略其他维度的存在）。虽然在这种情况下 objective 函数的计算成本仍然很高，但一些代数表明 objective 的导数很容易计算。它是所有对 (i, j) 的总和，其中 i < v 和 j > 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)

所提出的方法的 objective 值为 1.1e6，质心方法的值为 1.6e9，这意味着所提出的方法将 objective 降低了 99.9% 以上。显然 objective 值的差异受点数分布的影响很大。

最后，为了测试缩放比例（删除最终的 objective 值计算，因为它们通常很棘手），我得到以下 m=300 的缩放比例：1,000 点 0.9 秒，7.1 秒10,000 点，122.3 秒为 100,000 点。因此，我预计对于包含 300 万个点的完整数据集，这大约需要 1-2 小时。

查找与集合中所有向量的距离大致相等的向量

Finding a vector that is approximately equally distant from all vectors in a set

python

vector

linear-algebra

mathematical-optimization

approximate