nicht angemeldet
Nähe von Elementen in hierarchischen Strukturen ermitteln
0 
Gunnar Bittersmann
0
Nähe von Elementen in hierarchischen Strukturen ermitteln
Guten Tag,
ich habe heute ein ausgefallenes Problem mit hierarchischen Strukturen:
Es gibt einen monohierarchischen Baum von Elementen. Jedes Element kommt dabei im Baum nur an einer Stelle vor, es gibt also zu jedem Element nur ein einziges übergeordnetes Element.
Die Elemente sollen Kategorien sein. Sie haben eine beliebige Verschachtelungs- und Verzweigungstiefe.
Es gibt verschiedene Möglichkeiten, dies in einer Datenbank abzubilden, z.B. in dem man jeder Kategorie eine parent_id mitgibt oder in Form sog. Nested Sets und andere Techniken. Darum geht es hier nicht.
Gesucht ist jetzt eine Nähe bzw. Verwandschaft zwischen den Kategorien auf Basis ihrer Position im Baum. Weltlich erklärt:
( ROOT )
/ \
/ \
+------------+ +-----------+
| Tiere | | Pflanzen |
+------------+ +-----------+
| | |
| | |
| +----------+ +---------+
| | Hund + | Tulpe |
| +----------+ +---------+
|
+-------+
| Katze |
+-------+
Als "Nachbar" von "Katze" ist es klar, dass "Hund" zu "Katze" eine engere Verwandtschaft hat als zu "Tulpe".
Möchte man nun die Verwandtschaft
"Hund" <-> "Katze"
und
"Hund" <-> "Tulpe"
miteinander vergleichen, ist es naheliegend, einfach den Baum als Graphen zu betrachten und die kürzeste Distanz (kürzester Weg) berechnen:
"Hund" <-> "Katze" = Hund->Tiere->Katze = 1
"Hund" <-> "Tulpe" = Hund->Tiere->Root->Pflanzen->Tulpe = 3
Hat jetzt Katze weitere Unterkategorien "Löwe" und "Hauskatze", ist die für den Menschen logische Verwandtschaft zwischen "Hund" und "Hauskatze" durch dieses System nicht mehr ganz gegeben.
Außerdem müsste, wenn man nun Inhalte der Kategorien miteinander vergleichen will, einen neu einzutragenden Inhalt mit allen schon bereits bestehenden vergleichen.
Lieber wäre mir eine ein- oder vielleicht zweidimensionale, numerische Repräsentation der Position im Baum. Diese numerische Repräsentation nennen wir "m". Wir speichern zu "Hund" nun "2", zu "Katze" 2.5 und zu Tulpe 5.
Platt gesagt: 2-2.5 >> 2-5,
ergo: Ein Hund ist eher eine Katze als eine Tulpe ;-))
Natürlich möchte ich diese numerische Repräsentation m nicht manuell redaktionell zu den Kategorien pflegen, sondern diese sollte berechenbar sein.
Ist klar, worauf ich hinaus will?
Hat jemand eine Idee oder einen Link?
Danke,
Thomas
-
@@Thomas K.:
Möchte man nun die Verwandtschaft […] miteinander vergleichen, ist es naheliegend, einfach den Baum als Graphen zu betrachten und die kürzeste Distanz (kürzester Weg) berechnen:
"Hund" <-> "Katze" = Hund->Tiere->Katze = 1
Naheliegend? Aber wohl nicht zielführend.
"Hund" <-> "Root" = Hund->Tiere->Root = 1
Root und Katze wären gleich eng mit Hund verwandt.
Wäre nicht die Anzahl der Schritte, die du im Baum HINAUFgehst, ein geeignetes Maß der Verwandtschaft?
Live long and prosper,
Gunnar--
„Das Internet ist ein großer Misthaufen, in dem man allerdings auch kleine Schätze und Perlen finden kann.“ (Joseph Weizenbaum)-
Hallo Gunnar,
Wäre nicht die Anzahl der Schritte, die du im Baum HINAUFgehst, ein geeignetes Maß der Verwandtschaft?
Ja, so wäre das in letzter Konsequenz auch gemeint, ich habe es nur nicht weiter ausgeführt.
Ich möchte aber ja im Vorfeld eine numerische Repräsentation finden, ohne bei einer Vergleichsiteration ein neues Element mit jedem bereits vorhandenen vergleichen zu müssen. Hier einfach die Verschachtelungstiefe als im Vorfeld berechneten Vergleichsfeld zu benutzen, tut es natürlich auch nicht...
Danke!
Thomas -
@@Gunnar Bittersmann:
@@Thomas K.:
Möchte man nun die Verwandtschaft […] miteinander vergleichen, ist es naheliegend, einfach den Baum als Graphen zu betrachten und die kürzeste Distanz (kürzester Weg) berechnen:
"Hund" <-> "Katze" = Hund->Tiere->Katze = 1
Naheliegend? Aber wohl nicht zielführend.
"Hund" <-> "Root" = Hund->Tiere->Root = 1
Root und Katze wären gleich eng mit Hund verwandt.
Wäre nicht die Anzahl der Schritte, die du im Baum HINAUFgehst, ein geeignetes Maß der Verwandtschaft?
Oops, zu früh abgeschickt.
Die zu vergleichenden Knoten können ja unterschiedlich weit vom gemeinsamen Vorfahrenknoten entfernt sein. Mich dünkt, man müsste das Minimum beider Entfernungen als Verwandtschaftsgrad nehmen.
Außerdem sollten vielleicht die Hierarchieebenen unterschiedlich gewichtet werden, sonst wären Hund und Tulpe gleich eng verwandt wie Schäferhund und Hauskatze.
Lebewesen
/\ 1/ \1
/ \ Tiere Pflanzen
/\ \ 0.1/ \0.1 \0.1
/ \ \ Katze Hund Tulpe
/\ /\ 0.01/ \0.01 0.01/ \0.01
/ \ / \ Hauskatze Löwe Dackel SchäferhundLive long and prosper,
Gunnar--
„Das Internet ist ein großer Misthaufen, in dem man allerdings auch kleine Schätze und Perlen finden kann.“ (Joseph Weizenbaum)-
Hallo Gunnar,
Außerdem sollten vielleicht die Hierarchieebenen unterschiedlich gewichtet werden, sonst wären Hund und Tulpe gleich eng verwandt wie Schäferhund und Hauskatze.
Wie gesagt, es geht mir nicht darum, zu einem Zeitpunkt zwei Verwandtschaften mit einander zu vergleichen, sondern eine Art Vektor/Matrix/whatever für jede Kategorie im Vorfeld zu berechnen, die dann verglichen werden kann. Das ganze also auf eine Art Abstraktion bringen.
Zu jeder Kategorie einen Punkt bestehend aus X und Y - Koordinate speichern und dann:
function findeÄhnlicheElemente($neuesElement)
foreach ($alleElemente as $element) {
$verwandtschaft = DISTANCE $neuesElement.X, $neuesElement.Y, $element.X, $element.Y
}
}Hier müsste ich nur eine mathematische berechnung im Koordinatensystem vornehmen, statt das ganze auf Grundlage eines komplexen Baumes für jeden Artikelvergleich vornehmen zu müssen.
So etwas in der Art möchte ich.
Ideen?
Danke,
Thomas
-
-
-
Hallo Thomas!
Gesucht ist jetzt eine Nähe bzw. Verwandschaft zwischen den Kategorien auf Basis ihrer Position im Baum.
Lieber wäre mir eine ein- oder vielleicht zweidimensionale, numerische Repräsentation der Position im Baum.
Natürlich möchte ich diese numerische Repräsentation m nicht manuell redaktionell zu den Kategorien pflegen, sondern diese sollte berechenbar sein.
Ist klar, worauf ich hinaus will?
Hat jemand eine Idee oder einen Link?
Ich glaube, da hst du dir ein sehr komplexes Thema ausgesucht, welches nicht so einfach zu lösen ist.
Für mich klingt dein Anliegen nach:
Gruß Gunther
-
Hallo Gunther,
Ich glaube, da hst du dir ein sehr komplexes Thema ausgesucht, welches nicht so einfach zu lösen ist.
das ist auch nicht so weiter tragisch, denn es gibt keinen zwingenden Umsetzungshintergrund. Für mich ist das einfach nur ein Thema, für das ich mich begeistern konnte und jetzt ein paar Denkanstöße brauche. Also tatsächlich reine Experimentierfreude statt dringende Notwendigkeit, etwas komplexes umsetzen zu müssen.
Für mich klingt dein Anliegen nach:
Recht herzlichen Dank für die Links!
Thomas
-