Embed Size (px)
Citation preview
© Prof. Kießling 2015 Kap. 1 - 1
Vorlesung Suchmaschinen
Universität Augsburg
Sommersemester 2015
Prof. Dr. Werner Kießling
Institut für Informatik
Lehrstuhl für Datenbanken und Informationssysteme
© Prof. Kießling 2015 Kap. 1 - 2
Klausur
Termin: steht noch nicht fest Dauer: 90 Minuten Nur Papierunterlagen sind zugelassen (open book) Anmeldung bei STUDIS zwingend erforderlich!
Näheres unter: http://www.informatik.uni-augsburg.de/lehrstuehle/dbis/db/lectures/ss15/se/exams/
© Prof. Kießling 2015 Kap. 1 - 3
Vorlesungsbetrieb
• Zwei Vorlesungen pro Woche im Hörsaal 2045 (N)
• Dienstag, 10:00 – 11:30 Uhr
• Donnerstag, 10:00 – 11:30 Uhr
• Folien der Vorlesung sind spätestens am jeweiligenVorlesungstag im Internet verfügbar
http://www.informatik.uni-augsburg.de/lehrstuehle/dbis/db/lectures/ss15/se/scripts/
Benutzername und Passwort: rz-Kennung
• Regelmäßig nach Aktuellem auf der Homepage schauen!
© Prof. Kießling 2015 Kap. 1 - 4
Übungen
Übungsblätter werden jeweils freitags auf der Homepage veröffentlicht Es wird davon ausgegangen, dass die Blätter vor dem Übungstermin
angesehen / bearbeitet werden Während der Übung:
– Erarbeitung der wichtigsten Aufgaben in Kleingruppen mit Tutoren– Präsentation und Diskussion der erarbeiteten Ergebnisse am Smartboard
Keine Punktevergabe, keine Zulassungsbedingung zur Klausur
© Prof. Kießling 2015 Kap. 1 - 5
Kontakt
• Prof. Dr. W. Kießling:
Sprechstunde: Dienstag, 11:45-12:45
• Florian Wenzel und Lena Rudenko
{wenzel, lena.rudenko}@informatik.uni-augsburg.de
© Prof. Kießling 2015 Kap. 1 - 6
Gliederung
1 Einführung
2 Volltext-Suchmaschinen
3 Präferenz-Theorie
4 Preference SQL-System
5 Implementierung von Präferenz-Querysprachen
6 Top-k-Algorithmen
7 XML-Suchmaschinen
8 Softwareaspekte von SQL-Suchanwendungen
© Prof. Kießling 2015 Kap. 1 - 7
Übungsgruppen
Gruppe Zeit Raum
1 DI, 12:15 – 13:45 Uhr 2056 (N)
2 DI, 15:45 – 17:15 Uhr 2056 (N)
3 MI, 12:15 – 13:45 Uhr 2056 (N)
4 FR, 10:00 – 11:30 Uhr 2056 (N)
http://www.informatik.uni-augsburg.de/lehrstuehle/dbis/db/lectures/ss15/se/groups/
© Prof. Kießling 2015 Kap. 1 - 8
Allgemeine LiteraturDirk Lewandowski (Hrsg.):Handbuch Internet-Suchmaschinen 2: Neue Entwicklungen in der Web SucheAkademische Verlagsgesellschaft AKA GmbH, Heidelberg, 2012;ISBN: 978-3-89838-651-7
Christopher D. Manning, Prabhakar Raghavan, Hinrich Schütze:Introduction to Information Retrieval, Cambridge University Press; 2008; ISBN: 978-0-521-86571-5
Marc Levene: An Introduction to Search Engines and Web Navigation, 2nd Edition, Wiley,2010; ISBN: 978-0-470-52684-2
Ricardo Baeza-Yates & Berthier Ribeiro-Neto:Modern Information Retrieval, 2nd Edition, New York, NY: ACM PressBooks; 2010; ISBN: 978-0-321-41691-9
© Prof. Kießling 2015 Kap. 1 - 9
1 Einführung1.1 Unterschiedliche Suchverfahren
1.2 Überblick IR-Systeme
1.3 Überblick Web-Suche
1.4 Überblick Attribut-Suche
1.5 Überblick Multimedia-Suche
1.6 Überblick Soziale Netzwerke
1.7 Mobile Dienste
1.8 Metasuchmaschinen
1.9 Google Analytics
1.10 Zusammenfassung
„I will use Google before asking dumb questions.“
Quelle: http://www.flickr.com/photos/deia/7942538/
© Prof. Kießling 2015 Kap. 1 - 10
1.1 Unterschiedliche Suchverfahren
Wichtigste Komponente für ein Such-System ist die Menge der Dokumente, Korpus genannt, und deren interne Struktur. Der Korpus kann
unstrukturiert semi-strukturiert oder auch strukturiert sein.
Such-System
Anfrage
Korpus vonDokumenten
Ergebnis
© Prof. Kießling 2015 Kap. 1 - 11
Dokumente können sein:
Artefakte (z.B. gescannte Bücher) Kataloge (z.B. Branchenbücher) Linksammlungen (Webkataloge) Videosammlungen (YouTube) Soziale Daten (z.B. Facebook) Dateien (z.B. Excel, PDF, Text, HTML, XML, …) …
© Prof. Kießling 2015 Kap. 1 - 12
Beispiel: Suche nach Buch im Antiquariat
1.) Stöbern Struktur (Sachgebiet, Thema, Autor, …) v.v. „Chaos“ „Navigation“, „blinde Suche“, „glücklicher Zufall“
2.) Dialog Zweck, Absicht, Ziel Fragen - Antworten Benutzer-Modellierung Hintergrundwissen „Gezielte Suche“
Antiquar
Empfehlungen
Relevanz?
Frage
© Prof. Kießling 2015 Kap. 1 - 13
Soziale Vernetzung
Mit Hilfe von sozialen Vernetzungen (Freundes-, Kollegenkreis, …) kann ein Suchvorgang gleichzeitig von mehreren Teilnehmern ausgeführt werden.
Für den Erfolg dieser Vorgehensweise ist wichtig: Hoher Vernetzungsgrad (Navigation), verteilter Korpus Gemeinsamer Code, klare Spezifikation Terminierung, Qualität und Quantität der Ergebnisse
Anfrage Ergebnis
Freundeskreis als Such-System
© Prof. Kießling 2015 Kap. 1 - 14
Beispiel: Wohnungssuche
1.) Suchanfrage über eigene soziale Netzwerke streuen und auf hohen Verbreitungsgrad hoffen.
2.) Gemeinsamer Code (Wohnungen und ihre Eigenschaften)
3.) Klare Spezifikation (Größe, Preis, Typ)
4.) Bewertung der Ergebnisse erfolgt auch nach weiteren (meist nicht vollständig kommunizierten) weichen Faktoren.
5) Meistens wird man unter den ersten k Rückmeldungen fündig (Top-k-Suche).
© Prof. Kießling 2015 Kap. 1 - 15
Eigenschaften von sozialen Netzen:
● Mitglieder von sozialen Netzen können sich ihrerseits auch wieder auf andere soziale Netze abstützen.
● Mitglieder von sozialen Netzen können aber auch automatische Suchsysteme, Spezialisten, Bibliotheken, … zu Rate ziehen.
● Die Kommunikation (Aussage, Frage – Antwort) erfolgt asynchron.
© Prof. Kießling 2015 Kap. 1 - 16
1.2 Überblick IR-Systeme
Suche nach Information in Bibliothek
IR-System
Anfrage
Korpus vonDokumenten
GewichteteDokumente
1. Doc12. Doc23. Doc3…
Relevanz?
InformationRetrieval
© Prof. Kießling 2015 Kap. 1 - 17
Beispiel: Anfrage nach Veröffentlichung in BibliothekOPAC der UB Augsburg:
© Prof. Kießling 2015 Kap. 1 - 18
Eigenschaften von OPAC:
Korpus (Katalog) abgeschlossen, geringe ÄnderungsrateSuchmöglichkeiten:
Autor, Schlagwort, … Attributsuche Logische Verknüpfungen Boolesche Algebra Trunkierungszeichen Wildcards: “?“, “*“ Freie Suche keine Volltextsuche dank
Digitalisierung des Korpus
Filter / Navigation: Suche eingrenzen Annotationen, sem. Kategorien BibTip Andere Benutzer fanden Empfehlungen durch Analyse
auch interessant des Benutzerverhaltens
© Prof. Kießling 2015 Kap. 1 - 19
Exemplarische Trefferliste: Autor = Kießling, Navigationshilfen
© Prof. Kießling 2015 Kap. 1 - 20
Exemplarischer Treffer: Attribute – digitalisierter Text(ausschnitt)
© Prof. Kießling 2015 Kap. 1 - 21
OPAC-Beispiele (Kardinalität der Ergebnismenge aus SS2010, SS2015):
Freie Suche „Preference und Algebra“ Leere Ergebnismenge (0, 0) Freie Suche „Kießling“ Überflutung (283, 391) Attributsuche: Autor „Kießling“ Relevanz (171, 202) Attributsuche: Autor „Kie?ling“ Korrektheit (-, 29) A.-Suche: Autor „Werner Kießling“ Relevanz (25, 31) Kießling, Kiessling automat. Graphemerweiterung
© Prof. Kießling 2015 Kap. 1 - 22
Digitalisierung von Buchbeständen: Volltextsuche
Beispiele: Google Book Search Search Inside! von Amazon
Rechtliche Probleme bei noch geschützten Werken: Urheberrechte Nutzungsrechte, Verwertungsrechte
© Prof. Kießling 2015 Kap. 1 - 23
Suche nach Information in Wikipedia
IR-System
Anfrage
Korpus vonDokumenten
GewichteteDokumente
1. Doc12. Doc23. Doc3…
Relevanz?
Autoren:
© Prof. Kießling 2015 Kap. 1 - 24
Beispiel: Anfrage nach Artikel (Konzept) in Wikipedia
Wikipedia
Korpus (Online-Enzyklopädie) geschlossener Korpus bezogen auf http://de.wikipedia.org/, offener und „kleiner“ Autorenkreis im sozialem Netzwerk, Kollaboration [Bearbeiten],
Suchmöglichkeiten: Artikel (Von A bis Z) Konzeptsuche Piktogramm Lupe Volltextsuche, Syntax Verlinkung Semantisches Netzwerk Links auf diese Seite Verweisstruktur (Backlinks)
© Prof. Kießling 2015 Kap. 1 - 25
1.3 Web-Suche
Websuche-Technologie stammt ursprünglich von IR-Systemen.
1993: der erste Such-Roboter „The Wanderer“ im WWW
„The Wanderer“ durchsuchte und katalogisierte von 1993 bis 1996 halbjährlich das zu dieser Zeit noch sehr übersichtliche Web. Im Juni 1993 gab es nur 130 Websites.
1995: erste Suchmaschinen von kommerziellen Firmen (Infoseek, Alta Vista, …)
© Prof. Kießling 2015 Kap. 1 - 26
1.3.1 Architektur Websuche
Web Spider
Such-System
Anfrage
Korpus vonDokumenten
GewichteteDokumente
Relevanz?
Spider
© Prof. Kießling 2015 Kap. 1 - 27
Im Unterschied zu einem IR-System, bei dem der Korpus eher geschlossen und statisch ist, wächst das Web kontinuierlich, und auch bereits erfasste Inhalte ändern sich.
Der Korpus des Webs ist offen und dynamisch, deswegen werden zusätzliche Komponenten benötigt.
Ein Spider (auch "Crawler" oder "Robot" genannt) bewegt sich durch das Verfolgen von Links selbständig durch den Datenbestand des Internets und ermittelt die Inhalte der Webseiten.
© Prof. Kießling 2015 Kap. 1 - 28
Web
TODO:Liste vonURLs
Auswahl Laden
Seiteindizieren
Füge URLsvon Links
hinzu
Extraktion
Spider:
Verfeinerung Spider
© Prof. Kießling 2015 Kap. 1 - 29
Wichtigstes Merkmal neben der Anzahl der erfassten Seiten ist die Update-Rate, wodurch neuer oder geänderter Inhalt erfasst wird.
Bei Google wird dies als „Google Dance“ bezeichnet:
Bis 2003 wurden die Suchindizes einmal monatlich neu berechnet. Inzwischen läuft der Update-Prozess kontinuierlich.
Trotzdem gibt es Seiten, die nicht erfasst werden bzw. nicht erfasst sein wollen (Deep Web).
© Prof. Kießling 2015 Kap. 1 - 30
In den meisten Fällen ist man natürlich an einer Anmeldung interessiert:• Google (Bekanntmachung für Spider per http://www.google.de/addurl/)• Beschreibung der eigenen Webstruktur z.B. durch Sitemaps
Über das Robots Exclusion Protocol kann ausgeschlossen werden, dass Seiten vom Crawler besucht werden.
© Prof. Kießling 2015 Kap. 1 - 31
Um der großen Datenmenge Herr zu werden, extrahiert ein Merkmalsextraktor relevante Merkmale und Texte aus den gefundenen Webseiten. Durch die Merkmalsextraktion wird die Datenmenge bereits deutlich verkleinert (Korpus).
Um die grammatikalische Komplexität (Flexion) zu reduzieren, werden Wörter durch Text-Operationen auf ihren Wortstamm zurückgeführt (Stemming).
Einer der bekannteste Algorithmen ist der Porter-Stemmer.
Zudem werden Füllwörter (Artikel, …) entfernt (Stopword removal),
da sie oft nur grammatikalische Informationen tragen.
© Prof. Kießling 2015 Kap. 1 - 32
Um über die Suchbegriffe wieder auf die Originale zurück schließen zu können, verwaltet der Indexierer die extrahierten Merkmale und Texte der Dokumente und erlaubt den schnellen Zugriff auf die Originale über diese Merkmale und Texte.
Dieser Suchindex wird als „Invertierter File“ implementiert. Er hat die gleiche Funktion wie ein Schlagwortregister, das Schlagwörter denjenigen Buchseiten zuordnet, in denen das Schlagwort vorkommt.Beispiel:
Unter einem blauenHimmel trafen …
ID Term Dokument : Position
…
n blau i : 3, j : 4
n+1 Himmel i : 4, j : 7
…
Montags machen viele blau. Unter freiem Himmel …
Di:
Dj:
© Prof. Kießling 2015 Kap. 1 - 33
Verfeinerung Websuche
DokumentDB
Datenbank-Manager
Indexierung
Index
Anfrage-Operationen
Suche
BewertungBewertete
Dokumente
Text-Operationen
Ergebnis-menge
Reformu-lierung
Logische Sicht
AnfrageSuch-System:
Spider
Invertierter File
© Prof. Kießling 2015 Kap. 1 - 34
1.3.2 Navigationsanfragen im Web
Beispiel: Navigation per Links
Ziel: Ich will mich über Vorlesungen des Lehrstuhls für „Datenbanksysteme“ informieren.
Einstieg per URL
http://www.informatik.uni-augsburg.de/de/lehrstuehle/
Ergebnis:
Durch die Linkstruktur in HTML werden die Lehrstühle thematisch so strukturiert, dass die Informationsbedürfnisse der Leser (hoffentlich vollständig) erfüllt werden. Der Leser erschließt nach den eigenen Bedürfnissen die Struktur der Webseite per Navigation.
Hypertext, HTTP, (X)HTML, serverseitiges Skripting (Java, Servlet, Python,
PHP, …), clientseitiges Skripting (JavaScript, Applet, AJAX)
© Prof. Kießling 2015 Kap. 1 - 35
Beispiel: Semantikunterstützte Navigation in a priori definierten Kategorien per Hierarchischer Suche
Ziel: Ich will mich mal grob um eine Urlaubsreise im Sommer kümmern. Einstieg per Portal:
Yahoo (Yet Another Hierarchical Officious Oracle):– Vordefinierte Hierarchien zur Navigation, z.B.
Regional → Countries → Germany → States → Baveria → Cities– Begrenzte Auswahl an Ergebnissen da von Menschen erstellt & verwaltet
DMOZ (open directory project):
- ähnlich zu Yahoo, z.B.Regional → Europe → Germany → States → Baveria → Localities
© Prof. Kießling 2015 Kap. 1 - 36
Ergebnis:
Exploratives Suchen in Kategorien keine einheitlichen Kategorien und Relationen für die Semantik einer
Applikation Anzahl der in einer Kategorie gesammelten Konzepte ist angegeben
Hierarchische Suche wird immer mehr durch Volltextsuche verdrängt. Hierarchische Suche, die einen Bezug zu geographischen Inhalten hat,
wird durch Oberflächenelemente wie interaktive Maps versteckt.
© Prof. Kießling 2015 Kap. 1 - 37
1.3.3 Suchanfragen im WebKorpus (WWW):
Offen Dynamisch, indizierter Inhalt ändert sich! Unentdeckte „Kontinente“ (Deep Web)
Suchmöglichkeiten: Stichwörter für Volltextsuche
Erweiterte Suche: (z.B. Google) Logische Verknüpfungen Wildcard-Suche Zahlenbereiche Ortsspezifische Suche per Domain-Einschränkung
Leere Ergebnismenge, Überflutung , Relevanz
© Prof. Kießling 2015 Kap. 1 - 38
Welche Suchbegriffe muss man wählen, um mit ihnen relevante Quellen zu finden? Ein Hinweis gibt das Zipfsche Gesetz:
Der Rang i eines Wortes ist indirekt proportional zu seiner rel. Häufigkeit:
Freq(Worti) = i-ϴ x Freq(Wort1),
wobei 1,5 < ϴ < 2 für die meisten Sprachen gilt (Potenzverteilung).Beispiel: Für ϴ = 1 besitzt das 2. häufigste Wort eine
Häufigkeit von 1/2 des häufigsten Wortes.
• Zone I: Sehr häufige Wörter sind meist funktionale Wörter (der, die, und, …). • Zone II: Mittelhäufige Wörter erschließen einen Text am besten.• Zone III: Seltene Wörter sind häufig Tipp-fehler oder zu spezifische Wörter (Ranb, Freq., Hornussen, …).
Rang i
Freq(Worti)
I II III
Zipfsches Gesetz
© Prof. Kießling 2015 Kap. 1 - 39
Folgerungen aus dem Zipfschen Gesetz:
Positiv: Füllwörter machen einen großen Anteil von Texten aus. Die Eliminierung von Füllwörtern hat keinen Einfluss auf das Retrieval, erspart jedoch Speicher.
Negativ: Für die meisten Wörter ist eine signifikante statistische Analyse (z.B. Korrelationsanalyse) schwer zu erzielen, da die Wörter in einem Korpus zu selten auftreten.
Beispiel:Sprachabhängige Worthäufigkeiten, englische Worthäufigkeiten
© Prof. Kießling 2015 Kap. 1 - 40
Beispiel: Verknüpfte Stichwortsuche
Welche Zulassungsbedingungen müssen eingehalten werden, um an der Klausur in Datenbanksysteme I teilnehmen zu dürfen?
Wunschseite:
Suche mit Google
Ergebnisse aus SS15:
Von den 42.000 Treffern finden sich auf Position 1 und 2 Dokumente des Lehrstuhls. Ein Ortsbezug wird automatisch hergestellt. Das gewünschte Dokument fehlt. Fehlende Relevanz
http://www.informatik.uni-augsburg.de/de/lehrstuehle/dbis/db/lectures/ws1415/datenbanksysteme1/exams/
© Prof. Kießling 2015 Kap. 1 - 41
1. Änderung: Domänenbezug erzwingen durch Domain-Einschränkung auf www.uni-augsburg.de
Suche mit Google
Ergebnis:
Die beiden zuvor gefunden Dokumente mit Bezug zum Lehrstuhl werden nicht mehr gefunden, da sie aus Subdomains der Uni Augsburg stammen.
SS15: keine Treffer
© Prof. Kießling 2015 Kap. 1 - 42
3. Änderung: ganz genauen Domänenbezug hinzunehmen www.informatik.uni-augsburg.de
Suche mit Google
Ergebnisse aus SS15:Es werden durch die Domain-Einschränkung 8 Treffer angeboten. Der 2. Treffer bietet zwar das Klausurdatum korrekt an, aber nicht die Zulassungsbedingungen. Es ist keine einfache Navigation möglich.Nur der 4. Treffer beinhaltet die von uns gewünschten Informationen.
Relevanz
© Prof. Kießling 2015 Kap. 1 - 43
Stand der Dinge:
Iteratives Vorgehen
(Suche im „Heuhaufen“ geeignetere (!) Stichwörter, Filterfunktionen der Suchmaschine wie z.B. Domain)
Solange keine Zufriedenheit mit dem Suchergebnis besteht,
1. Abfrage(re)formulierung,
2. [Selektion],
3. [Navigation].
© Prof. Kießling 2015 Kap. 1 - 44
Bei der Stichwortsuche ist ein häufiges Phänomen eine leere Ergebnismenge (empty result set) bzw. als Alternative eine Überflutung (flooding effect) durch meist irrelevante Dokumente.
Beide Phänomene erschweren, dass Benutzer relevante Treffer entdecken können.
Um die Relevanz der Treffer zu erhöhen, bieten sich Modelle an, die semantische Zusatzinformationen bei der Suche bzw. Navigation ins Spiel bringen:
Stichwortsuche mit Unterstützung von in Beziehung stehenden semantischen Kategorien (Semantische Netzwerke, Ontologien, Taxonomien)
Attributsuche (Schemata) Präferenzen (Benutzermodelle)
© Prof. Kießling 2015 Kap. 1 - 45
Beispiel: Stichwortsuche nach mehrdeutigem Wort „Saturn“ in verschiedenen Suchräumen
Ergebnis: Die Suche in Kategorien erhöhte die Relevanz der Treffer, da irreführende Synonyme ausgeschlossen sind. Das Erstellen von Kategorien sowie die Zuordnung von Dokumenten zu Kategorien erfordert jedoch redaktionellen Zusatzaufwand bzw. gemeinschaftliches Indexieren (social tagging, folksonomy).
Korpus Treffer (SS07) (SS15)
1. Web, Suche mit Google 54.100.000 143.000.000
2a. Gesamtverzeichnis, Suche mit Google
66.500 2012: Semantische Suche abgeschaltet
2b. Verzeichnis „Wissenschaft“, Suche mit Google
189 2012: Semantische Suche abgeschaltet
© Prof. Kießling 2015 Kap. 1 - 46
Stichwortsuche mit semantisch richtigen, aber nicht im Korpus verwendeten Stichwörtern
Beispiele (Ergebnisse aus SS15): Suche Zahnarzt (479.000) / Dentist (221.000) in Augsburg? Suche Zahnarzt OR Dentist (500.000) in Augsburg? Synonymsuche z.B. ~Dentist in Augsburg bei Google (221.000)?
Ergebnis:
Die Suche erfolgt nur anhand von Wörtern nicht Konzepten.
Stichworterweiterung aus Synonymwörterbücher,
VerODERung mit Synonymen oder themenrelevante Vorschläge
© Prof. Kießling 2015 Kap. 1 - 47
Beispiele: Stichwortsuche mit Unterstützung durchsemantisches / linguistisches Wissen
Beispiele: Suche nach Alfons Huhn als Bild bei Flickr
Bis 2013 alternative Vorschläge nach leerer Ergebnismenge wie “chicken“, 2015 leere Ergebnismenge
Suche nach Information Retrieval bei Ask.com Bis 2013 Möglichkeit von semantischen Anfrageerweiterungen bzw. Anfrageeinengungen (wissensbasiert), 2015 statistikbasierte Termerweiterungen
Ergebnis:Semantisches / linguistisches Wissen wird durch statistikbasiertes Wissenersetzt.
© Prof. Kießling 2015
Beispiel: Volltextsuche und PlagiarismusWelchen Autoren lässt sich der Text "Let us exemplify the unsatisfying state of the art" zuschreiben?
Suche mit Google
Ergebnis:
Textstellen, insbesondere Zitate, lassen sich hervorragend mit Volltext-suche überprüfen.
Ergebnisse 1 - 1 von ungefähr 1 für "Let us exemplify the unsatisfying state of the art". (0,27 Sekunden, SS2007)
SS2015: 4 URLs der gleichen Quelle
Kap. 1 - 48
© Prof. Kießling 2015 Kap. 1 - 49
1.4 Überblick Attribut-Suche
Voraussetzung für eine Attribut-Suche sind strukturierte Daten. Diese werden im Normalfall durch Schemata beschrieben. Standardmäßig kommt eine Datenbank im Backend zum Einsatz:
Im Unterschied zur Stichwortsuche ist bei einer Attributsuche ein exaktes Daten-Retrieval möglich.
Web-Applikationen verstecken das Datenmodell, die dazu gehörenden Schemata und die Ablauflogik.
Eingabefelder erlauben die Selektion und Projektion der gewünschten Daten.
Beispiel: Reiseauskunft bei der DB
© Prof. Kießling 2015 Kap. 1 - 50
Bei der Attributsuche mit exakten Treffern (exact match) treten die
bekannten Phänomene auf:
1. Leere Ergebnismenge (empty result set)
2. Überflutung (flooding effect)
3. Eine Bewertung (ranking) ist nicht möglich.
Viele Datenbanksysteme kombinieren die Attribut- mit der Volltextsuche
wie z.B. „Oracle Text“ von Oracle.
© Prof. Kießling 2015 Kap. 1 - 51
Bemerkung (Warnung):
Webseiten, die dynamisch durch Attributsuche generiert werden, können nicht indiziert werden, da der Spider sonst alle möglichen Eingabe-Kombinationen ausprobieren müsste ( Deep Web).
Die Ergebnisse von Fachdatenbanken mit einem Web-Frontend liegen aus dem gleichen Grund im Deep Web trotz einer guten Ergebnisqualität.
Die Stichwortsuche kann in diesen Fällen also nur dazu benutzt werden, geeignete Fachportale zu finden.
„I will use Google before asking dumb questions.“
© Prof. Kießling 2015 Kap. 1 - 52
Beispiel: Elektronischer Handel (E-Commerce)
B2C (Business-to-Consumer)
Ecommerce-System
Anfrage
GewichteteWaren
1. Ware1 Kauf!2. Ware2 Kauf!3. Ware3 Kauf!…
Relevanz?
Kauf!
DB
© Prof. Kießling 2015 Kap. 1 - 53
Beispiel 1: Mieten einer Wohnung
Online-Immobilienmakler Korpus (Immobilienbestand) abgeschlossen, rel. geringe ÄnderungsrateSuchmöglichkeiten:
Reiter, Überschriften Kategorien, Navigation Suchfenster Attributsuche, hierarchische Suche Hintergrundwissen Geographisches Informationssystem (GIS)
Beispiel: Wohnen, Augsburg … , Mietwohnungen(SS07) Salomon-Idler, Umkreis Automat. Erweiterung um Univiertel,
ab SS08: „Radius“(SS15) #Zimmer, Fläche, Preis Leeres Ergebnis bei zu geringem Preis
Parametrische Suche (Synonym Facettensuche)
© Prof. Kießling 2015 Kap. 1 - 54
Seit SS2013
Vorschläge für Autovervollständigung (z.B. STARTS WITH “Augs“) der Benutzereingabe auf mehreren geographischen Konzeptebenen:
- Orte, Kreise, Bezirke und Gemeinden, Straßen
Parallele, konzeptspezifische Suche mit Beschränkung der konzeptspezifischen Ergebnismenge durch Ranking mit LIMIT=5 wegen beschränkter Fenstergröße des Auswahlfensters
http://www.immobilienscout24.de/de/finden/wohnen/index.jsp
© Prof. Kießling 2015 Kap. 1 - 55
Seit SS2013
Ziel: Vermeidung der leeren Ergebnismenge! Zulässige Vergleichsoperatoren sind nur ≤ und ≥. Dynamische Anzeige der Trefferanzahl in Abhängigkeit von jedem
Parameter
Frühere attributbasierte Suche ist ersetzt durch Parametrische Suche mit 4 Attributen, wobei WO und WAS für den Anwender als Prefilter wirken.
© Prof. Kießling 2015 Kap. 1 - 56
SS2014
Ziel: Vermeidung der leeren Ergebnismenge! Großzügige semantische Auslegung von „Mietwohnung“ nach Eingabe
Preis ≤ 200 EUR, #Zimmer: egal, ab 20m2, Radius: 10km
© Prof. Kießling 2015 Kap. 1 - 57
Suche anpassen: Anzeige aller vorhandenen Parameter
© Prof. Kießling 2015 Kap. 1 - 58
Beobachtung:
In Abhängigkeit vom Datenbestand und der Anfrage können bei
der Attribut-Suche zwei Phänomene auftauchen:
1. Leere Ergebnismenge (empty result set)
2. Viel zu große Ergebnismenge (flooding effect)
Mit Hilfe der „Parametrischen Suche“ wird der Einfluss von
Attributen auf die Größe der Ergebnismenge visualisiert und damit
dem Benutzer ein Feedback auf seine Aktionen gegeben.
© Prof. Kießling 2015 Kap. 1 - 59
Parametrische Suche
Beispiel 2: Auswahl von Elektronikware
Preisvergleich (z.B. Fernseher) bei Idealo
Ergebnis:
Nach einem hierarchischen Suchvorgang gelangt man zu einer Startseite für eine parametrische Suche. Bei einer parametrischen Suche wird durch die Benutzerauswahl eines Attributwertes die Ergebnismenge eingeschränkt.
Die Ergebnismenge kann dann durch Auswahl weiterer Attributwerte iterativ eingeschränkt werden, dabei kann auch eine leere Ergebnismenge auftreten. Durch Rücknahme von Einschränkungen kann sich die Ergebnismenge wieder vergrößern. Die Kardinalität der Ergebnismenge der momentanen Selektion ist (meistens) angegeben.
Die Vorgehensweise entspricht einer iterativen Navigation bezüglich der Attribute des Suchraums.
© Prof. Kießling 2015 Kap. 1 - 60
1.5 Übersicht Multimedia-SucheSuche in Multimediabeständen bestehend aus
Bildern, Audios, Videos.
Multimediasuche findet meist in textuell erschlossenen Beständen ab. Die Erschließung findet in sozialen Netzwerken durch Annotierungen (Tagging) mit Hilfe eines offenen Vokabulars statt.
Für die professionelle Annotierung existieren z.B. spezifische XML-Sprachen wie MPEG-7 (siehe Schema).
Beispiele: Videos mit den Annotierungen „Clinton“ „1984“ ● YouTube● Yahoo
© Prof. Kießling 2015 Kap. 1 - 61
Praktisches Beispiel: Google Bildersuche
Suche Bild aus tz aus der Wochenendausgabe vom 11./12.11.06:
© Prof. Kießling 2015 Kap. 1 - 62
Aus dem Zeitungsartikel, in dem das Bild eingebettet ist (Erschließung über Umgebungstext), kann der Leser folgende Stichwörter entnehmen:
1. Versuch: saturn, ring, earth, cassini
(SS07: 79.400, seit SS13: Anzahl wird nicht mehr angezeigt.) 2. Versuch: saturn, eclipse, 2006-09-15, cassini
(SS07: 215, seit SS13: Anzahl wird nicht mehr angezeigt.)
Aus der Ergebnismenge von Google-Bildsuche kann bislang nur durch (menschliche) Analyse das gesuchte Bild und seine Quelle gefunden werden.
Quelle: http://photojournal.jpl.nasa.gov/catalog/?IDNumber=PIA08329
© Prof. Kießling 2015 Kap. 1 - 63
Die Suche nach ähnlichen Bildern in einem Bildarchiv bzw. die Bild-Annotierung und Suche ausgehend von einem Vergleichsbild ist im Allgemeinen ein kaum zu lösendes Problem. Für stark eingeschränkte Anwendungsdomänen wie z.B. Gesichtserkennung werden Lösungen angeboten.
Beispiele:Polar Rose, 2010 gekauft von Apple, bzw. Gesichtserkennung bei Facebookabgeschlossenes Lehrstuhlprojekt: Heron
Bildsuchekriterien: z.B. Farbhistogramm (blau/weiß) Textur (Hermelinfell)
© Prof. Kießling 2015 Kap. 1 - 64
1.6 Übersicht Soziale Netzwerke
Suche nach Information in sozialen Netzwerken
IR-System
Korpus vonDokumenten
GewichteteDokumente
1. Doc12. Doc23. Doc3...
Relevanz?
Anfrage, Blogstart
EditierteDokumente
(Blog)
© Prof. Kießling 2015 Kap. 1 - 65
Suchfunktionalität:
Synchrone Suche: Dokumente einer Benutzergruppe (auch Profile)
Dokumente mit expliziter Schlagwortzuordnung (z.B. Multimedia)
IR-System als Kernkomponente
Asynchrone Suche: Anfrage / Nachricht an das soziale Netzwerk
Asynchrone Ergebnisse der Anfrage werden gesammelt und liegen als Dokumente für eine Verarbeitung bereit.
© Prof. Kießling 2015 Kap. 1 - 66
Quelle: http://newsroom.fb.com
Soziale Netzwerke als Massenphänomen: Allein Facebook hat weltweit etwa 890 Millionen täglich aktive
und 1,39 Milliarden monatlich aktive Nutzer (4. Quartal 2014).
© Prof. Kießling 2015 Kap. 1 - 67
Eigenschaften:
Soziale Netze erweitern die Web-Suche um soziale Kontakte bzw. persönliche Kontakte um eine technische Komponente zur Virtualisierung der Beziehungen.
Soziale Kontakte sind in Gruppen gegliedert, die gemeinsame Interessen teilen und darüber kommunizieren.
Eine Mitgliedschaft in mehreren Gruppen ist möglich.
Ein wichtiges Merkmal sind die durch Menschen generierten Beschreibungen (Annotationen, Tagging) von eigentlich nur maschinenlesbaren Formaten.
© Prof. Kießling 2015 Kap. 1 - 68
Meinungsmacher (soziale Multiplikatoren) sind Knoten mit einem hohen Verknotungsgrad.
Kommunikation wird oft über Beziehungsstruktur gestreut per Push-Strategie.
Persönliches Profil
Vielfach Multimediadaten
Datenschutz (oft nur privat bzw. öffentlich)
Social Bots als Datendiebe
© Prof. Kießling 2015 Kap. 1 - 69
Beispiele
Freundeskreis:
Gegründet 2004 (Marc Zuckerberg, Student in Harvard) ½ Milliarde USD Venture Capital Etwa 1.39 Milliarden Nutzer im Dezember 2014,
Benutzerstatistiken
2012 Übernahme des Foto-Sharing-Dienstes Instagram 2014 Übername des Messanger-Dienstes WhatsApp 2014 Übername des VR-Anbieters Oculus Rift
(Quelle: Wikipedia)
© Prof. Kießling 2015 Kap. 1 - 70
Profilangaben
• Allgemeines• Interessen• Kontakt• Ausbildung / Beruf• Wohnorte• Familie
© Prof. Kießling 2015 Kap. 1 - 71
Auswahl von Interessenaus Kandidaten
• Sport• Filme• TV-Serien• Musik• Bücher• Likes
© Prof. Kießling 2015 Kap. 1 - 72
Geschäftskontakte:
Gegründet 2003, seit 2006 an der deutschen Börse
Zielgruppe Berufstätige und Firmen
Hubert Burda Medien seit 2009 Hauptaktionär
Leistungsdaten: – 46.868 Diskussionsforen (Okt. 2011)*, – Organisation von 180.000 Events (2010)*
*Quelle: Wikipedia
© Prof. Kießling 2015 Kap. 1 - 73
Anmeldeformular:
Beispielprofil
© Prof. Kießling 2015 Kap. 1 - 74
Nachrichtenaustausch: Twitter
Gegründet 2006 als kleines Internet Startup. Öffentlich einsehbares „Tagebuch“ im Internet, welches weltweit
auch per Mobiltelefon geführt werden kann. Angemeldete Benutzer können eigene Textnachrichten mit maximal
140 Zeichen eingeben und an andere Benutzern senden. Einsatz besonders für schnelle Nachrichtenverbreitung
(z.B. Notwasserung von US-Airways-Flug 1549, Amoklauf von Winnenden, Nutzung in der Politik für Wahlkampf Obama, Twitter Revolution zur Organisation von Revolutionen)
Suchmaschinen für Tweets:
z.b. Topsy, Jobsuchmaschine
© Prof. Kießling 2015 Kap. 1 - 75
Anstelle der Domain-Einschränkung ist bei mobilen Geräten durch GPS ein alternativer Ortsbezug möglich:
Ortung von (mobilen) Freunden / Diensten in einer Landkarte
(z.B. Google Latitude, Yahoo Fire Eagle bereits 2013 eingestellt, jedoch Integration in Android, Google+)
Informationen (z.B. Einkaufsmöglichkeiten) - als Beschreibungen von Situationen - verlieren an Wert, wenn sie auf Grund der räumlich / zeitlichen Distanz nicht in Aktivitäten (z.B. Einkaufen) umgesetzt werden können.
Ziel: ortsspezifische bzw. zeitrelevante Informationen auf kleinen, mobilen Geräten (iPhone, Android)
1.7 Mobile Dienste
© Prof. Kießling 2015 Kap. 1 - 76
Beispiel: Bergwanderung
1.) Tourenwahl
© Prof. Kießling 2015 Kap. 1 - 77
2.) Ortsspezifische Online- Suche nach Points of Interest (POI) anhand von Kategorien
© Prof. Kießling 2015 Kap. 1 - 78
3.) Festlegung der Sportart
© Prof. Kießling 2015 Kap. 1 - 79
4.) Tourenvorschläge
© Prof. Kießling 2015 Kap. 1 - 80
5.) Route der gewählten Tour mit POIs (Points of Interest)
© Prof. Kießling 2015 Kap. 1 - 81
6.) Beschreibung der gewählten Tour
© Prof. Kießling 2015 Kap. 1 - 82
1.8 MetasuchmaschinenMetasuchmaschinen lassen Suchbegriffe von mehreren Suchmaschinen gleichzeitig suchen. Dabei ergeben sich zusätzliche Anforderungen:
Terminierung jeder Suchmaschine Fusion der Ergebnisse und Bewertungen der einzelnen
Suchmaschinen
Andrerseits entfällt das Crawling und die Indexierung, da die Metasuch-maschine sich auf existierende Suchmaschinen abstützt.
Beispiele:● Dogpile, ● Zoo, ● …
© Prof. Kießling 2015 Kap. 1 - 83
1.9 Google Analytics
Google Analytics ist ein kostenloser Dienst, der zur Analyse des Datenverkehrs auf Webseiten dient.
Gibt dem Betreiber der Web-Seite Feedback, – wie sie die Seite gefunden haben (Einstiege)– wie lange seine Besucher auf einzelnen Seiten verweilen– zu welchen fremden Seiten sie navigieren (Ausstiege)
Ermöglicht daher eine gute Beurteilung von Landing-Pages, Werbekampagnen, Social Media Kampagnen, etc.
Ist unter Gesichtspunkten des Datenschutzes stark umstritten.
© Prof. Kießling 2015 Kap. 1 - 84
Google Analytics - Technik
Einbindung des Skripts „ga.js“ auf jeder zu trackenden Web-Seite:
Der Tracking-Code setzt zusätzlich Cookies, um wiederkehrende Benutzer zu identifizieren.
Der Java Script-Code wird (seit 2009) asynchron ausgeführt, um die Performance beim Laden der Seite nicht zu beeinträchtigen.
<script src='http://www.google-analytics.com/ga.js' type='text/javascript'></script><script type="text/javascript">!try{ var pageTracker = _gat._getTracker("UA-xxxxxx-x"); pageTracker._trackPageview();} catch(err) {}</script>
eindeutige Tracking-ID
© Prof. Kießling 2015 Kap. 1 - 85
Google Analytics - Analysen
Detaillierte Analysen, wie– (Eindeutige) Seitenzugriffe
(keine Spider, etc.)– Absprungrate– Ausstiege
Graphisch ansprechend aufbereitet:
Verschiedene Aggregationen möglich(einzelne Unterverzeichnisse,ganzes Web-Angebot)
© Prof. Kießling 2015 Kap. 1 - 86
Google Analytics – Datenschutz
Es ist unklar, was Google mit den gewonnenen Daten intern macht.
Die Nutzung der IP-Adresse (z. B. zur Lokalisation) ist in Deutschland rechtlich unzulässig.
Nutzung von GA auf den Web-Seiten von Behörden, Universitäten ist in der Regel in Deutschland nicht zulässig. Vgl. Datenschutzerklärung der Universität Augsburg: „Auswertung der [protokollierten] Daten erfolgt nicht.“
Einfache Abhilfe, um Tracking über Besuche an verschiedenen Tagen zu vermeiden:
– Browser so einstellen, das Cookies beim Beenden des Browsers gelöscht werden.
© Prof. Kießling 2015 Kap. 1 - 87
Google Analytics – Aufspüren und deaktivieren
Mit Ghostery steht ein kostenloses Firefox Plug-In zur Verfügung, welches viele Tracker wie Google Analyticserkennen und deaktivieren kann
Beispielsweise werden auf der Nachrichtenseite „Zeit online“ 11 Tracker gefunden
Diese lassen sich einzeln deaktivieren, sowieweitere Informationen darüber abrufen
Die Anbieter sind sowohl Werbeanbieter wie„DoubleClick“ (Tochterunternehmen vonGoogle) und viele andere Anbieter, dieInteresse am Surfverhalten der Besucher haben
© Prof. Kießling 2015 Kap. 1 - 88
1.10 Zusammenfassung
• Benutzersicht User-Interface:
- Input: Suchanfrage (Suchmaske; Verknüpfungen; Kategorien als Filter)
Attributsuche; Volltextsuche;
- Output: nach Relevanz geordnete Suchergebnisse
• Benutzerverhalten Navigieren (surfing) Deklaratives Suchen (searching) Iterativ, Mischformen
© Prof. Kießling 2015 Kap. 1 - 89
Beobachtungen in heutigen Suchmaschinen: „Überspezifizierung“ in der Suchanfrage kann zu einer leeren
Ergebnismenge (empty result set) führen, während andrerseits eine „Unterspezifizierung“ zu einer Überflutung (flooding effect) führen kann.
Eine Beurteilung der Qualität der Suchergebnisse ist in erster Linie benutzerabhängig. Benutzerunabhängige Qualitätsmaße (Precision/Recall) werden später eingeführt.
Suchwörter repräsentieren keine Struktur und Abhängig-keiten ( Taxonomien, Ontologien, Semantische Netze).
Eine Navigation ist in den meisten Fällen unumgänglich, um die gewünschte Information zu finden.
© Prof. Kießling 2015 Kap. 1 - 90
Spannweite des Einsatzes von Such-Technologien
Firmenintern Folksonomy Web
Korpus Geschlossen „Geschlossen“ Offen
Inhalt Erschlossen:Attribute, Text
Teils erschlossen Nicht erschlossen
Erstellung DV-Spezialisten Virt. Redakteure „Jeder“
Beispiel OPAC Wikipedia, soz. Netzwerke
Web
Textsuche IR IR IR
Attributsuche Ja Teilweise Kaum
