スパース行列とnumpy配列の使用

Question

私は、Pythonでワード数を持ついくつかのnumpy配列を作成しています。行はドキュメントであり、列はワードXのカウントです。ゼロカウントが多い場合、これらを処理するときにスパース行列を使用することをおすすめします。さらに、例えばクラシファイアで。 Sciggit logistic regression classifierに疎な行列を並べるときには、それほど大きな違いはありませんでした。

• Wikipediaが

  スパース行列は要素のほとんどが

  ゼロが適切な方法を決定するためにということですされた行列であると言う：だから私は約3つのことを思っていましたスパース行列 フォーマットを使用する場合 - 値の50％以上がゼロになるとすぐに？ちょうどその場合に使用する意味は ですか？

• 疎な行列は、私のような仕事でパフォーマンスを助けますか？ 特にnumpyの配列や標準リストと比較しますか？
• これまでのところ、私はnumpyの配列にデータを収集し、Scipyの csr_matrixに変換しました。それはそれを行う正しい方法ですか？私は を土台から疎な行列を作る方法を考え出すことができず、その は不可能かもしれません。

ご協力いただきありがとうございます。

Answer 1

疎行列パッケージ、およびMATLABの同様のものは、大きな疎線形方程式（例えば、有限差分および有限要素実装）を解くなど、線形代数問題から開発されたアイデアに基づいています。したがって、マトリックス製品（数値配列の場合は dot製品）や方程式ソルバなどの要素がよく開発されています。

私の大まかな経験は、疎なcsrマトリックス製品は、同等の高密度のdot操作よりも高速であるために1％のスパース性がなければならないということです。言い換えれば、99個のゼロごとに1つの非ゼロ値です。 （ただし、以下のテストを参照）

しかし、人々はまた、メモリを節約するために希薄な行列を使用しようとします。しかし、そのような行列は3列の値を格納しなければならないことに留意してください（少なくともcoo形式）。したがって、メモリの節約を開始するには、希薄さは1/3未満でなければなりません。明らかに、密な配列を最初に構築し、その配列から疎な配列を作成すると、メモリを節約することはできません。

scipyパッケージには多くのスパースフォーマットが実装されています。 coo形式は、理解して作成するのが最も簡単です。ドキュメントに従ってビルドし、その.data、.row、および.col属性（3 1d配列）を見てください。

csrおよびcscは、通常coo形式から作成され、データを少し圧縮するため、理解が少し難しくなります。しかし、彼らは数学の機能のほとんどを持っています。

csrの形式をインデックスすることもできますが、一般的にこれは等価の密行列/配列の場合よりも遅くなります。値の変更（特に0から非ゼロへの変更）、連結、インクリメンタルな成長など、他の操作も遅くなります。

lil（リストのリスト）もわかりやすく、段階的な構築に最適です。 dokは実際には辞書サブクラスです。

重要な点は、疎な行列が2dに制限され、多くの点でnp.matrixクラスのように振る舞います（サブクラスではありませんが）。

scikit-learnとsparseを使用して他の質問を検索すると、これらのマトリックスを使用する際の賛否両論を見つける最良の方法です。私はいくつかの質問に答えましたが、私は「疎」側が「学習」側よりも優れていることを知っています。私は彼らが役に立つと思うが、フィット感がいつもベストではないという感覚がある。カスタマイズはlearn側にあります。これまでのところ、sparseパッケージはこのアプリケーション用に最適化されていません。

---

私は指定されたスパースとスパース行列を作成するsparse.random方法を使用して、いくつかの行列積テストを試みました。スパース行列の乗算は、予想よりも良好に実行されました。

In [251]: M=sparse.random(1000,1000,.5) 

In [252]: timeit M1=M*M 
1 loops, best of 3: 2.78 s per loop 

In [253]: timeit Ma=M.toarray(); M2=Ma.dot(Ma) 
1 loops, best of 3: 4.28 s per loop 

サイズの問題です。小さい行列に対して密dotは

In [255]: M=sparse.random(100,100,.5) 

In [256]: timeit M1=M*M 
100 loops, best of 3: 3.24 ms per loop 

In [257]: timeit Ma=M.toarray(); M2=Ma.dot(Ma) 
1000 loops, best of 3: 1.44 ms per loop 

速いですが、追加のノート、scipyのダウンロードドキュメントパトリック・リンクは、実際にスパース行列を構築する方法の下部にあるいくつかの例を持っているためにとインデックス

In [268]: timeit M.tocsr()[500,500] 
10 loops, best of 3: 86.4 ms per loop 

In [269]: timeit Ma[500,500] 
1000000 loops, best of 3: 318 ns per loop 

In [270]: timeit Ma=M.toarray();Ma[500,500] 
10 loops, best of 3: 23.6 ms per loop 

Answer 2

スパース行列は、要素のほとんどがゼロ された行列は、スパース行列形式を使用するかを決定するために、適切な方法である - とすぐに>値の50％がゼロでありますか？または、ちょうどその場合に使用するのが理にかなっていますか？

一般的なルールはありません。これは後で正確な使用法に依存します。モデルの複雑さは、まばらな行列に基づいて計算しなければならず、そうでなければ、「スイートスポット」を見つけることができます。これは、サンプル数とディメンションの両方に依存します。一般に、想定すると、それはしばしば、Xはデータ行列NのXDであるフォーム

X' W 

の行列乗算に帰着、およびWは、スパースながらK.が結果的に「密」は乗算を、NdK時間がかかり、いくつかの重み行列DXありますあなたの平均1行あたりのスパース性がpであるのはNpdKです。したがって、希少性が50％であれば、2倍近くの高速動作が期待できます。より困難な部分は、密接に最適化された密集に基づくのではなく、疎アクセスのオーバーヘッドを推定することです。

私のようなタスクで、疎なマトリックスがパフォーマンスを助けているのはどれくらいですか？特にnumpy配列や標準リストと比較してですか？

LRの特定のケースでは、これは密度の高いフォーマットよりも数倍高速かもしれませんが、違いを観察するには高次元（> 100）のデータが大量（> 1000）必要です。

これまでのところ、私はnumpy配列に自分のデータを集めてから、Scipyのcsr_matrixに変換しました。それはそれを行う正しい方法ですか？私は最初から疎な行列を作る方法を考え出すことができず、それは不可能かもしれません。

いいえ、それは良いアプローチではありません。たとえば、まず最初に辞書を作成してから変換するなどして、 "最初から"構築することができます。最初は密な行列を使わずに疎行列を構築する方法はたくさんあります。