Das BibSonomy

BibSonomy
Lesezeichen und Literatur verwalten in
sozialen Systemen
Dr. Andreas Hotho
Miranda Grahl, Robert Jäschke, Christoph Schmitz, Gerd Stumme
Soziale Bookmark-Systeme:
Kollaboratives Annotieren von Web-Resourcen
mit frei wählbaren Wörtern
Einfach zu benutzen, offen für jedermann
Ergänzt/überholt Semantic-Web-Ansatz
Gemeinsames Benutzen führt zu konvergierendem
Sprachgebrauch und emergenter Semantik.
Hier: http://www.bibsonomy.org/
BibSonomy@Kassel
2
Ausblick: Folksonomies & Co.
Das populärste System
dieser Art ist Flickr,
ein öffentliches
Fotoalbum.
IBM denkt an, sein
Intranet ähnlich zu
strukturieren, da
leichter zu warten.
Microsofts neues
Betriebssystem soll(te)
ähnlich werden.
BibSonomy@Kassel
3
Übersicht
Motivation
BibSonomy (Demo)
Soziale Bookmark-Systeme
und Folksonomies
Suche in Folksonomies
Trends entdecken
Lernen von Beziehungen
BibSonomy@Kassel
4
Bibsonomy
Bibsonomy ist ein Bookmark-Server:
Benutzer können ihre Bookmarks hochladen,
mit frei wählbaren “Tags” versehen,
und bei sich und anderen danach suchen.
Online unter: http://www.bibsonomy.org
BibSonomy@Kassel
5
Folksonomies
• Eine Folksonomy erlaubt es
Nutzern
mit Hilfe von Tags
Ressourcen
wie Bookmarks, Photos,
… zu beschreiben und zu
verwalten
• Leichtgewichtiges
Wissensmanagement
wenig Overhead
gut integriert in die tägliche
Arbeit
Gerd Stumme
28/09/06
6
Bibsonomy
Bibsonomy ist auch ein Literatur-Server:
Benutzer können Referenzen hochladen,
mit frei wählbaren “Tags” versehen,
und bei sich und anderen danach suchen.
BibSonomy@Kassel
7
Relationen in BibSonomy
BibSonomy@Kassel
8
Typische Tag-Wolke
BibSonomy@Kassel
9
Übersicht
Motivation
BibSonomy (Demo)
Soziale Bookmark-Systeme
und Folksonomies
Suche in Folksonomies
Trends entdecken
Lernen von Beziehungen
BibSonomy@Kassel
10
Folksonomy-Typen
Tagging von Objekten durch die
Gemeinschaft (z.B. Webseiten)
http://del.icio.us/
BibSonomy@Kassel
Tagging von Objekten die sonst
schwer suchbar sind (z.B. Bilder)
http://www.flickr.com
Thomas Vander Wal (http://www.personalinfocloud.com/2005/02/explaining_and_.html)
11
Def.: Folksonomy
Eine Folksonomy ist ein Tupel F := (U, T, R, Y, ≺) wobei
•
U, T, und R endliche Mengen sind, deren Elemente users, tags und
resources, heißen.
• Y ist eine dreistellige Relation zwischen ihnen, d.h. Y ⊆ U × T × R,
dessen Elemente tag assignments (TAS) heissen und
•
≺ ist eine benutzerspezifische Unter-/Obertag-Relation,
d.h. ≺ ⊆ U × T × T.
Die Personomy Pu von Benutzer u ist die Einschränkung von F auf u.
BibSonomy@Kassel
12
Evaluierung auf del.icio.us-Daten
Wir crawlten del.icio.us vom 27. bis 30.7.2005
und erhielten
•
•
•
•
|U| = 75,242 Nutzer,
|T| = 533,191 Tags,
|R| = 3,158,297 Resourcen, und
|Y| = 17,362,212 Tag-Zuordnungen.
BibSonomy@Kassel
13
Ergebnisse: Power-Law-Verteilung
BibSonomy@Kassel
14
Übersicht
Motivation
BibSonomy (Demo)
Soziale Bookmark-Systeme
und Folksonomies
Suche in Folksonomies
Trends entdecken
Lernen von Beziehungen
BibSonomy@Kassel
15
Suche in Folksonomies
PageRank-Ansatz ist sehr erfolgreich im Web (s. Google):
Autoritätswerte werden entlang der Hyperlinks propagiert.
Folksonomies haben eine andere Struktur als der Web-Graph:
Tag 12
User
3
User23
Tag
4
User34
Tag
User 1
3
2
User 2
4
3
User 3
4
User 4
Res 1
Res 2
Res 3
Web-Graph
Folksonomies
Wie kann ein Ranking-Verfahren für diese neue Struktur
aussehen?
BibSonomy@Kassel
16
Erster Ansatz: Adaptierter PageRank
Hyperkanten aufspalten in ungerichtete Kanten
V=U∪T∪R
E = {{u,t} | ∃ r ∈ R : (u,t,r) ∈ Y} ∪
{{t,r} | ∃ u ∈ U : (u,t,r) ∈ Y} ∪
{{u,r} | ∃ t ∈ T : (u,t,r) ∈ Y}
Iterative Gewichts-Propagation gemäß
x ← d Ax + (1-d) p
wobei A
x
p
d
BibSonomy@Kassel
die Adjazenzmatrix des Graphen ist,
der Rankvektor,
ein Präferenzvektor,
ein Gewichtungsfaktor.
17
Ergebnisse: Adaptierter PageRank
BibSonomy@Kassel
18
Ergebnisse: Adaptierter PageRank
http://slashdot.org/
0,0002613
http://pchere.blogspot.com/2005/02/absolutely-delicious-complete-tool.html
0,0002320
http://script.aculo.us/
0,0001770
http://www.adaptivepath.com/publications/essay s/archives/000385.php
0,0001654
http://johnvey .com/features/deliciousdirector/
0,0001593
http://en.wikipedia.org/wiki/Main_Page
0,0001407
http://www.flickr.com/
0,000137 6
http://www.goodfonts.org/
0,0001349
http://www.43folders.com/
0,0001160
http://www.csszengarden.com/
0,0001149
http://wellstyled.com/tools/colorscheme2/index -en.html
0,0001108
http://pro.html.it/esempio/nifty/
0,000107 0
http://www.alistapart.com/
0,0001059
http://postsecret.blogspot.com/
0,0001058
http://www.beelerspace.com/index .php?p=890
0,0001035
http://www.techsupportalert.com/best_46_free_utilities.htm
0,0001034
http://www.alv it.de/web-dev/
0,0001020
http://www.technorati.com/
0,0001015
BibSonomy@Kassel
http://www lifehacker com/
0 0001009
19
FolkRank: Thematisches Ranking
Durch Zuordnung von Gewicht zu nur einem Eintrag in
Präferenzvektor p in
x ← d Ax + (1-d) p
können relevante Seiten zu einem Thema gefunden werden.
Problem: In Folksonomies ist die globale Struktur zu dominant.
FolkRank-Lösung:
Berechne ausserdem iterativ den Fixpunkt von
x0 ← Ax0
und bilde den Vektor x - x0 .
BibSonomy@Kassel
20
Ergebnis für das tag: boomerang
PageRank ohne Präferenz
BibSonomy@Kassel
PageRank mit Präferenz
FolkRank mit Präferenz
21
Ergebnisse: Suche nach “Semantic Web”
PageRank ohne Präferenz
BibSonomy@Kassel
PageRank mit Präferenz
FolkRank mit Präferenzz
22
Ergebnisse: Suche nach “Semantic Web”
http:// www .semanticweb .org /
0,3761957
http://flink. semanticweb .org /
0,0005566
http:// simile .mit.edu/piggy -bank /
0,0003828
http://www.w3.org/2001/ sw/
0,0003216
http:// infomesh .net/2001/ swintro /
0,0002162
http://del. icio.us/register
0,0001745
http:// mspace .ecs .soton .ac.uk/
0,0001712
http:// www .adaptivepath .com/publications /essays /archives /000385.php
0,0001637
http:// www .ontoweb .org /
0,0001617
http:// www .aaai.org /AITopics /html /ontol .html
0,0001613
http:// simile .mit.edu/
0,0001395
http:// itip.evcc.jp/itipwiki/
0,0001256
http:// www .google .be/
0,0001224
http:// www .letterjames .de/index.html
0,0001224
http:// www .daml .org /
0,0001216
http:// shirky .com/writings /ontology _overrated .html
0,0001195
http:// jena.sourceforge .net/
0,0001167
http:// www .alistapart .com /
0,0001102
http:// www .federalconcierge .com/WritingBusinessCases .html
0,0001060
http:// pchere .blogspot .com/2005/02/ absolutely -delicious -complete -tool.html
0,0001059
http:// www .shirky.com/writings /semantic _syllogism .html
0,0001052
BibSonomy@Kassel
23
FolkRank: Zusammenfassung
Folkrank basiert nur auf der Folksonomy,
nicht auf dem Inhalt der Dokumente.
Geeignet für
Multimedia-Suche
Suche im Intranet
Empfiehlt dem Benutzer
andere Benutzer mit verwandten Interessen
andere Tags zum selben Thema
interessante Ressourcen
BibSonomy@Kassel
24
Übersicht
Motivation
BibSonomy (Demo)
Soziale Bookmark-Systeme
und Folksonomies
Suche in Folksonomies
Trends entdecken
Lernen von Beziehungen
BibSonomy@Kassel
25
Trend Detection in Folksonomies
• Wie kann man interessante Ressourcen, aufkommende Trends
oder Themen, an denen man interessiert ist, ausfindig
machen?
Menge an Ressourcen im WWW ist sehr groß
Nutzen des Wissens und der Erfahrung von Folksonomynutzern
Nutze FolkRank um den „popularity change“ zu berechnen
Fokussierung auf spezifische Themen möglich
Unabhängig von der Art der Ressource oder des Inhaltes
Del.icio.us posts zwischen 15. Juni 2004 und 15. Juli 2005
BibSonomy@Kassel
26
Trends in Delicious
Popularity Change:
BibSonomy@Kassel
27
Baseline mit Empty-tag
1
"empty_tag"
"blog"
"css"
"design"
"linux"
"music"
"news"
"programming"
"software"
"web"
0.9
0.8
0.7
rank
0.6
0.5
0.4
0.3
0.2
0.1
0
0
2
4
6
8
10
12
14
month
BibSonomy@Kassel
28
Entwicklung von Tags in Verbindung zum Tag “politics”
0.01
funny
religion
politics
bushco
bush
economics
usa
humor
activism
war
society
media
us
iraq
news
election
culture
0.008
rank
0.006
0.004
0.002
0
0
2
4
6
8
10
12
14
month
BibSonomy@Kassel
29
Globale Entwicklung der Ressourcen
1
http://www.intersmash.com/300images/
http://www.musicplasma.com/
http://www.pixy.cz/apps/barvy/index-en.html
http://bugmenot.com/
http://pchere.blogspot.com/2005/02/absolutely-delicious-complete-tool.html
http://www.ficml.org/jemimap/style/color/wheel.html
http://script.aculo.us/
http://www.flickr.com/
http://slashdot.org/
http://www.adaptivepath.com/publications/essays/archives/000385.php
0.8
rank
0.6
0.4
0.2
0
0
2
4
6
8
10
12
14
month
BibSonomy@Kassel
30
Änderung der Popularität von Ressourcen 15. Mai vs. 15. Juni 2005
Tags: ‘semantic web’, ‘semantic’, ‘web’, and ‘semanticweb’
BibSonomy@Kassel
31
Übersicht
Motivation
BibSonomy (Demo)
Soziale Bookmark-Systeme
und Folksonomies
Suche in Folksonomies
Trends entdecken
Lernen von Beziehungen
BibSonomy@Kassel
32
Mining Association Rules in Folksonomies
• Wir wenden Rule-Mining-Techniken an, um
Recommender zu erstellen
Tags vorzuschlagen
Communities zu finden
• Standard Rule-Mining arbeitet auf binären Relation:
z.B. contains(shopping transaction, item)
• Wir wenden Rule-Mining auf Folksonomies an
Ternäre Relation
verschiedene Projektionen
Apriori-Algorithmus
BibSonomy@Kassel
33
Mining Association Rules
• Betrachte Kontext K = (G, M, I)
• Untersuche Transaktionen g ∈ G bestehend aus Items m ∈ M
{{a,b,c,d}, {a,d,f,h}, {d,f,g,h}, ...}
Z. B. Warenkörbe
• Kann aufgefasst werden als Matrix der Inzidenzrelation I ⊆ G × M
t1
t2
t3
a
1
1
0
b
1
0
0
BibSonomy@Kassel
c
1
0
0
d
1
1
1
e
0
0
0
f
0
1
1
g
0
0
1
h
0
1
1
34
Mining Association Rules
Finde alle Regeln der Form
IF a basket contains items I = {i1,..., ik} ⊆ M
THEN it also contains item J = {j1,..., jl} ⊆ M
mit einer hohen confidence
( |(I ∪ J)´| / |I´| ≥ minconf for some given minconf ∈[0,1]. )
und mit einem hohen support.
( |(I ∪ J)´| / G ≥ minsupp for some given minsupp ∈[0,1]. )
Standard-Algorithmus: Apriori (Agrawal 1994)
BibSonomy@Kassel
35
Von Folksonomies zu Association Rules
Folksonomies haben eine triadische Natur:
Würfel Y anstelle der Matrix I
Tripartiter Hypergraph anstelle des bipartiten Graphen
Einfache Lösung:
ternäre Relation → Projektion auf dyadischen Kontext
→ Apriori-Algorithmus
Dimensionsreduktion:
konvertiere F = (U, T, R, Y) in ein K = (G, M, I) indem
man entlang einer Dimension eine Scheibe abschneidet
man projiziert und aggregiert
BibSonomy@Kassel
36
Zwei Beispielprojektionen
• K1 = (U x R, T, I1)
Wenn ein Nutzer Ressources mit Tags ti verschlagwortet, dann nutzt
er auch tj
Anwendung:
Tag-Empfehlungen
Lernen von Implikationen (subsumption)
• K2 = (T x U, R, I2)
Wenn Nutzer die Ressourcen ri mit einem speziellen Tag taggen,
dann Nutzen sie es auch, um rj zu taggen
Anwendung:
Entdecken von Communities
Empfehlen von Resource
BibSonomy@Kassel
37
Sample Projections
• K1 = (U x R, T, I1)
Wenn ein Nutzer Ressourcen mit Tags ti verschlagwortet,
dann nutzt er auch tj
Anwendung:
Tag-Empfehlungen
Lernen von Implikationen (subsumption)
BibSonomy@Kassel
38
Association Rules
• K2 = (T x U, R, I2)
Wenn Nutzer die Ressourcen ri mit einem speziellen Tag taggen,
dann Nutzen sie es auch, um rj zu taggen
Anwendung:
Entdecken von Communities
Empfehlen von Ressourcen
BibSonomy@Kassel
39
Association Rules
• K2 = (T x U, R, I2)
Wenn Nutzer die Ressourcen ri mit einem speziellen Tag taggen,
dann Nutzen sie es auch, um rj zu taggen
Anwendung:
Entdecken von Communities
Empfehlen von Ressourcen
BibSonomy@Kassel
40
Zusammenfassung: Folksonomies
Folksonomien überwinden den Wissensakquisitions-Flaschenhals
durch einfache Bedienung
und schnell wachsende Benutzerzahlen.
Unser FolkRank-Algorithmus unterstützt die Suche in
Folksonomies.
FolkRank bildet die Basis für die Methoden zur Trendentdeckung
Assoziationsregeln dienen der weiteren Strukturierung.
BibSonomy@Kassel
41
Ausblick
Spamerkennung
Entdecken von Communities
Skalierung des Rankingverfahrens
Recommender
Geotagging
…
BibSonomy@Kassel
42
Ausblick: Folksonomies & Co.
Zu guter Letzt:
Folksonomies werden
uns bei allen
relevanten Dingen
des täglichen Lebens
begleiten. ☺
BibSonomy@Kassel
43
Übersicht
http://www.kde.cs.uni-kassel.de/
Motivation
BibSonomy (Demo)
Soziale Bookmark-Systeme
und Folksonomies
Suche in Folksonomies
Trends entdecken
http://www.bibsonomy.org/
Lernen von Beziehungen
Ende
BibSonomy@Kassel
44