2

我有一组 300 万个向量（每个向量 300 个维度），我正在这 300 个昏暗空间中寻找一个新点，该点与所有其他点（向量）的距离大致相等

我能做的是初始化一个随机向量 v，然后对 v 进行优化，目标是： 目标函数

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

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

4

2 回答 2

1

从Math StackExchange 上的这个问题：

没有一个点与平面上一般位置上的 4 个或更多点等距，或者在 n 维上与 n+2 个点等距。

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

质心是平面中距离平方和 $\sum |CP_i|^2$ 最小的点 C。也可以优化不同的中心性度量，或者坚持代表是点之一（例如加权生成树的图论中心），或者以某种方式为点分配权重并取那些点的质心.

请注意，具体而言，“质心是最小二乘意义上的最佳选择”，因此您的成本函数（即最小二乘成本）的最佳解决方案只是平均所有点的坐标（这将给出你是质心）。

于 2015-06-11T10:22:29.250 回答
1

我同意，总的来说，这是一个非常棘手的优化问题，尤其是在您所描述的规模上。每个目标函数评估需要 O(nm + n^2) 为 n 个维度 m 的点工作 - O(nm) 来计算从每个点到新点的距离和 O(n^2) 来计算给定距离的目标. 当 m=300 且 n=3M 时，这非常可怕。因此，即使是一项功能评估也可能难以解决，更不用说解决完整的优化问题了。

另一个答案中提到的一种方法是采用点的质心，可以有效地计算 - O(nm)。这种方法的一个缺点是它可能会在提议的目标上做得非常糟糕。例如，考虑一维空间中的情况，有 300 万个值为 1 的点和 1 个值为 0 的点。通过检查，最优解是 v=0.5，目标值为 0（与每个点等距），但质心将选择目标值为 300 万的 v=1（嗯，比那个小一点）。

我认为比质心做得更好的一种方法是分别优化每个维度（忽略其他维度的存在）。虽然在这种情况下目标函数的计算成本仍然很高，但一些代数表明目标函数的导数很容易计算。它是值 4*((vi)+(vj)) 的所有对 (i, j) 的总和，其中 i < v 和 j > v。请记住，我们正在优化单个维度，因此点 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 小时。

于 2015-06-11T17:18:04.783 回答