Mengapa jarak Euclidean bukan metrik yang baik dalam dimensi tinggi?

241

Saya membaca bahwa 'jarak Euclidean bukan jarak yang baik dalam dimensi tinggi'. Saya kira pernyataan ini ada hubungannya dengan kutukan dimensi, tetapi apa sebenarnya? Selain itu, apa itu 'dimensi tinggi'? Saya telah menerapkan pengelompokan hierarkis menggunakan jarak Euclidean dengan 100 fitur. Hingga berapa banyak fitur yang aman untuk menggunakan metrik ini?

teaLeef
sumber
5
Terkait erat: Jarak Euclidean biasanya tidak baik untuk data yang jarang? seperti yang ditunjukkan oleh facuq .
kardinal
5
Ini mungkin terlalu mendasar untuk Anda; Saya menulis serangkaian posting blog tentang masalah metrik Euclidean dalam dimensi yang lebih tinggi dan bagaimana hal itu memengaruhi pencarian ruang vektor untuk pencocokan terdekat. blogs.msdn.com/b/ericlippert/archive/tags/…
Eric Lippert
1
@ HorstGrünbusch lihat jawaban di bawah untuk beberapa referensi. Variasi jarak menjadi kecil dibandingkan dengan rata-rata. Jadi pada titik tertentu, Anda mengalami kesulitan memilih ambang, bobot, pemesanan; dan Anda bahkan bisa mendapatkan masalah ketepatan angka juga. Tetapi jika data Anda jarang, kemungkinan dimensi intrinsiknya jauh lebih rendah .
Anony-Mousse
3
"dimensi tinggi" tampaknya merupakan istilah yang menyesatkan - beberapa jawaban memperlakukan 9-12 sebagai "dimensi tinggi", tetapi di area lain dimensi tinggi akan berarti ribuan atau sejuta dimensi (misalnya, mengukur sudut antara vektor bag-of-words di mana setiap dimensi adalah frekuensi suatu kata dalam kamus), dan 100 dimensi akan disebut rendah, bukan tinggi.
Peteris
2
Pertanyaan ini benar-benar dapat dilakukan dengan beberapa konteks. Tidak bagus untuk apa?
Szabolcs

Jawaban:

244

Ringkasan hebat hasil non-intuitif dalam dimensi yang lebih tinggi berasal dari " Beberapa Hal Berguna untuk Diketahui tentang Pembelajaran Mesin " oleh Pedro Domingos di University of Washington:

[O] intuisi Anda, yang berasal dari dunia tiga dimensi, sering tidak berlaku dalam dunia berdimensi tinggi. Dalam dimensi tinggi, sebagian besar massa distribusi Gauss multivariat tidak mendekati rata-rata, tetapi dalam “cangkang” yang semakin jauh di sekitarnya; dan sebagian besar volume jeruk dimensi tinggi ada di kulit, bukan pulp. Jika sejumlah contoh konstan didistribusikan secara seragam dalam hypercube dimensi tinggi, di luar beberapa dimensi sebagian besar contoh lebih dekat ke permukaan hypercube daripada tetangga terdekat mereka. Dan jika kita memperkirakan hypersphere dengan menuliskannya dalam hypercube, dalam dimensi tinggi hampir semua volume hypercube berada di luar hypersphere. Ini adalah berita buruk untuk pembelajaran mesin, di mana bentuk-bentuk dari satu jenis sering kali diperkirakan oleh bentuk-bentuk yang lain.

Artikel ini juga penuh dengan banyak mutiara kebijaksanaan tambahan untuk pembelajaran mesin.

Aplikasi lain, di luar pembelajaran mesin, adalah pencarian tetangga terdekat: diberikan pengamatan yang menarik, temukan tetangga terdekatnya (dalam arti bahwa ini adalah titik dengan jarak terkecil dari titik permintaan). Tetapi dalam dimensi tinggi, sebuah fenomena aneh muncul: rasio antara titik terdekat dan terjauh mendekati 1, yaitu titik-titik tersebut pada dasarnya menjadi saling berjauhan satu sama lain. Fenomena ini dapat diamati untuk berbagai metrik jarak, tetapi lebih jelas untuk metrik Euclidean daripada, katakanlah, metrik jarak Manhattan. Premis pencarian tetangga terdekat adalah bahwa poin "lebih dekat" lebih relevan daripada poin "lebih jauh", tetapi jika semua titik pada dasarnya seragam satu sama lain, perbedaannya tidak berarti.

Dari Charu C. Aggarwal, Alexander Hinneburg, Daniel A. Keim, " Tentang Perilaku Metrik Jarak yang Mengejutkan di Ruang Dimensi Tinggi ":

Telah diperdebatkan dalam [Kevin Beyer, Jonathan Goldstein, Raghu Ramakrishnan, Uri Shaft, " Kapan 'Tetangga Terdekat' Berarti? "] Bahwa berdasarkan asumsi masuk akal tertentu pada distribusi data, rasio jarak dari tetangga terdekat dan terjauh. untuk target yang diberikan dalam ruang dimensi tinggi hampir 1 untuk berbagai distribusi data dan fungsi jarak. Dalam kasus seperti itu, masalah tetangga terdekat menjadi tidak jelas, karena kontras antara jarak ke titik data yang berbeda tidak ada. Dalam kasus seperti itu, bahkan konsep kedekatan mungkin tidak bermakna dari perspektif kualitatif: masalah yang bahkan lebih mendasar daripada penurunan kinerja algoritma dimensi tinggi.

... Banyak struktur pengindeksan dimensi tinggi dan algoritma menggunakan metrik jarak uclidean [E] sebagai perpanjangan alami dari penggunaan tradisionalnya dalam aplikasi spasial dua atau tiga dimensi. ... Dalam makalah ini kami memberikan beberapa hasil teoritis dan eksperimental yang mengejutkan dalam menganalisis ketergantungan norma pada nilai . Lebih khusus, kami menunjukkan bahwa kontras relatif jarak ke titik kueri sangat bergantung pada metrik digunakan. Ini memberikan bukti yang cukup besar bahwa norma memburuk lebih cepat dalam peningkatan dimensi untuk nilai lebih tinggi . Jadi, untuk masalah tertentu dengan nilai tetap (tinggi) untuk dimensi k L k L k k d k L 1 L 2LkkLkLkkd, mungkin lebih baik menggunakan nilai lebih rendah . Ini berarti bahwa metrik jarak (metrik jarak Manhattan) adalah yang paling disukai untuk aplikasi dimensi tinggi, diikuti oleh metrik Euclidean ( ). ...kL1L2

Para penulis makalah "Perilaku Mengejutkan" kemudian mengusulkan penggunaan norma dengan . Mereka menghasilkan beberapa hasil yang menunjukkan bahwa "norma fraksional" ini menunjukkan sifat meningkatkan kontras antara titik terjauh dan terdekat. Ini mungkin berguna dalam beberapa konteks, namun ada peringatan: "norma fraksional" ini bukan metrik jarak yang tepat karena melanggar ketimpangan segitiga. Jika ketimpangan segitiga adalah kualitas penting untuk dimiliki dalam penelitian Anda, maka metrik fraksional tidak akan sangat berguna. k < 1Lkk<1

Sycorax
sumber
7
referensi ini luar biasa
Antoine
1
Membaca sekali lagi ... Cantik ...
Richard Hardy
113

Gagasan tentang jarak Euclidean, yang bekerja dengan baik di dunia dua dimensi dan tiga dimensi yang dipelajari oleh Euclid, memiliki beberapa sifat dalam dimensi yang lebih tinggi yang bertentangan dengan intuisi geometris kami (mungkin hanya saya ) yang juga merupakan ekstrapolasi dari dua dan tiga ukuran.

4×4(±2,±2)(±1,±1)(1,1)(2,1)(1,2)(1,0)(0,1)r2=21(±r2/2,±r2/2)(r2,0)(2,0,0)(1,0,0)(1,1)(1,1)

4×4×4(±2,±2,±2)8(±1,±1,±1)r3=31<1(r3,0,0)(2,0,0)

n42n(±1,±1,,±1)

(1)rn=n1
(rn,0,0,,0)(1)n=4rn=1n4n>9(1)rn>2(rn,0,0,,0)4 meskipun "sepenuhnya dikelilingi" oleh unit-radius hyperspheres yang "mengisi" hypercube (dalam arti mengemasnya). Bola pusat "menonjol" di luar hypercube dalam ruang dimensi tinggi. Saya menemukan ini sangat kontra-intuitif karena terjemahan mental saya tentang gagasan jarak Euclidean ke dimensi yang lebih tinggi, menggunakan intuisi geometris yang telah saya kembangkan dari ruang 2 dan 3 yang saya kenal, tidak menggambarkan realitas ruang dimensi tinggi.

n9

Dilip Sarwate
sumber
9
@ stackoverflowuser2010: Jika jawaban ini benar-benar tidak dapat dipahami, bagaimana Anda bisa tahu apakah itu menjawab atau mencoba menjawab pertanyaan awal? Pendekatan yang lebih konstruktif mungkin dengan meminta penjelasan tentang poin-poin yang Anda temukan tidak jelas daripada mengabaikan semuanya.
Scortchi
8
@ stackoverflowuser2010 Karena jawaban ini memiliki banyak upvotes, akan tampak bahwa banyak orang merasa bahwa keduanya cukup masuk akal dan merespons dengan cara yang dapat diterima terhadap pertanyaan. Mungkin Anda bisa mencoba kritik yang lebih konstruktif - bagaimana, khususnya menurut Anda jawaban ini akan ditingkatkan? Apa yang harus termasuk yang tidak?
Glen_b
1
@ Scortchi: Mungkin saya berharap terlalu banyak, tetapi jawaban yang jelas untuk pertanyaan ini yang dapat membantu komunitas akan menjadi sesuatu seperti "Jarak Euclidean bukan metrik yang baik karena <X>".
stackoverflowuser2010
7
@ stackoverflow2010 Anda tidak akan pernah melihat jawaban "baik" seperti itu karena <semuanya jauh lebih rumit daripada pernyataan if-then>. Jika Anda menginginkan jawaban yang mudah, kemungkinan besar salah. Sama seperti pembohong sialan Brexit, mereka pandai menawarkan jawaban mudah (salah, tapi mudah).
Anony-Mousse
42

Ini adalah masalah signal-to-noise . Jarak Euclidean, karena istilah kuadrat, sangat sensitif terhadap kebisingan; tetapi bahkan jarak Manhattan dan "fraksional" (non-metrik) menderita.

Saya menemukan studi dalam artikel ini sangat mencerahkan:

Zimek, A., Schubert, E. dan Kriegel, H.-P. (2012),
Sebuah survei tentang deteksi outlier tanpa pengawasan dalam data numerik dimensi tinggi.
Statistik Analisis Data Mining, 5: 363-387. doi: 10.1002 / sam.11161

Itu meninjau kembali pengamatan yang dibuat dalam misalnya pada Perilaku Mengejutkan Metrik Jarak di Ruang Dimensi Tinggi oleh Aggarwal, Hinneburg dan Keim yang disebutkan oleh @Pat. Tetapi juga menunjukkan bagaimana eksperimen sintetik menyesatkan dan bahwa pada kenyataannya data berdimensi tinggi dapat menjadi lebih mudah . Jika Anda memiliki banyak sinyal (redundan), dan dimensi baru menambah sedikit noise.

x,yx,y,x,y,x,y,x,y,...,x,y

Jadi pada akhirnya, itu masih tergantung pada data Anda. Jika Anda memiliki banyak atribut yang tidak berguna, jarak Euclidean akan menjadi tidak berguna. Jika Anda bisa dengan mudah menanamkan data Anda dalam ruang data dimensi rendah, maka jarak Euclidean juga harus bekerja di ruang dimensi penuh. Khususnya untuk data yang jarang , seperti vektor TF dari teks, ini tampaknya merupakan kasus bahwa data memiliki dimensi yang jauh lebih rendah daripada yang disarankan oleh model ruang vektor.

Beberapa orang percaya bahwa jarak cosinus lebih baik daripada Euclidean pada data dimensi tinggi. Saya tidak berpikir begitu: jarak cosinus dan jarak Euclidean terkait erat ; jadi kita harus mengharapkan mereka menderita masalah yang sama. Namun, data tekstual di mana cosine populer biasanya jarang , dan cosinus lebih cepat pada data yang jarang - jadi untuk data jarang, ada alasan bagus untuk menggunakan cosinus; dan karena data jarang, dimensi intrinsik jauh lebih kecil daripada dimensi ruang vektor.

Lihat juga balasan ini yang saya berikan pada pertanyaan sebelumnya: https://stats.stackexchange.com/a/29647/7828

Anony-Mousse
sumber
[1,1]nn
Dan apa kesimpulannya? Pada [-1; 1] ^ seseorang tidak boleh menggunakan Cosine karena itu tidak didefinisikan pada 0, rata-rata tidak memberi tahu kita apa pun tentang kutukan, dan data yang seragam tidak realistis.
Anony-Mousse
Saya belum mencobanya sekarang, tapi saya kira sudutnya terlihat mirip dengan data nyata. Fakta bahwa itu tidak didefinisikan pada 0 seharusnya tidak terlalu penting karena hanya satu titik. Kesimpulan saya mirip dengan Anda: Jarak cosine tidak cocok untuk ruang dimensi tinggi (meskipun mungkin ada domain jika masih berfungsi)
Martin Thoma
Skenario yang lebih realistis adalah poin pada unit sphere non-negatif. Dan ukuran bunga kemungkinan akan varians, bukan berarti.
Anony-Mousse
Untuk sampai ke unit sphere non-negatif, Anda hanya perlu menambahkan +1 dan membaginya dengan 2 ...
Martin Thoma
34

Tempat terbaik untuk memulai mungkin membaca Tentang Perilaku Mengejutkan Metrik Jarak dalam Ruang Dimensi Tinggi oleh Aggarwal, Hinneburg dan Keim. Ada tautan yang saat ini berfungsi di sini (pdf) , tetapi harus sangat dapat digunakan oleh Google jika rusak. Singkatnya, ketika jumlah dimensi bertambah, jarak euclidean relatif antara satu titik dalam satu set dan tetangga terdekatnya, dan antara titik itu dan tetangga terjauhnya, berubah dalam beberapa cara yang tidak jelas. Apakah ini akan mempengaruhi hasil Anda atau tidak, sangat tergantung pada apa yang ingin Anda capai dan seperti apa data Anda.

Menepuk
sumber
6

Jarak Euclidean sangat jarang jarak yang baik untuk dipilih dalam Pembelajaran Mesin dan ini menjadi lebih jelas dalam dimensi yang lebih tinggi. Ini karena sebagian besar waktu dalam Pembelajaran Mesin Anda tidak berurusan dengan Ruang Metrik Euclidean, tetapi Ruang Metrik Probabilistik dan oleh karena itu Anda harus menggunakan fungsi jarak teoretis probabilistik dan informasi, misalnya yang berbasis entropi.

Manusia menyukai ruang euclidean karena mudah dikonseptualisasikan, lebih jauh secara matematis karena sifat linearitas yang berarti kita dapat menerapkan aljabar linier. Jika kita mendefinisikan jarak dari segi, katakanlah Kullback-Leibler Divergence, maka lebih sulit untuk memvisualisasikan dan bekerja dengan matematis.

samthebest
sumber
2
Ini bisa bermasalah, karena KL Divergence bukan metrik. :-)
agarie
2
Jika seseorang membutuhkan simetri, Anda dapat menggunakan Mutual Information, yang seperti diisyaratkan, dapat didefinisikan dalam istilah KL.
samthebest
3

Sebagai analogi, bayangkan sebuah lingkaran yang berpusat pada titik asal. Poin didistribusikan secara merata. Misalkan titik yang dipilih secara acak adalah pada (x1, x2). Jarak Euclidean dari titik asal adalah ((x1) ^ 2 + (x2) ^ 2) ^ 0,5

Sekarang, bayangkan poin terdistribusi secara merata di sebuah bola. Titik yang sama (x1, x2) sekarang kemungkinan akan menjadi (x1, x2, x3). Karena, dalam distribusi genap, hanya beberapa titik yang memiliki salah satu koordinat sebagai nol, kita harus mengasumsikan bahwa [x3! = 0] untuk titik distribusi merata yang dipilih secara acak. Dengan demikian, titik acak kami kemungkinan besar (x1, x2, x3) dan tidak (x1, x2, 0).

Efeknya adalah: titik acak apa pun sekarang berada pada jarak ((x1) ^ 2 + (x2) ^ 2 + (x3) ^ 2) ^ 0,5 dari asal bola 3-D. Jarak ini lebih besar dari itu untuk titik acak di dekat titik asal lingkaran 2-D. Masalah ini semakin memburuk di dimensi yang lebih tinggi, itulah sebabnya kami memilih metrik selain dimensi Euclidean untuk bekerja dengan dimensi yang lebih tinggi.

EDIT: Ada pepatah yang saya ingat sekarang: "Sebagian besar massa oranye dimensi lebih tinggi ada di kulit, bukan bubur kertas", yang berarti bahwa dalam dimensi yang lebih tinggi titik-titik yang didistribusikan secara merata lebih "dekat" (jarak Euclidean) batas dari asal.

Catatan: Jarak Euclidean tidak terlalu buruk untuk masalah dunia nyata karena 'berkah ketidak-seragam', yang pada dasarnya menyatakan bahwa untuk data nyata, data Anda mungkin TIDAK akan didistribusikan secara merata di ruang dimensi yang lebih tinggi, tetapi akan menempati subset kecil dari ruang. Ini masuk akal secara intuitif: jika Anda mengukur 100 jumlah tentang manusia seperti tinggi, berat, dll, distribusi yang merata di atas ruang dimensi tidak masuk akal, misalnya seseorang dengan (tinggi = 65 inci, berat = 150 lbs, avg_calorie_intake = 4000) yang tidak mungkin di dunia nyata.

Abhishek Divekar
sumber
Jika ada pembaca di masa depan yang tertarik dengan kutipan "oranye / bubur kertas", atau "berkah tidak seragam", keduanya muncul dalam "Beberapa hal bermanfaat untuk dipelajari tentang pembelajaran mesin," yang terkait dengan jawaban saya tentang ini. benang.
Sycorax
1

Sisi lain dari pertanyaan ini adalah ini:

Dimensi yang sangat tinggi dalam masalah (pembelajaran mesin / statistik) adalah hasil dari fitur yang terlalu terbatas.

Artinya dimensi BUKAN independen (atau tidak berkorelasi), tetapi metrik Euclidean berasumsi (setidaknya) tidak berkorelasi dan karenanya tidak dapat menghasilkan hasil terbaik

Jadi untuk menjawab pertanyaan Anda, jumlah "dimensi tinggi" terkait dengan berapa banyak fitur yang saling tergantung atau berlebihan atau terlalu terbatas

Selain itu: Ini adalah teorema oleh Csiszar (et al.) Bahwa metrik Euclidean adalah kandidat "alami" untuk inferensi ketika fitur berupa bentuk tertentu

Nikos M.
sumber
3
Metrik Euclidean tidak "menganggap ... tidak berkorelasi". Jarak Euclidean bekerja paling buruk dalam dimensi tinggi dengan variabel tidak berkorelasi. Pertimbangkan kasus ekstrim: Anda memiliki sangat banyak dimensi yang semuanya berkorelasi sempurna, r = 1, sekarang data Anda sebenarnya uni-dimensional, & Euclidean distance berfungsi dengan baik dengan data uni-dimensional.
gung
Tidak saya tidak berpikir begitu, jarak Euclidean menurut definisi mengasumsikan data yang tidak terkorelasikan (kecuali jika menggunakan jarak Euclidean umum dengan matriks korelasi)
Nikos M.
Fitur dengan korelasi total (r = 1) adalah contoh sepele dan setara dengan "matriks korelasi sepele", tapi mungkin saya salah
Nikos M.
@ Gung Anda dapat mengartikan kerugian Euclidean sebagai kehilangan lintas entropi dari Gaussians dengan matriks varian unit isotropik unit tetap. Saya pikir ini adalah poin yang bagus, tetapi bisa dijelaskan dengan lebih baik.
Neil G
1
(0,0)(1,1)dE=j(x2jx1j)22X1=X212cor(X1,X2)=02
0

Makalah ini dapat membantu Anda juga "Peningkatan pengukuran kesamaan sqrt-cosinus" kunjungi https://journalofbigdata.springeropen.com/articles/10.1186/s40537-017-0083-6 Makalah ini menjelaskan mengapa jarak Euclidean bukan metrik yang baik dalam dimensi tinggi data dan apa pengganti terbaik untuk jarak Euclidean dalam data dimensi tinggi. Jarak Euclidean adalah norma L2 dan dengan mengurangi nilai k dalam norma Lk kita dapat mengatasi masalah jarak dalam data dimensi tinggi. Anda dapat menemukan referensi dalam makalah ini juga.

Sahar
sumber
2
Selamat datang di situs ini. Kami mencoba membangun repositori permanen untuk informasi statistik berkualitas tinggi dalam bentuk pertanyaan & jawaban. Karena itu, kami waspada terhadap jawaban tautan saja, karena tautannya. Bisakah Anda memposting kutipan lengkap & ringkasan informasi di tautan, kalau-kalau mati?
gung