我有一组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/

10-16 04:18