Ranking (pobieranie informacji) - Ranking (information retrieval)

Ranking zapytań jest jednym z podstawowych problemów w wyszukiwaniu informacji (IR), dyscyplinie naukowo-inżynierskiej stojącej za wyszukiwarkami . W przypadku zapytania $q$ i zbioru dokumentów $D$ pasujących do zapytania problemem jest uszeregowanie, to znaczy posortowanie dokumentów w $D$ według jakiegoś kryterium, tak aby „najlepsze” wyniki pojawiły się na początku listy wyników wyświetlanej użytkownik. Ranking w zakresie wyszukiwania informacji jest ważnym pojęciem w informatyce i jest używany w wielu różnych aplikacjach, takich jak zapytania wyszukiwarek i systemy rekomendacji . Większość wyszukiwarek korzysta z algorytmów rankingowych, aby zapewnić użytkownikom dokładne i trafne wyniki.

Historia

Pojęcie page rank pochodzi z lat 40. XX wieku, a pomysł zrodził się w dziedzinie ekonomii. W 1941 r. Wassily Leontief opracował iteracyjną metodę wyceny sektora kraju opartą na znaczeniu innych sektorów, które dostarczały mu zasoby. W 1965 roku Charles H Hubbell z Uniwersytetu Kalifornijskiego w Santa Barbara opublikował technikę określania ważności jednostek na podstawie ważności osób, które je popierają.

Gabriel Piński i Francis Narin wymyślili podejście do rangi dzienników. Ich zasadą było, że czasopismo jest ważne, jeśli jest cytowane przez inne ważne czasopisma. Jon Kleinberg , informatyk z Cornell University , opracował niemal identyczne podejście do PageRank, które nazywało się Hypertext Induced Topic Search lub HITS i traktowało strony internetowe jako „huby” i „autorytety”.

Algorytm Google PageRank został opracowany w 1998 roku przez założycieli Google, Sergeya Brina i Larry'ego Page'a i jest kluczowym elementem metody Google do rankingu stron internetowych w wynikach wyszukiwania. Wszystkie powyższe metody są nieco podobne, ponieważ wszystkie wykorzystują strukturę łączy i wymagają podejścia iteracyjnego.

Modele rankingowe

Funkcje rankingowe są oceniane na różne sposoby; jednym z najprostszych jest określenie precyzji pierwszych k najwyższych wyników dla pewnego ustalonego k ; na przykład odsetek 10 najlepszych wyników, które są trafne, średnio dla wielu zapytań.

Modele IR można ogólnie podzielić na trzy typy: modele logiczne lub BIR, modele przestrzeni wektorowej i modele probabilistyczne.

Modele logiczne

Model Boolean lub BIR jest prostym podstawowym modelem zapytań, w którym każde zapytanie jest zgodne z podstawowymi zasadami algebry relacyjnej z wyrażeniami algebraicznymi i gdzie dokumenty nie są pobierane, chyba że całkowicie do siebie pasują. Ponieważ zapytanie albo pobiera dokument (1), albo nie pobiera dokumentu (0), nie ma metodologii ich uszeregowania.

Model przestrzeni wektorowej

Ponieważ model Boolean pobiera tylko pełne dopasowania, nie rozwiązuje problemu częściowego dopasowania dokumentów. Wektorowa przestrzeni modelu rozwiązuje ten problem poprzez wprowadzenie elementów wektorów indeksu każdej przypisanej z ciężarami. Wagi są w zakresie od dodatnich (jeśli są dopasowane całkowicie lub w pewnym stopniu) do ujemnych (jeśli są niedopasowane lub dopasowane całkowicie przeciwnie), jeśli dokumenty są obecne. Częstotliwość terminów - odwrotna częstotliwość dokumentu ( tf-idf ) to jedna z najpopularniejszych technik, w której wagami są terminy (np. słowa, słowa kluczowe, frazy itp.), a wymiary to liczba słów w korpusie.

Wynik podobieństwa między zapytaniem a dokumentem można znaleźć, obliczając wartość cosinus między wektorem wagi zapytania a wektorem wagi dokumentu przy użyciu podobieństwa cosinusów . Pożądane dokumenty można pobrać, uszeregowując je według wyniku podobieństwa i pobranych k dokumentów, które mają najwyższe wyniki lub są najbardziej odpowiednie dla wektora zapytania.

Model probabilistyczny

W modelu probabilistycznym teoria prawdopodobieństwa została wykorzystana jako główny środek do modelowania procesu wyszukiwania w kategoriach matematycznych. Model prawdopodobieństwa wyszukiwania informacji został wprowadzony przez Marona i Kuhnsa w 1960 roku, a następnie rozwinięty przez Roberstona i innych badaczy. Według Spack Jones i Willett (1997): Uzasadnienie wprowadzenia koncepcji probabilistycznych jest oczywiste: systemy IR zajmują się językiem naturalnym, a to jest zbyt nieprecyzyjne, aby umożliwić systemowi stwierdzenie z pewnością, który dokument będzie odpowiedni dla konkretnego zapytania.

Model wykorzystuje teorię prawdopodobieństwa do wyszukiwania informacji (zdarzenie ma możliwość wystąpienia od 0 do 100%). tj. w modelu prawdopodobieństwa istotność jest wyrażana w kategoriach prawdopodobieństwa. Tutaj dokumenty są uszeregowane według malejącego prawdopodobieństwa trafności. Uwzględnia element niepewności w procesie IR. tj. niepewność, czy dokumenty pobrane przez system są istotne dla danego zapytania.

Model prawdopodobieństwa ma na celu oszacowanie i obliczenie prawdopodobieństwa, że dokument będzie odpowiedni dla danego zapytania w oparciu o niektóre metody. „Zdarzenie” w tym kontekście wyszukiwania informacji odnosi się do prawdopodobieństwa związku między zapytaniem a dokumentem. W przeciwieństwie do innych modeli IR, model prawdopodobieństwa nie traktuje istotności jako dokładnego pomiaru braku lub dopasowania.

W modelu zastosowano różne metody określania prawdopodobieństwa istotności między zapytaniami a dokumentami. Trafność w modelu prawdopodobieństwa jest oceniana na podstawie podobieństwa między zapytaniami a dokumentami. Ocena podobieństwa jest ponadto zależna od częstotliwości terminu.

Zatem w przypadku zapytania składającego się tylko z jednego terminu (B) prawdopodobieństwo, że dany dokument (Dm) zostanie uznany za odpowiedni, jest stosunkiem użytkowników, którzy przesyłają termin zapytania (B) i uważają, że dokument (Dm) jest odpowiedni w w stosunku do liczby użytkowników, którzy przesłali termin (B). Jak przedstawiono w modelu Marona i Kuhna, można je przedstawić jako prawdopodobieństwo, że użytkownicy przesyłający określony termin zapytania (B) ocenią, że dany dokument (Dm) jest odpowiedni.

Według Saltona i McGilla istotą tego modelu jest to, że jeśli można obliczyć oszacowania prawdopodobieństwa wystąpienia różnych terminów w odpowiednich dokumentach, to prawdopodobieństwa, że dokument zostanie odnaleziony, biorąc pod uwagę, że jest on istotny lub że jest nie, można oszacować.

Kilka eksperymentów wykazało, że model probabilistyczny może dać dobre wyniki. Jednak takie wyniki nie były wystarczająco lepsze niż te uzyskane za pomocą modelu Boolean lub Vector Space.

Środki oceny

Najczęstszymi miarami oceny są precyzja, pamięć i f-score. Są one obliczane przy użyciu nieuporządkowanych zestawów dokumentów. Środki te muszą zostać rozszerzone lub muszą zostać zdefiniowane nowe, w celu oceny rankingowych wyników wyszukiwania, które są standardowe w nowoczesnych wyszukiwarkach. W kontekście wyszukiwania z rankingiem, odpowiednie zestawy wyszukanych dokumentów są naturalnie podane przez k najczęściej wyszukiwanych dokumentów. Dla każdego takiego zestawu można wykreślić wartości precyzji i przywracania, aby uzyskać krzywą precyzji przywracania.

Precyzja

Precyzja mierzy dokładność procesu pobierania. Jeżeli rzeczywisty zbiór odpowiednich dokumentów oznaczony jest przez I, a wyszukany zbiór dokumentów przez O, to precyzję określa wzór:

{\text{Precision}}={\frac {|\{{\text{I}}\}\cap \{{\text{O}}\}|}{|\{{\text{O}}\}|}}

Przypomnienie sobie czegoś

Przypomnienie jest miarą kompletności procesu IR. Jeżeli rzeczywisty zestaw odpowiednich dokumentów jest oznaczony przez I, a wyszukany zestaw dokumentów przez O, to wycofanie następuje przez:

{\text{Recall}}={\frac {|\{{\text{I}}\}\cap \{{\text{O}}\}|}{|\{{\text{I}}\}|}}

Wynik F1

F1 Score próbuje połączyć pomiar precyzji i przywołania. Jest to średnia harmoniczna tych dwóch. Jeśli P oznacza precyzję, a R oznacza wycofanie, F-Score jest wyrażony przez:

F_{1}=2\cdot {\frac {\mathrm {P} \cdot \mathrm {R} }{\mathrm {P} +\mathrm {R} }}

Algorytm PageRank

PageRank algorytm generuje rozkład prawdopodobieństwa używany do reprezentowania prawdopodobieństwo, że dana osoba losowo klikając na linki dotrze do konkretnej strony. PageRank można obliczyć dla zbiorów dokumentów o dowolnej wielkości. W kilku pracach naukowych zakłada się, że rozkład jest równomiernie rozłożony na wszystkie dokumenty w zbiorze na początku procesu obliczeniowego. Obliczenia PageRank wymagają kilku przejść przez zbiór, aby dostosować przybliżone wartości PageRank, aby lepiej odzwierciedlały teoretyczną wartość rzeczywistą. Wzory podano poniżej:

PR(u)=\sum _{v\in B_{u}}{\frac {PR(v)}{L(v)}}

tzn. wartość PageRank dla strony u jest zależna od wartości PageRank dla każdej strony v zawartej w zestawie B _u (zestaw zawierający wszystkie strony linkujące do strony u ), podzielonej przez liczbę L ( v ) linków ze strony v .

Algorytm trafień

Podobnie jak PageRank, HITS używa analizy linków do analizy trafności stron, ale działa tylko na małych zbiorach podwykresów (a nie na całym wykresie internetowym) i jest zależny od zapytania. Podwykresy są uszeregowane według wag w centrach i urzędach, w których pobierane i wyświetlane są strony o najwyższej pozycji w rankingu.

Zobacz też

Nauka pozycjonowania : zastosowanie uczenia maszynowego do problemu rankingowego

Languages

In other projects