Embed Size (px)
Web IntelligenceResearch and Engineering Corsin Capol
Einführung in Web Science
Die Wissenschaft des Web und Social Media Metriken
Web Science als interdisziplinäre Wissenschaft
Quelle Bild: http://blogs.exeter.ac.uk/wip/blog/2010/05/28/the-emerging-web-science/
AgendaThema
Vorstellung
ÜberblicküberdieTechnologien derWebScience
Pause
Machine Learning
Pause
Workshop Clustering
Vorstellung
«We create value from data by providing innovative, data driven software»
Software Development | Media Monitoring | Information Retrieval
http://muncca.com
Lernziele• Begriff Web Science positionieren• Ziele und Methoden zum Erheben von Social
Media Metriken erläutern• Beschreiben inwiefern das Web und das Internet
als Netzwerk aufgefasst werden können• Grundzüge des Machine Learnings• Skizzieren, wozu Clustering Techniken dienen und
erläutern dieser
ÜBERBLICKDie Technologien der Web Science
Machine Learning• Ziele
– Durch algorithmische Analyse vorhandener Daten Voraussagen über andere Daten zu treffen
• Daten Analysieren• Zusammenhänge finden/aufzeigen• Daten Klassifizieren
• Einsatzgebiete– Recommender Systems– Information Retrieval– Big Data Analysis
Natural Language Processing• Ziele
– Präzisierung der Ergebnisse durch natürliche Sprache
– Computergestützte Verarbeitung natürlicher Sprachen
• Einsatzgebiete– Sentiment Analysis– Maschinelle Übersetzung– Information Retrieval
Natural Language Processing
Natural Language Processing
Natural Language Processing
PRP VBP NN NN NNI like sentiment analysis @munccagmbh
Part-of-Speech-Tagging (Penn Treebank Tagset)• VBP: Verb, non-3rd person singular present• PRP: Personal Pronoun• NN: Noun, singular or mass
Information Retrieval• Begriff erstmals gebraucht von Calvin N. Mooers (1950)
– The requirements of information retrieval, of finding informationwhose location or very existence is a priori unknown. . . .
• Ziele– Information
• Repräsentieren• Speichern• Organisieren• (Wieder-) auffinden
• Einsatzgebiete– Enterprise Search– Digital Library– Web Search
Garfield, E. (1997). A tribute to Calvin N. Mooers, a pioneer of informationretrieval. The Scientist, 11(6), 9.
Information Retrieval
Netzwerkanalyse• Ziele
– Analyse von Netzwerktopologien– Klassifizierung von Netzwerken– Bestimmung von Eigenschaften ganzer Netzwerke– Bestimmung von Eigenschaften einzelner Knoten
im Netzwerk• Einsatzgebiete
– Soziale Netze– World Wide Web– Stromnetz– Wassernetz
Netzwerkanalyse
Netzwerkanalyse der Programmiersprache Java (Klassen) mit Gephi
Semantic Web• “Most of today’s web is suitable for human consumption”• Ziele
– Web um Wissen erweitern, dass für Maschinen semantisch interpretierbar ist
• Einsatzgebiete– Personal Agents– Information Retrieval– Wissensmanagement– B2B / B2C
Semiotisches Dreieck: Charles MorrisCalegari, S., & Sanchez, E. (2008). Object-fuzzy concept network: An enrichment of ontologies in semantic information retrieval. Journal of the American Society for Information Science andTechnology.
Zeichen
BenutzerSituation
Syntax
Pragmatik
SemantikBedeutung
Semantic Web
http://dbpedia.org/ontology/university
MACHINE LEARNING
Abgrenzung• Anwendung von Methoden des maschinellen
Lernens auf grössere Datenbanken nennt man Data Mining
• Nutzt Methoden der Statistik• Prädiktives Modell
– Zukünftige Vorhersagen zu treffen• Deskriptives Modell
– Wissen aufgrund der Daten zu erlangen
Distanz- und Ähnlichkeitsmasse
• Distanzmasse– Unähnlichkeit zwischen zwei Vektoren– Bei grösserer Distanz sind sich die Vektoren weniger
ähnlich– Beispiele
• Euklidische Distanz• Minkowski Distanz• Canberra Distanz
• Ähnlichkeitsmasse– Ähnlichkeit zwischen zwei Vektoren– Wert ist bei grösserer Übereinstimmung höher
• Cosinus Similarity• Pearson Korrelationskoeffizient• Jaccard Koeffizient
Euklidische Distanz• Abstand zwischen zwei Vektoren im
mehrdimensionalen Raum• Bei der quadrierten euklidischen Distanz werden
grosse Abstände zwischen den Vektoren stärker gewichtet als kleine Abstände
d(x, y) = (xi − yi )2
i=1
n
∑
Jaccard-Koeffizient• Ähnlichkeitsmass für binäre Attribute• Mengenbezogen• Entwickelt von Schweizer Botaniker Paul Jaccard• Siehe auch Jaccard-Metrik• Wert zwischen 0 und 1
– Je näher bei 1, desto ähnlicher sind sich die Mengen
J(A,B) = | A∩B || A∪B |
Lernmethoden• Supervised Learning• Unsupervised Learning
Supervised Learning• Überwachtes Lernen• Die Eingabedaten und die dazugehörigen
Ausgabedaten, werden dazu verwendet um daraus die Abbildung der Eingabe auf die Ausgabe zu erlernen
• Trainingsdaten sind notwendig• Unterscheidung zwischen
– Klassifikationsproblem• Eingabedaten analysieren und bestehender Klasse zuordnen• Mustererkennung
– Regressionsproblem• Vorhersage quantitative Eigenschaften
Beispiele• K-Nearest-Neighbors• Naïve Bayes• Support Vector Machines• Decision Trees
Naïve Bayes• Klassifizierte Daten• Zuordnung neuer Objekte zu einer Klasse,
aufgrund Wahrscheinlichkeit• Naiv
– Mögliche Abhängigkeiten zwischen Eingabewerten, werden ignoriert und multivariantes Problem wird auf eine Gruppe von univarianten Problemen reduziert
• Effektive Methode zur Klassifizierung– Trainieren– Klassifizierung– Nicht sensitiv für irrelevante Features
Naïve BayesBeispiel
• Ausgangslage– 40 grüne Punkte
• P(X=grün) = 40/60 – 20 rote Punkte
• P(x=rot) = 20/60
• Vorgehen– Zeichnen einen Kreis um X und zähle die Punkte– Wahrscheinlichkeit berechnen
• P(X=grün) = 1/40 = 0.025• P(X=rot) = 3/20 = 0.15
– Wahrscheinlichkeiten multiplizieren• P(X=grün) = 4/6 * 1/40 = 1/60 = 0.017• P(X=rot) = 2/6 * 3/20 = 1/20 = 0.05
Quelle: http://www.statsoft.com/Textbook/Naive-Bayes-Classifier
Unsupervised Learning
• Unüberwachtes Lernen• Durch algorithmische Analyse der
Eingabedaten wird versucht, die Struktur in diesen Daten zu erkennen
• Nur die Eingabedaten sind bekannt
Beispiele• K-Means• DBSCAN• Singular Value Decomposition
Clustering• Clusteranalyseverfahren
– Unvollständig• Ergebnis lediglich eine räumliche Darstellung in einem
niedrigdimensionalen Raum• Zuordnung der Elemente (Klassifikationsobjekte) wird nicht
vorgenommen• Geometrische Methoden• Beispiel: Multiple Korrespondenzanalyse, Nichtmetrische
Mehrdimensionale Skalierung– Deterministisch
• Cluster werden berechnet und Elemente deterministisch zugeordnet• Disjunkt (nur einem Cluster), überlappend (mehreren Clustern
zugewiesen)• Beispiel für disjunktes deterministisches Verfahren ist K-Means
– Probabilistisch• Grundlage ist Wahrscheinlichkeit, dass Element zu einem Cluster
gehört
Hierarchisches Clustering
• Deterministisches Verfahren• Baumstruktur entsteht• Varianten
– Bottom-Up• Es wird mit allen Elementen gestartet und diese werden
sukzessiv zu einem Cluster verschmolzen
– Top-Down• Mit einem grossen Cluster starten und rekursiv in kleine
Cluster aufteilen
Hierarchisches Clustering• Vorgehen bei Bottom-up Algorithmus
1. Anfangs bildet jedes Element sein eigenes Clusterzentrum2. Zwei ähnlichsten Cluster suchen3. Clusterpaar verschmelzen
• Je nach Verfahren die Clusterzentren neu berechnen4. Wiederholen der Schritte
zwei und drei, bis alle Elemente zu einem Cluster gehören• Verfahren um die Clusterzentren zu berechnen
– Single Linkage• Cluster mit der geringsten Distanz werden verschmolzen
– Complete Linkage, Average Linkage, Median, Zentroid, Ward
Hierarchisches ClusteringBeispiel
• Ausgangslage– Fünf Elemente im mehrdimensionalen Raum– Hierarchisches Clustering – Single Linkage Verfahren– Euklidische Distanz– Bottom-Up– Jedes Element bildet eigener Cluster
Hierarchisches ClusteringBeispiel
• Dendrogramm• Hierarchische Zerlegung der Datenmenge in
kleinere Teilmengen• Baumstruktur• Wurzel repräsentiert Cluster mit
Gesamter Menge
K-Means• Disjunktes deterministisches Verfahren• Clusterzentren werden konstruiert zur Bildung von Clustern• Anzahl Cluster muss im voraus bekannt sein• Gefundene Cluster hängen von initial bestimmten
Zentren ab. Mehrfach durchführen.• Vorgehen
1. k-Clusterzentren zufällig festlegen2. Jedes Element dem naheliegendsten Clusterzenter zuordnen
• Distanzmass3. Clusterzentren berechnen (mehrdimensionaler Mittelwert)4. Schritte zwei und drei wiederholen, bis es keine Änderungen
mehr gibt oder die festgelegte Iterationstiefe erreicht wurde
K-MeansBeispiel
• Ausgangslage– Fünf Elemente und zwei zufällig platzierte Cluster
im mehrdimensionalen Raum– k-Means Clustering– Quadrierte Euklidische Distanz
K-MeansBeispiel
• Neue Clusterzentren berechnet
• Zuordnung mittels Distanzfunktion– Zuordnung hat sich nicht geändert
• Beenden des Clusterings
WORKSHOP CLUSTERING40 Minuten Workshop / 20 Minuten Präsentation
