Unterschiede

Hier werden die Unterschiede zwischen zwei Versionen der Seite angezeigt.

Link zu der Vergleichsansicht

Beide Seiten, vorherige Überarbeitung Vorherige Überarbeitung
Nächste Überarbeitung		 Vorherige Überarbeitung
talit:indexing [2024-08-11 13:50] – hoftalit:indexing [2025-02-15 13:38] (aktuell) – hof
Zeile 1: Zeile 1:
 # Text Indexing # Text Indexing
 +
 +<nodisp 1>
 +++++Repo|
 +https://github.com/tkilla77/ksr_talit_indexing/blob/main/04_text_indexing.ipynb
 +++++
 +</nodisp>
  
 Nachdem wir in [[retrieval]] ein einzelnes Attribut indexiert haben, möchten wir dasselbe für einen ganzen Text erreichen. Statt der Geodatenbank verwenden wir dafür Artikel von Wikipedia. Nachdem wir in [[retrieval]] ein einzelnes Attribut indexiert haben, möchten wir dasselbe für einen ganzen Text erreichen. Statt der Geodatenbank verwenden wir dafür Artikel von Wikipedia.
Zeile 14: Zeile 20:
  
 Anders als bei der Geodatenbank müssen wir hier noch den Text in einzelne Wörter (_en_. Tokens) zerlegen. Anders als bei der Geodatenbank müssen wir hier noch den Text in einzelne Wörter (_en_. Tokens) zerlegen.
- 
 ### Aufgabe 1 - Tokenizer ### Aufgabe 1 - Tokenizer
  
Zeile 40: Zeile 45:
 <code python> <code python>
 def query_index(index, query): def query_index(index, query):
-    result_set = set() 
     return index.get(query, set())     return index.get(query, set())
  
Zeile 76: Zeile 80:
 </code> </code>
  
-<nodisp 2>+<nodisp 1>
 ++++Lösung| ++++Lösung|
 <code python> <code python>
Zeile 90: Zeile 94:
 ++++ ++++
 </nodisp> </nodisp>
 +
 +Wir sehen bereits: Einige Wörter (`antoine`) sind _wertvoller_ als andere (`film`), um eine Frage richtig zu beantworten. Im obigen Beispiel liefert das Token `film` überhaupt keine Information darüber, welches Dokument am besten zur Query passt, da es in jedem Dokument vorkommt. Wir werden das Problem später mit _Stop Wording_ behandeln.
 +
  
 ## Moar Data ## Moar Data
Zeile 117: Zeile 124:
  
 Wieviele Filme mit `'harrison'` gibt es? Und wieviele mit einem `'delorean'`? Wieviele Filme mit `'harrison'` gibt es? Und wieviele mit einem `'delorean'`?
- 
- 
 ## Stop Wording ## Stop Wording
 Wenn du den erstellten Index untersuchst, wirst du Wörter wie ''der'' oder ''ein'' finden, die in praktisch allen Artikeln vorkommen. Entsprechend benötigen die sehr viel Platz im Index, und liefern auch kaum interessante Resultate. Wenn du den erstellten Index untersuchst, wirst du Wörter wie ''der'' oder ''ein'' finden, die in praktisch allen Artikeln vorkommen. Entsprechend benötigen die sehr viel Platz im Index, und liefern auch kaum interessante Resultate.
  
-Normalerweise werden solche _Stop Words_ bereits bei der Indexierung ignoriert. Natürlich könnten wir eine Stop-Word-Liste aus dem Internet laden - aber eigentlich haben wir ja alle Informationen selber bereits zur Hand, um eine solche zu erstellen: Wir wissen ja für jedes Wort, in wievielen Artikeln es vorkommt. Wörter, die in mehr als der Hälfte der Artikel vorkommen, dürften kaum interessant sein. Wir sind also interessiert an der relativen Dokumentenhäufigkeit (_en._ document frequency): $\frac{frequency}{n}$.+Normalerweise werden solche _Stop Words_ bereits bei der Indexierung ignoriert. Natürlich könnten wir eine Stop-Word-Liste aus dem Internet laden - aber eigentlich haben wir ja alle Informationen selber bereits zur Hand, um eine solche zu erstellen: Wir kennen die Häufigkeit jedes Wortes, also in wie vielen Artikeln es vorkommt. Wörter, die in mehr als der Hälfte der Artikel vorkommen, dürften kaum interessant sein. Mehr als an der _absoluten_ Häufigkeit sind wir also interessiert an der _relativen_ Dokumentenhäufigkeit (_en._ document frequency): $\frac{frequency}{n}$.
  
 ### Aufgabe 3 - Stop Words ### Aufgabe 3 - Stop Words
Zeile 155: Zeile 160:
  
 Nehmen wir folgendes Beispiel: Wir indexieren alle Film-Artikel der 1980er Jahre und wollen möglichst gute Suchresultate für folgende Queries: Nehmen wir folgendes Beispiel: Wir indexieren alle Film-Artikel der 1980er Jahre und wollen möglichst gute Suchresultate für folgende Queries:
-  * ''Luke Skywalker''+  * ''michael fox delorean'' 
 +  * ''michael fox'' 
 +  * ''michael fox wortdasesnichtgibt''
  
 Unsere Query-Funktion muss erstens mit mehreren Wörtern umgehen können - es bietet sich an, die `tokenize` Funktion auch hier anzuwenden und eine Suchanfrage für jedes Token in der Query durchzuführen. Die Frage ist allerdings, wie wir die einzelnen Resultatlisten kombinieren...  Unsere Query-Funktion muss erstens mit mehreren Wörtern umgehen können - es bietet sich an, die `tokenize` Funktion auch hier anzuwenden und eine Suchanfrage für jedes Token in der Query durchzuführen. Die Frage ist allerdings, wie wir die einzelnen Resultatlisten kombinieren... 
Zeile 164: Zeile 171:
 Schreibe eine neue Query-Funktion, die mehrere Wörter kombinieren kann. Welche Kombinationsmethode wählst du? Schreibe eine neue Query-Funktion, die mehrere Wörter kombinieren kann. Welche Kombinationsmethode wählst du?
  
-<nodisp 2>+<nodisp 1>
 ++++Lösung| ++++Lösung|
  
Zeile 192: Zeile 199:
  
 ### Numerisches Ranking ### Numerisches Ranking
-Die Schnittmenge scheint für die Query ''Luke Skywalker'' gut zu funktionieren, weil ''skywalker'' ein ziemlich spezifisches Wort ist, das nur in wenigen Filmen vorkommt - aber was, wenn wir eine Query ohne spezifische Wörter haben? Teste die Suche mit der Query ''luke zeitung''! +Die Schnittmenge scheint für die Query ''michael fox delorean'' gut zu funktionieren, weil ''delorean'' ein ziemlich spezifisches Wort ist, das nur in wenigen Filmen vorkommt - aber was, wenn in der Query ein Wort vorkommt, das nicht im Index ist?
-#### Aufgabe 5: Ranking mit log IDF +
-Statt eine strikte AND-Verknüpfung aller Suchterme möchten wir ein Ranking erstellen, das alle Dokumente einschliesst, die mindestens einen Suchterm enthält. Jeder Such-Begriff soll entsprechend seiner _Inverse-Document-Frequency_ (IDF) zum Rang beitragen. Das bedeutet, dass das Auftreten des seltenen Begriffs ''skywalker'' mehr zum Rang beiträgt als ein häufiges Wort wie ''zeitung''. Trotzdem sollte ein einzelnes seltenes Wort nicht alles andere ausblenden dürfen.+
  
-Damit ein einzelner Wert nicht komplett dominiert, transformieren wir die IDF-Werte mit dem Logarithmus. Die Gewichte sind damit näher beieinander:+Die Vereinigungsmenge hingegen liefert sehr viele Resultate für eine Query wie ''michael fox delorean''.
  
-{{:talit:indexing:pasted:20231204-144516.png?nolink&400}}+#### Wortfrequenzen 
 +Zuerst werden die Inverse Document Frequencies in ein Dictionary überführt, das einfach auszulesen ist:
  
 +<code python>
 +word_frequencies = {word: freq for word, freq in freqs}
  
 +table = [['Term', 'Relative Document Frequency']]
 +for token in tokenize("michael fox delorean"):
 +    table.append([token, word_frequencies[token]])
 +
 +%pip install tabulate
 +from tabulate import tabulate
 +tabulate(table, headers="firstrow", floatfmt=".2%", tablefmt='html')
 +</code>
 +
 +#### Inverse Document Frequency
 +
 +Die erste Idee wäre, die Tokens nach ihrer _document frequency_ zu gewichten: Ein Wort, das nur in einem Dokument vorkommt, ist ein guter Hinweis dafür, dass dieses in die Resultatliste gehört. Ein Allerweltswort (soweit es noch nicht durch Stopwording herausgefiltert worden ist) ist hingegen kein sehr gewichtiges Indiz, dass ein es enthaltendes Dokument wichtig ist.
 +
 +Wenn wir die Document Frequency plotten, sehen wir aber, dass die Frequenzen sehr ungleich verteilt sind:
 +
 +<code python>
 +#!pip install matplotlib
 +
 +def plot_terms(terms):
 +    import matplotlib.pyplot as plt
 +    import matplotlib as mpl
 +    import math
 +
 +    labels = [x for x, y in terms.items()]
 +    values = [y for x, y in terms.items()]
 +    fig, ax = plt.subplots() 
 +    #ax.set_yscale('log')
 +    label_count = 10
 +    label_multiple = len(terms) // label_count
 +    ax.xaxis.set_major_locator(mpl.ticker.MultipleLocator(label_multiple, 0))
 +    ax.set_xticklabels([None] + labels[0:-1:label_multiple], rotation=90)
 +    #print(labels[0:-1:label_multiple])
 +    ax.plot(values)
 +
 +plot_terms(word_frequencies)
 +</code>
 +
 +{{:talit:indexing:pasted:20240830-143037.png?nolink&400}}
 +
 +Das sieht nach einer exponentiellen Funktion aus ([[wpde>Zipfsches_Gesetz]]). Um die Werte näher zueinander zu bringen, hilft uns eine Logarithmus-Transformation - zudem invertieren wir die Werte, so dass seltene Wörter einen höheren Score haben als häufige:
 +
 +<code python>
 +import math
 +log_terms = {term: math.log(1/weight) for term, weight in word_frequencies.items()}
 +print(f"Michael: {log_terms['michael']:.2g}, Fox: {log_terms['fox']:.2g}, delorean: {log_terms['delorean']:.2g}")
 +
 +plot_terms(log_terms)
 +</code>
 +
 +{{:talit:indexing:pasted:20240830-143300.png?nolink&400}}
 +
 +#### Aufgabe 5: Ranking mit log IDF
 +Statt eine strikte AND-Verknüpfung aller Suchterme möchten wir ein Ranking erstellen, das alle Dokumente einschliesst, die mindestens einen Suchterm enthält. Jeder Such-Begriff soll entsprechend seiner _Inverse-Document-Frequency_ (IDF) zum Rang beitragen. Das bedeutet, dass das Auftreten des seltenen Begriffs ''delorean'' mehr zum Rang beiträgt als ein häufiges Wort wie ''michael''. Trotzdem sollte ein einzelnes seltenes Wort nicht alles andere ausblenden dürfen.
 +
 +<nodisp 1>
 +++++Lösung|
 +<code python>
 +def query_index_weighted(index, query, k=10):
 +    """Returns the top k search results matching query."""
 +    result_set = dict()
 +    for term in tokenize(query):
 +        idf = log_terms[term]
 +        results = index.get(term, set())
 +        for result in results:
 +            result_set[result] = result_set.get(result, 0) + idf
 +    return dict(sorted(result_set.items(), reverse=True, key=lambda item: item[1])[:k])
 +</code>
 +++++
 +</nodisp>
  • talit/indexing.1723384235.txt.gz
  • Zuletzt geändert: 2024-08-11 13:50
  • von hof