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