1Evaluasi Model dan Metrik 2Training, Validation, dan Test Set3Cross-Validation 4Bias-Variance Tradeoff 5Learning Curve 6Class Imbalance & Resampling7Feature Selection 8Curse of Dimensionality

Lensa ML

Curse of Dimensionality

Q: Apakah curse of dimensionality memengaruhi deep learning?

Lebih kecil daripada yang terlihat dari ukuran input mentah. Neural network mempelajari representasi berdimensi rendahnya sendiri, dan data alami seperti gambar berada di dekat manifold berdimensi rendah, jadi gambar 150.000 pixel tidak butuh 10^150.000 sampel. Curse ini tetap muncul pada nearest-neighbor search atas embedding, dan itu salah satu alasan vector database memakai metode aproksimasi dan cosine similarity.

Q: Apakah memakai cosine similarity, bukan jarak Euclidean, menyelesaikan masalah ini?

Tidak sepenuhnya. Cosine similarity menghilangkan efek panjang vector, dan itu membantu untuk teks dan embedding, tetapi similarity antar-vector acak berdimensi tinggi tetap mengumpul rapat di sekitar nol. Aggarwal dkk. menemukan bahwa metrik dengan eksponen lebih kecil, seperti jarak Manhattan, mempertahankan kontras lebih baik daripada jarak Euclidean saat dimensi bertambah.

Langkah 1 dari 6: Ledakan Volume

Kejutan hypercube

Dimensi (d)2

Dimensi

Bola / kubus

78.54%

Volume bola

3.142

Di dimensi rendah, bola di dalam kubus mengisi sebagian besar kubus, dan hanya sedikit volume yang ada di sudut.

Geser slider dimensi dari 1 ke 20 dan lihat bola menyusut di dalam kubusnya. Volume bola satuan adalah π^(d/2) / Γ(d/2 + 1), sedangkan kubus dengan sisi 2 punya volume 2^d, jadi rasionya turun lebih cepat daripada eksponensial. Pada d = 10 bola hanya memuat 0,25% kubus, dan pada d = 20 sekitar 0,0000025%. Geometri yang sama membuat distribusi Gaussian berdimensi tinggi berperilaku aneh: hampir tidak ada sampel yang jatuh dekat rata-rata, dan sebagian besar berada di cangkang tipis yang berjarak sekitar √d dari rata-rata.

Langkah 2 dari 6: Konsentrasi Jarak

Semuanya berjauhan

Dimensi (d)2

Dimensi

Jarak min

0.02

Jarak maks

1.09

Maks / min

59.36

Jarak masih menyebar: titik dekat dan titik jauh mudah dibedakan.

Geser dimensi dari 2 ke 100 dan perhatikan kartu Maks / min. Untuk 30 titik acak ini, nilainya turun dari sekitar 59 pada d = 2 menjadi 3 pada d = 10 dan 1,4 pada d = 100. Untuk titik yang tersebar merata di kubus satuan, jarak tipikal tumbuh seperti √(d/6), tetapi sebarannya kira-kira tetap, sehingga selisih relatif antara dekat dan jauh menyusut mendekati nol. Beyer dkk. membuktikan pada 1999 bahwa, dalam kondisi yang luas, rasio jarak tetangga terjauh terhadap tetangga terdekat mendekati 1 saat d membesar.

Langkah 3 dari 6: Data Jadi Sparse

Kebutuhan data naik secara eksponensial

Dimensi (d)1

Dimensi

Data dibutuhkan

Tersedia

1,000

Kepadatan

100.00

Dengan 1000 titik, rata-rata ada minimal satu titik per sel, jadi ruangnya tertutup.

Geser dimensi dari 1 ke 10. Setiap sumbu dibagi menjadi 10 bin, jadi untuk menutup ruang pada resolusi itu kamu butuh 10^d sel dan minimal titik sebanyak itu. Dengan 1.000 titik, sel-selnya terisi sampai d = 3, dan pada d = 10 lebih dari 99,9999% sel kosong. Data sungguhan lolos dari kondisi terburuk ini karena sebarannya tidak merata. Gambar, teks, dan pembacaan sensor berada di dekat permukaan yang dimensinya jauh lebih rendah. Ini disebut manifold hypothesis, dan inilah sebabnya model bisa mempelajari digit 784 pixel dari 60.000 contoh.

Langkah 4 dari 6: k-NN di Dimensi Tinggi

Neighborhood membengkak

Dimensi (d)2

Dimensi

Radius (k=5)

0.224

Ruang tercakup

5.0%

Neighborhood kecil sudah memuat 5 titik, jadi tetangga k-NN benar-benar lokal.

Geser dimensi dari 2 ke 30. Radius di sini adalah panjang sisi sub-kubus yang memuat 5 dari 100 titik seragam, r = (5/100)^(1/d). Kartu Ruang tercakup tetap 5% di setiap d: neighborhood selalu memuat porsi data yang sama, tetapi sisinya harus meregang dari 0,22 tiap sumbu pada d = 2 menjadi 0,74 pada d = 10 dan 0,91 pada d = 30. Tetangga sejauh itu tidak lagi mirip dengan query, sehingga prediksi k-NN bergeser ke rata-rata global.

Langkah 5 dari 6: Feature yang Tidak Relevan

Noise menenggelamkan sinyal

Feature tidak relevan0

Relevan

Tak relevan

Total

Akurasi

98%

Dengan hanya dua feature yang relevan, kedua kelas terpisah dengan bersih.

Geser slider feature tidak relevan dari 0 ke 20. Dua feature membawa sinyal kelas, dan setiap tambahan hanyalah noise murni. Pada jarak Euclidean, setiap feature noise menambah jumlah yang kira-kira sama ke semua jarak antarpasangan, jadi setelah beberapa feature seperti itu, dua koordinat yang informatif hanya menyumbang sebagian kecil dari totalnya. Model berbasis jarak seperti k-NN, k-means, dan SVM dengan RBF kernel paling terdampak. Tree ensemble dan model linear dengan L1 regularization lebih tahan, karena keduanya bisa belajar mengabaikan satu feature sepenuhnya.

Langkah 6 dari 6: Strategi Mitigasi

Mengurangi dimensi

Dimensi target (setelah reduksi)20

d asli

d target

Akurasi awal

60%

Akurasi akhir

60%

Dimensinya masih terlalu banyak: sebagian besar hanya menambah noise tanpa informasi yang berguna.

Geser dimensi target dari 20 turun ke 2. Akurasi memuncak di rentang yang diarsir dan turun di kedua sisinya: terlalu banyak dimensi menyimpan noise, terlalu sedikit membuang sinyal. Labelnya menandai tiga keluarga solusi. PCA menyimpan arah dengan variance terbesar, feature selection menyimpan sebagian kolom asli, dan autoencoder mempelajari kompresi non-linear. Dimensi target biasanya dipilih dengan cross-validation pada seluruh pipeline, dan reduksinya di-fit di dalam tiap fold supaya baris validasi tetap tidak terlihat.

Apa itu curse of dimensionality?

Curse of dimensionality adalah kumpulan masalah yang muncul ketika data punya banyak feature: volume ruang tumbuh secara eksponensial seiring jumlah dimensi, sehingga sampel yang jumlahnya tetap menjadi jarang, dan jarak antartitik menjadi hampir sama. Istilah ini diciptakan oleh Richard Bellman dalam konteks dynamic programming.

Masalah ini muncul di mana pun model mengandalkan jarak atau kepadatan lokal. Kinerja k-nearest neighbors, k-means clustering, kernel method, dan detektor anomali menurun ketika banyak feature hanya membawa sedikit sinyal. Studi ekspresi gen dengan 20.000 gen dan beberapa ratus pasien, data rekomendasi dengan jutaan kolom sparse, dan pixel gambar mentah semuanya menghadapi masalah ini. Cara standar mengatasinya adalah feature selection, dimensionality reduction seperti PCA, regularization, dan mengumpulkan lebih banyak data.

Ide utama

Volume tumbuh secara eksponensial seiring dimensi, jadi sampel yang jumlahnya tetap menjadi jarang.
Di dimensi tinggi, hampir seluruh volume kubus ada di sudut-sudutnya.
Jarak antarpasangan terkonsentrasi, jadi tetangga terdekat dan terjauh berjarak hampir sama.
Neighborhood k-NN harus membentang di sebagian besar tiap sumbu untuk memuat beberapa titik saja.
Feature yang tidak relevan mengencerkan jarak dan paling merugikan model berbasis jarak.
Feature selection, dimensionality reduction, dan regularization adalah solusi utamanya.

Pertanyaan umum

Apakah curse of dimensionality memengaruhi deep learning?

Lebih kecil daripada yang terlihat dari ukuran input mentah. Neural network mempelajari representasi berdimensi rendahnya sendiri, dan data alami seperti gambar berada di dekat manifold berdimensi rendah, jadi gambar 150.000 pixel tidak butuh 10^150.000 sampel. Curse ini tetap muncul pada nearest-neighbor search atas embedding, dan itu salah satu alasan vector database memakai metode aproksimasi dan cosine similarity.

Berapa sampel yang dibutuhkan per feature?

Tidak ada aturan universal. Untuk model linear, patokan yang umum adalah minimal 10 sampai 20 sampel per feature, sedangkan metode nonparametrik seperti k-NN butuh jauh lebih banyak karena kebutuhan datanya tumbuh secara eksponensial seiring dimensi. Regularization dan feature selection menurunkan kebutuhan itu, dan cross-validation menunjukkan apakah sebuah dataset sudah cukup.

Apakah ada blessing of dimensionality?

Ada. Di dimensi yang lebih banyak, kelas lebih sering bisa dipisahkan secara linear, dan itulah ide di balik kernel method. Concentration of measure juga membuat random projection bisa diandalkan: lema Johnson-Lindenstrauss menyatakan titik-titik bisa diproyeksikan ke sekitar log(n)/ε² dimensi sambil mempertahankan jarak antarpasangan dalam faktor 1 ± ε.

Apakah memakai cosine similarity, bukan jarak Euclidean, menyelesaikan masalah ini?

Tidak sepenuhnya. Cosine similarity menghilangkan efek panjang vector, dan itu membantu untuk teks dan embedding, tetapi similarity antar-vector acak berdimensi tinggi tetap mengumpul rapat di sekitar nol. Aggarwal dkk. menemukan bahwa metrik dengan eksponen lebih kecil, seperti jarak Manhattan, mempertahankan kontras lebih baik daripada jarak Euclidean saat dimensi bertambah.

Penjelasan terkait

K-Nearest Neighbors · Klasifikasi berdasarkan kedekatan dan metrik jarak
Dimensionality Reduction · PCA dan t-SNE untuk melihat data berdimensi tinggi
Feature Selection · Metode filter, wrapper, dan embedded untuk memilih feature
Norm dan Metrik Jarak · L1, L2, cosine similarity: cara mengukur kedekatan di ruang vector
Regularization · Dropout, L1, dan L2 agar model tetap jujur
K-Means Clustering · Pengelompokan unsupervised berdasarkan jarak ke centroid

Referensi

Terakhir diperbarui 2 November 2026