Systemy rekomendacyjne od kuchni

- autor: tsissput
Poprzedni mój wpis dotyczył tematyki systemów rekomendacyjnych i dokonywał pobieżnego sprecyzowania problemu i wyjaśnienia kwestii z nim związanych. Dziś również chciałbym zająć się tematyką dotyczącą systemów rekomendacyjnych, jednak tym razem od strony praktycznej. Rekomdendować można dosłownie wszystko, jednak aktualnie chciałbym się zająć rekomendacjami dotyczącymi sprzedaży produktów. Jak wspomniałem ostatnio wyróżniamy kilka podejść do rekomendacji. Pierwsze podejście polega na wykorzystaniu atrybutów opisujących produkty w celu odnalezienia produktów podobnych. Może być to rodzaj, typ produktu, przedział cenowy, kategoria itp. Metody te określa się mianem Content Based Filtering. Drugie podejście, Collaborative Filtering, polega na identyfikacji innych użytkowników, których preferencje są podobne do naszych i rekomendowaniu nam produktów, które zostały przez nich pozytywnie ocenione. Obie te metody są powszechnie wykorzystywane w systemach rekomendacyjnych takich jak np. w sklepie internetowym amazon.com[1].

Content Based Filtering

 Rekomendowanie produktów z wykorzystaniem Content Based Filtering polega na poszukiwaniu produktów zakupionych (lub pozytywnie ocenionych) przez użytkownika oraz proponowanie mu produktów podobnych. Metoda ta jest wykorzystywana w stosunku do nowych użytkowników, o których ciężko jest cokolwiek wywnioskować, ponieważ nie posiadamy o nich wystarczających informacji, by móc zastosować metody z zakresu Collaborative Filtering. Problem ten określany jest mianem zimnego startu (ang. cold start)[2]. Gdy użytkownik rejestruje się w naszym sklepie internetowym nie mamy możliwości zaprezentowania mu spersonalizowanej treści, ponieważ nie wiemy nic na temat jego gustu. W trakcie, gdy użytkownik przegląda produkty w naszym sklepie możemy mu polecać jedynie produkty podobne do tych, które ogląda jak np. książki tego samego autora, filmy tego samego gatunku, czy produkty danego producenta. Zakładając, że mamy przygotowane mechanizmy śledzące zachowanie użytkownika, z czasem poznajemy jego gust. Wiemy jakich produktów poszukuje, jakie kategorie go interesują, czym kieruje się w ich wyborze itp. Jednak wraz z rosnącą ilością posiadanych przez nas informacji, rekomendacje uwzględniające produkty podobne stają się nienajlepsze. Zakładając, że użytkownik często ogląda produkty z kategorii “obuwie sportowe” mija się z celem polecanie mu wszystkich, losowo wybranych, czy nawet najlepszych produktów z tej kategorii. Rekomendacje bazujące jedynie na globalnej ocenie danego produktu powodują powstanie problemu tzw. długiego ogona prowadzącego do tego, że 80% użytkowników ogląda 20% wszystkich produktów. Jest to cecha wysoce nieporządana, ponieważ powoduje, że pewne produkty nigdy nie znajdą się na listach rekomendacyjnych klientów sklepu. Stąd też wprowadza się metody z rodziny Collaborative Filtering służące aktywacji drugiej części długiego ogona.

Collaborative Filtering

Wykorzystanie metod z zakresu Collaborative Filtering wymaga zastosowania bardziej wyrafinowanych mechanizmów filtracji. Użycie ich prowadzi jednak do uzyskania lepszych wyników, co przekłada się na większe zyski finansowe. Za 35% produktów sprzedawanych przez sklep internetowy amazon.com odpowiadają właśnie systemy rekomendacyjne[1]. Natomiast firma NetFlix (największa wypożyczalnia filmów w USA) aż 60% sprzedanych produktów zawdzięcza właśnie systemom rekomendacyjnym.

Jak w praktyce wygląda poszukiwanie rekomendacji z wykorzystaniem Collaborative Filtering?

Tradycyjne algorytmy Collaborative Filtering przedstawiają użytkownika jako N-wymiarowy wektor produktów, gdzie N jest liczbą prodkuktów w sklepie. Wektor ten zawiera wartości jego ocen danych produktów[1]. Wektor ten może dodatkowo zawierać wartości wag będące odwrotnością częstości globalnego oceniania danego produktu. Dzięki zastosowaniu wag zwiększamy istotność produktów, które posiadają niewiele ocen, dzięki czemu dajemy im szansę trafienia do list rekomendacyjnych użytkowników. Na podstawie otrzymanego wektora ocen poszukujemy użytkowników, których oceny pokrywają się z ocenami badanego użytkownika. Formalnie grupę takich użytkowników określa się mianem sąsiedztwa danego użytkownika. Do wyznaczenia takiego sądziedztwa należy zdefiniować tzw. funkcję odległości. Funkcja odległości stosuje natomiast wybraną metrykę do wyznaczenia odległości. Do wyboru są różne metryki odległości, m.in. odległość euklidesowa, odległość Czebyszewa, odległość Minkowskiego, czy odległośc cosinusowa[3]. Zajmiemy się ostatnią z nich jako jedną z najczęściej wykorzystywanej w e-commerce[4].

Odległość ta zdefiniowana jest następującym wzorem:

Algorytm Collaborative Filtering wykorzystywany do poszukiwania rekomendacji jest kosztowny pod względem czasu wykonania. Jego złożoność wynosi O(MN) w najgorszym razie, gdzie M jest liczbą użytkowników, a N liczbą produktów[1]. W praktyce jednak wektor ocen użytkownika jest rzadki (liczba zakupionych produktów przez klienta stanowi niewielki procent liczby wszystkich produktów w sklepie), przez co złożoność algorytmu poszukiwania rekomendacji dąży do O(M+N). Złożoność tą można jeszcze zmniejszyć jak zastosuje się dodatkowe filtrowanie polegające m.in. na wyeliminowaniu klientów, którzy kupili niewiele produktów, czy na wyeliminowaniu produktów, które mają dużo ocen.

Co w przypadku, gdy budujemy system rekomendacyjny do sklepu internetowego, który zawiera 29 milionów klientów oraz kilka milionów produktów (patrz amazon.com[1]), oraz który ma działać sprawnie w czasie rzeczywistym? Wówczas analizowanie ocen danego użytkownika z ocenami innych użytkowników w czasie rzeczywistym jest niewykonalne. Ponadto trzeba mieć na uwadze, że w każdej sekundzie oceniane są setki książek. Tu z pomocą przychodzą tzw. cluster models, czyli modele oparte o skupienia. Modele te dzielą użytkowników na wiele grup[5]. Rekomendacje są wówczas wyznaczane dla grup, a nie dla pojedynczych użytkowników, co jest operacją znacznie mniej kosztowną z uwagi na fakt, iż tych grup jest o kilka rzędów wielkości mniej niż użytkowników. Dodatkowym problemem pozostaje jednak przydzielenie danego użytkownika do danej grupy. Zastosowanie tej metody siłą rzeczy pogarsza wyniki, ale diametralnie zwiększa skalowalność i wydajność całego systemu. Ponadto najbardziej kosztowną pod względem czasowym operację, czyli wyznaczanie rekomendacji do grup, można wykonać off-line.

Podsumowanie

Jak już wspomniałem w poprzednim wpisie, systemy rekomendacyjne stopniowo zaczynają towarzyszyć nam na każdym kroku. Ogromny potencjał biznesowy tkwiący w systemach rekomendacyjnych gwarantuje im środki na dynamiczny rozwój. Już dziś tego typu systemy możemy spotkać na portalach społecznościowych (polecanie nowych znajomych, jak również stron firmowych), sklepach internetowych, portalach muzycznych, filmowych, wypożyczalniach dvd, czy nawet w klientach pocztowych (np. gmail[6]). Stopniowo większość (jak nie wszystkie) stron internetowych opartych na koncepcji Web2.0[7] będzie stosować coraz to bardziej zaawansowane systemy rekomendacyjne w celu dostarczania użytkownikowi silnie spersonalizowanej treści dopasowanej do jego upodobań umożliwiając przy tym wszelkiej maści reklamodawcom zupełnie nowy sposób reklamowania swoich produktów.

Reklamy

Skomentuj

Wprowadź swoje dane lub kliknij jedną z tych ikon, aby się zalogować:

Logo WordPress.com

Komentujesz korzystając z konta WordPress.com. Wyloguj / Zmień )

Zdjęcie z Twittera

Komentujesz korzystając z konta Twitter. Wyloguj / Zmień )

Zdjęcie na Facebooku

Komentujesz korzystając z konta Facebook. Wyloguj / Zmień )

Zdjęcie na Google+

Komentujesz korzystając z konta Google+. Wyloguj / Zmień )

Connecting to %s

%d blogerów lubi to: