Scipy.sparse.csr_matrix: Jak zdobyć dziesięć najlepszych wartości i indeksów?

Question

Mam duży csr_matrix i interesują mnie dziesięć najlepszych wartości i ich indeksy w każdym wierszu. Ale nie znalazłem porządnego sposobu manipulowania matrycą.

Oto mój obecny rozwiązanie i główną ideą jest, aby przetworzyć je wiersz po wierszu:

row = csr_matrix.getrow(row_number).toarray()[0].ravel() 
top_ten_indicies = row.argsort()[-10:] 
top_ten_values = row[row.argsort()[-10:]] 

Dzięki temu zalety csr_matrix nie jest w pełni wykorzystywany. To bardziej przypomina brutalne rozwiązanie.

Answer 1

Nie widzę, jakie są w tym przypadku zalety formatu csr. Oczywiście, wszystkie niezerowe wartości są zbierane w jednej macierzy .data, z odpowiednimi indeksami kolumn w .indices. Ale są one w blokach o różnej długości. Oznacza to, że nie mogą być przetwarzane równolegle lub z krokami macierzy.

Jednym z rozwiązań jest umieszczenie tych bloków we wspólnych blokach długości. Tak robi .toarray(). Następnie możesz znaleźć maksymalne wartości z argsort(axis=1) or with argpartition`.

Innym jest rozbicie ich na bloki o rozmiarach rzędów i przetworzenie ich. To właśnie robisz z .getrow. Innym sposobem ich rozbicia jest konwersja do formatu lil i przetworzenie podlisty z tablic .data i .

Ewentualną trzecią opcją jest użycie metody ufuncreduceat. Umożliwia to stosowanie metod do bloków sekwencyjnych tablicy. Istnieją zalety: ufunc, takie jak np.add, które wykorzystują to. argsort nie jest taką funkcją. Ale istnieje sposób na skonstruowanie ufunc z funkcji Pythona i uzyskanie niewielkiej prędkości w porównaniu do zwykłej iteracji Pythona. [Muszę przejrzeć ostatnie pytanie SO, które ilustruje to.]

Zilustruję niektóre z nich prostszą funkcją, sumując wiersze.

Jeśli A2 jest matrycą csr.

A2.sum(axis=1) # the fastest compile csr method 
A2.A.sum(axis=1) # same, but with a dense intermediary 
[np.sum(l.data) for l in A2] # iterate over the rows of A2 
[np.sum(A2.getrow(i).data) for i in range(A2.shape[0])] # iterate with index 
[np.sum(l) for l in A2.tolil().data] # sum the sublists of lil format 
np.add.reduceat(A2.data, A2.indptr[:-1]) # with reduceat 

jest zaimplementowany jako multiplikacja macierzy. Nie ma to związku z problemem sortowania, ale nadal jest interesującym sposobem spojrzenia na problem sumowania. Pamiętaj, że opracowano format csr dla wydajnego mnożenia.

Dla mojego obecnego matrycy próbki (stworzonej dla siebie tak rzadki pytanie)

<8x47752 sparse matrix of type '<class 'numpy.float32'>' 
    with 32 stored elements in Compressed Sparse Row format> 

kilka razy porównawcze są

In [694]: timeit np.add.reduceat(A2.data, A2.indptr[:-1]) 
100000 loops, best of 3: 7.41 µs per loop 

In [695]: timeit A2.sum(axis=1) 
10000 loops, best of 3: 71.6 µs per loop 

In [696]: timeit [np.sum(l) for l in A2.tolil().data] 
1000 loops, best of 3: 280 µs per loop 

Wszystko inne jest 1ms lub więcej.

Proponuję koncentrując się na rozwoju swojej funkcji jednym rzędzie, coś jak:

def max_n(row_data, row_indices, n): 
    i = row_data.argsort()[-n:] 
    # i = row_data.argpartition(-n)[-n:] 
    top_values = row_data[i] 
    top_indices = row_indices[i] # do the sparse indices matter? 
    return top_values, top_indices, i 

Następnie zobaczyć, jak gdyby ataki w jednej z tych metod iteracyjnych. tolil() wygląda najbardziej obiecująco.

Nie odpowiedziałem na pytanie, jak zebrać te wyniki. Czy powinny to być listy list, tablica z 10 kolumnami, inna rzadka macierz z 10 wartościami na wiersz itp.?

---

sorting each row of a large sparse & saving top K values & column index - Podobne pytanie od kilku lat wstecz, ale bez odpowiedzi.

Argmax of each row or column in scipy sparse matrix - Ostatnie pytanie dotyczące argmax dla wierszy csr. Omawiam niektóre z tych samych problemów.

how to speed up loop in numpy? - przykład użycia np.frompyfunc do utworzenia ufunc. Nie wiem, czy wynikowa funkcja ma metodę .reduceat.

Increasing value of top k elements in sparse matrix - uzyskać najlepsze k elementów CSR (a nie z rzędu). Sprawa dla argpartition.

---

Sumowanie rząd realizowane z np.frompyfunc:

In [741]: def foo(a,b): 
    return a+b 
In [742]: vfoo=np.frompyfunc(foo,2,1) 
In [743]: timeit vfoo.reduceat(A2.data,A2.indptr[:-1],dtype=object).astype(float) 
10000 loops, best of 3: 26.2 µs per loop 

To poważny prędkość. Ale nie mogę wymyślić sposobu zapisu funkcji binarnej (przyjmuje 2 argumenty), które zaimplementowałyby argsort poprzez redukcję. Jest to prawdopodobnie śmiertelny problem dla tego problemu.

Answer 2

Wystarczy odpowiedzieć na pierwotne pytanie (dla ludzi takich jak ja, którzy znaleźli na to pytanie szuka kopiowaniem makaronu), oto rozwiązanie wykorzystujące wieloprocesorowe oparte na użytkownika @ hpaulj sugestią konwersji do lil_matrix i iteracji po wierszach

from multiprocessing import Pool 

def _top_k(args): 
    """ 
    Helper function to process a single row of top_k 
    """ 
    data, row = args 
    data, row = zip(*sorted(zip(data, row), reverse=True)[:k]) 
    return data, row 

def top_k(m, k): 
    """ 
    Keep only the top k elements of each row in a csr_matrix 
    """ 
    ml = m.tolil() 
    with Pool() as p: 
     ms = p.map(_top_k, zip(ml.data, ml.rows)) 
    ml.data, ml.rows = zip(*ms) 
    return ml.tocsr()