3. MIT Youtube Kurs, Document Distance unter 0 ?

MIT Youtube Kurs, Document Distance unter 0 ?


  • Hallo Zusammen,

    Ich habe versucht den Algorithmus für das Problem aus diesem Video zu implementieren (ab 33:10)
    http://www.youtube.com/watch?v=Zc54gFhdpLA&list=SPUl4u3cNGP61Oq3tWYp6V_F-5jb5L2iHb&index=2
    (Formel ab 39:00)
    Nun bekomme ich zwar Output, aber ich bin mir nicht sicher, wie ich überprüfen kann, ob dieser richtig ist. Mir fehlt dazu das Wissen und im Video wurde nichts darüber gesagt.

    Was ich berechnet habe sollte theoretisch den Unterschied zwischen zwei .txt Dateien beschreiben. Kann das also überhaupt unter 0 liegen (der Logik nach, "Die Dateien haben den gleichen Inhalt", also 0 Unterschied).

    Ich habe mein Programm mal über zwei gleiche Dateien laufen lassen und bekomme
    -2147483648, das sieht doch ziemlich falsch aus, oder?

    Weiß jemand welches Ergebnis man haben sollte, wenn die Dateien exakt den gleichen Inhalt haben, bzw. wenn kein einziges Wort übereinstimmt?

    Wenn wir alles überspringen bis zu zwei vector<string>, welche jeweils die Wörter der Dateien enthalten bin ich wie folgt vorgegangen:

    vector<string> words_file1, words_file2;

map<string,int> wordcounts1;
map<string,int> wordcounts2;

//Wörter + dessen Häufigkeit in einer Map speichern
for(size_t i = 0; i < words_file1.size(); ++i)
{
    ++wordcounts1[words_file1[i]];
}

for(std::size_t i = 0; i < words_file2.size(); ++i)
{
    ++wordcounts2[words_file2[i]];
}
// Das dot product/ inner product berechnen
int dot_product = 0;

typedef map<std::string,int>::const_iterator Iter;

for(Iter p = wordcounts1.begin(); p != wordcounts1.end(); ++p)
{
    for( Iter i = wordcounts2.begin(); i != wordcounts2.end(); ++i)
    {
        if(p->first == i->first)
        {
            dot_product += p->second * i->second;
         }
    }
}
dot_product = acos(dot_product / words_file1.size() * words_file2.size());

    mfg
    HarteWare

    0
  • Mod

    Ich würde mal spontan vermuten, dass der acos NaN ergibt. Sicher, dass die (nicht vorhandenen) Klammern in dem Ausdruck richtig sind? Insgesamt finde ich Trigonometrie mit Integern verdächtig. Sicher, dass du den Algorithmus überhaupt richtig verstanden hast? Dir ist klar, dass die Ausdrücke alle einen Ganzzahltyp haben?

    (Wie du merkst, habe ich mir dein Video nicht angesehen. Dies sind allgemeine Beobachtungen, die ich aus dem Wert -2147483648 folgere. Der ist nämlich was besonderes.)

    0

  • SeppJ schrieb:

    Ich würde mal spontan vermuten, dass der acos NaN ergibt. Sicher, dass die (nicht vorhandenen) Klammern in dem Ausdruck richtig sind? Insgesamt finde ich Trigonometrie mit Integern verdächtig. Sicher, dass du den Algorithmus überhaupt richtig verstanden hast? Dir ist klar, dass die Ausdrücke alle einen Ganzzahltyp haben?

    (Wie du merkst, habe ich mir dein Video nicht angesehen. Dies sind allgemeine Beobachtungen, die ich aus dem Wert -2147483648 folgere. Der ist nämlich was besonderes.)

    Vielen Dank für die Antwort. Das sich jemand das Video 15 Minuten lang zu Ende schaut, hab ich auch nicht wirklich erwartet^^

    Also dass der acos wert eventuell kein int ist kann gut sein, um ehrlich zu sein weiß ich nicht was arccos überhaupt ist, ich habe es nur am Ende noch verbaut. Auf jeden Fall sollte es schon passen, dass die Zahlen davor alle ints sind. Ich meine, ein Wort in der einen Datei gleicht entweder dem Wort in der anderen oder nicht. Ob das Wort nun zu 50% mit einem anderen übereinstimmt oder nicht, das wird garnicht behandelt.

    Ich habe den obskuren Wert mal gegoogelt, aber da kam nix. ist das eventuell die negative höchstgrenze für einen int?

    wegen den Klammern, bei * und / dürfte das doch egal sein, oder? Aber das sollte schon alles in die acos Funktion rein.

    Nunja, ich glaube der algo ist auch abgesehen von dem acos etwas daneben^^ Vielleicht sollte ich mich vorerstmal leichteren Dingen widmem

    mfg
    HarteWare

    P.S.: Bedeutet NaN dass die Zahl auch keine Gleitkommazahl ist?

    0
  • O

    NaN bedeutet Not a Number. Du übergibst dem arccos da einen Wert, für den das Ergebnis nicht definiert ist.

    0
  • Mod

    HarteWare schrieb:

    wegen den Klammern, bei * und / dürfte das doch egal sein, oder? Aber das sollte schon alles in die acos Funktion rein.

    10/5*2 != 10/(5*2)

    0

  • Danke vorerstmal für die weiteren Hilfestellungen 🙂

    Ok, peinlich... Das mit den Klammern war mir in dem Moment nicht ganz bewusst 😃 Aber ich hab gestern noch ein bissle überlegt und das war so oder so falsch...

    mfg
    HarteWare

    P.S.: Für die zukünftigen Leser, die es interessieren könnte, der fertige Algorithmus (Verwendung auf eigene Gefahr, keine Garantie auf richtigkeit, provided "as is" etc. etc.)

    nähere Informationen gibts im obigen Video (Link)

    //Gegeben seien die beiden Vektoren mit allen Wörtern der jeweiligen Datei
vector<string> words_file1;
vector<string> words_file2;

map<string,int> wordcounts1;
map<string,int> wordcounts2;

for(size_t i = 0; i < words_file1.size(); ++i)
{
    ++wordcounts1[words_file1[i]];
}

for(size_t i = 0; i < words_file2.size(); ++i)
{
   ++wordcounts2[words_file2[i]];
}

double dot_product = 0;

typedef map<string,int>::const_iterator Iter;

for(Iter p = wordcounts1.begin(); p != wordcounts1.end(); ++p)
{
    for( Iter i = wordcounts2.begin(); i != wordcounts2.end(); ++i)
    {
        if(p->first == i->first)
        {
            dot_product += p->second * i->second;
        }
    }
}

double cos_word_vecs = dot_product / (words_file1.size() * words_file2.size());
double angle = acos(cos_word_vecs); 
// Winkel beschreibt ähnlichkeit der beiden Vektoren, welche wiederrum die Wörter + deren Anzahl der jeweiligen Datei beschreiben.

    Jegliche Art von Kommentaren sind gern gesehen 🙂

    0
Anmelden zum Antworten