Das Verborgene Web (Hidden Web)hpi.de/fileadmin/user_upload/fachgebiete/naumann/folien/SS07/II/... · –Star Schema OLAP Anfragen Optimierung SE „„gSchema Matching“ Korrespondenzen

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


Shallow web

Deep web (tiefes Netz)

Inv

(uns

ic

Quelle: [To01]

Surface Web vs. Hidden Web

6

Keywords

Surface WebHidden Web

SUBMIT

KeywordsCLEAR


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


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


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


Methoden zur Analyse und Visualisierung der Überdeckunsgradevon Suchmaschinen – Deumlich

12


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


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.”


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


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


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.


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


11

Beispiel: CompletePlanet.com

21


22

Überblick








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)


13

25

Überblick







■ (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


Library of Congress

PubMed ESPN

Nieren 220,000 Steine 40,000...

Nieren 5 Steine 40...

Nieren 20 Steine 950...


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


28


15

29


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


... ...

Vorschau zur Verwendung von content summaries• Anfrage „Darm-Krebs“• Anzahl Treffer = dc * df(Darm)/dc * df(Krebs)/dc = 74569

16


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


Web Database 1

MetasearcherKrebs

Krebs 4,532CPU 23

Web Database 2Basketball 4Krebs 60,298CPU 0

Web Database 3Basketball 6,340Krebs 2CPU 0


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



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


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.


word rank

Zipf’s law

Deshalb jetzt verbesserte Lösung


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.



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.



Fokussiertes Sampling

■ Fokus nun auf Subkategorie

38

■ Neue Regelmenge, deshalb neue Anfragemenge

■ Vorteile

□ Weniger Anfragen

□ Fokussierte Anfragen



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


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.


Zur Abschätzung der (besseren) Document-frequencieswerden Infos der Ein-Wort Anfragen verwendet.


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


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.



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.



45

Überblick








23


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


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.


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


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


49

Überblick








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“


„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, `*´, `_´, `“ “´, ÀND´, ÒR´, `NOT´, `+´, `-´}■ Ziel

□ Automatische Erkennung der unterstützten Operatoren□ Automatische Erkennung der Interpretation der Syntax


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□ ÀND´ → AND□ ÒR´ → OR□ `NOT´ → ignored□ `+´ → AND□ `-´ → NOT□ ∅ →literal, unknown


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?


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


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


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, `*´, `_´, `“ “´, ÀND´, ÒR´, `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.
