Prozentuale Ähnlichkeit (Mustererkennung)

[Go2EITS]

So ich habe wieder ein Problem, mit dem ich mich schon länger beschäftige.
Gegeben ist ein Muster: (erste Zeile die Feldnamen)

Delphi-Quellcode:

Sta Proz GL1   GL2  Gl3  GL4  
2    3,5 0,23  1,2  0,6    0,7
0   -0,5 0,24  1,3  0,7    0,73
1    1,2 0,25  1,4  0,8    0,85

In der Datei befinden sich weitere, sagen wir mal 1000 Zeilen mit solchen unterschiedlichen Zahlen.
Ich möchte wissen, a) wieviele gleiche Muster vorkommen - das ist kein Problem aber
b) welche sind von 100% bis 90% ähnlich.
Das ist aber insofern problematisch, da Sta 0,1,2 annehmen kann.
Wenn sich dieser Wert verändert, habe ich ein Problem mit der Ähnlichkeit:

Beispiel:
2 3,5 0,23 1,2 0,6 0,7 (Muster)
0 3,5 0,24 1,2 0,6 0,7 (Gefundenes oder besser zu prüfendes Muster)
Wenn sich ein Wert von 0,23 auf 0,24 im Suchmuster in der ersten Zeile befindet, wird das das Muster als ähnlich erkannt.
Ist jedoch unter Sta die 2 verändert auf 0, so habe ich eine große prozentuale Abweichung.

Daher meine Frage, bevor ich überhaupt anfange das Programm zu schreiben:
Wie löse ich das Problem? Muss ich eine Gewichtsmatrix über die Zahlen legen?
Wie kann ich feststellen, dass die obigen 3 Datenzeilen mit drei anderen Datenzeilen in der Datei ähnlich sind.
:gruebel:
Hat jemand einen Link, eine Idee, oder einen Ansatz?

[HERMES]

Es wäre wohl Sinnvoll hier eine Metrik zu definieren, mit welcher du ein Maß für die Unterschiede der einzelnen Vektoren hast ( ich nenne deine Zeilen jetzt einfach mal so).

Zum Beispiel könntest du die Euklid Norm/ euklidischen Abstand nehmen. Eventuell könntest du auch noch zusätzliche gewichte einführen.

[KPBecker]

Solange Du nicht den Begriff "Ähnlich" für die Parameter einzeln quantifizieren kannst, ist die Sache wohl kaum lösbar.
Klaus-Peter

[stahli]

Vergleichst Du die Datensätze durch einen Text-Vergleich?
Das wäre sicher nicht sinnvoll.

Da Du hier mit Zahlen arbeitest, solltest Du die Differenzen für jedes Feld zwischen zwei Datensätzen ermitteln.
Die Differenz kannst Du dann hernehmen, um die Ähnlichkeit zu ermitteln. Wir können ja hier nicht einschätzen, ob 0,2 Differenz noch einen ähnliche Werte beinhalten.
Dann ermittelst Du den Durchschnitt über alle Feld-Ähnlichkeiten und erhälst ein brauchbares Ergebnis.

Stahli

[Go2EITS]

Danke für Eure Antworten, ich glaube ich erstmal einen Ansatz schreiben und dann hier als Source zur Diskussion reinstellen,
dann versteht man auch besser, wass ich meine.
@Stahli
Nein, kein Stringvergleich. Es sind die Floats wie oben.
So weit, denke ich, ist mein Ansatz auch. Ich habe da noch irgendwie einen Denkfehler:
Die Differenz von 1 auf 2 ist 100%, wobei bei den anderen Werten "bessere" Werte kommen.
Daher auch die Überlegung mit einer Gewichtung. Aber ich glaube, ich bin noch auf dem Holzweg.
Genau genommen kann es sein, das die Bedingungen unter Sta zu 100% zutreffend sein müssen, weil sonst zu viele Ähnlichkeiten in den 1000 Datensätzen vorhanden sind.

Vielen Dank für Eure Mühe vorerst und gute Nacht!

[stahli]

Delphi-Quellcode:

Sta  1:1       -> Diff=0    -> Ähnlichkeit=100%
Proz 3,5:-0,5  -> Diff=-4   -> Ähnlichkeit=80%
Gl1  0,23:0,24 -> Diff=0,01 -> Ähnlichkeit=99%
Gl2  1,2:1,3   -> Diff=0,1  -> Ähnlichkeit=98%
Gl3  0,6:0,7   -> Diff=0,01 -> Ähnlichkeit=98%
Gl4  0,7:0,73  -> Diff=0,03 -> Ähnlichkeit=99%

Ähnlichkeit durchschnittlich: 95,67%

Bei Differenz=0 ist die Ähnlichkeit pro Feld 100%.
Andernfalls musst Du einen Prozentwert pro Feld selbst festlegen (Z.B. Abhängig von den möglichen Maximal- und Minimalwerten pro Feld).
Du kannst natürlich die Bewertungen der anderen Felder auch wiederum von der Ähnlichkeit von Sta abhängig machen...

Stahli

[Go2EITS]

So ich habe mal ein schmutziges schnelles Programm geschrieben:

Ich habe 1000 Zeilen in der Daten.txt (liegt bei)
Damit es nicht zu kompliziert wird, habe ich mich auf die erste Zeile in der "Datenbank" beschränkt, die auf Ähnlichkeit mit den restlichen 999 Zeilen zu prüfen ist.
Wir sehen ab der Zeile 2 bis 1000 nach, wie ähnlich sich die Zeilen sind.

Ich verwende folgende Formel,
Ergebnis[x,i]:=(daten[x,i]/daten[1,i])/5;

wobei
x von 2 nach 1000 alle Zeilen durchläuft
i von 2 nach 6 alle Spalten, bis auf die erste Spalte, durchlaufen werden. (Mit der ersten Spalte habe ich noch ein Problem, sie verfälscht mein Ergebnis.) Die Ergebnisse speichere ich in das Array Ergebnis[1..1000,1..7], wobei die ich die Spaltenergebnisse in Ergebnis[1..1000,2..6] und die Summe/5 (5=Anzahl der Spalten) in Position 7 (Ergebnis[1..1000,7]) speichere.


Vorgehensweise:
Daten einlesen.
Alle Nullen in 0.01 ändern, weil ich ein Problem mit Division mit 0 bekomme.
Negative Ergebnisse unserer Berechnung werden in positive Zahlen mit *-1 überführt.
Einzelergebnisse von Spalte 2 bis 6 in 7 speichern.
Ausgabe der Ergebnisse beschränken auf Zahlen kleiner als 1 mit: if (ergebnis[x,7] < 1) then ...

Delphi-Quellcode:

program ReadDaten;

{$APPTYPE CONSOLE}
uses math;
var f:textfile;
    Feldnamen:string;
    Daten:Array[1..1000,1..6] of real;
    Ergebnis:Array[1..1000,1..7] of real;
    x,i:integer;
    h:real;
    AnzahlZeilen:integer;

function Runden(x: Extended; Stellen: Byte): Extended;
begin
Result:= Round(x * IntPower(10, Stellen))/IntPower(10, Stellen);
end;

begin

// DATEN in Array Daten einlese
assignfile(f,'C:\Daten.txt');
Reset(f);
readln(f,Feldnamen);
for X:=1 to 1000 do
    begin
    for i:=1 to 6 do
        begin
        read(f,daten[x,i]);
        end;
end;
closefile(f);


//Wir stellen sicher, dass keine 0 vorkommt und ersetzten diese durch 0.01;
for x:=1 to 1000 do
     begin
     for i:=1 to 6 do if daten[x,i]=0 then daten[x,i]:=0.01;
     end;


// Wir gehen alle Zeilen und Spalten in Muster durch und speichern das Ergebnis:
for x:=2 to 1000 do
    begin
    for i:=2 to 6 do
        begin
        // Wir dividieren durch die Anzahl der Daten, hier 5:
        Ergebnis[x,i]:=(daten[x,i]/daten[1,i])/5;
        //<Negative Ergebnisse bringen nicht das resultat, daher *-1
        if Ergebnis[x,i]< 0 then ergebnis[x,i]:=ergebnis[x,i]*-1;
        //Ursprünglich:
        {
        Ergebnis[x,i]:=(daten[x,i]/daten[1,i]);
        }

        end;//i..
    //Ergebnis von Spalte 2 bis 6 in 7 speichern:
    ergebnis[x,7]:=0;
    for I:=2 to 6 do ergebnis[x,7]:=ergebnis[x,7]+ergebnis[x,i];


// Die Ausgabe wird beschränkt:
if (ergebnis[x,7] < 1)  then
    begin
    writeln('Datensatz: ',x);
    for i:=2 to 6 do write(daten[1,i]:2:2,' ');writeln;
    for i:=2 to 6 do write(daten[x,i]:2:2,' ');writeln;
    for i:=2 to 6 do write(ergebnis[x,i]:2:2,' ');writeln;
    writeln('Ergebnis: ',ergebnis[x,7]:2:2);writeln;
    writeln('Taste');
    readln;
end;

end;//x..
writeln('Ende - ENTER');
readln;

end.

Ach ja, Datensatz 94 und 905 entspricht fast dem ersten Datensatz.
Wie könnte man es besser lösen? :gruebel:
Nachtrag: Die Datei Daten.txt bitte als C:\daten.txt speichern. Ich habe keine Fehlerabfragen zu besseren Übersichtlichkeit eingebaut.

[Go2EITS]

So, ich habe eine Ergänzung:
Wenn von die 5 Feldern ein Feld ein "Ausreisser" ist, dann prüfe, ob die Summe der restlichen 4 kleiner 1 ist.
Ist das der Fall, dann wird die Zeile/Datensatz als ähnlich angezeigt.
Ich verwende hierfür die Abfrage, an welcher Position der Aussreißer steht und weise den Index der Varibalen p zu und lösche
dann das Ergebnis[x,p]. Die neue Summe zeigt mir dann, ob der Datensatz, bis auf den Ausreißer ähnlich meiner ersten Zeile in der Datenbank ist.

Delphi-Quellcode:

// Wir prüfen, einen Aussreißer im Array Ergbnis[x,1.6] um zu sehen,
// ob 4 von 5 Werten unsere Bedingungen erfüllen.
if ergebnis[x,7] > 1 then
begin
   h:=ergebnis[x,2];
   p:=0;
   // 2 haben wir schon, mit drei machen wir weiter:
   for i:=3 to 6 do If ergebnis[x,i] >h then p:=I;
   // Aussreißer gefunden? Dann...
   if p>0 then
      begin
   // Wir setzen den Ausreisser auf NUll
      Ergebnis[x,p]:=0;
   // und berechnen die Summen von Ergebnis neu:
      ergebnis[x,7]:=0;
      for I:=2 to 6 do ergebnis[x,7]:=ergebnis[x,7]+ergebnis[x,i];
      end;

Der neue vollständige Code liegt bei. Bitte Daten.txt auf C:\ speichern.

Delphi-Quellcode:

program ReadDaten;

{$APPTYPE CONSOLE}
uses math;
var f:textfile;
    Feldnamen:string;
    Daten:Array[1..1000,1..6] of real;
    Ergebnis:Array[1..1000,1..7] of real;
    x,i:integer;
    h:real;
    p:integer;
    Anzahl:integer;

function Runden(x: Extended; Stellen: Byte): Extended;
begin
Result:= Round(x * IntPower(10, Stellen))/IntPower(10, Stellen);
end;

begin

// DATEN in Array Daten einlese
assignfile(f,'C:\Daten.txt');
Reset(f);
readln(f,Feldnamen);
for X:=1 to 1000 do
    begin
    for i:=1 to 6 do
        begin
        read(f,daten[x,i]);
        end;
end;
closefile(f);


//Wir stellen sicher, dass keine 0 vorkommt und ersetzten diese durch 0.01;
for x:=1 to 1000 do
     begin
     for i:=1 to 6 do if daten[x,i]=0 then daten[x,i]:=0.01;
     end;


// Wir gehen alle Zeilen und Spalten in Muster durch und speichern das Ergebnis:
for x:=2 to 1000 do
    begin
    for i:=2 to 6 do
        begin
        // Wir dividieren durch die Anzahl der Daten, hier 5:
        Ergebnis[x,i]:=(daten[x,i]/daten[1,i])/5;
        //<Negative Ergebnisse bringen nicht das resultat, daher *-1
        if Ergebnis[x,i]< 0 then ergebnis[x,i]:=ergebnis[x,i]*-1;
        //Ursprünglich:
        {
        Ergebnis[x,i]:=(daten[x,i]/daten[1,i]);
        }

        end;//i..
    //Ergebnis von Spalte 2 bis 6 in 7 speichern:
    ergebnis[x,7]:=0;
    for I:=2 to 6 do ergebnis[x,7]:=ergebnis[x,7]+ergebnis[x,i];


// Wir prüfen, einen Aussreißer im Array Ergbnis[x,1.6] um zu sehen,
// ob 4 von 5 Werten unsere Bedingungen erfüllen.
if ergebnis[x,7] > 1 then
begin
   h:=ergebnis[x,2];
   p:=0;
   // 2 haben wir schon, mit drei machen wir weiter:
   for i:=3 to 6 do If ergebnis[x,i] >h then p:=I;
   // Aussreißer gefunden? Dann...
   if p>0 then
      begin
   // Wir setzen den Ausreisser auf NUll
      Ergebnis[x,p]:=0;
   // und berechnen die Summen von Ergebnis neu:
      ergebnis[x,7]:=0;
      for I:=2 to 6 do ergebnis[x,7]:=ergebnis[x,7]+ergebnis[x,i];
      end;
end;


end;//x..

//Kurze Anzeige aller Datensätze, die gefunden wurden:
Anzahl:=0;
for x:=2 to 1000 do if Ergebnis[x,7] <1 then inc(Anzahl);
writeln('Anzahl der aehnlichen Datensaetze: ',Anzahl:2);
writeln;

// Anzeige aller Datensätze, die die Bedingungen erfüllen:
writeln('Anzeige der gefundenen Datensätze');
for x:=2 to 1000 do
begin
// Die Ausgabe wird beschränkt:
if (ergebnis[x,7] < 1)  then
    begin
    writeln('Datensatz: ',x);
    for i:=2 to 6 do write(daten[1,i]:2:2,' ');writeln;
    for i:=2 to 6 do write(daten[x,i]:2:2,' ');writeln;
    for i:=2 to 6 do write(ergebnis[x,i]:2:2,' ');writeln;
    writeln('Ergebnis: ',ergebnis[x,7]:2:2);writeln;
    writeln('Taste');
    readln;
end;
end;

writeln('Ende - ENTER');
readln;

end.

Programmanzeige nauch "unten" verlagert.
Vorschläge, Verbesserungen?

[alzaimar]

Zitat:

Zitat von stahli

Delphi-Quellcode:

Proz 3,5:-0,5  -> Diff=-4   -> Ähnlichkeit=80%

:gruebel:
Nicht doch eher soetwas wie -114% (also: gar nicht ähnlich)?

Ich würde mir eine Funktion schreiben, die zwei Tupel miteinander vergleicht, und den Ähnlichkeitsindex (0..1 oder 0..100) zurückliefert. Im Prinzip hast Du das ja gemacht, aber eine Funktion zentralisiert diese Entscheidungslogik und macht es imho übersichtlicher. Vielleicht solltest Du auch nicht von 'Ähnlichkeit' sprechen, sondern von einem 'Abstand', aber das ist Wortklauberei.

Für den Zugriff auf die Tupel sowohl als Array als auch auf die individuellen Werte würde ich einen 'variant record' verwenden.

Delphi-Quellcode:

Type
  TValues = Record
    Case Boolean Of
      False : (Sta, Proz, Gl1, Gl2, Gl3, Gl4 : Double); // Individueller Zugriff
      True  : (Values : Array [0..5] Of Double); // Indizierter Zugriff
  End;

Und die Funktion selbst so deklarieren;

Delphi-Quellcode:

Function SimilarityIndex (Const A,B : TValues) : Double;
Begin
....
End;

[stahli]

Zitat:

stahli hat folgendes geschrieben:
Delphi-Quellcode: markieren
Proz 3,5:-0,5 -> Diff=-4 -> Ähnlichkeit=80%

Nicht doch eher soetwas wie -114% (also: gar nicht ähnlich)?

... kann natürlich auch sein ;-)

Ich denke, wir meinen das Gleiche.
Ähnlichkeit oder Abstand, in jedem Fall muss er das selbst für jeden Eintrag und Feld selbst festlegen (was immer die Werte auch bedeuten mögen) und die Ähnlichkeit der Datensätze dann über eine Funktion ermitteln...

stahli