2

300 万個のベクトル (それぞれ 300 次元) のセットがあり、この 300 薄暗い空間で、他のすべての点 (ベクトル) からほぼ同じ距離にある新しい点を探しています。

私ができることは、ランダムなベクトル v を初期化し、目的で v に対して最適化を実行することです。 目的関数

d_xy はベクトル x とベクトル y の間の距離ですが、これは計算コストが非常に高くなります。

非常に大規模なベクトルのセットですばやく見つけることができる、この問題の近似解ベクトルを探しています。（または、私のためにこのようなことをするライブラリ-任意の言語）

4

2 に答える 2

1

Math StackExchange に関するこの質問から:

平面内の一般的な位置で 4 点以上、または n 次元で n+2 点から等距離にある点はありません。

ポイントの集合を 1 つのポイントで表す基準は、統計、機械学習、およびコンピューター サイエンスで考慮されます。重心は最小二乗法の意味で最適な選択ですが、他にも多くの可能性があります。

重心は、距離の平方和 $\sum |CP_i|^2$ が最小になる平面上の点 C です。中心性の別の尺度を最適化するか、代表がポイントの 1 つ (重み付きスパニング ツリーのグラフ理論上の中心など) であることを主張するか、何らかの方法でポイントに重みを割り当ててそれらの重心を取得することもできます。 .

特に、「重心は最小二乗の意味で最適な選択である」ことに注意してください。そのため、コスト関数（最小二乗コスト）の最適なソリューションは、ポイントのすべての座標を平均することです（これにより、あなたは重心です）。

于 2015-06-11T10:22:29.250 に答える
1

特にあなたが説明している規模では、これは非常に難しい最適化問題であることに同意します。各目的関数の評価では、次元 m の n 個の点に対して O(nm + n^2) の作業が必要です。つまり、各点から新しい点までの距離を計算するのに O(nm)、距離が与えられた目的を計算するのに O(n^2) が必要です。 . m=300 で n=3M の場合、これはかなり恐ろしいことです。したがって、完全な最適化問題を解くことは言うまでもなく、1 つの関数評価でさえおそらく扱いにくいものです。

他の回答で言及されている1つのアプローチは、ポイントの重心を効率的に計算できるO（nm）を取ることです。このアプローチの欠点は、提案された目的に対して非常にうまくいく可能性があることです。たとえば、値 1 の 300 万点と値 0 の 1 点がある 1 次元空間の状況を考えてみましょう。調べると、最適解は v=0.5 で目的値 0 (すべての点から等距離) ですが、重心はv=1 (まあ、それより少し小さい) を選択し、目的値は 300 万です。

重心よりもうまくいくと私が考えるアプローチは、各次元を個別に最適化することです (他の次元の存在を無視します)。この場合、目的関数の計算には依然としてコストがかかりますが、少し代数を考えると、目的関数の微分は非常に簡単に計算できることがわかります。これは、値 4*((vi)+(vj)) の i < v および j > v であるすべてのペア (i, j) の合計です。点 i と j が v と同様に 1 次元になるように、1 次元を最適化していることを思い出してください。したがって、各次元について、データ (O(n lg n)) を並べ替え、値 v の導関数を計算できます。二分探索と基本代数を使用した O(n) 時間。次に、使用できますscipy.optimize.newtonその次元の最適値となる導関数のゼロを見つけます。すべての次元を反復すると、問題の近似解が得られます。

最初に、1 次元のデータ ポイント {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

提案されたアプローチは正確な最適解を見つけますが、重心法は少しミスします。

次元 300 の 1000 個の点があり、各点がガウス混合から引き出された少し大きな例を考えてみましょう。各ポイントの値は、確率 0.1 で平均 0 と分散 1 の正規分布であり、確率 0.9 で平均 100 と分散 1 の正規分布です。

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 に答える