Ähnlichkeitsberechnung für zwei Vektoren

Neue Frage »

05.07.2010, 20:28	online-dan	Auf diesen Beitrag antworten »
Ähnlichkeitsberechnung für zwei Vektoren Meine Frage: Hallo zusammen, nach langer Zeit beschäftige ich mich nun mal wieder mit einem mathematischen Problem. Und zwar schreibe ich ein Java-Programm, welches u.a. die Ähnlichkeit zwischen zwei Vektoren berechnen soll. Wie ich gelesen habe, kann man für so was das Kosinus Ähnlichkeitsmaß heranziehen. Ich habe nun in folgendem Beispiel mit meinem Programm mal den Kosinus Ähnlichkeitswert für zwei neun-dimensionale Vektoren a und b berechnet. Meine Bitte wäre nun an Euch: Könnt ihr mir vielleicht sagen, ob das Ergebnis bzw. der Rechenweg so ok sind. Es kommt mir nämlich etwas komisch vor, dass die beiden Vektoren zu 99% gleich sein sollen. Hier also das Beispiel: Vektor a hat diese Werte: $\begin{eqnarray} \begin{pmatrix} 5 \\ 7 \\ 2010 \\ 14 \\ 45 \\10 \\ 0 \\ 0 \\ 2 \end{pmatrix} \end{eqnarray}$ Vektor b hat diese Werte: $\begin{eqnarray} \begin{pmatrix} 23 \\ 12 \\ 2009 \\ 9 \\ 9 \\ 6 \\ 43 \\178 \\ 2 \end{pmatrix} \end{eqnarray}$ Meine Ideen: Als Formel für die Kosinus Ähnlichkeit habe ich dies hier verwendet: $\begin{eqnarray} \frac{a_1b_1 + a_2b_2 + ... + a_9b_9}{\sqrt{a_1² + a_2² + ... + a_9²} \sqrt{b_1² + b_2² + ... + b_9²} } \end{eqnarray}$ Im Zähler (a1b1 + a2b2 + ... + a9b9) komme ich damit auf 4038884.0 Den Nenner habe ich in zwei Schritten berechnet. Erst: Wurzel aus (a1² + a2² + ... + a9²) = 2010.596677605929 Dann: Wurzel aus (b1² + b2² + ... + b9²) = 2017.545290693619 Der Nenner ist dann das Produkt dieser beiden Werte. Als Endergebnis erhalte ich 0.9956647383064576 als Wert für die Cosinus-Ähnlichkeit dieser beiden Vektoren a und b. Kann das so stimmen??? Oder stimmt gar die angewandte Formel nicht? Vielleicht gibt es ja noch einfachere Formeln für eine Ähnlichkeitsberechnung zwischen zwei Vektoren. Vielen Dank Euch schon mal für Eure Mühen. Schöne Grüße Dan
06.07.2010, 09:42	Ehos	Auf diesen Beitrag antworten »
Die von dir benutzte Formel gibt lediglich den Kosinus des Winkels zwischen beiden Vektoren an, also $\begin{eqnarray} \cos(\phi)=\frac{a_1b_1+a_2b_2+...+a_nb_n}{\sqrt{a_1^2+a_2^2+...+a_n^2}\cdot \sqrt {b_1^2+b_2^2+...+b_n^2}} \end{eqnarray}$ Die Länge der Vektoren wird also gar nicht berücksichtigt. Hat man z.B. zwei parallele Vektoren beliebiger Länge, so ergäbe die obige Formel immer die "maximale Änlichkeit" $\begin{eqnarray} \cos(\phi)=1 \end{eqnarray}$ , egal wie groß der Längennterschied ist. Das wäre unlogisch. Die obige Formel hätte nur Sinne, wenn alle Vektoren, die man vergleichen will, stets die selbe Länge haben. Du findest im Netz noch andere Formeln, um die Ähnlichkeit zweier Vektoren quantitativ zu erfassen. Es hängt vom Problem ab, welche Formel die "richtige" ist.
06.07.2010, 11:21	online-dan	Auf diesen Beitrag antworten »
Ok, danke schon mal für Deine Hinweise. Hab zum Thema Vektor Ähnlichkeit mal genauer recherchiert und bin dann auf folgende Powerpoint-Präsentation gestoßen: Slides von VektorAehnlichkeit.ppt (dbs.mathematik.uni-marburg.de) In Folie #16 finde ich dann meine Formel wieder. Dachte eigentlich die berücksichtigt die Länge. Denn dort steht unter der Formel: "Zähler: wie gut xk und yk korrelieren Nenner: Teilung durch (Euklidische) Länge der Vektoren" Das ist doch die Formel, die ich anwende? Oder muss ich die Euklidische Distanz (von Folie #33) noch irgendwie in meine Formel einbauen? Oder meinst Du ein komplett anderes Ähnlichkeitsmaß (wie z.B. auf Folie #11) wäre in meinem Fall besser? Du siehst, ich bin jetzt noch etwas verwirrt. Hoffe Du kannst den Nebel noch mal beseitigen ;-) Danke + Gruß Dan
06.07.2010, 11:42	Ehos	Auf diesen Beitrag antworten »
Deine Formel liefert stets Werte im Intervall [0;1] (Vom Vorzeichen sehe ich mal ab.). Dabei bedeutet 0 = gar keine Übereinstimmug 1 = maximale Übereinstimmung Nimm als Beispiel mal das Vektorpaar a=(1\|0\|0) und b=(1\|0\|0). Beide Vektoren sind identisch. Deshalb ergibt deine Formel erwartungsgemäß den Wert 1 (=maximale Übereinstimmung). Nun nimm als Beispiel das Vektorpaar a'=(1\|0\|0) und b'=(x\|0\|0), wobei x ein beliebig großer Wert ist. Beide Vektoren sind parallel aber unterschiedlich lang. Wegen der Parallelität ergibt deine Formel wie oben den maximale Wert 1 - egal welchen Wert x man einsetzt. Das bedeutet, dass das Vektorpaare {a;b} und {a';b'} gleich gut überein stimmen - unabhängig von x. Das ergibt aus meiner Sicht keinen Sinn. Beschreibe mal dein Modell. Dann kann ich dir am Mittwoch eventuell eine "passende Formel" raussuchen. Das hängt sehr vom Sachverhalt ab, den man betrachtet.
06.07.2010, 13:38	online-dan	Auf diesen Beitrag antworten »
Ok, jetzt verstehe ich etwas mehr. Danke. Dann will ich mal den Hintergrund meines (Recommender-)Problems etwas näher erklären: Grundvoraussetzung ist für mich eine Bewertungsmatrix (mit den Benutzern als Zeilen und den Produkten, die bewertet wurden, als Spalten). Jeder dieser Matrixwerte spiegelt also eine Bewertung eines bestimmten Benutzers für ein bestimmtes Produkt wieder. Zusätzlich wurde jede dieser Bewertungen in einem bestimmten Kontext abgegeben. D.h. ich habe eine weitere Tabelle mit Kontext-Profilen. Jedes Kontext-Profil darin interpretiere ich als Vektor mit 9 Dimensionen (siehe Vektoren a und b aus meinem Beispiel oben). Ich möchte nun prüfen, wie ähnlich jedes einzelne Kontext-Profil (Vektor) aus dieser Tabelle zu einem festen aktuellen Kontext -Profil (Vektor) ist. Daher suche ich hier das passende Ähnlichkeitsmaß und bin eben auf die Cosinus-Ähnlichkeit gestoßen. Für die weitere Verarbeitung nehme ich dann nur noch die Bewertungen her, die unter einem ähnlichen Kontext abgegeben wurden, wie der aktuelle. Hoffe meine Erklärung ist einigermaßen verständlich und Du kannst damit was anfangen. Danke + Gruß Dan
07.07.2010, 13:34	Ehos	Auf diesen Beitrag antworten »
Ich gebe mal eine mögliche Definition für das "Maß der Übereinstimmung" zweier Vektoren an. Angenommen wir haben 2 Kunden, die pro Jahr Waren/Dienstleistungen für folgendes Beträge gekauft haben Kunde 1: (Urlaub 1.000€; Elektronik 900€; Kultur 800€) Kunde 2: (Urlaub 500€; Elektronik 2.000€; Kultur 50€)__________(1) Zu vergleichen sind also die Vektoren (1000\|900\|800) und (500\|2000\|50). Es ist wohl kaum möglich, diese Vektoren (=Kaufverhalten) mit einem einzigen Kriterium zu vergleichen. Du hattest als "Maß der Übereinstimmung" den Kosinus des Winkels zwischen beiden Vektoren vorgeschlagen, also $\begin{eqnarray} \cos(phi)=\frac{a_1b_1+a_2b_2+a_3b_3}{\sqrt{a_1^2+a_2^2+a_3^3}\sqrt{b_1^2+b_2^2+b_3^2}} \end{eqnarray}$ __________(2) Angenommen Kunde 1 würde überall genau das 10-fache wie Kunde 2 kaufen, also z.B. Kunde 1: (Urlaub 100€; Elektronik 90€; Kultur 80€) Kunde 2: (Urlaub 1.000€; Elektronik 900€; Kultur 500€) Dann hätten beide Kunden gemäß Formel (1) die maximale Übereinstimung, weil beide Vektoren parallel sind. Dies besagt aber nur, dass das Kaufverhalten beider Kunden "proportional" ist. Es wird aber nichts darüber ausgesagt, dass der Kunde 2 zehn Mal "kauffreudiger" ist als Kunde 2. Das ist ein Mangel der Formel (2). Um auch ein Maß für das "Abweichen der Kauffreudigkeit" zu bekommen, könnte man die beiden Vektoren (1) in ein Säulendiagramm zeichnen und den Betrag der Summe der Höhendifferenzen der Säulen als "Maß für den Unterschied der Kauffreudigkeit" interpretieren, also $\begin{eqnarray} \|(a_1-b_1)+(a_2-b_2)+(a_1-b_1)\|=\|(1000-500)+(900-2000)+(800-50)\| \end{eqnarray}$ Der Nachteil dieser Definition ist, dass das Ergebnis nicht zwischen 0 und 1 liegt, sondern beliebig hohe Wert annehmen kann. Ich halte es für prinzipiell für "zu grob", das Marktverhalten zweier Kunden durch die Angabe einer einzigen Zahl zu vergleichen. Man sollte mehrere Kriterien verwenden: "Gleichheit der Interessen", Gleichheit der Kauffreudigkeit" usw.
Anzeige

07.07.2010, 14:55	online-dan	Auf diesen Beitrag antworten »
Ok, danke für den Einwand zur Ähnlichkeitsbestimmung mit mehreren Kriterien. Werde das in einem Programm berücksichtigen. Die Formel und das Ergebnis meiner Kosinus-Ähnlichkeitsberechnung scheinen dann aber in Ordnung zu sein, oder? Ich bin da nämlich etwas stutzig geworden. Und zwar habe ich ungefähr 20 dieser Vektor-Pärchen betrachtet und jedes Mal kam ein Wert zw. 0,995 und 0,999 raus. Hier nochmal zwei Beispiele: a) Vektor 1 mit a1= 7, a2=7, a3=2010, a4=12, a5=21, a6=32, a7= 0, a8= 0, a9=2 Vektor 2 mit b1=23, b2=8, b3=2009, b4=18, b5=57, b6=31, b7=53, b8=-154, b9=1 Zaehler: 4040714.0 Nenner1: 2010.4255768369044 Nenner2: 2016.862414742265 Endergebnis (Cosinus-Aehnlichkeit): 0.9965379425651134 b) Vektor 1 mit a1= 7, a2=7, a3=2010, a4=12, a5=21, a6=32, a7= 0, a8= 0, a9=2 Vektor 2 mit b1=23, b2=12, b3=2009, b4= 9, b5=9, b6= 6, b7=43, b8=-178, b9=2 Zaehler: 4038828.0 Nenner1: 2010.4255768369044 Nenner2: 2017.545290693619 Endergebnis (Cosinus-Aehnlichkeit): 0.9957356698057415 Ist dieser knappe Wertebereich (0,995 bis 0,999) plausibel? Die Vektoren a und b aus den Beispielen sind ja doch z.T. etwas auseinander. Hätten da nicht niedrigere Werte für die Cosinus-Ähnlichkeiten rauskommen müssen? Danke + Gruß Dan
07.07.2010, 15:46	Ehos	Auf diesen Beitrag antworten »
Deine Vektoren sind deshalb "fast parallel", weil die 3.Komponenten a3=2010 und b3=2009 einerseits fast gleich und andererseits sehr groß sind (im Vergleich zu den anderen Komponenten) Die kleinen Komponenten machen davon nur ca. 1% oder weniger aus. Wenn du diese weglässt (also Null setzt), wird sich am Ergebnis 0,99... nicht viel ändern. Überlege dir, ob die kleinen Komponenten in deinem Modell so wenig berücksichtigt werden sollen. Eventuell muss man das ändern. Dies geschieht dadurch, dass man anstelle des üblichen Skalarproduktes $\begin{eqnarray} \vec a \cdot \vec b \end{eqnarray}$ das "gewichtete" Skalarprodukt $\begin{eqnarray} \vec a\cdot G \vec b \end{eqnarray}$ einführt, wobei G eine diagonale nxn-Matrix mit positiven Elementen in der Diagonalen sein muss. Im 3D-Fall würde so ein Skalarprodukt lauten $\begin{eqnarray} \begin{pmatrix} a_1 \\ a_2 \\ a_3 \end{pmatrix} \begin{pmatrix} G_{11} & 0 & 0 \\ 0 & G_{22} & 0 \\ 0 & 0 & G_{33} \end{pmatrix} \begin{pmatrix} b_1 \\ b_2 \\ a_3 \end{pmatrix} \end{eqnarray}$ Die positiven Matrixelemete G(11), G(22), G(33) in der Diagonalen geben an, wie stark die jeweilige Komponente im Vergleich zu anderen gewichtet werden soll. Diese Diagonalelemente musst du "in geeigneter Weise" selbst wählen. Das "Ähnlichkeitsmaß" würde dann lauten nicht $\begin{eqnarray} \frac{\vec a\cdot \vec b}{\sqrt{\vec a \cdot \vec a}\cdot \sqrt{\vec b \cdot \vec b}} \end{eqnarray}$ sondern $\begin{eqnarray} \frac{\vec a\cdot G\vec b}{\sqrt{\vec a \cdot G\vec a}\cdot \sqrt{\vec b \cdot G\vec b}} \end{eqnarray}$ Bis morgen.
08.07.2010, 16:01	online-dan	Auf diesen Beitrag antworten »
So, wollte mich noch mal kurz für Deine kompetenten Tipps bedanken. Der Vorschlag mit der Gewichtungsmatrix - vorher mit den mehreren Ähnlichkeitsmaßen - klingt gut. Ich werde das in meinem Programm berücksichtigen. Danke + Gruß Dan

Neue Frage »

Antworten »

Ähnlichkeitsberechnung für zwei Vektoren

Verwandte Themen