Właśnie przeczytałem, jak zespół Pragmatic Chaos zespołu BellKor jest winning the Netflix Challenge na Wired i jestem ciekawy, jak zwykle działają tego rodzaju algorytmy. Wiem, że rozwiązanie zespołu Bellkora musi być innowacyjne na polu ... ale jak zwykle działa to pole? Czy jest to po prostu bardzo szczegółowa baza danych z łańcuchami Markowa, które są uruchamiane raz po raz czy co?Jak zwykle działają automatyczne algorytmy rekomendacji?
ale jak to zwykle działa?
Jest to technika Data Mining. Data Mining jest wykorzystywany jako część Business Intelligence (Data Warehouse i innych), próbując znaleźć relacje i informacje w ogromnych ilościach danych. Jest to dziedzina informatyki, zajmująca się również ogólnie uczeniem maszynowym, np. rozpoznawanie wzorców. Automatyczne rekomendacje są dostępne pod numerem Association Mining. Związek z wysokim wsparciem jest pokazany jako zalecenie. Algorytm k-najbliższego-sąsiada jest tylko jednym z wielu algorytmów wykorzystywanych przez osoby uczące się/eksploracji danych.
Jeśli interesuje Cię podstawowa teoria, polecam Data Mining: Practical Machine Learning Tools and Techniques autorstwa Iana H. Wittena.
Dla języka Java dostępny jest wielki pakiet uczenia maszynowego, WEKA, który może wykonać association mining. Ian Witten jest także jednym z autorów WEKA.
Zobacz artykuł z Wikipedii: Euclidean Distance.
Podstawową ideą jest użycie metryki odległości (takiej jak Euklidesa powyżej) do porównywania ludzi lub rzeczy ze sobą.
Nowa książka O'Reilly, Programming Collective Intelligence: Building Smart Web 2.0 Applications ma wspaniały rozdział na ten temat.
Znalazłem this previous article na Wired, który krótko wspomina o k-nearest-neighbor algorithm, używanym w przeszłości przez Bellkor i Cinematch.
Obserwacje poczynione przez psychologa na temat tego, jak znaleźć błąd, są również interesujące.
Większość uczestników Konkursu Netflix używa wersji Singular Value Decomposition. Algorytm ten działa poprzez wzięcie dużej macierzy i uproszczenie jej do przybliżonej macierzy 2x2. Ta matryca 2x2 może następnie zostać wykreślona na dwuwymiarowej przestrzeni, w której punkty w pobliżu siebie mają powinowactwo ze sobą w oryginalnej macierzy.
W przypadku Netflix można utworzyć matrycę z filmami będącymi kolumnami, a użytkownikami będącymi wierszami, gdzie dowolna wartość [i, j] to ocena przyznana przez użytkownika i. J. Jest to bardzo duża matryca, która może następnie zastosować SVD do wygenerowania dwuwymiarowej matrycy, która służy jako przybliżenie większej matrycy. Użytkownicy, którzy są blisko siebie, gdy są narysowani na tej płaszczyźnie, mają podobne oceny, więc jeśli jeden użytkownik nie widział filmu, który inny użytkownik zobaczył, kto jest blisko niego na tej płaszczyźnie, może to być zalecenie dla nowego użytkownika.
Zwycięskie rozwiązanie zaprojektowało odmianę prostego algorytmu SVD o nazwie SVD ++ i wymieszało to wraz z innymi skrajnymi przypadkami w celu wypróbowania algorytmu, który przekroczyłby 10% poprawę potrzebną do odebrania nagrody.
Innym podejściem jest odległość manhattan (lub geometria Taxicab) (szybciej obliczyć, mniej dokładna niż Euklidesowa) – adhg