Recall und Precision

Recall, Precision und Fallout sind Maße zur Beurteilung der Güte von Treffermengen einer Recherche beim Information Retrieval. Beim allgemeineren Fall der Beurteilung eines Klassifikators werden Precision, Recall und Fallout auch als Positiver Vorhersagewert, Sensitivität und umgekehrte Spezifität bezeichnet. Alle drei Maße können Werte zwischen Null und Eins (beziehungsweise 0% bis 100%) annehmen und hängen voneinander ab. Für die Bewertung eines Rechercheverfahrens sollten sie deshalb gemeinsam betrachtet werden, zum Beispiel in einem Precision-Recall-Diagramm oder durch abgeleitete Maße. Dies ist allerdings oft nicht problemlos möglich, da nicht alle Werte bekannt sind.

Recall und Precision lassen in einer einfachen Wahrheitsmatrix aus den richtig ermittelten Treffern und falsch eingeordneten Objekten (rot) bestimmen

Definition

Der Recall gibt mit dem Anteil der bei einer Suche gefundenen relevanten Dokumente die Vollständigkeit eines Suchergebnisses an. Die Precision beschreibt mit dem Anteil relevanter Dokumente an der Ergebnismenge die Genauigkeit eines Suchergebnisses. Der (seltener gebräuchliche) Fallout bezeichnet den Anteil gefundener irrelevanter Dokumente an der allen irrelevanten Dokumenten, er gibt also in negativer Weise an, wie gut irrelevante Dokumente im Suchergebnis vermieden werden.

Als Wahrscheinlichkeiten

Statt als Maß können Recall, Precision und Fallout auch als Wahrscheinlichkeit interpretiert werden:

• Recall ist die Wahrscheinlichkeit, mit der ein relevantes Dokument gefunden wird.

• Precision ist die Wahrscheinlichkeit, mit der ein gefundenes Dokument relevant ist.

• Fallout die Wahrscheinlichkeit, mit der ein irrelevantes Dokument gefunden wird.

Als Mengenverhältnisse

Sei R die Menge relevanter Dokumente,I die Menge irrelevanter Dokumente, sowie P (für positiv) die Menge gefundener und N (für negativ) die Menge nicht gefundener Dokumente, so ergeben sich die Maße als:

• ${\mbox{Recall}}={\frac {|R\cap P|}{|R|}}$
• ${\mbox{Precision}}={\frac {|R\cap P|}{|P|}}$
• ${\mbox{Fallout}}={\frac {|I\cap P|}{|I|}}$

Es sei zu beachten, dass R und I sowie P und N als disjunkte Teilmengen zusammengenommen jeweils die Gesamtheit aller Dokumente ergeben.

Als Eigenschaften eines Klassifikators

Recall

Precision

Eine Recherche kann auch als Klassierung von Dokumenten in mutmaßlich relevante Dokumente (gefunden) und mutmaßlich nicht relevante Dokumente (nicht gefunden) aufgefasst werden. Somit kann folgendes Verfahren zur Beurteilung als Klassifikator angewandt werden, das auch bei statistische Tests Verwendung findet:

Die Grundgesamtheit aller Dokumente wird in einer Konfusionsmatrix in relevante, nicht relevante, gefundene und nicht gefundene Dokumente aufgeteilt. Es ergeben sich die vier disjunkten Teilmengen richtig gefundener, relevanter Dokumente (richtig positiv, TP), fälschlicherweise gefundener, nicht relevanter Dokumente (falsch positiv, FP), nicht gefundener, relevanter Dokumente (falsch negativ, FN) und richtigerweise nicht gefundener, nicht relevanter Dokumente (richtig negativ, TN).

Im Folgenden geben TP, FP, FN und TP die Anteile entsprechender Dokumente zwischen Null und Eins an. Im Vergleich zur Angabe durch Mengenverhältnisse gilt $|R|=TP+FN$, $|I|=FP+TP$, $|P|=TP+FP$ und $|N|=FN+TN$.

	Relevant (TP+FN)	Nicht relevant (FP+TN)
Gefunden (TP+FP)	richtig positiv (TP)	falsch positiv (FP)
Nicht gefunden (FN+TN)	falsch negativ (FN)	richtig negativ (TN)

Eine gute Recherche sollte möglichst alle relevanten Dokumente finden (richtig positiv) und die nicht relevanten Dokumente nicht finden (richtig negativ). Wird ein irrelevanten Dokument gefunden (falsch positiv), so spricht man bei Statistischen Tests auch von einem Fehler 1. Art oder α-Fehler und beim Nicht-Finden eines relevanten Dokumentes (falsch negativ) von einem Fehler 2. Art oder β-Fehler.

• Der Recall eines Verfahrens ergibt sich aus dem Verhältnis richtig positiver zu allen relevanten Dokumente $TP/(TP+FN)$. Er entspricht der statistischen Sensitivität (auch true positive rate, TPR).
• Die Precision ergibt sich aus dem Verhältnis richtig positiver zu allen gefundenen Dokumenten $TP/(TP+FP)$. Sie entspricht der statistischen Relevanz (auch Positiver Vorhersagewert).
• Der Fallout ergibt sich aus dem Verhältnis nicht gefundener, irrelevanter Dokumente (richtig negativ) zu allen nicht relevanten Dokumenten $TN/(FP+TN)$. Er entspricht der statistischen false positive rate (FPR) und ist das Gegenteil der Spezifität ($1-FPR$).

Veranschaulichung

Zur Veranschaulichung der Zusammenhänge zwischen Recall, Precision und Fallout ist es hilfreich, die Extremfälle eines Rechercheverfahrens zu betrachten:

• Wenn wenn eine Recherche alle Dokumente zurückliefert, ist der Recall maximal. Allerdings gilt dies auch für den Fallout. Die Precision hängt vom Anteil relevanter und nicht-relevanter Dokumente in der Grundgesamtheit.
• Wird nur ein einziges relevantes Dokument zurückgeliefert, ist die Precision maximal und der Fallout minimal. Allerdings dürfte der Recall sehr gering sein, er hängt von der Anzahl relevanter Dokumente ab.

Im Allgemeinen sinkt mit steigendem Recall (mehr Treffer) die Precision (mehr irrelevante Ergebnisse). Umgekehrt sinkt mit steigender Precision (weniger irrelevante Ergebnisse) der Recall (mehr relevante Dokumente die nicht gefunden werden). Es besteht also eine negative Korrelation zwischen Recall und Precision.

Precision-Recall-Diagramm

Zur Einschätzung eines Retrievelverfahrens werden meist Recall und Precision gemeinsam betrachtet. Dazu werden im so genannten Precision-Recall-Diagramm (PR-Diagram) für verschieden große Treffermengen zwischen den beiden Extremen Precision auf der Ordinate und Recall auf der Abszisse eingetragen. Dies ist vor allem leicht bei Verfahren möglich, deren Treffermenge durch einen Parameter gesteuert werden kann.

Der (höchste) Wert im Diagramm, an dem der Precision-Wert gleich dem Recall-Wert ist – also der Schnittpunkt des Precision-Recall-Diagramms mit der Identitätsfunktion – wird der Precision-Recall-Breakeven-Punkt genannt. Da beide Werte voneinander abhängen wird auch oft der eine bei fixiertem anderen Wert genannt. Ein häufiger Irrtum ist jedoch die Interpolation zwischen den Punkten werden, es handelt sich jedoch um diskrete Punkte, deren Zwischenräume nicht definiert sind!

Eine Alternative zum PR-Diagramm ist eine ROC-Kurve, die auch als Fallout-Recall-Diagramm bezeichnet werden könnte.

Abgeleitete Maße

Einfache Maße

Aus der Konfusionsmatrix lassen sich zur Beurteilung einer Recherche neben Precision, Recall und Fallout weitere Maße ableiten:

• Die Irrtumswahrscheinlichkeit oder Falschklassifikationsrate $(FP+FN)/(TP+FP+FN+TN)$ gibt an, mit welcher Wahrscheinlichkeit ein Dokument durch Nicht-Finden bzw. Finden falsch eingeordnet wurde, da es tatsächlich relevant bzw. nicht relevant war.
• Die Irrtumsunwahrscheinlichkeit oder Korrektklassifikationsrate $(TP+TN)/(TP+FP+FP+TN)$ ist das Gegenteil der Irrtumswahrscheinlichkeit, also der Anteil richtig eingeschätzter Dokumente.
• Der Negative Vorhersagewert $TN/(FN+TN)$ gibt die Wahrscheinlichkeit dafür an, dass ein nicht gefundenes Dokument auch tatsächlich irrelevant ist.
• Die Falscherkennungsrate (auch false discovery rate, FDR) $FP/(TP+FP)$ ist der Anteil irrelevanter Dokumente, die gefunden wurden.

Je nach Anwendungsfall sind die unterschiedlichen Maße zur Beurteilung mehr oder weniger relevant. Bei einer Patentrecherche ist es beispielsweise wichtig, dass keine relevanten Patente unentdeckt bleiben (Fehler 2. Art), also sollte der Negative Vorhersagewert möglichst hoch sein. Bei anderen Recherchen ist es wichtiger, dass die Treffermenge wenig irrelevante Dokumente enthält, d.h. der Positive Vorhersagewert sollte möglichst hoch sein.

Kombinierte Maße

Zur Beurteilung der Güte mit einer einzigen Kennzahl wurden verschiedene Maße vorgeschlagen.

Das F-Maß kombiniert Precision und Recall mittels des gewichteten harmonischen Mittels (?):

$F=2\cdot (\mathrm {precision} \cdot \mathrm {recall} )/(\mathrm {precision} +\mathrm {recall} ).\,$

Neben diesem auch als $F_{1}$ bezeichneten Maß, bei dem Precision und Recall gleich gewichtet sind, gibt es auch andere Gewichtungen. Der Allgemeinfall ist das Maß $F_{\alpha }$ (für postive Werte von $\alpha$):

$F_{\alpha }=(1+\alpha )\cdot (\mathrm {precision} \cdot \mathrm {recall} )/(\alpha \cdot \mathrm {precision} +\mathrm {recall} ).\,$

Beispielsweise wichtet $F_{2}$ den Recall doppelt so groß wie die Precision und $F_{0.5}$ die Precision doppelt so hoch wie den Recall.

Das Effektivitätsmaß (E) entspricht ebenfalls dem gewichteten harmonischen Mittel. Es wurde von van Rijsbergen (?) entwickelt. Die Effektivität liegt zwischen 0 (beste Effektivität) und 1 (schlechte Effektivität). Erreicht die Effektivität den Wert 0, so ist sie auf den Recall (R) reduziert. Erreicht sie den Wert 1 ist sie auf die Precision (P) reduziert:

$E=1-{\frac {1}{a({\frac {1}{P}})+(1-a){\frac {1}{R}}}}$

Beispiel

Beispiel (siehe Text)

In einer Datenbank mit 36 Dokumenten sind zu einer Suchanfrage Dokumente 20 relevant und 16 nicht relevant. Eine Suche liefert 12 Dokumente, von denen tatsächlich 8 relevant sind. In nebenstehender Grafik sind die relevanten Dokumente links, die nicht relevanten rechts, und die gefundenen Dokumente innerhalb des Ovals eingezeichnet. Die übereinstimmenden Fälle sind grün und die Fehler rot.

	Relevant	Nicht relevant
Gefunden	8	4
Nicht gefunden	12	12

Recall und Precision für die konkrete Suche ergeben sich aus den Werten der Konfusionsmatrix.

• Precision: $8/(8+4)=8/12=2/3\approx 0,67$
• Recall: $8/(8+12)=8/20=2/5=0,4$
• Fallout: $12/(4+12)=12/16=3/4=0,75$

Praxis und Probleme

Ein Problem bei der Berechnung des Recalls ist die Tatsache, dass man nur selten weiß, wie viele relevante Dokumente insgesamt existieren und nicht gefunden wurden (c, Fehler 2. Art). Bei größeren Datenbanken, bei denen die Berechnung des absoluten Recalls besonders schwierig ist, wird deswegen mit dem relativen Recall gearbeitet. Dabei wird die gleiche Suche mit mehreren Suchmaschinen durchgeführt und die jeweils neuen relevanten Treffer zu den nicht gefundenen relevanten Dokumenten hinzu addiert. Mit der Rückfangmethode kann abgeschätzt werden, wie viele relevante Dokumente insgesamt existieren.

Problematisch ist auch, dass zur Bestimmung von Recall und Precision die Relevanz eines Dokumentes als Wahrheitswert (ja/nein) bekannt sein muss. In der Praxis ist jedoch oft die Subjektive Relevanz von Bedeutung. Auch für gerankte Treffermengen ist die Angabe von Recall und Precision oft nicht ausreichend, da es nicht nur darauf ankommt, ob ein relevantes Dokument gefunden wird, sondern auch ob es im Vergleich zu nicht relevanten Dokumenten genügend hoch gerankt wird. Bei sehr unterschiedlich großen Treffermengen kann die Angabe durchschnittlicher Werte für Recall und Precision irreführend sein.

Literatur

• Makhoul, John; Francis Kubala; Richard Schwartz; Ralph Weischedel: Performance measures for information extraction. In: Proceedings of DARPA Broadcast News Workshop, Herndon, VA, February 1999.

• Baeza-Yates, R.; Ribeiro-Neto, B. (1999). Modern Information Retrieval. New York: ACM Press, Addison-Wesley. Seiten 75 ff. ISBN 0-201-39829-X

• Womser-Hacker, Christa: Theorie des Information Retrieval III: Evaluierung. In R. Kuhlen: Grundlagen der praktischen Information und Dokumentation. München. Saur, 5. Auflage 2004. Seiten 227-235. ISBN 3-598-11675-6, ISBN 3-598-11674-8

• van Rijsbergen, C.V.: Information Retrieval. London; Boston. Butterworth, 2nd Edition 1979. ISBN 0-408-70929-4

• Jesse Davis und Mark Goadrich: The Relationship Between Precision-Recall and ROC Curves. In: 23rd International Conference on Machine Learning (ICML), 2006.

Weblinks

• Information Retrieval – C. J. van Rijsbergen 1979