Chciałbym zrobić program przyporządkowujący dokumenty do wcześniej zdefiniowanych kategorii zawierających dokumenty testowe, na podstawie dokumentów testowych algorytm zaklasyfikuje do konkretnej kategorii dokumenty testowe. Zaimplementowałem już jeden algorytm, a teraz implementuję w celu porównania drugi - metodę k-nn i to z nią mam problem. Czas klasyfikacji u mnie metodą k-nn jest bardzo, bardzo długi, nie mówiąc już o tym, że często program kończy się błędem z powodu braku pamięci, więc coś musi być nie tak.
Algorytm k-nn (k - najbliższych sąsiadów) polega na tym, że to do jakiej kategorii zaklasyfikować dokument testowy ustala się porównując każdy dokument testowy z każdym dokumentem treningowym, po czym o przynależności do konkretnej kategorii decyduje wyliczone w ten sposób k - największych podobieństw dokumentu testowego do treningowego.
podobieństwo dokumentu testowego X do dokumentu treningowego Dj
http://imageshack.us/photo/my-images/225/beztytuuleq.jpg/
Czyli jak mam 10 000 dokumentów testowych i 200 dokumentów treningowych to będzie 2 mln porównań. A to jeszcze nie wszystko, bo w powyższym wzorze mamy jeszcze w - jest to waga.
w - waga słowa i w dokumencie j:
http://imageshack.us/photo/my-images/52/beztytuu2uv.jpg/
gdzie:
a - liczba wystapien slowa i w dokumencie j
b - calkowita liczba slow w dokumencie j
c - liczba dokumentow w zbiorze treningowym
d - liczba dokumentow w zbiorze treningowym zawierajacych wyraz i
więc to już w ogóle jest kosztowne, całość sprawia że klasyfikacja działa bardzo długo (nawet kilkadziesiąt minut) i często kończy się pamięć - co robię źle ?