Powrót
|
| Sposoby implementacji systemów rekomendacyjnych |
 |
|
|
Marcin Majda, Software Engineer III Software Mind SA,
Software Developer's Journal nr 11
Marcin wprowadzi Cię w świat rekomendacji. Pokaże, jak przygotować spersonalizowaną treść która zainteresuje użytkownika. Przedstawi algorytmy podzielone na dwie kategorie: „User based” oparte na podobieństwach użytkowników, oraz „Item based” oparte na podobieństwie pozycji. Autor również przedstawia przykłady zastosowania rekomendacji oraz prezentuje najpopularniejsze metryki: euklidesową i cosinus-ową służące do wyliczania miary podobieństwa. |
Z systemami rekomendacji najczęściej mamy do czynienia w serwisach internetowych. Służą do personalizacji zawartości strony, czyli do przedstawienia informacji najbardziej interesujących aktualnie odwiedzającego użytkownika. Przykładów jest wiele, pierwszym, który chciałbym przedstawić, jest serwis YouTube.com. Oglądając film, mamy dostępną po prawej stronie sekcję „Podobne filmy wideo” (Rysunek 1). Przyglądając się sekcji, widać, że oferowane są podobne filmy, związane z tematyką aktualnie oglądanej pozycji. Bardzo często doprowadza to do sytuacji, że użytkownik klika kolejne i kolejne filmy, przez co jego zadowolenie z serwisu rośnie (dostaje spersonalizowaną zawartość – to, co mu się podoba) i spędza w nim coraz więcej czasu, na czym zależy właścicielom witryny. Drugim przykładem są sklepy internetowe, których szeroko znanym przykładem jest amazon.com – o jego rekomendacjach piszę w dalszej części artykułu. Innymi przykładami są serwisy randkowe, które starają się dopasować osoby do siebie, serwisy z galeriami zdjęć i wszystkie inne serwisy, które posiadają dużą liczbę pozycji, których użytkownik nie ma czasu przeglądać. Trzeba mu pokazać spersonalizowaną treść, dopasowaną do jego upodobań. Rekomendacje powinny pomóc odkryć nowe, interesujące pozycje. W serwisach internetowych często mamy do czynienia z listami TOP10, najlepiej oceniane, najczęściej kupowane, najczęściej komentowane. Doprowadza to do tego, że 80% użytkowników ogląda 20% produktów. Rekomendacje mają za zadanie aktywizację tzw. „długiego ogona” (Rysunek 2), czyli pokazanie użytkownikowi potencjalnie mało popularnych pozycji (znajdujących się w 80% nieoglądanych produktów), ale za to interesujących dla niego.
| | Rysunek 1. "Podobne filmy wideo" w serwisie YouTube |
| Rysunek 2. Zasada "długiego ogona"
|
Jak działają rekomendacje? Wszystko zaczyna się od zbierania danych. W przypadku sklepów internetowych pierwszą rzeczą, która się nasuwa, jest stworzenie sekcji „osoby, które kupiły tę pozycję również kupiły”. Sekcja taka pokazuje się obok aktualnie przeglądanej pozycji i podpowiada użytkownikowi, co jeszcze mógłby kupić, co może mu się przydać lub spodobać. W tym celu dla każdego klienta należy przechowywać listę pozycji, które kupił. Do serwowania rekomendacji można wykorzystać wiele różnych algorytmów. Jednym z nich może być znajdowanie podobnych użytkowników, to znaczy takich, którzy również kupili dany przedmiot i zaprezentowanie kupującemu listy pozycji, które ci użytkownicy nabyli. Dla przykładu użytkownik oglądający w księgarni książkę „Java i XML” może być zainteresowany pozycją „XML dla zaawansowanych”. Wiemy, że może nią być zainteresowany, ponieważ większość użytkowników, która kupiła „Java i XML”, kupiła również „XML dla zaawansowanych”. Drugie z możliwych rozwiązań polega na wyszukiwaniu i prezentowaniu pozycji podobnych do tej, którą kupujący właśnie ogląda. Dokładniej te algorytmy zostały opisane w dalszej części artykułu.
Algorytmy rekomendacji dają bardzo dobre efekty biznesowe. Greg Linden, autor systemu rekomendacyjnego amazon.com, podaje na swoim blogu, że aktualnie w sklepie 35% sprzedanych pozycji pochodzi z algorytmów rekomendacyjnych. Jeszcze większe współczynniki podaje NetFlix, największa wypożyczalnia filmów DVD w USA. Rekomendacje są dla nich kluczowym elementem, gdyż odpowiadają za 60% sprzedaży. Należy jednak pamiętać, że na efektywność rekomendacji wpływ ma wiele czynników. Na pewno najważniejszą kwestią jest dobry algorytm, ale nie bez znaczenia jest interfejs użytkownika. To, w którym miejscu umieścimy rekomendacje, jak duże one będą, ma kluczowe znaczenia dla ich efektywności. Jedynym z podziałów algorytmów rekomendacji jest „User based” i „Item based”. W pierwszym generujemy rekomendacje na podstawie podobieństwa użytkowników. Dla danego użytkownika znajdujemy listę podobnych do niego i w oparciu o to generujemy rekomendacje. Jeśli chodzi o drugie podejście, to rekomendacje generowane są w oparciu o podobne pozycje. Dla każdej pozycji poszukujemy podobnych do niej i przedstawiamy je użytkownikom. Na początek zajmijmy się najprostszymi algorytmami typu „Item base”, są tzw. „Search-Based Methods” oraz „Content-Based Methods”. Wyszukują one podobne pozycje, wybierając na przykład:
- książki tego samego autora,
- filmy tego samego reżysera,
- filmy tego samego aktora,
- filmy z tego samego gatunku,
- książki/filmy z podobnymi słowami w tytule,
- książki/filmy z podobnym tytułem.
Metody te charakteryzują się tym, że są skuteczne i działają dobrze, gdy mamy mało informacji o użytkowniku. Jeśli użytkownik pojawia się w naszym sklepie internetowym po raz pierwszy, nie posiada żadnej historii zakupów i ogląda jakąś pozycję, to możemy mu polecić inne książki tego samego autora (lub jedną z opcji wypisanych powyżej). Sprawdzamy, jaki jest autor aktualnie oglądanej pozycji, wyszukujemy wszystkie pozycje tego autora, jakie mamy w bazie danych, i pokazujemy użytkownikowi. Jeśli ilość dostępnych pozycji danego autora w bazie jest większa niż ilość miejsc na rekomendacje, to możemy wybrane pozycje sortować od najnowszej lub od najlepiej ocenianej (jeśli posiadamy ranking według ocen nadawanych przez użytkowników). Jeśli jednak chcemy wykorzystać te metody do budowy pełnego systemu rekomendacyjnego, to stają się one mało efektywne. Jeśli użytkownik posiada kilka zakupionych lub ocenionych pozycji, to nie ma problemu, jeśli posiada ich setki, to jesteśmy zmuszeni do budowania zapytania, które ma znaleźć wszystkie książki jednego z setek autorów. W związku z tym algorytmy te stają się niepraktyczne, gdyż czas i koszt zapytania do bazy danych jest zbyt duży. Zostajemy zmuszeni do redukcji ilości pozycji branych do zapytania, musimy brać podzbiory, przez co pogarsza się jakość rekomendacji. W każdym przypadku, jakość tych rekomendacji jest niska. Stają się one zbyt wąskie (na przykład pokazujemy książki jednego autora) i zbyt ogólne (pokazujemy tylko filmy dramatyczne). Jak pisałem na początku, rekomendacje powinny pomóc znaleźć i odkryć nowe, interesujące pozycje. Niestety, „Search-Based Methods” oraz „Content-Based Methods” pokazują popularne pozycje, które w wielu przypadkach użytkownik już zna. Algorytmem z drugiej grupy możliwym do wykorzystania przy tworzeniu systemów rekomendacyjnych jest tzw. „Collaborative filtering”, który jest typu „User based”. Pozwala on wyszukiwać użytkowników o podobnych gustach (preferencjach). Rozważmy przykład księgarni internetowej. Mamy dostęp do informacji, jakie pozycje zakupił nasz klient. Możemy traktować każdego klienta jako n-wymiarowy wektor pozycji dostępnych w księgarni. Każdy klient jest wektorem o wartościach: 1 - kiedy klient zakupił daną książkę, i 0 - kiedy klient nie zakupił danej książki. Dla większości klientów taki wektor jest rzadki, tzn. występuje dużo więcej wartości 0 niż 1. Wynika to z tego, że księgarnie posiadają tysiące produktów w swojej ofercie, a przeciętny klient w historii zakupów posiada zazwyczaj kilka, kilkanaście lub kilkadziesiąt pozycji. Algorytm generuje rekomendacje w oparciu ogrupę klientów, którzy są najbardziej podobni do rozważanego użytkownika. Miarę podobieństwa między dwoma użytkownikami można wyliczać na wiele sposobów. Pierwszym sposobem jest wykorzystanie Euklidesowej odległości między dwoma punktami. W naszym przypadku będą to końce wektorów (każdy użytkownik jest reprezentowany jako wektor i porównujemy podobieństwo dwóch użytkowników):
| Wzór 1. Euklidesowa odległość między dwoma punktami
|
A – współrzędne wektora rozważanego użytkownika,
B – współrzędne wektora użytkownika, do którego porównujemy,
d(A,B) – Euklidesowa miara odległości między dwoma punktami,
n – ilość pozycji w księgarni,
W takiej mierze użytkownicy są bardziej do siebie podobni im mniejsza jest wartość d(A,B). Zazwyczaj doprowadza się miarę do formy pozwalającej określić że użytkownicy są tym bardziej podobni im wartość podobieństwa jest większa. Do tego celu wykorzystuje się normalizację i określa:
| Wzór 2. Podobieństwo wektorów A i B wykorzystujących Euklidesową miarę odległości
|
Dzięki temu zabiegowi każde podobieństwo między dwoma użytkownikami będzie zawierać się w przedziale (0,1> i im większa jego wartość tym użytkownicy są bardziej podobni.
Innym sposobem obliczania podobieństwa jest miara cosinusowa wyrażająca się wzorem:
| Wzór 3. Cosinus-owa miara podobieństwa dwóch wektorów
|
Istnieje bardzo wiele metryk pozwalających określać miary podobieństwa i często są one wybierane na etapie budowy systemu rekomendującego. Można eksperymentować i testować swój system dobierając taką metrykę, która daje najlepsze efekty. Ale wracając do algorytmu, mając wybraną metrykę, system dla danego użytkownika wyszukuje kilku użytkowników, którzy są do niego najbardziej podobni. Odbywa się to poprzez sprawdzenie miary podobieństwa między rozpatrywanym użytkownikiem a każdym innym znajdującym się w systemie. Z grupy wybranych użytkowników eliminujemy pozycje, które użytkownik, dla którego generujemy rekomendacje już zakupił. Powstaje nam w ten sposób zbiór pozycji, które zakupili użytkownicy najbardziej podobni do aktualnie rozważanego. Tak powstały zbiór jest listą rekomendacji, które możemy przedstawiać na stronie internetowej. Drugą możliwością implementacji „Collaborative filtering” jest wykorzystanie ocen użytkowników. Wybierając skalę od 1 do 5 użytkownik może ocenić każdą pozycję. Na podstawie ocen możemy stworzyć wektor dla każdego użytkownika. Podobnie jak z zakupionymi pozycjami, przy czym tutaj pojawia się większy zakres wartości. Dla tak stworzonego wektora w analogiczny sposób poszukujemy podobnych użytkowników do aktualnie rozpatrywanego, wybieramy grupę najbardziej podobnych, eliminujemy pozycje, które nasz użytkownik już ocenił i pokazujemy te, które zostały wysoko ocenione przez grupę podobnych użytkowników.
Trzecim rodzajem algorytmów są modele klastrujące tzw. „Cluster Models” typu „User based”. Modele te dzielą użytkowników na wiele grup. Celem jest przyporządkowanie użytkownika do grupy zawierającej najbardziej podobnych użytkowników do niego. Podobnie jak „Collaborative filtering” wykorzystują metrykę podobieństwa. Algorytm wylicza podobieństwo użytkownika do danej grupy a wartość dla grupy jest sumą wektorów wszystkich użytkowników w danej grupie. Metody klastrujące posiadają lepszą skalowalność i wydajność niż Collaborative Filtering, porównują użytkownika tylko z grupami a nie użytkownika z każdym innym. Modele te posiadają również wiele wadę, mianowicie klastrowanie jest bardzo kosztowne. Często wykorzystuje się zachłanne algorytmy wybierając losowych użytkowników i tworząc w ten sposób początkowe grupy, zapewnia się metody łączenia grup i tworzenia nowych, niektóre algorytmy klasyfikują użytkownika do wielu grup i opisują siłę relacji z każdą z nich. Metody klastrujące grupują wielu użytkowników do jednej grupy, następnie rozpatrują wszystkich użytkowników w grupie w celu stworzenia rekomendacji. Rekomendacje tworzone są podobnie jak w przypadku Collaborative Filtering. Z użytkowników w danej grupie usuwane są pozycje zakupione (ocenione lub przeglądnięte w zależności, czym jest wektor użytkownika) przez danego użytkownika i z pozostałych wybieramy podobnie jak w Collaborative Filtering zbiór, który staje się rekomendacjami.
Powyższe algorytmy rekomendacji nadają się do pewnych grup zastosowań. W przypadku małej ilości użytkowników Collaborative Filtering sprawdza się bardzo dobrze. Jeśli w początkowej fazie nie posiadamy żadnych informacji o użytkowniku to możemy wykorzystać „Search-Based Methods” oraz „Content-Based Methods”. Jednak, gdy mamy do czynienia z milionami użytkowników i milionami pozycji należy sięgać, po bardziej złożone algorytmy takie jak zaproponowany przez zespół badawczy amazon.com „Item-to-Item Collaborative Filtering”, który mam nadzieję będzie tematem kolejnego artykułu.
Podsumowując systemy rekomendacyjne są bardzo złożonymi i trudnymi do implementacji systemami. Należy pamiętać, że przed implementacją należy określić cele biznesowe, jakie mają być realizowane, przeprowadzić dokładną analizę posiadanych danych i na tej podstawie wybrać algorytm dostosowany do potrzeb danego systemu. Stosowane są również rozwiązania hybrydowe, wykorzystujące metody „Item based” przy krótkiej historii, oraz metody „User based” przy długiej historii użytkownika w systemie. Ostateczny algorytm w systemach rekomendacyjnych jest zazwyczaj efektem wielu prób i analiz na żywym organizmie. Po stworzeniu pierwszej wersji systemu sprawdzana jest skuteczność algorytmu i rozpoczyna się żmudny proces optymalizacji, który trwa wiecznie, gdyż nie należy „spuszczać oka” z systemu rekomendacji i zawsze trzeba kontrolować i optymalizować jego skuteczność. |
|