Jarak berpasangan tanpa loop

Diberikan X berbentuk (n, d) dan Y berbentuk (m, d). Kembalikan matriks D berbentuk (n, m) dengan

D_{ij} = \lVert X_i - Y_j \rVert^2

Tulis tanpa loop Python.

X = [[0, 0], [1, 1]], Y = [[1, 0]]  →  [[1], [1]]

Vektorisasi

Loop Python per elemen ratusan kali lebih lambat daripada operasi NumPy, karena NumPy menjalankan loop-nya di C. Pola X[:, None, :] - Y[None, :, :] adalah trik standar untuk “semua pasangan”: setiap dimensi tambahan bernilai 1 di-broadcast terhadap dimensi lawannya.

Alternatif hemat memori

Bentuk antara (n, m, d) bisa sangat besar. Uraikan kuadratnya:

\lVert x - y \rVert^2 = \lVert x \rVert^2 - 2\,x\cdot y + \lVert y \rVert^2

sehingga D = (X**2).sum(1)[:, None] - 2 * X @ Y.T + (Y**2).sum(1)[None, :] hanya butuh memori (n, m). Pola ini adalah inti k-NN dan k-means.

Penjelasan

Yang diminta. Untuk setiap pasangan baris X[i] dan Y[j], hitung jarak kuadrat $\lVert X_i - Y_j \rVert^2$ . Hasilnya matriks (n, m). Tanpa loop Python.

Ide kunci: tambah dimensi supaya broadcasting membuat semua pasangan.

X[:, None, :] mengubah (n, d) menjadi (n, 1, d).
Y[None, :, :] mengubah (m, d) menjadi (1, m, d).
Dikurangkan, dimensi bernilai 1 direntangkan sehingga hasilnya (n, m, d): entri [i, j] adalah vektor X[i] - Y[j].

Langkah di kode:

diff = X[:, None, :] - Y[None, :, :], berbentuk (n, m, d).
(diff ** 2).sum(axis=-1) mengkuadratkan setiap komponen lalu menjumlahkannya di sepanjang d, sehingga axis terakhir hilang: (n, m).

Contoh kecil. X = [[0,0],[1,1]], Y = [[1,0]]: selisihnya [[-1,0]] dan [[0,1]], kuadrat dijumlah menjadi [[1],[1]].

Yang dikembalikan: array (n, m).

Kesalahan umum: memakai np.sqrt (yang diminta jarak kuadrat); menjumlahkan di axis yang salah sehingga bentuknya (n, d) atau (m, d).