Manhattan Distance: Konsep, Rumus, dan Contoh

Manhattan Distance adalah salah satu metrik jarak yang sering digunakan di bidang ilmu komputer dan machine learning untuk mengukur perbedaan antara dua titik atau vektor di ruang berdimensi. Berbeda dengan Euclidean Distance yang menghitung jarak garis lurus, Manhattan Distance menghitung jumlah selisih absolut pada setiap dimensi, eolah-olah kamu berjalan di jaringan jalan berbentuk grid dan tidak bisa memotong sudut. Karakteristik ini membuat Manhattan Distance cocok untuk data yang direpresentasikan dalam grid, fitur kategori yang dicoded numerik, dan skenario di mana pergerakan diagonal tidak realistis.

Bagi programmer, mahasiswa IT, dan pelajar yang sering berkutat dengan algoritma, pemahaman mendalam tentang Manhattan Distance penting karena metrik ini memengaruhi hasil algoritma seperti K-Nearest Neighbors (KNN), clustering, dan pathfinding. pada artikel ini kita membahas definisi, asal-usul istilah, rumus dan contoh perhitungan 2D hingga multidimensi, perbandingan dengan Euclidean Distance, kelebihan serta kekurangannya.

Apa Itu Manhattan Distance?

Manhattan Distance, dikenal juga sebagai Taxicab Distance atau L1 norm, mengukur jarak antara dua titik $P$ dan $Q$ dengan menjumlahkan nilai absolut selisih pada setiap dimensi. Secara aljabar untuk vektor $P=(p_1, p_2, …, p_n)$ dan $Q=(q_1, q_2, …, q_n)$, Manhattan Distance ditulis sebagai:

$$D_{Manhattan}(P,Q)=\sum_{i=1}^{n} |p_i – q_i|$$

Konsep ini mudah divisualisasikan: bayangkan kota dengan jalan grid (seperti Manhattan) — taksi harus mengikuti jalan, sehingga jarak dihitung berdasarkan jumlah blok horizontal ditambah blok vertikal, bukan jarak lurus diagonal.

Manhattan Distance banyak digunakan saat fitur bersifat sparsity (banyak nol) atau data memiliki skala berbeda di tiap dimensi karena perhitungannya yang linear. Untuk fitur kategorikal yang sudah di-encode (misalnya one-hot), Manhattan Distance sering lebih stabil daripada Euclidean karena pengaruh perubahan satu fitur ke total jarak tidak dikuadratkan. Di praktik machine learning untuk KNN dan clustering, pemilihan L1 vs L2 (Euclidean) bisa memengaruhi performa—L1 cenderung lebih tahan terhadap outlier ekstrem pada satu dimensi karena kontribusi linearnya.

Asal Usul Istilah Manhattan Distance

Nama “Manhattan Distance” muncul dari analogi tata kota Manhattan, New York, yang tata jalannya berupa grid ortogonal jalan sejajar utara selatan dan timur barat sehingga pergerakan sering mengikuti blok-blok kotak. Konsep ini juga disebut Taxicab Geometry karena perilaku taksi yang tidak bisa melintasi blok diagonal, melainkan harus mengikuti ruas jalan. Dalam literatur matematika, metrik ini merupakan bentuk norm L1 pada ruang vektor, norm yang mengukur “panjang” vektor dengan jumlah nilai absolut komponennya.

Dalam sejarah matematika dan teori metrik, taxicab geometry digunakan untuk mempelajari geometri non-Euclidean sederhana, yang kemudian diadopsi ke bidang komputasi karena kemudahan komputasinya dan sifat yang relevan terhadap banyak aplikasi praktis. Selain itu, istilah “L1 distance” sering dipakai di konteks statistik dan optimisasi, terutama ketika ingin meminimalkan error absolut (median) dibandingkan error kuadrat (mean squared error). Pemilihan istilah berbeda kerap muncul berdasarkan disiplin: data scientist cenderung menyebut L1, sedangkan praktisi grafika permainan atau pathfinding lebih nyaman dengan nama Manhattan atau taxicab.

Cara Kerja Manhattan Distance

Cara kerja Manhattan Distance sangat sederhana dan terdiri dari beberapa langkah terstruktur:

1. Ambil Dua Titik/Vektor
   Pilih dua vektor $P$ dan $Q$ dengan jumlah dimensi sama.
2. Hitung Selisih Per-Dimensi
   Untuk setiap dimensi $i$, hitung $d_i = |p_i – q_i|$ (nilai absolut selisih).
3. Jumlahkan Semua Selisih
   Jumlahkan semua $d_i$di​ untuk mendapatkan jarak keseluruhan: $D = \sum_i d_i$
4. Interpretasi Hasil
   Hasil D merepresentasikan jarak “grid” antara dua titik; semakin besar D, semakin jauh posisi relatifnya.

Contoh kerja praktis: untuk dua titik 2D $P=(x_1,y_1)$ dan $Q=(x_2,y_2)$, langkahnya hanya dua operasi absolut dan satu penjumlahan: $|x_1-x_2| + |y_1-y_2|$. Karena operasi yang terlibat hanya tambah dan absolut, perhitungan Manhattan sangat murah secara komputasi dan mudah di-parallel-kan jika bekerja pada dataset besar. Kejernihan langkah ini membuatnya cocok untuk implementasi sederhana di kode dan untuk debugging ketika membandingkan hasil metrik jarak.

Rumus Manhattan Distance

Rumus formal Manhattan Distance untuk dua vektor $P$P dan $Q$Q berdimensi $n$n adalah:$$D_{Manhattan}(P,Q) = \sum_{i=1}^{n} |p_i – q_i|$$

Untuk dua dimensi, rumus disederhanakan menjadi:

$$D((x_1,y_1),(x_2,y_2)) = |x_1-x_2| + |y_1-y_2|$$

Rumus ini menegaskan bahwa tiap dimensi berkontribusi secara linear terhadap jarak total tanpa pengaruh kuadrat atau akar. Karena sifat linear ini, kontribusi outlier di satu dimensi sebanding langsung dengan besar outlier tersebut dan tidak mengecil atau membesar akibat operasi berpangkat.

Contoh hitung: $P=(2,5)$, $Q=(7,1)$. Maka $D = |2-7| + |5-1| = 5 + 4 = 9$. Untuk dimensi lebih tinggi, rumus sama diterapkan komponen demi komponen. Sifatnya yang mudah dianalisis juga memudahkan optimisasi: misalnya meminimalkan jumlah Manhattan Distances ke sejumlah titik dikenal sebagai masalah median geometris (1-median), yang berbeda jauh dari masalah rata-rata kuadrat (least squares) yang memunculkan mean sebagai solusi.

Perbedaan Manhattan Distance dan Euclidean Distance

Aspek	Manhattan Distance (L1)	Euclidean Distance (L2)
Sensitivitas outlier	Lebih robust terhadap outlier tunggal (kontribusi linear)	Lebih sensitif (kontribusi kuadrat)
Komputasi	Lebih murah (hanya absolut dan penjumlahan)	Lebih mahal (kuadrat dan akar)
Bentuk kontur jarak	Kotak / diamond (L1 ball)	Lingkaran (L2 ball)
Kesesuaian untuk data satuan/one-hot	Cocok	Kurang ideal
Interpretasi fisik	Pergerakan di grid	Jarak lurus/Euclidean

Perbedaan utama terletak pada bagaimana setiap dimensi mempengaruhi total jarak: L1 menjumlahkan kontribusi linear, L2 memberikan bobot lebih besar untuk perbedaan besar karena kuadrat. Di banyak aplikasi, L1 lebih stabil ketika beberapa fitur berfluktuasi besar atau saat fitur bersifat diskret. Namun, L2 lebih representatif bila konsep “jarak garis lurus” memang relevan (mis. lokasi fisik tanpa pembatas).

Contoh Perhitungan Manhattan Distance pada Data 2D

Bayangkan kamu memiliki dua titik pada peta grid: $A=(3,8)$ dan $B=(10,4)$. Untuk mencari Manhattan Distance, lakukan langkah berikut:

1. Hitung selisih pada sumbu x: $|3-10| = 7$
2. Hitung selisih pada sumbu y: $|8-4| = 4$
3. Jumlahkan: $7 + 4 = 11$. Jadi jarak Manhattan antara A dan B adalah 11 blok.

Contoh lain yang relevan pada pemrograman: saat mengerjakan pathfinding di permainan grid, koordinat pemain dan tujuan sering dihitung dengan Manhattan untuk estimasi heuristik (mis. A* sederhana). Karena heuristik Manhattan admissible ketika hanya bergerak empat arah, estimator tersebut tidak melebih-lebihkan jarak sebenarnya dan membantu algoritme menjelajah lebih efisien.

Selain contoh manual, untuk dataset 2D besar perhitungan ini cocok dioptimalkan memakai operasi vectorized (mis. NumPy) agar perhitungan antar banyak pasang titik dapat dilakukan secara cepat tanpa loop eksplisit.

Contoh Perhitungan Manhattan Distance pada Data Multidimensi

Dalam ruang berdimensi banyak, prinsipnya sama: hitung selisih absolut tiap komponen lalu jumlahkan. Misal vektor $P=(2,0,5,9)$ dan $Q=(7,0,3,12)$. Komponen per-dimensi: $|2-7|=5$, $|0-0|=0$, $|5-3|=2$, $|9-12|=3$. Total Manhattan Distance = $5+0+2+3 = 10$.

Pada data fitur machine learning yang memiliki 100 atau 1000 dimensi (mis. teks setelah TF-IDF, embeddings satu-hot), perhitungan Manhattan tetap odometer linear: setiap dimensi berkontribusi proporsional. Namun perlu diperhatikan skala fitur—jika satu fitur memiliki rentang besar, tanpa normalisasi akan mendominasi jarak. Oleh karena itu sering dilakukan standardisasi atau scaling (mis. Min-Max) sebelum menghitung L1.

Kelebihan lain di multidimensi adalah efisiensi memori-komputasi: operasi L1 dapat dioptimalkan dengan bitwise/CPU SIMD di library numerik, serta cocok untuk sparse matrix representations karena hanya non-zero entries perlu diproses untuk menghitung selisih absolut.

Kelebihan Manhattan Distance

Berikut kelebihan utama Manhattan Distance dengan penjelasan tiap poin:

• Komputasi Murah: Operasinya hanya melibatkan pengurangan, nilai absolut, dan penjumlahan — jauh lebih ringan daripada kuadrat dan akar. Ini penting pada dataset besar atau embedded devices.
• Robust terhadap Outlier Tunggal: Karena kontribusi linear, satu dimensi yang ekstrem tidak meledak menjadi dominan seperti pada L2. Ini membantu stabilitas pada dataset dengan noise.
• Cocok untuk Data Diskret / Grid: Saat data merepresentasikan letak di grid atau fitur biner/one-hot, L1 sering merepresentasikan “perbedaan nyata” lebih baik.
• Sparse-friendly: Untuk representasi sparse (mis. TF-IDF), hanya indeks non-zero perlu dihitung sehingga efisiensi tercapai.
• Heuristik Pathfinding: Dalam algoritma seperti A*, Manhattan admissible ketika pergerakan terbatas pada empat arah sehingga membantu estimasi jarak tanpa overshoot.

Kekurangan Manhattan Distance

Berikut kelemahan Manhattan Distance beserta penjelasan tiap poin:

• Tidak Merepresentasikan Jarak Lurus: Dalam konteks fisik tanpa pembatas, Euclidean memberikan jarak sesungguhnya; Manhattan bisa melebihkan jalur nyata.
• Bergantung pada Skala Fitur: Tanpa normalisasi, fitur dengan rentang besar akan mendominasi perhitungan jarak.
• Kurang Informasi Arah: L1 hanya mengagregasi magnitudo perbedaan; informasi arah (mis. sudut) yang dapat dijelaskan oleh L2 hilang.
• Tidak Selalu Optimal untuk Data Kontinu: Untuk data yang tergolong kontinu dan smooth, L2 sering memberi hasil clustering/estimasi yang lebih representatif.
• Tidak Admissible untuk Pergerakan Diagonal: Pada pathfinding yang mengizinkan diagonal, Manhattan heuristik tidak admissible (akan menghasilkan overestimate).

Kapan Menggunakan Manhattan Distance?

Gunakan Manhattan Distance ketika skenario berikut terpenuhi:

• Data berbentuk grid (game maps, raster data) atau pergerakan dibatasi empat arah.
• Fitur bersifat diskret, biner, atau one-hot sehingga kontribusi linear lebih masuk akal.
• Dataset memiliki banyak dimensi dengan sparsity tinggi; L1 memanfaatkan sparse representation.
• Kamu ingin metrik yang lebih tahan terhadap outlier tunggal di satu dimensi.
• Komputasi adalah faktor kritis (mis. embedded systems, real-time) sehingga operasi ringan diperlukan.

Manhattan Distance dalam Machine Learning

Di machine learning, Manhattan Distance muncul di beberapa tempat penting:

• K-Nearest Neighbors (KNN): Sebagai metric untuk menghitung tetangga terdekat. L1 sering dipilih bila fitur diskret atau ada outlier.
• Clustering (k-medians): Menggunakan median dalam minimisasi L1 (k-medians) berbeda dari k-means (L2). K-medians lebih robust terhadap outlier.
• Regularisasi L1 (Lasso): Meskipun bukan metrik jarak, penalti L1 mendorong sparsity dalam koefisien; konsep L1 dioptimalkan di banyak model.
• Feature Selection dan Similarity Measures: Untuk membandingkan dokumen atau pengguna dengan representasi berdimensi tinggi dan sparse.

Manhattan Distance dalam Data Mining dan Big Data

Di dunia data mining dan big data, karakter L1 sangat berguna untuk skenario berikut:

• Skalabilitas: Perhitungan L1 cocok untuk distributed computing karena sederhana dan dapat diparallel-kan menggunakan map-reduce atau Spark (aggregate absolut differences).
• Sparse Vectors: Representasi sparse di teks mining atau recommendation system membuat perhitungan jarak L1 lebih efisien dibanding memproses banyak nol.
• Anomali Detection: L1 dapat membantu deteksi anomali yang terlihat sebagai deviasi absolut di beberapa fitur.
• Preprocessing untuk Algoritma Lanjutan: Sering dipakai sebagai baseline similarity metric sebelum menerapkan metode yang lebih kompleks.

Manhattan Distance dalam Pemrograman

Dalam praktik pemrograman, Manhattan Distance sering dipakai untuk:

• Heuristik A* pada grid-based pathfinding (di mana pergerakan diagonal tidak diizinkan).
• Collision detection sederhana dan estimasi jarak di permainan berbasis tile.
• Similarity search antar fitur vector sederhana (mis. rekomendasi cepat).
• Evaluasi jarak dalam algoritma clustering ketika menggunakan k-medians.

Kesalahan Umum dalam Menggunakan Manhattan Distance

Beberapa kesalahan yang sering terjadi dan cara menghindarinya:

• Tidak Menyamakan Dimensi: Menghitung jarak antara vektor beda panjang menyebabkan error; selalu validasi dimensi sebelum operasi.
• Melupakan Scaling/Normalisasi: Fitur dengan rentang besar akan mendominasi L1. Terapkan Min-Max atau StandardScaler.
• Menggunakan L1 untuk Data Kontinu Tanpa Alasan: Jika data representasi fisik tanpa pembatas, L2 mungkin lebih tepat.
• Mengabaikan Kosakata Sparse: Saat data sangat sparse, menghitung semua dimensi tanpa memanfaatkan sparsity memakan waktu. Gunakan struktur sparse.
• Memakai Manhattan sebagai Heuristik di Grid dengan Diagonal Allowed: Ini akan menjadi overestimate; gunakan Euclidean atau Chebyshev tergantung aturan gerak.

Kesimpulan

Pada pembahasan kita di atas dapat kita simpulkan bahwa Manhattan Distance adalah metrik jarak sederhana namun kuat yang sangat berguna untuk banyak aplikasi di bidang teknologi seperti pathfinding di game, KNN dan clustering di machine learning, hingga operasi pada data besar yang sparse. Karena kontributor jarak bersifat linear, L1 memberikan robustnes terhadap outlier tunggal dan efisiensi komputasi yang signifikan.

Namun, pemilihan metrik harus didasarkan pada karakter data dan tujuan aplikasi untuk data continuous dan representasi jarak garis lurus, Euclidean sering lebih cocok. Di sisi praktis, penerapan Manhattan Distance mudah diimplementasikan dan dioptimalkan secara vectorized, sehingga menjadi alat wajib bagi programmer dan mahasiswa IT.

Artikel ini merupakan bagian dari seri artikel belajar Kecerdasan Buatan dan jika ada ide topik yang mau kami bahas silahkan komen di bawah ya..