Aplikasi pencincangan sensitif lokaliti dalam anggaran carian jiran terdekat

Locale Sensitive Hashing (LSH) ialah kaedah untuk anggaran carian jiran terdekat, terutamanya sesuai untuk data dalam ruang dimensi tinggi. Dalam banyak aplikasi dunia nyata, seperti data teks dan imej, dimensi titik data boleh menjadi sangat tinggi. Dalam ruang dimensi tinggi, kaedah pengukuran jarak tradisional seperti jarak Euclidean tidak lagi berkesan, dan kaedah carian linear tradisional tidak cekap. Oleh itu, kami memerlukan beberapa algoritma yang cekap untuk menyelesaikan masalah ini. Idea asas LSH adalah untuk memetakan titik data yang serupa kepada baldi cincang yang serupa melalui fungsi cincang. Dengan cara ini, kami hanya perlu mencari dalam baldi cincang yang serupa dan bukannya merentasi keseluruhan set data, sekali gus meningkatkan kecekapan carian. Teras algoritma LSH adalah untuk mereka bentuk fungsi cincang yang sesuai. Fungsi cincang harus mempunyai dua ciri: pertama, titik data yang serupa mempunyai kebarangkalian tinggi untuk dipetakan ke baldi cincang yang serupa, iaitu, ia mempunyai kepekaan setempat kedua, titik data yang tidak serupa

pencincangan sensitif tempatan ( Idea asas bagi LSH adalah untuk memetakan titik data dalam ruang dimensi tinggi ke ruang dimensi rendah melalui fungsi cincang, supaya dapat melakukan anggaran carian jiran terdekat dalam ruang dimensi rendah. Dengan memperkenalkan teknik rawak, LSH boleh meningkatkan kebarangkalian bahawa titik data yang serupa dipetakan ke baldi yang sama, dengan itu mengurangkan ruang carian. Kelebihan LSH ialah ia sangat mengurangkan ruang carian sambil memastikan ketepatan pertanyaan tertentu, dengan itu meningkatkan kecekapan pertanyaan.

LSH digunakan secara meluas, seperti carian imej yang serupa dalam enjin carian, pengesyoran lagu yang serupa dalam sistem pengesyoran muzik dan pengesyoran pengguna yang serupa dalam rangkaian sosial. Berikut akan memperkenalkan prinsip dan proses pelaksanaan LSH melalui contoh mudah.

Andaikan kita mempunyai set data dan setiap titik data ialah vektor 100 dimensi. Untuk menanyakan set data ini untuk titik data yang paling serupa dengan vektor tertentu, kami berharap dapat menggunakan LSH (Locality Sensitive Hashing) untuk meningkatkan kecekapan pertanyaan. Memandangkan dimensi titik data adalah sangat tinggi, kaedah carian linear tradisional sangat memakan masa. LSH boleh memetakan titik data dalam ruang dimensi tinggi ke ruang dimensi rendah, mengekalkan titik data yang serupa secara relatifnya hampir dalam ruang dimensi rendah dan mengurangkan masa carian. Oleh itu, menggunakan LSH untuk pertanyaan boleh mempercepatkan carian dan meningkatkan kecekapan.

Pertama, kita perlu mentakrifkan fungsi cincang untuk memetakan vektor 100 dimensi ke dalam ruang dimensi rendah. Terdapat dua fungsi cincang yang biasa digunakan: cincang Euclidean dan cincang kosinus. Pencincangan Euclidean memetakan vektor ke domain nombor nyata dengan menjana beberapa hyperplanes secara rawak untuk memetakan titik data ke dalam baldi yang berbeza. Pencincangan kosinus memetakan vektor ke hipersfera berdimensi tinggi, dan juga memetakan titik data ke baldi yang berbeza dengan menjana beberapa hyperplanes secara rawak. Dalam contoh ini, kami menggunakan pencincangan Euclidean sebagai contoh.

Kita boleh menyatakan fungsi cincang sebagai h(x)=lfloorfrac{a^Tx+b}{w}flloor, dengan a ialah vektor rawak, b ialah pemalar rawak, dan w ialah lebar baldi , lflooerfloor bermaksud membulatkan ke bawah. Untuk mana-mana vektor x, ia akan dipetakan ke baldi, dan nombor baldi ialah h(x).

Sekarang kita perlu memilih beberapa vektor rawak a dan pemalar rawak b, serta lebar baldi w. Untuk memetakan titik data yang serupa ke baldi yang sama sebanyak mungkin, kita perlu memilih beberapa parameter supaya kebarangkalian titik data yang serupa dipetakan ke baldi yang sama adalah agak tinggi, dan titik data yang berbeza dipetakan ke baldi yang sama. Kebarangkalian agak kecil. Proses ini boleh dicapai dengan melaraskan parameter.

Secara umumnya, kita perlu memilih berbilang fungsi cincang dan memetakan setiap fungsi cincang sekali. Melalui pemetaan fungsi cincang ini, kita boleh mendapatkan berbilang baldi Kita boleh menganggap baldi ini sebagai set calon, dan kemudian melakukan anggaran carian jiran terdekat dalam set calon ini. Secara khusus, kita boleh mengira jarak antara vektor pertanyaan dan setiap titik data dalam set calon, dan kemudian pilih titik data dengan jarak terkecil sebagai anggaran jiran terdekat. Oleh kerana saiz set calon jauh lebih kecil daripada saiz keseluruhan set data, proses ini jauh lebih cekap daripada carian linear.

Perlu diingatkan bahawa LSH adalah kaedah anggaran dan ia tidak dapat menjamin ketepatan keputusan pertanyaan. Mungkin terdapat beberapa ralat dalam hasil pertanyaan LSH, dan saiz ralat berkaitan dengan pilihan fungsi cincang dan tetapan parameter. Oleh itu, dalam aplikasi praktikal, kita perlu memilih fungsi dan parameter cincang yang sesuai mengikut senario dan keperluan tertentu untuk mencapai keseimbangan antara ketepatan pertanyaan dan kecekapan pertanyaan.

Atas ialah kandungan terperinci Aplikasi pencincangan sensitif lokaliti dalam anggaran carian jiran terdekat. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!