Einführung in Web Science

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

KONTAKT

info@muncca.comhttp://muncca.com

muncca GmbHOttostrasse 297000ChurSwitzerland