wtorek, sierpnia 18, 2009

Ekszperyment :-) czyli Podobne posty :-)

Jeśli ktoś częściej zagląda na mojego bloga, to na pewno zauważył, ze od jakiegoś czasu nowe posty wzbogacone są o sekcję "Podobne posty".
Ma to na celu rozpropagowanie mojego skrzywionego spojrzenia na świat ;-) mówiąc inaczej ma zmniejszyć bouncing rate mojego bloga. Wstępne obserwacje wskazują, że może się to powieść ;-)

Do teraz sekcja ta dodawana była przeze mnie ręcznie na podstawie linków wygenerowanych przez jeden z moich programików. Ale teraz doszedłem już do wariantu półautomatycznego ;-)
Najpierw trzeba uruchomić programik, który pobierze bloga [trawa to około 10-20 sekund ;-)], później drugi, który wyliczy podobieństwo między postami i stworzy odpowiedni zestaw "instrukcji" [do niedawna było to około 700 sekund, teraz około 150-170], i w końcu trzeci program który na podstawie "instrukcji" przeprowadza updatowanie postów ;-) [kilka minut dla całego bloga ;-)]

Sam proceder obliczania podobieństwa między postami byłby dużo prostszy gdyby nasz język nie był złośliwy ;-) i gdybyśmy nie mieli odmiany przez czasy, osoby, liczbę, rodzaj, przypadki i co tam jest jeszcze. Ale mimo wszystko wyniki zwykle mają jakiś sens ;-)

Na początku próbowałem użyć standardowego podejścia z obliczaniem odległości między dokumentami, gdzie odległością była odległość między punktami w n-wymiarowej przestrzeni [gdzie n to moc zbioru słów użytych w porównywanych dokumentach], które to punkty wyznaczane były przez współrzędne będące częstotliwościami występowania słów w dokumentach, działało to tak sobie. Nawet wzięcie pod uwagę średniej dla całego korpusu częstotliwości słów niewiele pomogło.

Następnym podejściem było skorzystanie ze sztuczki ;-) W końcu jeżeli mamy dwie częstotliwości dla danego słowa - f1 i f2 w dwóch dokumentach to wiemy, że ułamek:
min(f1,f2)/max(f1,f2)

będzie miał wartość 1 tylko gdy częstotliwości w obu dokumentach są identyczne, czyli gdy są bardziej podobne. Sumując po wszystkich słowach dojdziemy do rankingu podobieństwa. To była w miarę dobra droga i wystarczyło ją wzbogacić o czynnik związany z tym czy dane słowo jest ważne czy nie, w końcu to, że spójnik "i" występuje w większości dokumentów nie czyni ich znów tak bardzo podobnymi. Czyli doszedł kolejny czynnik count, czyli ilość dokumentów w korpusie z danym słowem:

min(f1,f2)/max(f1,f2)/count


Im słowo częściej występuje w korpusie tym mniej jest ważne. Nie jest to do końca bezpieczna hipoteza, ale w miarę pomaga ;-) [choć w dłuższej perspektywie wprowadza pewne zamieszanie w wynikach].

Takie podejście działa już w miarę dobrze, ale dobrze jeszcze wziąć pod uwagę prawdopodobieństwo w danym dokumencie ;-) Tu nie do końca umiem znaleźć wytłumaczenie, ale wyniki wydają się wtedy lepsze. Mamy więc w końcu:

min(f1,f2)/max(f1,f2)/count*f1


przy założeniu, że liczymy współczynniki dla dokument1. Teraz wystarczy to wszystko zsumować ;-) I mamy już wartość dla dokumentu, wystarczy teraz więc policzyć te sumy dla wszystkich dokumentów i następnie je posortować ;-)

Jak łatwo stwierdzić, dokumenty będą tym bardziej podobne im mają więcej wspólnych słów [sensowna hipoteza], częstotliwości tych słów są podobne [też ma sens], i są to ważne słowa.

Mam jeszcze kilka pomysłów na wyliczanie podobieństwa i mam nadzieje je wypróbować ;-) Teraz celem jest połączenie 3 programów w 1 i dodanie mu jakiegoś GUI ;-)
Muszę też dodać trochę "inteligencji", która pozwoli na uniknięcie updatowania postów, które już mają odpowiednie linki w sobie. Bez tego Blogger trochę szaleje ;-) przez co przez przypadek zyskałem dziś jakieś 40 wejść bo moje posty zasypały listę "ostatnich wpisów" Bloggera.


Podobne postybeta
Podobne posty i zachwyty nad nimi... ;-) i trochę o Java 7
"Semisubiektywna" klasyfikacja dokumentów ;-)
Działa :-)
Przybijające cosie.......
Postęp... powolny postęp