Memahami Jarak Chebyshev: Panduan Komprehensif

Ilmu data dan analisis spasial sangat bergantung pada berbagai metrik jarak untuk menyelesaikan masalah kompleks. Meskipun jarak Manhattan dan Euclidean banyak dikenal, ada metrik lain yang sangat menarik dan patut mendapat perhatian: jarak Chebyshev. Ukuran jarak ini menawarkan perspektif berbeda tentang hubungan spasial, khususnya di lingkungan berbasis kisi (grid) dan ruang data multidimensi.

Dalam panduan ini, kita akan membahas dasar-dasar jarak Chebyshev, meninjau sifat matematisnya, dan menelusuri penerapannya di dunia nyata. Kami juga menyediakan contoh kode praktis dalam Python dan R, sehingga Anda dapat mengimplementasikan perhitungan jarak Chebyshev dalam proyek Anda sendiri. Selain itu, jika Anda ingin memperdalam pemahaman tentang bagaimana metrik semacam ini cocok dalam alur kerja ilmu data yang lebih luas, kursus kami Designing Machine Learning Workflows in Python menawarkan wawasan berharga tentang mengintegrasikan berbagai teknik analitis, termasuk pembelajaran berbasis jarak.

"Jarak papan catur." Gambar oleh Dall-E.

Apa itu Jarak Chebyshev?

Jarak Chebyshev, dinamai dari matematikawan Rusia Pafnuty Chebyshev, didefinisikan sebagai selisih maksimum antara koordinat dua titik sepanjang satu sumbu mana pun. Secara matematis, untuk dua titik P = (x1, y1, ..., z1) dan Q = (x2, y2, ..., z2) dalam ruang berdimensi-n, jarak Chebyshev dinyatakan sebagai:

Definisi ini membedakan jarak Chebyshev dari metrik umum lainnya seperti jarak Manhattan (menjumlahkan selisih absolut) dan jarak Euclidean (menghitung jarak garis lurus). 

Cara Kerja Jarak Chebyshev

Mari kita lihat bagaimana jarak Chebyshev bekerja untuk membangun intuisi kita. 

Interpretasi geometris 

Jarak Chebyshev menekankan pergeseran maksimum pada arah koordinat mana pun, yang penting dalam skenario di mana pergerakan tidak terbatas pada jalur horizontal atau vertikal, tetapi mencakup garis langsung apa pun.

Pertimbangkan dua titik dalam ruang 2 dimensi: Titik A pada koordinat (1, 1) dan Titik B pada koordinat (4, 5). Untuk mencari jarak Chebyshev antara kedua titik ini, kita fokus pada selisih maksimum sepanjang salah satu sumbu koordinat.

• Selisih sepanjang sumbu x: |4 - 1| = 3
• Selisih sepanjang sumbu y: |5 - 1| = 4

Di sini, jarak Chebyshev adalah 4 karena jarak Chebyshev = max(3, 4) = 4.

Visual pendamping menggambarkan titik-titik ini pada kisi, menyoroti area yang berada dalam jarak Chebyshev 4 dari Titik A. Area berarsir kuning menunjukkan semua posisi yang dapat dijangkau dalam metrik jarak ini. 

Jarak Chebyshev Ditunjukkan dalam Sistem Koordinat 2D. Gambar oleh Penulis. 

Interpretasi grid

Jarak Chebyshev juga umum disebut jarak papan catur karena mudah dipahami dalam konteks catur: Jarak Chebyshev antara dua petak setara dengan jumlah langkah raja yang diperlukan untuk berpindah dari satu petak ke petak lainnya. Interpretasi ini dapat divisualisasikan pada kisi kita, di mana setiap angka merepresentasikan jarak Chebyshev dari petak tengah (tempat raja berada) ke setiap petak lain di papan.

Jarak Chebyshev Divisualisasikan pada Tata Letak Papan Catur. Gambar oleh Penulis. 

Dalam model visual kami, raja ditempatkan di c5. Angka-angka pada papan catur mewakili jarak Chebyshev dari c5 ke semua petak lainnya. Misalnya, jarak dari c5 ke e7 adalah 2 karena raja dapat mencapai e7 dalam dua langkah: satu langkah diagonal ke d6, diikuti satu langkah diagonal lagi ke e7. Demikian pula, jarak ke petak tepi terdekat (seperti c8 atau h5) cukup dihitung dari jumlah langkah horizontal atau vertikal langsung.

Pendekatan berbasis kisi untuk menjelaskan jarak Chebyshev ini menyoroti penerapannya yang praktis dalam permainan seperti catur dan juga relevan dalam algoritme pencarian jalur yang digunakan dalam robotika dan kecerdasan buatan, di mana tujuannya adalah menemukan jalur paling efisien antar titik dalam kisi.

Aplikasi Jarak Chebyshev

Sifat-sifat jarak Chebyshev membuatnya bernilai di berbagai bidang, khususnya ketika melibatkan struktur menyerupai kisi atau pergerakan simultan sepanjang sumbu yang berbeda. Mari jelajahi beberapa aplikasinya:

Robotika dan logistik gudang

Di lingkungan tempat robot atau sistem otomatis bergerak mengikuti pola kisi, jarak Chebyshev dapat mengoptimalkan perencanaan jalur. Bayangkan, misalnya, robot pertanian yang menavigasi lahan tanaman atau kendaraan otonom di lingkungan terstruktur. 

Di gudang otomatis, robot sering bergerak sepanjang jalur mirip kisi. Jarak Chebyshev membantu mengoptimalkan pergerakan mereka, terutama ketika mereka dapat bergerak secara diagonal. Optimasi ini dapat meningkatkan efisiensi secara signifikan dalam proses pengambilan dan penyimpanan barang.

Pemrosesan citra

Dalam analisis citra digital, jarak Chebyshev digunakan dalam operasi berbasis piksel. Ini membantu mendefinisikan lingkungan di sekitar sebuah piksel untuk berbagai transformasi dan filter. Ini sering digunakan dalam tugas seperti deteksi tepi atau pengenalan pola.

Kemampuan untuk mempertimbangkan piksel diagonal semudah piksel horizontal atau vertikal membuat jarak Chebyshev sangat berguna dalam aplikasi ini.

Sistem informasi geografis (GIS)

Perencana kota dan layanan darurat dapat menggunakan jarak Chebyshev untuk menghitung jumlah langkah minimum yang diperlukan antara dua titik pada peta kisi. Ini bernilai untuk mengoptimalkan perencanaan rute darurat di kota dengan tata letak jalan berbentuk kisi atau merencanakan rute transportasi umum yang efisien.

Dalam skenario ini, jarak Chebyshev dapat memberikan perkiraan cepat waktu tempuh atau jarak di lingkungan yang memungkinkan pergerakan diagonal.

Machine learning dan data science

Dalam bidang machine learning dan ilmu data, jarak Chebyshev diterapkan dalam algoritme pengelompokan tertentu atau sistem deteksi anomali.

Ini sangat berguna dalam skenario di mana selisih maksimum di sepanjang dimensi mana pun lebih penting daripada selisih keseluruhan. Misalnya, dalam deteksi anomali, suatu titik data yang menyimpang secara signifikan pada satu fitur saja dapat dianggap anomali, terlepas dari nilainya pada dimensi lain.

Pengembangan game

Di luar catur, jarak Chebyshev memiliki aplikasi yang lebih luas dalam pengembangan game, khususnya untuk game berbasis kisi. Ini dapat memodelkan biaya pergerakan untuk entitas yang dapat bergerak secara diagonal semudah secara horizontal atau vertikal. Ini sangat berguna dalam game strategi, roguelike, atau game apa pun dengan pergerakan berbasis kisi. 

Selain itu, dengan memasukkan jarak Chebyshev, pengembang game dapat menciptakan mekanika pergerakan yang lebih detail dan realistis, meningkatkan permainan dan kedalaman strategi.

Sifat Matematis Jarak Chebyshev

Jarak Chebyshev memenuhi semua sifat ruang metrik, yang penting untuk penerapannya di berbagai bidang. Mari verifikasi sifat-sifat ini:

1. Non-negativitas: Untuk sembarang dua titik x dan y, d(x, y) ≥ 0
   Jarak Chebyshev selalu non-negatif karena didefinisikan sebagai nilai maksimum dari selisih absolut, yang selalu non-negatif.

2. Identitas yang tak terbedakan: d(x, y) = 0 jika dan hanya jika x = y
   Jarak Chebyshev antara suatu titik dan dirinya sendiri selalu 0. Jika jarak Chebyshev bernilai 0, artinya selisih maksimum pada dimensi mana pun adalah 0, yang menyiratkan titik-titik tersebut identik.

3. Simetri: d(x, y) = d(y, x)
   Urutan titik tidak berpengaruh dalam perhitungan jarak Chebyshev. Selisih absolut maksimum tetap sama terlepas dari titik mana yang dipertimbangkan terlebih dahulu.

4. Pertaksamaan segitiga: d(x, z) ≤ d(x, y) + d(y, z)
   Sifat ini berlaku untuk jarak Chebyshev. Secara intuitif, selisih maksimum antara x dan z pada dimensi mana pun tidak dapat lebih besar daripada jumlah selisih maksimum dari x ke y dan dari y ke z.

Sifat-sifat ini memastikan bahwa jarak Chebyshev berperilaku konsisten dan intuitif dalam berbagai aplikasi matematis dan praktis.

Membandingkan Chebyshev dengan Metrik Jarak Lain

Dalam visual di bawah ini, kita menelusuri perbedaan antara jarak Manhattan, Euclidean, dan Chebyshev: 

Perbandingan Jarak Chebyshev, Manhattan, dan Euclidean. Gambar oleh Penulis. 

• Jarak Manhattan (D=7): Diilustrasikan oleh garis putus-putus magenta, metrik ini menjumlahkan selisih absolut dari koordinat Kartesius. Ini sering divisualisasikan sebagai jalur yang menelusuri garis-garis kisi dalam pola tegak lurus, mencerminkan analogi dunia nyata jarak antarkota blok yang hanya dapat dilalui di jalan-jalan ortogonal. Untuk pemahaman lebih mendalam tentang metrik ini Anda dapat merujuk pada tutorial komprehensif kami, What is Manhattan Distance? 
• Jarak Euclidean (D=5): Ditunjukkan oleh garis hijau solid, ini adalah jarak "garis lurus" antara dua titik dalam ruang Euclidean. Ini adalah bentuk jarak yang paling intuitif: jalur langsung yang menghubungkan dua titik.
• Jarak Chebyshev (D=4): Diwakili oleh area berarsir kuning, metrik jarak ini didefinisikan sebagai nilai maksimum dari selisih absolut antara koordinat sepasang objek. Ini sangat berguna dalam skenario di mana Anda dapat bergerak ke arah mana pun dari titik kisi dengan gerakan diagonal diizinkan.

Keterkaitan dengan jarak Minkowski

Jarak Chebyshev berkaitan erat dengan keluarga metrik jarak yang lebih luas yang dikenal sebagai jarak Minkowski. Faktanya, jarak Chebyshev adalah kasus khusus dari jarak Minkowski.

Jarak Minkowski orde p antara dua titik x = (x₁, ..., xn) dan y = (y₁, ..., yn) didefinisikan sebagai:

Di mana:

• p ≥ 1 adalah bilangan riil
• n adalah jumlah dimensi

Jarak Chebyshev muncul sebagai kasus khusus ketika p mendekati tak hingga. Secara matematis, kita dapat menyatakannya sebagai:

Keterkaitan ini menempatkan jarak Chebyshev dalam konteks bersama metrik jarak terkenal lainnya:

• Ketika p = 1, kita memperoleh jarak Manhattan.
• Ketika p = 2, kita memperoleh jarak Euclidean.
• Ketika p → ∞, kita memperoleh jarak Chebyshev.

Memahami keterkaitan ini membantu dalam memilih metrik jarak yang sesuai untuk aplikasi tertentu, karena setiap metrik menekankan aspek yang berbeda dari jarak antar titik.

Jarak Chebyshev di Python dan R

Untuk membantu Anda mengimplementasikan perhitungan jarak Chebyshev dalam proyek Anda, mari lihat cara melakukannya dalam dua bahasa pemrograman populer: Python dan R. Contoh ini akan menunjukkan cara menghitung jarak Chebyshev antara dua titik dalam ruang 2D.

Contoh Python

Python menawarkan cara langsung untuk menghitung jarak Chebyshev menggunakan pustaka SciPy. Berikut caranya:

from scipy.spatial import distance

# Define points
point_A = (1, 1)
point_B = (4, 5)

# Calculate Chebyshev distance
chebyshev_dist = distance.chebyshev(point_A, point_B)

print(f"The Chebyshev distance between {point_A} and {point_B} is {chebyshev_dist}.")

The Chebyshev distance between (1, 1) and (4, 5) is 4.

Dalam contoh Python ini, kita menggunakan fungsi distance.chebyshev() dari modul spatial milik SciPy. Fungsi ini menerima dua titik sebagai argumen dan mengembalikan jarak Chebyshevnya. Titik-titik direpresentasikan sebagai tuple, sehingga mudah digunakan untuk koordinat dalam dimensi apa pun.

Contoh R

Untuk pengguna R, kita dapat menghitung jarak Chebyshev menggunakan paket philentropy. Berikut caranya:

# Install and Load the philentropy package
# install.packages("philentropy")
library(philentropy)

# Define points
point_A <- c(1, 1)
point_B <- c(4, 5)

# Bind points into a matrix
points_matrix <- rbind(point_A, point_B)

# Calculate Chebyshev distance
chebyshev_dist <- distance(points_matrix, method = "chebyshev")

# Print the result
print(paste("The Chebyshev distance between points is:", chebyshev_dist))

The Chebyshev distance between points is: 4

Dalam contoh R ini, kita terlebih dahulu memuat paket philentropy. Kita mendefinisikan titik sebagai vektor lalu menumpuknya menjadi matriks. Fungsi distance() dari philentropy kemudian digunakan untuk menghitung jarak Chebyshev; kita hanya perlu menyebutkan chebyshev pada argumen method.

Potongan kode ini memberikan titik awal yang praktis untuk mengimplementasikan perhitungan jarak Chebyshev dalam proyek ilmu data atau machine learning Anda.

Kesimpulan

Sepanjang artikel ini, kita telah menelusuri jarak Chebyshev dan perspektifnya yang bernilai dalam mengukur hubungan spasial. Kemampuannya menangkap selisih maksimum pada dimensi mana pun membuatnya sangat cocok untuk skenario di mana pergerakan ke segala arah sama mudah atau sama mahal, seperti dalam robotika, logistik gudang, dan algoritme catur.

Saat Anda terus mengeksplorasi metrik spasial dan analisis data, ingatlah bahwa jarak Chebyshev menawarkan lensa berbeda untuk melihat dan menyelesaikan masalah spasial yang kompleks. Pertimbangkan untuk menjelajahi jalur keterampilan Machine Learning in Production kami untuk membantu menjembatani kesenjangan antara pemahaman teoretis dan implementasi praktis model machine learning, termasuk penerapan metrik jarak di lingkungan produksi. Bagi mereka yang ingin memvalidasi keahliannya di bidang ini, Data Scientist Certification menyediakan kredensial yang diakui yang menunjukkan kemahiran dalam keterampilan ilmu data esensial, termasuk penggunaan berbagai metrik jarak dan penerapannya.