skuteczny sposób obliczyć odległość między kombinacjami kolumn ramowych pandy

Question

Zadanie

Mam dataframe pandy gdzie:

• kolumny są nazwy dokumentu
• wiersze są słowa zawarte w tych dokumentach
• numery wewnątrz komórek ramki są miarą trafności słowa (liczba słów, jeśli chcesz zachować proste)

trzeba obliczyć nową macierz doc1-doc podobieństwa gdzie:

• wierszy i kolumn nazwy dokument
• komórki wewnątrz ramki są miarą podobieństwa (1 - cos odległości) pomiędzy dwa dokumenty:

Odległość cosinus jest wygodnie dostarczana przez script.spatial.distance.cosine.

Jestem obecnie to robi:

1. użytku itertools stworzyć listę wszystkich 2-kombinacje nazw dokumentów (kolumny dataframe Names)
2. pętla ponad nich i stworzyć aktualizację słownika {doc1 {zmienna doc2: podobieństwo}}
3. po pętli, tworzenie nowej ramki przy użyciu pandas.DataFrame (dict)

problem

Ale to zajmuje bardzo dużo czasu. Poniżej pokazano aktualną prędkość MacBooka Pro 13 z 16GB pamięci RAM i 2,9 GHz i5cpu z najnowszym anakondy Pythona 3.5 ... czas kreślenia przeciwko kombinacjom dokumentów.

Widać, że 100.000 kombinacje trwa 1200 sekund. Ekstrapolacja tego do mojego korpusu dokumentów , która tworzy 3 1,549,596, zajęłaby 5 dni w celu obliczenia tej macierzy podobieństwa!

Jakieś pomysły?

• I previously dynamicznie tworzenie df.ix dataframe [doc1, zmienna doc2] = podobieństwa .. co było bardzo znacznie wolniej.
• Zastanawiam się nad numba @ git, ale zawiedzie się w strukturach danych pand.
• nie mogę znaleźć wbudowaną funkcję, która będzie wykonywać wszystkie prace wewnętrznie (w C?)
• Co muszę zrobić taktycznie jest losowo próbka dokumenty do stworzenia znacznie mniejszy zestaw do pracy z .. obecnie ułamek 0,02 prowadzi do około 20 minut obliczeń!

Oto kod (github)

docs_combinations = itertools.combinations(docs_sample, 2) 
for doc1, doc2 in docs_combinations: 
    # scipy cosine similarity function includes normalising the vectors but is a distance .. so we need to take it from 1.0 
    doc_similarity_dict[doc2].update({doc1: 1.0 - scipy.spatial.distance.cosine(relevance_index[doc1],relevance_index[doc2])}) 
    pass 

#convert dict to pandas dataframe 
doc_similarity_matrix = pandas.DataFrame(doc_similarity_dict) 

Prosty przykład

@MaxU zadawane na przykład ilustracyjny.

związek macierzy (WordCount tutaj, żeby utrzymać proste)

...  doc1 doc2 doc3 
wheel 2. 3. 0. 
seat 2. 2. 0. 
lights 0. 1. 1. 
cake 0. 0. 5. 

obliczono macierz podobieństwa oparte na 2-kombinacjach (doc1, zmienna doc2), (zmienna doc2, doc3), (doc1, doc3)

...  doc2 doc3 
doc1 0.9449 0. 
doc2 -  0.052 

Take że wartość górnego lewego 0,889 .. ów iloczyn skalarny (2 * 3 * 2 + 2 + 0 + 0) = 10, ale znormalizowane o długości wektorów ... więc dzielenie przez sqrt (8) i sqrt (14) daje 0.9449. Widać, że nie ma podobieństwa między doc1 i doc3 .. iloczyn jest zerowy.

Skala ta z 3 dokumentów z 4 słów ... do dokumentów, który tworzy 3 kombinacje ...

Answer 1

Numba będzie dobrym rozwiązaniem dla tego produktu. Jak myślę, wiesz, to nie obsługuje Pandas DataFrames, ale jest zbudowany wokół tablic NumPy. Nie stanowi to problemu - możesz łatwo i szybko przekonwertować swoją ramkę DataFrame na tablicę 2D i przekazać ją do funkcji Numba (która będzie w zasadzie tym, co już masz, po prostu ozdobionym na górze @njit).

Należy również zauważyć, że zamiast dict-of-dicts dla wyników, można użyć jednego trójkąta z kwadratowej macierzy je przechowywać:

 doc1 doc2 doc3 
doc1 NAN NAN NAN 
doc2 ... NAN NAN 
doc3 ... ... NAN 

---

Edit: Masz teraz wprowadziły go używając Numby, ale dostałem tylko 2,5-krotne przyspieszenie. Pobiegłem kilka eksperymentów i znalazł wielką wygraną:

In [66]: x = np.random.random((1000,1000)) 

In [67]: y = np.array(x, order='F') 

In [68]: %timeit similarity_jit(x) 
1 loop, best of 3: 13.7 s per loop 

In [69]: %timeit similarity_jit(y) 
1 loop, best of 3: 433 ms per loop 

Oznacza to, że Twój algorytm będzie znacznie, znacznie szybciej, jeśli działają na sąsiadujących fragmentów danych, ze względu na buforowanie. Ponieważ jądro twojego algorytmu to numpy.dot(m[:,i], m[:,j]), a m[:,i] przyjmuje jedną kolumnę, lepiej jest najpierw zorientować swoje dane w "Fortran order" (kolejność kolumna-główna), tak aby m[:,i] dała jedną ciągłą tablicę (ponieważ tablica jest ułożona "transponowana" w pamięć).

Answer 2

To jest tak skuteczne, jak mogę zrobić algorytm bez przechodzenia w proces wieloprocesowy (bleh). Funkcja używa numpy array dla wszystkich obliczeń.

def cos_sim(data_frame): 
    # create a numpy array from the data frame 
    a = data_frame.values 
    # get the number of documents 
    n = a.shape[-1] 
    # create an array of size docs x docs to populate 
    out = np.ravel(np.zeros(shape=(n, n))) 

    for i in range(n): 
     # roll the array one step at a time, calculating the cosine similarity each time 
     r = np.roll(a, -i, axis=1) 
     cs = np.sum(a[:,:n-i]*r[:,:n-i], axis=0)/(
       np.sqrt(np.sum(a[:,:n-i]*a[:,:n-i], axis=0)) 
       *np.sqrt(np.sum(r[:,:n-i]*r[:,:n-i], axis=0))) 

     # push the cosine similarity to the output array's i-th off-diagonal 
     out[i:n*n-i*n:n+1] = cs 

    return out.reshape((n,n))