Jarak Minkowski: Panduan Komprehensif

Metrik jarak merupakan tulang punggung dari banyak algoritma dalam data science dan machine learning, memungkinkan pengukuran kemiripan atau ketidakmiripan antar titik data. Dalam panduan ini, kita akan membahas dasar-dasar jarak Minkowski, sifat-sifat matematisnya, dan implementasinya. Kita akan meninjau keterkaitannya dengan ukuran jarak umum lainnya dan mendemonstrasikan penggunaannya melalui contoh kode di Python dan R. 

Baik Anda sedang mengembangkan algoritma klastering, mengerjakan deteksi anomali, atau menyetel model klasifikasi, memahami jarak Minkowski dapat meningkatkan pendekatan Anda terhadap analisis data dan pengembangan model. Mari kita lihat.

Apa itu Jarak Minkowski?

Jarak Minkowski adalah metrik serbaguna yang digunakan dalam ruang vektor bernorma, dinamai dari matematikawan Jerman Hermann Minkowski. Ini merupakan generalisasi dari beberapa ukuran jarak yang terkenal, menjadikannya konsep mendasar di berbagai bidang seperti matematika, ilmu komputer, dan analisis data.

Intinya, jarak Minkowski menyediakan cara untuk mengukur jarak antara dua titik dalam ruang multi-dimensi. Yang membuatnya sangat berguna adalah kemampuannya untuk mencakup metrik jarak lain sebagai kasus khusus, terutama melalui parameter p. Parameter ini memungkinkan jarak Minkowski menyesuaikan diri dengan berbagai ruang permasalahan dan karakteristik data. Rumus umum untuk jarak Minkowski adalah:

Dengan keterangan:

• x dan y adalah dua titik dalam ruang berdimensi n

• p adalah parameter yang menentukan jenis jarak (p ≥ 1)

• |xi - yi| merepresentasikan selisih absolut antara koordinat x dan y pada setiap dimensi

Jarak Minkowski bermanfaat karena dua alasan utama. Pertama, ia memberi Anda fleksibilitas untuk beralih antara jarak Manhattan atau Euclid sesuai kebutuhan. Kedua, ia menyadari bahwa tidak semua dataset (pikirkan ruang berdimensi tinggi) cocok menggunakan jarak yang murni Manhattan atau murni Euclid.

Dalam praktiknya, parameter p umumnya dipilih dengan memasukkan alur kerja validasi latih/uji. Dengan menguji berbagai nilai p selama cross-validation, Anda dapat menentukan nilai mana yang memberikan kinerja model terbaik untuk dataset spesifik Anda.

Cara Kerja Jarak Minkowski

Mari kita lihat bagaimana jarak Minkowski berhubungan dengan rumus jarak lainnya, lalu menelusuri sebuah contoh. 

Generalisasi metrik jarak lain

Hal pertama yang perlu dipertimbangkan adalah bagaimana rumus jarak Minkowski memuat di dalamnya rumus untuk jarak Manhattan, Euclid, dan Chebyshev. 

Jarak Manhattan (p = 1): 

Saat p disetel ke 1, jarak Minkowski menjadi jarak Manhattan. 

Dikenal juga sebagai jarak city block atau norma L1, Jarak Manhattan mengukur jumlah selisih absolut. 

Jarak Euclid (p = 2): 

Saat p disetel ke 2, jarak Minkowski menjadi jarak Euclid.

Jarak Euclid adalah metrik jarak yang paling umum, merepresentasikan jarak garis lurus antara dua titik. 

Jarak Chebyshev (p → ∞): 

Jarak Chebyshev, juga dikenal sebagai jarak papan catur, mengukur selisih maksimum di sepanjang dimensi mana pun. 

Menelusuri sebuah contoh

Untuk benar-benar memahami fungsionalitas dan kekuatan jarak Minkowski, mari kita telusuri sebuah contoh. Eksplorasi ini akan membantu kita memahami bagaimana parameter p memengaruhi perhitungan dan interpretasi jarak dalam ruang multi-dimensi.

Pertimbangkan dua titik dalam ruang 2D:

• Titik A: (2, 3)
• Titik B: (5, 7)

Kita akan menghitung jarak Minkowski antara kedua titik ini untuk berbagai nilai p.

Parameter p dalam rumus jarak Minkowski mengontrol sensitivitas metrik terhadap perbedaan pada setiap komponen:

• Saat p=1: Semua perbedaan berkontribusi secara linear.
• Saat p=2: Perbedaan yang lebih besar berdampak lebih signifikan karena dikuadratkan.
• Saat p>2: Penekanan yang lebih besar diberikan pada perbedaan besar.
• Saat p→∞: Hanya perbedaan maksimum di antara semua dimensi yang penting.

Seiring p meningkat, jarak Minkowski umumnya menurun, mendekati jarak Chebyshev. Ini karena nilai p yang lebih tinggi memberikan bobot lebih pada perbedaan terbesar dan lebih sedikit pada perbedaan yang lebih kecil.

Untuk memvisualisasikan bagaimana berbagai nilai p memengaruhi perhitungan jarak antara titik kita A(2, 3) dan B(5, 7), mari kita amati grafik berikut:

Dengan mengamati grafik, kita dapat melihat bagaimana ukuran jarak berubah saat p meningkat:

• Jarak Manhattan (p=1), yang diwakili jalur hijau, menghasilkan lintasan terpanjang karena mengikuti kisi secara ketat.
• Jarak Euclid (p=2), ditunjukkan oleh garis lurus oranye, memberikan jalur langsung.
• Jarak Chebyshev (p=∞), digambarkan dengan garis putus-putus merah, hanya berfokus pada perbedaan koordinat terbesar, menciptakan jalur yang bergerak maksimal pada satu dimensi sebelum menangani dimensi lainnya.
• Jarak Minkowski dengan p=3 berwarna ungu menunjukkan sedikit kelengkungan, menandakan transisi antara jarak Euclid dan Chebyshev.

Visualisasi ini membantu kita memahami mengapa nilai p yang berbeda mungkin dipilih untuk berbagai aplikasi. Misalnya, jarak Manhattan mungkin lebih tepat untuk permasalahan navigasi kota, sementara jarak Euclid sering digunakan dalam perhitungan di ruang fisik. Nilai p yang lebih tinggi, seperti pada Minkowski p=3, dapat berguna dalam skenario di mana perbedaan besar perlu ditekankan, dan jarak Chebyshev mungkin dipilih ketika perbedaan maksimum pada dimensi mana pun menjadi faktor paling kritis.

Aplikasi Jarak Minkowski

Jarak Minkowski, dengan parameter p yang dapat disesuaikan, adalah alat yang fleksibel yang digunakan di berbagai bidang. Dengan mengubah p, kita dapat menyesuaikan cara mengukur jarak antar titik, menjadikannya cocok untuk berbagai tugas. Berikut empat aplikasi di mana jarak Minkowski berperan penting.

Machine learning dan data science

Dalam machine learning dan data science, jarak Minkowski mendasar bagi algoritma yang bergantung pada pengukuran kemiripan atau ketidakmiripan antar titik data. Salah satu contohnya adalah algoritma k-Nearest Neighbors (k-NN), yang mengklasifikasikan titik data berdasarkan kategori dari tetangga terdekatnya. Dengan menggunakan jarak Minkowski, kita dapat menyesuaikan parameter p untuk mengubah cara kita menghitung "kedekatan" antar titik.

Pengenalan pola

Pengenalan pola melibatkan identifikasi pola dan keteraturan dalam data, seperti pengenalan tulisan tangan atau deteksi fitur wajah. Dalam konteks ini, jarak Minkowski mengukur perbedaan antara vektor fitur yang merepresentasikan pola. Misalnya, dalam pengenalan citra, setiap gambar dapat direpresentasikan oleh vektor nilai piksel. Menghitung jarak Minkowski antar vektor ini memungkinkan kita mengukur seberapa mirip atau berbeda gambar-gambar tersebut.

Dengan menyesuaikan p, kita dapat mengontrol sensitivitas ukuran jarak terhadap perbedaan pada fitur tertentu. Nilai p yang lebih rendah mungkin mempertimbangkan perbedaan keseluruhan di seluruh piksel, sementara nilai p yang lebih tinggi dapat menekankan perbedaan signifikan pada wilayah tertentu dari gambar.

Deteksi anomali

Deteksi anomali bertujuan mengidentifikasi titik data yang menyimpang secara signifikan dari mayoritas, yang penting dalam bidang seperti deteksi kecurangan, keamanan jaringan, dan deteksi kerusakan pada sistem. Jarak Minkowski digunakan untuk mengukur seberapa jauh sebuah titik data dari yang lain dalam dataset. Titik dengan jarak besar berpotensi menjadi anomali. Dengan memilih p yang tepat, analis dapat meningkatkan sensitivitas sistem deteksi anomali terhadap jenis penyimpangan yang paling relevan dengan konteks spesifik mereka.

Geometri komputasional dan analisis spasial

Dalam geometri komputasional dan analisis spasial, jarak Minkowski digunakan untuk menghitung jarak antar titik di ruang, yang menjadi dasar bagi banyak algoritma geometri. Misalnya, deteksi tumbukan dalam domain ini bergantung pada jarak Minkowski untuk menentukan kapan objek cukup dekat untuk berinteraksi. Dengan menyesuaikan p, pengembang dapat membuat batas tumbukan beragam, mulai dari bersudut (p rendah) hingga membulat (p tinggi).

Di luar deteksi tumbukan, jarak Minkowski dapat berguna dalam klasterisasi spasial dan analisis bentuk. Memvariasikan nilai p memungkinkan peneliti menekankan aspek yang berbeda dari hubungan spasial, dari jarak blok kota hingga kemiripan bentuk secara keseluruhan.

Sifat Matematis Jarak Minkowski

Jarak Minkowski bukan hanya alat yang serbaguna dalam aplikasi praktis, tetapi juga konsep penting dalam teori matematika, khususnya dalam studi ruang metrik dan norma.

Sifat ruang metrik

Jarak Minkowski memenuhi empat sifat esensial yang diperlukan agar suatu fungsi dianggap sebagai metrik dalam ruang metrik:

• Non-negativitas: Jarak Minkowski antara dua titik mana pun selalu tidak negatif, d(x,y)≥0. Ini jelas karena merupakan akar ke-p dari jumlah suku tak negatif (nilai absolut dipangkatkan p).
• Identitas Ketakterbedaan: Jarak Minkowski antara dua titik bernilai nol jika dan hanya jika kedua titik tersebut identik. Secara matematis, d(x,y) = 0 jika dan hanya jika x=y. Ini mengikuti karena selisih absolut antara komponen yang identik adalah nol.
• Simetri: Jarak Minkowski bersifat simetris, artinya d(x,y)=d(y,x). Sifat ini berlaku karena urutan pengurangan dalam nilai absolut tidak memengaruhi hasil.
• Pertaksamaan Segitiga: Jarak Minkowski memenuhi pertaksamaan segitiga, yang menyatakan bahwa untuk tiga titik x, y, dan z mana pun, jarak dari x ke z paling besar sama dengan jumlah jarak dari x ke y dan dari y ke z; secara formal, d(x,z)≤d(x,y)+d(y,z). Sifat ini kurang intuitif untuk dibuktikan langsung dari rumus dan umumnya memerlukan matematika yang lebih lanjut, namun pada dasarnya memastikan bahwa jalur langsung antara dua titik adalah rute terpendek.

Generalisasi norma

Jarak Minkowski bertindak sebagai kerangka umum yang menyatukan berbagai cara untuk mengukur jarak dalam ruang matematis melalui konsep norma. Secara sederhana, sebuah norma adalah fungsi yang memberikan panjang atau ukuran tak negatif pada sebuah vektor di ruang vektor, pada dasarnya mengukur seberapa "panjang" vektor tersebut. Dengan menyesuaikan parameter p dalam rumus jarak Minkowski, kita dapat beralih mulus antar norma yang berbeda, masing-masing menyediakan cara unik untuk menghitung panjang vektor.

Sebagai contoh, ketika p=1, jarak Minkowski menjadi norma Manhattan, mengukur jarak sebagai jumlah selisih absolut pada setiap dimensi—bayangkan menavigasi kisi jalan kota. Dengan p=2, ia berubah menjadi norma Euclid, menghitung jarak garis lurus ("seperti burung terbang") antar titik. Saat p mendekati tak hingga, ia berkonvergensi ke norma Chebyshev, di mana jarak ditentukan oleh perbedaan tunggal terbesar di antara dimensi. Fleksibilitas ini memungkinkan jarak Minkowski beradaptasi dengan berbagai konteks matematis dan praktis, menjadikannya alat yang serbaguna untuk mengukur jarak dalam berbagai skenario.

Menghitung Jarak Minkowski di Python dan R

Mari telusuri implementasi perhitungan jarak Minkowski menggunakan Python dan R. Kita akan meninjau paket dan pustaka yang tersedia untuk mencapainya. 

Contoh Python

Untuk menghitung jarak Minkowski di Python, kita dapat menggunakan pustaka SciPy, yang menyediakan implementasi efisien dari berbagai metrik jarak. Berikut contoh yang menghitung jarak Minkowski untuk berbagai nilai p:

import numpy as np
from scipy.spatial import distance

# Example points
point_a = [2, 3]
point_b = [5, 7]

# Different p values
p_values = [1, 2, 3, 10, np.inf]
print("Minkowski distances using SciPy:")

for p in p_values:
	if np.isinf(p):
	    # For p = infinity, use Chebyshev distance
	    dist = distance.chebyshev(point_a, point_b)
	    print(f"p = ∞, Distance = {dist:.2f}")
	else:
	        dist = distance.minkowski(point_a, point_b, p)
	        print(f"p = {p}, Distance = {dist:.2f}")Didukung oleh

Dengan menjalankan kode ini, pembaca dapat mengamati bagaimana jarak berubah dengan nilai p yang berbeda, mempertegas konsep yang dibahas sebelumnya dalam artikel.

Minkowski distances using SciPy:
p = 1, Distance = 7.00
p = 2, Distance = 5.00
p = 3, Distance = 4.50
p = 10, Distance = 4.02
p = ∞, Distance = 4.00Didukung oleh

Kode ini menunjukkan:

1. Cara menggunakan fungsi jarak SciPy untuk jarak Minkowski dan Chebyshev.
2. Perhitungan jarak untuk berbagai nilai p, termasuk tak hingga.
3. Hubungan antara jarak Minkowski dan metrik lainnya (Manhattan, Euclid, Chebyshev).

Contoh R

Untuk R, kita akan memanfaatkan fungsi dist() dari pustaka stats:

# Define the Minkowski distance function using stats::dist

minkowski_distance <- function(x, y, p) {
  points <- rbind(x, y)
  if (is.infinite(p)) {
    # For p = Inf, use method = "maximum" for Chebyshev distance
    distance <- stats::dist(points, method = "maximum")
  } else {
    distance <- stats::dist(points, method = "minkowski", p = p)
  }
  return(as.numeric(distance))
}

# Example usage
point_a <- c(2, 3)
point_b <- c(5, 7)

# Different p values
p_values <- c(1, 2, 3, 10, Inf)
cat("Minkowski distances between points A and B using stats::dist:\n")

for (p in p_values) {
  distance <- minkowski_distance(point_a, point_b, p)
  if (is.infinite(p)) {
    cat(sprintf("p = ∞, Distance = %.2f\n", distance))
  } else {
    cat(sprintf("p = %g, Distance = %.2f\n", p, distance))
  }
}Didukung oleh

Kode ini menunjukkan:

1. Cara membuat fungsi minkowski_distance menggunakan fungsi dist() dari stats.

2. Penanganan berbagai nilai p, termasuk tak hingga untuk jarak Chebyshev.

3. Perhitungan jarak Minkowski untuk berbagai nilai p.

4. Format output untuk menampilkan jarak dibulatkan hingga 2 angka desimal.

Output dari kode ini akan menjadi:

Minkowski distances between points A and B using stats::dist:
p = 1, Distance = 7.00
p = 2, Distance = 5.00
p = 3, Distance = 4.50
p = 10, Distance = 4.02
p = ∞, Distance = 4.00Didukung oleh

Implementasi R ini menjadi padanan contoh Python, memungkinkan pembaca melihat bagaimana jarak Minkowski dapat dihitung di berbagai lingkungan pemrograman.

Kesimpulan

Jarak Minkowski menyediakan pendekatan yang fleksibel dan adaptif untuk mengukur jarak dalam ruang multi-dimensi. Kemampuannya untuk menggeneralisasi metrik jarak umum lainnya melalui parameter p menjadikannya alat yang berharga di berbagai bidang dalam data science dan machine learning. Dengan menyesuaikan p, praktisi dapat menyesuaikan perhitungan jarak dengan karakteristik spesifik data mereka dan kebutuhan proyek, yang berpotensi meningkatkan hasil pada tugas mulai dari klastering hingga deteksi anomali.

Saat Anda menerapkan jarak Minkowski dalam pekerjaan Anda, kami mendorong Anda untuk bereksperimen dengan berbagai nilai p dan mengamati dampaknya pada hasil. Bagi yang ingin memperdalam pemahaman dan keterampilan, kami merekomendasikan untuk menjelajahi kursus Designing Machine Learning Workflows in Python dan mempertimbangkan program karier Sertifikasi Data Scientist kami. Sumber daya ini dapat membantu Anda membangun pengetahuan tentang metrik jarak dan menerapkannya secara efektif dalam berbagai skenario.