Klassifikation und Assoziationen von Interessen
Dr.-Ing. Thomas Schwotzer
5. Januar 2016
1
Einführung
Wir haben uns bisher viel mit Interessen beschäftigt. Diese Veranstaltung beschäftigt
sich mit der Analyse von Interessen. Wir wollen uns dem Thema aber allgemein
nähern, so dass die Ausführungen auch für anderen Anwendungeszenarien geeignet sind. Die Darstellungen dieser LN basieren nahezu vollständig auf [1, Kapitel
5] und wird Interessierten wärmstens zur vertiefenden Lektüre empfohlen.
Generell gehen wir davon aus, dass eine Menge an Interessen gesammelt
wurden. Zwei Fragen wollen wir uns heute widmen:
Klassifikation beschäftigt sich damit, (Mengen von) Interessen zu klassifizieren, d.h. unterschiedliche Interessen (und damit Nutzer) einer Klasse zuzuordnen oder eben nicht.
Assoziation können zwischen Interessen existieren. Regelmäßig ist es hilfreich
zu ermitteln, ob das Auftreten von Interessen Regeln folgt.
Beginnen wir mit der Klassifikation.
2
Klassifikation = Konzept
Eine Klassifikation ist prinzipiell schnell erklärt. Gehen wir von unseren Interessen aus. Alice hatte sich in vielen Beispielen für Java, die Programmiersprache
und Tauchen interessiert. Bob interessierte sich für Programmiersprachen allgemein.
Verallgemeinert kann man sagen, dass es eine Menge von Interessen I gibt.
Wir folgen im weiteren der Terminologie von [1]. Dort wird definiert:
Ein Konzept c ist eine einstellige Funktion, die einer Grundmenge einen
boolschen Wert zuordnet. Nehmen wir die Interessen als Grundmenge, so können
wir schreiben:
c : I → {0,1}
Die Funktion entscheidet demnach darüber, ob ein Element der Menge zum
Konzept passt. Das ist genau dann der Fall, wenn dem Element der Wert 1
1
zugewiesen wird. Ein solches Element wird Instanz von c oder auch positives
Beispiel von c genannt.
Die Menge aller positiven Beispiele wird auch Extension von c genannt.
Alle Elemente der Menge I, die keine positiven Beispiel sind, heißen negative Beispiele.
In [1] werden Eigenschaften von Konzepte definiert:
• Ein Konzept c ist vollständig genau dann wenn für alle positiven Beispiele b ∈ B gilt c(b) = 1. Anders gesagt: Das Konzept c ordnet tatsächlich
jedem positiven Beispiel den Wert 1 zu. Vollständige Konzepte erkennen
jedes positive Beispiel als solches.
• Ein Konzept c ist korrekt genau dann wenn für alle negativen b ∈ B gilt
c(b) = 0. Anders gesagt: Das Konzept c ordnet tatsächlich jedem negativen Beispiel den Wert 0 zu. Korrekte Konzepte erkennen jedes negative
Beispiel als solches.
• Ein Konzept c wird konsistent genannt, wenn es vollständig und korrekt
ist.
Das mag alles ein wenig abstrakt klingen. Man könnte sich zum Beispiel
denken, dass es doch unsinnig wäre, sich ein Konzept zu erdenken, das nicht
konsistent ist. Dabei ist aber zu bedenken, dass Konzepte nicht plötzlich auftauchen, sondern entwickelt werden müssen. Das ist in der Regel ein interativer
Prozess, in dem man versucht, ein konsistentes Konzept zu erzeugen.
Der Prozess der Erzeugung eines Konzeptes wird auch als Konzeptlernproblem bezeichnet. Für eine formale Definition sei auf [1, Abschnitt 5.4.3]
verwiesen.
Weniger formal kann man das Problem wir folgt beschreiben: Gegeben seien
einige positive und einige negative Beispiele. Ziel ist es nun, ein Konzept zu
finden, das vollständig ist über allen Beispielen.
Ein extrem einfaches Beispiel soll helfen. Dazu wählen wir Alice und Bob.
Wir definieren nun, dass Alice ein positives und Bob ein negatives Beispiel sein
möge. Gesucht ist nun ein vollständiges Konzept.
Zur Erinnnerung: Alice interessiert sich für Java und Tauchen. Bob interessiert sich für Programmiersprachen. Es gibt einige Möglichkeiten. Man könnte
das Konzept definieren:
• Ein Interesse ist eine Instanz, wenn es ein Interesse an Tauchen beinhaltet.
Alle anderen Interessen wird der Wert 0 zugewiesen.
• Ein Interesse ist eine Instanz, wenn es ein Interesse an Java beinhaltet.
Alle anderen Interessen wird der Wert 0 zugewiesen.
• Ein Interesse ist eine Instanz, wenn es ein Interesse an Java UND Tauchen
beinhaltet. Alle anderen Interessen wird der Wert 0 zugewiesen.
• Ein Interesse ist eine Instanz, wenn kein Interesse an Programmiersprachen
enthält.
2
Offensichtlich ist die Beispielmenge mit nur zwei Elementen auch sehr klein,
aber es zeigt hoffentlich das Prinzip des Problems.
Wir wollen noch ein anderes prinzipielles Problem anreißen: Angenommen,
wird würden Claudia als weiteres positives Beispiel heranziehen und Claudia
möge sich allgemein für Sport interessieren.
Alice und Claudia sind jeweils positive Beispiele. Sie haben allerdings kein
Interesse, das sich direkt überlappt. Zieht man allerdings den semantischen Zusammenhang hinzu, dass Tauchen ein Sport ist, kann ein mögliches Konzept
lauten:
Ein Interesse ist eine Instanz, wenn ein Interesse an Sport oder konkreten
Sportarten vorliegt. Im anderen Fall ist es keine Instanz.
In der Veranstaltung schauen wir uns das Verfahren der Versionsräume an.
Hier sei auf [1, Abschnitt 5.4.5] verwiesen.
3
Assoziationsregeln
Das Erkennen von (nicht-zufälligen) Zusammenhängen ist regelmäßig sinnnvoll
in wissensbasierten Systemen. Kommt es zum Beispiel häufiger vor, dass sich
Personen, die sich für Java interessieren auch ein Interesse an Tauschen haben?
Oder ist das eher Zufall.
Auch hier beziehen wir uns auf [1, Abschnitt 5.5.4]. Assoziationsregeln werden über einer Menge von Items ermittelt. Die Grundidee ist diese:
Es möge eine Menge I von Items (oder in unseren bisherige Fällen - Semantic
Tags - geben). Basierend auf der Grundmenge I können Teilmengen gebildet
werden. Das sind in Shark unsere Semantic Tag Sets die Teil eines Interesses
sein können, z.B. in der Topic-Dimension. In [1] wird eine solche Menge als
Transaktion bezeichnet - vermutlich Verkaufsszenarien Basis der Überlegungen
waren. Wir wollen eine solche Transaktion mit t bezeichnen. Sie ist inhaltlich
identisch z.B. zur Topic-Dimension eines Interesses in Shark.
Eine Datenbasis wird in diesem Zusammenhang als eine Menge von Transaktionen angesehen:
D = {t1 , t2 , .., tn }
Ausgehend von einem Item (einem Semantic Tag) kann man sich die Frage stellen, in welchen Transaktionen dieses Item (das Semantic Tag) enthalten
ist. Konkret könnte man sich fragen: In welchen Interessen liegt in der TopicDimension das Semantic Tag ’Tauchen’ vor?
Man kann die Frage auch verallgemeinern und fragen, in welcher Transaktion mehrere Items (mehrere Semantic Tags) vorkommen. Konkret könnte man
fragen, in welchem Interesse in der Topic-Dimension die Tags ”Tauchen” und
”Java” vorkommen.
Nennen wir diese Menge X. Es gilt X ⊆ tn , d.h. X ist Teilmenge einer Transaktion. Anhand dieser Überlegungen kann man nun die Anzahl von möglichen
Mengen X ermitteln:
|{t ∈ D|X ⊆ t}|
3
Diese Definition liefert eine natürliche Zahl. Sie nennt die Anzahl der Transaktionen, die die Menge X enthalten. In Bezug auf Shark beschreibt sie die
Anzahl der Interessen, die z.B. in der Topic-Dimension die Tags ”Tauchen” und
”Java” enthalten.
Interessant ist natürlich auch in welchen Verhältnis diese Zahl zur Gesamtmenge der Transaktionen steht. Für Shark: Wir wissen nun, welche Interessen
die gewünschten Tags enthalten. Wie groß ist diese Zahl aber nun im Verhältnis
zur Gesamtzahl der Interessen.
Dieses Verhältnis bezeichnet man als Support:
support(X) =
|{t∈D|X⊆t}|
|{D}|
Der Support gibt an, wie viele Transaktionen (Interessen) die die interessierenden Items (Semantic Tags) im Verhältnis zur Gesamtmenge enthalten. Der
Support ist 1, wenn die Items in allen Transaktionen vorhanden sind. Er ist
entsprechend 0, wenn sie in keiner vorliegen.
Soweit so gut. Wir versuchen nun aber Zusammenhänge zu ermitteln zwischen Item-Sets (Semantic Tag Sets) einer Transaktion (eines Interesses). Wir
fragen uns also: Zieht das Auftreten einer Menge von Items das Auftreten anderer Items nach sich? Zieht das Interesse an ’Tauchen’ ein Interesse an ’Java’
nach sich oder umgekehrt oder gar nicht?
Wir beschreiben das mathematisch: Wir suchen also zwei Mengen von Items
X und Y , die keine gemeinsamen Elemente besitzen:
X ∩ Y = ∅.
Wir wollen ja gerade ermitteln, welche Interessen andere nach sich ziehen,
daher ist der Schnitt beider Mengen leer. Wenn nicht würde man die FRage
zulassen, ob sich Leute, die sich für ’Tauchen’ interessieren für ’Tauchen’ interessieren. Dei Antwort ist offensichtlich ’Ja’, aber leider ohne jede Relevanz.
Gleichzeitig aber sollen X und Y in einer Transakation enthalten sein:
X ∪ Y ⊆ t.
Wir suchen nach Transaktionen, die ’Tauchen’ UND ’Java’ enthalten.
Anhand dieser Überlegungen lässt sich die Assoziationsregel einführen, siehe
auch [1, S. 148]. Es wird folgendes Symbol eingeführt:
X → Y mit X, Y ⊆ I|X ∩ Y = ∅
Eine Transaktion t erfüllt die die Regeln, wenn gilt X ∪ Y ⊆ t.
Daraus ergibt sich direkt:
support(X → Y ) = support(X ∪ Y )
Nun lässt sich die Konfidenz definieren als:
conf idence(X → Y ) =
support(X→Y )
support(X)
Der Nennen der Bruches ist die Anzahl aller Transaktionen, die X enthalten.
In unserem Beispiel wären es alle Transaktionen, die ’Tauchen’ enthalten. Der
4
Zähler des Bruches ist die Anzahl der Transaktionen, die ’Tauchen’ UND ’Java’
enthalten. Die Konfidenz sagt demnach aus, wie viele Transaktionen vorliegen,
in denen die Menge X die Menge Y nach sich zieht im Verhältnis zu allen
Transaktionen, die X enthalten.
Ist die Konfidenz 1, so zieht – jedenfalls in der gewählten Menge der Transaktionen – die Menge X zwingend die Menge Y nach sich. Wäre in unserem
Beispiel die Konfidenz 1, so könnte man (fälschlich) schlussfolgern, dass das
Interesse an ’Tauchen’ zwingend das Interesse an ’Java’ nach sich zieht. Die
Schlussfolgerung ist basierend auf der Konfidenz richtig. In jedem Fall ist aber
auch die Gesamtzahl der Transktionen zu betrachten. Diese sollten eine Anzahl
besitzen, dass sie statistische Relevanz besitzen.
Ist die Konfidenz 0 so zieht die Menge X die Menge Y in keinem Fall nach
sich. Je nach Anwendungen können Schwellwerte definiert werden, aber wann
die Konfidenz relevant erscheint.
In der Veranstaltung rechnen wir ein Beispiel durch.
Literatur
[1] Gabriele Kern-Isberner Christoph Beierle. Methoden wissensbasierter Systeme. Springer Vieweg, 2014.
5
© Copyright 2024 ExpyDoc
