"Densifying" very large sparse matrices by rearranging rows/columns
<p>I have a very large sparse matrix (240k*4.5k, â¤1% non-zero elements), which I would like to "densify" by rearranging its rows and columns in a way that the upper left region is enriched in non-zero elements as much as possible. (To make it more manageable and visually assessable.) I would prefer <code>scipy</code> and related tools to do this.</p>

<ul>
<li>A good suggestion was already made <a href="http://stackoverflow.com/questions/15155276/rearrange-sparse-arrays-by-swapping-rows-and-columns">here</a> for a solution to "manually" swap rows/columns of sparse matrices, but it does not cover the challenge of identifying which rows/columns to swap to get an optimal enrichment (dense block) in the upper left corner.</li>
<li>Note that a simple sorting of rows/columns based on the number of non-zero elements does not solve the problem. (If I take <em>e.g.</em> the two rows with the most elements, there will not necessarily be any overlap between them in terms of where - <em>i.e.</em> in which columns - are the elements located.)</li>
<li>I'm also curious about the optimal sparse matrix representation in <code>scipy.sparse</code> for this task.</li>
</ul>

<p>Any suggestions or specific implementation ideas are welcome.</p>

<p>I finally ended up with the solution below:<br>
- First of all, based on the <a href="http://docs.scipy.org/doc/scipy/reference/generated/scipy.sparse.lil_matrix.html#scipy.sparse.lil_matrix" rel="nofollow">scipy documentation</a>, the LiL (linked list) format seems to be ideal for this sort of operations. (However I never did any actual comparison!)<br>
- I've used the functions described <a href="http://stackoverflow.com/a/15162737/6869965">here</a> to swap rows and columns.<br>
- Following the <a href="http://stackoverflow.com/a/39791339/6869965">suggestion of elyase</a>, I defined a 200*200 'window' in the 'upper left' corner of the matrix and implemented a 'window score' which was simply equal to the number of non-zero elements inside the window.<br>
- To identify the columns to swap, I checked which column contains the least non-zero elements inside the window, and which column contains the most non-zero elements outside the window. In case of a tie, the number of non-zero elements in the whole column was the tie-breaker (if this was tied as well, I've chosen randomly).<br>
- The method for swapping rows was identical.</p>

<pre><code>import numpy as np
import scipy.sparse
import operator

def swap_rows(mat, a, b):
    ''' See link in description'''

def swap_cols(mat, a, b) :
    ''' See link in description'''

def windowScore(lilmatrix,window):
    ''' Return no. of non-zero elements inside window. '''
    a=lilmatrix.nonzero()

    return sum([1 for i,j in list(zip(a[0],a[1])) if i&lt;window and j&lt;window])

def colsToSwap(lilmatrix,window):
    ''' Determine columns to be swapped.
    In: lil_matrix, window (to what col_no is it considered "left") 
    Out: (minColumnLeft,maxColumnRight) columns inside/outside of window w/ least/most NZ elements'''

    # Locate non-zero elements
    a=lilmatrix.nonzero()

    totalCols=lilmatrix.get_shape()[1]

    # Store no. of NZ elements for each column {in the window,in the whole table}, initialize with zeros
    colScoreWindow=np.zeros(totalCols)
    colScoreWhole=np.zeros(totalCols)

    ### Set colScoreWindow scores
    # Unique row indices
    rows_uniq={k for k in a[0] if k&lt;window}
    for k in rows_uniq:
        # List of tuples w/ location of each NZ element in current row
        gen=((row,col) for row,col in list(zip(a[0],a[1])) if row==k)
        for row,col in gen:
           # Increment no. of NZ elements in current column in colScoreWindow
            colScoreWindow[col]+=1

    ### Set colScoreWhole scores
    # Unique row indices
    rows_uniq={k for k in a[0]}
    for k in rows_uniq:
        # List of tuples w/ location of each NZ element in current row
        gen=((row,col) for row,col in list(zip(a[0],a[1])) if row==k)
        for row,col in gen:
            # Increment no. of NZ elements in current column in colScoreWhole
            colScoreWhole[col]+=1


    # Column inside of window w/ least NZ elements
    minColumnLeft=sorted(list(zip(np.arange(totalCols),colScoreWindow,colScoreWhole,np.random.rand(totalCols)))[:window], key=operator.itemgetter(1,2,3))[0][0]
    # Column outside of window w/ most NZ elements
    maxColumnRight=sorted(list(zip(np.arange(totalCols),colScoreWindow,colScoreWhole,np.random.rand(totalCols)))[window:], key=operator.itemgetter(1,2,3))[-1][0]

    return (minColumnLeft,maxColumnRight)

def rowsToSwap(lilmatrix,window):
    ''' Same as colsToSwap, adjusted for rows.'''
</code></pre>

<p>After running a suitable number of iterations of <code>colsToSwap</code> and <code>rowsToSwap</code> and the actual swapping functions, the number of non-zero elements inside the window converges to a maximum. Note that the method is not optimized at all, and there is much room for improvement. For example, I suspect that reducing the number of sparse matrix type conversions and/or the <code>a=lilmatrix.nonzero()</code> call would significantly speed it up.</p>

python numpy matrix scipy scikit-learn