Hallo zusammen,
für meine Masterarbeit suche ich gerade nach Möglichkeiten, aus einer
Datenmenge ähnliche Objekte zu finden. Bei Amazon kennt ihr ja ist es
ähnlich dort erscheint auch immer Produkte, die andere, ähnliche Käufer
gekauft haben. Wie funktioniert so etwas statistisch oder welche
Stichwörter könnte ich für meine Literaturrecherche verwenden?
Viele Grüße
Chris
Christian S. schrieb:> für meine Masterarbeit suche ich gerade nach Möglichkeiten, aus einer> Datenmenge ähnliche Objekte zu finden.
OK.
> Bei Amazon kennt ihr ja ist es> ähnlich dort erscheint auch immer Produkte, die andere, ähnliche Käufer> gekauft haben. Wie funktioniert so etwas statistisch oder welche> Stichwörter könnte ich für meine Literaturrecherche verwenden?
Statistik ist da gar keine im Spiel. Und Amazon vergleicht auch keine
Produkte. Wenn überhaupt, dann vergleicht Amazon das Käuferverhalten.
Modelliert wird sowas typischweise über einen Graph. Achtung: nicht das
Ding von "graphische Darstellung" sondern das andere, bestehend aus
Knoten die durch Kanten verbunden sind.
Bei Amazon wäre jedes Produkt ein Knoten. Wenn ein Kunde sowohl Produkt
A als auch Produkt B kauft, wird im Graph eine Kante von A nach B
eingefügt. Praktisch wird man Kanten ein Gewicht geben. So wird man
bspw. wichten wieviel Zeit zwischen dem Kauf von A und B vergangen ist.
Und wenn mehrere Kunden A und B kaufen, dann erhöht sich das Gewicht der
Kante entsprechend.
Wenn jetzt ein Kunde Produkt A kauft, schaut Amazon einfach welche
Kanten von A ausgehen und zeigt alle die an, deren Gewicht oberhalb
einer gewissen Schranke liegt.
Hilft dir das jetzt bei deinem Problem? Ich denke, nein. Du mußtest
zuerst mal Ähnlichkeit quantifizieren. Ein einfacher Ansatz wäre, N
Objekteigenschaften Werte zwischen z.B. 0 und 100 zuzuweisen. Dann ist
jedem Objekt ein Punkt in einem N-dimensionalen Raum zugeordnet. Als Maß
für die Ähnlichkeit könnte man jetzt den euklidischen Abstand der Punkte
nehmen:
Objekt A = (a1, a2, a3, ..., aN)
Objekt B = (b1, b2, b3, ..., bN)
Abstand D(A, B) = sqrt((a1-b1)² + (a2-b2)² + ... + (aN-bN)²)
Identische Objekte haben den Abstand 0 und ganz allgemein gilt daß die
Ähnlichkeit umso größer ist je kleiner der Abstand ist. In der Praxis
will man verschiedene Eigenschaften vielleicht verschieden bewerten.
Dazu könnte man vor die quadratischen Glieder jeweils noch einen
Wichtungsfaktor setzen.
XL
Das Proble ist erst mal Aehnlichkeit zu definieren. Und dann auf
Datensets anzuwenden. Computer koennen nur rechnen. Sprache ist schon
sehr schwierig, und nur regelbasiert moeglich.
Es gab mal assoziative Memories, die haetten sowas auf viel tieferem
Level tun sollen, da hoert man aber nichts mehr davon
Super ihr habt mit gut für einen ersten Überblick geholfen. Wie wird
dann ausgehend von einem Graphennetzwerk die Ähnlichkeit definiert? Gibt
es hierzu gute Literatur oder habt ihr ein Beispiel?
@a-za-z0-9
Deine Ekklärung war super, - Danke nur die Angelegenheit mit der
Ähnlichkeit kannst du das etwas genauer erklären? Danke!
Da ist nix mit Ähnlichkeit. Wenn du einen Artikel 4711 auf deinen
Bestellzettel setzt, dann gucken sie nach, wer noch 4711 bestellt hat
und durchforsten diese Bestellungen nach anderen Artikeln.
Aus diesen anderen Artikeln werden dann Vorschläge erzeugt und so
unsinnig sind sie zuweilen auch.
Christian S. schrieb:> Super ihr habt mit gut für einen ersten Überblick geholfen. Wie wird> dann ausgehend von einem Graphennetzwerk die Ähnlichkeit definiert?
Bei der Modellierung als Graph ist die Ähnlichkeit (auch "Nähe",
"Kompatibilität" etc. je nach Festlegung des Kantengewichtes) direkt
durch das Gewicht der Kante zwischen den beiden zu vergleichenden Knoten
gegeben. Keine Kante zählt dabei als Gewicht=0 ~=~ keine Ähnlichkeit.
Allerdings ist es alles andere als trivial, einen wirklich großen
Graphen für sagen wir mal 10 Mio. Produkte aus einen Onlineshop auch
irgendwo abzuspeichern und dann effizient Operationen drauf auszuführen.
Da muß man dann schon etwas mehr Gehirnschmalz reinstecken.
Typischerweise sind solche Graphen aber sehr dünn besetzt, was die Sache
wieder erleichtert.
> @a-za-z0-9> Deine Ekklärung war super, - Danke nur die Angelegenheit mit der> Ähnlichkeit kannst du das etwas genauer erklären? Danke!
Fang einfach mit einem kleinen Beispiel an. Die Objekte sind Fahrzuge.
Wir haben zwei Merkmale: Höchstgeschwindigkeit und Farbe. Jetzt malst du
dir auf ein Blatt ein Diagramm. An die eine Achse schreibst du v_max,
die Achse geht vielleicht von 4km/h bis 300km/h. Die andere Achse heißt
"Farbe" und du machst z.B. alle 10 Einheiten einen Strich und schreibst
Farben dran: weiß, silber, gelb, orange, rot, ...
Jedes Fahrzeug ergibt nun einen Punkt im Diagramm. Je näher zwei Punkte
sind, desto ähnlicher sind sich die Fahrzeuge. Wenn du ein drittes
Merkmal dazu nimmst, wird aus der Ebene ein 3-dimensionaler Raum mit
Punkten darin. Und für den allgemeinen Fall mit N Eigenschaften ist es
halt ein n-dimensionaler Raum. Der euklidische Abstand, den ich gegeben
habe, entspricht dabei dem "gewohnten" Abstand, den du auch mit dem
Lineal messen würdest.
Auch den Einfluß der Wichtung kann man an diesem Beispiel schön sehen.
Ein silberner Golf hat von einem roten Golf einen Abstand von 30.
Genauso wie ein gelbes Moped mit v_max=100 von einem gelben Polo mit
v_max=130. Je nachdem, ob Übereinstimmung bei der Farbe wichtiger ist,
ober Übereinstimmung bei der Maximalgeschwindigkeit, würde man die
Beiträge der jeweiligen Eigenschaft zum Abstand mit einem bestimmten
Faktor versehen. Je größer der Faktor für ein Merkmal, desto ähnlicher
müssen sich die Objekte bezüglich dieses Merkmals sein. Bspw. hättest du
auf der Farbachse die farben auch mit Abstand 100 anordnen können. Dann
wäre die Farbe viel wichtiger bei der Beurteilung des Abstands.
Der praktische Wert des Konzepts steht und fällt dabei mit der Auswahl
der Merkmale und der Wichtung derselben.
XL
Uhu Uhuhu schrieb:> Da ist nix mit Ähnlichkeit. Wenn du einen Artikel 4711 auf deinen> Bestellzettel setzt, dann gucken sie nach, wer noch 4711 bestellt hat> und durchforsten diese Bestellungen nach anderen Artikeln.
Doch. "Ähnlichkeit" ist ja zunächst mal ein völlig undefinierter
Begriff. Amazon definiert Ähnlichkeit (oder Zusammengehörigkeit oder wie
immer man es nennen will) in diesem Fall nun genau als diejenigen
Produkte, die andere Käufer des jeweiligen Produkts auch gekauft haben.
Das macht auch intuitiv Sinn: Wer ein Buch über Elektronik gekauft hat,
der wird mit grösserer Wahrscheinlichkeit ein weiteres Buch über
Elektronik kaufen, als eines über Pferdezucht. Und niemand würde
abstreiten, dass zwei Elektronikbücher sich in vieler Hinsicht ähnlicher
sind als ein Buch über Pferdezucht und eines über Elektronik.
P. M. schrieb:> Das macht auch intuitiv Sinn: Wer ein Buch über Elektronik gekauft hat,> der wird mit grösserer Wahrscheinlichkeit ein weiteres Buch über> Elektronik kaufen, als eines über Pferdezucht.
Nur kommt zuweilen eben auch das Buch über Pferdezucht in die
Vorschlagsliste.
Ich glaube nicht, daß die die Graphentheorie bemühen, um zu ihren
"Vorschlägen" zu kommen.
Ein nettes Beispiel sind die Werbe-Mails, die ich von EBay bekomme. Das
ist immer ein fröhliches Sammelsurium von irgendwelchem
Elektronikkrempel und Mode - völliger Schwachsinn, aber durchaus
erklärbar, wenn man den dümmstmöglichen Algorithmus ansetzt.
Gibt es für das Verfahren von Axel Schwenke (a-za-z0-9) Stichworte, um
die "Vorhersage" von Daten mittels Graphen zu repräsentieren und ggfs
Suchalogithmen für bestimmte Fragestellungen zu finden? Ich möchte gerne
Literatur dazu suchen - Danke !
Christian S. schrieb:> Gibt es für das Verfahren von Axel Schwenke (a-za-z0-9) Stichworte, um> die "Vorhersage" von Daten mittels Graphen zu repräsentieren und ggfs> Suchalogithmen für bestimmte Fragestellungen zu finden?
Die Sache mit dem Graph meinst du? Das ist weniger ein Verfahren als
vielmehr ein (naheliegendes?) Modell. Das mathematische Fachgebiet
dazu heißt - wenig überraschend - Graphentheorie. Dieses Gebiet hat
viele Berührungspunkte mit anderen. Bspw. ist ein Baum aus der
Informatik eine spezielle Art von Graph (einer ohne Kreise). Netzwerke
sind Graphen. Dito Leiterplatten (einseitig geroutete sind planare
Graphen). Spiele der Art zeichne die Figur in einem Zug sind
Anwendungen der Graphentheorie. etc. pp
XL
Fun Fact: eine mögliche Darstellungsform für Graphen ist eine
http://de.wikipedia.org/wiki/Adjazenzmatrix
Wenn man in dieser Matrix statt 0 und 1 das Gewicht der jeweiligen Kante
speichert (wobei "keine Kante" dem Gewicht 0 entspricht) dann hat man
genau die Ähnlichkeitsmatrix. Da eine Ähnlichkeitsrelation symmetrisch
ist, ist auch die Matrix symmetrisch, was wiederum einem ungerichteten
Graphen entspricht.
Der Trick bei Amazon & Co besteht nun darin, nicht die volle Matrix (und
auch nicht die Hälfte) zu speichern. Das wäre aus mehreren Gründen
unökonomisch, u.a. schon deswegen, weil eine solche Matrix für alle
Amazon-Artikel sehr viele Nullen enthalten wird.
Eine Strategie, die das früher mal genannte Paper andeutet, besteht
darin, zwischen bestimmten Produktgruppen gar keine Ähnlichkeiten
anzunehmen. Im Falle eines Graphen zerfällt der dann in mehrere,
miteinander nicht verbundene Zusammenhangskomponenten. In der Matrix
äußert sich das bei geeigneter Anordung der Elemente als große
quadratische Bereiche, die nur Nullen enthalten.
Dazu ein Beispiel: 4 Elemente, A, B, C und D. Die beiden Gruppen {A, B}
und {C, D} seien einander total unähnlich. Die Matrix anthält dann
entsprechend große Bereiche mit Nullen:
1
|A B C D
2
-+-------
3
A|. . 0 0
4
B|. . 0 0
5
C|0 0 . .
6
D|0 0 . .
Man könnte die Matrix auch als zwei 2x2 Matrizen speichern, die wiederum
je einer der beiden Komponenten des Graphen entsprechen.
Ist doch schön, wie alle Wege nach Rom führen, oder? :)
XL
Eine eigene Frage?
Dieser Thread ist über 12 Jahre alt.
Stell sie in einem eigenen Thread – dort lesen mehr Leute mit, und sie wird öfter und schneller beantwortet.
