Jarak bergantung pada geometri yang dipilih

Ketika router tiket dukungan, sistem rekomendasi, atau sistem pengambilan informasi mencari contoh tersimpan yang “paling dekat”, sistem itu sedang membuat pilihan geometris. Sebuah titik yang paling dekat ketika setiap koordinat berkontribusi secara terpisah dapat kalah dari titik lain ketika koordinat digabungkan berdasarkan panjang kuadrat. Algoritmanya tidak menjadi inkonsisten; makna “dekat” yang berubah.

Di akhir pelajaran ini, Anda akan dapat menurunkan jarak dari norma, menghitung peringkat tetangga terdekat berukuran kecil di bawah beberapa metrik, serta mengenali keputusan prapemrosesan dan penanganan seri yang membuat peringkat itu bermakna.

Hasil belajar: Menurunkan jarak dari norma dan membandingkan tetangga terdekat.

Pelajaran ini dibangun di atas Pelajaran 040: L1, L2, dan L-infinity Memaknai Besar Secara Berbeda, yang memperkenalkan beberapa cara untuk mengukur ukuran satu vektor. Bagian 3.3 dari buku resmi Mathematics for Machine Learning menyediakan rujukan matematis. Kumpulan data, perhitungan, kode, visual, dan asesmen di sini adalah karya asli.

Titik terdekat dimulai dari perpindahan

Misalkan $x=(x_1,\ldots,x_n)$ dan $y=(y_1,\ldots,y_n)$ adalah dua titik dalam $\mathbb{R}^n$ . Setiap koordinat adalah posisi fitur; $n$ adalah jumlah fitur. Untuk menanyakan seberapa jauh $x$ dari $y$ , kurangkan terlebih dahulu koordinat demi koordinat:

x-y=(x_1-y_1,\ldots,x_n-y_n).

Selisih ini adalah sebuah vektor perpindahan. Vektor tersebut menyatakan seberapa jauh satu titik harus bergerak pada setiap koordinat untuk sampai ke titik lainnya. Urutan pengurangan mengubah tanda perpindahan, tetapi norma menghasilkan ukuran yang sama di kedua arah karena $\lVert v\rVert=\lVert -v\rVert$ .

Nama-nama tersebut menggambarkan aturan pergerakan yang berbeda. L1, yang sering disebut jarak Manhattan, menjumlahkan perpindahan pada setiap koordinat. L2 mengukur panjang garis lurus dari perpindahan. L-infinity hanya menanyakan perpindahan terbesar pada satu koordinat. Model yang menggunakan salah satu ukuran ini sedang menyatakan jenis perpindahan mana yang dianggap mahal.

Rujukan Bagian 3.3 juga menghubungkan hasil kali dalam dengan norma melalui $\lVert v\rVert=\sqrt{\langle v,v\rangle}$ . Dengan dot product biasa, ini adalah norma Euclidean, sehingga $d_2(x,y)=\sqrt{\langle x-y,x-y\rangle}$ . Ada satu hal penting: konstruksi jarak berlaku untuk norma apa pun. L1 adalah norma yang valid dan menginduksi metrik yang valid, meskipun dalam pengertian ruang vektor real yang biasa norma itu tidak diinduksi oleh hasil kali dalam.

Mengapa pengurangan harus dilakukan lebih dahulu

Jarak membandingkan dua lokasi melalui satu perpindahan. Jarak bukan selisih ukuran masing-masing lokasi. Misalnya, jika $x=(1,1)$ dan $y=(1,-1)$ , kedua titik memiliki norma L2 $\sqrt{2}$ , tetapi

x-y=(0,2),\qquad d_2(x,y)=\sqrt{0^2+2^2}=2.

Menghitung $\lVert x\rVert_2-\lVert y\rVert_2=0$ akan menghapus fakta bahwa kedua titik berjarak dua unit secara vertikal. Resep mental yang aman adalah kurangkan dahulu, lalu terapkan norma yang dipilih.

Titik yang sama dapat memiliki tetangga terdekat yang berbeda

Pertimbangkan titik kueri $q=(0,0)$ dan tiga catatan kandidat dalam representasi dua fitur. Koordinatnya sengaja kecil dan tanpa unit: koordinat tersebut mewakili nilai setelah suatu representasi fitur dipilih, bukan pengertian universal tentang kemiripan.

Titik	Deskripsi	Koordinat
$A$	kasus dominan sumbu	$(6,0)$
$B$	kasus seimbang	$(4,4)$
$C$	kasus campuran	$(5,2)$

Hitung setiap jarak sebelum membuat peringkat

Karena $q=(0,0)$ , setiap perpindahan sama dengan kandidatnya. Untuk titik $A$ ,

\begin{aligned} A-q&=(6,0),\\ d_1(q,A)&=|6|+|0|=6,\\ d_2(q,A)&=\sqrt{6^2+0^2}=\sqrt{36}=6,\\ d_\infty(q,A)&=\max(|6|,|0|)=6. \end{aligned}

Untuk titik $B$ ,

\begin{aligned} B-q&=(4,4),\\ d_1(q,B)&=|4|+|4|=8,\\ d_2(q,B)&=\sqrt{4^2+4^2}=\sqrt{32}\approx5.657,\\ d_\infty(q,B)&=\max(4,4)=4. \end{aligned}

Untuk titik $C$ ,

\begin{aligned} C-q&=(5,2),\\ d_1(q,C)&=|5|+|2|=7,\\ d_2(q,C)&=\sqrt{5^2+2^2}=\sqrt{29}\approx5.385,\\ d_\infty(q,C)&=\max(5,2)=5. \end{aligned}

Sekarang urutkan setiap kolom dari jarak terkecil ke terbesar:

\begin{aligned} \text{L1:}&\quad A\;(6),\ C\;(7),\ B\;(8),\\ \text{L2:}&\quad C\;(5.385),\ B\;(5.657),\ A\;(6),\\ \text{L-infinity:}&\quad B\;(4),\ C\;(5),\ A\;(6). \end{aligned}

Peringkatnya berubah karena norma-norma tersebut memberi nilai berbeda pada bentuk perpindahan. L1 memilih titik $A$ yang dominan sumbu di sini karena total perpindahan koordinatnya paling kecil. L2 memilih $C$ : gabungan kedua koordinatnya membentuk ruas garis lurus yang lebih pendek daripada diagonal $B$ dan ruas horizontal panjang $A$ . L-infinity memilih $B$ karena tidak ada satu pun koordinat yang berpindah lebih dari $4$ .

Satu kueri, tiga peta tetangga

Tabel ini adalah cadangan semantik yang lengkap: jarak yang lebih kecil berarti lebih dekat ke kueri q = (0, 0).
Kandidat	Koordinat	L1jumlah perpindahan absolut	L2panjang garis lurus	L-infinityperpindahan koordinat terbesar
A dominan sumbu	(6, 0)	6.000peringkat 1	6.000peringkat 3	6.000peringkat 3
B seimbang	(4, 4)	8.000peringkat 3	5.657peringkat 2	4.000peringkat 1
C campuran	(5, 2)	7.000peringkat 2	5.385peringkat 1	5.000peringkat 2
Dua kandidat terdekat		A → C	C → B	B → C

Angka di dalam lingkaran memberikan peringkat untuk metrik tersebut. Segmen putus-putus menunjuk ke kandidat terdekat; dua peringkat pertama diberi garis tepi agar peta tidak bergantung pada warna saja.

Untuk L1, urutannya A lalu C lalu B. Untuk L2, urutannya C lalu B lalu A. Untuk L-infinity, urutannya B lalu C lalu A. Kueri berada di titik asal pada setiap panel.

Geometri mengubah peta tetangga meskipun koordinat kueri dan kandidat tetap sama.

Tabel dan label peringkat membuat kesimpulannya tersedia tanpa perlu membaca SVG. Visual tersebut menambahkan satu petunjuk spasial: titik akhir segmen putus-putus berubah saat metrik berubah, sedangkan koordinatnya tetap.

Pencarian NumPy yang transparan

Dokumentasi NumPy untuk numpy.linalg.norm memperlihatkan dua kontrol yang diperlukan di sini: ord memilih orde norma dan axis memilih sumbu koordinat yang akan direduksi. Karena itu, batch yang berisi tiga baris kandidat ditangani dengan mengurangkan kueri dari setiap baris dan mereduksi setiap baris secara terpisah.

Kode berikut mencerminkan penurunan matematisnya, bukan menyembunyikannya dalam objek tetangga terdekat. Kode ini dijalankan dengan NumPy; urutan yang dicetak sama dengan contoh yang sudah dihitung.

import numpy as np

query = np.array([0.0, 0.0])
points = np.array([[6.0, 0.0], [4.0, 4.0], [5.0, 2.0]])
labels = np.array(["A", "B", "C"])

difference = points - query
for name, order in [("L1", 1), ("L2", 2), ("L-infinity", np.inf)]:
    distances = np.linalg.norm(difference, ord=order, axis=1)
    ranked = np.argsort(distances, kind="stable")
    print(
        f"{name}: "
        + ", ".join(f"{labels[i]}={distances[i]:.3f}" for i in ranked)
    )

L1: A=6.000, C=7.000, B=8.000
L2: C=5.385, B=5.657, A=6.000
L-infinity: B=4.000, C=5.000, A=6.000

Ada tiga operasi terpisah yang perlu diperhatikan:

points - query melakukan pengurangan sebelum norma apa pun diterapkan.
axis=1 menghitung satu norma per baris, sehingga setiap kandidat mendapat satu jarak.
argsort mengubah jarak menjadi peringkat; norma itu sendiri tidak menentukan cara menangani nilai yang sama.

Untuk kumpulan data yang lebih besar, kelas NearestNeighbors dari scikit-learn mengemas gagasan yang sama. Pengaturan metric="minkowski" menggunakan parameter p, dengan $p=1$ yang berarti L1 dan $p=2$ yang berarti L2; metodenya, kneighbors, mengembalikan jarak sekaligus indeks. Estimator ini berguna ketika pencarian harus diintegrasikan ke dalam alur model, tetapi versi NumPy lebih baik untuk penelusuran masalah karena setiap larik perantara terlihat.

Untuk contoh yang persis sama, konfigurasi pencarian yang setara adalah:

from sklearn.neighbors import NearestNeighbors

search = NearestNeighbors(n_neighbors=2, metric="minkowski", p=2)
search.fit(points)
distances, indices = search.kneighbors(query.reshape(1, -1))
nearest_labels = labels[indices[0]]

Mengubah p menjadi 1 atau np.inf mengubah geometrinya sambil mempertahankan data dan nilai $k=2$ . API tidak menghilangkan pilihan metrik; API membuat pilihan itu eksplisit sebagai parameter.

Batasan yang mengubah jawaban

Jarak hanya presisi setelah ruang fitur, metrik, dan kebijakan pencarian ditentukan. Inilah kasus-kasus yang paling mungkin membuat demo tetangga terdekat berukuran kecil menjadi menyesatkan.

Seri adalah informasi, bukan noise

Misalkan $q=(0,0)$ , $u=(1,1)$ , dan $v=(2,0)$ . Kedua kandidat memiliki

d_1(q,u)=|1|+|1|=2, \qquad d_1(q,v)=|2|+|0|=2.

Jika $k=1$ , matematika memberikan seri, bukan pemenang tunggal. Sistem produksi harus menyatakan kunci sekunder yang deterministik, mengembalikan semua kandidat yang seri, atau menggunakan kebijakan yang sesuai dengan aplikasinya. Pengurutan stable dalam kode NumPy membuat proses berulang dapat direproduksi, tetapi tidak membuktikan bahwa baris seri yang muncul pertama lebih mirip.

Titik identik memiliki jarak nol

Jika $x=y$ , maka $x-y=(0,\ldots,0)$ dan setiap norma memberikan $d(x,y)=0$ . Itu adalah kecocokan persis yang valid, bukan kesalahan. Namun, dalam pencarian pada data pelatihan, melakukan kueri terhadap baris yang sama pada koleksi yang sudah disesuaikan dapat mengembalikan baris itu sendiri sebagai tetangga terdekat. Tentukan apakah pencocokan diri berguna sebelum menafsirkan hasil; kueri eksternal yang kebetulan sama dengan baris tersimpan tetap harus menerima jarak nol.

Penskalaan fitur adalah bagian dari geometri

Misalkan satu koordinat adalah pendapatan tahunan dalam dolar dan koordinat lainnya adalah hitungan dari nol sampai sepuluh. Koordinat dolar dapat mendominasi jarak L1 atau L2 hanya karena satuan angkanya lebih besar. Standardisasi, penskalaan ulang, atau pemberian bobot domain mengubah geometri; semua itu bukan tahap awal yang sekadar kosmetik. Sesuaikan setiap aturan penskalaan yang bergantung pada data menggunakan data pelatihan, lalu terapkan aturan yang sama pada kueri, atau peta tetangga dapat membocorkan informasi dari himpunan evaluasi.

Jarak dan kemiripan kosinus menjawab pertanyaan yang berbeda

Jarak membandingkan perpindahan antara dua titik sehingga mencakup posisi dan besar keduanya. Kemiripan kosinus membandingkan arah setelah panjang dinormalisasi. Untuk $x=(1,1)$ dan $y=(10,10)$ ,

\cos(x,y)=\frac{x^\mathsf{T}y}{\lVert x\rVert_2\lVert y\rVert_2}=1,

karena vektornya menunjuk tepat ke arah yang sama, sedangkan

d_2(x,y)=\lVert x-y\rVert_2 =\sqrt{(-9)^2+(-9)^2}=9\sqrt{2}\approx12.728.

Sistem pengambilan berbasis embedding mungkin memilih kosinus ketika arah adalah pengertian kecocokan yang diinginkan. Aplikasi yang sensitif terhadap skala mungkin memilih jarak yang diinduksi norma. Tidak ada pilihan yang selalu benar, dan kemiripan kosinus memerlukan kebijakan terpisah untuk vektor nol karena arahnya tidak terdefinisi.

Dimensi tinggi membutuhkan pengukuran, bukan slogan

Pada beberapa distribusi data berdimensi tinggi, jarak terdekat dan terjauh dapat menjadi semakin berdekatan sehingga peringkatnya kurang diskriminatif. Beyer, Goldstein, Ramakrishnan, dan Shaft menjelaskan hasil konsentrasi jarak ini dalam kondisi tertentu di makalah mereka tentang tetangga terdekat. Hasil itu adalah peringatan tentang asumsi data dan beban kerja, bukan hukum bahwa setiap ruang embedding menjadi tidak berguna. Periksa selisih jarak tetangga, validasi metrik pada kueri yang disisihkan, dan pertimbangkan apakah representasi mengandung banyak koordinat yang tidak relevan sebelum menyalahkan algoritma pencarian.

Pelajaran berikutnya memisahkan perbandingan arah yang sengaja dicampur oleh jarak dengan panjang: Pelajaran 044, Angles and Cosine Similarity. Halaman kursus Math for AI berbahasa Inggris akan menampilkan pelajaran itu ketika paket terjemahannya sudah aktif.