Folksr: algorytm szukania podobnych wpisów
29 May 2009
folksr algorytm podobne wpisy
Program prywatnej bety Folksr-a postępuje znakomicie i odzew społeczności jest ogromnie nagradzający. Szczególne podziękowania należą się roziemu i breffie (czy to się odmienia?) za cenne uwagi i raporty. Myślę, że będę Was musiał jakoś wynagrodzić, chłopaki ;-) Ale do rzeczy; oto algorytm używany przez Folksr-a do wyszukiwania podobnych wpisów.
Co się stanie jak dodam 1000 tagów?
No właśnie. Obliczanie podobieństwa wpisów na podstawie tylko i wyłącznie liczby tagów nie jest lepszym pomysłem. Technologia WWW już to przerabiała w postaci nagłówków meta z atrybutem keywords. Pole to szybko stało się na tyle bezużyteczne, że obecnie żadna wyszukiwarka nie bierze go pod uwagę. Folksr ogranicza liczbę indeksowanych tagów do dziesięciu. Jest to przyzwoita liczba, którą można wyrazić esencję treści i zachęca do rzetelnego tagowania swoich wpisów. Jest poza tym zgodna z ogólnymi wzorcami interfejsów użytkownika, gdzie 3-7 to zakres optymalny (jak myślicie, skąd 37signals wzięło swoją nazwę?).
Punkty za ilość
Każdy zbieżny tag jest punktowany i stanowi równą część wyniku. Załóżmy więc, że popełniłem wpis otagowany jako ubuntu 9.04 jaunty launch party dublin. Przyjmijmy też, że dwie inne osoby postanowiły podzielić się z blogsferą podobnymi wpisami. Pierwszy z nich zawiera tagi ubuntu 9.04 release party katowice, drugi jest oznaczony ubuntu 9.04 jaunty jackalope linux unix gnome recenzja. W obu przypadkach znalezione blogi mają po trzy tagi wspólne z wpisem na blogu gospodarza, ale ten drugi jest dużo szerszy. Jak ocenić który z nich jest trafniejszy?
Punkty za jakość
Do głosu dochodzi zatem zasada, że nie liczy się ilość lecz jakość. Ponieważ szerzej otagowane wpisy mogą być mniej trafne Folksr pomniejsza wagę wpisów o dużej liczbie tagów. Zapobiec ma to dodawaniu etykiet, które są słabo bądź wcale nie powiązane z tagami na blogu gospodarza. W drugim przypadku przytoczonym powyżej można się zgodzić, że tagi linux unix gnome są nieco nadmiarowe, a nawet błędne (unix???)
Jakość × ilość
Folksr bierze pod uwagę zarówno jakość jak i ilość. Każdy tag ma przyznaną pewną liczbę punktów, ale im więcej tagów tym punktów mniej. Ponieważ liczba tagów ograniczona jest do 10, to dwie skrajne możliwości są następujące:
- 1 tag za 10 punktów
- 10 tagów po jeden punkt każdy
Wielkości pośrednie łatwo sobie wyobrazić: 2 tagi po 9 punktów każdy, 3 tagi po 8 punktów każdy, itd. Gdy wartość pojedyńczego tagu jest wyznaczona Folksr przystępuje do zliczania pasujących tagów. Wartość każdej etykiety zostanie pomnożona przez liczbę tagów zgodnych z tagami na blogu gospodarza, wg wzoru:
wynik = (11 - liczba tagów) × liczba podobnych tagów
Wracając do wcześniejszych przykładów, wyliczmy punktację dla każdego z nich:
-
ubuntu 9.04 release party katowice
(11 - 5) × 3 = 18 -
ubuntu 9.04 jaunty jackalope linux unix gnome recenzja
(11 - 8) × 3 = 9
Zgodnie z przeczuciem, wpis nr 2 został oceniony niżej, natomiast nagrodzona została celność tagów we wpisie nr 1.
Punktacja na max
Skoro wiemy już, że Folksr nagradza za ilość przekładającą się na jakość, to ile punktów można osiągnąć maksymalnie? Szybki rachunek w arkuszu kalkulacyjnym pokazuje, że najwyższa liczba punktów możliwych do osiągnięcia to 30:
| Liczba trafień | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
|---|---|---|---|---|---|---|---|---|---|---|
| Wartość taga | 10 | 9 | 8 | 7 | 6 | 5 | 4 | 3 | 2 | 1 |
| Wynik | 10 | 18 | 24 | 28 | 30 | 30 | 28 | 24 | 18 | 10 |
Wartość 30-tu punktów można osiągnąć publikując 5 lub 6 tagów pod warunkiem, że wszystkie z nich są zbieżne z tagami na blogu gospodarza. Całkiem przyzwoite wyniki uzyskuje się również dla 4 lub 7-miu tagów, co może być dość dobrą strategią biorąc pod uwagę trudność utrafienia wszystkich pięciu lub sześciu tagów (twórcy totolotka też potrafią liczyć ;-)
Kalkulator punktacji
Poniżej zamieszczam szybki kalkulator punktacji napisany w JavaScripcie. Oczywiście nie ma sensu brać go na poważnie – w końcu nie o to chodzi w blogowaniu; niech posłuży tylko jako ilustracja zastosowanego w Folkserze algorytmu i miernik jego jakości.
Liczba tagów: × Liczba trafionych: = 21
- Breffa
Sam to tak wymysliles? Wielki szacun dla Ciebie :)
PS. Tak, dobrze odmieniasz :) Jako jeden z nielicznych ;)- stronger
Breffa, miałem kilka podejść do algorytmu. Większość z nich była skomplikowana i dawała się oszukać. Niektóre budowane z uwzględnieniem punktacji wcześniejszych wpisów były na tyle niestabilne, że ze zdziwieniem zauważyłem, że inflacja może występować nie tylko w finansach. Tylko algorytmy liniowe bez zapisu historycznego działały w miarę wiarygodnie, więc ostatecznie wybrałem ten najprostszy.
- Airborn
Najprostsze rozwiązania kolejny raz okazują się najskuteczniejsze...
- rozie
Dzięki za wyjaśnienie algorytmu. Nie jest zły, choć pewne wnioski są oczywiste. :-) Biorąc pod uwagę analizę optymalnej ilości tagów trzeba uwzględniać (średnią? minimalną?) ilość tagów w wpisach, z którymi chcemy mieć zbieżność.
Chociaż i tak wydaje mi się, że jeśli nie ma gwarancji symetrii wpisów (teraz jeśli wpis A ma 3 tagi, wpis B 8 tagów i zbieżne są 2, to wartość W(A->B)=(11-3)*2=16, a W(B->A)=(11-8)*2=6) to istnieje możliwość abuse. Tak naprawdę w tej chwili im więcej mamy tagów, tym większa szansa, że do kogoś podlinkujemy, a ten ktoś do nas nie, prawda?- stronger
rozie, prawda i nieprawda. Musisz znaleźć złoty środek, bo zwiększając liczbę tagów zwiększasz swoje szanse na zakwalifikowanie się do cudzego widgetu, ale jednocześnie obniżasz szanse na wysoką pozycję. W efekcie możesz w ogóle wypaść z widgetu ze względu na niewystarczającą punktację.