pytanie o algorytm k-nn

0

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 ?

0

Skoro masz tylko 200 dokumentów treningowych i kończy Ci się pamięć to bez wątpienia coś robisz źle (o ile pojedynczy dokument nie zajmuje jakoś strasznie dużo, np. 50M).
Może próbujesz także wszystkie dokumenty testowe ładować do pamięci?
W jakim języku to piszesz? Jaka jest przeciętny rozmiar w bajtach dokumentu? W jaki sposób przechowujesz wagi konkretnych słów (jakaś mapa)? Ile jest różnych słów w dokumentach treningowych (tj. jaki jest rozmiar tej mapy)?

0

Wygląda to tak:

ilość dokumentów treningowych: 7 000
ilość dokumentów testowych: 3 000
ilość kategorii: 135

mój pierwszy zaimplementowany klasyfikator - naiwny klasyfikator Bayesa, który działa świetnie:
czas trenowania (uczenia klasyfikatora): 3 sekundy
czas testowania (przyporządkowania dokumentów testowych do kategorii): 23 sekundy
poprawność klasyfikacji: 80%

klasyfikator k-nn:
czas trenowania (uczenia klasyfikatora): 24 sekundy
czas testowania (przyporządkowania dokumentów testowych do kategorii): 447 sekund
poprawność klasyfikacji: 76%

W przypadku 12 000 dokumentów treningowych i 5 000 dokumentów testowych oraz 175 kategorii program z klasyfikatorem k-nn kończy się błędem OutOfMemory Exception.

Wszystkie dokumenty są typu .txt ze zwykłym plain textem. Każdy dokument ma maksymalnie 600 słów i maksymalnie 4 KB.

Język w jakim wykonałem programy to C#. Wagi i liczności słów przechowuje w kolekcjach o nazwie Dictionary.

0

No to kilka estymacji. Przy założeniu, że w każdym dokumencie jest ok. 100 unikalnych słów i słowo ma rozmiar 6 bajtów to daje razem: 12000 * 100 * (6 + 4) = 12MB na wagi słów a więc zbyt mało, żeby przepełnić pamięć.
Pamięć zajmowana przez dokumenty: 12 000 * 4KB = 48MB więc też mało.
Stawiał bym że masz gdzieś spory wyciek pamięci, czyli błąd w implementacji.

Wyjątek dostajesz w fazie uczenia algorytmu, czy w fazie testowania? Poczytaj jak debugować memory leaki w C# (akurat nie znam się na C# więc tutaj nie podpowiem).

0

A czy twoim zdaniem tak długi czas testowania jest normalny ? Bo jak porównuje do naiwnego klasyfikatora Bayesa to tam czas był znacznie krótszy.

0

Złożoność klasyfikatora Bayesa wynosi: O(ndk), gdzie n liczba sampli testowych, d to rozmiar dokumentu, k liczba klas.
Złożoność k-NN wynosi O(ndm), gdzie m to liczba sampli użytych do treningu (czyli w Twoim przypadku 20k). Nic dziwnego, że k-NN jest wolniejszy.
Istnieją metody do przybliżonego wyszukiwania k najbliższych sąsiadów, np. Locality Sensitive Hashing, które działają szybciej niż k-NN. Wada jest taka, że mogą być mniej dokładne niż k-NN.

0

Widzisz? jakbyś kodził w R to byłaby to bułka z masłem.

1 użytkowników online, w tym zalogowanych: 0, gości: 1