Apa itu Jarak Manhattan?

Metrik jarak adalah alat penting untuk mengukur seberapa jauh objek atau titik di ruang saling berjauhan. Metrik ini berperan besar di banyak bidang, termasuk machine learning, robotika, dan sistem informasi geografis. Dengan mengkuantifikasi jarak, kita dapat melakukan tugas seperti pengenalan pola, pengelompokan data, dan analisis spasial, yang penting baik bagi bisnis maupun peneliti. 

Jarak Manhattan, yang juga dikenal sebagai jarak L1 atau taxicab distance, menonjol sebagai ukuran yang sangat berguna untuk menghitung jarak pada lintasan berbentuk kisi atau antara titik-titik dalam ruang multidimensi. Di sini kita akan melihat dasar matematisnya sekaligus cara mengimplementasikan jarak Manhattan baik di Python maupun R. 

"Manhattan distance." Gambar oleh Dall-E.

Perlu diingat, jarak Manhattan hanyalah satu bagian dari topik luas metrik jarak, yang berulang kali muncul di berbagai bidang. Untuk menjadi ahli dalam pembelajaran berbasis jarak, pertimbangkan kursus Designing Machine Learning Workflows in Python atau kursus Cluster Analysis in R, tergantung bahasa pilihan Anda. 

Mendefinisikan Jarak Manhattan

Jarak Manhattan adalah metrik yang digunakan untuk menentukan jarak antara dua titik pada lintasan berbentuk kisi. Tidak seperti jarak Euclidean, yang mengukur garis terpendek antara dua titik, jarak Manhattan mengukur jumlah dari selisih absolut antara koordinat-koordinat titik tersebut. Metode ini disebut "jarak Manhattan" karena, seperti taksi yang melaju di jalan-jalan Manhattan yang berbentuk kisi, ia harus bergerak mengikuti garis-garis kisi. 

Secara matematis, jarak Manhattan antara dua titik dalam ruang berdimensi-n adalah jumlah dari selisih absolut koordinat Kartesiusnya. 

Rumus jarak Manhattan memasukkan fungsi nilai absolut, yang secara sederhana mengubah selisih negatif menjadi nilai positif. Ini krusial untuk menghitung jarak, karena memastikan semua pengukuran jarak tidak bernilai negatif, mencerminkan jarak skalar yang sebenarnya tanpa memperhatikan arah perjalanan.

Menghitung dan Memvisualisasikan Jarak Manhattan

Seperti yang telah disebutkan, jarak Manhattan dihitung dengan menjumlahkan selisih absolut antara koordinat-koordinat yang bersesuaian dari dua titik. Sekarang mari kita jelajahi dengan contoh di ruang 2D dan 3D.

Contoh 2D

Pertimbangkan dua titik: A(1, 1) dan B(4, 5):

1. Hitung |x₁ - x₂| = |1 - 4| = 3
2. Hitung |y₁ - y₂| = |1 - 5| = 4
3. Jumlahkan hasilnya: 3 + 4 = 7

Dengan demikian, jarak Manhattan antara A dan B adalah 7 satuan. 

Jarak Manhattan dari dua vektor. Gambar oleh Penulis.

Dalam kisi 2D ini, Anda dapat melihat bahwa jarak Manhattan mengikuti jalur yang akan dilalui taksi, bergerak hanya secara horizontal dan vertikal untuk mencapai dari titik A ke titik B.

Contoh 3D

Sekarang, pertimbangkan dua titik dalam ruang 3D: A(1, 2, 3) dan B(4, 5, 6):

1. Hitung |x₁ - x₂| = |1 - 4| = 3
2. Hitung |y₁ - y₂| = |2 - 5| = 3
3. Hitung |z₁ - z₂| = |3 - 6| = 3
4. Jumlahkan hasilnya: 3 + 3 + 3 = 9

Jarak Manhattan antara titik 3D ini adalah 9 satuan.

Perbandingan dengan jarak Euclidean

Sementara jarak Manhattan mengukur jalur sepanjang garis kisi, jarak Euclidean mengukur jarak garis lurus antara dua titik atau, seperti istilahnya, "seperti burung gagak terbang." 

Untuk contoh 2D kita:

• Jarak Manhattan: 7 satuan
• Jarak Euclidean: √((1-4)^² + (1-5)^²) = 5 satuan

Berikut perbandingan visual antara jarak Manhattan dan Euclidean: 

Jarak Manhattan vs. jarak Euclidean. Gambar oleh Penulis.

Di ruang Euclidean, jarak Euclidean selalu kurang dari atau sama dengan jarak Manhattan. 

Memilih antara jarak Manhattan dan jarak Euclidean

Jarak Manhattan sangat berguna dalam skenario ketika:

1. Pergerakan dibatasi pada lintasan berbentuk kisi (misalnya blok kota, tata letak papan sirkuit).
2. Gerakan diagonal tidak diizinkan atau biayanya lebih tinggi.
3. Anda bekerja dengan data berdimensi tinggi dalam machine learning, di mana hal ini bisa lebih efisien secara komputasional dibanding jarak Euclidean.
4. Anda menganalisis perbedaan pada data diskret atau ordinal.

Sebaliknya, jarak Euclidean lebih tepat ketika:

1. Anda mengukur jarak fisik di ruang terbuka.
2. Anda bekerja dengan data kontinu di mana gerakan diagonal sama validnya.

Aplikasi Jarak Manhattan

Jarak Manhattan memiliki aplikasi di berbagai bidang ilmu komputer, analisis data, dan teknologi geospasial. Berikut beberapa area utama di mana jarak Manhattan sangat berguna.

Algoritma penelusuran jalur (misalnya, algoritma A*) 

Dalam lingkungan berbasis kisi, jarak Manhattan memberikan heuristik yang cepat dan efektif untuk memperkirakan jarak antara dua titik. Ini sangat berguna dalam algoritma A*, di mana ia dapat membantu mengarahkan pencarian menuju tujuan dengan lebih efisien dalam skenario di mana pergerakan dibatasi pada arah horizontal dan vertikal. Pikirkan tentang perutean di jalan-jalan kota, algoritma pemecahan labirin, dan jenis penelusuran jalur AI gim video tertentu. 

Teknik pengelompokan (misalnya, K-Means clustering) 

Jarak Manhattan dapat digunakan sebagai metrik jarak dalam algoritma pengelompokan, terutama saat menangani data berdimensi tinggi. Dalam K-Means clustering, menggunakan jarak Manhattan alih-alih jarak Euclidean dapat menghasilkan hasil yang lebih baik, terutama saat menangani data berdimensi tinggi yang jarang atau ketika terdapat outlier. Selain itu, ini sering disukai dalam klasifikasi teks dan pengelompokan dokumen karena efektivitasnya pada ruang vektor yang jarang. Kepekaan jarak Manhattan yang lebih rendah terhadap nilai ekstrem pada dimensi individual dapat menghasilkan hasil pengelompokan yang lebih seimbang pada dataset tertentu.

Pengenalan gambar 

Jarak Manhattan dapat digunakan untuk membandingkan nilai piksel atau vektor fitur. Ini sangat berguna dalam pencocokan templat, saat Anda mencoba menemukan kemunculan gambar kecil dalam gambar yang lebih besar. Ini juga bernilai dalam sistem pengenalan wajah, deteksi objek pada aliran video, atau pencocokan pola di basis data gambar besar, di mana kecepatan sangat penting, dan sedikit kehilangan presisi dibanding jarak Euclidean sering kali dapat diabaikan.

Deteksi outlier 

Jarak Manhattan dapat digunakan untuk mengidentifikasi titik data yang berbeda secara signifikan dari yang lain dalam sebuah dataset karena lebih tidak sensitif terhadap nilai ekstrem pada dimensi individual dibanding jarak Euclidean. Sifat ini membuatnya berguna dalam sistem deteksi anomali, seperti yang digunakan dalam deteksi penipuan atau keamanan jaringan. Dalam sistem keuangan, misalnya, jarak Manhattan dapat membantu mengidentifikasi pola transaksi yang tidak biasa tanpa terlalu dipengaruhi oleh nilai ekstrem pada satu atribut, sehingga berpotensi mengurangi kesalahan.

Sistem Informasi Geografis (GIS) 

Dalam aplikasi GIS, jarak Manhattan dapat memodelkan pergerakan sepanjang jaringan jalan berbentuk kisi, sehingga berguna untuk perencanaan kota dan logistik. Ini digunakan dalam masalah lokasi-alokasi, seperti menentukan lokasi optimal untuk fasilitas berdasarkan meminimalkan total jarak perjalanan di sebuah kota. Jarak Manhattan juga dapat diterapkan dalam tugas analisis spasial, seperti pembuatan zona penyangga di sekitar fitur linear seperti jalan atau sungai. Perencana kota mungkin menggunakan jarak Manhattan untuk menganalisis aksesibilitas layanan publik, sementara perusahaan logistik dapat memanfaatkannya untuk mengoptimalkan rute pengiriman di kota.

Sifat Matematis Jarak Manhattan

Jarak Manhattan memiliki beberapa sifat matematis penting yang membuatnya sangat berguna. Mari jelajahi dua aspek kunci: sifat ruang metriknya dan ketahanannya terhadap outlier.

Sifat ruang metrik

Jarak Manhattan adalah metrik sejati, yang berarti memenuhi keempat syarat yang diperlukan untuk suatu fungsi jarak dalam ruang metrik:

1. Non-negativitas: Jarak antara dua titik mana pun selalu tidak negatif. d(x, y) ≥ 0 untuk semua x dan y.
2. Identitas ketakterbedaan: Jarak antara suatu titik dan dirinya sendiri adalah nol, dan jika jarak antara dua titik adalah nol, keduanya adalah titik yang sama. d(x, y) = 0 jika dan hanya jika x = y.
3. Kesimetrian: Jarak dari titik A ke titik B sama dengan jarak dari B ke A. d(x, y) = d(y, x) untuk semua x dan y.
4. Ketaksamaan segitiga: Jarak antara dua titik selalu kurang dari atau sama dengan jumlah jarak antara titik-titik tersebut dan titik ketiga. d(x, z) ≤ d(x, y) + d(y, z) untuk semua x, y, dan z.

Berbeda dengan jarak kosinus, yang tidak memenuhi ketaksamaan segitiga, kepatuhan jarak Manhattan terhadap semua sifat ini membuatnya berguna dalam berbagai aplikasi matematis dan komputasional. Misalnya:

• Dalam algoritma optimisasi, ketaksamaan segitiga dapat digunakan untuk memangkas ruang pencarian secara efisien.
• Dalam struktur data seperti metric tree, sifat-sifat ini memungkinkan pencarian tetangga terdekat yang lebih cepat.
• Dalam machine learning, algoritma yang bergantung pada metrik jarak (seperti k-nearest neighbors) dapat memanfaatkan sifat-sifat ini untuk jaminan teoretis dan implementasi yang efisien.

Diskriminasi outlier yang lebih baik 

Jarak Manhattan, dengan pendekatan penjumlahan linear, sering memberikan pembedaan outlier yang lebih baik dibanding jarak Euclidean, yang mengkuadratkan selisih. Perbedaan ini muncul karena jarak Manhattan mengakumulasikan selisih absolut pada setiap dimensi secara independen, mengurangi pengaruh luar biasa dari perbedaan besar pada satu dimensi.

Pertimbangkan dua titik dalam ruang 2D: A(0, 0) dan B(10, 0). Sekarang mari perkenalkan titik outlier C dengan koordinat (0, 100):

• Jarak Manhattan antara A dan C: |0 - 0| + |0 - 100| = 100
• Jarak Euclidean antara A dan C: √((0 - 0)^² + (0 - 100)^²) = 100
• Jarak Manhattan antara B dan C: |10 - 0| + |0 - 100| = 110
• Jarak Euclidean antara B dan C: √((10 - 0)^² + (0 - 100)^²) ≈ 100,5

Jarak Manhattan vs Euclidean dengan outlier. Gambar oleh Penulis

Dalam contoh ini, jarak Manhattan dengan jelas membedakan antara jarak AC dan BC, sementara jarak Euclidean menunjukkan keduanya hampir sama karena efek dominan dari outlier pada koordinat y.

Sifat ini membuat jarak Manhattan sangat berguna dalam:

1. Ruang berdimensi tinggi di mana outlier umum terjadi, seperti dalam pemrosesan citra atau analisis teks.
2. Algoritma pengelompokan ketika Anda ingin mengurangi dampak outlier pada centroid klaster.
3. Sistem deteksi anomali ketika Anda ingin mengidentifikasi outlier tanpa terlalu membesar-besarkan signifikansinya.

Dengan lebih tidak sensitif terhadap nilai ekstrem pada dimensi individual, jarak Manhattan dapat memberikan ukuran ketakmiripan yang lebih seimbang pada banyak dataset dunia nyata, terutama yang datanya bising atau tidak sempurna.

Jarak Manhattan di Python dan R

Di sini, kita akan menjelajahi cara menghitung jarak Manhattan menggunakan Python dan R. Setiap contoh akan menunjukkan pendekatan berbeda, dari fungsi kustom hingga metode pustaka.

Contoh Python

Python menawarkan beberapa cara untuk menghitung jarak Manhattan. Mari jelajahi dua metode berbeda.

1. Perhitungan menggunakan array NumPy:

import numpy as np
point_a_np = np.array([1, 1, 1])
point_b_np = np.array([4, 5, 6])
distance_numpy = np.sum(np.abs(point_a_np - point_b_np))
print(f"Manhattan distance (NumPy): {distance_numpy}")Didukung oleh

Keluaran: 

Manhattan distance (NumPy): 12Didukung oleh

Metode ini menggunakan array NumPy secara langsung, yang bisa sangat efisien, terutama saat menangani dataset besar atau ketika Anda sudah bekerja dengan array NumPy dalam analisis Anda.

2. Perhitungan menggunakan fungsi cityblock() dari SciPy: 

from scipy.spatial.distance import cityblock
point_a = (1, 1, 1)
point_b = (4, 5, 6)
distance_scipy = cityblock(point_a, point_b)
print(f"Manhattan distance (SciPy): {distance_scipy}")Didukung oleh

Keluaran:

Manhattan distance (SciPy): 12Didukung oleh

SciPy menyediakan fungsi cityblock(), yang menghitung jarak Manhattan. Metode ini lugas dan efisien, terutama saat Anda bekerja dengan SciPy dalam proyek Anda. 

Contoh R

R juga menyediakan beberapa cara untuk menghitung jarak Manhattan. Mari kita tinjau dua pendekatan berbeda.

1. Membuat fungsi kustom

manhattan_distance <- function(x1, y1, x2, y2) {
  abs(x1 - x2) + abs(y1 - y2)
}
# Example points 
point1 <- c(3, 5) # (x1, y1) 
point2 <- c(1, 9) # (x2, y2) 
# Calculate Manhattan distance between point1 and point2 
distance <- manhattan_distance(point1[1], point1[2], point2[1], point2[2]) 
print(paste("Manhattan distance (custom function):", distance))Didukung oleh

Keluaran:

"Manhattan distance (custom function): 6"Didukung oleh

Dalam contoh ini, kita membuat fungsi kustom bernama manhattan_distance. Fungsi ini mengambil koordinat dua titik sebagai masukan dan menemukan jarak Manhattan dengan menjumlahkan selisih absolut dari masing-masing koordinatnya.

2. Menggunakan pustaka stats

point_a <- c(1, 1, 1)
point_b <- c(4, 5, 6)
distance_builtin <- stats::dist(rbind(point_a, point_b), method = "manhattan")
print(paste("Manhattan distance:", distance_builtin))Didukung oleh

Keluaran: 

"Manhattan distance: 12"Didukung oleh

Dalam contoh kedua, kita memanfaatkan fungsi dist() dari paket stats untuk menghitung jarak Manhattan. Pendekatan ini berguna saat menangani matriks atau banyak titik, karena secara signifikan menyederhanakan proses.

Kesimpulan

Pentingnya jarak Manhattan terletak pada kesederhanaannya, efisiensi komputasi, dan ketahanannya terhadap outlier dalam skenario tertentu. Berbeda dengan jarak Euclidean, jarak Manhattan sering memberikan hasil yang lebih intuitif pada sistem berbasis kisi dan dapat lebih efisien dihitung, terutama di ruang berdimensi tinggi. 

Lebih dari itu, jarak Manhattan dan metrik jarak lainnya muncul di berbagai konteks. Selain kursus Designing Machine Learning Workflows in Python, yang menampilkan satu bab tentang pembelajaran berbasis jarak, dan kursus Cluster Analysis in R, yang menggunakan metrik berbasis jarak untuk klasifikasi dan reduksi dimensi, Anda juga dapat melihat kursus Anomaly Detection in Python, yang menggunakan metrik jarak untuk deteksi outlier dan penskalaan fitur.  

Ingat, pilihan metrik jarak dapat sangat memengaruhi performa dan hasil algoritme Anda. Dengan memahami kapan dan bagaimana menggunakan jarak Manhattan, Anda menambahkan alat yang kuat ke kotak peralatan data science Anda. Teruslah bereksperimen, belajar, dan mendorong batasan kemungkinan dengan algoritma berbasis jarak!