Servus!

Gibts zufällig schon ein Modul (wer jetzt schon denkt, ich will wieder nur anderer Leute Arbeit nehmen und mich selbst damit rühmen möchte unverzüglich seinen Browser schließen und sich gefälligst alle OT-Kommentare kneifen) zur Darstellung von merkmalsräumen?

Weil folgendes: Ich habe mehrere verschiedene Vektoren aus Merkmalen.
Die kann ich vergleichen, indem ich die Winkel berechne.
Hätte ich immer nur 3 Merkmale könnte ich einen 3dimensionalen Graphen nehmen, um die Sache zu visualisieren - was mein Ziel ist.
Aber: ich werde einige (hundert) Merkmale mehr.

Jetzt kann man Vektoren auf 0 normalisieren und trotzdem die Divergenz behalten. Das gibt dann so eine zweidimensionale Matrix mit Punkten drin.
Und das will ich darstellen.

Also, gibts sowas schon? Hat jemand schon was?
Das nur so als Frage, wenns nix gibt, mache ich es selbst.

Grüße, pktm

PS: für interessierte: gerne gibts da noch mehr Infos zu - einfach fragen :)

Irgendwie verstehe ich das nicht: Du redest von Vektoren aus Merkmalen und von Divergenzen. Aber was ist ein Merkmal bzw. wie wird es in Deinem mathematischen Modell repräsentiert? Macht der Begriff der Divergenz nicht nur im Bezug auf Vektorfelder, also vektorwertige Funktionen, Sinn? Und bezüglich welcher Variablen willst Du irgendwelche Grenzwerte bilden? Zumindest hört sich Deine Beschreibung des gewünschten Resultates für mich so an, als wäre das irgendein Grenzwert bzw. vielleicht einfach eine Matrix, die verschiedene partielle Ableitungen enthält.

Vielleicht bin ich einfach nur zu doof und unwissend und Du brauchst eher Hilfe von jemanden, der aus Deinem Fachgebiet kommt, aber ich fände einen Link zu einer Erklärung der zugrundeliegenden Theorie nützlich...

murphy+2008-11-20 22:32:51--

Vielleicht bin ich einfach nur zu doof und unwissend und Du brauchst eher Hilfe von jemanden, der aus Deinem Fachgebiet kommt, aber ich fände einen Link zu einer Erklärung der zugrundeliegenden Theorie nützlich...

Würde ich davon ausgehen, hätte ich hier nicht gefragt ;)

Ich verwende primär zwei Paper für meine Arbeit, das eine ist Salton/Wong 1975 und das andere Vidal 2006.

Und was ich tun möchte ist, ein "kleines" Textkategorisierungssystem möglichst weitgehend mit Automaten zu basteln. Textkategorisierung (TK) funktioniert dabei so, dass man für Dokumente Merkmalsvektoren erhebt (immer die gleichen Merkmale, z.B. alle Wortstämme, aber keine Stopwörter). Das kann man auch mit einem Automaten machen.

Mein Problem ist, dass ich das gerne mit Bildern illustrieren möchte, und zwar mit welchen, die tatsächlich auf Daten beruhen. Das wird zwar nicht wirklich repräsentativ (aus Platzgründen werde ich wohl nur so 100 Dokumente nehmen), aber dafür schick anzusehen.

Nun zurück zu meiner Problemstellung.
Divergenzen - richtig - bezieht sich auf Vektorfelder. 100 Dokumente, die jeweils durch einen Vektor repräsentiert werden, ergeben (so glaube ich doch) ein Vektorfeld. Und sowas kann man herrlich in Automaten prügeln.

Also habe ich da eine ganze Menge von Zahlen, und würde die gerne grafisch darstellen.

Hmm, ich befinde mich hier weit außerhalb meines normalen Arbeitsgebietes, also lass mich mal nachfragen, ob ich das richtig verstehe: Du hast Vektoren, die jeweils ein Dokument charakterisieren. Diese Vektoren sind Elemente eines hochdimensionalen rellen Vektorraumes, wobei jede Dimension des Raumes einem Indexbegriff, in deinem Fall einem möglichen Wortstamm, entspricht. Die Komponenten der Vektoren geben irgendein Gewichtungsmaß des entsprechenden Indexbegriffes an, also zum Beispiel die Häufigkeit seines Auftretens in dem Dokument.

Definiert man jetzt noch eine Metrik auf dem Vektorraum, wobei es wahrscheinlich schon die normale euklidische Metrik tut, dann kann man durch Abstände oder Winkel zwischen den Vektoren die Ähnlichkeit der Dokumente beurteilen. Wählt man die Winkel als Ähnlichkeitsmaß, kann man die Vektoren auch getrost normieren, ohne Informationen zu verlieren.

Stimmt das soweit?

Wenn das soweit korrekt ist, verstehe ich aber immer noch nicht, wie man hier eine Divergenz bilden will. Man hat zwar eine große Menge Vektoren, aber keine "Positionen", denen sie zugeordnet werden. Ich versuche das mal mit einem Beispiel aus der klassischen Physik zu vergleichen: Wenn Wasser aus einem Spülbecken in den Abfluss fließt, kann man jedem Wassermolekül eine aktuelle Position im Spülbecken und eine aktuelle Geschwindigkeit relativ zum Abfluss zuordnen. Beides sind dreidimensionale, reelle Vektoren. Bildet man die Divergenz des Geschwindigkeitsfeldes, um zu bestimmen, wieviel Wasser von einer bestimmten Stelle aus im Abfluss verschwindet, so muss man dazu sowohl die Position im Spülbecken kennen, an der man die Divergenz wissen will, als auch die Geschwindigkeit der Wassermoleküle um die Position herum. In Deinem Beispiel kennt man aber nur das Analogon der Geschwindigkeiten und nicht das der Positionen der einzelnen Dokumente.

Wo ist also mein Denkfehler?

Ich kann Dir im Moment zum Bearbeiten grosser Datenmengen mit Methoden der Linearen Algebra und Analysis nur empfehlen, mal einen Blick auf die Modulkollektionen PDL und Math::GSL zu werfen.

Ich vermute, dass eine Statistiksoftware sinnvoller für so eine Problemstellung ist: http://www.r-project.org/

murphy+2008-11-21 16:32:46--

Wo ist also mein Denkfehler?

Das ist nicht zwangsläufig deiner :-s

Wenn man aus ein paar Dokumenten einen Merkmalsraum erstellt hat, dann will man ja auch irgendwas damit machen. So kann man z.B. Suchanfragen stellen: "gib ein Kochrezept für Pfannkuchen".
Dann hat man eine Beschreibung eines Vektors, und zwischen diesem Vektor und dem Merkmalsraum kann man die Divergenz bilden (bitte korrigieren, wenn das nicht exakt stimmt, ich bin mit dem Thema noch nicht so warm).
Wenn meine Überlegung stimmt, dann müsste eine niedrige Divergenz für einen Treffer im Suchraum stehen.

So als brachialst auf das notwendigste runtergenüppelt könnte man es sich so vorstellen (ja, das ist nicht repräsentativ und weit weg von der Realität):
Wir haben zwei Dokumente D1 "Rezept für Pfannkuchen" und D2 "Rezept für Kekse" und die Anfrage "Rezept Pfannkuchen".
Mein Merkmalsvektor besteht aus drei Feldern: <Rezept, Pfannkuchen, Keks>, D1 = <1,1,0>, D2 = <1,0,1>. Meine Anfrage (Q) müsste dann eigentlich sowas wie Q = <1,1,0> sein.

Ich habe mir die Statistiksoftware mal (sehr) kurz angesehen, und stehe da wie ein Ochs vorm Berg. Ich würde mal pauschal sagen, das ist nichts für mich - hauptsächlich, weil ich keinen Grund sehe, mich da einzuarbeiten.

Math::GSL sieht dagegen aber sehr interessant aus.

Grüße, pktm

Ronnie+2008-11-21 19:13:33--

Ich vermute, dass eine Statistiksoftware sinnvoller für so eine Problemstellung ist: http://www.r-project.org/

nee Ronnie, das sind diskrete (~ Integer) und algebraische Verfahren wie sie bei Spamfiltern, Datamining und Suchmaschinen Anwendung finden.

pktm+2008-11-21 22:18:39--

[...] Dann hat man eine Beschreibung eines Vektors, und zwischen diesem Vektor und dem Merkmalsraum kann man die Divergenz bilden (bitte korrigieren, wenn das nicht exakt stimmt, ich bin mit dem Thema noch nicht so warm). [...]

Ich glaube ja, man berechnet einfach den Abstand oder Winkel zwischen der Suchanfrage, die man so wie die Dokumente als Merkmalsvektor kodiert, und allen Dokumenten. Das Dokument mit dem kleinsten Abstand oder Winkel zur Anfrage ist dann der beste Treffer.

Ich glaube ferner, Du suchst vielleicht gar keinen Weg da irgendwas zu differenzieren, sondern eher eine clevere Projektion Deines hochdimensionalen Merkmalsraumes auf zwei oder drei Dimensionen derart, dass die Abstände oder Winkel zwischen den Dokumenten halbwegs orginalgetreu erhalten bleiben und somit eine grafische Darstellung zumindest die korrekte Identifikation von Clustern erlaubt.

Um das zu bewerkstelligen, würde ich vielleicht versuchen, wenige Dokumente im Zentrum von Clustern als Basisvektoren auszuwählen und dann in den von diesen Vektoren erzeugten Untervektorraum zu projizieren. Dieses Verfahren könnte man auch mehrfach iterieren.

Um von den Polarkoordinaten normierter Vektoren auf planare kartesische zu kommen, könnte man zum Beispiel eine stereographische Projektion verwenden. Die ist winkeltreu und gibt in der Regel einen guten Eindruck von der Kugeloberfläche.

Für bessere Ideen ist es im Moment zu spät, wenn mir noch etwas schlaues einfällt, sage ich Bescheid ;-)

Jetzt mal einfach ins Blaue gedacht.
Positioniere alle Vektoren (Dimension n) am selben Ursprungsort (du bekommst einen Strahl). Ziehe mit dem Suchvektor (Strahl) eine Ebene auf, die Rechtwinklig zum Vektor steht und siehe nach wo sich die Ebenen und die anderen Vektoren schneiden. Nun kannst du den Raum so drehen, dass die Ebene genau auf zwei Dimensionen zum Liegen kommt und somit einfach darstellbar ist. veränderst du die Länge des Suchvektors rücken die Schnittpunkte auf der Ebene näher zusammen oder weiter aus einander.

Das ist eine stereographische Projektion (ähnlich murphy's Ansatz), jedoch reduziert auf dein Spezielles Problem.
Der Suchvektor ist das Zentrum der Projektion, alle ähnlichen Vektoren stehen Näher.

Ich habe nochmal über die Sache mit der Divergenz nachgedacht: Wenn man hier etwas differenzieren möchte, dann am besten die Funktion, die das am besten passende Dokument zu einem Suchvektor findet.

Die diskretisierte Divergenz dieser Funktion berechnet sich in etwa so: Man legt zunächst einen Suchvektor fest und berechnet dann nicht nur für den Suchvektor selbst sondern auch für Vektoren, die in jeweils einer der Komponenten vom Suchvektor aus um einen kleinen Betrag verändert wurden, das am besten passende Dokument. Anschliessend bestimmt man den Abstand zwischen den Dokumenten, die zu den modifizierten Suchvektoren passen, und dem Dokument, das zum ursprünglichen Suchvektor passt, und normiert diese Abstände über die jeweilige Veränderung am Suchvektor. Die Summe aus diesen normierten Abständen ist nun eine Näherung für die Divergenz der Suchfunktion im ursprünglichen Suchvektor.

Damit bekommt man ein Maß dafür, wie spezifisch die Treffer der Suchfunktion sind. Je größer die Divergenz, desto breiter streuen die Treffer für leicht unterschiedliche Suchanfragen über den Merkmalsraum.

Ich könnte mir vorstellen, dass das eine für die Analyse interessante Größe ist, weiß aber nicht, ob sie sich besonders gut zur Visualisierung eignet – die Divergenz der Suchfunktion, welche eine Funktion von einem n-dimensionalen Raum in denselben Raum ist, ist immer noch eine Funktion von einem n-dimensionalen Raum in einen eindimensionalen Raum.

edit: Allerdings kann es sein, dass diese Divergenzfunktion einem hilft, Cluster zu finden, was wiederum nützlich sein könnte, wenn man eine Projektions(hyper)ebene für die Visualisierung auswählen möchte.