レコメンデーションとクラスタリングを例にして「密な行列」と「疎な行列」について説明する
ここまでのログでは、Hadoop MapReduceで「密な行列（Dense Matrix）」の行列積を計算することを考えてきた。多変量解析の多くは「密な行列」を仮定しておけば、理論的な演算に問題が生じることはない（これが、「密」にこだわってきた理由）。
ただ、機械学習のエリアでは、「疎な行列（スパース行列：Sparse Matrix）」が前提にされることが多い。
読んでくださっている方の中には、「なんで密とか疎とか言ってるんだ？」という方がいらっしゃると思うので、今回のログでは、機械学習を例にして「密な行列」と「疎な行列」について説明したいと思う。
最初にちょっとだけ「数式めいたもの」が出てくるが、基本的には言葉で説明したいと思う。
まず、「疎」と「密」というのは、「数字がいっぱい詰まっているか」ということ（密度）を表している。
いつも通り、観測値が以下の形式で得られているとする。列が変量を表し、行がサンプル（各々の変量についてデータを得た個体 etc）を表す。
これを以下のように行列表記する。
今、m=4, n=4としたとき、以下のような（数字の詰まった行列）を「密な行列」という。
これにたいして、０の数が多い行列を「疎な行列」という。
統計学でいう、回帰分析や主成分分析といった多変量解析を行う場合には、観測値が密な行列として得られると仮定することが多い。
これに対して、協調フィルタリングやクラスタリングといったエリアでは、観測値としては疎な行列を仮定する。
なぜなのかというと、以下のように考えると納得がいくと思う。
協調フィルタリング（IT的にはリコメンデーションと同じ意味で用いられている）の場合、多くの評価データから「ある人に、何か買ってくれるようにアイテムをリコメンドする」というのが目的となる。
このとき、アイテム（数千〜数万オーダー）に対して、既存のお客様（何万〜何億人）がどのような評価をしてきたか、というデータが観測値になる。
ユーザーベースのリコメンデーションの場合、アイテムが変量、サンプルがお客様ということになって、サンプル間（お客様間）の評価の類似性をもってリコメンデーションする。たとえば、AさんとBさんは評価が似ていて、あるアイテムMをBさんが高評価している。しかもAさんはまだ購入していない、というときに、AさんにアイテムMをリコメンドする。
上の状況では、全てのアイテムを持っているお客様は殆どおらず、ほぼ全てのお客様は「いくつかのアイテム」についてのみ評価データを与えているであろう、ことがわかる。
したがって、観測値行列Xは、中身が殆ど０の行列、つまり、疎な行列を仮定するのが妥当である。
アイテムベースのリコメンドも、ユーザーベースと殆ど同じだが、アイテム間の類似性をもとにリコメンドを行う。
つまり、アイテムMとアイテムNでは、お客様の評価が非常ににている。AさんはアイテムMに高評価をしているが、アイテムNを持っていない。だから、アイテムNをリコメンドするという理屈になる。
この場合には、変量はお客様、サンプルはアイテムとみたてた行列Xをつくる。この場合も疎な行列になるのは明らかである。
追記：
「ユーザーベースのリコメンデーションの場合、アイテムが変量、サンプルがお客様」といった表現をしたが、
ユーザーベースの協調フィルタリングでは、お客様をアイテム数次元のプロットとして類似度を計り、アイテムベースでは、アイテムをお客様数次元のプロットとして類似度をはかる。
といった方が直感的でためになる。
また、クラスタリングの世界では、疎な行列に縛られる理由はないのだが、ITの世界では、この手法が「文書の分類で使える」とされているため（Mahout in Action のサンプルもそのようになっている）に、以下のような理由で疎な行列が仮定される。
文書の類似度をはかるには、語彙の出現頻度を計って、その類似度で文書を分類する、というアプローチが一般的である（非階層なクラスタリング手法。k-means法など）。
この場合、語彙が上でいう変量となって、文書がサンプルとなる（追記での言い方をすれば、文書を語彙数次元内のプロットとしてとらえる）。
細かい話をすれば、語彙に関しては、
と行った処理を行ったのちに、類似度を計る。
いずれにせよ、このような条件では、観測値Xの中は殆どが０になってしまう。（つまり、疎な行列になる）
以前のログで、Twitterにある語彙のカウントをしたが、文書をTweetに変えても、まったく同じことがいえる（ただし、SNSなど、ライフログ関連ではスパムが多いため、語彙の前処理が大変になる）
以上は、「モデリングによって観測値行列の性質が異なってしまう」という話だったが、困ったことにプログラムの実装面でも、「疎」と「密」では大きく異なった実装になってしまう。
たとえば、以前のログで、密な行列の表現（入力データ）を
行インデックス 列インデックス 観測値
とした場合に、「行列積の計算が非常に遅い（＝使い物にならない）」という結果を得た。
これは、１つには、改善した入力データ（行列をそのまま入力データとする）と比較して、データが３倍になってしまうためである。
だが、疎な行列の場合には、０ではない要素に対して上記のフォーマットを利用した方が（０を並べるよりも）データサイズを小さくすることができる場合が多いため、この形式が使われることが多い。
つまり、先の例は、「密な行列だから失敗した」ということで、逆を言えば、「疎」な行列のプログラムをそのまま持ちこむと、「密」な行列では失敗してしまう、という例題になっている。
Mahoutでは、RandomAccessSparceVector.javaというクラスが、ハッシュマップをもとに実装されており、Sequentialな利用用途用に、SequetialAccessSparseVector.javaというクラスが、配列で実装されている。（因に、DesnseVectorも配列で実装されている。）
以上のように、分析モデル（回帰分析 vs 協調フィルタリング）によってずいぶんと数学的な仮定を変えなくてはならないし、それによって、数値解析的なアルゴリズムが全く違うものになってしまう。古い歴史をもつ数値解析の世界では、（コンピュータの性能的な制約が故に）大きな行列演算でもスパースならできますよ、という理論的発展をしてきたように感じる部分が否めない。
あれこれごちゃごちゃ書いてしまったが、たしかに「データサイエンティストが必要」というのもうなずける気がする。
ついでに「類似度」の話を書こうと思っていたが、日を改めたいと思う。
