Jarak Euclidean biasanya tidak baik untuk data yang jarang?

Saya telah melihat suatu tempat bahwa jarak klasik (seperti jarak Euclidean) menjadi sangat lemah ketika kita memiliki data multidimensi dan jarang. Mengapa? Apakah Anda memiliki contoh dua vektor data jarang di mana jarak Euclidean tidak berkinerja baik? Dalam hal ini kesamaan mana yang harus kita gunakan?

Berikut ini adalah contoh mainan sederhana yang menggambarkan efek dimensi dalam masalah diskriminasi misalnya masalah yang Anda hadapi ketika Anda ingin mengatakan apakah ada sesuatu yang diamati atau jika hanya efek acak yang diamati (masalah ini klasik dalam sains).

Heuristis. Masalah utama di sini adalah bahwa norma Euclidian memberikan kepentingan yang sama ke segala arah. Ini merupakan kurangnya sebelumnya, dan seperti yang Anda ketahui dalam dimensi tinggi tidak ada makan siang gratis (yaitu jika Anda tidak memiliki gagasan sebelumnya tentang apa yang Anda cari, maka tidak ada alasan mengapa beberapa kebisingan tidak akan terlihat seperti apa Anda sebenarnya. mencari, ini tautologi ...).

Saya akan mengatakan bahwa untuk masalah apa pun ada batasan informasi yang diperlukan untuk menemukan sesuatu selain kebisingan. Batas ini terkait dengan "ukuran" area yang Anda coba jelajahi terkait dengan level "noise" (yaitu level konten tidak informatif).

Dalam dimensi tinggi jika Anda memiliki sebelumnya bahwa sinyal Anda jarang, maka Anda dapat menghapus (yaitu menghukum) vektor non jarang dengan metrik yang mengisi ruang dengan vektor jarang atau dengan menggunakan teknik thresholding.

Kerangka Asumsikan bahwa adalah vektor gaussian dengan mean dan kovarians diagonal ( diketahui) dan Anda ingin menguji hipotesis sederhana$\xi$$\nu$$\sigma Id$$\sigma$

Uji statistik dengan energi . Intuisi yang pasti Anda miliki adalah ide yang baik untuk mengevaluasi norma / energi dari Anda pengamatan untuk membangun statistik uji. Sebenarnya Anda dapat membangun versi terpusat standar (di bawah ) dari energi . Itu membuat wilayah kritis di level dari formulir untuk$\mathcal{E}_n=\frac{1}{n}\sum_{i=1}^n\xi_i^2$$\xi$$H_0$$T_n$$T_n=\frac{\sum_i\xi_i^2-\sigma^2}{\sqrt{2n\sigma^4}}$$\alpha$$\{T_n\geq v_{1-\alpha}\}$$v_{1-\alpha}$

Kekuatan tes dan dimensi. Dalam hal ini, ini adalah latihan probabilitas yang mudah untuk menunjukkan rumus berikut untuk kekuatan pengujian Anda:

$$P_{\theta}(T\leq v_{1-\alpha})=P\left (Z\leq \frac{v_{1-\alpha}}{\sqrt{1+2\|\theta\|_2^2/(n\sigma^2)}}-\frac{\|\theta\|^2_2}{\sqrt{2n\sigma^4+2\sigma^2\|\theta\|_2^2/(n\sigma^2)}}\right )$$ dengan sejumlah variabel acak iid dengan dan .$Z$$n$$\mathbb{E}[Z]=0$$Var(Z)=1$

Ini berarti bahwa kekuatan pengujian Anda ditingkatkan oleh energi sinyal Anda dan berkurang sebesar . Secara praktis ini berarti bahwa ketika Anda meningkatkan ukuran dari masalah Anda jika tidak meningkatkan kekuatan sinyal pada saat yang sama maka Anda menambahkan informasi yang tidak informatif ke pengamatan Anda (atau Anda mengurangi proporsi informasi yang berguna dalam informasi tersebut) Anda punya): ini seperti menambahkan noise dan mengurangi kekuatan tes (yaitu lebih mungkin bahwa Anda akan mengatakan tidak ada yang diamati sementara sebenarnya ada sesuatu).$\|\theta\|^2_2$$n$$n$

Menuju tes dengan statistik ambang batas. Jika Anda tidak memiliki banyak energi dalam sinyal Anda tetapi jika Anda tahu transformasi linear yang dapat membantu Anda untuk memiliki energi ini terkonsentrasi di sebagian kecil dari sinyal Anda, maka Anda dapat membangun statistik uji yang hanya akan mengevaluasi energi untuk yang kecil. bagian dari sinyal Anda. Jika sebelumnya Anda tahu di mana itu terkonsentrasi (misalnya Anda tahu tidak ada frekuensi tinggi dalam sinyal Anda) maka Anda dapat memperoleh kekuatan dalam tes sebelumnya dengan diganti dengan angka kecil dan hampir sama ... Jika Anda tidak mengetahuinya terlebih dahulu, Anda harus memperkirakannya, ini mengarah ke uji ambang batas yang sudah dikenal luas.$n$$\|\theta\|^2_2$

Perhatikan bahwa argumen ini persis pada akar banyak makalah seperti

• A Antoniadis, F Abramovich, T Sapatinas, dan B Vidakovic. Metode wavelet untuk pengujian dalam analisis fungsional model varians. International Journal on Wavelets dan aplikasinya, 93: 1007-1021, 2004.
• MV Burnashef dan Begmatov. Pada masalah deteksi sinyal yang mengarah ke distribusi stabil. Teori probabilitas dan penerapannya, 35 (3): 556–560, 1990.
• Y. Baraud. Laju minimax non asimptotik dalam pengujian sinyal. Bernoulli, 8: 577–606, 2002.
• J Fan. Uji signifikansi berdasarkan ambang batas wavelet dan pemotongan neyman. JASA, 91: 674-688, 1996.
• J. Fan dan SK Lin. Uji signifikansi ketika data berupa kurva. JASA, 93: 1007-1021, 1998.
• V. Spokoiny. Pengujian hipotesis adaptif menggunakan wavelet. Annals of Statistics, 24 (6): 2477–2498, Desember 1996.

Saya percaya ini bukan sparsity, tetapi dimensionality tinggi biasanya terkait dengan data sparse. Tapi mungkin itu bahkan lebih buruk ketika datanya sangat jarang. Karena dengan demikian jarak dari dua objek kemungkinan akan menjadi rata-rata kuadrat dari panjangnya, atau

Persamaan ini berlaku sepele jika . Jika Anda meningkatkan dimensi dan sparseness sehingga cukup untuk hampir semua atribut, perbedaannya akan minimal.$\forall_i x_i=0 \vee y_i=0$

Lebih buruk lagi: jika Anda menormalkan vektor Anda memiliki panjang , maka jarak euclidean dari dua objek akan menjadi dengan probabilitas tinggi.$||x||=1$$\sqrt{2}$

Jadi sebagai aturan praktis, agar jarak Euclidean dapat digunakan (saya tidak mengklaim berguna atau bermakna) objek harus tidak nol dalam atribut. Maka harus ada sejumlah atribut yang masuk akal di manajadi perbedaan vektor menjadi berguna. Ini juga berlaku untuk perbedaan yang diinduksi norma lainnya. Karena dalam situasi di atas$3/4$$|y_i| \neq |x_i-y_i| \neq |x_i|$$|x-y| \rightarrow_p |x + y|$

Saya tidak berpikir ini adalah perilaku yang diinginkan untuk fungsi jarak menjadi sebagian besar independen dari perbedaan yang sebenarnya, atau perbedaan absolut yang menyatu dengan jumlah absolut!

Solusi umum adalah menggunakan jarak seperti jarak Cosine. Pada beberapa data mereka bekerja dengan sangat baik. Secara kasar, mereka hanya melihat atribut di mana kedua vektor tidak nol. Pendekatan yang menarik dibahas dalam referensi di bawah (mereka tidak menemukannya, tapi saya suka evaluasi eksperimental mereka tentang properti) adalah dengan menggunakan tetangga terdekat yang dibagikan. Jadi, bahkan ketika vektor x dan y tidak memiliki atribut yang sama, mereka mungkin memiliki beberapa tetangga yang sama. Menghitung jumlah objek yang menghubungkan dua objek terkait erat dengan jarak grafik.

Ada banyak diskusi tentang fungsi jarak di:

• Bisakah Jarak Bersama-Tetangga Mengalahkan Kutukan Dimensiitas?
  ME Houle, H.-P. Kriegel, P. Kröger, E. Schubert dan A. Zimek
  SSDBM 2010

dan jika Anda tidak suka artikel ilmiah, juga di Wikipedia: Kutukan Dimensiitas

Saya sarankan mulai dengan jarak Cosine , bukan Euclidean, untuk data apa pun dengan sebagian besar vektor hampir ortogonal, 0. Untuk melihat alasannya, lihat . Jika 0, ini berkurang menjadi : ukuran jarak yang payah, seperti ditunjukkan oleh Anony-Mousse.$x \cdot y \approx$
$|x - y|^2 = |x|^2 + |y|^2 - 2\ x \cdot y$
$x \cdot y \approx$$|x|^2 + |y|^2$

Jumlah jarak cosine untuk menggunakan, atau memproyeksikan data ke permukaan unit sphere, jadi semua= 1. Lalu metrik yang sangat berbeda dan biasanya lebih baik daripada Euclidean biasa. mungkin kecil, tetapi tidak ditutupi oleh noise .$x / |x|$$|x|$$|x - y|^2 = 2 - 2\ x \cdot y$
$x \cdot y$$|x|^2 + |y|^2$

$x \cdot y$ kebanyakan mendekati 0 untuk data yang jarang. Misalnya, jika masing-masing dan memiliki 100 suku bukan nol dan 900 nol, keduanya akan menjadi nol dalam hanya sekitar 10 suku (jika suku bukan nol tersebar secara acak).$x$$y$

Normalisasi / =mungkin lambat untuk data yang jarang; itu cepat di scikit-belajar .$x$$|x|$

Ringkasan: mulai dengan jarak cosinus, tetapi jangan berharap keajaiban pada data lama apa pun.
Metrik yang berhasil membutuhkan evaluasi, penyetelan, pengetahuan domain.

Bagian dari kutukan dimensi adalah data mulai menyebar jauh dari pusat. Ini berlaku untuk multivarian normal dan bahkan ketika komponennya IID (spherical normal). Tetapi jika Anda ingin benar-benar berbicara tentang jarak Euclidean bahkan dalam ruang dimensi rendah jika data memiliki struktur korelasi, jarak Euclidean bukan metrik yang sesuai. Jika kita mengira data multivarian normal dengan beberapa kovarian non-nol dan demi argumen misalkan matriks kovarians diketahui. Maka jarak Mahalanobis adalah ukuran jarak yang sesuai dan tidak sama dengan jarak Euclidean yang hanya akan berkurang jika matriks kovarians sebanding dengan matriks identitas.

Saya percaya ini terkait dengan kutukan dimensi / konsentrasi ukuran tetapi saya tidak bisa lagi menemukan diskusi yang memotivasi komentar ini. Saya percaya ada utas tentang metaoptimize tapi saya gagal Google itu ...

Untuk data teks, menormalkan vektor menggunakan TF-IDF dan kemudian menerapkan kesamaan cosinus mungkin akan menghasilkan hasil yang lebih baik daripada jarak euclidean karena dokumen panjang (dengan banyak kata) dapat berbagi topik yang sama sehingga sangat mirip dengan dokumen pendek berbagi jumlah umum yang tinggi kata-kata. Membuang norma vektor membantu dalam kasus khusus itu.

Ukuran aksiomatis dari sparsity adalah apa yang disebut dengan count, yang menghitung jumlah entri tidak nol dalam vektor. Dengan ukuran ini, vektor dan memiliki sparsity yang sama. Dan sama sekali tidak norma sama . Dan (sangat jarang) memiliki norma sama dengan , vektor yang sangat datar, tidak jarang. Dan sama sekali tidak dihitung sama .$\ell_0$$(1,0,0,0)$$(0,21,0,0)$$\ell_2$$(1,0,0,0)$$\ell_2$$\left(\frac{1}{4},\frac{1}{4},\frac{1}{4},\frac{1}{4}\right)$$\ell_0$

Fungsi ini, baik norma maupun quasinorm, tidak sederhana dan non-cembung. Bergantung pada domain, namanya legiun, misalnya: fungsi kardinalitas, ukuran angka, atau hanya kekikiran atau sparsitas. Ini sering dianggap sebagai tidak praktis untuk tujuan praktis karena penggunaannya menyebabkan masalah sulit NP .

Sementara jarak atau norma standar (seperti jarak Euclidian ) lebih dapat ditelusuri, salah satu masalah mereka adalah homogenitasnya:untuk . Ini dapat dilihat sebagai non-intuitif, karena produk skalar tidak mengubah proporsi entri nol dalam data ( adalah -homogeneneous).$\ell_2$$1$

Jadi dalam praktiknya, beberapa ressort ke kombinasi ( ), seperti laso, ridge, atau regularisasi jaring elastis. The norma (Manhattan atau jarak Taksi), atau avatar merapikan nya, ini sangat berguna. Karena karya-karya E. Candès dan yang lainnya, orang dapat menjelaskan Mengapa Adalah Perkiraan yang Baik untuk : Penjelasan Geometris . Yang lain telah membuat dalam , dengan harga masalah tidak konveks.$\ell_p(x)$$p \ge1$$\ell_1$$\ell_1$$\ell_0$$p < 1$$\ell_p(x)$

Jalan lain yang menarik adalah untuk kembali aksioma gagasan sparsity. Salah satu karya terkenal baru-baru ini adalah Membandingkan Ukuran dari Sparsity , oleh N. Hurley et al., Yang berhubungan dengan sparsitas distribusi. Dari enam aksioma (dengan nama-nama lucu seperti Robin Hood, Scaling, Rising Tide, Kloning, Bill Gates, dan Bayi), beberapa indeks sparsity muncul: satu berdasarkan pada indeks Gini, satu lagi pada rasio norma, terutama satu-over- dua rasio-normal, ditunjukkan di bawah:$\frac{\ell_1}{\ell_2}$

Meskipun tidak cembung, beberapa bukti konvergensi dan beberapa referensi historis dirinci dalam Euclid di Taxicab: Dekonvolusi Buta Jarang dengan Smoothed Regularisasi$\frac{\ell _1}{\ell_2}$ .

Makalah Tentang perilaku mengejutkan metrik jarak dalam ruang dimensi tinggi membahas perilaku metrik jarak dalam ruang dimensi tinggi.

Mereka mengambil norma dan mengusulkan norma manhattan sebagai yang paling efektif dalam ruang dimensi tinggi untuk tujuan pengelompokan. Mereka juga memperkenalkan norma fraksional mirip dengan norma tetapi dengan .$L_k$$L_1$ $L_f$$L_k$$f \in (0..1)$

Singkatnya, mereka menunjukkan bahwa untuk ruang dimensi tinggi menggunakan norma euclidean sebagai standar mungkin bukan ide yang baik; kita biasanya memiliki sedikit intuisi dalam ruang seperti itu, dan ledakan eksponensial karena jumlah dimensi sulit untuk diperhitungkan dengan jarak euclidean.