Gestione di dati incompleti (scarsità di dati) in kNN

Question

Sto cercando di creare un sistema di raccomandazione semplice usando knn.

Diciamo che ho un po 'di una tabella:

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  | ?  | 

Quindi, se per trovare i punteggi possibili per l'utente 1, stavo pensando che basta prendere la differenza assoluta del libri utente 1 lettura con altri utenti. Quindi userò questa differenza per scoprire quale utente da quella lista è "più vicino" all'utente 1. Ma nella situazione del mondo reale, ci sarebbero più/punteggi sconosciuti. Quindi come faccio a gestire quei punteggi sconosciuti quando si usa knn?

non ho alcun codice, come devo ancora capire veramente come implementare questa.

Qualsiasi aiuto è apprezzato!

Answer 1

Non è "caratteristiche sconosciute" che hai punti di dati incompleti.

Questo è in realtà un problema ben noto in kNN ed e v'è un modello completamente convalidato per trattare con esso.

Anche se il problema è in realtà un problema di "dati incompleti", nel contesto kNN è spesso (solito?) denominato scarsità problema.

In pratica, il problema di sparsità nella creazione di modelli knn è, con la possibile eccezione di archiviazione/recupero efficiente dei dati che comprendono il modello, il nodo di kNN.

Ad esempio, si consideri motore raccomandazione di Amazon.com, in cui feedback sui prodotti come utente dispone comprendente le colonne e utenti comprendente le righe , per questa matrice di essere completa al 100%, ogni cliente Amazon avrebbe avere acquistato e rivisto ogni singolo porduct Amazon vende. L'effettiva scarsità di questa matrice deve essere> 95%.

La tecnica più comune (e che è ancora allo stato dell'arte per quanto ne so) è noto come NNMA o non negativo matrice approssimazione. Questa tecnica viene anche spesso indicata come in modo errato come NNMF, in cui F sta per fattorizzazione. (L'NNMA si basa su una tecnica di fattorizzazione, ma il risultato non sono i fattori della matrice di dati originale.) Lo dico perché questo termine alternativo, sebbene scorretto, è ampiamente usato, quindi lo includerei nelle mie query sui motori di ricerca.

In sostanza, questa tecnica può essere utilizzata per rimuovere la scarsità da una matrice, o in altro modo, per popolare le celle mancanti (ad esempio, il cliente della riga R non ha rivisto il prodotto della colonna C).

È possibile trovare un'implementazione completa di nnma, incluso un tutorial di accompagnamento (in python + numpy) in Albert Au Yeung Ching-man's blog.

In alternativa, ci sono diversi pacchetti python (disponibili tramite PyPI) che contengono codice pacchettizzato per NNMA. Ho usato solo uno di questi, PyMF, che puoi trovare su Google Code.

In modo che si può vedere come NNMA la sua magia, ecco mia semplice ma completa attuazione NNMA in 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) 

Per utilizzare questa funzione NNMA, basta passare in una matrice 2D (matrice) con uno "0" per ogni cella mancante (in altre parole, la matrice di dati, con uno "0" inserito per ciascun valore mancante):

>>> 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]]) 

Come potete vedere, i risultati non sono male, in particolare per un'implementazione molto semplice. Tutti gli elementi mancanti vengono popolati e il resto dei valori è molto vicino al valore corrispondente dalla matrice di dati originale, ad esempio, colonna 0, la riga 0 è 7.0 nella matrice di dati originale e 6.998 in quella approssimata.

Answer 2

KNN è solitamente sensibile alle #funzionalità. Nella vita reale, mi aspetto che tu abbia molti più libri.

vorrei provare a modificare lo spazio caratteristiche: invece di avere una funzione per ogni documento, forse la pena indagare utilizzando gli elenchi di libri come le caratteristiche.

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

Ora, è possibile definire la distanza per ogni caratteristica - forse utilizzando recall and precision tra ogni due elenchi di 2 utenti.

Un altro vantaggio di questo metodo è che si può facilmente dare peso alle caratteristiche - forse l'elenco dei libri classificato come 5 è più informativo poi quello classificato con 3?

Lo svantaggio è chiaro, non si otterrà alcun spinta se gli utenti A, B classificato un libro con 4,5 - ma può anche essere risolto con l'aggiunta di un altro elemento, confrontando questi elenchi tra due utenti ..

Disclaimer: Non ho mai testato questo metodo e non ho idea di come si comporterà, ma penso che sia un approccio che vale la pena di investigare. Penso che non ci sia un buon modo per determinare se questo suggerimento darà buoni risultati eccetto i test empirici, che possono essere fatti usando il set di allenamento cross-validation.

Answer 3

Il pezzo che ti manca è il metodo per misurare le distanze. La correlazione di Pearson è uno dei metodi più utilizzati. La distanza del Coseno è un'altra. La distanza L1 (somma assoluta delle differenze) di solito non dà buoni risultati.

Se google troverete qual è il modo consigliato di trattare con valori mancanti in base alla distanza similitudine che si usa. Ad esempio, in Pearson vengono utilizzati solo i libri classificati comunemente da due utenti per misurare la correlazione, quindi i valori mancanti vengono semplicemente ignorati. Ciò ha senso, come se una piccola percentuale di libri letti da due utenti fosse comune che molto probabilmente implica gusti diversi. Nella distanza Coseno i valori mancanti possono essere assunti pari a zero.

L'altro approccio comunemente utilizzato è quello di imputare valori mancanti. Ad esempio, potresti per prima cosa usare Pearson per trovare la somiglianza tra i libri e poi per ogni persona prevedere le classificazioni mancanti.

Answer 4

Il mio suggerimento è che si utilizza la decomposizione a valore singolo (SVD) per eseguire la riduzione di rango sul set di dati. Questo riempirà quei valori mancanti riducendo efficacemente il numero di caratteristiche che ogni libro ha da offrire. Questo è molto simile all'Analisi semantica latente, cercalo.