行/列を並べ替えることで非常に大きなスパース行列を「緻密化」する

Question

私は非常に大きなスパース行列（240k * 4.5k、≤1％非ゼロ要素）を持っています。左上の領域が非ゼロ要素でできるだけ豊富になるような方法で列を作成します。 （管理しやすく視覚的に評価するため）scipyとそれに関連するツールが好きです。

• は良い提案がすでにスパース行列の「手動」のスワップ行/列を解決するためにhereとしたが、それは（密最適な濃縮を取得するために交換する行/列を特定の課題をカバーしていませんブロック）を左上隅に表示します。
• 非ゼロ要素の数に基づいて行/列を単純にソートしても問題は解決しないことに注意してください。 （私は例えば、ほとんどの要素を持つ 2つの行をを取る場合は、必ずしもという点で、それらの間の任意の重複ができなくなります - 列のつまり - 位置要素です。）
• 私も興味このタスクの最適なスパース行列表現はscipy.sparseです。

任意の提案や具体的な実装のアイデアを歓迎します。

Answer 1

最後に、 ：
- まず、scipy documentationに基づいて、LiL（リンクリスト）形式がこの種の操作に理想的なようです。 （ただし、実際の比較は一度も行っていませんでした）
- 私はhereの機能を使って行と列を入れ替えました。
に続いて、私は200×200の 'ウィンドウ'をマトリックスの左上隅に定義し、ウィンドウ内の非ゼロ要素の数と単純に等しい「ウィンドウスコア」を実装しました。
- スワップする列を特定するために、ウィンドウ内の非ゼロ要素が最も少ない列と、ウィンドウ外の最も非ゼロの要素を含む列を調べました。タイの場合、列全体の非ゼロ要素の数はタイブレーカー（これが結ばれていれば、ランダムに選択した）です。
- 行を交換する方法は同じでした。

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<window and j<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<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.''' 

colsToSwapとrowsToSwapの反復と実際のスワッピング機能の適切な数を実行した後、ウィンドウ内の非ゼロ要素の数が最大値に収束します。この方法はまったく最適化されておらず、改善の余地があることに注意してください。たとえば、疎な行列型変換の回数を減らすことや、a=lilmatrix.nonzero()呼び出しを減らすことで、速度が大幅に向上すると思われます。

Answer 2

スパース性を保持している行をすでに交換できるように見えます。行方不明の部分は行を並べ替えるアルゴリズムです。だからあなたはあなたに「左利き」のスコアを与える関数が必要です。

1. 最初にゼロ以外の要素のマスクを取得します（実際の値は考慮しませんが、ゼロ以外の値についてのみ考慮します）。

   def density(row, window): 
       padded = np.insert(row, 0, 0) 
       cumsum = np.cumsum(padded) 
       return (cumsum[window:] - cumsum[:-window])/window 
   

2. が最大左献上密度を有するカラムとしてleftnessスコアを計算する（右から見て）：推定値は列軸に沿って非ゼロ値の密度分布

def leftness_score(row): 
    n = len(a) 
    window = n/10 # 10 is a tuneable hyper parameter 
    smoothness = 1 # another parameter to play with 
    d = density(row) 
    penalization = np.exp(-smoothness * np.arange(n)) 
    return n - (penalization * d).argmax() 

このアルゴリズムは、限り、この密度の最大値があまりにも右端にはないような値の高い密度を有する行に高いスコアを与えます。いくつか考えてみましょう：密度の推定を改善し、別のペナルティ機能（ネクストの代わりに）でプレイし、予想されるソートなどを反映する合成データにパラメータをフィットさせます。