Metrik jarak dan kutukan dimensi

Beberapa tempat saya membaca catatan bahwa jika Anda memiliki banyak parameter dan Anda mencoba menemukan "metrik kesamaan" antara vektor-vektor ini, Anda mungkin memiliki "kutukan dimensioality". Saya percaya itu berarti sebagian besar skor kesamaan akan sama dan tidak memberi Anda informasi yang berguna. Dengan kata lain, hampir semua vektor mitra akan memiliki skor jarak menengah yang tidak berguna untuk kategorisasi atau pengelompokan dll.$(x_1, x_2, \ldots, x_n)$

Apakah Anda tahu di mana saya dapat mempelajari lebih lanjut tentang itu?

Apakah ada metrik yang kurang menderita akibat efek ini?

Beberapa pengamatan klasik tentang jarak dalam data dimensi tinggi:

• K. Beyer, J. Goldstein, R. Ramakrishnan, dan U. Shaft, ICDT 1999: "Kapan Tetangga Terdekat Berarti Berarti?"
• CC Aggarwal, A. Hinneburg, dan DA Keim, ICDT 2001: "Tentang Perilaku yang mengejutkan dari Metrik Jarak dalam Ruang Dimensi Tinggi"

Beberapa penelitian terbaru tentang hal ini, yang melibatkan tetangga-tetangga terdekat dan hubness:

• ME Houle, H.-P. Kriegel, P. Kröger, E. Schubert dan A. Zimek, SSDBM 2010: "Bisakah Jarak Bersama-Tetangga Mengalahkan Kutukan Dimensi?"
• T. Bernecker, ME Houle, H.-P. Kriegel, P. Kröger, M. Renz, E. Schubert dan A. Zimek, SSTD 2011: "Kualitas Peringkat Kesamaan dalam Time Series"
• N. Tomašev, M. Radovanović, D. Mladenić, dan M. Ivanović. Adv. KDDM 2011: "Peran hubness dalam pengelompokan data dimensi tinggi"
• Tidak ingat yang lain, cari "Hubness", itu adalah pengamatan dimensi tinggi mereka

Ini menarik, karena mereka menunjukkan beberapa kesalahpahaman populer tentang kutukan dimensi. Pada dasarnya mereka menunjukkan bahwa hasil teoritis - yang menganggap data sebagai iid - mungkin tidak berlaku untuk data yang memiliki lebih dari satu distribusi. Kutukan itu mengarah pada masalah numerik, dan hilangnya diskriminasi dalam satu distribusi tunggal, sementara itu bisa membuatnya lebih mudah untuk membedakan dua distribusi yang terpisah dengan baik.

Beberapa di antaranya harus agak jelas. Katakanlah Anda memiliki objek yang iid di setiap dimensi dan set objek lain yang iid di setiap dimensi. Perbedaan antara objek dari dua set yang berbeda akan selalu besaran lebih besar dari jarak dalam satu set, dan masalah bahkan akan mendapatkan lebih mudah dengan meningkatnya dimensi .$A_i\sim \mathcal{N}(0;1)$$B_i\sim \mathcal{N}(100;1)$

Saya merekomendasikan membaca karya ini oleh Houle et al., Terutama karena itu menunjukkan bahwa dengan mengklaim "data ini adalah dimensi tinggi, dan karena kutukan dimensi itu tidak dapat dianalisis" Anda mungkin membuat hal-hal yang agak terlalu mudah. Masih itu adalah garis yang digunakan di semua tempat. "Algoritma kami hanya berfungsi hanya untuk data dimensi rendah, karena kutukan dimensi." "Indeks kami hanya berfungsi hingga 10 dimensi, karena kutukan dimensi." Yadda yadda yadda. Banyak dari pernyataan ini tampaknya hanya menunjukkan bahwa penulis tersebut belum memahami apa yang terjadi pada dimensi tinggi dalam data dan algoritme mereka (atau membutuhkan alasan). Houle et al. tidak sepenuhnya memecahkan teka-teki (belum? ini cukup baru), tetapi mereka setidaknya mempertimbangkan kembali banyak pernyataan populer.

Lagi pula, jika dimensi tinggi adalah masalah sebesar ini, bagaimana bisa dalam penambangan teks orang dengan senang hati menggunakan dimensi pada urutan 10.000-100.000, sedangkan di domain lain orang menyerah hanya pada 10 dimensi?!?

Adapun bagian kedua dari pertanyaan Anda: kesamaan cosinus tampaknya kurang menderita dari dimensi . Terlepas dari itu, selama Anda ingin membedakan distribusi yang berbeda, kontrol presisi numerik dan jangan bergantung pada ambang pilihan yang dipilih sendiri (karena Anda mungkin perlu memberi mereka dengan banyak digit signifikan), -Norms klasik masih harus baik-baik saja.$L_p$

Namun, Cosine juga dipengaruhi oleh kutukan dimensi , seperti yang dibahas dalam:

• M. Radovanović, A. Nanopoulos, dan M. Ivanović, SIGIR 2010. "Tentang keberadaan hasil keras kepala dalam model ruang vektor."

• Aggarwal CC, Hinneburg A., Keim, DA (2001), "Tentang Perilaku Metrik Jarak yang Mengejutkan dalam Ruang Dimensi Tinggi"
• Beyer K., Goldstein J., Ramakrishnan R., Shaft U. (1999), “Kapan Tetangga Terdekat Berarti Penuh?”, Prosedur Konferensi ICDE.

Juga:

• Robert J. Durrant, Ata Kabán: Kapan 'tetangga terdekat' bermakna: Sebuah teorema dan implikasi sebaliknya. J. Complexity 25 (4): 385-397 (2009)

• Ata Kabán: Pada kesadaran konsentrasi jarak dari teknik reduksi data tertentu. Pengenalan Pola 44 (2): 265-277 (2011)

• Ata Kabán: Deteksi non-parametrik dari jarak yang tidak berarti dalam data dimensi tinggi. Statistik dan Komputasi 22 (2): 375-385 (2012)