JS06 - ANN (Approximate Nearest Neighbors)
Bagaimana cara anda mencari kemiripan anda dengan teman-teman dalam satu kelas? ambil satu fitur misal warna kulit. Warna kulit dalam sebuah citra bisa direpresentasikan menggunakan ruang warna RGB. ambil foto punggung tangan kita, crop dengan ukuran resolusi tertentu (misal 200 x 200 px). Hitung rata-rata RGB dari semua pixel, dan akan kita dapatkan satu nilai avg_RGB untuk warna kulit kita. langkah berikutnya tinggal kita hitung jarak terdekat antara avg_RGB kita sendiri dengan avg_RGB teman-teman sekelas. dengan menghitung jarak untuk semua teman sekelas, maka akan kita dapatkan tabel urutan kemiripan mulai dari yg termirip hingga yang paling tidak mirip.
Misalkan nama saya Anto, warna kulit saya avg_RGB = (120, 65, 21). teman-teman yang mirip warna kulitnya dengan saya adalah:
1.
Andika
(123, 69, 17)
0,03
2.
Wendy
(132, 56, 15)
0,05
3.
dst
dst
dst
Tabel diatas sudah diurutkan mulai dari yang termirip hingga yang paling tidak mirip dari nilai kedekatannya (makin dekat makin kecil nilainya -Euclidean), yang harus kita lakukan adalah menghitung jarak antara warna kulit kita (Anto) dengan warna kulit semua teman-teman dalam sekelas. Data Anto kita kenal dengan nama (Query Point). Artinya jika teman sekelas ada 30 orang, anto akan menghitung jarak dengan semua 30 org temannya agar dapat membentuk tabel urutan seperti diatas. Sekarang jika Anto ingin menghitung kemiripan warna kulitnya dengan seluruh manusia diseluruh dunia, maka dia harus menghitung jaraknya dengan semua orang (7,8 miliar) kemudian mengurutkannya. Bagaimana jika ditambah fiturnya tidak hanya warna kulit tetapi warna rambutnya juga diperhitungkan sebagai parameter kemiripan, ditambah tinggi badan, tambah berat badan. kita akan lakukan percobaan nanti terkait hal ini. Agar proses pencarian kedekatan data ini tidak memakan waktu, ada beberapa rekayasa model penentuan kedekatan / kemiripan data yang bisa digunakan yang dikenal dengan ANN (Approximate Nearest Neighbors / Perkiraan Tetangga terdekat). Dengan menggunakan model ini, kita dapat melakukan optimalisasi model clustering atau klasifikasi yang didalam tahapannya ada perhitungan kedekatan (seperti misal KMeans (clustering) dan KNN (Classification). ANN ini menjadi populer karena dapat memberikan hasil yang mendekati model nearest neighbors asli (exact) tetapi membutuhkan waktu komputasi yang jauh lebih cepat, sangat cocok sekali dengan skenario saat ini yang menggunakan Big Data. Beberapa model yang akan kita pelajari adalah ANNOY, FAISS, dan HNSW.
Sebelum membahas tentang ANN diatas, kita perlu tahu tentang perhitungan (metrics) yang digunakan untuk mengukur jarak antar data. Beberapa metrics yang digunakan adalah Euclidean Distance, Inner Product, Cosine Similarity, dan Angular Distance.
Dalam sistem Approximate Nearest Neighbor (ANN) seperti Annoy misalnya, pilihan metrik jarak yang tersedia umumnya terbatas pada Euclidean dan Angular. Hal ini bukan tanpa alasan. Kedua metrik tersebut dianggap paling relevan untuk berbagai kasus pencarian kedekatan vektor berdimensi tinggi. Euclidean distance (L2 distance) dipilih karena ia mewakili jarak geometris absolut di ruang vektor, sehingga cocok ketika besarnya nilai (magnitudo) dari data memang penting. Sementara itu, Angular distance didasarkan pada cosine similarity yang hanya mempertimbangkan arah vektor, sehingga lebih sesuai ketika yang ingin dibandingkan adalah pola atau orientasi, bukan besarnya nilai.
Metrik lain contoh seperti Manhattan (L1 distance) atau Mahalanobis distance jarang digunakan dalam ANN library seperti Annoy karena dua alasan utama. Pertama, dari sisi komputasi, perhitungan Euclidean dan Angular relatif sederhana serta efisien di ruang dimensi tinggi, sedangkan Manhattan atau Mahalanobis akan menambah beban perhitungan. Kedua, dalam banyak aplikasi similarity search—misalnya pada teks, gambar, atau embedding dari model pembelajaran mesin—informasi yang paling bermakna biasanya ada pada jarak Euclidean dan sudut (cosine/Angular), sehingga keduanya sudah cukup mewakili kebutuhan umum. Dengan demikian, Annoy berfokus hanya pada dua metrik ini untuk menjaga performa dan kesesuaian dengan kasus nyata yang paling sering ditemui.
Library lain seperti Faiss (buatan Meta/FB) dan HNSW (Hierarchical Navigable Small World) menyediakan lebih banyak fleksibilitas dalam pemilihan metrik. Selain Euclidean, keduanya mendukung inner product sebagai ukuran kesamaan, yang berguna pada kasus maximum inner product search (MIPS) seperti rekomendasi produk atau sistem retrieval berbasis embedding. Beberapa implementasi bahkan memungkinkan penggunaan variasi metrik lain, meskipun dengan konsekuensi beban komputasi lebih tinggi. Dengan kata lain, Annoy mengutamakan kesederhanaan dan efisiensi dengan dua metrik paling umum, sementara Faiss dan HNSW memberikan pilihan lebih luas sesuai kebutuhan spesifik aplikasi.
Annoy
Random Projection Trees
Euclidean, Angular
Sangat ringan, mudah digunakan
FAISS
Inverted file + clustering, GPU optimized
L2, Inner Product (Cosine via normalisasi)
Cocok untuk dataset besar dan GPU
HNSW
Small World Graph (navigable)
L2, Inner Product, Cosine
Lebih cepat & akurat di CPU, fleksibel
Euclidean Distance (L2 Distance)
Mengukur jarak lurus antara dua titik dalam ruang Euclidean.
Contoh:
Inner Product
Mengukur kedekatan arah dengan mengalikan dan menjumlahkan komponen vektor.
Contoh:
Cosine Similarity
dengan:
Contoh:
Angular Distance
Mengubah cosine similarity menjadi ukuran jarak berdasarkan sudut.
Dinormalisasi ke [0,1]:
Contoh
Untuk interpretasi:
Euclidean → selalu positif, menunjukkan jarak fisik absolut di bidang.
Inner Product → bisa positif/negatif. Negatif artinya arah vektor berlawanan.
Cosine Similarity → antara [−1, 1]. Nilai mendekati 1 → searah, 0 → tegak lurus, -1 → berlawanan arah.
Angular Distance → hasil transformasi cosine ke skala sudut [0,1].
0 → arah identik (0°).
1 → arah berlawanan total (180°).
dengan melihat tabel diatas, kita dapat simpulkan jika:
Skenario 1 (hampir searah) → cosine mendekati 1, angular kecil.
Skenario 2 (berlawanan arah) → cosine = -1, angular = 1.
Last updated