Elemente einer Tabelle anhand einer nicht exakten Tabelle zuordnen (Allgemeines zu Perl)

[thread]13869[/thread]

Elemente einer Tabelle anhand einer nicht exakten Tabelle zuordnen

Leser: 22

Articles: hide open all | hide show old branches

+9 replies
Gast TheDude

2009-08-15 23:50

Hi erstmal, etwas blöder Threadtitel ich weiß. Ich weiß nur grad nicht wie ich es besser beschreiben soll.

Also ich hab eine Tabelle die sieht ungefähr so aus..

Attribut 1 | Attribut 2 | Attribut 3
1
2
3
4
5
.
.

Denkt euch in die Zellen irgendwelche Werte ist egal welche. Die können mal sehr nah bei einander liegen mal sehr weit auseinander.

Jetzt moechte ich einem Objekt von dem ich die Attribute 1 bis 3 kennen einen Typ zuordnen also 1, 2, 3 oder 4 usw.

Das Problem ist nur die Attribute stimmen nicht mit denen in der Tabelle überein. In der Tabelle sind nur Richtwerte und die Attribute meines Objekts koennen mehr oder weniger stark abweichen das heißt ich möchte dem Objekt den Typ zuordnen dem es am ähnlichsten ist. Alle Attribute sind aber gleichberechtigt. Also nicht erst schauen zwischen welchen Werten liegt das Objekt bei Attribut 1 und dann anhand des zweiten bzw. dritten entscheiden welchen Typ ich zuordne. Sondern die Uebereinstimmung mit allen Elemente bewerten.

Das ganze muss leider auch noch relativ effizient sein aber das stell ich erstmal hinten an.

Vielleicht habt ihr ja irgendwelche Vorschläge wie ich das lösen könnte.
- +8 replies
- Gast wer
  
  2009-08-16 04:27
  Was ich jetzt verstanden habe:
  1. Da ist eine Datenbank.
  2. Eine Tabelle enthält beliebige Werte mit beliebigen Attributen
  3. Die Werte sind doch nicht beliebig, da es eine Spalte/mehrere Spalten gibt, die einen Wertebereich definiert/definieren.
  4. Es soll "Etwas" diesem Wertebereich zugeordnet werden, und zwar dem der "am besten" Passt.
  5. Bei Unklarheiten soll eine Spalte/mehrere Spalten, nicht näher spezifizierter Werte, zur Bewertung hinzugezogen werden.
  
  Das ist reichlich unscharf.
  Du versuchst hier eine Brücke mit den Worten "etwas, das über Wasser reicht." zu beschreiben.
  
  Ein paar Fragen:
  
  über was für Werte reden wir hier? Zahlenwerte, Texte, Objekte?
  kannst du etwas konkreter werden?
  Sind die Wertebereiche überschneidend?
  was währe der beste Treffer?
  Wenn der Wert möglichst mittig in den kleinsten Wertebereich fällt?
  Wenn der Wert einen Wertebereich möglichst mittig fällt?
  Wenn der Wert in den Kleinsten Wertebereich fällt?
  wie liegen die Daten genau vor (Datei/SQL-DB/sonstwie) und wie groß ist die Datenmenge (Kb,Mb,Gb,Tb)
  
  Grundsätzlich kann man eine Menge mit "sort" anstellen, aber dafür müssen die Daten entsprechend vorliegen.
  - +7 replies
  - Gast TheDude
    
    2009-08-16 05:26
    
    Ok ich hab mich wohl nicht gut ausdrückt.
    
    Die Werte in der Tabelle hab ich nur aus bequemlichkeit weggelassen.
    
    Tatsächlich würde die Tabelle z.B. so aussehen:
    
    Wert 1 Wert 2 Wert 3
    
    Typ 1 109.339632149156 71.2834467120181 30.1753590325019
    
    Typ 2 19.4394053917863 56.1546989166037 99.2312925170068
    
    Typ 3 97.2249937011842 96.7168052406148 99.9543965734442
    
    Typ 4 35.6661627614009 112.246157722348 33.411186696901
    
    Typ 5 141.426303854875 50.0745779793399 53.4378936759889
    
    Typ 6 71.9997480473671 17.6830435878055 73.3968253968254
    
    Typ 7 80.3456790123457 80.1315192743764 24.8614260519022
    
    Das sind halt die Werte anhand derer ich denen Objekten einen Typ zuordnen moechte.
    Von den Objekten kenn ich die 3 Werte aber eben nicht den Typ.
    
    Hätte ich jetzt ein Objekt 1 mit den Werten 25/60/80 würde das am ehesten dem Typ 2 entsprechen und dementsprechend auch den Typ 2 zugeordnet kriegen.. Entschieden hab ich das weil die Werte des Objekts 1 im Vergleich zu den anderen Typen die geringste Differenz zu den Richtwerten des Typs 2 aufweisen: +~6/-~4/+~19.
    Es geht eben nicht um exakte Zuordnung sondern darum anhand der groeßten Uebereinstimmung bzw. geringsten Abweichung die Entscheidung zu treffen.
    
    40/115/29 waer Typ 4.. 120/65/28 waer Typ 1.. 80/25/70 waer Typ 7.. 100/100/100 waer Typ 3 usw.
    
    Ich hoffe jetzt ist das etwas verstaendlicher.
    - +6 replies
    - Gast wer
      
      2009-08-16 13:13
      
      Ich glaube ich verstehe jetzt.
      
      Wir haben Drei Werte Die zusammen einen "Typ" definieren.
      Mehrere Typen mit den Wertetrippeln wurden definiert.
      Nun sollen Objekte, welche die drei Werte enthalten, den Typen zugeortnet werden. Da die Werte in den Objekten nicht exakt übereinstimmen, sogar weit voneinander abweichen können, soll das Objekt dem wert zugeordnet werden, dass am "besten" passt.
      
      Die Definition was dieses "am besten Passt" umfasst ist der Schlüssel zu deinem Problem.
      
      Da es sich um Zahlenwerte handelt kannst du einen Durchschnitt bilden und diesen als Entscheidungskriterium heran ziehen.
      
      Ich will versuchen es an einem Beispiel zu Erklären was ich meine:
      
      Code: (dl )
      
      1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
      
      A B C Typ1 109 71 30 Typ2 19 56 99 Obj1 25 60 80 schlüssel-obj1-typ1 = abs(25 - 109) + abs(60 - 71) + abs(30 - 80) schlüssel-obj1-typ1 = 145 schlüssel-obj1-typ2 = abs(25 - 19) + abs(60 - 56) + abs(30 - 99) schlüssel-obj1-typ2 = 79 allgemein: schlüssel = abs(objX->A - typY->A) + abs(objX->B - typY->B) + abs(objX->C - typY->C)
      
      In dem Beispiel oben werden alle Werte gleich bedeutend behandelt, durch multiplizieren der Werte mit festen Faktoren kannst du die Bewertung verschieben.
      Formel:
      
      Code: (dl )
      
      schlüssel = abs(objX->A - typY->A)*prioA + abs(objX->B - typY->B)*prioB + abs(objX->C - typY->C)*prioC
      
      Beispiel:
      A soll höher bewertet sein als B soll höher bewertet sein als C
      
      Code: (dl )
      
      1 2 3
      
      prioA = 0.01 prioB = 0.1 prioC = 1
      
      Die genaue Verteilung musst du selbst bestimmen, das konkret von den Werten und deren Wertebereichen abhängt.
      
      Durch umstellen der Formel kannst du alle Werte im Vornherein berechnen und musst dann nur noch objX und typY subtrahieren um den Vergleichswert zu erhalten. Das geht sehr schnell.
      - +5 replies
      - murphy
        
        2009-08-16 15:12
        
        User since
        2004-07-19
        1776 Artikel
        HausmeisterIn
        
        Ich kenne zwar den genauen Hintergrund dieser Problemstellung nicht, aber im Allgemeinen ist es günstiger, ein Abstandsmaß zu verwenden, bei dem die Differenzen der Einzelkriterien quadratisch gewichtet werden, nicht linear. Ich würde also die Aufrufe von abs durch Anwendung von **2 ersetzen.
        
        Der Vorteil liegt darin, dass bei dieser Art von Metrik die Dreiecksungleichung nicht mehr zur Gleichung entartet ist. Anschaulicher ausgedrückt: Bei der Methode mit Quadraten ist nicht jeder Umweg zwischen zwei Punkten im Kriterienraum genauso lang wie der direkte Weg, bzw. kleine Abweichungen in mehreren Kriterien wiegen nicht genauso schwer wie eine große Abweichung in einem Kriterium.
        When C++ is your hammer, every problem looks like your thumb.
        
        +4 replies
        
        Gast wer
        
        2009-08-16 15:52
        
        Sicher, nur wird die Berechnung um den Faktor 10 langsamer, da man viel weniger am Anfang Vorberechnen kann.
        Weiterhin macht die 3dimensionale Darstellung nur dann auffällige Unterschiede wenn man einen großen Ausreißer in dem Wertetrippel hat.
        
        Aber Grundsätzlich stimme ich dir zu, dass eine Berechnung über den räumlichen Abstand weniger "fehleranfällig" ist.
        
        Nur ob sie gebraucht wird ist eine Frage, dich ich nicht beantworten kann.
        
        +3 replies
        
        Gast TheDude
        
        2009-08-16 17:46
        
        Ok danke an euch beide.
        
        Code (perl): (dl )
        
        1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28
        
        sub PerformCheck { my @TableOfValues = ([109.339632149156, 71.2834467120181, 30.1753590325019], [19.4394053917863, 56.1546989166037, 99.2312925170068], [97.2249937011842, 96.7168052406148, 99.9543965734442], [35.6661627614009, 112.246157722348, 33.4111866969010], [141.426303854875, 50.0745779793399, 53.4378936759889], [71.9997480473671, 17.6830435878055, 73.3968253968254], [80.3456790123457, 80.1315192743764, 24.8614260519022]); my @ObjValues = @_; my $CurrValue = 195076; my $objType = 0; for my $i (0..$#TableOfValues) { my $diff = (); for my $i2 (0..2) { $diff += ($ObjValues[$i2] - ${$TableOfValues[$i]}[$i2]) ** 2; } if ($diff < $CurrValue) { $CurrValue = $diff; $objType = $i + 1; } } return $objType; }
        
        Jetzt kann ich einfach die drei Werte des Objekts uebergeben und krieg den Typ zurueck.
        wer hatte den richtigen Ansatz aber das quadrieren war auch wichtig. Ich hab mal nen Testlauf gemacht und es wurden alle Objekte erkannt. Danke also nochmal.
        
        +2 replies
        
        Gast wer
        
        2009-08-16 19:18
        
        Ein paar kleine Vorschläge zur Verbesserung:
        
        Code (perl): (dl )
        
        1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30
        
        sub PerformCheck { my @TableOfValues = ([109.339632149156, 71.2834467120181, 30.1753590325019], [19.4394053917863, 56.1546989166037, 99.2312925170068], [97.2249937011842, 96.7168052406148, 99.9543965734442], [35.6661627614009, 112.246157722348, 33.4111866969010], [141.426303854875, 50.0745779793399, 53.4378936759889], [71.9997480473671, 17.6830435878055, 73.3968253968254], [80.3456790123457, 80.1315192743764, 24.8614260519022]); my @ObjValues = @_; my $CurrValue = undef; my $objType = 0; for my $i (0..$#TableOfValues) { my $diff = (); for my $i2 (0..2) { $diff += ($ObjValues[$i2] - $TableOfValues[$i][$i2]) ** 2; } # Es einen Wert geben, der den voreingestellten übersteigt, aber der Beste ist. $CurrValue = $diff if(!defined($CurrValue)); if ($diff < $CurrValue) { $CurrValue = $diff; $objType = $i + 1; } } return $objType; }
        
        Gast TheDude
        
        2009-08-16 21:30
        
        Hm wenn ich das richtig sehe wuerde aber jetzt das Objekt doch nicht erkannt wenn es Typ 1 waere.
        Im ersten Durchgang waere $CurrValue ja undefiniert und wuerde den Wert $diff zugewiesen kriegen. Dadurch waere aber ja $diff nicht mehr kleiner als $CurrValue sondern gleich was die Folge haette das $objType 0 bleibt was bei mir ja fuer unerkannt steht. Der Typ 1 wuerde also nie erkannt. Klappen wuerde das wohl wenn man + 1 rechnen wuerde.
        
        Code (perl): (dl )
        
        $CurrValue = $diff + 1 if(!defined($CurrValue));
        
        Aber dann haette ich zusaetzliche Abfrage jeden Durchlauf.. Gut das kann man wohl vernachlaessigen aber wo siehst du da denn genau den Vorteil?
        
        Aber ich hatte mir den voreingestellten Wert schon ueberlegt. Es handelt sich bei den Werten naemlich jeweils um das arithmetische Mittel aus einigen Bytes.. Und da ein Byte ja maximal FF = 255 ist kann die hoechste Abweichung ja nur 255^2*3 = 195075 sein. Wenn ich dann noch 1 addiere wird in jedem Fall ein Typ gefunden. Das kann natuerlich auch ein Nachteil sein wenn ich mal Objekte haben sollte deren Typ nicht definiert ist. Da haette ich dann natuerlich lieber 0 zurueck. Das Problem hab ich gluecklicherweise momentan nicht aber wenn dann wuerde ich es mit Grenzwerten fuer die Abweichung versuchen..

View all threads created 2009-08-15 23:50.