Thread by @pacmannai

Distance Function: Sudut Pandang Baru atas Jarak
.
.
.
A thread

Pastinya kita udah gak asing lagi ya denger-denger kata korelasi, similaritas, klasifikasi, clustering, dan hal-hal lain yang sejenis

Katakanlah kita ingin bikin sebuah clustering pake pendekatan similaritas. Gimana sih caranya kita mengatakan 2 titik/data itu similar? Ya simplenya adalah dengan mengatakan bahwa tipe mereka sama

Tapi gimana caranya kita melihat mereka punya tipe yang sama? Kalau kita plot mereka, kemungkinan jarak antara mereka itu berdekatan

Nah udah keliatan ya arah pembicaraan kita. Yes, kita bakal ngomongin jarak (distance). Dalam algoritma-algoritma machine learning yang udah kita kenal selama ini, ternyata gak lepas dari yang namanya jarak

Name it. KNN, face recognition, censored image, recommendation system, dan lainnya itu membutuhkan jarak dalam penyusunan algoritmanya.

Nah topik yang bakal kita bahas kali ini adalah distance function. Apa sih itu?

Sebelum masuk kesitu, kita kenalan dulu sama yang namanya distance metric. Secara formal distance metric itu sebuah fungsi d yang memenuhi 3 syarat ini:

Kalo kita hilangin syarat ke-3 atau syarat ke-2, maka kita dapatkan definisi dari distance function itu. Jadi clear ya, kalo kita punya fungsi yang memenuhi syarat distance metric, maka jelas dia memenuhi syarat distance function

Balik lagi, algoritma yang kita kenal selama ini ternyata gak lepas dari pemakaian distance function atau jarak. Oleh karena itu, pemilihan jenis jarak yang tepat akan membuat algoritma berjalan dengan baik

Loh loh, pemilihan jarak? Maksudnya ada banyak macam jarak gitu yang bisa kita pake? Bener banget, jarak yang dipake itu macem-macem pendefinisiannya. So, mari kita mulai!

Yang pertama, yang paling terkenal sedunia. Udah kita pake sejak SMP. Euclidean Distance! Ciri khasnya, dia menghitung jarak antar titik dengan mencari akar dari selisih kuadrat antar komponen titiknya.

Euclidean Distance yang paling sering kita temui adalah yang bekerja pada ruang 1 dan 2 dimensi. Padahal ini juga tetap bekerja sampai dimensi-n! Fyi, KNN sering menggunakan Euclidean Distance sebagai perhitungan jaraknya

Kedua, Manhattan (Taxi-Cab) Distance. Yang satu ini menghitung jarak berdasarkan jarak terpendek yang bisa ditempuh suatu titik jika ingin dateng ke titik yang lain tapi geraknya harus mengikuti komponen titiknya.

Biar gampang mikirnya, bayangin dalam 2 dimensi kalian bikin grid di setiap titik (x,y). Nah kalian tarik garis lurus titik awal ke titik tujuan, terus mulai hitung berapa langkahnya untuk sampe kesana

Ketiga, ada Chebyshev Distance. Kalo yang ini nentuin jaraknya dengan cara mengambil nilai maksimal dari selisih mutlak antara dua titik pada setiap komponennya. Pada kasus 2 dimensi, Chebyshev akan ngitung gedean mana selisih di sumbu x atau di sumbu y

Keempat, Minkowski Distance. Nah kalo yang ini sih perumuman dari 3 distance yang udah kita bahas tadi. Kalo lo perhatiin definisi jaraknya di gambar ini, semakin gede nilai p nya, maka dia bakal makin mendekati definisi dari Chebyshev Distance

Kelima, agak sedikit beda nih. Gak ngomongin dimensi. Hamming Distance. Dia ini menghitung seberapa beda 2 string dengan panjang yang sama jika dibandingkan berdasarkan karakter-karakter yang seletak.

Contoh sederhana dari menghitung Hamming Distance ini misalnya kita punya string 11011001 dan 10011101. Nah kita liat perbedaannya ada di karakter ke 2 dan ke 6, berarti Hamming Distancenya adalah 2 sebab ada 2 karakter yg seletak tapi isinya beda.

Ini sama dengan mengatakan seberapa “error” suatu string jika dibandingkan dengan string lain yang dijadikan patokan. Nah Hamming Distance ini kepake banget di error correcting pada coding theory

Sekarang mari kita coba sedikit kegunaan distance ini. Misalkan kita punya data yang berisi data bola ungu dan kuning. Kita beri angka 1 dan R untuk kelas bola ungu lalu angka 2 dan A untuk kelas bola kuning. Dan kita punya data kaya gini

Setiap baris menyatakan karakteristik suatu bola dan di kolom terakhirnya menyatakan warna bola tersebut. Karena ada 5 baris maka artinya kita punya 5 bola.

Sekarang anggaplah kita gatau bola di baris pertama itu warnanya apa (namakan si X). Nah kita pengen jalanin KNN ini supaya kita tau si X ini masuk ke bola warna apa

Normalnya kalo kita mau nentuin si X ini masuk ke kelas mana, cara paling mudah adalah dengan kita tinjau si X ini karakteristiknya paling mirip ke kelas yang mana ya, kalo miripnya sama kelas kuning, ya kemungkinan si X ini adalah bola kuning, otherwise, dia ungu

Tapi tidak untuk KNN, dia bakal pake cara matematis yaitu dengan memanfaatkan distance function untuk melakukan klasifikasi. Dalam kasus kita, artinya kita harus menghitung jarak satu baris dengan lainnya

Sebagai contoh, kita pake Euclidean Distance untuk menghitung jarak antar baris ini. Kita ambil data di baris pertama dan kedua. Berarti kita cari dulu selisih tiap kolom, kita kuadratkan, kita jumlahkan, baru kita akarin.

Dari baris pertama dan kedua, berarti kita punya (1-2)^2 + (1-2)^2 + (1-2)^2 + (1-2)^2 + (1-2)^2 + (1-2)^2 + (1-2)^2 + (1-2)^2 = 8. Nah berarti distance antara baris 1 dan 2 adalah akar 8 yakni sekitar 2,83. Cara ini kita lakukan terus untuk semua baris

Setelah kita dapatkan semua distance antar baris, kita urutkan dari yg paling kecil sampe paling besar, lalu kita pilih nilai yg kita mau dari list distance tersebut untuk dijadikan nilai K pada KNNnya. Misalkan kita pilih K = 3

Berarti kita cari deh data-data mana aja yang paling deket dengan distance 3 dari si X tersebut. Kelas yang memuat data lebih banyak adalah yang menjadi jawaban kita. Berdasarkan plotnya, kita punya kaya gini nih

Karena data yang paling banyak masuk di K = 3 adalah warna ungu, berarti kemungkinan besar si X ini adalah bola berwarna ungu. Sesuai dong ya sama data awal kita tadi.

Ternyata konsep distance ga cuma dipake di topik-topik fisika atau matematika yang kita udah kenal sejak dulu. Distance dengan berbagai macam definisinya, punya manfaat masing-masing tergantung kebutuhannya

Masih banyak konsep lain yang bisa kalian eksplor untuk membantu pekerjaan kalian sebagai Data Scientist. Di non degree program Data Scientist Pacmann.AI, kalian ga hanya cuma belajar konsep aja, tapi juga akan praktek langsung

Yuk, upgrade kemampuan kamu di non degree program Data Scientist Pacmann.AI. Kurikulumnya bisa kalian cek di bit.ly/brosurpacmannai atau langsung aja daftar di bit.ly/PendaftaranNon…. See you!

Referensi:
cs.huji.ac.il/~daphna/theses…
towardsdatascience.com/knn-k-nearest-…