Scipy.sparse.csr_matrix: शीर्ष दस मान और सूचकांक कैसे प्राप्त करें?

Question

मेरे पास एक बड़ा csr_matrix है और मुझे शीर्ष दस मानों और प्रत्येक पंक्ति में उनके सूचकांक में रूचि है। लेकिन मुझे मैट्रिक्स में हेरफेर करने का एक अच्छा तरीका नहीं मिला।

यहाँ मेरे वर्तमान समाधान है और मुख्य विचार उन्हें पंक्ति दर पंक्ति कार्रवाई करने के लिए है:

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

ऐसा करने से, csr_matrix के फायदे पूरी तरह से नहीं किया जाता है। यह एक ब्रूट फोर्स समाधान की तरह है।

Answer 1

मुझे नहीं पता कि csr प्रारूप के फायदे इस मामले में हैं। निश्चित रूप से, सभी nonzero मान सरणी में एकत्र किए जाते हैं, संबंधित कॉलम इंडेक्स .indices में। लेकिन वे अलग-अलग लंबाई के ब्लॉक में हैं। और इसका मतलब है कि उन्हें समांतर या numpy सरणी के चरणों में संसाधित नहीं किया जा सकता है।

एक समाधान पैड उन सामान्य ब्लॉक ब्लॉक में ब्लॉक करता है। यही .toarray() करता है। फिर आप argsort(axis=1) or with argpartition` के साथ अधिकतम मान पा सकते हैं।

दूसरा उन्हें पंक्ति आकार के ब्लॉक में तोड़ना है, और उनमें से प्रत्येक को संसाधित करना है। .getrow के साथ आप यही कर रहे हैं। उन्हें तोड़ने का एक और तरीका lil प्रारूप में परिवर्तित हो गया है, और .data और .rows सरणी के उपन्यासों को संसाधित करता है।

ufuncreduceat विधि का उपयोग करने का एक संभावित तीसरा विकल्प है। यह आपको सरणी के अनुक्रमिक ब्लॉक के लिए ufuncreduction विधियों को लागू करने देता है। ufuncnp.add जैसे स्थापित हैं जो इसका लाभ उठाते हैं। argsort ऐसा कोई फ़ंक्शन नहीं है। लेकिन पाइथन फ़ंक्शन से ufunc बनाने का एक तरीका है, और नियमित पायथन पुनरावृत्ति पर कुछ मामूली गति प्राप्त करें। [मुझे हाल ही में एक SO सवाल देखने की ज़रूरत है जो इसे दर्शाती है।]

मैं इनमें से कुछ को सरल कार्य, पंक्तियों के साथ योग के साथ चित्रित करूंगा।

यदि A2 एक सीएसआर मैट्रिक्स है।

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 

A2.sum(axis=1) मैट्रिक्स गुणा के रूप में लागू किया गया है। यह सॉर्ट समस्या के लिए प्रासंगिक नहीं है, लेकिन अभी भी सारांश समस्या को देखने का एक दिलचस्प तरीका है। याद रखें csr प्रारूप कुशल गुणा के लिए विकसित किया गया था।

एक मेरे वर्तमान नमूना मैट्रिक्स (एक और इतना विरल प्रश्न के लिए बनाया)

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

के लिए कुछ तुलनात्मक बार

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 

बाकी सब कुछ 1ms या उससे अधिक है।

मैं अपने एक पंक्ति समारोह, जैसे कुछ विकसित करने पर ध्यान केंद्रित कर सुझाव देते हैं:

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 

फिर देखते हैं कि कैसे इन पुनरावृत्ति तरीकों में से एक में फिट हैं। tolil() सबसे अधिक आशाजनक लग रहा है।

मैंने इन परिणामों को एकत्रित करने के सवाल को संबोधित नहीं किया है। क्या उन्हें सूचियों की सूची, 10 कॉलम के साथ सरणी, प्रति पंक्ति 10 मानों के साथ एक और स्पैर मैट्रिक्स होना चाहिए?

---

sorting each row of a large sparse & saving top K values & column index - वापस कई वर्षों से इसी तरह के सवाल, लेकिन अनुत्तरित।

Argmax of each row or column in scipy sparse matrix - की पंक्तियों के लिए argmax मांगने वाला हालिया प्रश्न। मैं कुछ मुद्दों पर चर्चा करता हूं।

how to speed up loop in numpy? - बनाने के लिए np.frompyfunc का उपयोग करने का उदाहरण। मुझे नहीं पता कि परिणामी फ़ंक्शन में .reduceat विधि है या नहीं।

Increasing value of top k elements in sparse matrix - सीएसआर के शीर्ष के तत्व प्राप्त करें (पंक्ति से नहीं)। argpartition के लिए केस।

---

पंक्ति योग 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 

सम्मानजनक गति है यही कारण है कि। लेकिन मैं एक बाइनरी फ़ंक्शन लिखने का तरीका नहीं सोच सकता (2 तर्कों को लेता है) जो argsort को कमी के माध्यम से कार्यान्वित करेगा। तो यह शायद इस समस्या के लिए एक deadend है।

Answer 2

बस मूल प्रश्न (मेरे जैसे लोग हैं, जो इस सवाल कॉपी-पास्ता की तलाश में पाया के लिए) जवाब देने के लिए, यहाँ एक समाधान बहु का उपयोग कर lil_matrix को बदलने, और पंक्तियों पर पुनरावृत्ति की @ hpaulj के सुझाव के आधार पर है

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