Obsługa niepełnych danych (Data Sparsity) w kNN

Question

Próbuję stworzyć prosty system rekomendujący za pomocą knn.

Powiedzmy mam jakąś tabelę:

User | Book1 | Book2 | Book3 | Book4 | Book5 | Book6 | Book7 | 
1 | 5  | ?  | 3  | ?  | 4  | 3  | 2  | 
2 | 3  | 4  | ?  | 2  | 3  | 4  | 2  | 
3 | 4  | 2  | 1  | ?  | ?  | 3  | 3  | 
4 | 2  | 5  | 3  | ?  | 4  | 1  | 1  | 
5 | 1  | 1  | 4  | 3  | 1  | ?  | 1  | 
6 | 5  | 2  | 5  | 4  | 4  | 2  | ?  | 

Jeśli więc znaleźć możliwe wyniki dla użytkownika 1, myślałem, że po prostu wziąć bezwzględną różnicę książek 1 użytkownik odczytuje się z innymi użytkownikami. Następnie użyłbym tej różnicy, aby dowiedzieć się, który użytkownik z tej listy jest "najbliższy" użytkownikowi 1. Jednak w sytuacji rzeczywistej byłoby więcej wyników/nieznanych. Tak więc jak radzić sobie z tymi nieznanymi wynikami podczas korzystania z knn?

Nie mam żadnego kodu, ponieważ nie rozumiem jeszcze, jak to zaimplementować.

Każda pomoc jest doceniana!

Answer 1

Nie masz "nieznanych funkcji", masz niepełne punkty danych.

Jest to właściwie znany problem w kNN i istnieje całkowicie zwalidowany wzorzec do radzenia sobie z nim.

Choć problem jest rzeczywiście „niekompletne dane” problem w kontekście KNN to często (zwykle?) dalej sparsity problemu.

W praktyce problemem z rzadkością w budowaniu modeli węzłów jest, z wyjątkiem możliwego wyjątkowego przechowywania/wyszukiwania danych, które składają się na model, sedno kNN.

Na przykład, rozważmy zalecenie silnik Amazon.com za, w którym ocenie produktu jako użytkownik dysponuje obejmujący kolumny i użytkowników zawierające wiersze dla tej matrycy w 100% kompletna, każdy klient musiałby Amazon kupić i przejrzeć każdy pojedynczy porduct sprzedawane przez Amazon. Rzeczywista rozpiętość tej macierzy musi wynosić> 95%.

Najbardziej powszechną metodą (i które jest ciągle state-of-the-art miarę wiem) jest znany jako NNMA, lub nieujemnej aproksymacji macierzy. Technika ta jest często określana jako niepoprawnie jako NNMF, w której F oznacza czynnikatyzacji. (NNMA jest oparta na technice faktoryzacji, ale wynikiem nie są czynniki pierwotnej macierzy danych). Wspominam o tym, ponieważ ten alternatywny termin, choć niepoprawny, jest szeroko stosowany, więc zawarłbym go w moich wyszukiwarkach.

W istocie ta technika może być używana do usuwania rzadkości z matrycy lub umieszczania w inny sposób w celu zapełnienia brakujących komórek (tj. Klient w rzędzie R nie odtworzył produktu z kolumny C).

Możesz znaleźć kompletną implementację nnma wraz z towarzyszącym samouczkiem (w python + numpy) w Albert Au Yeung Ching-man's blog.

Alternatywnie istnieje kilka pakietów Pythona (dostępnych przez PyPI), które zawierają spakowany kod dla NNMA. Użyłem tylko jednego z nich, PyMF, który można znaleźć w Google Code.

Tak, że można zobaczyć, jak NNMA działa jego magia, tutaj jest moje proste, ale pełne wdrożenie NNMA w python + NumPy:

import numpy as NP 

def cf(q, v): 
    """ the cost function """ 
    qv = (q - v)**2 
    return NP.sum(NP.sum(qv, axis=0)) 


def nnma(d, max_iter=100): 
    x, y = d.shape 
    z = y 
    w = NP.random.rand(x, y) 
    h = NP.random.rand(y, z) 
    for i in range(max_iter): 
     wh = NP.dot(w, h) 
     cost = cf(d, wh) 
     if cost == 0: 
      break 
     hn = NP.dot(w.T, d) 
     hd = NP.dot(NP.dot(w.T, w), h) 
     h *= hn/hd 
     wn = NP.dot(d, h.T) 
     wd = NP.dot(NP.dot(w, h), h.T) 
     w *= wn/wd 
    return NP.dot(w, h) 

Aby skorzystać z tej funkcję NNMA, prostu przekazać w macierzy 2D z macierzą "0" dla każdej brakującej komórki (innymi słowy macierz danych z wstawionym "0" dla każdej brakującej wartości):

>>> d # the original (sparse) data matrix with missing cells denoted by "0"s 

    array([[ 7., 0., 4., 7., 0., 1.], 
     [ 3., 9., 7., 3., 1., 7.], 
     [ 4., 4., 3., 7., 3., 9.], 
     [ 4., 8., 0., 9., 2., 1.], 
     [ 6., 3., 9., 5., 9., 3.], 
     [ 6., 1., 4., 4., 1., 0.], 
     [ 0., 4., 8., 6., 0., 5.], 
     [ 9., 0., 6., 0., 5., 2.], 
     [ 6., 8., 4., 6., 3., 7.], 
     [ 3., 6., 3., 8., 7., 2.]]) 

>>> d1 = nnma(d)  # call nnma, passing in the original data matrix 

>>> d1 # the approximated data matrix with all missing values populated 

    array([[ 6.998, 0.29 , 3.987, 7.008, 0.292, 0.796], 
      [ 2.989, 8.92 , 6.994, 3.02 , 1.277, 7.053], 
      [ 4.007, 4.496, 2.999, 7.01 , 3.107, 8.695], 
      [ 4.005, 8.019, 0.254, 9.002, 1.917, 0.89 ], 
      [ 5.998, 3.014, 9.001, 4.991, 8.983, 3.052], 
      [ 5.992, 1.077, 4.007, 3.976, 0.753, 0.464], 
      [ 0.346, 3.436, 7.993, 5.988, 0.194, 5.355], 
      [ 9.001, 0.124, 5.997, 0.375, 5.02 , 1.867], 
      [ 6. , 7.994, 3.998, 6. , 2.999, 7.009], 
      [ 2.995, 6.022, 3.001, 7.987, 6.939, 2.185]]) 

Jak widać, wyniki nie są złe, szczególnie w przypadku bardzo prostej implementacji. Wszystkie brakujące elementy zostaną wypełnione, a pozostałe wartości są zbliżone do odpowiadającej wartości z oryginalnej macierzy danych, np. Kolumna 0, wiersz 0 to 7.0 w oryginalnej macierzy danych, a 6,998 w przybliżeniu.

Answer 2

KNN jest zwykle wrażliwy na #funkcje. W prawdziwym życiu spodziewam się, że będziesz mieć o wiele więcej książek.

Spróbowałbym zmienić przestrzeń funkcji: zamiast funkcji dla każdego dokumentu, może warto przeanalizować wykorzystanie list książek jako funkcji.

Feature1 = { books with score 1 } 
Feature2 = { books with score 2 } 
... 

Teraz można określić odległość dla każdej funkcji - być może za pomocą recall and precision pomiędzy każdymi dwoma listami 2 użytkowników.

Kolejną zaletą tej metody jest łatwy do nadania wagi funkcjom - być może lista książek w rankingu 5 jest bardziej pouczająca niż ta z 3?

Wadą jest to oczywiste, że nie zdobędą żadnego impuls jeśli użytkownicy A, B Miejsce książkę z 4,5 - jednak może być również rozwiązany poprzez dodanie innej funkcji, porównywanie tych list pomiędzy dwoma użytkownikami ..

Nota prawna: Nigdy nie testowałem tej metody i nie mam pojęcia, jak to będzie zachowywać się - ale myślę, że jest to podejście warte zbadania. Myślę, że nie ma dobrego sposobu na stwierdzenie, czy ta sugestia przyniesie dobre wyniki, z wyjątkiem testów empirycznych, które można wykonać za pomocą zestawu treningowego za pomocą cross-validation.

Answer 3

Utwór, którego brakuje, jest metodą pomiaru odległości. Korelacja Pearsona jest jedną z najczęściej stosowanych metod. Odległość Cosine jest inna. Odległość L1 (suma wartości bezwzględnych różnic) zwykle nie daje dobrych wyników.

Jeśli znajdziesz w Google zalecany sposób radzenia sobie z brakującymi wartościami na podstawie używanej odległości podobieństwa. Na przykład w Pearson tylko książki ocenione powszechnie przez dwóch użytkowników są używane do pomiaru korelacji, stąd brakujące wartości są po prostu ignorowane. Ma to sens, jak gdyby niewielka część książek czytanych przez dwóch użytkowników była wspólna, co najprawdopodobniej oznacza, że ​​mają różne gusta. W odległości kosinusowej brakujące wartości można przyjąć jako zero.

Inną powszechnie stosowaną metodą jest przypisywanie brakujących wartości. Możesz na przykład najpierw użyć Pearsona, aby znaleźć podobieństwo między książkami, a następnie dla każdej osoby przewidzieć brakujące oceny.

Answer 4

Moja sugestia jest taka, że ​​używasz Singular Value Decomposition (SVD) do wykonywania redukcji rang w swoim zestawie danych. Spowoduje to uzupełnienie brakujących wartości poprzez skuteczne zmniejszenie liczby funkcji, które każda książka ma do zaoferowania. Jest to bardzo podobne do Latent Semantic Analysis, sprawdź to.