Upload
bruna-werkmeister
View
105
Download
1
Embed Size (px)
Citation preview
1
Bettina Berendt
www.berendt.de
Web Mining
1. Ein Überblick2. Analyse von Nutzer- und Kundenverhalten: Zur Rolle von Distributionsstrategien und demographischen Variablen
2
Agenda
1. Person
2. Motivation
3. Web Mining
4. Web Usage Mining
5. 2 Fallstudien + Methodenbeispiele
3
Zur Person
Derzeit Juniorprofessorin für Wirtschaftsinformatik, Humboldt-Universität zu Berlin
Ausbildung:
Habilitation 2003 – Wirtschaftsinformatik, Pädagogik und Informatik (HU Berlin), Computervisualistik (Magdeburg)
Promotion 1998 – Informatik / Kognitionswissenschaft (Hamburg)
M.Sc. 1992 – Informatik / Künstliche Intelligenz (Edinburgh)
Diplom 1991 – Betriebswirtschaftslehre (FU Berlin)
M.Phil. 1988 – Volkswirtschaftslehre (Cambridge)
4Wirtschaftsinformatik – Information Systems Science
Gegenstand: Informations- und Kommunikationssysteme in Institutionen (IS)
IS = Systeme interdependenter Agenten – menschliche und maschinelle –, die gemeinsame Ziele und Aufgaben haben,
unter den Einschränkungen knapper Resourcen entscheiden u. handeln
Ziele und Aufgaben: abhängig von der Art der Institution
„Business Intelligence“: die analytischen Konzepte, Prozesse und Werkzeuge, um unternehmensinterne und -externe Daten in entscheidungsrelevantes Wissen zu transformieren.
~ Wissensentdeckung / Knowledge Discovery / Data Mining(Anm.: Das beinhaltet Data Warehousing, Reporting usw. – da die Begrifflichkeiten in
den beteiligten Communities nicht eindeutig und häufig auch wenig formal sind, bitte ggf. nachfragen!)
5
Ziele und Fragen: Bsp. 0 / Verstehen der DomäneWoher kommt die Cholera?
J. Snow: “cholera map“, 1854
6
Warum Web? Das WWW als Datenquelle und Ort wirtschaftlichen und gesellschaftlichen Handelns
1.018 Millionen Menschen online!1.018 Millionen Menschen online!
Daten: http://www.internetworldstats.com/, www.archive.org, http://www.isc.org/index.pl?/ops/ds/
7Ziele und Fragen: Bsp. 1 / Marktforschung (und ?) Wo wohnen Menschen, die demnächst den Koran kaufen werden?
[Owad (2006). http://www.applefritter.com/bannedbooks]
8Ziele und Fragen: Bsp. 2 / Marktforschung, polit. Willensbildung, ... Was werden Menschen demnächst kaufen (was sie vielleicht noch
gar nicht wissen)?
The Lance Armstrong Performance Program: Seven Weeks to the Perfect Ride by Lance Armstrong, Chris Carmichael, & Peter Jore Nye
[Gruhl, Guha, Kumar, Novak, & Tomkins, Proc. SIGKDD 2005]
9Ziele und Fragen: Bsp. 3 / Customer Relationship Management
Warum in ein Geschäft gehen ...
... wenn es doch alles im Internet gibt?
10Ziele und Fragen: Bsp. 4 / UsabilityWie kann ein Informationssystem weltweit, d.h. für verschiedenste Nutzergruppen, nutzbar gemacht werden?
11
Web Mining
12
Web Mining
Knowledge discovery (aka Data mining):
“the non-trivial process of identifying valid, novel, potentially useful, and ultimately understandable patterns in data.” 1
Web Mining: die Anwendung von Data-Mining-Techniken auf Inhalt, (Hyperlink-) Struktur und Nutzung von Webressourcen. Webmining-Gebiete:
Web content mining
Web structure mining
Web usage mining
1 Fayyad, U.M., Piatetsky-Shapiro, G., Smyth, P., & Uthurusamy, R. (Eds.) (1996). Advances in Knowledge Discovery and Data Mining. Boston, MA: AAAI/MIT Press
13
Muster, Data-Mining-Aufgaben, Methodenbeispiele
Globale Muster Deskription
– Clustering
» K-means, EM, hierarchisches Clustern, ...
– Hidden Markov Modelle
– Zitationsmuster Prädiktion
– Klassifikation
» Bayes-Verfahren, Entschei-dungsbäume, Support Vector Machines, ...
– Regression Lokale Muster
Häufige Itemsets, Sequenzen, Subgraphen
» A priori und abgeleitete Verfahren Assoziationsregeln Cliquen (“Web Communities“)
14
Anwendungsbereiche, die (u.a.) Web Mining einsetzen
Suchmaschinen: RankingSuchmaschinen: Ranking
Digitale BibliothekenDigitale Bibliotheken
e-Learninge-Learning
WissensmanagementWissensmanagementInformationssuche, ubiquitäre Information
Informationssuche, ubiquitäre Information
Semantic WebSemantic Web
Suchmaschinen: Query Mining
Suchmaschinen: Query Mining
Kennzahlen für den e-Commerce
Kennzahlen für den e-Commerce
Evaluation von Informationssystemen
Evaluation von Informationssystemen
E-PrivacyE-Privacy Trend-Entdeckung, Evolution
Trend-Entdeckung, Evolution
Entdeckung von Missbrauch (fraud detection)
Entdeckung von Missbrauch (fraud detection)
Empfehlungssysteme (z.B. cross-/up-selling), Personalisierung
Empfehlungssysteme (z.B. cross-/up-selling), Personalisierung
Suchmaschinen: Dokumenten-Erschließung
Suchmaschinen: Dokumenten-Erschließung
Web CommunitiesWeb Communities
Blog MiningBlog Mining
Spam-ErkennungSpam-Erkennung
Plagiarismus-Entdeckung
Plagiarismus-Entdeckung
Marktforschung, z.B. Kundensegmentierung
Marktforschung, z.B. Kundensegmentierung
15
Wer wird demnächst welches Buch kaufen (und wo wohnt er/sie)?
1. http://www.amazon.com/gp/registry/search.html/?encoding=UTF8&type=wishlist&field-name=edgar&page=1 contains “edgar“ wishlist URLs:
http://www.amazon.com/gp/registry/registry.html/?encoding=UTF8&type=wishlist&id=theFirstEdgar...
2. 6-line shell script + wget : Viele Wunschlisten
3. ls -1 | xargs grep -HiFof bookSpec.txt > matches.txt (bookSpec: ISBN or term):
book {person name + city}
4. http://people.yahoo.com/
book {name + address}
5. http://www.ontok.com/ geocoder:
book {geo-coordinates}
6. Google Maps API: Geo-Koordinaten in Karte einfügen
[Owad (2006). http://www.applefritter.com/bannedbooks]
16Welche Bücher werden demnächst gekauft
(ohne dass dieses explizit gesagt wurde)?
[Gruhl, Guha, Kumar, Novak, & Tomkins, Proc. SIGKDD 2005]Blog Tagging / Recommendation: [Berendt & Navigli, Proc. AAAI Spring Sympos. Weblogging 2006]
1. Sales rank: http://www.amazon.com/gp/aws/landing.html
2. Blogs (+) data: http://www.almaden.ibm.com/webfountain/
3. Einfache Keyword (Namen, Buchtitel)-Suchmaschine
4. Definition von „spike“ alle ranks > 1 Woche weg vom min. rank m sind >
max(m+50,1.5*m)
5. Zeitreihen-Kreuzkorrelation für den besten lag k = arg max cBS(k)
Cross-correlation rBS(k) = cBS(k) / sqrt( cBB(0) * cSS(0) )
6. Vorhersage-Modelle Moving average, weighted least-squares prediction; Markov
predictor
Spike predictor on blog mention rank data
– Predict spike if current rank > max. rank (history) and > mean of history + 4 * standard deviation of history
17
Web Usage Mining...p3ee24304.dip.t-dialin.net - - [19/Mar/2002:12:03:51 +0100]"GET /search.html?t=jane%20austen&SID=023785&ord=asc HTTP/1.0" 200 1759 p3ee24304.dip.t-dialin.net - - [19/Mar/2002:12:05:06 +0100] "GET /search.html?t=jane%20austen&m=video&SID=023785&ord=desc HTTP/1.0" 200 8450p3ee24304.dip.t-dialin.net - - [19/Mar/2002:12:06:41 +0100] "GET /view.asp?id=3456&SID=023785 HTTP/1.0" 200 3478...
Ver-stehen
18
Mining-Verfahren: Assoziationsregel-Mining Sequenzmining Graphmining Semantic Web Mining
Anwendungsfragen: Distributionskanäle Informationssuche Demographische Variablen
2 Fallstudien zum Web Usage Mining
19
Anwendung: Distributionskanal-Mix bei Multi-Channel-Händlern
Fragen:
• Wie verhalten sich Kunden? Sind Kundensegmente erkennbar?
• Kann Mining zur Erfolgsmessung in Multi-Channel-Sites beitragen?
Fragen:
• Wie verhalten sich Kunden? Sind Kundensegmente erkennbar?
• Kann Mining zur Erfolgsmessung in Multi-Channel-Sites beitragen?
52 5467 69
48 4633 31
0%
10%
20%
30%
40%
50%
60%
70%
80%
90%
100%
1999 2000 2001 2002 (proj.)
Pure Internetcompanies
Multi-channelbusinesses
[BCG 2002]
20
Einschub:Das Web als optimaler Vertriebskanal für Suchgüter?!
Erfahrungsgut Winterjacke
Suchgut Kamera
[Berendt, Günther, & Spiekermann, Comm. of the ACM,2005; Berendt, Data Mining and Knowlege Disc. 2002]
21
Schritt 1: Modellierung Ontologien
22
Webseiten/Anfragen: Inhalt und Dienst Site-Modell = (Inhalts-Ontologie, Dienst-Ontologie)
Inhalt: Produkt Produktkategorie ...
Inhalts-Taxonomie/-Ontologie
Inhalt: Produkt Produktkategorie ...
Inhalts-Taxonomie/-Ontologie
Dienst: Suche nach Marke Suche DienstSuche nach Preis Suche DienstSofortbestellung Bestellung DienstProduktbeschreibung Dienst...
Dienst-Taxonomie/-Ontologie
Dienst: Suche nach Marke Suche DienstSuche nach Preis Suche DienstSofortbestellung Bestellung DienstProduktbeschreibung Dienst...
Dienst-Taxonomie/-Ontologie
23
Was ist eine Ontologie?
Definition Kernontologie mit Axiomen:
Eine Struktur O := ( C, ≤C , R , σ , ≤R , A ) aus
zwei disjunkten Mengen C (Konzept-Identifizierer) und R (Relationen-Identifizierer)
einer partiellen Ordnung ≤C auf C (Konzept-Hierarchie o. Taxonomie)
einer Funktion σ : R → C+ (Signatur), wobei C+ die Menge aller finiten Tupel von Elementen in C ist.
einer partiellen Ordnung ≤R auf R (Relationen-Hierarchie), wobei
r1 ≤R r2 impliziert |σ(r1)| = |σ(r2)|
i (σ(r1)) ≤C i (σ(r2)) für alle 1 ≤ i ≤ |σ(r1)|,
mit i der Projektion auf die i-te Komponente
einer Menge A von Axiomen in einer logischen Sprache L[s. Stumme, Hotho, & Berendt, Journal of Web Semantics, in press, sowie Quellen dort]
24
Schritt 2: Was bedeutet ein Klick?
25
Atomare Anwendungsereignisse
Def.:
Ein Tupel AAE := (s,c) mit
s: ein Konzept oder eine Relation aus der Dienste-Ontologie S des Site-Modells (S,C),
c: ein Konzept oder eine Relation aus der Inhalts-Ontologie C des Site-Modells
Eine Anfrage und somit eine URL / Webseite kann einem oder mehreren AAEs zugeordnet werden.
[vereinfacht und modifiziert nach Berendt, Stumme, & Hotho. In Data Mining: Next Generation Challenges and Future Directions. AAAI/MIT Press 2004]
26
Webseite/Anfrage Anwendungsereignis: Extraktion von Konzepten und Relationen aus URLs
1. URL in einer Semantic-Web-Site mit Konzepten und Relationen :
FORALL N, ITEMS <- ITEMS: Headset [istZubehoerVon ->> "M57"] and ITEMS: Product [name->>N].
[nach ka2portal.aifb.uni-karlsruhe.de – Ontologie, Wissensbasis, Anfragen in F-Logic]
2. URL einer typischen datenbankgenerierten Webseite:
http://www.theShop.com/show.html?product=m57& options=zubehoer&search=name
[Oberle, Berendt, Hotho, & Gonzalez, Proc. AWIC 2003; Berendt & Spiliopoulou, VLDB Journal 2000;
Berendt, Data Mining and Knowledge Discovery 2002]
27
Schritt 3: Was bedeutet eine Sequenz von Anfragen?
28
Komplexe Anwendungsereignisse
Def.:
Ein CAE ist eine nichtleere
Sequenz
Regulärer Ausdruck
Graphenstruktur
deren Elemente AAEs sind.
[vereinfacht und modifiziert nach Berendt, Stumme, & Hotho. In Data Mining: Next Generation Challenges and Future Directions. AAAI/MIT Press 2004]
29
Semantik: Der Kaufprozess als Dienst-Ontologie
30
Mining 1: Der Kaufprozess als regulärer Ausdruck
Alternativ: n = online, f = offline, a = acquisition etc.; Kaufprozess = ( na | (fa,fi?) ) , ni , no , ( (np,nd,ns) | (np,nd,fs) | (np,fd,fs) | (fp,fd,fs) )
31
Mining 2: Assoziationsregeln zur Untersuchung derPräferenzen für Handlungskonzepte im Kaufprozess
Studie basierend auf ~100K Sessions, ~13K Transaktionen aus 2002 bei einem führenden europäischen Konsumelektronik-Anbieter zeigte u.a.:
Online payment Direct delivery (s=0.27, c=0.97) < 1/3 tradit. Online-User!
Online payment In-store pickup (s=0.02, c=0.03)
Cash on delivery Direct delivery (s=0.02, c=0.03)
In-store payment In-store pickup (s=0.69, c=0.94)
Site wird v.a. zur Informationssuche genutzt.
Kennzahlen („Web metrics “), z.B.:
• Konversionseffizienz• Offline-Konversion • Effektivität und Effizienz von Suchoptionen
Kennzahlen („Web metrics “), z.B.:
• Konversionseffizienz• Offline-Konversion • Effektivität und Effizienz von Suchoptionen
[Berendt & Spiliopoulou, VLDB Journal, 2000,Berendt, Data Mining and Knowl. Discovery, 2002; Teltzrow & Berendt, Proc. WebKDD 2003]
32
70.065.0
60.055.0
50.045.0
40.035.0
30.025.0
20.015.0
10.05.0
0.0
3000
2000
1000
0
Customers
Std.Dev.: 9.32,
Mean: 10.0, N=13653
km
Resultate: Einfluss von demographischen Variablen, Einfluss des Offline-Distributionskanals ?!
Signifikante Pearson-Korrelationen:
Anzahl der Kunden in PLZ-Gebiet, normalisiert durch Anzahl der Einwohner des PLZ-Gebiets Distanz zum nächsten Geschäft (r = -0.3, p < 0.001).
Anzahl der Einwohner in PLZ-Gebiet Distanz zum nächsten Geschäft (r =-0.01, p<0.001)
Shops
Customers
33
Schritt 4: Was bedeuten weitere Strukturen auf Anfragen?
34
Anwendung: Suche in Informationsportalen; e-Health
Fragen:
• Wie suchen Nutzer? Gibt es unterschiedliche Suchtypen?
• Führen unterschiedliche Suchoptionen zu unterschiedlichen Arten der Exploration?
• Zusammenhänge zwischen Verhalten u. Sprache, Kultur, Domänenwissen?
Fragen:
• Wie suchen Nutzer? Gibt es unterschiedliche Suchtypen?
• Führen unterschiedliche Suchoptionen zu unterschiedlichen Arten der Exploration?
• Zusammenhänge zwischen Verhalten u. Sprache, Kultur, Domänenwissen?
35
Semantik: Dienst-Ontologie
Alphabetical
search
Diagnosis 21002
Diagnosis info
TOP
Search
36
[Berendt, Proc. WebKDD 2005]
Mining:Häufige Subgraphen, Visualisierung mit Detail & Kontext
37Grundidee des Mining-Algorithmus: Suche im Muster-Raum (“Apriori”)
a – b – c | d
a – b – c a – b – d c – b – d
a – b b – c b – d
Ø
Duplikatenerkennung undEinbettung in die Datenerfordern Isomorphietestsprinzipiell NP(-vollständig)Was sind geeignete Vereinfachungen?
Duplikatenerkennung undEinbettung in die Datenerfordern Isomorphietestsprinzipiell NP(-vollständig)Was sind geeignete Vereinfachungen?
38
Apriori-Algorithmus zum Finden häufiger Patterns – Grundprinzip
FP all frequent patterns of size 1; k 2
while k ≤ KMax do
extend frequent patterns of size (k-1) to patterns of size k
(processing each candidate further only once)
for each candidate pattern cp do
if cp is frequent in the data
add cp to the set of k-frequent patterns FP
k++
Candidate generation
Support pruning
Duplicate detection
Subgraph embedding
Lösungsansatz:
• Isomorphie-Tests durch:• Bekannte Automorphismen• Kanonische Formen
• IP: sortierte Kantenlisten• AP: spezielle kan. Formen für Pfade, Bäume, zyklische Graphen
• Verringerung der Duplikatengenerierung durch kanonische Formen • Reduktion von Zugriffen auf die Daten / Subgraphen-Isomorphietests [Weiterentw. v. Nijssen & Kok‘s Gaston, SIGKDD 2004]
Lösungsansatz:
• Isomorphie-Tests durch:• Bekannte Automorphismen• Kanonische Formen
• IP: sortierte Kantenlisten• AP: spezielle kan. Formen für Pfade, Bäume, zyklische Graphen
• Verringerung der Duplikatengenerierung durch kanonische Formen • Reduktion von Zugriffen auf die Daten / Subgraphen-Isomorphietests [Weiterentw. v. Nijssen & Kok‘s Gaston, SIGKDD 2004]
39
Laufzeit-Verhalten: lineare Abhängigkeit von Datenmenge und Zahl der Muster
40
Suchverhalten: häufige abstrakte Muster
Diagnosen sind “Hubs" fürdie Navigation (5.3%, 4%)
Alphabetische Suche: hub-and-spoke → nur linguistische Relationen (6.4%)
Lokalisationssuche: linear / Tiefensuche → Suchverfeinerung
& medizinisches Wissen (5%)2 Studien (Webserverlog: 277K Sessions aus 188 Ländern; Webserverlog + Fragebogen: 165 Personen aus 34 Ländern): Suchmaschine, alphabetische Suche: v.a. Muttersprachler, Ärzte
Lokalisationssuche: nicht-muttersprachliche Patienten
Domänenwissen kompensiert geringe Sprachkenntnisse.
[Berendt, Proc. WebKDD 2005][Kralisch & Berendt, New Review of Hypermedia and Multimedia 2005]
41
Kontext: Projekte und weitere Aktivitäten
Leiterin des Bildungsportals www.schulweb.de (1999-2001) Projekte mit
dem Bildungsportal www.eduserver.de dem Digitalen-Bibliotheks-Portal edoc.hu-berlin.de E-Business-, E-Health-, Informations-Sites Deutsche Welle Neue Medien
EU 5FP Network of Excellence KDNet (2002-2004) EU 6FP Coord. Action KDUbiq (2005-), Leiterin von “HCI / Cognitive
Modelling“ Interdisziplinäres Zentrum „Ubiquitäre Information“, HU Berlin (2006-) Virtuelles Institut für Bildwissenschaft (2004-) Semantics, Web, und Mining: Workshops, Tutorials (seit 2001)
ECML/PKDD, AAAI, KDD, IJCAI, ...
Mitaufbau / Mitgestaltung des Masters Wirtschaftsinformatik sowie weitere Bachelor- und Masterstudiengänge (seit 2004)
Erasmus/Socrates-Kooperation mit der Informatischen Fakultät der Universidad Politécnica de Madrid (seit 2005)
42
Zusammenfassung und Ausblick
Web Mining ist Wissensentdeckung / Business Intelligence+ auf globalen Daten.
Datenquellen-Kombination: zentrale Chance und Risiko
Web Mining: Verständnis, Gestaltung/Verbesserung, Evaluation von Informationssystemen
Web Usage Mining: wertvoll, da Verhaltensbeobachtung
Aktuelle Projekte:
Ubiquitäre Wissensentdeckung
Semantic Web Mining für Partizipative Medien (Blogs, ...)
Digitale Bibliotheken: wissensbasiertes eLearning für das wissenschaftliche Schreiben
43
… für Ihre Aufmerksamkeit!
Danke …
44
Bildnachweise- mit herzlichem Dank an die Internet-Gemeinde! -
S.5: http://www.ncgia.ucsb.edu/pubs/snow/snow.html
S.9: http://www.santeecooperkids.com/culver/sse_root/body/potato.html
S. 10: http://www.mitretek.org/gbc/images/pic_doctor.jpg und http://thecia.com.au/reviews/b/images/brokeback-mountain-3.jpg
Weitere Abbildungen wurden den zitierten Quellen entnommen bzw. sind Screenshots der untersuchten Websites.