1
Informationsintegration Das Verborgene Web (Hidden Web)
16.7.2007
Felix Naumann
Workshop "Datenreinigung" für Studenten und Doktoranden
Prof. Felix NaumannFUZZY! Informatik AG
8 Okt b 10 Okt b 2007 N M Mi
2
8. Oktober - 10. Oktober 2007(Mo. – Mi. direkt vor dem Wintersemester)
Innerhalb eines Unternehmens werden Kundendaten häufig in unterschiedlichen Systemen gehalten. DieGründe dafür können in der Struktur des Unternehmens (getrennte Sparten), in unterschiedlichenVertriebskanälen oder in einer Unternehmensfusion liegen. Um eine einheitliche Sicht auf den Kunden zubekommen, müssen die Daten aus diesen Systemen zusammengeführt werden. Ein wichtiges Ziel istdabei die automatische Erkennung von Dubletten, d.h. die Tatsache, dass ein Kunde in mehrerenSystemen vorkommt, also in mehreren Beziehungen zum Unternehmen steht.
Sie sollen erkennen, welche Arten von Problemen beim Zusammenführen von Datenbeständen auftreten,welche Probleme sich mit einfachen Mitteln (SQL, Skripte, Text-Editor, etc.) lösen lassen und welchenicht. In praktischer Teamarbeit implementieren Sie Algorithmen zur Dublettenerkennung für großeD t (1 Mi K d d t ät ) D T it d i t i hti f d D bl tt
Neu: Mo - Mi
Datenmengen (1 Mio. Kundendatensätze). Das Team mit den meisten richtig gefundenen Dublettengewinnt! Die in den beiden ersten Tagen gewonnenen Erkenntnisse und Lösungen sollen amAbschlusstag präsentiert werden.
Weitere Informationen und Programm: http://www.hpi.uni-potsdam.de/naumann/
Anmeldung
Formlose Anmeldung per Email bis zum 25. September an [email protected].
Es können maximal 20 Teilnehmer (Bachelor- und Master-Studenten und Doktoranden) mitmachen.
Felix Naumann | VL Datenbanksysteme II | SS 07
2
Masterveranstaltungen
■ VL Data Warehouses
3
□ Architektur zur Integration von Unternehmensdatenbeständen
□ Mehrdimensionale Modellierung
– Star Schema
□ OLAP Anfragen
□ Optimierung
■ SE „Schema Matching“„ g
□ Korrespondenzen zwischen Schemata und Ontologien finden
□ Automatisiert
□ Label-basiert: Analyse der Schemata
□ Instanz-basiert: Analyse der zugehörigen Daten
Felix Naumann | VL Datenbanksysteme II | SS 07
4
Überblick
■ Motivation [Be01,To01]□ Suche über das Web □ Begriffe und Definitionen
■ Auffinden von Hidden Web Informationsquellen□ Potenzielle Hidden Web Quellen Finden
[BC04]□ Themen extrahieren [IGS01]□ Klassifikation nach Themen [IGS01]
VL Informationsintegration | Felix Naumann | SS 2007
□ Klassifikation nach Themen [IGS01]■ Anfragen an relevante Quellen des Hidden
Web□ Anfragen geeignet verteilen [IGS01]□ Anfragesprache lernen [BC04]
■ (Ergebnisse integrieren)
3
Das Web
5
z)
Surface web
Shallow webvisi
ble
Web
chtb
ares
Net
z
VL Informationsintegration | Felix Naumann | SS 2007
Shallow web
Deep web (tiefes Netz)
Inv
(uns
ic
Quelle: [To01]
Surface Web vs. Hidden Web
6
Keywords
Surface WebHidden Web
SUBMIT
KeywordsCLEAR
VL Informationsintegration | Felix Naumann | SS 2007
Surface Web■ Link-Struktur■ Kann gecrawled werden■ Dokumente durch Suchmaschinen
indiziert■ Anfragen auf viele Websites
gleichzeitig
■ Keine Link-Struktur■ Dokumente verborgen in DBMS■ Dokumente nicht durch Internet-
Suchmaschinen indiziert■ Dokumente eventl. durch
Intranet-Suchmaschinen indiziert■ Anfragen auf jede Sammlung
einzelnQuelle: Folie aus [IGS01]
4
Hidden Web: Beispiel
■ Suche in PubMed nach “diabetes”
7
□ 178,975 Treffer
■ Google Suche: “diabetes site:www.ncbi.nlm.nih.gov”
□ nur 119 matches
■ Weitere Beispiele:
Database Query Matches GooglePubMed diabetes 178,975 119
■ Gegenbeispiel
□ Amazon: Hilft explizit bei VerlinkungVL Informationsintegration | Felix Naumann | SS 2007
,U.S. Patents wireless network 16,741 0Library of Congress visa regulations >10,000 0… … … …
Quelle: Folie aus [IGS01]
Suche über das Web
■ Kataloge
8
■ Suchmaschinen
■ Metacrawler
■ Antwort Services
■ Unsichtbares/Tiefes/Verborgenes Web
VL Informationsintegration | Felix Naumann | SS 2007
5
Kataloge
■ Indizes speichern URL, Titel Kategorien und
9
Titel, Kategorien, und Zusammenfassung
■ Wartung durch Experten □ freiwillig, bezahlt,
Selbst-Registrierung■ Das Web (Stand 2001):
□ >5,000,000,000 Dateien
■ Yahoo:□ ~2,000,000 Sites
■ 1/2500 des bekannten Webs
VL Informationsintegration | Felix Naumann | SS 2007
Quelle: [To01]
Suchmaschinen
■ Indizes speichern URL, Titel, Meta-Tags, Links,
10
Diplomarbeit
Titel, Meta Tags, Links, und vollständigen Inhalt
■ Wartung durch Agenten (Crawler)
■ Das Web (Stand 2001):□ >5,000,000,000
Dateien■ Google:
2 469 940 685 □ 2,469,940,685 Seiten
■ FAST:□ 2,112,188,990
Seiten■ HotBot (Inktomi):
□ 500,000,000 SeitenVL Informationsintegration | Felix Naumann | SS 2007
Quelle: [To01]
6
Methoden zur Analyse und Visualisierung der Überdeckunsgradevon Suchmaschinen – Deumlich
11
VL Informationsintegration | Felix Naumann | SS 2007
Methoden zur Analyse und Visualisierung der Überdeckunsgradevon Suchmaschinen – Deumlich
12
VL Informationsintegration | Felix Naumann | SS 2007
7
Meta-Suchmaschinen
■ Haben keinen eigenen Katalog oder Index
13
■ Nutzer geben Suchbegriff ein, der simultan an andere Suchmaschinen weitergeleitet wird.
■ Ergebnisse werden integriert und als eine Liste zurückgegeben.■ Vorteile:
□ Eine einzige Anfrage□ Geschwindigkeit
(parallel statt sequentiell)■ Nachteile:
Ti t d □ Time-outs und unvollständige Suche
□ Anfragesyntax oft reduziert auf kleinsten gemeinsamen Nenner
VL Informationsintegration | Felix Naumann | SS 2007Quelle: [To01]
Antwort Services
■ Datenbank mit gespeicherten häufigen Fragen
14
□ Katalog von Ask Jeeves enthält 7,000,000 Fragen
■ Natürlich-sprachliche Suche
■ Suche in eigener DB undin fremden Katalogen/Indices
■ Kennt Spezial-Daten-quellen des Hidden Web
■ Gewichtung anerkannter Quellen (z.B. Almanache)
VL Informationsintegration | Felix Naumann | SS 2007Quelle: [To01]
8
Invisible/Hidden/Deep Web
15
VL Informationsintegration | Felix Naumann | SS 2007
Quelle: [To01]
Surface vs. Hidden Web [Be01]
■ “Der Inhalt des SurfaceWeb ist persistent auf
16crawling
Web ist persistent auf statischen Seiten, die mittels crawling von Suchmaschinen entdeckt werden kann. Inhalt des Hidden Web wird dynamisch präsentiert in Antwort auf eine konkrete Anfrage.”
■ “ der größte Anteil ■ …der größte Anteil Inhalts des Hidden Web wird unterhalb der Oberfläche bleiben und kann nur im Kontext einer bestimmten Anfrage entdeckt werden.”
VL Informationsintegration | Felix Naumann | SS 2007
Quelle: [To01]trawling
9
Das Verborgene Web
■ Der Teil des Webs, der nicht durch Suchmaschinen indiziert wird
17
□ Oft gespeichert in Datenbanken
□ Dynamisch generierte Web Seiten durch Anwendungen im Server
– jsp, cgi, …
□ Sites und Seiten mit Passwort-geschütztem Inhalt
□ Inhalt von Dateien, die nicht in Standard-Formaten gespeichert werden
– *.pdf, *.ppt, *.doc– Grafikformate
VL Informationsintegration | Felix Naumann | SS 2007
Quelle: [To01]
Begriffe / Synonyme
■ Surface Web (Oberflächen-Web)
18
□ Inhalt für „normale“ Suchmaschinen sichtbar■ Shallow Web (Flaches Web)
□ „Normale“ Web-Seiten, die dynamisch generiert werden□ Anfragen durch Klicken auf Links
■ Hidden Web (verborgenes Web)□ Inhalt für „normale“ Suchmaschinen unsichtbar□ Invisible Web (unsichtbares Web)
– Synonym mit Hidden weby y□ Deep Web (tiefes Web)
– nach BrightPlanet,– Synonym mit Hidden Web
VL Informationsintegration | Felix Naumann | SS 2007
Quelle: [To01]
10
Statistiken [Be01]
■ 400 bis 550 fach größer als Surface Web
19
□ 7,500 Terabytes Informationen im Hidden Web
□ 19 Terabytes Information im Surface Web
□ 550 Milliarden Dokumente im Hidden Web
□ 1 Milliarde Dokumente im Surface Web
□ je nach dem, was man zählt…
– Dynamische Seiten...Dynamische Seiten...
■ 100,000 Hidden Websites
■ ca. 84% sind auf Text-Dokumente spezialisiert
■ ca. 95% des Hidden Web ist öffentlich verfügbar.
VL Informationsintegration | Felix Naumann | SS 2007
Eigenschaften [Be01]
■ Hidden Websites haben thematisch oft „schmaleren“, aber
20
■ Hidden Websites haben thematisch oft „schmaleren , aber
„tieferen“ Inhalt.
■ Oft qualitativ bessere Informationen
■ Meist relevanter Inhalt
□ Kein Spam
Über die Hälfte aller Hidden Websites sind thematisch spezialisiert■ Über die Hälfte aller Hidden Websites sind thematisch spezialisiert.
■ Am schnellsten wachsende Kategorie neuer Informationen im
Internet
VL Informationsintegration | Felix Naumann | SS 2007
11
Beispiel: CompletePlanet.com
21
VL Informationsintegration | Felix Naumann | SS 2007
22
Überblick
■ Motivation [Be01,To01]□ Suche über das Web □ Begriffe und Definitionen
■ Auffinden von Hidden Web Informationsquellen□ Potenzielle Hidden Web Quellen Finden
[BC04]□ Themen extrahieren [IGS01]□ Klassifikation nach Themen [IGS01]
VL Informationsintegration | Felix Naumann | SS 2007
□ Klassifikation nach Themen [IGS01]■ Anfragen an relevante Quellen des Hidden
Web□ Anfragen geeignet verteilen [IGS01]□ Anfragesprache lernen [BC04]
■ (Ergebnisse integrieren)
12
Auffinden von Hidden Web Quellen [BC04]
■ Ziel: Finde Webseiten, die als Einstiegspunkt ins Hidden Web dienen.
23
□ Seiten mit HTML Formular■ Einschränkungen
□ Textuelle Formulare– mindestens ein Textinput– Gegenbeispiele?
» Nur radio buttons, menus, checkboxen...□ Anfrageformulare
– Formulare, die Anfragen entgegennehmen und I f ti li fInformationen liefern
– Gegenbeispiele?» Login Seiten
□ „Hidden Web Formulare“– Keine Seiten mit komplexen Formularen (mehr als ein
Inputfeld)■ Aufgabe: Automatisches Finden und Erkennen von Hidden Web
FormularenVL Informationsintegration | Felix Naumann | SS 2007
Auffinden von Hidden Web Quellen
■ Manuell
24
■ Automatisches Auffinden von Formularen1. Google-Suche (nach Themen)2. Lokales breadth-first Crawling bis Formular gefunden
– Innerhalb einer Site– Bis zu einer festen Tiefe
■ Automatisches Erkennen von Hidden Web Formularen (Heuristiken)□ Testanfragen mit positiven und negativen Suchwörtern
P iti d “ W t– Positiv: „passende“ Worte– Negativ: Fantasieworte
□ Ergebnisse negativer Suchwörter immer gleich groß (Byte)□ Ergebnisse positiver Suchworte immer größer als negative
– Berechnung der Größe durch „Subtraktion“ von Webseiten (als Baum)
VL Informationsintegration | Felix Naumann | SS 2007
13
25
Überblick
■ Motivation [Be01,To01]□ Suche über das Web □ Begriffe und Definitionen
■ Auffinden von Hidden Web Informationsquellen□ Potenzielle Hidden Web Quellen Finden
[BC04]□ Themen extrahieren [IGS01]□ Klassifikation nach Themen [IGS01]
VL Informationsintegration | Felix Naumann | SS 2007
□ Klassifikation nach Themen [IGS01]■ Anfragen an relevante Quellen des Hidden
Web□ Anfragen geeignet verteilen [IGS01]□ Anfragesprache lernen [BC04]
■ (Ergebnisse integrieren)Panagiotis G. Ipeirotis, NYU
Suche im Hidden Web – Probleme
■ Auswahl relevanter Quellen für Anfrage
26
□ Themen extrahieren
– Content summary
□ Nach Themen klassifizieren
Hidden Web MetasearcherHidden Web
VL Informationsintegration | Felix Naumann | SS 2007
Library of Congress
PubMed ESPN
Nieren 220,000 Steine 40,000...
Nieren 5 Steine 40...
Nieren 20 Steine 950...
Quelle: Folie aus [IGS01]
14
Klassifikation von Hidden Web Quellen
■ Klassifikation hier:
27
□ Hierarchie über Kategorien und Subkategorien□ Zuordnung von Quellen ist nicht immer eindeutig.
■ Manuell□ Yahoo, dmoz□ InvisibleWeb (www.invisibleweb.com)□ SearchEngineGuide (www.searchengineguide.com)□ Hierarchien sind einsehbar.
■ Automatisch□ Basierend auf Kategorie der Dokumente in der Quelle
VL Informationsintegration | Felix Naumann | SS 2007
28
VL Informationsintegration | Felix Naumann | SS 2007
15
29
VL Informationsintegration | Felix Naumann | SS 2007
Content Summaries
■ Statistiken, die den Inhalt
30
K b DBeiner Hidden Web Quelle beschreiben
■ Document-cardinality dc
□ Anzahl der Dokumente insgesamt
■ Document-frequency df(w)
KrebsDBDocument cardinality: 148.944Wort Document frequencyDarm 121.134Krebs 91.688
□ Pro Wort: Anzahl der Dokumente, die dieses Wort enthalten
VL Informationsintegration | Felix Naumann | SS 2007
... ...
Vorschau zur Verwendung von content summaries• Anfrage „Darm-Krebs“• Anzahl Treffer = dc * df(Darm)/dc * df(Krebs)/dc = 74569
16
Suche im Hidden Web – Probleme
31
Basketball 4Krebs 4,532
1. Wie extrahiert man content summaries?
2. Wie verwendet man content summaries?
Web Database
Web Database 1
CPU 23
Basketball 4Krebs 4 532
VL Informationsintegration | Felix Naumann | SS 2007
Web Database 1
MetasearcherKrebs
Krebs 4,532CPU 23
Web Database 2Basketball 4Krebs 60,298CPU 0
Web Database 3Basketball 6,340Krebs 2CPU 0
Quelle: Folie aus [IGS01]
Extraktion von Content Summaries –Probleme
■ Kein direkter Zugang zu den Dokumenten ohne konkrete A f
32
Anfrage□ Gebundene Variablen
■ Deswegen: Anfrage-basiertes Dokument-Sampling:1. „Sinnvolle“ Anfragen an Datenbank schicken (focussed
probing)– Ergebnisliste mit Links
2. Ergebnisdokumente aus Liste einholen (das „Sample“)3 Sample verwenden um content summary zu erstellen3. Sample verwenden um content summary zu erstellen
VL Informationsintegration | Felix Naumann | SS 2007
Quelle: Folie aus [IGS01]
17
“Zufälliges” Anfrage-basiertes Sampling
1. Start mit leerem contentsummary
33
summary□ Jedes Wort hat df(w)
= 0.2. Wähle ein Wort und
schicke es als Anfrage an Hidden Web Quelle.
3. Wähle top-k Dokumente der Antwort (z.B. k=4).
4. Zähle df(w) für alle w in Sample um contentSample um contentsummary zu füllen.
5. Wiederhole bis „genug“ (z.B. 300) Dokumente empfangen wurden
VL Informationsintegration | Felix Naumann | SS 2007
Wort Häufigkeit in Sample
Krebs 150 (out of 300)
aids 114 (out of 300)
Herz 98 (out of 300)
…
Basketball 2 (out of 300)Quelle: Folie aus [IGS01]
Zufälliges Sampling – Probleme
■ df(w) zwischen 1 und Anzahl der D k t
34
Dokumente■ Es wird nicht Document-frequency
ermittelt, sondern Sample-frequency. □ Absolute Zahlen sind nicht
aussagekräftig.□ Große Quellen haben ähnliche
content summary wie kleine Quellen
# documents
Quellen.□ Zahlen sind nur relativ zu
interpretieren (als ranking).■ Viele Anfragen ohne oder nur mit
kleinem Ergebnis (Zipf‘s law)■ Viele, seltene Worte fehlen in der
content summary.
VL Informationsintegration | Felix Naumann | SS 2007
word rank
Zipf’s law
Deshalb jetzt verbesserte Lösung
Quelle: Folie aus [IGS01]
18
Zufälliges Sampling – Verbesserung
Algorithmus: Überblick
35
1. Trainiere Dokument-Klassifikatoren
□ Finde repräsentative Wörter für jede Kategorie.
2. Verwende Klassifikationsregeln um ein themenspezifisches Sample aus Quelle zu erhalten.
3. Schätze df(w) aller entdeckten Wörter.
VL Informationsintegration | Felix Naumann | SS 2007
Quelle: Folie aus [IGS01]
Fokussiertes Sampling: Trainingsphase
■ Start mit vordefinierter Themen-Hierarchie und bereits klassifizierten Dokumenten
36
□ Bsp: Yahoo, dmoz Open Directory, Google ...
■ Trainiere Dokument-Klassifikatorenfür jeden Knoten der Hierarchie.
□ Mittels der bekannten Dokumente
■ Extrahiere automatisch Regeln aus den Klassifikatoren:
□ ibm AND computers → Computers
□ lung AND cancer → Health
□ …
□ angina → Heart
□ hepatitis AND liver → Hepatitis
□ …VL Informationsintegration | Felix Naumann | SS 2007
} Root
} Health Quelle: Folie aus [IGS01]
19
Fokussiertes Sampling
■ Transformiere jede Regel in eine Boolesche Anfrage.
■ Für jede Anfrage:
37
■ Für jede Anfrage:
□ Schicke Anfrage an Quelle
□ Merke Anzahl der Ergebnisse
– Parsing
□ Hole top-k Dokumente ein.
■ Am Ende einer Runde:
□ Analysiere Ergebnisse für jede Kategorie (zählen).
□ Wähle Kategorie zum fokussieren in nächster Runde.
VL Informationsintegration | Felix Naumann | SS 2007
Quelle: Folie aus [IGS01]
Fokussiertes Sampling
■ Fokus nun auf Subkategorie
38
■ Neue Regelmenge, deshalb neue Anfragemenge
■ Vorteile
□ Weniger Anfragen
□ Fokussierte Anfragen
VL Informationsintegration | Felix Naumann | SS 2007
Quelle: Folie aus [IGS01]
20
39
Aufruf für jede Kategorie und Subkategorie
Anfragen entsprechend der Regeln des Klassifikators
Sammle Dokumente ein
Bei Ein-Wort Anfragen erlernen wir die tatsächliche erlernen wir die tatsächliche
df(w)
Zähle sample-frequency für jedes Wort
Maße zur Berechnung des Grades der Zugehörigkeit zu
einer Kategorie
Falls hinreichend zu einer
VL Informationsintegration | Felix Naumann | SS 2007
Falls hinreichend zu einer Subkategorie zugehörig
Wiederhole für Subkategorie
Vereinige gesammelte Metadaten
Quelle: [IG02]
Sample-frequency vs. Document-frequency
■ Motivation: □ Sample-frequencies sind nur relativ.□ Quelle mit ähnlichem Inhalt aber unterschiedlicher Größe
41
□ Quelle mit ähnlichem Inhalt aber unterschiedlicher Größe haben gleiche content summary.
■ Sample Frequencies□ “Leber” erscheint in 200 von 300 Dokumenten im Sample.□ “Niere” erscheint in 100 von 300 Dokumenten im Sample.□ “Hepatitis” erscheint in 30 von 300 Dokumenten im Sample.
■ Document-frequencies□ Anfrage “Leber” ergibt 140,000 Matches.
Anfrage “Hepatitis” ergibt 20 000 Matches□ Anfrage Hepatitis ergibt 20,000 Matches.□ “Niere” war kein Trainingswort…□ “Darm” und “Krebs” waren zwar Trainingsworte, aber nur
gemeinsam.
VL Informationsintegration | Felix Naumann | SS 2007
Zur Abschätzung der (besseren) Document-frequencieswerden Infos der Ein-Wort Anfragen verwendet.
Quelle: Folie aus [IGS01]
21
Abschätzen der Document-frequencies
■ Bekannt aus Algorithmus□ Ranking r der Worte
nach Sample-
42
fnach Samplefrequencies
□ Document-frequencyf der Worte aus Ein-Wort Anfragen
■ Mandelbrot’s Formel verfeinert Zipfs Formel:
□ f = P (r+p)-B
□ P, p und B sind Parameter der Quelle
□ Niedriger rank ergibt hohe frequency
■ Dann: Kurvenanpassung□ z.B.: P = 8*105, p
=.25, B = 1.15
VL Informationsintegration | Felix Naumann | SS 2007
r
Quelle: Folie aus [IGS01]http://www.math.yale.edu/mandelbrot/web_pdfs/9_E7rankSizePlots.pdf
Abschätzen der Document-frequencies
■ Algorithmus
43
□ Sortiere Wörter absteigend nach Sample-frequency
□ Ermittle P, p und B durch Fokus auf Wörter mit bekannter Document-frequency. (Kurvenanpassung)
□ Berechne df(wi) = P (ri+p)-B für alle anderen Wörter.
VL Informationsintegration | Felix Naumann | SS 2007
Quelle: Folie aus [IGS01]
22
Vorteile des Fokussierten Sampling
■ Wenige Anfragen (Fokus auf Thema)
44
■ Vielversprechende Anfragen
■ Klassifikation „along the way“
□ Nützlich für Auswahl relevanter Quellen
■ Schätzung Document-frequency statt nur Sample-frequency.
VL Informationsintegration | Felix Naumann | SS 2007
Quelle: Folie aus [IGS01]
45
Überblick
■ Motivation [Be01,To01]□ Suche über das Web □ Begriffe und Definitionen
■ Auffinden von Hidden Web Informationsquellen□ Potenzielle Hidden Web Quellen Finden
[BC04]□ Themen extrahieren [IGS01]□ Klassifikation nach Themen [IGS01]
VL Informationsintegration | Felix Naumann | SS 2007
□ Klassifikation nach Themen [IGS01]■ Anfragen an relevante Quellen des Hidden
Web□ Anfragen geeignet verteilen [IGS01]□ Anfragesprache lernen [BC04]
■ (Ergebnisse integrieren)
23
Suche im Hidden Web – Probleme
46
Basketball 4K b 4 5321. Wie extrahiert man
content summaries?
2. Wie verwendet man content summaries?
Web Database
Web Database 1
Krebs 4,532CPU 23
Basketball 4Krebs 4 532
VL Informationsintegration | Felix Naumann | SS 2007
Web Database 1
MetasearcherKrebs
Krebs 4,532CPU 23
Web Database 2Basketball 4Krebs 60,298CPU 0
Web Database 3Basketball 6,340Krebs 2CPU 0
Quellenauswahl und Content Summaries
■ Quellenauswahl nimmt vollständige content summaries an.
47
□ Falls unvollständig (das Suchwort fehlt), kann nicht entschieden werden, ob die Quelle relevant ist.
■ Content summaries aus Sampling sind immer unvollständig.■ Idee: Klassifikation verwenden
□ Quellen gleicher Kategorie sollten auch ähnliche contentsummary haben.
□ Content summaries verschiedener Quellen gleicher Kategorie können sich komplementieren.können sich komplementieren.
VL Informationsintegration | Felix Naumann | SS 2007
24
Content Summaries für Kategorien (statt für Quellen)
48Anzahl der
Quellen Category: CancerNumDBs: 2
Anzahl der Dokumente (Summe)
Document-frequencies (Summe)
CANCERLIT CancerBACUP
Number of Documents: 166,272
… ...breast 133,680… ...cancer 101,423… ...diabetes 11,344… …metastasis 3,569
Number of Documents: 148 944 Number of Documents: 17,328
VL Informationsintegration | Felix Naumann | SS 2007
Somit kann jede Kategorie als Hidden Web Quelle angesehen werden.
… ...breast 121,134… ...cancer 91,688… ...diabetes 11,344… …metastasis <not found>
… ...breast 12,546… ...cancer 9,735… ...diabetes <not found>… …metastasis 3,569
Number of Documents: 148,944 Number of Documents: 17,328
Quelle: Folie aus [IGS01]
49
Überblick
■ Motivation [Be01,To01]□ Suche über das Web □ Begriffe und Definitionen
■ Auffinden von Hidden Web Informationsquellen□ Potenzielle Hidden Web Quellen Finden
[BC04]□ Themen extrahieren [IGS01]□ Klassifikation nach Themen [IGS01]
VL Informationsintegration | Felix Naumann | SS 2007
□ Klassifikation nach Themen [IGS01]■ Anfragen an relevante Quellen des Hidden
Web□ Anfragen geeignet verteilen [IGS01]□ Anfragesprache lernen [BC04]
■ (Ergebnisse integrieren)
25
Anfragen an Quellen des Hidden Web
■ Hidden Web Quellen verwenden unterschiedliche Anfragesprachen (S h itt t ll H t ität)
50
(Schnittstellen-Heterogenität)□ Suchwörter□ Phrasen□ Boolesche Kombinationen
Es gilt, solche Anomalien“
VL Informationsintegration | Felix Naumann | SS 2007
„Anomalien automatisch
zu entdecken.
Quelle [BC04]
Anfragesprache an Quellen des Hidden Web
■ Mögliche Operatoren
51
□ O = {CASE, STEM, PHRASE, AND, OR, NOT}■ Mögliche Syntax
□ S = {wort, `*´, `_´, `“ “´, `AND´, `OR´, `NOT´, `+´, `-´}■ Ziel
□ Automatische Erkennung der unterstützten Operatoren□ Automatische Erkennung der Interpretation der Syntax
VL Informationsintegration | Felix Naumann | SS 2007
26
Maschinelles Lernen für Syntax
■ Zielfunktion: T:S → OZ d A d ü k O t
52
□ Zuordnung von Ausdrücken zu Operatoren■ Problem: Nicht jede Syntax wird unterstützt
□ Erweiterung von O zu O‘– O = {CASE, STEM, PHRASE, AND, OR, NOT}– O‘ = O ∪ {ignored, literal, unknown}
■ Beispiel: Google□ Wort → CASE, STEM□ `*´ → ignored□ `_´ → AND□ `“ “´ → PHRASE□ `AND´ → AND□ `OR´ → OR□ `NOT´ → ignored□ `+´ → AND□ `-´ → NOT□ ∅ →literal, unknown
VL Informationsintegration | Felix Naumann | SS 2007
Maschinelles Lernen für Syntax
■ IdeeT t f hi k d E b i öß t h
53
□ Testanfragen verschicken und Ergebnisgrößen untersuchen.□ Machine Learning Methoden verwenden.
■ Wichtige Annahme: Man kann Ergebnisgröße herausparsen.
■ Training□ Hidden Web Quellen mit bekannter Syntax und bekannten Operatoren□ Testanfrage verschicken und Eigenschaften der Ergebnisse
(insbesondere Ergebnisgröße) beobachten.■ Testing
□ Unbekannte Hidden Web Quelle□ Gleiche Testanfragen verschicken und Eigenschaften vergleichen.
■ Welche Testanfragen?■ Welche Eigenschaften?
VL Informationsintegration | Felix Naumann | SS 2007
27
Testanfragen
■ Beispiele□ ‘caSaBlancA’ (template ‘RandomCase(A)’)
– Einzelnes Wort‘B AND’ ( l ‘B AND’)
54
□ ‘Bogart AND’ (template ‘B AND’)– Nicht wohlgeformt
□ ‘+Casablanca +Bogart’ (template ‘+A +B’)– Kombination von Worten
□ Variationen– ‘+Bogart +Casablanca ’ (template ‘+B +A’)
□ In [BC04]: 22 templates■ Templates füllen mit drei Sorten von Wortpaaren
□ Phrasen: A = information, B = retrieval□ Co-occurrence: A = information, B = knowledge□ Nicht verwandte Worte: A = China, B = Käse
VL Informationsintegration | Felix Naumann | SS 2007
Quelle [BC04]
Eigenschaften der Ergebnisse (Features)
■ Für jede Anfrage qi
55
□ Extraktion der Trefferanzahl m(qi)
■ Für jedes Paar von Anfragen qi, qj (231 Stück)
□ merke (zur Normalisierung)– -1 falls m(qi) < m(qj)– 0 falls m(qi) = m(qj)– +1 falls m(qi) > m(qj)
■ Dies sind dreiwertige Machine Learning Features■ Dies sind dreiwertige Machine Learning Features.
■ Nun: Beliebiger Algorithmus für Maschinelles Lernen verwenden
□ Decision Trees, k-Nearest Neighbour, Support-Vector-Machines
VL Informationsintegration | Felix Naumann | SS 2007
Quelle [BC04]
28
Weitere Probleme
■ Stop-Wörter
□ a, the, on, in, ...
56
, , , ,
■ Kontextsensitive Stop-Wörter
□ Google: ‚www‘ vs. ‚www database‘
■ Dynamische Interpretation
□ CiteSeer: ‚www databases‘
– (i) entspricht www AND databases– (ii) entspricht www OR databases falls (i) leer
■ Ergebnisgröße oft nur geschätzt.VL Informationsintegration | Felix Naumann | SS 2007
Rückblick
■ Motivation [Be01,To01]
57
□ Suche über das Web
□ Begriffe und Definitionen
■ Auffinden von Hidden Web Informationsquellen
□ Potenzielle Hidden Web Quellen Finden
□ Themen extrahieren
Web Database
Basketball 4Krebs 4,532CPU 23
□ Klassifikation nach Themen
■ Anfragen an relevante Quellen des Hidden Web
□ Anfragen geeignet verteilen
□ Anfragesprache lernen
VL Informationsintegration | Felix Naumann | SS 2007 57
O = {CASE, STEM, PHRASE, AND, OR, NOT}
S = {wort, `*´, `_´, `“ “´, `AND´, `OR´, `NOT´, `+´, `-´}
Klassifikation
29
Literatur
■ Wichtigste Literatur
58
□ [IGS01] Probe, Count, and Classify. P.G. Ipeirotis, L. Gravano, and M. Shami. SIGMOD 2001
□ [BC04] A. Bergholz and B. Chidlovskii. Learning Query Languages of Web Interfaces, SAC04
■ Weiteres□ [Be01] The Deep Web: Surfacing Hidden Value Michael K.
Bergman, Whitepaper atBergman, Whitepaper athttp://www.completeplanet.com/Tutorials/DeepWeb/index.asp
□ [To01] Foliensatz von Dawne Tortorella (BellCow) nach [Be01]□ [IG02] Distributed Search of the Hidden Web: Hierarchical
Data Sampling and Selection. P.G. Ipeirotis and L. Gravano in VLDB 2002.
VL Informationsintegration | Felix Naumann | SS 2007