Model ruang vektor cosinus tf-idf untuk menemukan dokumen serupa

Memiliki kumpulan lebih dari jutaan dokumen

Untuk dokumen yang diberikan ingin mencari dokumen serupa menggunakan cosinus seperti dalam model ruang vektor

$d_1 \cdot d_2 / ( ||d_1|| ||d_2|| )$

Semua tf telah dinormalisasi menggunakan frekuensi augmented, untuk mencegah bias terhadap dokumen yang lebih panjang seperti dalam tf-idf ini :

$tf(t,d)=0.5+0.5\frac{f(t,d)}{\mathrm{max}\{f(t,d): t\in d\}}$

Telah menghitung sebelumnya semua Memiliki nilai-nilai untuk penyebut yang sudah dihitung sebelumnya. Jadi untuk tertentu perlu mencetak lebih dari 1 juta Memiliki ambang 0,6 cosinus untuk kesamaan $||d||$

$d1$ $d2$

Saya dapat mengamati bahwa untuk yang diberikanada kisaran yang cukup sempituntuk cosinus 0.6 Misalnya dalam satu pencarian yang mirip untuk cosinus 0.6 dan adari 7.7631 laluberkisar dari 7,0867 hingga 8,8339 Di mana di luar ambang batas cosinus 0,6 berkisar dari 0,7223 hingga 89,3395 Ini dengan standar tf normalisasi dokumen. Ini melihat BANYAK yang tidak memiliki peluang menjadi pertandingan cosinus 0,6 $||d_1||$ $||d_2||$ $\ge$
$\ge$ $||d_1||$ $||d_2||$
$||d_2||$

$||d_2||$

Akhirnya pertanyaan:
Untuk memberidan cosine dari> = 0,6 cara menentukan rentangyang punya kesempatan? Yangdapatkah saya menghilangkan dengan aman? $||d_1||$ $||d_2||$
$||d_2||$

Saya juga tahu jumlah istilah dalam dan jika ada rentang hitungan istilah. $d_1$ $d_2$

Melalui eksperimendan tampaknya aman tetapi mudah-mudahan ada kisaran yang terbukti aman
$||d2|| > .8 ||d1||$ $||d2|| < ||d1|| / .8$

Dibuat beberapa test case dengan beberapa istilah yang sangat unik, beberapa tidak begitu unik, dan beberapa umum. Cukup yakin Anda dapat mengambil istilah yang paling unik dan meningkatkan frekuensi itu di bandingkan. Pembilang akan (titik produk) naik dan begitu juga || membandingkan || dan akan mendapatkan kosinus yang sangat dekat dengan 1.

Agak terkait dan BUKAN pertanyaan.
Saya juga menggunakan tf-idf untuk mengelompokkan dokumen ke dalam grup. Basis pelanggan tempat saya menjual digunakan untuk mendekati grup dup. Di sana saya mengambil pendekatan terkait di saya terlihat sebagai jumlah term terkecil dan mengevaluasinya terhadap term term hingga 3x. Jadi hitungan istilah 10 terlihat pada 10 hingga 30 (4-9 sudah memiliki kesempatan mereka di 10). Di sini saya dapat melewatkan satu yang dijemput di yang lain. Saya selesai 10% dan rasio terbesar adalah 1,8.

Silakan identifikasi kekurangan dalam analisis ini
Seperti yang ditunjukkan oleh AN6U5, ada kelemahan dalam analisis
ini. Tidak lagi merupakan kosinus jika dokumen dinormalisasi berdasarkan bobot.
Dan seperti yang ditunjukkan oleh Mathew juga tidak dapat menyimpulkan d1⋅d2≤d1⋅d1.
Saya masih berharap ada sesuatu yang membuat saya terikat tetapi orang-orang yang tampaknya tahu hal ini mengatakan tidak,
saya tidak ingin mengubah pertanyaan, jadi abaikan saja ini,
saya akan melakukan beberapa analisis dan mungkin mengirim pertanyaan terpisah pada normalisasi dokumen
Untuk tujuan dari pertanyaan ini menganggap dokumen dinormalisasi pada baku tf
Maaf tapi saya hanya tidak baik dengan markup apa yang pernah digunakan untuk membuat persamaan
Jadi dalam notasi saya
|| d1 || = sqrt (jumlah (w1 x w1))
d1 dot d2 = jumlah (w1 X w2)
Diasumsikan d1 adalah dokumen yang lebih pendek.
Yang terbaik d1 dot d2 yang dapat dicapai adalah d1 dot d1
Jika d1 menikah 100 paul 20
Dan d2 menikah 100 paul 20 peter 1
Normalisasi
d1 menikah 1 paul 1/5
d2 menikah 1 paul 1/5 peter 1/100
Jelas menikah dan paul memiliki idf yang sama di kedua dokumen
. Kemungkinan terbaik d1 dot d2 adalah d1 dot d1
Pencocokan maksimum yang mungkin untuk d1 adalah d1
cos = d1 dot d1 / || d1 || || d2 ||
persegi kedua sisi
cos X cos = (d1 dot d1) X (d1 dot d1) / ((d1 dot d1) X (d2 dot d2)) cos X cos = (d1 dot d1) / (d2 dot d2)
ambil kotak akar dari kedua sisi
cos = || d1 || / || d2 ||
adalah || d2 || tidak dibatasi oleh cos?
Jika saya hanya menggunakan || d2 || > = cos || d1 || dan || d2 || <= || d1 || / cos saya mendapatkan kecepatan komputasi yang saya butuhkan

text-mining similarity paparazzo
sumber

Argumen Anda yang diakhiri dengan terikat ditentukan oleh tidak berfungsi karena "Titik d1 terbaik yang dapat dicapai adalah titik d1 d1 "salah Sementara , ini bukan huruf . Untuk kelas vektor khusus ini, ia mungkin bekerja dalam cukup banyak kasus yang merupakan perkiraan yang layak, tetapi akan jauh lebih sulit untuk menetapkan bahwa selalu demikian.

c o s = \frac{| | d_{1} | |}{| | d_{2} | |}

$\mathrm{cos}=\frac{||d_1||}{||d_2||}$

\frac{d_{1} \cdot d_{2}}{| | d_{1} | | | | d_{2} | |} \leq \frac{d_{1} \cdot d_{1}}{| | d_{1} | | | | d_{1} | |}

$\frac{d_1\cdot d_2}{||d_1||\ ||d_2||}\le\frac{d_1\cdot d_1}{||d_1||\ ||d_1||}$

d_{1} \cdot d_{2} \leq d_{1} \cdot d_{1}

$d_1\cdot d_2\le d_1\cdot d_1$

Matthew Graves

@ MatthewGraves, saya rasa saya setuju dengan Anda. Bukan keahlian saya tapi saya masih meretasnya.

paparazzo

Jawaban:

Sayangnya, matematika menyederhanakan untuk menunjukkan bahwa Anda tidak dapat membenarkan dengan ketat membatasi perbandingan kesamaan cosinus dari vektor berdasarkan panjangnya.

Poin kuncinya adalah bahwa metrik kesamaan cosine menormalkan berdasarkan panjang, sehingga hanya vektor satuan yang dipertimbangkan. Saya tahu ini bukan jawaban yang Anda inginkan, tetapi matematika dengan jelas menunjukkan bahwa metrik kesamaan cosinus adalah agnostik dengan panjang vektor.

Mari kita lihat matematika lebih terinci:

Anda menerapkan metrik kesamaan cosinus dan mengharuskan metrik itu lebih besar dari 0,6:

s i m i l a r i t y = \cos (θ) = \frac{A \cdot B}{| | A | | | | B | |} \geq 0.6

$similarity=\cos{(\theta)}=\frac{\mathbf{A}\cdot\mathbf{B}}{||A|| ||B||}\geq0.6$

Tetapi panjang skalar di bagian bawah dapat didistribusikan ke dalam produk silang di atas (properti distributif):

\frac{A \cdot B}{| | A | | | | B | |} = \frac{A}{| | A | |} \cdot \frac{B}{| | B | |} = \hat{A} \cdot \hat{B}

$\frac{\mathbf{A}\cdot\mathbf{B}}{||A|| ||B||} = \frac{\mathbf{A}}{||A||}\cdot\frac{\mathbf{B}}{||B||}=\hat{\mathbf{A}}\cdot\hat{\mathbf{B}}$

Sekarang dan adalah vektor yang titik dalam arah yang sama dengan dan tetapi mereka telah dinormalisasi dengan panjang satu. Jadi definisi metrik kesamaan cosinus adalah mengambil vektor asli, menormalkannya dengan panjang satu, dan kemudian mengukur produk titik dari vektor satuan. $\hat{\mathbf{A}}$ $\hat{\mathbf{B}}$ $\mathbf{A}$ $\mathbf{B}$

Untuk itu:

s i m i l a r i t y = \cos (θ) = \frac{d 1 \cdot d 2}{| | d 1 | | | | d 2 | |} = \hat{d 1} \cdot \hat{d 2} \geq 0.6

$similarity=\cos{(\theta)}=\frac{\mathbf{d1}\cdot\mathbf{d2}}{||d1|| ||d2||}=\hat{\mathbf{d1}}\cdot\hat{\mathbf{d2}}\geq0.6$

hanya bergantung pada orientasi vektor dan bukan pada besarnya mereka (yaitu panjang).

Rekonsiliasi ini dengan apa yang Anda lakukan:

Terlepas dari apa yang ditunjukkan hasil aljabar linier, Anda mungkin masih melihat hasil yang signifikan secara statistik. Secara praktis, Anda mungkin menemukan bahwa statistik menunjukkan bahwa batasan panjang berlaku untuk data Anda. Misalnya, Anda mungkin menemukan bahwa tweet tidak pernah memiliki kesamaan cosinus bila dibandingkan dengan "Perang dan Damai" Tolstoy. Jika statistik Anda terlihat bagus untuk menggunakan dan $\geq0.6$ $||d2|| > .8 ||d1||$ maka saya sarankan Anda pergi karena jenis pembatasan kanopi ini sangat berguna dalam menghemat waktu komputasi. $||d2|| < ||d1|| / .8$

Anda mungkin dapat mendamaikan apa yang telah Anda lakukan dengan metrik jarak dengan juga mempertimbangkan jarak Euclidean. Dimana kemiripan cosinus hanya mengembalikan nilai antara -1 dan 1 berdasarkan sudut antara dua vektor, jarak Euclidean akan mengembalikan nilai yang bergantung pada panjang kedua vektor tersebut. Dalam beberapa hal, Anda menggabungkan aspek jarak Euclidean dengan kesamaan cosinus.

Masuk akal cukup baik untuk mensyaratkan bahwa panjang relatif berada dalam jarak 25% dari satu sama lain dalam arti bahwa ini menggabungkan aspek jarak Euclidean untuk membuat kanopi kelompok-oleh, yang memotong waktu perhitungan, kemudian panjang kesamaan cosinus agnostik dapat digunakan sebagai penentu akhir.

Perhatikan bahwa 1 / .8 = 1.25, jadi d2> =. 8d1 adalah batasan yang lebih ketat daripada d2 <= d1 / .8. Saya sarankan menggunakan d2> = .75d1 dan d2 <= 1.25d1 karena ini simetris.

Semoga ini membantu!

AN6U5
sumber

Saya pikir ini tidak menggunakan fakta bahwa panjang vektor sebagian besar berasal dari bobot idf bersama, karena skema normalisasi yang dia gunakan. Jika suatu dokumen memiliki norma yang sangat rendah, itu menyiratkan bahwa itu tidak mengandung kata-kata langka (atau mengandungnya pada frekuensi fraksional yang sangat rendah), yang berarti bahwa ia dapat dikesampingkan seperti halnya dengan dokumen yang hanya berisi kata-kata langka. Tetapi seberapa ketat batasan ini secara umum tampaknya tidak jelas bagi saya. Mungkin kasus bahwa batas teoritis sangat luas dibandingkan dengan batas empiris yang diamati.

Matthew Graves

@Matthew Graves, Yang saya katakan adalah bahwa kesamaan cosinus adalah agnostik dengan panjang vektor. Dia bertanya bagaimana perbedaan panjang vektor dapat mempengaruhi kesamaan cosine yang dihasilkan dan jawabannya adalah: mereka tidak bisa.

AN6U5

Korelasi empiris tidak dapat diabaikan. Ada cara untuk mengkorelasikan keacakan korpus untuk melimpah jika hanya statistik. Saya tidak punya cukup perwakilan di situs ini untuk mendaftar.

paparazzo

Di sinilah saya tidak setuju. Itu tidak menormalkan berdasarkan panjang. Ini menormalkan pada satu istilah yang paling umum. Dokumen yang lebih panjang hanya bisa encer. Saya bersedia menyesuaikan bagaimana normalisasi dilakukan untuk mendapatkan batasan yang dapat saya dukung.

paparazzo

Terima kasih telah mengubah pertanyaan Anda. Lebih baik menjelaskan apa yang ingin Anda capai. Perhatikan bahwa normalisasi Anda yang diubah menjadikan ini sebenarnya bukan kesamaan cosinus, karena ini didefinisikan secara ketat. Saya akan menyarankan beberapa suntingan tambahan untuk menguraikan ini. Jaga baik-baik dan semoga sukses.

AN6U5

$||d_i||$ $||d_i||$ $||d_i||$

Untuk mengerjakan beberapa aljabar, izinkan saya memperkenalkan beberapa istilah lagi (dan ganti beberapa istilah menjadi yang lebih pendek):

$d_1$ $[t_1, t_2, ...]$ $[w_1, w_2, ...]$ $[d_1, d_2, ...]$ $0.5\le t_i\le 1$ $0\le w_i\le 6$ $D_1=||d_1||$

$d_1$ $x$ $d_1+x$ $X$

$X=\sqrt{\sum_i w_i^2 (t_i+x_i)^2}$

$0.6D_1X\le \sum_i w_i^2t_i(t_i+x_i)$

$0.5\le t_i+x_i \le 1$

$x$ $x_i=0\ \forall i$ $d_i+x_i=1$

$x$ $X^2$ $X$ $X>0$ $X$ $-X$ $P$ $P$

$0\ge 0.36D_1^2\sum_i w_i^2 (t_i+x_i)^2-\sum_{i,j}w_i^4t_it_j(t_i+x_i)(t_j+x_j)$

$0\ge x^TPx+q^Tx+r$ $P_{i,j}=0.36D_1^2-w_i^2t_it_j$ $i=j$ $-w_i^2t_it_j$

$P$ $d_1$ $X$

$X$ $w$ $x$ $X$

Matthew Graves
sumber

Saya tidak setuju dengan || d || dengan tampaknya berfungsi sebagai ukuran kelangkaan. Itu dinormalisasi. "Mary punya domba kecil" akan memiliki yang lebih kecil || dari "Menikah punya domba kecil putih". Dan "oddxxA oddxxB oddxxC" akan memiliki || yang lebih kecil dari "oddxxA oddxxB oddxxC oddxxD" dalam rasio yang kira-kira sama. Dan kedua perbandingan tersebut akan memiliki cos serupa.

paparazzo

@ Frisbee, apakah Anda yakin tentang perbandingan itu? Misalkan idf adalah 0 untuk 'a', 0,5 untuk 'punya' dan 'Mary', 1 untuk 'kecil' dan 'putih', dan 2 untuk 'domba', saya menghitung 2,4 untuk "Mary punya domba kecil" dan 2,55 untuk "Mary punya domba kecil putih", tetapi 1,83 untuk "A Mary punya domba kecil". Artinya, satu-satunya cara untuk mengurangi norma adalah dengan meningkatkan frekuensi istilah yang paling sering, bukan dengan menambahkan kata-kata baru. Atau apakah kita tidak menggunakan formula yang sama?

Matthew Graves

Saya pikir Anda menormalkan dokumen pada tertimbang (dengan IDF) bukan frekuensi mentah. Itu akan mengubah banyak hal. Lebih masuk akal bagi saya untuk menormalkan berat badan. Secara signifikan mengubah dokumen || dengan membuat 'a' istilah yang paling umum mengacaukan barang.

paparazzo

d_{t} = w_{t} (0.5 + 0.5 \frac{w_{t} f (t, d)}{m a x {w_{t} f (t, d) : t \in d}})

$d_t=w_t(0.5+0.5\frac{w_tf(t,d)}{\mathrm{max}\{w_tf(t,d): t\in d\}})$

w_{t} = l o g \frac{N}{| {d \in D : t \in d} |}

$w_t=\mathrm{log}\frac{N}{|\{d\in D: t\in d\}|}$

d

$d$

d_{i}

$d_i$

d

$d$

Saya mengirim jawaban tetapi jelas saya akan memberikan bonus kepada orang lain

Saya pikir ada pembilang maksimum jika tf dokumen dinormalisasi

d1⋅d2 / (|| d1 |||| d2 ||)

Asumsikan d1 memiliki istilah yang sama atau kurang (atau ambil saja d dengan persyaratan kurang)
Tf maksimum yang dinormalisasi adalah 1
Jadi jumlah pembilang maksimum yang mungkin (tf1, i * idf, i * 1 * idf, i)

|| d2 || = jumlah (tf1, i * idf, i * 1 * idf, i) / || d1 || / .6

Adapun minimum saya sedang mengerjakan itu tetapi jelas ada minimum.
Jika Anda akan mencocokkan Anda akan memiliki || d ||

paparazzo
sumber