Model przestrzeni wektorowej cosinus tf-idf do wyszukiwania podobnych dokumentów

Posiadaj korpus ponad miliona dokumentów

Dla danego dokumentu chcesz znaleźć podobne dokumenty przy użyciu cosinus jak w modelu przestrzeni wektorowej

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

Wszystkie tf zostały znormalizowane przy użyciu zwiększonej częstotliwości, aby zapobiec tendencyjności do dłuższych dokumentów, jak w tym tf-idf :

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

Wstępnie obliczone wszystkie Miej wstępnie obliczone wartości mianownika. Więc dla danego musisz zdobyć ponad 1 milion Mieć próg 0,6 cosinusa dla podobieństwa $||d||$

$d1$ $d2$

Widzę to dla danego istnieje dość wąski zakres dla cosinusa 0,6 Na przykład w jednym poszukiwaniu podobnego dla cosinusa 0,6 i a z 7,7631 następnie zakres od 7,0867 do 8,8339 Gdzie poza progiem cosinus 0,6 Zakres od do 0,7223 do 89,3395 $||d_1||$ $||d_2||$ $\ge$
$\ge$ $||d_1||$ $||d_2||$
$||d_2||$
Było to przy standardowej normalizacji dokumentów TF Patrzy się
na DUŻO które nie mają szans na dopasowanie cosinus 0.6 $||d_2||$

Na koniec pytanie:
Dla dawania i cosinus> = 0,6, w jaki sposób można określić zakres które mają szansę? Które czy mogę bezpiecznie wyeliminować? $||d_1||$ $||d_2||$
$||d_2||$

Wiem też liczbę terminów w i jeśli jest określenie zakresu count. $d_1$ $d_2$

Poprzez eksperymenty
i wydaje się bezpieczny, ale mam nadzieję, że istnieje zasięg, który okazał się bezpieczny $||d2|| > .8 ||d1||$ $||d2|| < ||d1|| / .8$

Utworzono kilka przypadków testowych z bardzo niektórymi unikalnymi terminami, niektóre nie tak wyjątkowe i niektóre wspólne. Rzeczywiście, możesz wziąć najbardziej unikalny termin i zwiększyć tę częstotliwość w porównaniu. Licznik pójdzie w górę (iloczyn skalarny), a zatem porówna || i otrzyma cosinus bardzo blisko 1.

Rodzaj pokrewny, a NIE pytanie.
Używam również tf-idf do grupowania dokumentów w grupy. Baza klientów, w której sprzedaję, jest przyzwyczajona do bliskich grup duplikatów. Podchodzę do podobnego podejścia i wyglądam na najmniejszą liczbę terminów i oceniam ją względem liczby terminów do 3x. Zatem liczba wyrażeń 10 wynosi 10 do 30 (4-9 już strzelało do 10). Tutaj mogę sobie pozwolić na pominięcie jednego z nich w innym. Skończyłem 10%, a największy stosunek to 1,8.

Proszę zidentyfikować błędy w niniejszej analizie
Jak podkreślił AN6U5 istnieje luka w niniejszej analizie
To już nie jest cosinus jeśli dokument jest znormalizowane na ważona
A jak podkreślił Mathew nie można również stwierdzić d1⋅d2≤d1⋅d1
jestem jeszcze nadzieję na coś dać mi ciężko, ale ludzie związani że wydaje się wiedzieć takie rzeczy mówią mi, nie
nie chcę zmienić pytanie tak po prostu zignorować to
zrobię jakąś analizę i może odpowiedzieć na pytanie osobnego dokumentu normalizacji
dla celem tego pytania jest założenie, że dokument jest znormalizowany na surowym tf
Przepraszam, ale po prostu nie jestem dobry z tym, co kiedykolwiek znaczniki są używane do tworzenia równań
Więc w mojej notacji
|| d1 || = sqrt (suma (w1 x w1))
d1 kropka d2 = suma (w1 X w2)
Załóżmy, że d1 jest krótszym dokumentem
Najlepszą d1 kropką d2, którą można osiągnąć, jest d1 kropka d1
Jeśli d1 jest małżeństwem 100 paul 20
I d2 jest małżeństwem 100 paul 20 peter 1
Znormalizowany
d1 jest małżeństwem 1 paul 1/5
d2 jest w związku małżeńskim 1 paul 1/5 peter 1/100
Wyraźnie wyjdź w związek małżeński i paul mają ten sam idf w obu dokumentach
Najlepsze możliwe d1 kropka d2 to d1 kropka d1
Maksymalne możliwe dopasowanie do d1 to d1
cos = d1 kropka d1 / || d1 || || d2 ||
kwadrat po obu stronach
cos X cos = (d1 kropka d1) X (d1 kropka d1) / ((d1 kropka d1) X (d2 kropka d2)) cos X cos = (d1 kropka d1) / (d2 kropka d2)
weź kwadrat pierwiastek z obu stron
cos = || d1 || / || d2 ||
wynosi || d2 || nie jesteś związany cos?
Jeśli tylko użyję || d2 || > = cos || d1 || i || d2 || <= || d1 || / cos Dostaję potrzebną prędkość obliczeniową

text-mining similarity paparazzo
źródło

Twój argument, który kończy się granicą wyznaczoną przez

nie działa, ponieważ „Najlepsza d1 kropka d2, którą można osiągnąć, to d1 kropka d1” jest niepoprawna. Podczas gdy

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

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

, nie jest tak, że

. W przypadku tej konkretnej klasy wektorów może to działać w wystarczającej liczbie przypadków, co jest dobrym przybliżeniem, ale znacznie trudniej byłoby ustalić, że zawsze tak jest.

\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 Myślę, że się z tobą zgadzam. Nie moja wiedza specjalistyczna, ale wciąż się nad tym zastanawiam.

paparazzo

Odpowiedzi:

Niestety matematyka upraszcza pokazanie, że nie można rygorystycznie uzasadnić ograniczenia porównania podobieństwa cosinusów wektorów na podstawie ich długości.

Kluczową kwestią jest to, że metryka podobieństwa cosinus normalizuje się na podstawie długości, tak że uwzględniane są tylko wektory jednostkowe. Wiem, że niekoniecznie była to odpowiedź, której chciałeś, ale matematyka wyraźnie pokazuje, że wskaźniki podobieństwa cosinus są agnostyczne do długości wektora.

Spójrzmy na matematykę bardziej szczegółowo:

Stosujesz metrykę podobieństwa cosinus i wymagasz, aby ta metryka była większa niż 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$

Ale długości skalarne na dole można podzielić na powyższe produkty krzyżowe (właściwość dystrybucyjna):

\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}}$

Teraz i są wektory, które zmierzają w tym samym kierunku, i , ale które zostały znormalizowane do długości jeden. Zatem definicją metryki podobieństwa cosinus jest wzięcie oryginalnych wektorów, znormalizowanie ich do długości jednego, a następnie zmierzenie iloczynu wektorów jednostkowych. $\hat{\mathbf{A}}$ $\hat{\mathbf{B}}$ $\mathbf{A}$ $\mathbf{B}$

W związku z tym:

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$

zależy tylko od orientacji wektorów, a nie od ich wielkości (tj. długości).

Pogodzenie tego z tym, co robisz:

Pomimo tego, co pokazują wyniki algebry liniowej, być może nadal widzisz statystycznie znaczący wynik. W praktyce może się okazać, że statystyki pokazują, że ograniczenia długości obowiązują dla twoich danych. Na przykład może się okazać, że tweety nigdy nie mają podobieństwa cosinusowego porównaniu z „Wojną i pokojem” Tołstoja. Jeśli twoje statystyki wyglądają dobrze na używanie i $\geq0.6$ $||d2|| > .8 ||d1||$ następnie sugeruję, abyś poszedł z tym, ponieważ tego rodzaju ograniczenia czaszy są bardzo przydatne w oszczędzaniu czasu obliczeniowego. $||d2|| < ||d1|| / .8$

Być może możesz pogodzić to, co robiłeś z pomiarami odległości, biorąc również pod uwagę odległość euklidesową. Tam, gdzie podobieństwo cosinusu zwraca tylko wartość od -1 do 1 w oparciu o kąt między dwoma wektorami, odległości euklidesowe zwrócą wartości, które zależą od długości dwóch wektorów. W pewnym sensie łączysz aspekty odległości euklidesowej z podobieństwem cosinus.

Dość rozsądne jest wymaganie, aby długości względne nie przekraczały 25% w tym sensie, że łączy to aspekt odległości euklidesowej w celu utworzenia zadaszeń grupowych, co skraca czas obliczeń, a następnie można zastosować agnostyczne podobieństwo kosinusa długości jako ostateczny wyznacznik.

Zauważ, że 1 / .8 = 1,25, więc d2> =. 8d1 jest bardziej restrykcyjnym ograniczeniem niż d2 <= d1 / .8. Sugeruję użycie d2> =. 75d1 i d2 <= 1,25d1, ponieważ jest to symetryczne.

Mam nadzieję że to pomoże!

AN6U5
źródło

Myślę, że nie korzysta to z faktu, że długości wektorów pochodzą głównie ze wspólnych wag idf, ze względu na stosowany przez niego schemat normalizacji tf. Jeśli dokument ma bardzo niską normę, oznacza to, że nie zawiera rzadkich słów (lub zawiera je z bardzo małą częstotliwością ułamkową), co oznacza, że można go wykluczyć jako podobny do dokumentu zawierającego tylko rzadkie słowa. Ale to, jak ścisłe jest to ograniczenie, wydaje mi się niejasne. Prawdopodobnie jest tak, że granice teoretyczne są bardzo szerokie w porównaniu z obserwowanymi granicami empirycznymi.

Matthew Graves

@Matthew Graves, mówię tylko, że podobieństwo cosinusa jest niezależne od długości wektora. Pyta, w jaki sposób różnice w długości wektora mogą wpływać na wynikowe podobieństwo cosinusa, a odpowiedź brzmi: nie mogą.

AN6U5

Korelacji empirycznej nie można zignorować. Istnieje sposób skorelowania losowości korpusu pod względem obfitości, jeśli tylko statystycznej. Nie mam wystarczającej liczby przedstawicieli na tej stronie, aby zarejestrować się do głosowania.

paparazzo

Tutaj nie zgadzam się. Nie normalizuje się na podstawie długości. Normalizuje się w odniesieniu do jednego najczęściej używanego terminu. Dłuższy dokument może jedynie rozcieńczyć. Jestem gotów dostosować sposób normalizacji, aby uzyskać granicę, którą mogę wesprzeć.

paparazzo

Dziękujemy za zmianę pytania. Lepiej wyjaśnia, co próbujesz osiągnąć. Zauważ, że zmodyfikowana normalizacja sprawia, że tak naprawdę nie jest to podobieństwo do kosinusa, ponieważ jest to ściśle określone. Sugerowałbym kilka dodatkowych zmian, aby to przeliterować. Trzymaj się i powodzenia.

AN6U5,

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

Aby przejść przez algebrę, pozwól, że przedstawię jeszcze kilka terminów (i zmień nazwy niektórych na krótsze):

$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
źródło

Nie zgadzam się z || d || wydaje się służyć jako rzadkość. Jest znormalizowany. „Mary miała małą owieczkę” będzie miała mniejszy || niż „Marry miała białego baranka”. I „oddxxA oddxxB oddxxC” będzie miał mniejszy || niż „oddxxA oddxxB oddxxC oddxxC” w mniej więcej tym samym stosunku. I te dwa porównania będą miały podobny Cos.

paparazzo

@Frisbee, czy jesteś pewien tego porównania? Przypuśćmy, że idf to 0 dla „a”, 0,5 dla „miał” i „Mary”, 1 dla „małego” i „białego” oraz 2 dla „baranka”, obliczam 2,4 dla „Mary miała małego baranka” i 2,55 dla „Maryja miała małego baranka”, ale 1,83 dla „A Maryja miała małego baranka”. Oznacza to, że jedynym sposobem na obniżenie normy jest zwiększenie częstotliwości najczęstszego terminu, a nie dodanie nowych słów. A może nie używamy tej samej formuły?

Matthew Graves

Myślałem, że znormalizowałeś dokument na ważonej (z IDF), a nie na surowej częstotliwości. To by zmieniło rzeczy. Bardziej sensowne jest dla mnie znormalizowanie ważenia. Znacząca zmiana dokumentu || czyniąc „a” najczęściej używanym terminem.

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$ , i

d

$d$ , dokument związany z tym wektorem.) Muszę dziś wieczorem zastanowić się, czy poprawiłoby to ograniczenie (ale prawdopodobnie wiąże się to z dużą ilością algebry).

Matthew Graves

Wysyłam odpowiedź, ale wyraźnie przyznam premię komuś innemu

Myślę, że istnieje maksymalny licznik, jeśli dokument tf jest znormalizowany

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

Załóżmy, że d1 ma takie same lub mniej terminów (lub po prostu weź d z mniejszymi terminami)
Maksymalna możliwa znormalizowana tf wynosi 1,
więc maksymalna możliwa suma licznika (tf1, i * idf, i * 1 * idf, i)

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

Jeśli chodzi o minimum, pracuję nad tym, ale oczywiście istnieje minimum.
Jeśli masz zamiar dopasować, będziesz miał || d ||

paparazzo
źródło